บันทึกของเคนดัลล์
ในทฤษฎีการเข้าคิว ซึ่งเป็นสาขาหนึ่งใน ทฤษฎีความน่าจะเป็นทางคณิตศาสตร์สัญกรณ์ของ Kendall (หรือบางครั้งเรียกว่า สัญกรณ์ Kendall ) เป็นระบบมาตรฐานที่ใช้ในการอธิบายและจำแนกประเภทของโหนดการเข้าคิวDG Kendallเสนอให้อธิบายแบบจำลองการเข้าคิวโดยใช้ปัจจัยสามประการที่เขียนว่า A/S/ cในปี 1953 [ 1 ]โดยที่ A หมายถึงเวลาที่อยู่ระหว่างการมาถึงของคิว S คือการกระจายเวลาการให้บริการ และcคือจำนวนช่องทางการให้บริการที่เปิดอยู่ที่โหนด ต่อมาได้มีการขยายเป็น A/S/ c / K / N /D โดยที่KคือความจุของคิวN คือขนาดของประชากรของงานที่จะได้รับ การบริการ และ D คือระเบียบวินัยของการเข้าคิว[ 2 ] [ 3 ] [ 4 ]
เมื่อไม่ได้ระบุพารามิเตอร์สามตัวสุดท้าย (เช่นคิว M/M/1 ) จะถือว่าK = ∞, N = ∞ และ D = FIFO [ 5 ]
ตัวอย่างแรก: คิว M/M/1
คิว M /M/1หมายความว่าเวลาระหว่างการมาถึงเป็นแบบมาร์โคเวียน (M) กล่าวคือ เวลาระหว่างการมาถึงเป็นไปตามการแจกแจงแบบเอกซ์โพเนนเชียลของพารามิเตอร์ λ M ตัวที่สองหมายความว่าเวลาให้บริการเป็นแบบมาร์โคเวียน: มันเป็นไปตามการแจกแจงแบบเอกซ์โพเนนเชียลของพารามิเตอร์ μ พารามิเตอร์สุดท้ายคือจำนวนช่องทางการให้บริการ ซึ่งคือหนึ่ง (1)
คำอธิบายพารามิเตอร์
ในส่วนนี้ เราจะอธิบายพารามิเตอร์ A/S/ c / K / N /D จากซ้ายไปขวา
A: ขั้นตอนการเดินทางมาถึง
รหัสที่ใช้อธิบายขั้นตอนการมาถึง รหัสที่ใช้มีดังนี้:
| เครื่องหมาย | ชื่อ | คำอธิบาย | ตัวอย่าง |
|---|---|---|---|
| เอ็ม | มาร์โคเวียนหรือไร้ความทรงจำ[ 6 ] | กระบวนการมาถึงแบบปัวซง (หรือแบบสุ่ม) (เช่นช่วงเวลาระหว่างการมาถึงแบบเลขชี้กำลัง ) | คิว M/M/1 |
| เอ็มเอ็กซ์ | มาร์คอฟแบบกลุ่ม | กระบวนการปัวซงที่มีตัวแปรสุ่มXแทนจำนวนผู้มาถึง ณ เวลาใดเวลาหนึ่ง | คิวM X /M Y /1 |
| แผนที่ | กระบวนการมาถึงแบบมาร์โคเวียน | การสรุปทั่วไปของกระบวนการปัวซง | |
| บีเมป | กระบวนการมาถึงแบบมาร์คอฟแบบกลุ่ม | การสรุปผลของMAPด้วยการมาถึงหลายครั้ง | |
| เอ็มเอ็มพีพี | กระบวนการปัวซงแบบมาร์คอฟ | กระบวนการปัวซงที่การมาถึงเกิดขึ้นเป็น "กลุ่ม" | |
| ดี | การกระจายแบบเสื่อมสภาพ | ช่วงเวลาระหว่างการมาถึงที่แน่นอนหรือคงที่ | คิว D/M/1 |
| อี | การกระจายเออร์ลัง | การแจกแจงแบบเออร์ลัง (Erlang distribution) โดยมีkเป็นพารามิเตอร์รูปร่าง (กล่าวคือ ผลรวมของ ตัวแปรสุ่มเอก ซ์โปเนนเชียลอิสระและ มีการกระจายเหมือนกันจำนวน k ตัว ) | |
| จี | การแจกจ่ายทั่วไป | แม้ว่า โดยทั่วไปแล้ว Gจะหมายถึงการมาถึงโดยอิสระ แต่ผู้เขียนบางคนก็ชอบใช้GIเพื่อความชัดเจนยิ่งขึ้น | |
| พีเอช | การกระจายแบบเฟส | การแจกแจงบางส่วนข้างต้นเป็นกรณีพิเศษของการแจกแจงแบบเฟส ซึ่งมักใช้แทนการแจกแจงทั่วไป |
S: การกระจายเวลาให้บริการ
นี่คือการกระจายเวลาในการให้บริการลูกค้า สัญลักษณ์ที่ใช้กันทั่วไปบางส่วน ได้แก่:
| เครื่องหมาย | ชื่อ | คำอธิบาย | ตัวอย่าง |
|---|---|---|---|
| เอ็ม | มาร์โคเวียนหรือไร้ความทรงจำ[ 6 ] | เวลาให้บริการเพิ่มขึ้นแบบทวีคูณ | คิว M/M/1 |
| ของฉัน | มาร์คอฟจำนวนมาก | เวลาให้บริการ แบบเลขชี้กำลังโดยมีตัวแปรสุ่มYสำหรับขนาดของกลุ่มเอนทิตีที่ได้รับการบริการในแต่ละครั้ง | คิวM X /M Y /1 |
| ดี | การกระจายแบบเสื่อมสภาพ | เวลาให้บริการที่แน่นอนหรือคงที่ | คิว M/D/1 |
| อี | การกระจายเออร์ลัง | การแจกแจงแบบเออร์ลัง (Erlang distribution) โดยมีkเป็นพารามิเตอร์รูปร่าง (กล่าวคือ ผลรวมของ ตัวแปรสุ่มเอก ซ์โปเนนเชียลอิสระและ มีการกระจายเหมือนกันจำนวน k ตัว ) | |
| จี | การแจกจ่ายทั่วไป | แม้ว่า โดยทั่วไปแล้ว Gจะหมายถึงเวลาให้บริการอิสระ แต่ผู้เขียนบางท่านนิยมใช้GIเพื่อให้ชัดเจนยิ่งขึ้น | คิว M/G/1 |
| พีเอช | การกระจายแบบเฟส | การแจกแจงบางส่วนข้างต้นเป็นกรณีพิเศษของการแจกแจงแบบเฟส ซึ่งมักใช้แทนการแจกแจงทั่วไป | |
| เอ็มเอ็มพีพี | กระบวนการปัวซงแบบมาร์คอฟ | การกระจายเวลาบริการ แบบเอกซ์โปเนนเชียลโดยที่พารามิเตอร์อัตราถูกควบคุมโดยห่วงโซ่มาร์คอฟ[ 7 ] |
ค : จำนวนเซิร์ฟเวอร์
จำนวนช่องทางการให้บริการ (หรือเซิร์ฟเวอร์) คิว M/M/1มีเซิร์ฟเวอร์เดียว และคิว M/M/c มีcเซิร์ฟเวอร์
K: จำนวนที่ว่างในคิว
ความจุของคิว หรือจำนวนลูกค้าสูงสุดที่อนุญาตให้เข้าคิวได้ เมื่อจำนวนลูกค้าถึงจำนวนสูงสุดนี้แล้ว ลูกค้าที่เข้ามาเพิ่มจะถูกปฏิเสธไม่ให้เข้าคิว หากไม่ระบุจำนวนสูงสุดนี้ จะถือว่าความจุไม่มีขีดจำกัด หรือไม่มีที่สิ้นสุด
- หมายเหตุ: บางครั้งอาจใช้สัญลักษณ์c + Kโดยที่K คือขนาดบัฟเฟอร์ ซึ่ง เป็นจำนวนตำแหน่งในคิวเหนือจำนวนเซิร์ฟเวอร์ c
N: จำนวนประชากรที่โทรเข้ามา
ขนาดของแหล่งที่มาของการโทร ขนาดของประชากรที่ลูกค้ามาจากนั้น ประชากรขนาดเล็กจะส่งผลกระทบอย่างมากต่ออัตราการมาถึงที่มีประสิทธิภาพ เพราะยิ่งมีลูกค้าในระบบมากขึ้นเท่าไหร่ ก็ยิ่งมีลูกค้าว่างที่จะเข้ามาในระบบน้อยลงเท่านั้น หากไม่ระบุตัวเลขนี้ จะถือว่าประชากรมีจำนวนไม่จำกัด หรืออนันต์
D: ความเป็นระเบียบเรียบร้อยของแถว
ระเบียบวินัยในการให้บริการหรือลำดับความสำคัญที่ใช้ในการให้บริการงานที่อยู่ในคิวหรือสายรอ:
| เครื่องหมาย | ชื่อ | คำอธิบาย |
|---|---|---|
| FIFO/FCFS | มาก่อนได้ก่อน/ใครมาก่อนได้ก่อน | ลูกค้าจะได้รับการบริการตามลำดับการมาถึง (ใช้เป็นค่าเริ่มต้น) |
| LIFO/LCFS | เข้าทีหลังได้ก่อน/มาก่อนได้ก่อน | ลูกค้าจะได้รับการบริการตามลำดับย้อนกลับจากลำดับที่พวกเขามาถึง |
| ไซโร | การให้บริการตามลำดับแบบสุ่ม | ลูกค้าจะได้รับการบริการตามลำดับแบบสุ่ม โดยไม่คำนึงถึงลำดับการมาถึง |
| พีคิว | การจัดลำดับความสำคัญ | มีตัวเลือกหลายอย่าง ได้แก่ การจัดคิวแบบมีลำดับความสำคัญแบบแย่งชิง (Preemptive Priority Queuing), การจัดคิวแบบไม่แย่งชิง (Non Preemptive Queuing), การจัดคิวแบบยุติธรรมโดยถ่วงน้ำหนักตามคลาส (Class Based Weighted Fair Queuing) และการจัดคิวแบบยุติธรรมโดยถ่วงน้ำหนัก (Weighted Fair Queuing) |
| พีเอส | การแบ่งปันโปรเซสเซอร์ | ลูกค้าจะได้รับการบริการตามลำดับที่กำหนด โดยไม่คำนึงถึงลำดับการมาถึง |
- หมายเหตุ : แนวทางการเขียนสัญลักษณ์อีกแบบหนึ่งคือ การบันทึกระเบียบการเข้าคิวไว้ก่อนจำนวนประชากรและความจุของระบบ โดยอาจมีหรือไม่มีวงเล็บก็ได้ ซึ่งโดยปกติแล้วจะไม่ก่อให้เกิดความสับสนเนื่องจากสัญลักษณ์ที่ใช้แตกต่างกัน