在人們的日常生活中常常會碰到擁擠和排隊現象。去醫院看病、在郵局營業視窗等候服務等，這是有形排隊。
除了有形排隊之外，還有無形的排隊，比如，由於上網人數多，網速大大減慢，這也是因為在“排隊”。
增加資源，如增加服務視窗，多設幾條跑道，網站設備擴容等，可以減少顧客排隊現象。但當顧客比較少時，必然會造成資源閒置。
由此可見，增加服務機構，當然可以減少排隊現象，但卻增加了服務成本；反之，減少服務機構，固然提高了服務機構的利用率，降低了成本，但卻增加了顧客的排隊等待時間。這是相互矛盾的。
我們把顧客和服務方構成的系統稱為排隊系統。電信網路中的信息流和信道，上網人員和網站設施等，都是顧客和服務員的系統。由於顧客到達和服務時間都是不確定的，絕大多數排隊系統工作於隨機狀態。因此，研究排隊系統的複雜性也就在於它的隨機性。排隊論利用機率論和隨機過程理論，研究排隊系統內的服務機構和顧客需求之間的關係，以便在所需的服務質量標準得到充分滿足的條件下，服務機構的費用最為經濟。這就是排隊論研究的目的。
排隊論就是試圖通過詳細的數學分析來回答這些問題：“顧客必須等待多久？”，“佇列中有多少顧客？”，“需要多少服務視窗才能消除排隊現象？”等。排隊論的套用相當廣泛，特別是在通信的套用中，最初排隊論主要套用在話務理論上，隨著通信網的發展，在分析網路的性能，如網路的時延、吞吐量、利用率等都要用到排隊理論。
基本介紹
- 中文名：排隊理論
- 外文名：QueuingTheory
- 所屬技術：電信技術
1．排隊系統的描述
一個排隊系統可以描述為：顧客為謀求服務而到達，如果前面已經有顧客到達，不能立即進入服務時，就需要排隊等待，接受服務，完畢後離開系統，如圖2.4所示。
排隊系統的基本特徵有：顧客到達模型、服務員的服務模型、排隊規則、系統容量、服務視窗數、服務級數。在大多數情況下，利用這6個基本特徵可以令人滿意地描述出一個排隊系統。
（1）顧客到達模型
顧客到達模型或排隊系統的輸入，通常用單位時間顧客到達的平均數(平均到達率)或相繼到達的顧客之間的平均時間(平均間隔時間)來表示。由於這兩個量很顯然是相關的，因此，只需其中之一就可描述排隊系統的輸入。
（2）服務員的服務模型
服務員的服務模型，在系統為非空閒的條件下，可用服務率和服務時間來表示，前者為單位時間服務完的顧客數，後者則為服務一個顧客所需的時間。
（3）排隊規則
排隊規則是佇列形成後，系統挑選顧客進入服務的方式。一般有非優先權方式和優先權方式兩種。非優先權中又有先到先服務，後到先服務及隨機服務三種，而優先權方式則又有中斷優先權方式和非中斷優先權方式兩種。
所謂中斷優先權方式為：較高優先權的顧客進入系統時，可以中斷為較低優先權顧客進行的服務，立即進入服務設施，接受服務；服務完成後，重新恢復被中斷的服務。非中斷優先權的方式，則必須等正在服務的顧客，服務完畢後，才能進入服務設施，接受服務。
優先權可以是大於1的任何正整數。如果在系統中同時有一個以上的顧客同屬一個優先權，那么還必須規定同級顧客的選擇原則。這可以是先到先服務，後到先服務和隨機服務中的任何一種。
（4）系統容量
系統容量即系統中可容納的顧客數，包括正在服務的顧客和佇列中的顧客。系統容量有限的排隊系統為有限排隊系統，否則為無限排隊系統。
在有限排隊系統中，最大的排隊長度為系統容量減去服務視窗數。如果系統容量等於服務視窗數，即最大排隊長度為0，則該系統稱為損失制服務系統。在目前的電話接續系統中，一般利用這種方法，即在用戶呼叫時如無通話電路可用，給主叫送忙音，主叫掛機退出。
（5）服務視窗數
如果只有一個服務視窗，則為單通道排隊系統，否則為多通道排隊系統。
（6）服務的級數
服務可以是多級的，在多級排隊系統中，服務甚至可以帶循環，這種情況可在機械製造過程中出現。如果只有一級服務，則為單級排隊系統。這裡我們只介紹單級服務系統。
2．服務系統的運行指標
用作評價服務質量的服務系統主要運行指標有三個。
（1）顧客等待時間W
式中Wq為顧客在佇列中等待的時間，Ws為顧客接受服務的時間。
（2）系統中的顧客數L
式中Lq為佇列中的顧客數，Ls為正在接受服務的顧客數。
（3）服務員的空閒時間，即出現顧客數小於服務視窗數的時間
3．排隊系統的表示方法
人們為方便起見，通常採用符號來表示一種排隊系統。常用的表示方法為：
X/Y/Z
其中X為顧客到達間隔時間的分布，Y為服務時間分布，Z為服務視窗數。系統容量有限的排隊系統，可在其後加括弧表示系統容量。
X/Y/Z(n)
表示顧客到達間隔時間分布和服務時間分布的符號有：M為泊松分布或負指數時間分布；D為定長分布，Ek為k階愛爾蘭分布；G為一般隨機分布。
因此，M/M/1表示顧客到達時間間隔和服務時間均為泊松分布，單視窗，系統容量無限的排隊系統。而M/M/m(n)則為顧客到達時間間隔和服務時間為泊松分布，m個視窗，系統容量為n(n≥m)。當n=m時，即M/M/m(m)系統容量等於視窗數。當系統中的顧客數等於視窗數時，新到的顧客就會遭到拒絕。電話通信網中，一般採用的就是這種損失制服務系統。
4．顧客到達時間間隔和服務時間的統計分布
（1）泊松分布
到達某系統的顧客數是一種統計數量(整數)的隨機過程，又稱計數過程。計數過程{N(t),t≥0}中，N(t)表示t時刻前產生事件的數量。N(t)的取值為非負整數。這裡所謂“事件產生”可以是到達一位顧客，事故發生等物理現象。N(t)=i表示在t時刻前產生i次顧客到達或i次事故等。用P{N(t)=i}表示它的機率。
計數過程是一個遞增過程，對於任意時刻t1<t2N(t1)≤N(t2)是必然事件。
① 定常泊松分布
在常見的排隊系統中，對顧客到達過程一般作如下假設
a．N(0)=0
即t=0時刻時，系統內無到達顧客
b．{N(t),t≥0}，具有定常獨立增量條件
即顧客到達是獨立的，而且是定常的，也就是不管在什麼時刻顧客到達法則都是相同的。某顧客到達與否與其他顧客到達是獨立無關的。
c．P{N(Δt)≥2}>O(Δt)
當Δt為非常小的時間間隔時，在Δt中存在兩個以上顧客到達的機率可以忽略不計。這稱為流的普通性。
d．P{N(Δt)=1}=λΔt+O(Δt)
當Δt為非常小的時間間隔時，在Δt中到達一個顧客的機率與Δt成正比，比例係數為λ。
其中λ為單位時間內顧客到達率，是大於零的常數，Δt是一個增量元素。O(Δt)表示隨著t→0，和Δt相比是可以忽略不計的一個高階無窮小量。
服務模型能滿足以上四個條件，即稱該隨機過程為滿足泊松分布的隨機過程，其數學分析就變得十分簡單。
假設該隨機過程至時刻t期間內產生的事件數或該期間內到達系統的顧客數恰為n的機率Pn(t)，則可以求得並用數學歸納法證明：
定理： 泊松過程顧客到達時間間隔Xk(k=1,2,……)是獨立的，都服從相同的指數分布，其參數為λ(均值為1/λ)。
也就是說泊松過程的顧客到達時間間隔服從指數分布，指數分布是一種套用很廣的分布。例如系統的可靠率R就服從指數分布規律。
泊松過程具有定常獨立增量性質是理想化的條件，它可以簡化數學分析，在很多情況下得到套用。例如在網路流量分析時，信息的到達很接近定常泊松分布，用泊松分布來近似表示信息的到達可以大大簡化分析的過程，而結果仍有參考價值。
② 非定常泊松分布
在實際問題中也有一些服務系統不具有定常增量的條件，如上網的客戶必然是傍晚多，而清晨少。
如果把泊松過程中的定常增量條件限制去除的話，則稱這類計數隨機過程為非定常泊松過程。其定義如下：
計數過程{N(t),t≥0}滿足以下四個條件時，稱該計數過程為非定常泊松過程。
a．N(0)=0
b．{N(t),t≥0}具有獨立增量性質
c．P{N(t+Δt)－N(t)≥2}=O(Δt)
d．P{N(t+Δt)－N(t)=1}=λ(t)Δt+O(Δt)
其中λ(t)>0，為非定常泊松過程分布的強度函式。
（2）愛爾蘭分布
現實問題中，顧客到達時間間隔不完全服從指數分布的情況還是比較多的，指數分布的密度函式f(t)為λe－λt。它為一遞減函式，最大值位於x=0處，即λ，如圖2.5所示。但是，實際問題中，t=0處的機率密度往往是小的。大多數場合，密度函式的最大值應該在t=a的附近，a為某一正數，如圖2.6所示。
k階愛爾蘭分布就是具有指數分布性質，而密度函式的最大值卻在x=a附近的一種分布律。
