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

การจำลองคิวแบบสุ่ม — การสร้างแบบจำลองเชิงความน่าจะเป็นของระบบแถวคอย

ผู้เสนอ
Kendall, D. G.
ปี
1953
ประเภท
Stochastic simulation — waiting-line system analysis
กลุ่มวิธี
Simulation / optimization

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

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

ใช้ทำอะไร?

แบบจำลองการจำลองคิวแบบสุ่ม (Stochastic Queueing Simulation) ใช้ในการจำลองระบบแถวคอยที่กระบวนการมาถึงและกระบวนการให้บริการเป็นไปตามการแจกแจงความน่าจะเป็น แทนที่จะเป็นอัตราคงที่ โดยการจำลองเหตุการณ์สุ่มหลายพันครั้ง จะประมาณค่าตัวชี้วัดสมรรถนะ — เช่น เวลาคอยเฉลี่ย ความยาวคอย การใช้ประโยชน์ของพนักงาน — ภายใต้ความไม่แน่นอนที่สมจริง ทำให้เป็นเครื่องมือมาตรฐานสำหรับการออกแบบและประเมินระบบบริการ ตั้งแต่โรงพยาบาลไปจนถึงศูนย์บริการทางโทรศัพท์

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

ในระบบบริการใดๆ ลูกค้าไม่ได้มาถึงเป็นช่วงเวลาที่แน่นอน และพนักงานก็ไม่ได้ใช้เวลาให้บริการเท่ากัน การจำลองคิวแบบสุ่มยอมรับความสุ่มนี้ โดยจะสุ่มเวลาการมาถึงและเวลาให้บริการจากการแจกแจงความน่าจะเป็นที่ปรับให้เหมาะสม ประมวลผลลูกค้าทีละเหตุการณ์ และสังเกตการณ์ว่าคิวจะก่อตัวและคลี่คลายไปตามกาลเวลาอย่างไร ผลลัพธ์ที่ได้คือภาพสมรรถนะของระบบที่สมจริง รวมถึงเหตุการณ์ความแออัดที่เกิดขึ้นได้ยากแต่มีค่าใช้จ่ายสูง ซึ่งสูตร M/M/c เชิงวิเคราะห์เพียงอย่างเดียวไม่สามารถจับต้องได้สำหรับโครงสร้างที่ซับซ้อนและไม่เป็นแบบ Markovian

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

ทฤษฎีคิวแบบสุ่มมีรากฐานมาจากการทำงานด้านปริมาณการจราจรทางโทรศัพท์ของ Erlang ในปี 1909 แต่รูปแบบที่ใช้การจำลองสมัยใหม่ได้ตกผลึกจากการจำแนกระบบคิวของ Kendall ในปี 1953 และการเพิ่มขึ้นของคอมพิวเตอร์ดิจิทัล หนังสือเรียนของ Law และ Kelton (ฉบับพิมพ์ครั้งแรกปี 1982 ปัจจุบันอยู่ในฉบับที่ห้า) ได้สร้างมาตรฐานวิธีการจำลองแบบขับเคลื่อนด้วยเหตุการณ์ (event-driven simulation) และเทคนิคการวิเคราะห์ผลลัพธ์ทางสถิติที่ผู้ปฏิบัติงานยังคงใช้มาจนถึงปัจจุบัน

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

ใช้การจำลองคิวแบบสุ่มเมื่อระบบมีรูปแบบการให้บริการหรือการมาถึงที่ไม่เป็นแบบ Markovian (การแจกแจงทั่วไป) มีคิวที่พึ่งพากันหลายคิว การกำหนดเส้นทางตามสถานะ หรือบัฟเฟอร์จำกัด ซึ่งสูตร Kendall แบบปิด (closed-form) ไม่สามารถคำนวณได้ เหมาะอย่างยิ่งสำหรับการวางแผนกำลังการผลิต การเพิ่มประสิทธิภาพจำนวนพนักงาน และการวิเคราะห์ระดับการให้บริการในด้านการดูแลสุขภาพ การผลิต โลจิสติกส์ และโทรคมนาคม **ห้าม**ใช้เมื่อแบบจำลองวิเคราะห์ M/M/c แบบง่ายเพียงพอ เมื่อข้อมูลนำเข้าสำหรับการปรับการแจกแจงไม่เพียงพอ หรือเมื่อต้องการคำตอบแบบสมดุลเชิงกำหนด (deterministic flow-balance) แทนที่จะเป็นการแจกแจงสมรรถนะเชิงความน่าจะเป็น

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

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

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

จุดแข็ง

  • รองรับการแจกแจงเวลาการมาถึงและเวลาให้บริการตามอำเภอใจ รวมถึงฮิสโตแกรมเชิงประจักษ์ โดยไม่จำเป็นต้องมีข้อสมมติฐานแบบ Markovian
  • จับเหตุการณ์ความแออัดที่เกิดขึ้นได้ยากและพฤติกรรมหางที่สูตรวิเคราะห์มองข้ามไป
  • สร้างแบบจำลองโครงสร้างเครือข่ายที่ซับซ้อน — คิวแบบอนุกรม การแตกแขนง วงจรป้อนกลับ — ภายในระบบจำลองเดียว
  • ให้ผลลัพธ์ตัวชี้วัดสมรรถนะแบบแจกแจงเต็ม (ไม่ใช่แค่ค่าเฉลี่ย) ช่วยให้สามารถรับประกันระดับการให้บริการตามเปอร์เซ็นไทล์
  • การทดสอบสถานการณ์ (ระดับพนักงาน กฎการกำหนดเส้นทาง) ทำได้ง่าย: เปลี่ยนพารามิเตอร์และรันใหม่
  • ได้รับการตรวจสอบความถูกต้องเทียบกับกฎของ Little และผลลัพธ์เชิงวิเคราะห์สภาวะคงตัวสำหรับการตรวจสอบแบบจำลอง

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

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

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

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

1

กำหนดโครงสร้างเครือข่ายคิว: จำนวนพนักงาน จำนวนที่นั่งในคิว ขนาดประชากรลูกค้า และระเบียบวินัยการให้บริการ (FCFS, priority, round-robin) ระบุสัญกรณ์ Kendall (เช่น M/G/c/K) เพื่อบันทึกขอบเขตของแบบจำลองและข้อสมมติฐานอย่างชัดเจน

2

ปรับการแจกแจงความน่าจะเป็นให้เข้ากับข้อมูลการมาถึงและข้อมูลการให้บริการเชิงประจักษ์ กำหนดเวลาการมาถึง T_a ~ F_a และเวลาให้บริการ T_s ~ F_s (เช่น Exponential, Erlang, Lognormal) การทดสอบความเหมาะสมของการแจกแจง (Goodness-of-fit tests) (K-S, chi-square) จะตรวจสอบการแจกแจงที่เลือกก่อนเริ่มการจำลอง

สูตร
T_a \sim F_a(\cdot), \quad T_s \sim F_s(\cdot)
3

ใช้ตัวสร้างเลขสุ่มเทียม (pseudo-random number generator) เพื่อสุ่มตัวอย่างจาก F_a และ F_s จัดเก็บรายการเหตุการณ์ในอนาคต (future-event list - FEL) ซึ่งกำหนดตารางเวลาเหตุการณ์การมาถึง การเริ่มให้บริการ และการออกจากการให้บริการตามลำดับเวลา นาฬิกาจำลองจะเลื่อนไปยังเหตุการณ์ถัดไป

4

ประมวลผลเหตุการณ์ตามลำดับ: เมื่อมีการมาถึง ลูกค้าจะเข้าคิวหรือเข้ารับบริการหากมีพนักงานว่าง เมื่อมีการออกจากการให้บริการ พนักงานจะเลือกรับลูกค้าที่รออยู่คนถัดไปหากคิวไม่ว่าง ใช้กฎของ Little (L = λW) เป็นการตรวจสอบความสอดคล้องภายในระหว่างการทำงาน

สูตร
L_q = \lambda W_q \quad (\text{Little's Law})
5

รวบรวมสถิติเฉลี่ยตามเวลา: จำนวนเฉลี่ยในคิว L_q, เวลาคอยเฉลี่ย W, การใช้ประโยชน์ของพนักงาน ρ, และปริมาณงานประสิทธิผล λ_eff บันทึกการแจกแจงเชิงประจักษ์ทั้งหมดของเวลาคอยเพื่อประมาณค่าเปอร์เซ็นไทล์หาง (tail percentiles) ที่เกี่ยวข้องกับข้อตกลงระดับการให้บริการ (service-level agreements)

สูตร
\bar{W} = \frac{1}{N}\sum_{i=1}^{N} W_i, \quad \bar{L} = \lambda \bar{W}
6

ทำการจำลองซ้ำหลายครั้งอย่างอิสระ เพื่อแยกอคติของช่วงเริ่มต้น (warm-up transient bias) ออกจากพฤติกรรมสภาวะคงตัว (steady-state behavior) ใช้วิธีการลบช่วงเริ่มต้น (deletion method) หรือวิธีค่าเฉลี่ยเป็นชุด (batch means) สำหรับการวิเคราะห์สภาวะคงตัว รายงานช่วงความเชื่อมั่นสำหรับตัวชี้วัดสมรรถนะแต่ละรายการ และทำการวิเคราะห์ความไว (sensitivity analysis) ต่อพารามิเตอร์การแจกแจงที่สำคัญ

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

  • การใช้การจำลองยาวครั้งเดียวแทนการจำลองซ้ำหลายครั้งอย่างอิสระ จะทำให้การประมาณค่าความแปรปรวนสูงเกินจริงและปกปิดอคติในช่วงเริ่มต้น
  • การปรับการแจกแจงให้เข้ากับจำนวนการสังเกตที่น้อยเกินไป (n < 30) นำไปสู่พฤติกรรมหางที่ไม่น่าเชื่อถือและการคาดการณ์สมรรถนะที่มองโลกในแง่ดีเกินไป
  • การละเลยความสัมพันธ์ระหว่างเวลาการมาถึงหรือเวลาให้บริการที่ต่อเนื่องกันเมื่อมีความสัมพันธ์นั้นอยู่ — เช่น การมาถึงเป็นชุด หรือความเหนื่อยล้าของพนักงาน — จะทำให้ข้อสมมติฐานความเป็นอิสระเป็นโมฆะ
  • การรายงานเฉพาะเวลาคอยเฉลี่ยโดยไม่มีช่วงความเชื่อมั่น จะให้ความรู้สึกแม่นยำที่ผิดพลาดในแบบจำลองสุ่ม
  • การสับสนระหว่างวัตถุประสงค์การจำลองช่วงเริ่มต้น (เช่น วันทำการที่ยุ่งวันเดียว) กับการวิเคราะห์สภาวะคงตัว และการใช้เกณฑ์การยุติที่ไม่เหมาะสม

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

ต้องใช้การจำลองซ้ำกี่ครั้งจึงจะได้ค่าประมาณที่น่าเชื่อถือ?

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

เมื่อใดที่สูตร M/M/c เชิงวิเคราะห์จะดีกว่าการจำลอง?

เมื่อการมาถึงเป็นแบบ Poisson อย่างแท้จริง เวลาให้บริการเป็นแบบ Exponential และระบบมีโครงสร้างแบบหลายพนักงานคิวเดียว สูตร M/M/c จะให้ผลลัพธ์สภาวะคงตัวที่แม่นยำทันที การจำลองจะเพิ่มคุณค่าก็ต่อเมื่อข้อสมมติฐานเหล่านี้ไม่เป็นจริง หรือเมื่อระบบมีการกำหนดเส้นทางที่ซับซ้อนและบัฟเฟอร์จำกัด

ฉันจะจัดการกับช่วงเริ่มต้น (warm-up period) ได้อย่างไร?

ช่วงเริ่มต้น (transient period) จะถูกระบุโดยการพล็อตค่าเฉลี่ยสะสมของตัวชี้วัดสมรรถนะเทียบกับเวลาจำลอง (วิธีของ Welch) และลบข้อมูลก่อนที่ค่าเฉลี่ยจะคงที่ อีกทางเลือกหนึ่งคือ เริ่มการจำลองในสภาวะสภาวะคงตัวที่สมจริง (เช่น มีพนักงานที่ใช้งานในระดับการใช้ประโยชน์ที่คาดหวัง)

ฉันสามารถใช้การจำลองคิวแบบสุ่มสำหรับความต้องการที่ไม่คงที่ตามเวลา (เช่น ช่วงชั่วโมงเร่งด่วน) ได้หรือไม่?

ได้ แบบจำลองอัตราการมาถึงที่เปลี่ยนแปลงตามเวลาโดยใช้กระบวนการ Poisson ที่ไม่เป็นเนื้อเดียวกัน (non-homogeneous Poisson process) หรือตารางอัตราการมาถึงเชิงประจักษ์ นาฬิกาจำลองจะติดตามพลวัตของคิวที่ขึ้นกับเวลาโดยธรรมชาติ ซึ่งสูตรวิเคราะห์สภาวะคงตัวไม่สามารถแสดงได้

ฉันจะตรวจสอบความถูกต้องของแบบจำลองการจำลองของฉันได้อย่างไร?

ตรวจสอบความถูกต้องโดยการเปรียบเทียบผลลัพธ์การจำลองกับข้อมูลระบบจริง (ข้อมูลในอดีต) ตรวจสอบความสอดคล้องภายในผ่านกฎของ Little (L = λW) และทดสอบเงื่อนไขขอบ (การใช้ประโยชน์เข้าใกล้ 0 หรือ 1) การวิเคราะห์ความไวต่อการแจกแจงนำเข้าจะยืนยันว่าผลลัพธ์ตอบสนองต่อการเปลี่ยนแปลงพารามิเตอร์อย่างสมเหตุสมผล

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

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

  1. Kendall, D. G. (1953). Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain. The Annals of Mathematical Statistics, 24(3), 338–354.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Law, A. M. (2015). Simulation Modeling and Analysis (5th ed.). McGraw-Hill Education.

    ISBN: 9780073401324
    คัดลอกแล้ว