ทฤษฎีการเข้าคิวเป็นการศึกษาทางคณิตศาสตร์เกี่ยวกับแถวรอหรือคิว [ ^{1 ]}มีการสร้างแบบจำลองการเข้าคิวเพื่อให้สามารถคาดการณ์ความยาวของคิวและเวลารอได้^{[ 1 ] โดย}ทั่วไปแล้วทฤษฎีการเข้าคิวถือเป็นสาขาหนึ่งของการวิจัยการดำเนินงานเนื่องจากผลลัพธ์มักถูกนำมาใช้ในการตัดสินใจทางธุรกิจเกี่ยวกับทรัพยากรที่จำเป็นในการให้บริการ

ทฤษฎีการเข้าคิวมีต้นกำเนิดมาจากการวิจัยของAgner Krarup Erlangซึ่งสร้างแบบจำลองเพื่ออธิบายระบบการโทรเข้าที่บริษัท Copenhagen Telephone Exchange ^{[ 1 ]}แนวคิดเหล่านี้มีความสำคัญอย่างยิ่งต่อสาขาวิศวกรรมการจราจรทางโทรศัพท์และต่อมาได้มีการนำไปประยุกต์ใช้ในด้านโทรคมนาคมวิศวกรรมจราจรการคำนวณ^{[ 2 ]}การจัดการโครงการและโดยเฉพาะอย่างยิ่งวิศวกรรมอุตสาหกรรมซึ่งมีการนำไปประยุกต์ใช้ในการออกแบบโรงงาน ร้านค้า สำนักงาน และโรง^{พยาบาล[ 3 ] [ 4} ]

ทฤษฎีการเข้าคิวเป็นหนึ่งในสาขาการศึกษาที่สำคัญในสาขาวิทยาการจัดการ วิทยาการจัดการช่วยให้ธุรกิจสามารถแก้ปัญหาต่างๆ ได้หลากหลายโดยใช้วิธีการทางวิทยาศาสตร์และคณิตศาสตร์ที่แตกต่างกัน การวิเคราะห์การเข้าคิวเป็นการวิเคราะห์เชิงความน่าจะเป็นของแถวรอ ดังนั้นผลลัพธ์ ซึ่งเรียกอีกอย่างว่าลักษณะการทำงาน จึงเป็นเชิงความน่าจะเป็นมากกว่าเชิงกำหนด^{[ 5 ]}ความน่าจะเป็นที่ลูกค้า n รายอยู่ในระบบการเข้าคิว จำนวนลูกค้าเฉลี่ยในระบบการเข้าคิว จำนวนลูกค้าเฉลี่ยในแถวรอ เวลาเฉลี่ยที่ลูกค้าใช้ในระบบการเข้าคิวทั้งหมด เวลาเฉลี่ยที่ลูกค้าใช้ในแถวรอ และสุดท้าย ความน่าจะเป็นที่เซิร์ฟเวอร์ไม่ว่างหรือว่างอยู่ ล้วนเป็นลักษณะการทำงานต่างๆ ที่แบบจำลองการเข้าคิวเหล่านี้คำนวณ^{[ 5 ]}เป้าหมายโดยรวมของการวิเคราะห์การเข้าคิวคือการคำนวณลักษณะเหล่านี้สำหรับระบบปัจจุบัน จากนั้นทดสอบทางเลือกต่างๆ ที่อาจนำไปสู่การปรับปรุง การคำนวณลักษณะการทำงานของระบบปัจจุบันและการเปรียบเทียบค่ากับลักษณะของระบบทางเลือกช่วยให้ผู้จัดการเห็นข้อดีข้อเสียของแต่ละตัวเลือกที่เป็นไปได้ ระบบเหล่านี้ช่วยในกระบวนการตัดสินใจขั้นสุดท้ายโดยแสดงวิธีการเพิ่มการประหยัด ลดเวลารอ ปรับปรุงประสิทธิภาพ ฯลฯ รูปแบบคิวหลักที่สามารถใช้ได้คือระบบคิวแบบเซิร์ฟเวอร์เดียวและระบบคิวแบบหลายเซิร์ฟเวอร์ ซึ่งจะกล่าวถึงต่อไปในภายหลัง รูปแบบเหล่านี้สามารถจำแนกเพิ่มเติมได้ขึ้นอยู่กับว่าเวลาให้บริการคงที่หรือไม่กำหนด ความยาวคิวมีจำกัด จำนวนผู้เรียกใช้มีจำกัด ฯลฯ^{[ 5 ]}

คิวหรือโหนดการเข้าคิวอาจเปรียบได้กับกล่องดำงาน(หรืออาจเรียกว่าลูกค้าหรือคำขอขึ้นอยู่กับสาขา) เข้ามาในคิว อาจต้องรอสักระยะหนึ่ง ใช้เวลาประมวลผล และจากนั้นก็ออกจากคิว ไป

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

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

พฤติกรรมของคิวเดี่ยว (หรือเรียกว่าโหนดคิว ) สามารถอธิบายได้ด้วยกระบวนการเกิด-ตายซึ่งอธิบายถึงการมาถึงและการออกจากคิว พร้อมกับจำนวนงานที่อยู่ในระบบในขณะนั้น หากkแทนจำนวนงานในระบบ (ไม่ว่าจะเป็นงานที่กำลังดำเนินการอยู่หรืองานที่รออยู่ หากคิวมีบัฟเฟอร์ของงานที่รออยู่) การมาถึงจะเพิ่มk ขึ้น 1 และการออกจากคิวจะลดkลง 1

ระบบจะเปลี่ยนค่าkโดยการเกิดและการตายซึ่งเกิดขึ้นตามอัตราการมาถึงและอัตราการออกจากงานแต่ละงานสำหรับคิว โดยทั่วไปแล้วอัตราเหล่านี้จะไม่เปลี่ยนแปลงตามจำนวนงานในคิว ดังนั้นจึง ถือว่ามีอัตรา เฉลี่ยของการมาถึง/การออกจากงานต่อหน่วยเวลาเพียงอัตราเดียว ภายใต้สมมติฐานนี้ กระบวนการนี้จะมีอัตราการมาถึงเท่ากับและอัตราการออกจากงานเท่ากับ ${\displaystyle \lambda _{i}}$${\displaystyle \mu _{i}}$${\displaystyle i}$${\displaystyle \lambda ={\text{avg}}(\lambda _{1},\lambda _{2},\dots ,\lambda _{k})}$${\displaystyle \mu ={\text{avg}}(\mu _{1},\mu _{2},\dots ,\mu _{k})}$

สม การ สภาวะคงที่สำหรับกระบวนการเกิดและตาย หรือที่เรียกว่าสมการสมดุลมีดังต่อไปนี้ โดยที่แทน ความน่าจะเป็นในสภาวะคงที่ที่จะอยู่ในสถานะn${\displaystyle P_{n}}$

${\displaystyle \mu _{1}P_{1}=\แลมบ์ดา _{0}P_{0}}$

${\displaystyle \lambda _{0}P_{0}+\mu _{2}P_{2}=(\lambda _{1}+\mu _{1})P_{1}}$

${\displaystyle \lambda _{n-1}P_{n-1}+\mu _{n+1}P_{n+1}=(\lambda _{n}+\mu _{n})P_{n}}$

สมการสองสมการแรกบ่งชี้ว่า

${\displaystyle P_{1}={\frac {\lambda _{0}}{\mu _{1}}}P_{0}}$

และ

${\displaystyle P_{2}={\frac {\lambda _{1}}{\mu _{2}}}P_{1}+{\frac {1}{\mu _{2}}}(\mu _{1}P_{1}-\lambda _{0}P_{0})={\frac {\lambda _{1}}{\mu _{2}}}P_{1}={\frac {\lambda _{1}\lambda _{0}}{\mu _{2}\mu _{1}}}P_{0}}$.

โดยใช้วิธีการอุปมานทางคณิตศาสตร์

${\displaystyle P_{n}={\frac {\lambda _{n-1}\lambda _{n-2}\cdots \lambda _{0}}{\mu _{n}\mu _{n-1}\cdots \mu _{1}}}P_{0}=P_{0}\prod _{i=0}^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}}$.

สภาวะดังกล่าวส่งผลให้เกิด ${\displaystyle \sum _{n=0}^{\infty }P_{n}=P_{0}+P_{0}\sum _{n=1}^{\infty }\prod _{i=0}^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}=1}$

${\displaystyle P_{0}={\frac {1}{1+\sum _{n=1}^{\infty }\prod _{i=0}^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}}}}$

ซึ่งเมื่อรวมกับสมการสำหรับ จะสามารถอธิบายความน่าจะเป็นสภาวะคงที่ที่ต้องการได้อย่างครบถ้วน ${\displaystyle P_{n}}$${\displaystyle (n\geq 1)}$

โดยทั่วไปแล้ว โหนดคิวเดี่ยวจะถูกอธิบายโดยใช้สัญกรณ์ของ Kendall ในรูปแบบ A/S/ cโดยที่Aอธิบายการกระจายของระยะเวลาระหว่างการมาถึงแต่ละครั้งในคิวSอธิบายการกระจายของเวลาให้บริการสำหรับงาน และcอธิบายจำนวนเซิร์ฟเวอร์ที่โหนด^{[ 6 ] [ 7 ]}สำหรับตัวอย่างของสัญกรณ์คิว ​​M/M/1เป็นแบบจำลองที่เรียบง่ายซึ่งเซิร์ฟเวอร์เดียวให้บริการงานที่มาถึงตามกระบวนการปัวซง (โดยที่ระยะเวลาระหว่างการมาถึงมีการกระจายแบบเอก ซ์โปเนนเชียล ) และมีเวลาให้บริการที่มีการกระจายแบบเอกซ์โปเนนเชียล (M หมายถึงกระบวนการมาร์คอฟ ) ในคิว M/G/1นั้น G หมายถึงทั่วไปและบ่งชี้ถึงการกระจายความน่าจะเป็น โดยพลการ สำหรับเวลาให้บริการ

พิจารณาคิวที่มีเซิร์ฟเวอร์หนึ่งตัวและมีลักษณะดังต่อไปนี้:

• ${\displaystyle \lambda }$อัตราการมาถึง (ส่วนกลับของเวลาที่คาดว่าจะใช้ระหว่างลูกค้าแต่ละรายที่มาถึง เช่น 10 รายต่อวินาที)
• ${\displaystyle \mu }$: ส่วนกลับของเวลาให้บริการเฉลี่ย (จำนวนครั้งที่คาดว่าจะมีการให้บริการต่อเนื่องกันต่อหน่วยเวลาเดียวกัน เช่น ต่อ 30 วินาที)
• n : พารามิเตอร์ที่บ่งบอกจำนวนลูกค้าในระบบ
• ${\displaystyle P_{n}}$ความน่าจะเป็นที่จะมี ลูกค้าจำนวน n รายในระบบในสภาวะคงที่

นอกจากนี้ ให้แทนจำนวนครั้งที่ระบบเข้าสู่สถานะnและแทนจำนวนครั้งที่ระบบออกจากสถานะnแล้วสำหรับทุกnนั่นคือ จำนวนครั้งที่ระบบออกจากสถานะจะแตกต่างจากจำนวนครั้งที่ระบบเข้าสู่สถานะนั้นไม่เกิน 1 เนื่องจากระบบจะกลับเข้าสู่สถานะนั้นอีกครั้งในอนาคต ( ) หรือไม่ ( ) ${\displaystyle E_{n}}$${\displaystyle L_{n}}$${\displaystyle \left\vert E_{n}-L_{n}\right\vert \in \{0,1\}}$${\displaystyle E_{n}=L_{n}}$${\displaystyle \left\vert E_{n}-L_{n}\right\vert =1}$

เมื่อระบบเข้าสู่สภาวะสมดุลแล้ว อัตราการมาถึงควรเท่ากับอัตราการออกเดินทาง

ดังนั้นสมการสมดุล

${\displaystyle \mu P_{1}=\lambda P_{0}}$

${\displaystyle \lambda P_{0}+\mu P_{2}=(\lambda +\mu )P_{1}}$

${\displaystyle \lambda P_{n-1}+\mu P_{n+1}=(\lambda +\mu )P_{n}}$

บ่งบอก

${\displaystyle P_{n}={\frac {\lambda }{\mu }}P_{n-1},\ n=1,2,\ldots }$

ข้อเท็จจริงที่นำไปสู่สูตร การแจกแจงทางเรขาคณิต${\displaystyle P_{0}+P_{1}+\cdots =1}$

${\displaystyle P_{n}=(1-\rho )\rho ^{n}}$

ที่ไหน. ${\displaystyle \rho ={\frac {\lambda }{\mu }}<1}$

ระบบคิวพื้นฐานที่ใช้กันทั่วไปนั้นมีที่มาจากเออร์ลังและเป็นการดัดแปลงมาจากกฎของลิตเติล โดยกำหนดอัตราการมาถึงλอัตราการออกจากคิวσและอัตราการออกจากคิวμความยาวของคิวLจะถูกกำหนดดังนี้:

${\displaystyle L={\frac {\lambda -\sigma }{\mu }}}$.

เมื่อสมมติว่าอัตราต่างๆ มีการแจกแจงแบบเอกซ์โปเนนเชียล เวลาในการรอคอยWสามารถกำหนดได้ว่าเป็นสัดส่วนของผู้มาถึงที่ได้รับการบริการ ซึ่งเท่ากับอัตราการรอดชีวิตแบบเอกซ์โปเนนเชียลของผู้ที่ไม่ถอนตัวออกไปในช่วงเวลารอคอย ดังนี้:

${\displaystyle {\frac {\mu }{\lambda }}=e^{-W{\mu }}}$

สมการที่สองมักถูกเขียนใหม่เป็น:

${\displaystyle W={\frac {1}{\mu }}\mathrm {ln} {\frac {\lambda }{\mu }}}$

แบบจำลองกล่องเดียวสองขั้นตอนเป็นเรื่องปกติในระบาดวิทยา^{[ 8 ]}

ในปี พ.ศ. 2452 Agner Krarup Erlangวิศวกรชาวเดนมาร์กที่ทำงานให้กับศูนย์แลกเปลี่ยนโทรศัพท์โคเปนเฮเกน ได้ตีพิมพ์บทความฉบับแรกเกี่ยวกับสิ่งที่ปัจจุบันเรียกว่าทฤษฎีการเข้าคิว^{[ 9 ] [ 10 ] [ 11 ]}เขาสร้างแบบจำลองจำนวนสายโทรศัพท์ที่เข้ามายังศูนย์แลกเปลี่ยนโดยใช้กระบวนการปัวซงและแก้ปัญหาคิว M/D/1ในปี พ.ศ. 2460 และแบบจำลองการเข้าคิวM/D/ k ในปี พ.ศ. 2463 ^{[ 12 ]}ในสัญกรณ์ของ Kendall:

• M ย่อมาจากMarkovหรือไม่มีความทรงจำซึ่งหมายความว่าการมาถึงเกิดขึ้นตามกระบวนการปัวซง
• D ย่อมาจากdeterministic (กำหนดได้แน่นอน ) ซึ่งหมายความว่างานที่เข้ามาในคิวต้องการปริมาณการบริการที่คงที่
• kอธิบายจำนวนเซิร์ฟเวอร์ที่โหนดคิว ( k = 1, 2, 3, ...)

หากโหนดมีงานมากกว่าจำนวนเซิร์ฟเวอร์ งานเหล่านั้นจะถูกจัดคิวและรอรับบริการ

คิวM/G/1ได้รับการแก้ไขโดยFelix Pollaczekในปี พ.ศ. 2473 ^{[ 13 ]} ซึ่งต่อมา Aleksandr Khinchinได้นำวิธีแก้ปัญหาดังกล่าวมาปรับปรุงใหม่ในแง่ของความน่าจะเป็นและปัจจุบันรู้จักกันในชื่อ สูตร Pollaczek – Khinchine ^{[ 12 ] [ 14 ]}

หลังปี 1940 ทฤษฎีการเข้าคิวกลายเป็นหัวข้อวิจัยที่นักคณิตศาสตร์ให้ความสนใจ^{[ 14 ]}ในปี 1953 เดวิด จอร์จ เคนดัลล์ ได้แก้ ปัญหาคิวGI/M/ k ^{[ 15 ]}และนำเสนอสัญลักษณ์สมัยใหม่สำหรับคิว ซึ่งปัจจุบันรู้จักกันในชื่อสัญลักษณ์ของเคนดัลล์ในปี 1957 พอลลาเช็กได้ศึกษาคิว GI/G/1 โดยใช้สมการอินทิกรัล [ ^{16 ] จอ}ห์น คิงแมนได้ให้สูตรสำหรับเวลาการรอคอยเฉลี่ยในคิว G/G/1ซึ่งปัจจุบันรู้จักกันในชื่อสูตรของคิงแมน^{[ 17 ]}

ลีโอนาร์ด ไคลน์ร็อกทำงานเกี่ยวกับการประยุกต์ใช้ทฤษฎีคิวกับการสลับข้อความในช่วงต้นทศวรรษ 1960 และการสลับแพ็กเก็ตในช่วงต้นทศวรรษ 1970 ผลงานชิ้นแรกของเขาในสาขานี้คือวิทยานิพนธ์ระดับปริญญาเอกที่สถาบันเทคโนโลยีแมสซาชูเซตส์ในปี 1962 ซึ่งตีพิมพ์เป็นหนังสือในปี 1964 งานทางทฤษฎีของเขาที่ตีพิมพ์ในช่วงต้นทศวรรษ 1970 เป็นพื้นฐานสำหรับการใช้การสลับแพ็กเก็ตในARPANETซึ่งเป็นเครือข่ายต้นแบบของอินเทอร์เน็ต

วิธีทางเรขาคณิตของเมทริกซ์และวิธีวิเคราะห์เมทริกซ์ ทำให้สามารถ พิจารณาคิวที่มี การกระจายระหว่างการมาถึงและเวลาบริการ แบบเฟสได้^{[ 18 ]}

ระบบที่มีวงโคจรที่เชื่อมโยงกันเป็นส่วนสำคัญในทฤษฎีคิวในการประยุกต์ใช้กับเครือข่ายไร้สายและการประมวลผลสัญญาณ^{[ 19 ]}

การประยุกต์ใช้ทฤษฎีคิวในปัจจุบันเกี่ยวข้องกับการพัฒนาผลิตภัณฑ์ซึ่งผลิตภัณฑ์ (วัสดุ) มีอยู่จริงในเชิงพื้นที่และเวลา กล่าวคือ ผลิตภัณฑ์มีปริมาณที่แน่นอนและมีระยะเวลาที่แน่นอน^{[ 20 ]}

ปัญหาต่างๆ เช่น ตัวชี้วัดประสิทธิภาพสำหรับคิวM/G/ kยังคงเป็นปัญหาที่ยังไม่ได้รับการแก้ไข^{[ 12 ] [ 14 ]}

สามารถใช้นโยบายการจัดตารางเวลาที่หลากหลายได้ที่โหนดคิว:

มาก่อนได้ก่อน

เรียกอีกอย่างว่ามาก่อนได้ก่อน (FCFS) ^{[ 21 ]}หลักการนี้ระบุว่าลูกค้าจะได้รับการบริการทีละราย และลูกค้าที่รอนานที่สุดจะได้รับการบริการก่อน^{[ 22 ]}

คนสุดท้ายเข้า คนแรกออก

หลักการนี้ยังให้บริการลูกค้าทีละราย แต่ลูกค้าที่มีเวลารอคอย น้อยที่สุด จะได้รับการบริการก่อน^{[ 22 ]}เรียกอีกอย่างว่า การ เรียงซ้อน

การแบ่งปันโปรเซสเซอร์

ความสามารถในการให้บริการจะถูกแบ่งปันอย่างเท่าเทียมกันระหว่างลูกค้า^{[ 22 ]}

บริการตามลำดับแบบสุ่ม (SIRO)

ระเบียบวิธีนี้ เรียกอีกอย่างว่าลำดับการให้บริการแบบสุ่ม (ROS) ซึ่งระบุว่า งานที่จะได้รับการบริการในลำดับถัดไปจะถูกเลือกแบบสุ่มจากงานที่รออยู่ในคิว

ลำดับความสำคัญ

ลูกค้าที่มีลำดับความสำคัญสูงจะได้รับการบริการก่อน^{[ 22 ]}คิวลำดับความสำคัญสามารถแบ่งออกได้เป็นสองประเภท: แบบ ไม่สามารถแทรกแซงได้ (ซึ่งงานที่กำลังดำเนินการอยู่ไม่สามารถถูกขัดจังหวะได้) และแบบแทรกแซงได้ (ซึ่งงานที่กำลังดำเนินการอยู่สามารถถูกขัดจังหวะโดยงานที่มีลำดับความสำคัญสูงกว่าได้) ไม่มีงานใดสูญหายในทั้งสองรูปแบบ^{[ 23 ]}

เริ่มจากงานที่ใช้เวลาน้อยที่สุดก่อน

งานต่อไปที่จะได้รับบริการคืองานที่มีขนาดเล็กที่สุด^{[ 24 ]}

ดำเนินการล่วงหน้าด้วยงานที่สั้นที่สุดก่อน

งานต่อไปที่จะได้รับบริการคืองานที่มีขนาดดั้งเดิมเล็กที่สุด^{[ 25 ]}

เวลาประมวลผลที่เหลือสั้นที่สุด

งานถัดไปที่จะให้บริการคืองานที่มีความต้องการการประมวลผลที่เหลืออยู่น้อยที่สุด^{[ 26 ]}

สิ่งอำนวยความสะดวกด้านบริการ

• เซิร์ฟเวอร์เดียว: ลูกค้าเข้าแถวรอ และมีเซิร์ฟเวอร์เพียงเครื่องเดียว
• เซิร์ฟเวอร์แบบขนานหลายเครื่อง (คิวเดียว): ลูกค้าเข้าแถวรอ และมีเซิร์ฟเวอร์หลายเครื่องให้บริการ
• เซิร์ฟเวอร์คู่ขนานหลายตัว (คิวหลายคิว): มีเคาน์เตอร์จำนวนมาก และลูกค้าสามารถเลือกได้ว่าจะเข้าคิวที่เคาน์เตอร์ใด

เซิร์ฟเวอร์ไม่น่าเชื่อถือ

ความล้มเหลวของเซิร์ฟเวอร์เกิดขึ้นตามกระบวนการสุ่ม (โดยปกติคือปัวซง) และตามมาด้วยช่วงเวลาการตั้งค่าซึ่งเซิร์ฟเวอร์ไม่สามารถใช้งานได้ ลูกค้าที่ได้รับผลกระทบจะยังคงอยู่ในพื้นที่ให้บริการจนกว่าเซิร์ฟเวอร์จะได้รับการแก้ไข^{[ 27 ]}

พฤติกรรมการรอคอยของลูกค้า

• การไม่ยอมต่อคิว: ลูกค้าตัดสินใจไม่ต่อคิวหากคิวยาวเกินไป
• การสลับคิว: ลูกค้าเปลี่ยนคิวหากคิดว่าการทำเช่นนั้นจะทำให้ได้รับการบริการเร็วขึ้น
• การละทิ้งสิทธิ์: ลูกค้าออกจากแถวหากรอรับบริการนานเกินไป

ลูกค้าที่มาถึงแล้วแต่ไม่ได้รับการบริการ (ไม่ว่าจะเนื่องจากคิวไม่มีตัวสำรอง หรือเนื่องจากลูกค้าปฏิเสธหรือเปลี่ยนใจ) เรียกว่า ลูกค้าที่ออกจากคิว (dropouts ) อัตราเฉลี่ยของลูกค้าที่ออกจากคิวเป็นพารามิเตอร์สำคัญที่ใช้อธิบายลักษณะของคิว

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

สำหรับเครือข่ายที่มี โหนด mโหนด สถานะของระบบสามารถอธิบายได้ด้วย เวกเตอร์มิติ m ( x ₁ , x ₂ , ..., x _m ) โดยที่x _iแทนจำนวนลูกค้าที่แต่ละโหนด

เครือข่ายคิวที่ไม่ธรรมดาที่ง่ายที่สุดเรียกว่า^คิวแบบแทนเดม [ ^{28 ] ผลลัพธ์}ที่สำคัญครั้งแรกในด้านนี้คือเครือข่ายแจ็กสัน [ ^{29 ] [ 30 ]}ซึ่ง มี การกระจายแบบคงที่ในรูปแบบผลิตภัณฑ์ ที่มีประสิทธิภาพ และ สามารถคำนวณ การวิเคราะห์ค่าเฉลี่ย^{[ 31 ]} (ซึ่งช่วยให้สามารถคำนวณเมตริกเฉลี่ย เช่น ปริมาณงานและเวลาการรอคอย) ได้^{[ 32 ]}หากจำนวนลูกค้าทั้งหมดในเครือข่ายคงที่ เครือข่ายนั้นเรียกว่าเครือข่ายปิดและได้รับการพิสูจน์แล้วว่ามีการกระจายแบบคงที่ในรูปแบบผลิตภัณฑ์โดยทฤษฎีบทกอร์ดอน-นิวเวลล์ [ ^{33 ] ผลลัพธ์}นี้ได้รับการขยายไปยังเครือข่าย BCMP ^{[ 34 ]}ซึ่งเครือข่ายที่มีเวลาให้บริการ ระบอบ และการกำหนดเส้นทางลูกค้าทั่วไปมาก แสดงให้เห็นว่ามีการกระจายแบบคงที่ในรูปแบบผลิตภัณฑ์เช่นกัน^ค่าคงที่การทำให้เป็นมาตรฐานสามารถคำนวณได้ด้วยอัลกอริทึมของ Buzenซึ่งเสนอในปี 1973 [ ^{35 ]}

เครือข่ายของลูกค้ายังได้รับการตรวจสอบ เช่นเครือข่าย Kellyซึ่งลูกค้าในระดับต่างๆ จะได้รับระดับความสำคัญที่แตกต่างกัน ณ โหนดบริการต่างๆ^{[ 36 ]}เครือข่ายอีกประเภทหนึ่งคือเครือข่าย Gซึ่งเสนอครั้งแรกโดยErol Gelenbeในปี 1993: ^{[ 37 ]}เครือข่ายเหล่านี้ไม่ได้สมมติการกระจายเวลาแบบเอกซ์โพเนนเชียลเหมือนเครือข่าย Jackson แบบคลาสสิก

ในเครือข่ายเวลาไม่ต่อเนื่องซึ่งมีข้อจำกัดว่าโหนดบริการใดบ้างที่สามารถทำงานได้ในเวลาใดเวลาหนึ่ง อัลกอริทึมการจัดตารางเวลาแบบน้ำหนักสูงสุดจะเลือกนโยบายบริการเพื่อให้ได้ปริมาณงานที่เหมาะสมที่สุดในกรณีที่งานแต่ละงานเข้าเยี่ยมชมโหนดบริการที่มีบุคคลเดียวเท่านั้น^{[ 21 ]}ในกรณีทั่วไปที่งานสามารถเข้าเยี่ยมชมโหนดได้มากกว่าหนึ่งโหนดการกำหนดเส้นทางแบบแรงดันย้อนกลับจะให้ปริมาณงานที่เหมาะสมที่สุดตัวจัดตารางเวลาเครือข่ายต้องเลือกอัลกอริทึมการจัดคิวซึ่งส่งผลต่อลักษณะของเครือข่ายขนาดใหญ่^{[ 38 ]}

แบบจำลองสนามเฉลี่ยพิจารณาพฤติกรรมจำกัดของการวัดเชิงประจักษ์ (สัดส่วนของคิวในสถานะต่างๆ) เมื่อจำนวนคิวmเข้าใกล้ค่าอนันต์ ผลกระทบของคิวอื่นๆ ต่อคิวใดๆ ในเครือข่ายจะถูกประมาณโดยสมการเชิงอนุพันธ์ แบบจำลองเชิงกำหนดจะลู่เข้าสู่การกระจายแบบคงที่เดียวกันกับแบบจำลองดั้งเดิม^{[ 39 ]}

ในระบบที่มีอัตราการครอบครองสูง (การใช้งานใกล้ 1) สามารถใช้การประมาณการจราจรหนาแน่นเพื่อประมาณกระบวนการความยาวคิวโดยใช้การเคลื่อนที่แบบบราวน์สะท้อน^{[ 40 ]}กระบวนการ Ornstein–Uhlenbeck หรือ กระบวนการแพร่กระจายทั่วไป[ ^{41 ] จำนวน}มิติของกระบวนการบราวน์เท่ากับจำนวนโหนดคิว โดยการแพร่กระจายถูกจำกัดไว้ที่ออร์แธนต์ที่ ไม่เป็นลบ

แบบจำลองของไหลเป็นอนาล็อกเชิงกำหนดต่อเนื่องของเครือข่ายคิวที่ได้มาจากการใช้ลิมิตเมื่อกระบวนการถูกปรับขนาดในเวลาและพื้นที่ ทำให้สามารถมีวัตถุที่ไม่เหมือนกันได้ วิถีที่ปรับขนาดนี้จะลู่เข้าสู่สมการเชิงกำหนด ซึ่งช่วยให้สามารถพิสูจน์เสถียรภาพของระบบได้ เป็นที่ทราบกันว่าเครือข่ายคิวอาจมีเสถียรภาพ แต่มีขีดจำกัดของไหลที่ไม่เสถียร^{[ 42 ]}

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

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

ทฤษฎีการเข้าคิวเจาะลึกถึงแนวคิดพื้นฐานต่างๆ โดยมีกระบวนการการมาถึงและกระบวนการบริการเป็นศูนย์กลาง กระบวนการการมาถึงอธิบายถึงวิธีการที่เอนทิตีเข้าร่วมคิวเมื่อเวลาผ่านไป ซึ่งมักจำลองโดยใช้กระบวนการสุ่ม เช่น กระบวนการปัวซง ประสิทธิภาพของระบบการเข้าคิวจะวัดได้จากตัวชี้วัดประสิทธิภาพหลัก ซึ่งรวมถึงความยาวคิวเฉลี่ย เวลาการรอเฉลี่ย และปริมาณงานของระบบ ตัวชี้วัดเหล่านี้ให้ข้อมูลเชิงลึกเกี่ยวกับการทำงานของระบบ ชี้นำการตัดสินใจที่มุ่งเป้าไปที่การเพิ่มประสิทธิภาพและลดเวลาการรอ^{[ 43 ] [ 44 ] [ 45 ]}

• กรอสส์, โดนัลด์; คาร์ล เอ็ม. แฮร์ริส (1998). พื้นฐานของทฤษฎีการเข้าคิว . ไวลีย์. ISBN 978-0-471-32812-4.ออนไลน์
• Zukerman, Moshe (2013). บทนำสู่ทฤษฎีการเข้าคิวและแบบจำลองการจราจรโทรคมนาคมเชิงสุ่ม (PDF) . arXiv : 1307.2968 .
• Deitel, Harvey M. (1984) [1982]. บทนำเกี่ยวกับระบบปฏิบัติการ (ฉบับปรับปรุงครั้งแรก). Addison - Wesley. หน้า  673. ISBN 978-0-201-14502-1.บทที่ 15 หน้า 380–412
• Gelenbe, Erol; Isi Mitrani (2010). การวิเคราะห์และการสังเคราะห์ระบบคอมพิวเตอร์ . World Scientific ฉบับที่ 2. ISBN 978-1-908978-42-4.
• Newell, Gordron F. (1 มิถุนายน 1971). การประยุกต์ใช้ทฤษฎีการเข้าคิว . Chapman and Hall.
• เลียวนาร์ด ไคลน์ร็อก, การไหลของข้อมูลในเครือข่ายการสื่อสารขนาดใหญ่ (MIT, เคมบริดจ์, 31 พฤษภาคม 1961) ข้อเสนอวิทยานิพนธ์ปริญญาเอก
• เลียวนาร์ด ไคลน์ร็อก. การไหลเวียนของข้อมูลในเครือข่ายการสื่อสารขนาดใหญ่ (รายงานความคืบหน้าประจำไตรมาสของ RLE, กรกฎาคม 1961)
• เลียวนาร์ด ไคลน์ร็อก. เครือข่ายการสื่อสาร: การไหลของข้อความแบบสุ่มและความล่าช้า (แมคกรอว์-ฮิลล์, นิวยอร์ก, 1964)
• ไคลน์ร็อก, เลียวนาร์ด (2 มกราคม 1975). ระบบการเข้าคิว: เล่มที่ 1 – ทฤษฎี . นิวยอร์ก: ไวลีย์ อินเตอร์ไซแอนซ์.  หน้า417. ISBN 978-0-471-49110-1.
• ไคลน์ร็อค, เลียวนาร์ด (22 เมษายน 1976). ระบบคิว: เล่มที่ 2 – การประยุกต์ใช้กับคอมพิวเตอร์ . นิวยอร์ก: ไวลีย์ อินเตอร์ไซแอนซ์.  หน้า576. ISBN 978-0-471-49111-8.
• Lazowska, Edward D.; John Zahorjan; G. Scott Graham; Kenneth C. Sevcik (1984). ประสิทธิภาพเชิงปริมาณของระบบ: การวิเคราะห์ระบบคอมพิวเตอร์โดยใช้แบบจำลองเครือข่ายคิว . Prentice-Hall, Inc. ISBN 978-0-13-746975-8.
• จอน ไคลน์เบิร์ก; เอวา ตาร์ดอส (30 มิถุนายน 2556). การออกแบบอัลกอริทึม เพียร์สัน. ไอเอสบีเอ็น 978-1-292-02394-6.

ลองค้นหาคำว่า queueing  หรือqueuingใน Wiktionary ซึ่งเป็นพจนานุกรมออนไลน์ฟรี

• บทช่วยสอนและเครื่องคำนวณทฤษฎีการเข้าคิวของ Teknomo
• หลักสูตรทฤษฎีการเข้าคิวของ Virtamo
• หน้าทฤษฎีการเข้าคิวของไมรอน ฮลินกา
• LINE: เครื่องมืออเนกประสงค์สำหรับแก้ปัญหารูปแบบคิว