แถวคอยแบบมาร์คอฟ (Markovian Queues)

แถวคอยแบบมาร์คอฟมีลักษณะการมาถึงแบบปัวซงและเวลาให้บริการแบบเอ็กซ์โพเนนเชียล ทำให้จำนวนลูกค้าเป็นลูกโซ่มาร์คอฟแบบเวลาต่อเนื่อง ซึ่งสามารถหาคำตอบสมดุลได้อย่างชัดเจน

Definition

แถวคอยแบบมาร์คอฟคือระบบบริการที่ลูกค้ามาถึงตามกระบวนการปัวซงและต้องการเวลาบริการแบบเอ็กซ์โพเนนเชียลที่เป็นอิสระต่อกัน ดังนั้นจำนวนในระบบจึงพัฒนาไปเป็นลูกโซ่มาร์คอฟแบบเวลาต่อเนื่องแบบเกิด-ตาย ซึ่งมีการกระจายตัวแบบสภาวะคงที่และเวลารอคอยที่ชัดเจน

Scope

หัวข้อนี้ครอบคลุมสัญกรณ์ของ Kendall สำหรับระบบแถวคอย, แถวคอย M/M/1 แบบเซิร์ฟเวอร์เดี่ยวและการกระจายตัวแบบคงที่ทางเรขาคณิต, ระบบ M/M/c แบบหลายเซิร์ฟเวอร์และระบบการสูญเสีย, สูตร Erlang B และ C, เสถียรภาพและความเข้มข้นของการจราจร, และการหาค่าเฉลี่ยความยาวแถวคอย, เวลารอคอย, และปริมาณช่วงเวลาที่ยุ่งจากกระบวนการเกิด-ตายที่รองรับ

Core questions

• แถวคอย M/M/1 เกิดขึ้นได้อย่างไรในฐานะกระบวนการเกิด-ตาย และมีการกระจายตัวแบบคงที่อย่างไร?
• เงื่อนไขใดเกี่ยวกับความเข้มข้นของการจราจรที่ทำให้แถวคอยมีเสถียรภาพ?
• ค่าเฉลี่ยความยาวแถวคอยและเวลารอคอยหาได้อย่างไร และกฎของ Little ถูกนำมาใช้อย่างไร?
• เซิร์ฟเวอร์หลายตัวและความจุที่จำกัดเปลี่ยนแปลงสูตรของ Erlang อย่างไร?

Key theories

การกระจายตัวแบบคงที่และความเสถียรของ M/M/1

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

สูตรการสูญเสียและความล่าช้าของ Erlang

สำหรับระบบหลายเซิร์ฟเวอร์ สูตร Erlang B ให้ความน่าจะเป็นของการบล็อกในระบบการสูญเสีย และสูตร Erlang C ให้ความน่าจะเป็นของการรอคอยในระบบความล่าช้า ซึ่งทั้งสองสูตรได้มาจากสมการสมดุลของการเกิด-ตาย และมีความสำคัญต่อการวางแผนกำลังการผลิต

Clinical relevance

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

History

Erlang ได้พัฒนาสูตรการสูญเสียและความล่าช้าสำหรับการจราจรทางโทรศัพท์ระหว่างปี 1909 ถึง 1917, Kendall ได้นำเสนอสัญกรณ์การมาถึง/บริการ/เซิร์ฟเวอร์ที่เป็นระบบและการวิเคราะห์ลูกโซ่ฝังตัวในปี 1953, และตำราของ Kleinrock ในทศวรรษ 1970 ได้นำทฤษฎีนี้ไปประยุกต์ใช้กับเครือข่ายคอมพิวเตอร์และการสื่อสาร

Key figures

• Agner Krarup Erlang
• David Kendall
• Leonard Kleinrock

Seminal works

• kleinrock1975

Frequently asked questions

M/M/1 หมายถึงอะไร?

ในสัญกรณ์ของ Kendall ตัว M ตัวแรกหมายถึงการมาถึงแบบมาร์คอฟ (ปัวซง), ตัว M ตัวที่สองหมายถึงเวลาบริการแบบเอ็กซ์โพเนนเชียล, และเลข 1 หมายถึงเซิร์ฟเวอร์เดี่ยว

แถวคอยแบบมาร์คอฟมีเสถียรภาพเมื่อใด?

เมื่อความเข้มข้นของการจราจร ซึ่งคืออัตราการมาถึงหารด้วยอัตราการบริการรวม น้อยกว่าหนึ่ง มิฉะนั้นแถวคอยจะเติบโตอย่างไม่มีขีดจำกัดและไม่มีการกระจายตัวแบบคงที่อยู่