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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、出現(xiàn)的次數(shù)如表10-1所示，試分析該排隊(duì)系統(tǒng)。表10-1病人到達(dá)數(shù)n出現(xiàn)次數(shù)fn診治時(shí)間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合 計(jì)100合 計(jì)100解：將此排隊(duì)系統(tǒng)抽象為模型（1）計(jì)算每小時(shí)病人的平均到達(dá)數(shù)，即到達(dá)率（人/小時(shí)）（2）計(jì)算每次診治的平均時(shí)間（v值取區(qū)間中值）每次診治的平均時(shí)間（小時(shí)/人）（3）每小時(shí)平均完成的診治人數(shù)（服務(wù)率）（人/小時(shí)）（4）通過(guò)統(tǒng)計(jì)檢驗(yàn)的方法，認(rèn)定在一定顯著水平下，病人的到達(dá)服從參數(shù)為2.1的泊松分布，診治時(shí)間服從參數(shù)為2.5

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

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

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

27、（分鐘）（5）顧客的損失率例10-5 某醫(yī)院門(mén)前有一個(gè)出租車(chē)?？空荆驁?chǎng)地的限制只有5個(gè)停車(chē)位，在沒(méi)有停車(chē)位時(shí)新來(lái)的出租車(chē)會(huì)自動(dòng)離開(kāi)。當(dāng)?？空居熊?chē)時(shí)，從醫(yī)院出來(lái)的病人就租車(chē)；當(dāng)?？空緹o(wú)車(chē)時(shí)，病人就向出租公司要車(chē)。設(shè)出租車(chē)以平均每小時(shí)8輛（）的泊松分布到達(dá)?？空?，從醫(yī)院出來(lái)病人的間隔時(shí)間為負(fù)指數(shù)分布，平均間隔時(shí)間為6分鐘。試求（1）出租車(chē)來(lái)到醫(yī)院門(mén)前，停靠站有空位的概率；（2）進(jìn)入?？空镜某鲎廛?chē)的平均等待時(shí)間；（3）從醫(yī)院出來(lái)的病人直接租到車(chē)的概率。解：將?？空九c到達(dá)的出租車(chē)作為一個(gè)排隊(duì)系統(tǒng)，1號(hào)車(chē)位相當(dāng)于正在接受服務(wù)的位置，2、3、4、5號(hào)車(chē)位相當(dāng)于隊(duì)列，這樣就構(gòu)建了一個(gè)排隊(duì)模型。在該排隊(duì)系統(tǒng)

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

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

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

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

32、（5） 機(jī)床每次停機(jī)的平均時(shí)間和等待處理的平均時(shí)間（小時(shí)）（分鐘）（小時(shí)）（分鐘）表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比較上述二例，可以看出當(dāng)三名工人聯(lián)合看管20臺(tái)機(jī)床時(shí)，雖然每一名工人平均看管的機(jī)床數(shù)增加了，但機(jī)床的利用率反而卻提高了，這是三名工人相互協(xié)作的結(jié)果。例10-8 某自餐廳有三個(gè)服務(wù)窗口，假設(shè)顧客的到達(dá)服從泊松分布，平均到達(dá)率人/分鐘，服務(wù)時(shí)間服從負(fù)指數(shù)分布，平均服務(wù)率人/分鐘。現(xiàn)假設(shè)顧客到達(dá)后排

34、成一個(gè)統(tǒng)一的隊(duì)列，從前依次向空閑的窗口購(gòu)餐，試分析該排隊(duì)系統(tǒng)的各項(xiàng)指標(biāo)。解：該例屬于顧客總體無(wú)限、系統(tǒng)容量無(wú)限的并聯(lián)服務(wù)系統(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)的運(yùn)行指標(biāo)：， 此例，；因此：（1） 餐廳的空閑率（2） 隊(duì)列中的平均顧客數(shù)（人）（3） 系統(tǒng)中的平均顧客數(shù)（人）（4） 顧客在隊(duì)列中的平均等待時(shí)間（分鐘）（5） 顧客在系統(tǒng)中的平均逗留時(shí)間（不包括就餐的時(shí)間）（分鐘）（6） 顧客到達(dá)需要等待的概率例10

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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