排隊論基礎

參考《運籌學教程》-胡運權

排隊論是對排隊問題的研究，表示為隨機聚散服務系統。聚即為到達，散即為離去，隨機指的是顧客的到達情況與每個顧客接受服務的時間是隨機的。

一般來說，顧客的相繼到達時間與服務時間這兩個量至少有一個量是未知的。因此，排隊論一般被稱為隨機服務系統理論。

以下僅介紹基本概念

輸入過程

說明顧客如何到達系統：

總數：有限/無限

到達方式：單個/成批

相繼到達時間的分布：設Tn為第n個顧客的到達時間，先假設n個顧客相繼到達，即T_1<T_2<...<T_n，設X_n=T_n-T_{n-1}，則假定Xn是獨立同分布的。

分布有：

• D，定長分布
• M，泊松分布
• Er，愛爾朗分布（介于泊松分布與正態分布之間）
• G，任意分布

排隊可以分為兩種：

• 有限排隊：排隊系統中顧客數有限
• 無限排隊：排隊系統中顧客數可以是無限的，到達系統后均可接受服務

有限排隊系統有可以分為：

• 損失制排隊系統，排隊空間為零，不能處理則立刻損失
• 混合制排隊系統，允許排隊，但不允許無限延長

混合制排隊系統一般具有以下特點：

隊長有限

等待時間有限

逗留時間（等待時間+服務時間）有限

排隊規則

• FCFS 先來先服務
• LCFS 后來先服務
• PS，具有優先權的服務

服務機制

已經知道服務太的服務時間V，對應的分布函數B(t)，密度函數b(t)

負指數分布：t>0時有$b(t)=\mu e^{?\mu t}$

…

記號系統

Kendall記號系統：X/Y/Z/A/B/C

• X表示顧客相繼到達時間間隔的分布
• Y表示服務時間的分布
• Z表示并聯服務臺的個數
• A表示系統容量，即總共能容納的顧客的個數
• B表示顧客源的數目
• C表示服務規則

描述指標

一些描述排隊系統的指標

• 隊長：系統中的顧客數$N(t)$
• 排隊長：系統中正在排隊的顧客數$N_q(t)$
• 等待時間：用戶到達到接受服務的時間，$T_q(t)$
• 逗留時間：用戶到達到服務完畢的時間$T(t)$

即如果涉及到隊列則加上q

一般來說，難以估算這些量的瞬時分布，所以排隊論中會選擇系統處于平衡狀態時進行分析。此時，隊長的分布，等待時間的分布，忙期的分布與系統所處的時刻無關。

• 隊長$N$的均值為$L$
• 排隊長$N_q$的均值為$L_q$
• 逗留時間$T$的均值為$W$
• 等待時間$T_q$的均值為$W_q$
• ${\lambda }_n$，表示狀態n下新客戶的平均到達率
• ${\mu }_n$，表示狀態n寫新客戶的平均服務率，即單位時間可以服務完的客戶數

此時，顧客相繼到達的平均時間間隔為$1/\lambda$，平均服務時間為$1/\mu$

服務臺的數量為s個，系統的容量（允許處理的所有顧客數）為K個

$\rho =\frac{\lambda }{s\mu }$，表示服務強度

一些公式

• Erlang等待公式：表示顧客到達系統需要等待的概率
• Little’s law，$W=L/\lambda$，即逗留時間會等于隊列長度除以平均到達率。
• Pollaczek-Khintchine(P-K公式)，M/G/1下的公式描述，表示等待隊列的長度與服務時間的分布無關。

總結

以上是生活随笔為你收集整理的排队论基础的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。