單渠道隨機排隊法

單渠道隨機排隊法是由一個單服務台，隨機到達和隨機服務時間的情況形成的排隊方法。

基本介紹

• 中文名：單渠道隨機排隊法
• 外文名：Single-channel random queuing method
• 學科：運籌學
• 隸屬：排隊論
• 套用領域：機場、港口模擬等
• ：

排隊論

排隊論是運籌學的重要分支之一，排隊論又稱隨機服務系統理論或等待線理論，是研究排隊擁擠現象的一門學科，即研究在保證服務質量的前提下，使得服務、設施及費用既經濟又合理。排隊論所要解決的主要問題是如何合理地設計與控制隨機服務系統，使得它既能滿足顧客需要，又能使機構的花費最小。

在排隊論中，稱要求服務的對象為顧客，稱從事服務的機構或個人為服務台。顧客—服務台，形成排隊的結構。顧客為了得到某種服務到達系統，在沒有得到服務時容許排隊等待，此時加入到等待的隊伍中，獲得服務後離開系統。在排隊系統中，顧客到達時間與服務台為其服務時間是隨機的，故隨機性是排隊系統的基本特徵。故排隊論又稱隨機服務系統理論。
20世紀50年代初，堪道爾(D.G.Kendall)對排隊論作了系統的研究，他用嵌入馬爾柯夫鏈方法研究排隊論，使排隊論得到了進一步的發展。是他首先（1951年）用3個字母組成的符號A/B/C表示排隊系統。其中A表示顧客到達時間分布，B表示服務時間的分布，C表示服務機構中的服務台的個數。

例如：M/M/1是指顧客到達的時間間隔服從參數為1/λ的泊松分布，服務時間服從參數為1/μ的指數分布，服務台的個數為1的排隊模型。此模型顧客的到達與服務時間均相互獨立、隨機的。M/M/c是指顧客到達的時間間隔服從參數為1/λ的泊松分布，服務時間服從參數為1/μ的指數分布，服務台的個數為c的排隊模型。此模型顧客的到達與服務時間均相互獨立的、隨機的。顧客在系統內排成一列等待服務，排隊空間無限。

任何一個隨機服務系統的運行過程的三個基本組成部分：顧客輸入、排隊規則、服務機構。

(1)顧客的輸入：顧客到達排隊系統的過程稱為輸入過程。輸入過程最基本的特徵是顧客到達間隔時間的機率分布。
(2) 排隊規則：排隊所遵循的規則，從佇列中挑選顧客進行服務的規則。根據顧客對等待的態度分為損失制與等待制。常用的排隊規則：先到先服務、後到先服務、優先權服務、隨機服務。

(3)服務機構：服務台的個數(單通道、多通道)，服務台的排列(並聯、串聯)，服務時間(確定性、隨機型)。

系統模擬

模擬又稱仿真，它的基本思想是構造一個試驗的模型，這個模型與我們研究的系統的主要性能十分近似。模擬是一種定量過程，先為過程設計一個模型，然後再組織一系列的反覆試驗，以預測該過程全部時間裡所發生的情況。

使用模擬的原因：

1.由於難以觀察到實際環境，模擬可能是惟一可以利用的方法；

2.不可能求出一個數學解；

3.實際觀察一個系統可能太費錢；

4. 不可能有足夠的時間來廣泛地操作該系統；

5. 對一個系統的實現運用和觀察可能破壞性太大。

模擬的不足：

1.模擬是不精確的；

2.一個良好的模型可能是非常昂貴的；

3.並非所有的方法都可用模擬的方法來估算；

4.模擬能產生一種估算答案的方法，但不能得出答案本身。

系統模擬過程是建立模型並通過模型的運行對模型進行檢驗和修正，使模型不斷趨於完善的過程。

步驟如下：

1.確定要模擬的問題和系統；

2.將所要用的模型化為公式；

3.測試模型：將其情況與真實問題周圍的情況作比較；

4.鑑別和收集所需數據以測試模型；

5.執行該模型；

6. 分析模型結果；

7. 重新執行該項模擬以測試新答案；

8. 使模擬生效。

排隊系統模擬描述

1.顧客到達模式：用到達時間間隔來描述，可分為確定性到達及隨機性到達。隨機性到達採用機率分布來描述，最常採用的泊松到達。
2.服務模式：描述服務台為顧客服務的時間：確定性的，也可能是隨機的。
3.排隊規則：服務台完成當前的服務後，從佇列中選擇下一實體的原則。
FCFS——先到先服務； LCFS——後到先服務；PS——根據實體的重要程度選擇最優先服務者。
4.服務流程：多個服務台，多個佇列，如何從某一個佇列中選擇某一個實體服務，包括實體可否換隊及換隊規則等。
5.系統狀態：一個事件是引起系統狀態瞬時變化情況的集合。在服務台排隊系統中兩個可能的事件會影響系統的狀態：顧客進入系統（到達事件）和顧客離開系統（離開事件）。

6.事件：引起系統狀態發生變化的行為。事件表：管理事件的表。時鐘： 標記事件出現的時間的時鐘。
隨機數： 事件是隨機出現的，為了模仿現實生活中所需的隨機性，套用“隨機數”來完成。

7.隨機數

隨機數（number)是在區間（0，1)上獨立和均勻分布的；隨機數字(digit)是在集合{0，1，2，3，…，9}上均勻分布的隨機數字可用來產生隨機數；從隨機數字表上選取合適的隨機數字，在選取的隨機數字的左邊加上十進制的小數點，可以構成隨機數；當用一組過程產生隨機數時，他們經常被稱為偽隨機數。

仿真實例

實例：假設6個顧客，到達時間間隔是隨機的，服務時間也是隨機的，仿真單服務台排隊系統。

基本假設：

1.顧客總體（無限）
顧客進入等候線或進入服務不會改變人的到達率；同時只有一個顧客以隨機的方式到達；顧客一旦進入等候線最終將得到服務。
2.服務時間
服從某一機率分布，分布不隨時間而變化。
3.系統的容量
無限的（被服務的人數加上等候的人數）。
4.被服務的規則
服務員進行服務的次序（ FCFS ，先來先服務）。
5.到達和服務描述
到達間隔時間分布和服務時間分布描述的整個有效的到達率必須小於最大的服務率。

仿真過程：

1.到達時間
　　 到達事件間隔和時鐘時間由擲6個值骰子五次並記錄它們的點數來產生，用來計算排隊系統的6個顧客的到達時間。

表1 到達間隔和時鐘時間

顧客	到達間隔時間	到達的時鐘時間
1	--	0
2	2	2
3	4	6
4	1	7
5	2	9
6	6	15

2.服務時間

服務時間假設有1，2，3，4個時間單位，假定所有的4個值等可能出現。把4個值預先刻在籌碼上，然後，輪迴隨機抽取籌碼，將選到的數據記錄下來。排隊系統到達間隔時間和服務時間必須匹配。

表2 服務時間

顧客	服務時間
1	2
2	1
3	3
4	2
5	1
6	4

3.仿真表

仿真表是為單服務台佇列設計的。仿真表記錄了每個事件出現時的時鐘時間。第2列是到達時間的時鐘時間；表第5列記錄了每個離開事件的時鐘時間；兩類事件按照時間順序排列。

表3 仿真表

顧客	到達時間; （時鐘）	開始服務時間（時鐘）	服務時間; （持續）	完成服務時間
1	0	0	2	2
2	2	2	1	3
3	6	6	3	9
4	7	9	2	11
5	9	11	1	12
6	15	15	4	19

4.服務顧客的規則：先進先出
　　5.按時間次序順序的事件

表4 仿真事件

事件類型	顧客	時鐘時間
到達	1	0
離開	1	2
到達	2	2
離開	2	3
到達	3	6
到達	4	7
離開	3	9
到達	5	9
離開	4	11
離開	5	12
到達	6	15
離開	6	19

套用範圍

單渠道隨機排隊法廣泛套用於港口的模擬，港口的等待時間分布問題；機場的模擬，飛機的起飛，著陸的分布問題等。