Skip to content
กลับไปยังผลการค้นหา

การจำลองคิว — การสร้างแบบจำลองและการวิเคราะห์ระบบการรอคอย

ผู้เสนอ
Agner Krarup Erlang
ปี
1909
ประเภท
Stochastic simulation / analytical modeling
กลุ่มวิธี
Simulation / optimization

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

การจำลองคิวเป็นการผสมผสานทฤษฎีคิวแบบดั้งเดิมเข้ากับการจำลองเหตุการณ์แบบไม่ต่อเนื่อง (discrete-event simulation) เพื่อสร้างแบบจำลองระบบที่หน่วย (entities) เข้ามา รอรับบริการ และออกจากระบบ การจำลองนี้สามารถคาดการณ์ตัวชี้วัดประสิทธิภาพ เช่น เวลาเฉลี่ยในการรอ, ความยาวคิว, และอัตราการใช้ประโยชน์ของเซิร์ฟเวอร์ ซึ่งช่วยในการวางแผนกำลังการผลิตและการระบุคอขวดในระบบบริการ, การผลิต, การดูแลสุขภาพ, และระบบเครือข่าย

แนวคิดเบื้องหลังวิธีการ

เมื่อใดก็ตามที่ลูกค้าต้องรอคิว ไม่ว่าจะเป็นที่ธนาคาร, ห้องฉุกเฉินของโรงพยาบาล, หรือในเครือข่ายคอมพิวเตอร์ จะเกิดคิวขึ้น พฤติกรรมของระบบขึ้นอยู่กับอัตราการเข้ามาของหน่วย, ระยะเวลาที่ใช้ในการให้บริการ, และจำนวนเซิร์ฟเวอร์ที่มีอยู่ การจำลองคิวสามารถจับพลวัตเหล่านี้ได้โดยการจำลองกระบวนการเข้ามาและการให้บริการแบบสุ่มซ้ำหลายครั้ง เพื่อวัดค่าเฉลี่ยของเวลาในการรอและการติดขัด (congestion) แตกต่างจากสูตรสำเร็จ การจำลองสามารถจัดการกับตารางเวลาที่ซับซ้อน, ประเภทคิวหลายแบบ, และการแจกแจงที่ไม่เป็นมาตรฐาน ซึ่งสมการรูปแบบปิด (closed-form equations) ไม่สามารถแก้ได้

ประวัติศาสตร์

ทฤษฎีคิวถูกก่อตั้งขึ้นโดยวิศวกรชาวเดนมาร์ก Agner Krarup Erlang ในปี 1909 ขณะที่ศึกษาความแออัดของชุมสายโทรศัพท์ที่บริษัท Copenhagen Telephone Company สูตร Erlang-B และ Erlang-C ของเขายังคงใช้มาจนถึงปัจจุบัน สาขานี้ได้รับการจัดระบบโดย Kendall (1953) ด้วยสัญกรณ์ของเขา และโดย Kleinrock (1975) สำหรับเครือข่ายคอมพิวเตอร์ การวิเคราะห์คิวโดยใช้การจำลองเริ่มปรากฏขึ้นเมื่อคอมพิวเตอร์ทำให้การสร้างแบบจำลองเชิงสุ่มขนาดใหญ่เป็นไปได้ในช่วงทศวรรษ 1960-1970

ควรใช้เมื่อใด

ใช้การจำลองคิวเมื่อระบบเกี่ยวข้องกับหน่วยที่รอทรัพยากรที่ใช้ร่วมกันและคุณต้องการการคาดการณ์ประสิทธิภาพเชิงปริมาณ — เช่น ศูนย์บริการลูกค้า, แผนกฉุกเฉิน, สายการผลิต, เครือข่ายคอมพิวเตอร์, ศูนย์โลจิสติกส์ ควรเลือกใช้การจำลองแทนแบบจำลองคิวเชิงวิเคราะห์เมื่อการแจกแจงไม่เป็นแบบมาร์คอฟ (non-Markovian), กระบวนการให้บริการขึ้นอยู่กับสถานะ, หรือมีคิวหลายคิวที่โต้ตอบกันจนทำให้การหาผลเฉลยแบบรูปแบบปิดเป็นไปไม่ได้ **ไม่ควร** ใช้เมื่อระบบไม่มีพลวัตการติดขัด, เมื่อการจัดตารางเวลาแบบกำหนดเวลา (deterministic scheduling) เพียงพอ, หรือเมื่อข้อมูลตัวอย่างเกี่ยวกับเวลาการเข้ามาและเวลาการให้บริการมีน้อยเกินไปที่จะปรับการแจกแจงอินพุตได้อย่างน่าเชื่อถือ

ข้อจำกัดและข้อควรพิจารณา

  • ต้องการข้อมูลเชิงประจักษ์ที่เพียงพอเพื่อปรับการแจกแจงเวลาการเข้ามาและเวลาการให้บริการ; แบบจำลองอินพุตที่ไม่ดีจะให้ผลลัพธ์ที่ทำให้เข้าใจผิด
  • การประมาณค่าสภาวะคงตัวต้องการการลบช่วงเริ่มต้น (warm-up period) และการวางแผนการจำลองซ้ำอย่างระมัดระวัง ซึ่งไม่ใช่เรื่องง่าย
  • เวลาในการรันการจำลองอาจยาวนานสำหรับเครือข่ายที่ซับซ้อนหรือการประมาณค่าเหตุการณ์ที่เกิดขึ้นได้ยาก
  • ผลลัพธ์เป็นค่าประมาณเชิงสุ่มพร้อมช่วงความเชื่อมั่น ไม่ใช่ค่าที่แน่นอน — ต้องการการตีความทางสถิติ
  • การตรวจสอบความถูกต้องของแบบจำลองเป็นสิ่งจำเป็นแต่ก็ยาก; แบบจำลองที่ดูสมเหตุสมผลอาจให้ผลลัพธ์ที่เอนเอียงอย่างเป็นระบบหากสมมติฐานผิดพลาด

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • จัดการกับการแจกแจงเวลาการเข้ามาและเวลาการให้บริการที่ซับซ้อนและไม่เป็นแบบมาร์คอฟ ซึ่งสูตรคิวแบบรูปแบบปิดไม่สามารถจัดการได้
  • สร้างแบบจำลองเครือข่ายเซิร์ฟเวอร์หลายตัว, คิวหลายตัว พร้อมการส่งต่อ, ลำดับความสำคัญ, และบัฟเฟอร์จำกัด ในกรอบการทำงานที่เป็นหนึ่งเดียว
  • กฎของลิตเติล (Little's Law) ให้การตรวจสอบความสอดคล้องภายในที่ไม่ขึ้นกับการสมมติฐานการแจกแจง
  • สนับสนุนการวิเคราะห์สถานการณ์สมมติ (what-if analysis) และการวางแผนกำลังการผลิต โดยการเปลี่ยนแปลงพารามิเตอร์ของระบบโดยไม่ต้องทำการทดลองจริง
  • ผลลัพธ์ช่วงความเชื่อมั่นให้การวัดปริมาณความไม่แน่นอนที่เข้มงวดทางสถิติสำหรับการตัดสินใจ
  • ได้รับการตรวจสอบความถูกต้องอย่างกว้างขวางในหลากหลายโดเมน: โทรคมนาคม, การดูแลสุขภาพ, การผลิต, และการขนส่ง

การประยุกต์ใช้

  • การวางแผนกำลังการผลิตของแผนกฉุกเฉินโรงพยาบาลและการปรับปรุงประสิทธิภาพการจัดลำดับความสำคัญของการคัดกรองผู้ป่วย
  • การวิเคราะห์การจัดกำลังคนของศูนย์บริการลูกค้าและการปฏิบัติตามข้อตกลงระดับบริการ (service level agreement)
  • การปรับขนาดบัฟเฟอร์ของเร้าเตอร์เครือข่ายและการประมาณค่าความล่าช้าของแพ็กเก็ตในระบบโทรคมนาคม
  • การวิเคราะห์ปริมาณงานของสายการผลิตและการระบุคอขวด
  • การกำหนดค่าช่องทางเช็คอินและช่องทางรักษาความปลอดภัยของสนามบินเพื่อจัดการการไหลของผู้โดยสาร
  • การจัดสรรทรัพยากรคอมพิวเตอร์คลาวด์และการจัดตารางงานภายใต้ภาระงานที่แปรผัน

วิธีการทำงาน

วิธีการทำงาน

1

กำหนดขอบเขตของระบบ: ระบุประเภทของหน่วย (ลูกค้า, งาน, แพ็กเก็ต), เซิร์ฟเวอร์ (ทรัพยากร), ระเบียบวินัยของคิว (FIFO, ลำดับความสำคัญ, รอบการทำงาน), และข้อจำกัดด้านความจุ ระบุโทโพโลยีของเครือข่าย — คิวเดี่ยว, คิวแบบอนุกรม, หรือเครือข่ายคิวทั่วไปที่มีความน่าจะเป็นในการส่งต่อระหว่างโหนด

2

ปรับการแจกแจงเวลาการเข้ามาและเวลาการให้บริการให้เข้ากับข้อมูลที่สังเกตได้ ตัวเลือกทั่วไปคือการเข้ามาแบบปัวซง (อัตราแลมบ์ดา) และเวลาการให้บริการแบบเอกซ์โพเนนเชียล (อัตรามิว) ซึ่งประกอบกันเป็นตระกูล M/M/c สำหรับระบบจริง ให้ใช้การแจกแจงแบบเออร์ลัง (Erlang), แกมมา (Gamma), หรือการแจกแจงเชิงประจักษ์ (empirical distributions) ที่ปรับให้เข้ากับข้อมูลโดยใช้การทดสอบความเหมาะสม (goodness-of-fit tests) ตรวจสอบความถูกต้องของแบบจำลองอินพุตก่อนทำการจำลอง

สูตร
\lambda \sim \text{Poisson}(\lambda),\quad S \sim \text{Exp}(\mu)
3

เลือกแบบจำลองตามสัญกรณ์ของเคนดัลล์ (Kendall notation) (A/B/c/K/N/D): การแจกแจงการเข้ามา / การแจกแจงการให้บริการ / จำนวนเซิร์ฟเวอร์ / ความจุ / ขนาดประชากร / ระเบียบวินัย ตรวจสอบเงื่อนไขเสถียรภาพ (stability condition) rho = lambda หารด้วย (c คูณ mu) น้อยกว่า 1 มิฉะนั้นคิวจะเพิ่มขึ้นอย่างไม่จำกัด สำหรับกรณีที่สามารถวิเคราะห์ได้ด้วยสูตร ให้คำนวณเมตริกสภาวะคงตัว (steady-state metrics) รูปแบบปิดเพื่อใช้เป็นเกณฑ์มาตรฐาน

สูตร
\rho = \lambda / (c \cdot \mu) < 1
4

ดำเนินการจำลองเหตุการณ์แบบไม่ต่อเนื่อง: ปฏิทินเหตุการณ์จะเลื่อนผ่านเหตุการณ์การเข้ามา, เหตุการณ์เริ่มต้นการให้บริการ, และเหตุการณ์การออกจากระบบ สำหรับแต่ละการจำลองซ้ำ (replication) หน่วยจะถูกสร้างขึ้นจากการแจกแจงที่ปรับให้เข้ากับข้อมูล, ถูกส่งต่อไปยังระบบ, และสถิติจะถูกรวบรวม ดำเนินการจำลองซ้ำให้เพียงพอ (หรือการรันยาวครั้งเดียวโดยมีการลบช่วงเริ่มต้น) เพื่อให้ได้ค่าประมาณสภาวะคงตัว

5

ประมาณค่าตัวชี้วัดประสิทธิภาพหลัก: จำนวนเฉลี่ยในระบบ L, จำนวนเฉลี่ยในคิว Lq, เวลาเฉลี่ยในระบบ W, และเวลาเฉลี่ยในการรอ Wq กฎของลิตเติล (Little's Law) (L = lambda คูณ W) เชื่อมโยงปริมาณเหล่านี้และใช้เป็นเครื่องมือตรวจสอบความสอดคล้อง คำนวณอัตราการใช้ประโยชน์ของเซิร์ฟเวอร์ rho และความน่าจะเป็นในการรอหรือถูกบล็อก

สูตร
L = \lambda W,\quad W_q = L_q / \lambda
6

สร้างช่วงความเชื่อมั่น (confidence intervals) สำหรับแต่ละตัวชี้วัดประสิทธิภาพโดยใช้ค่าเฉลี่ยกลุ่ม (batch means) หรือการจำลองซ้ำแบบอิสระ ดำเนินการวิเคราะห์ความไว (sensitivity analysis) โดยการเปลี่ยนแปลงอัตราการเข้ามา, อัตราการให้บริการ, หรือจำนวนเซิร์ฟเวอร์เพื่อระบุคอขวด เปรียบเทียบทางเลือกการออกแบบ (เช่น การเพิ่มเซิร์ฟเวอร์, การเปลี่ยนระเบียบวินัย) โดยใช้การจัดอันดับและคัดเลือก (ranking-and-selection) หรือเทคนิคการลดความแปรปรวนด้วยการจำลองแบบสุ่มร่วม (common-random-numbers variance reduction)

ข้อผิดพลาดที่พบบ่อย

  • การละเลยช่วงเริ่มต้น (transient period) ทำให้ค่าประมาณสภาวะคงตัวเอนเอียง โดยผสมพฤติกรรมของระบบที่ว่างเปล่าในช่วงแรกเข้ากับประสิทธิภาพที่แท้จริง
  • การสมมติว่าการเข้ามาเป็นแบบปัวซงโดยไม่ได้ทดสอบข้อมูล; การเข้ามาที่มีความแปรปรวนสูงเกินไปหรือเป็นกลุ่มก้อน (เช่น ในเครือข่าย) ต้องการการแจกแจงที่มีหางยาวกว่า (heavier-tailed distributions)
  • การรายงานผลการจำลองเพียงครั้งเดียวเสมือนว่าเป็นผลลัพธ์ที่แน่นอน โดยไม่มีช่วงความเชื่อมั่นหรือการจำลองซ้ำ
  • การปฏิบัติต่อคิวที่ไม่เสถียร (rho >= 1) ราวกับว่ามันถึงสภาวะคงตัว — แบบจำลองจะแสดงให้เห็นคิวที่เพิ่มขึ้นอย่างไม่สิ้นสุด
  • การสับสนระหว่างปริมาณงาน (throughput) กับอัตราการใช้ประโยชน์ (utilization): เซิร์ฟเวอร์อาจถูกใช้งาน 90% แต่อัตราปริมาณงานยังคงถูกจำกัดโดยคอขวดที่อยู่ต้นน้ำ

คำถามที่พบบ่อย

เมื่อใดควรใช้การจำลองแทนสูตร M/M/c?

ควรใช้การจำลองเมื่อการแจกแจงเวลาการเข้ามาหรือเวลาการให้บริการแตกต่างอย่างมากจากแบบเอกซ์โพเนนเชียล (เช่น บริการแบบกำหนดเวลา, ความแปรปรวนสูง), เมื่อคิวหลายคิวโต้ตอบกันด้วยการส่งต่อ, เมื่อเซิร์ฟเวอร์มีการขัดข้องหรือมีตารางการทำงาน, หรือเมื่อคุณต้องการประสิทธิภาพในช่วงเปลี่ยนผ่าน (time-dependent) แทนที่จะเป็นค่าเฉลี่ยสภาวะคงตัว

ต้องทำการจำลองซ้ำกี่ครั้ง?

ไม่มีคำตอบที่เป็นสากล การศึกษาเบื้องต้น 5-10 ครั้งจะช่วยประมาณค่าความแปรปรวน จากนั้นใช้สูตร n = (z * s / epsilon)^2 เพื่อหาจำนวนครั้งที่ต้องการสำหรับความกว้างครึ่งหนึ่ง (half-width) epsilon ที่ต้องการที่ระดับความเชื่อมั่น z โดยทั่วไป 20-50 ครั้งก็เพียงพอสำหรับความแม่นยำปานกลาง แต่ปัญหาเกี่ยวกับเหตุการณ์ที่เกิดขึ้นได้ยากอาจต้องการการจำลองหลายพันครั้ง

กฎของลิตเติลคืออะไรและมีความสำคัญอย่างไร?

กฎของลิตเติลระบุว่า L = lambda * W: จำนวนเฉลี่ยในระบบในระยะยาวเท่ากับอัตราการเข้ามาคูณด้วยเวลาเฉลี่ยที่ใช้ในระบบ กฎนี้ใช้ได้กับแทบทุกคิวที่เสถียรโดยไม่ขึ้นกับการแจกแจง และมีประโยชน์ในการตรวจสอบความสมเหตุสมผลของผลลัพธ์การจำลอง

ฉันจะทราบได้อย่างไรว่าคิวของฉันเสถียรหรือไม่?

สำหรับคิวที่มีเซิร์ฟเวอร์เดียว, ความเข้มของการจราจร rho = lambda / mu ต้องน้อยกว่า 1 อย่างเคร่งครัด สำหรับ c เซิร์ฟเวอร์, rho = lambda / (c * mu) < 1 หาก rho >= 1, คิวจะไม่เสถียรและจะเพิ่มขึ้นอย่างไม่จำกัด; จะไม่มีการแจกแจงสภาวะคงตัว และผลลัพธ์การจำลองจะแสดงเวลาในการรอที่เพิ่มขึ้นเรื่อยๆ

การจำลองคิวสามารถจัดการกับคิวลำดับความสำคัญและการตัดการทำงาน (preemption) ได้หรือไม่?

ได้ การจำลองเหตุการณ์แบบไม่ต่อเนื่องสามารถรองรับคลาสลำดับความสำคัญหลายคลาส, การจัดตารางแบบตัดการทำงานและไม่ตัดการทำงาน, และกฎลำดับความสำคัญแบบไดนามิกได้อย่างเป็นธรรมชาติ มีผลลัพธ์เชิงวิเคราะห์สำหรับ M/M/c/PR (preemptive resume priority) ภายใต้การเข้ามาแบบปัวซงเท่านั้น สำหรับโครงสร้างลำดับความสำคัญอื่นๆ การจำลองเป็นแนวทางมาตรฐาน

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Kleinrock, L. (1975). Queueing Systems, Volume 1: Theory. Wiley-Interscience, New York.

    ISBN: 978-0471491101
    คัดลอกแล้ว
  2. Law, A. M. (2015). Simulation Modeling and Analysis (5th ed.). McGraw-Hill Education, New York.

    ISBN: 978-0073401324
    คัดลอกแล้ว