排隊系統(tǒng)的基本構(gòu)成

1、 排隊論排隊論（queuing theory）是一門應用十分廣泛的運籌學分支，它在各種存在等待情形的環(huán)境中都有非常成功的應用。盡管人們有時可能并不太在意等待時間的長短，但在許多商務活動中我們必須給顧客的等待時間以充分的重視。絕大多數(shù)大型零售店的設計其實就是平衡顧客方便度和企業(yè)運營效率的產(chǎn)物，這很好地解釋了為什么一個超級市場可能會有十幾個收銀通道，盡管在大多數(shù)時間里可能只有兩三個在運作。零售商不敢讓顧客在隊伍中等待太長的時間，因為時間對顧客來說可能是十分寶貴的，如果等待時間過長，他們完全有可能轉(zhuǎn)向自己的競爭者。在管理科學或運籌學中，等待的隊伍被稱為隊列（queue），排隊論作為運籌學的一個重要分

2、支在過去的幾十年里得到了長足的發(fā)展，代表特定環(huán)境的模型的數(shù)量 穩(wěn)步增加。作為最早的定量優(yōu)化方法之一，排隊論的起源可以追溯到1909年愛爾朗（A. K. Erlang, a Danish telephone engineer）發(fā)表的一篇論文，從那時起愛爾朗的名字就與概率排隊模型緊密聯(lián)系了在一起，該論文的發(fā)表為后來排隊論的發(fā)展奠定了堅實的基礎。排隊模型的目的就是要規(guī)劃一種為顧客提供服務的方式以實現(xiàn)一定的運營效率，它并不象前面已經(jīng)遇到的一些模型（如線性規(guī)劃模型、存貯模型）那樣追逐一個最小成本或最大收益目標。具體來講，排隊模型的目的就是要確定排隊系統(tǒng)的各項特征，如平均等待時間、平均隊長等；或者是構(gòu)建一

3、個服務系統(tǒng)以滿足特定的顧客服務水平。這些平均值是系統(tǒng)對顧客服務水平的標志，在后續(xù)的成本分析中將發(fā)揮重要的作用。§1排隊系統(tǒng)綜述在日常生活和生產(chǎn)中，人們會經(jīng)常碰到各種各樣的排隊系統(tǒng)，如道路紅綠燈系統(tǒng)、超市的收銀系統(tǒng)、電話通訊系統(tǒng)等。一些排隊系統(tǒng)的構(gòu)成十分明顯，而另一些排隊系統(tǒng)的構(gòu)成可能很模糊。如從廣州往北京打電話，由于受廣州與北京之間信道通過能力的限制，同一時間通話的人數(shù)是有限的；因此，當要求通話人數(shù)超過這一限制時，就不得不等待，雖然打電話的人分散在全市的各個角落，彼此互不見面，但他們與長話臺一起構(gòu)成一個服務系統(tǒng)，他們在長話臺前形成一個無形的隊伍，其實這種無形的隊伍與超市收銀系統(tǒng)中的有

4、形隊伍都可以構(gòu)成排隊系統(tǒng)中的隊列。在排隊系統(tǒng)中總是存在一組服務設施（service facility），有許多顧客（customer）隨機地來到該系統(tǒng)要求得到服務，服務完畢后即自動離去。如果顧客到達時有服務設施空閑，則到達的顧客即刻得到服務，否則顧客將排隊等待或離去。通常我們會自然地認為顧客就是來到服務系統(tǒng)準備接受服務的人，然而在排隊系統(tǒng)中顧客不該受到任何限制，可以是人，也可以是物。汽車修理廠等待維修的汽車、機場等待降落的飛機都可以構(gòu)成排隊系統(tǒng)中的顧客。在排隊系統(tǒng)中，服務設施同樣可以是人、物或者人和物的集合。如果顧客按固定的時間間隔到達服務系統(tǒng)，服務設施用在每個顧客身上的服務時間也是固定的，就

5、象工廠流水線的生產(chǎn)那樣有固定的節(jié)拍，那么這類服務系統(tǒng)的設計是十分簡便的。但在絕大多數(shù)的服務系統(tǒng)中，顧客的到達是隨機的，顧客的服務時間也是隨機的，這就意味著排隊論有著廣泛的應用前景。1.1 排隊系統(tǒng)的基本構(gòu)成一個排隊系統(tǒng)由輸入、隊列、服務臺和輸出四部分構(gòu)成，可以用圖10-1來加以描述。輸出輸入顧客總體隊列服務臺圖10-1 排隊系統(tǒng)構(gòu)成示意圖1輸入輸入描述的是顧客出現(xiàn)在排隊系統(tǒng)中的方式，人們通常用某種帶有任意參數(shù)和適當簡化假設的隨機過程來表示它。輸入過程又由如下一些元素構(gòu)成：（1）顧客總體顧客總體可以是一個有限的集合，也可以是一個無限的集合；但只要顧客總體所包含的元素數(shù)量充分大，就可以把顧客總體有

6、限的情況近似看成是顧客總體無限的情況來處理。上游河水流入水庫可以認為顧客總體是無限的，而工廠里等待修理的機器設備顯然是有限的顧客總體。（2）顧客到達的時點雖然顧客的到達可能是單個發(fā)生的，也可以是成批發(fā)生的，但在排隊系統(tǒng)中總是假設在同一時點上只能有一個顧客到達，同時到達的一批顧客只能看成是一個顧客。（3）顧客到達的相關(guān)性顧客到達可以是相互獨立的，也可以是相關(guān)聯(lián)的。所謂獨立即先前顧客的到達對后續(xù)顧客的到達沒有影響，否則就是相關(guān)的。（4）顧客到達的時間間隔顧客到達的時間間隔可以是確定的，也可以是隨機的。如在流水線上裝配的各部件必須按確定的時間間隔到達裝配點，定點運行的列車、班機的到達也都是確定的；但

7、商場購物的顧客、醫(yī)院診病的病人、通過路口的車輛的到達都是隨機的。對于隨機的情形，我們必須了解單位時間的顧客到達數(shù)或相繼到達的時間間隔的概率分布。（5）顧客到達的平穩(wěn)性平穩(wěn)性是指顧客到達的時間間隔分布及其特征參數(shù)（數(shù)學期望、方差等）不隨時間的變化而變化。最簡單的到達過程是符合泊松（Poisson）分布的隨機過程，在這種情況下，顧客到達的時間間隔是一系列相互獨立并具有負指數(shù)分布的隨機變量。2 隊列顧客到達時，如果所有服務臺都正在被占用，顧客可能選擇隨即離去或排隊等待。隨即離去的系統(tǒng)稱為即時制系統(tǒng)或損失制系統(tǒng)，排隊等待的系統(tǒng)稱為等待系統(tǒng)。普通電話的呼叫屬于損失制。系統(tǒng)如果有多個服務臺，各服務臺可以有

8、各自獨立的隊列，也可以有一個公共的隊列。隊列可以是具體的也可以是抽象的，可以是有限的也可以是無限的。在實際排隊系統(tǒng)中，有時顧客會因等待時間過長而中途離去，或因某些隊列服務較快而更換隊列，但在排隊論中假設這些復雜情況不發(fā)生。3服務臺一個排隊系統(tǒng)中可以有一個服務臺，也可以有多個服務臺。對于多服務臺來講，各服務臺可以串聯(lián)、并聯(lián)也可以混聯(lián)。（1）服務方式服務可針對單一顧客來進行，也可以針對一批顧客來進行。公共汽車對等候的顧客就是成批進行服務的。（2）服務時間服務時間同到達時間一樣，也可以分為確定和隨機兩種類型。自動沖洗汽車的裝置、紅綠燈系統(tǒng)屬于確定服務時間，而其他更常見的排隊系統(tǒng)大多屬于隨機服務時間。

9、（3）服務的平穩(wěn)性服務的平穩(wěn)性是指服務時間分布及其特征參數(shù)不隨時間的變化而變化。服務的平穩(wěn)性排除了工作時間長短（疲勞程度）以及對列長短（服務員有意加快各種速度）對服務時間分布的影響。（4）服務規(guī)則按對等待顧客的服務順序，服務規(guī)則可分為先到先服務（FIFO, first in, first out）、后到先服務（LIFO, last in, first out）、有優(yōu)先權(quán)的服務（SWP, service with priority）和隨機服務（SIRO, service in random order）。先到先服務對一般排隊系統(tǒng)是最符合常理的，但當顧客是一些待加工的工件時，就不存在明顯的誘因去遵

10、守先到先服務的規(guī)則，事實上，如果工件是一一堆起來的，那么服務規(guī)則自然是后到先服務；如果工件是無規(guī)則零散存放的，那么隨機服務規(guī)則可能是最合適的。有優(yōu)先權(quán)的服務即服務臺對具有某種特性的顧客給予有限服務，如醫(yī)院會優(yōu)先搶救危重病人。最簡單的服務時間分布是負指數(shù)分布，在這種情況下，平均服務率一個參數(shù)就完全描述了整個服務過程。4 輸出輸出是指顧客從得到服務到離開服務系統(tǒng)的情況，由于一結(jié)束服務顧客即刻離開服務系統(tǒng)，所以輸出是通過服務時間來加以描述的。1.2 排隊系統(tǒng)的分類描述根據(jù)排隊系統(tǒng)的基本構(gòu)成，肯達爾（Kendall）于1953年提出了排隊系統(tǒng)的分類描述法。這種方法是通過由斜線分割開的6項代碼來表示一個

11、特定排隊模型的。前兩項為字符碼，分別表示到達過程和服務過程的分布形式，通常用M代表泊松輸入（相繼到達間隔時間服從負指數(shù)分布）或服務時間服從負指數(shù)分布；D代表確定的相繼到達間隔時間或服務時間；EK代表k階愛爾朗（Erlang）分布的相繼到達間隔時間或服務時間；GI代表相互獨立的相繼到達間隔時間；G代表一般的服務時間。第三、四、五三項可以是數(shù)字型代碼，分別代表服務臺數(shù)目、系統(tǒng)的容量和顧客總量。最后一項表示排隊規(guī)則，即顧客接受服務的順序。此記法的前三項為必選項必須明確寫出，而后三項為選擇項，在系統(tǒng)容量無限、顧客總量無限和先到先服務的情況下，它們可以被省略。按照肯達爾排隊模型的記法，M/M/n代表顧客

12、輸入為泊松分布，服務時間為負指數(shù)分布，有n個并聯(lián)服務臺的排隊系統(tǒng)；M/D/2/N代表泊松分布的顧客到達，確定的服務時間，有2個并聯(lián)服務臺，系統(tǒng)容量為N的排隊系統(tǒng)；D/G/1代表定長輸入，一般服務時間，單個服務臺的排隊系統(tǒng)；GI/E3/c/10/10/LIFO代表相互獨立的相繼到達間隔時間，三階愛爾朗分布的服務時間，c個并聯(lián)服務臺，系統(tǒng)容量為10，顧客總量為10，后到先服務的排隊系統(tǒng)。1.3 排隊系統(tǒng)的數(shù)量指標一個特定的模型可能會有多種假設，同時也需要通過多種數(shù)量指標來加以描述。由于受所處環(huán)境的影響，我們只需要選擇那些起關(guān)鍵作用的指標作為模型求解的對象。環(huán)境不同，選擇的指標也會不同；例如，我們有

13、時關(guān)心的是顧客平均等待的時間，有時關(guān)心的是服務臺的利用率。盡管人們希望得到關(guān)于系統(tǒng)行為的詳細信息，但研究中所能夠給出的一切結(jié)果都只能是一個穩(wěn)定指標。穩(wěn)定指標并不意味著系統(tǒng)以某種固定的方式有規(guī)律地運轉(zhuǎn)，它們所提供的僅僅是這個系統(tǒng)經(jīng)歷長期運轉(zhuǎn)所反映出的數(shù)學期望值。1系統(tǒng)中顧客數(shù)量的概率分布（Pn）無論什么樣的排隊模型，都以Pn代表穩(wěn)定狀態(tài)下系統(tǒng)中包含n個顧客的概率，n的取值可以從0一直到系統(tǒng)容量N。2系統(tǒng)中顧客數(shù)量期望值（系統(tǒng)狀態(tài)，L）系統(tǒng)中顧客數(shù)量既包括正在接受服務的顧客，也包括排隊等待的顧客。3隊列中顧客數(shù)量期望值（對長，Lq）系統(tǒng)中等待服務的顧客數(shù)量，它等于系統(tǒng)狀態(tài)減去正在接受服務的顧客數(shù)。

14、4顧客在系統(tǒng)中的平均逗留時間（W）顧客在系統(tǒng)中的平均逗留時間包括顧客接受服務的時間，也包括顧客排隊等待的時間。5顧客的平均等待時間（Wq）顧客的平均等待時間等于其系統(tǒng)逗留時間減去服務時間。若用c表示并聯(lián)服務臺的數(shù)量，因此代表所有服務臺均被占用的概率或顧客被迫排隊的概率。被占用服務臺的個數(shù)是一個與系統(tǒng)狀態(tài)密切相關(guān)的隨機變量，當時有個服務臺被占用，當時有個服務臺被占用。這也就是說，在全部的服務臺被占滿之前，個服務臺被占用同系統(tǒng)中有個顧客是等價的。如果用代表有個顧客在隊列中的概率，那么 （）系統(tǒng)狀態(tài)L是系統(tǒng)中顧客數(shù)量期望值，因此與系統(tǒng)顧客數(shù)量的概率分布Pn具有如下關(guān)系： （10-1）用B表示被占用服

15、務臺數(shù)量的期望值，則： （10-2）Lq是對長，代表隊列中顧客數(shù)量的期望值，則： （10-3）于是： （10-4）即系統(tǒng)中顧客數(shù)量期望值等于隊列中顧客數(shù)量期望值與被占用服務臺數(shù)量的期望值之和。如果用代表服務時間期望值，與式（10-4）類似有： （10-5）用U代表服務臺利用率期望值，由于各服務臺的利用率不盡相同，所以U是所有服務臺綜合的利用率期望值。服務臺利用率期望值應該等于被占用服務臺數(shù)量的期望值與總服務臺數(shù)之比，即： （10-6）如果，式（10-6）可簡化為。§2 排隊系統(tǒng)的數(shù)學模型2.1 最簡單流在排隊論中經(jīng)常用到最簡單流這一概念。所謂最簡單流就是指在這一時間段里有個顧客到達服

16、務系統(tǒng)的概率服從泊松分布，即： （） （10-7）由于最簡單流與實際顧客到達流的近似性，更是由于最簡單流假設極大地簡化了問題的分析與計算，因此排隊論所研究的問題普遍是最簡單流問題。什么樣的排隊系統(tǒng)才能具有最簡單流呢？我們可以通過如下三個標準來加以判斷：1平穩(wěn)性平穩(wěn)性是指在一定的時間間隔內(nèi)，來到服務系統(tǒng)的顧客數(shù)量只與這段時間間隔的長短有關(guān)，而與這段時間間隔的起始時刻無關(guān)。2獨立性獨立性是指顧客的到達率與系統(tǒng)的狀態(tài)無關(guān)，無論系統(tǒng)中有多少顧客，顧客的到達率不變。3唯一性在一個充分小的時間間隔里不可能有兩個或兩個以上的顧客到達，只能有一個顧客到達。式（10-7）中的參數(shù)代表單位時間里到達顧客的平均數(shù)，

17、即平均到達率。我們可以通過令求的數(shù)學期望來加以證明：既然代表單位時間里到達顧客的平均數(shù)，那么自然代表平均的顧客到達時間間隔。2.2 負指數(shù)分布的服務時間負指數(shù)分布具有如下的概率密度函數(shù)和分布函數(shù)：，假設服務臺對顧客的服務時間服從負指數(shù)分布，即；則對于每一顧客的平均服務時間為，而自然代表服務率。這一點可以通過如下式子加以證明：2.3 生死過程一個顧客的到達將使系統(tǒng)狀態(tài)從到，這一過程成為生；一個顧客的離開將使系統(tǒng)狀態(tài)從到，這一過程成為死。系統(tǒng)狀態(tài)的轉(zhuǎn)移可以用狀態(tài)轉(zhuǎn)移圖（圖10-2）來加以描述，圖中結(jié)點代表狀態(tài)，箭線代表狀態(tài)轉(zhuǎn)移。由于在同一時間不可能有兩個事件發(fā)生，所以不存在跨狀態(tài)的狀態(tài)轉(zhuǎn)移。0nn

18、-121n+1生死圖10-2 生死過程示意圖利用圖10-2所示的狀態(tài)轉(zhuǎn)移形式，根據(jù)流的平衡原理可以建立起穩(wěn)定狀態(tài)的狀態(tài)轉(zhuǎn)移方程組。所謂流的平衡原理就是在穩(wěn)定狀態(tài)下，流入任意一個結(jié)點的流量等于流出該結(jié)點的流量。流量的概念是這樣定義的，如果從狀態(tài)i到狀態(tài) j轉(zhuǎn)移弧上的轉(zhuǎn)移率為rij，那么這條轉(zhuǎn)移弧所發(fā)生的流量就是rij pi。流的平衡原理具有鮮明的直觀性和廣泛的適用性。將流的平衡原理應用于轉(zhuǎn)移圖的各個狀態(tài)，每一狀態(tài)都可給出一個以pi為變量的線性方程。這些線性方程組成的線性方程組無條件地決定了pi的分布。¼¼¼¼流的平衡方程具有一種特別易于手工求解的形式，第一

19、個方程是根據(jù)狀態(tài)“0”的流平衡條件建立的，因為與狀態(tài)“0”相鄰的狀態(tài)只有狀態(tài)“1”，所以此方程只含有p0和p1兩個未知量。雖然p0和p1都隨模型的變化而變化，但利用此方程用p0表示p1總是可以實現(xiàn)的。第二個方程是根據(jù)狀態(tài)“1”的流平衡條件建立的，它涉及p0、p1和p2三個未知量。通過以p0表示p1，可以把未知量減少為p0和p2兩個，進而實現(xiàn)用p0表示p2。依次類推，每一個方程均可以把一個新的未知量表示為p0的函數(shù)，直到將所有的未知量都用p0表示出來。因為此時每一個pi都已表示為p0的函數(shù)，所以正規(guī)方程可表示為只含p0一個未知量的形式，進而求的p0和其他所有的狀態(tài)概率pi。如果模型含有無限個狀態(tài)

20、，正規(guī)方程可表示為只含p0一個未知量的無窮序列。對于系統(tǒng)容量無限的排隊系統(tǒng)，按照上述求解過程可以得到如下結(jié)果：¼¼¼¼引入正規(guī)方程有：出現(xiàn)在方括號中的無窮序列是一個簡單的等比序列，倘若是一個小于1的數(shù)，那么該等比序列將收斂于一個有限的和。解該正規(guī)方程有：進而有：從上述的概率分布解可以看出，和兩個參數(shù)總是以比值的形式出現(xiàn)在一起，所以我們可以用一個小寫的希臘字母來代替，即。將代入上述解中去可使其更具簡明的形式：新的參數(shù)是到達率與服務率之比，被稱為繁忙率。也可以有其他的表現(xiàn)形式，如，此時的含義是平均服務時間與相繼到達平均間隔時間之比；，此時的含義是到達率與平均

21、服務時間的積，即在一個平均服務時間里到達的平均顧客數(shù)量。的所有這些含義，均給出了要求的邏輯解釋；簡言之，如果顧客的平均到達率大于平均服務率，那么系統(tǒng)的隊長將無限增加，從而造成系統(tǒng)永遠也達不到穩(wěn)定狀態(tài)。2.4 基本模型由于系統(tǒng)中顧客的數(shù)量越多，顧客在系統(tǒng)中逗留的時間也就會越長，所以可以希望在W和L之間建立起某種關(guān)系。李特爾（Little）公式給出了L、W和三者之間的關(guān)系，即系統(tǒng)中平均顧客數(shù)等于顧客平均到達率與平均逗留時間的積。根據(jù)李特爾公式，自然可以得到關(guān)系式。有了李特爾公式，即可得到如下排隊系統(tǒng)的基本模型： （10-8） （10-9） （10-10） （10-11）需要強調(diào)的是，本節(jié)所涉及的所

22、有模型均是基于排隊系統(tǒng)構(gòu)建的，對于其他排隊系統(tǒng)，應根據(jù)系統(tǒng)的具體情況對某些模型進行適當?shù)恼{(diào)整。，即代表了平均被占用的服務臺數(shù)或服務臺利用率。從式（10-8）和式（10-10）可以顯示出一個令人關(guān)心的問題，為了限制平均隊長為一個適度小的數(shù)值，那么就不得不犧牲一定的服務臺利用率。例如，要保持，那么服務臺利用率就一定不會超過90%。也就是說為了確保系統(tǒng)中的顧客數(shù)不超過9人，必須容忍服務臺有10%的空閑時間。§3排隊模型的應用例10-1 某醫(yī)院的一個診室根據(jù)病人來診和診治的時間記錄，任意抽查100個工作小時，每小時來就診的病人數(shù)n的出現(xiàn)次數(shù)，以及任意抽查100個完成診治的病人病歷，所用時間v

23、出現(xiàn)的次數(shù)如表10-1所示，試分析該排隊系統(tǒng)。表10-1病人到達數(shù)n出現(xiàn)次數(shù)fn診治時間v出現(xiàn)次數(shù)fv0100.0 0.2381280.2 0.4252290.4 0.6173160.6 0.894100.8 1.06561.0 1.25611.2 1.40合 計100合 計100解：將此排隊系統(tǒng)抽象為模型（1）計算每小時病人的平均到達數(shù)，即到達率（人/小時）（2）計算每次診治的平均時間（v值取區(qū)間中值）每次診治的平均時間（小時/人）（3）每小時平均完成的診治人數(shù)（服務率）（人/小時）（4）通過統(tǒng)計檢驗的方法，認定在一定顯著水平下，病人的到達服從參數(shù)為2.1的泊松分布，診治時間服從參數(shù)為2.5

24、負指數(shù)分布。具體檢驗過程可參見數(shù)理統(tǒng)計學。（5）計算繁忙率說明該診室有84%的時間在為病人服務，有16%的時間是空閑的。（6）計算各排隊系統(tǒng)指標（人）（人）（小時）（小時）例10-2 顧客到達只有一名理發(fā)師的理發(fā)部，顧客平均每20分鐘到達一位，每位顧客的處理時間為15分鐘。假設以上兩種時間均服從負指數(shù)分布，若該理發(fā)部希望90%的顧客都能有座位，則應設置多少個等待席位。解：將此排隊系統(tǒng)抽象為模型并設等待席位為N90%的顧客都能有座位，相當于該理發(fā)部內(nèi)的顧客總數(shù)不多于N +1的概率不小于0.9，即：例10-3 某一大型客運公司，機車大修率服從泊松分布，平均每天2臺。機修廠對每臺大修機車的修理時間服

25、從負指數(shù)分布，平均每臺天。是一個與修理廠年度運行費用K有關(guān)的函數(shù)，（其中元）。又已知機車大修平均每天損失1000元，試決定該客運公司機修廠最佳的年度運行費用。解：將此排隊系統(tǒng)抽象為模型（1）計算每月機車發(fā)生故障造成的損失S1S1 = （系統(tǒng)中的機車數(shù)）´（每輛每天損失）´（月工作日數(shù)）（2）計算每月機修廠的運行費用S2（3）計算每月總費用S（4）求最佳的年度運行費用（萬元）（輛/天）例10-4 某一個只有一名理發(fā)師的理發(fā)部，有3個座位供顧客排隊等待，當3個等待座位都被占用時，后來的顧客會自動離開。顧客的平均到達率為每小時3人，理發(fā)的平均時間為15分鐘，試分析該排隊系統(tǒng)的運行

26、情況。解：將此排隊系統(tǒng)抽象為模型，其狀態(tài)轉(zhuǎn)移模型如圖10-334021生死圖10-3利用流平衡方程組可以得到與模型具有相同形式的狀態(tài)概率分布： （）再利用正規(guī)方程即可求得系統(tǒng)空閑的概率：（1）計算顧客一到達即刻就能得到服務的概率，（2）理發(fā)部內(nèi)的平均顧客數(shù)和隊列中等待的平均顧客數(shù)（3）有效的到達率在隊長受到限制的情況下，當系統(tǒng)滿員時，新來的顧客會自動離開；雖然顧客以的速率來到服務系統(tǒng)，但由于一部分顧客的自動離開，真正進入系統(tǒng)的顧客輸入率應該是比小的。因為服務系統(tǒng)的利用率可以從兩個不同的角度表達為或，即，所以應有。（人/小時）（4）顧客在理發(fā)部的平均逗留時間和平均等待時間（小時）（分鐘）（小時）

27、（分鐘）（5）顧客的損失率例10-5 某醫(yī)院門前有一個出租車?？空?，因場地的限制只有5個停車位，在沒有停車位時新來的出租車會自動離開。當停靠站有車時，從醫(yī)院出來的病人就租車；當?？空緹o車時，病人就向出租公司要車。設出租車以平均每小時8輛（）的泊松分布到達?？空?，從醫(yī)院出來病人的間隔時間為負指數(shù)分布，平均間隔時間為6分鐘。試求（1）出租車來到醫(yī)院門前，?？空居锌瘴坏母怕剩唬?）進入?？空镜某鲎廛嚨钠骄却龝r間；（3）從醫(yī)院出來的病人直接租到車的概率。解：將?？空九c到達的出租車作為一個排隊系統(tǒng)，1號車位相當于正在接受服務的位置，2、3、4、5號車位相當于隊列，這樣就構(gòu)建了一個排隊模型。在該排隊系統(tǒng)

28、中有效的服務率：同上例：，將系統(tǒng)狀態(tài)、和列于表10-2，便可十分方便地回答本例的各個問題。 表10-200.180010.1740.17420.1690.33830.1640.49240.1590.63650.1540.770合 計1.0002.410（1）出租車來到醫(yī)院門前，?？空居锌瘴坏母怕剩?）進入停靠站的出租車的平均等待時間（小時）（分鐘）（3）從醫(yī)院出來的病人直接租到車的概率例10-6 設一名工人負責照管6臺自動機床，當機床需要加料或發(fā)生故障時就自動停機，等待工人處理。設機床平均的停機間隔為1小時（），工人處理的平均時間為0.1小時（），以上兩個時間均服從負指數(shù)分布。試計算系統(tǒng)的各項

29、指標。解：該例屬于顧客總體有限的排隊系統(tǒng)，記為，可用圖10-4加以描述。有限的顧客源圖10-4 有限源排隊系統(tǒng)示意圖這種模型同前面討論過的模型的主要區(qū)別就在于到達率的不同。通過直覺的分析，我們可以得到這樣的結(jié)論：顧客源中的潛在顧客越多，顧客的到達率越大；而系統(tǒng)中的顧客越多，顧客的到達率越小。在顧客源變空（所有顧客均在系統(tǒng)中）的極限狀態(tài)，顧客的到達率自然減少到“0”。令代表每一個顧客的平均到達率，它可以通過觀測每一個顧客在顧客源中所逗留的時間來加以統(tǒng)計。顧客在顧客源中所逗留的時間是指從某一顧客接受完服務回到顧客源到他再次進入排隊系統(tǒng)所經(jīng)歷的時間。假設此時間服從具有共同數(shù)學期望的負指數(shù)分布，那么將

30、是平均逗留時間的倒數(shù)。需要注意的是，此時的不能象以往一樣通過觀測顧客到達系統(tǒng)的時間間隔來推算，因為此時的時間間隔與系統(tǒng)中的顧客數(shù)之間存在相關(guān)關(guān)系，這樣得到的到達率僅僅是整個系統(tǒng)的平均到達率而不是每一個顧客的平均到達率。34021圖10-556如果只有一個顧客在顧客源中而其他顧客均在系統(tǒng)中，很顯然此時的顧客到達率就是；如果顧客源中有兩個顧客，那么此時的顧客到達率將是2，這樣依次類推可以得到圖10-5所示的系統(tǒng)狀態(tài)轉(zhuǎn)移圖。根據(jù)圖10-5可得穩(wěn)定狀態(tài)流平衡方程：求解這些方程可得一般形式的解：此例，所以有：， ， ， 又由于，所以有，進而有：（1） 工人的忙期（2） 系統(tǒng)內(nèi)的平均機床數(shù)和隊列中等待的平

31、均機床數(shù)（3） 機床每次停機的平均時間和等待處理的平均時間（小時）（分鐘）（小時）（分鐘）（4） 機床停機時間占總時間的比率例10-7 如果將上例改為三名工人聯(lián)合負責看管20臺自動機床，其他各項數(shù)據(jù)不變，試分析系統(tǒng)的各項指標。解：該例屬于顧客總體有限并聯(lián)服務臺的排隊系統(tǒng)，記為，即，；系統(tǒng)狀態(tài)轉(zhuǎn)移如圖10-6所示。¼34021圖10-619520根據(jù)圖10-6可得穩(wěn)定狀態(tài)流平衡方程，從而計算出系統(tǒng)狀態(tài)的概率分布。計算數(shù)據(jù)列于表10-3中，由于當時，故忽略不計。（1） 工人的平均空閑時間（2） 工人的忙期（3） 系統(tǒng)內(nèi)的平均機床數(shù)和隊列中等待的平均機床數(shù)（4） 機床停機時間占總時間的比率

32、（5） 機床每次停機的平均時間和等待處理的平均時間（小時）（分鐘）（小時）（分鐘）表10-3狀態(tài)i處理數(shù)等待數(shù)空閑人數(shù)Pi /P0Pi(i-3) PiiPi00031.00000.13626-11022.00000.27250-0.2725022011.90000.25888-0.5177633001.14000.15533-0.4659943100.64600.088020.088020.3520853200.34450.046940.093880.2347063300.17220.023470.070410.1408273400.08040.010950.043800.0766583500

33、.03480.004750.023750.0388093600.01390.001900.011400.01710103700.00510.000700.004900.00700113800.00170.000230.001840.00253123900.00050.000070.000630.00084比較上述二例，可以看出當三名工人聯(lián)合看管20臺機床時，雖然每一名工人平均看管的機床數(shù)增加了，但機床的利用率反而卻提高了，這是三名工人相互協(xié)作的結(jié)果。例10-8 某自餐廳有三個服務窗口，假設顧客的到達服從泊松分布，平均到達率人/分鐘，服務時間服從負指數(shù)分布，平均服務率人/分鐘?，F(xiàn)假設顧客到達后排

34、成一個統(tǒng)一的隊列，從前依次向空閑的窗口購餐，試分析該排隊系統(tǒng)的各項指標。解：該例屬于顧客總體無限、系統(tǒng)容量無限的并聯(lián)服務系統(tǒng)，記為，即；系統(tǒng)狀態(tài)轉(zhuǎn)移如圖10-7所示。¼01圖10-7SS+1S-1S+25根據(jù)圖10-7可得穩(wěn)定狀態(tài)流平衡方程： （） （）這里，且。用遞推法可求解出系統(tǒng)各狀態(tài)的概率： （） （）利用各狀態(tài)概率，可求得系統(tǒng)的運行指標：， 此例，；因此：（1） 餐廳的空閑率（2） 隊列中的平均顧客數(shù)（人）（3） 系統(tǒng)中的平均顧客數(shù)（人）（4） 顧客在隊列中的平均等待時間（分鐘）（5） 顧客在系統(tǒng)中的平均逗留時間（不包括就餐的時間）（分鐘）（6） 顧客到達需要等待的概率例10

35、-9 在黑龍江省的大慶市有一座糧庫，由于該市處于高寒的平原地帶，小麥是其最主要的農(nóng)作物。在收獲的季節(jié)里，卡車載著小麥從田地運往糧庫并盡可能快地返回再運下一車。在卡車將小麥傾入烘干爐之前，要抽樣檢查小麥的質(zhì)量，當然還有稱重等其他一些驗收細節(jié)。因小麥一旦成熟很容易受到風雨的侵蝕，任何耽擱都會給農(nóng)場帶來巨大的損失，所以農(nóng)場總是想盡快收完田里的小麥并運往糧庫。由于該市的所有小麥幾乎是在同一時間成熟的，因此在糧庫產(chǎn)生車輛排隊問題并不令人驚奇。為方便起見，假設卡車相繼到達的時間間隔是6.67分鐘，平均服務時間為6分鐘，這樣利用模型的標準公式就能計算出每輛卡車在糧庫的平均逗留時間。這一時間應與實際消耗的時間

36、相匹配，如有耽擱農(nóng)場會認為是無法忍受的。在農(nóng)場合作大會上，提出了三種完善糧庫收糧系統(tǒng)的方案：1增加卡車負荷，這樣卡車相繼到達的時間間隔將增至10分鐘；同時增加驗收人員，使平均服務時間減少為4分鐘。這種相對較小的系統(tǒng)調(diào)整，預計需要花費3萬元。2一些農(nóng)場認為，盡管第一個方案能在一定程度上緩解矛盾，但并不能從根本上解決問題。他們相信進行較大的改造是必要的，主張對糧庫進行擴建，使服務能力提高一倍。到達的卡車排成一個統(tǒng)一的隊列，最前面的車將進入最早可利用的驗收站接受驗收。這一改造大約需要40萬元。3一些農(nóng)場認為應該在城市的另一處再單獨建一座與現(xiàn)有糧庫完全相同的新糧庫。這一方案除了把整個服務能力提高一倍外

37、，還把車輛的到達分為兩等份，其預算投資為100萬元。經(jīng)過初步分析，大家普遍認為：第一個方案雖然從費用角度具有一定的吸引力，但如此小的調(diào)整對于解決如此嚴重的問題其效果不會理想；第三個方案似乎提供了一種根本的解決問題的方法，但所需的費用將成為巨大的經(jīng)濟負擔；第二個方案才是權(quán)衡的最佳選擇?；谏鲜稣J識，你將做出怎樣的選擇呢？用排隊論的術(shù)語來講，第一個方案只改變了模型的參數(shù)而沒有改變模型的結(jié)構(gòu)；第二個方案形成一個單隊列雙服務臺服務系統(tǒng)；第三個方案形成一個雙隊列雙服務臺系統(tǒng)。假設卡車到達服從泊松分布，服務時間服從負指數(shù)分布，可利用簡單的馬爾科夫排隊模型進行分析。方案一和方案二的分析可以直接利用前例中的相

38、應模型來進行，而方案三需要分解為兩個獨立的系統(tǒng)。由于這兩個獨立的系統(tǒng)具有相同的系統(tǒng)參數(shù)；因此，在分析個別車輛時，只研究其中一個系統(tǒng)就足夠了。表10-4給出了各方案車輛在系統(tǒng)中的平均逗留時間，這一結(jié)果足以使你大吃一驚，花錢最少的方案（方案一）卻產(chǎn)生了最佳的系統(tǒng)完善效果，這是每一個農(nóng)場單憑直覺無法想象的。表10-4方 案模 型到 達 率服 務 率逗 留 時 間現(xiàn)方案9（人/小時）10（人/小時）60（分鐘）16156.6729107.5234.51010.91§4非馬爾科夫排隊模型上述的一切排隊模型都是以馬爾科夫模型（最簡單流）為基礎的，系統(tǒng)的概率分布處于負指數(shù)分布這一基本假設的約束之下

39、。雖然這一假設為我們帶來了許多方便，但有時它確實與實際情況具有相當大的差距。因此，特別需要那些不嚴格依靠馬爾科夫假設的排隊模型。 鑒于此，本節(jié)將對幾種典型的非馬爾科夫排隊模型進行簡單的介紹。依據(jù)前面的分析，下述關(guān)系式無論在什么情況下都應該是成立的：其中：為服務臺中顧客數(shù)量期望值，為服務時間期望值。4.1 模型對于模型，服務時間是一般分布（但要求期望值和方差都存在），其他條件與相同。為了達到穩(wěn)定狀態(tài)，這一條件還是必要的，這里。在上述條件下有：此式被稱為Pollaczek-Khintchine（P-K）公式，只要知道、和，不管是什么分布，都可以求出系統(tǒng)中的平均顧客數(shù)，進而通過一定的關(guān)系式求出、和。

40、例10-10 顧客按平均2分30秒的時間間隔的負指數(shù)分布到達某一排隊系統(tǒng)，平均服務時間為2分鐘。（1）若服務時間也服從負指數(shù)分布，求顧客的平均逗留時間和等待時間；（2）若服務時間至少需要1分鐘且服從如下分布：， ， 再求顧客的平均逗留時間和等待時間。解：（1），（分鐘）（分鐘）（2）令為服務時間，那么，其中是服從均值為1的負指數(shù)分布；于是，。代入P-K公式得：，（分鐘），（分鐘）4.2 模型對于服務時間是確定常數(shù)的情形，由于有和，所以P-K公式將簡化為：例10-11 一自動汽車清洗機，清洗每輛汽車的時間均為6分鐘，汽車按泊松分布到達，平均每15分鐘來一輛。試求、和。 解：此系統(tǒng)是排隊系統(tǒng)，其中

41、：，（輛）（輛）（小時）（分鐘）（小時）（分鐘）通過P-K公式可以證明，在一般分布的服務時間中，定長服務時間的、和最小。這完全符合人們通常的理解，即服務時間越有規(guī)律，等候的時間也就越短。例10-12 一裝卸隊專為來到碼頭倉庫的貨車裝卸貨物，設貨車的到達服從泊松分布，平均每10分鐘一輛，而裝卸時間與裝卸隊的人數(shù)成反比。又設該裝卸隊每班（8小時）的生產(chǎn)費用為元，汽車在碼頭裝卸貨物時每小時的損失是15元。若（1）裝卸時間為常數(shù)，一名裝卸工人裝卸一輛汽車需要30分鐘，（2）裝卸時間為負指數(shù)分布，一名裝卸工人裝卸一輛汽車需要30分鐘；試分別確定該裝卸隊應配備的裝卸工人數(shù)。解：計算一小時的費用，該費用包括

42、裝卸隊費用和汽車在系統(tǒng)中逗留的損失，即：（1）裝卸時間為常數(shù)，于是，代入的表達式有：所以：令，可得：經(jīng)過試算，該方程在11和12之間有一個根，分別比較二者所對應的費用值，因有、，故裝卸隊應配備11名裝卸工人。（2）裝卸時間為負指數(shù)分布令，可得：，從而比較和，由于，故裝卸隊配備12或13名裝卸工人均可。4.3 模型當服務時間為定長時，均方差；當服務時間為負指數(shù)分布時，均方差；而均方差介于這二者之間的一種理論分布稱為愛爾朗（Erlang）分布。假設、¼、為個具有相同分布而又相互獨立的負指數(shù)分布，其概率密度分別為： （）其中、是取正值的參數(shù)，而且取整數(shù)。服務時間概率密度函數(shù)圖10-8如果服

43、務臺對顧客的服務不是一項，而是按順序進行的項，又假設其中每一項服務的服務時間都具有相同的負指數(shù)分布，則總的服務時間服從階愛爾朗分布。實際上愛爾朗分布是Gamma分布的一個特例，愛爾朗分布的數(shù)學期望和方差分別為、。這里有兩個參數(shù)和，有于值的不同，可以得到不同的愛爾朗分布，見圖10-8。當時是負指數(shù)分布，當時是定長分布。將代入P-K公式得：， ， 如上所述，階愛爾朗分布的服務時間可用來描述個服務臺串聯(lián)的排隊系統(tǒng)。當然，這里要求每個服務臺的服務時間相互獨立且服從相同的負指數(shù)分布，各服務臺前的隊列容量無限。例10-13 某產(chǎn)品的生產(chǎn)需要經(jīng)過4道工序，每一工序的工序時間均服從期望值為2（小時）的負指數(shù)分

44、布。該產(chǎn)品的毛坯按泊松分布到達，平均到達率為每小時0.1件，問計算毛坯經(jīng)過4道工序的期望時間。解：設為平均服務率，那么就是每件產(chǎn)品的平均服務時間，而即是平均每道工序所需要的時間。依題意可知：，（即），。于是：（件）（小時）即毛坯經(jīng)過4道工序的期望時間為28小時。§5具有優(yōu)先級的排隊模型在具有優(yōu)先級的排隊模型中，服務對象的選擇并不嚴格按照先到先服務的規(guī)則，如醫(yī)院優(yōu)先搶救急重病人，列車運行客車優(yōu)先貨車、快車優(yōu)先慢車等等。可見在這類模型中，顧客是有等級區(qū)別的，較高等級的顧客比較低等級的顧客具有優(yōu)先接受服務的權(quán)力。假設顧客可以分為個等級，第一級享有至高的優(yōu)先權(quán)，第級享有最低的優(yōu)先權(quán)，對同屬一

45、級別的顧客仍然按先到先服務的規(guī)則選擇服務對象。又假設系統(tǒng)中每一級別顧客的輸入均服從泊松分布，用（）代表具有第優(yōu)先級顧客的平均到達率；每一級別顧客的服務時間均服從負指數(shù)分布，且不管級別的差異都具有相同的服務率（表示每名顧客的服務時間）。再假設當一個具有較高級別顧客到達時，正在接受服務的較低級顧客將被中斷服務，回到排隊系統(tǒng)等待重新得到服務。根據(jù)以上假設，對具有最高級別優(yōu)先級的顧客來講，只有當系統(tǒng)中正在接受服務的顧客也具有最高級別優(yōu)先級的時候，他才需要等待，其他情況均可以立刻得到服務。因此，對于具有最高級別優(yōu)先級的顧客在排隊系統(tǒng)中得到服務的情況就如同沒有其他級別的顧客一樣。所以，對最高級別優(yōu)先級的顧

46、客只要將輸入率換以，此章較前推導的公式是完全適用的?，F(xiàn)在一并考慮第一、第二優(yōu)先級的顧客，設表示一、二兩級綜合在一起的每個顧客在系統(tǒng)中的平均逗留時間；根據(jù)負指數(shù)分布的性質(zhì)，對由于高級別顧客到達而中斷服務回到隊列中的顧客，無論他被中斷幾次，他所接受服務的總時間不會有所改變。因此，對只要將一、二兩級顧客的輸入率簡單相加即可，所以有：其中和分別表示具有第一、第二優(yōu)先級的顧客在系統(tǒng)中的平均逗留時間。將此式變形有： 同理有： 即： 依次類推有： 其中。例10-14 某醫(yī)院門診部的患者按泊松分布到達，平均到達率人/小時，醫(yī)生對患者的服務時間服從負指數(shù)分布，服務率人/小時。假設患者中有60%屬于一般患者，30

47、%屬于重病患者，10%屬于病?；颊?，分別就該門診部有一名醫(yī)生和兩名醫(yī)生的情況，計算各類患者等待醫(yī)治的平均等待時間。解：依題可知、（1） 一名醫(yī)生所以：（小時）（分鐘）（小時）（分鐘）（小時）（分鐘）（2） 兩名醫(yī)生利用模型的、公式，可推得。所以：（小時）（分鐘）（小時）（分鐘）（小時）（分鐘）§6排隊系統(tǒng)的最優(yōu)化排隊系統(tǒng)的最優(yōu)化問題可分為兩類，即系統(tǒng)設計的最優(yōu)化和系統(tǒng)控制的最優(yōu)化。前者稱為靜態(tài)問題，從排隊論一誕生起就成為人們研究的內(nèi)容，目的在于使新構(gòu)建的系統(tǒng)有最大的效益；后者稱為動態(tài)問題，是指一個給定的系統(tǒng)如何根據(jù)環(huán)境的變化做出適當?shù)恼{(diào)整，以使某些系統(tǒng)指標得到優(yōu)化。進入80年代以來，

48、動態(tài)問題成為了排隊論研究的重點之一。動態(tài)分析是建立在靜態(tài)分析的基礎之上的，本教材只討論靜態(tài)最優(yōu)化問題。排隊系統(tǒng)存在兩類費用，即與服務設施相關(guān)的服務費用和與顧客等待時間長短相關(guān)的等待費用。費用模型的出發(fā)點就是要使這兩類費用的總和最小，各種費用在穩(wěn)定狀態(tài)下都是按單位時間來考慮的。一般情況下，服務費用是可以較精確計算或估計的，而顧客的等待費用較為復雜。如機械故障問題中的等待費用可以較精確地估計，但象患者就診或由于隊列太長而失掉顧客所造成的損失，就只能根據(jù)統(tǒng)計經(jīng)驗來加以估計了。6.1 模型中最優(yōu)服務率的確定設系統(tǒng)單位時間的服務費用與值成正比，比例系數(shù)為；每一個顧客在系統(tǒng)中逗留（包括接受服務的時間）的等

49、待費用與等待時間成正比，比例系數(shù)為，如果用表示在給定值時的系統(tǒng)總費用，則：當、一定時，最佳服務率只與顧客的到達率有關(guān)，根號前取“+”號是因為的緣故。對于排隊系統(tǒng)，為顧客被拒絕的概率，就是顧客被接受的概率，所以就是單位時間實際進入系統(tǒng)的平均顧客數(shù)。在穩(wěn)定狀態(tài)下，也等于單位時間完成服務的平均顧客數(shù)。設每服務1人可收入元，于是單位時間收入的期望值是，純利潤是。用代表純利潤，于是：令，可得。1694321圖10-9即最佳服務率應滿足此式，雖然此式中的、（）和都是已知數(shù)，但要通過此式求解出卻不是一件容易的事。對該問題的處理，我們經(jīng)常將式子的左側(cè)（對一定的）作為的函數(shù)繪制出圖形（如圖10-9），對于給定的

50、根據(jù)圖形可直接求出，從而求出。對于排隊系統(tǒng)，我們?nèi)匀话凑赵O備故障問題來加以考慮。設共有臺設備，設備連續(xù)運轉(zhuǎn)的時間服從負指數(shù)分布；有一名維修人員，其處理故障的時間服從負指數(shù)分布。的含義同上，為單位時間每臺運轉(zhuǎn)設備可得的收益，設備的平均運轉(zhuǎn)臺數(shù)為，所以單位時間的純收益為：式中的，稱為泊松部分和，而求，可得。2110.5圖10-10當給定、，要由上式求解出也是很困難的。對此問題的處理，我們經(jīng)常將式子的左側(cè)（對一定的）作為的函數(shù)繪制出圖形（如圖10-10），對于給定的根據(jù)圖形可直接求出，從而求出。6.2 模型中最優(yōu)服務臺數(shù)的確定設、分別代表每一服務臺單位時間的成本和每一顧客在系統(tǒng)中逗留單位時間的費用。因為只能取整數(shù)，所以不是連續(xù)函數(shù)，因此無法使用微分法，只能使用邊際分析法。根據(jù)是最小值的特點，可得和；將代入這兩個不等式，可得：化簡可得，依次求時的值并計算相鄰兩個值的差，因是已知數(shù)，根據(jù)所在的不等式區(qū)間就可以確定的值。例10-15 某車間有一個工具維修部，要求維修的工具按泊松流到達，平均每小時17.5件；維修部工人每人每小時平均維修10件，服