การจำลองคิว — การสร้างแบบจำลองและการวิเคราะห์ระบบการรอคอย
- ผู้เสนอ
- 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)
- การปรับขนาดบัฟเฟอร์ของเร้าเตอร์เครือข่ายและการประมาณค่าความล่าช้าของแพ็กเก็ตในระบบโทรคมนาคม
- การวิเคราะห์ปริมาณงานของสายการผลิตและการระบุคอขวด
- การกำหนดค่าช่องทางเช็คอินและช่องทางรักษาความปลอดภัยของสนามบินเพื่อจัดการการไหลของผู้โดยสาร
- การจัดสรรทรัพยากรคอมพิวเตอร์คลาวด์และการจัดตารางงานภายใต้ภาระงานที่แปรผัน
วิธีการทำงาน
วิธีการทำงาน
กำหนดขอบเขตของระบบ: ระบุประเภทของหน่วย (ลูกค้า, งาน, แพ็กเก็ต), เซิร์ฟเวอร์ (ทรัพยากร), ระเบียบวินัยของคิว (FIFO, ลำดับความสำคัญ, รอบการทำงาน), และข้อจำกัดด้านความจุ ระบุโทโพโลยีของเครือข่าย — คิวเดี่ยว, คิวแบบอนุกรม, หรือเครือข่ายคิวทั่วไปที่มีความน่าจะเป็นในการส่งต่อระหว่างโหนด
ปรับการแจกแจงเวลาการเข้ามาและเวลาการให้บริการให้เข้ากับข้อมูลที่สังเกตได้ ตัวเลือกทั่วไปคือการเข้ามาแบบปัวซง (อัตราแลมบ์ดา) และเวลาการให้บริการแบบเอกซ์โพเนนเชียล (อัตรามิว) ซึ่งประกอบกันเป็นตระกูล M/M/c สำหรับระบบจริง ให้ใช้การแจกแจงแบบเออร์ลัง (Erlang), แกมมา (Gamma), หรือการแจกแจงเชิงประจักษ์ (empirical distributions) ที่ปรับให้เข้ากับข้อมูลโดยใช้การทดสอบความเหมาะสม (goodness-of-fit tests) ตรวจสอบความถูกต้องของแบบจำลองอินพุตก่อนทำการจำลอง
สูตร
\lambda \sim \text{Poisson}(\lambda),\quad S \sim \text{Exp}(\mu)เลือกแบบจำลองตามสัญกรณ์ของเคนดัลล์ (Kendall notation) (A/B/c/K/N/D): การแจกแจงการเข้ามา / การแจกแจงการให้บริการ / จำนวนเซิร์ฟเวอร์ / ความจุ / ขนาดประชากร / ระเบียบวินัย ตรวจสอบเงื่อนไขเสถียรภาพ (stability condition) rho = lambda หารด้วย (c คูณ mu) น้อยกว่า 1 มิฉะนั้นคิวจะเพิ่มขึ้นอย่างไม่จำกัด สำหรับกรณีที่สามารถวิเคราะห์ได้ด้วยสูตร ให้คำนวณเมตริกสภาวะคงตัว (steady-state metrics) รูปแบบปิดเพื่อใช้เป็นเกณฑ์มาตรฐาน
สูตร
\rho = \lambda / (c \cdot \mu) < 1
ดำเนินการจำลองเหตุการณ์แบบไม่ต่อเนื่อง: ปฏิทินเหตุการณ์จะเลื่อนผ่านเหตุการณ์การเข้ามา, เหตุการณ์เริ่มต้นการให้บริการ, และเหตุการณ์การออกจากระบบ สำหรับแต่ละการจำลองซ้ำ (replication) หน่วยจะถูกสร้างขึ้นจากการแจกแจงที่ปรับให้เข้ากับข้อมูล, ถูกส่งต่อไปยังระบบ, และสถิติจะถูกรวบรวม ดำเนินการจำลองซ้ำให้เพียงพอ (หรือการรันยาวครั้งเดียวโดยมีการลบช่วงเริ่มต้น) เพื่อให้ได้ค่าประมาณสภาวะคงตัว
ประมาณค่าตัวชี้วัดประสิทธิภาพหลัก: จำนวนเฉลี่ยในระบบ L, จำนวนเฉลี่ยในคิว Lq, เวลาเฉลี่ยในระบบ W, และเวลาเฉลี่ยในการรอ Wq กฎของลิตเติล (Little's Law) (L = lambda คูณ W) เชื่อมโยงปริมาณเหล่านี้และใช้เป็นเครื่องมือตรวจสอบความสอดคล้อง คำนวณอัตราการใช้ประโยชน์ของเซิร์ฟเวอร์ rho และความน่าจะเป็นในการรอหรือถูกบล็อก
สูตร
L = \lambda W,\quad W_q = L_q / \lambda
สร้างช่วงความเชื่อมั่น (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) ภายใต้การเข้ามาแบบปัวซงเท่านั้น สำหรับโครงสร้างลำดับความสำคัญอื่นๆ การจำลองเป็นแนวทางมาตรฐาน
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Kleinrock, L. (1975). Queueing Systems, Volume 1: Theory. Wiley-Interscience, New York.
ISBN: 978-0471491101คัดลอกแล้วLaw, A. M. (2015). Simulation Modeling and Analysis (5th ed.). McGraw-Hill Education, New York.
ISBN: 978-0073401324คัดลอกแล้ว