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

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

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

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

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

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

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

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

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

9、（3）服務(wù)的平穩(wěn)性服務(wù)的平穩(wěn)性是指服務(wù)時間分布及其特征參數(shù)不隨時間的變化而變化。服務(wù)的平穩(wěn)性排除了工作時間長短（疲勞程度）以及對列長短（服務(wù)員有意加快各種速度）對服務(wù)時間分布的影響。（4）服務(wù)規(guī)則按對等待顧客的服務(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ì)系統(tǒng)是最符合常理的，但當(dāng)顧客是一些待加工的工件時，就不存在明顯的誘因去遵

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

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

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

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

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

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

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

17、即平均到達(dá)率。我們可以通過令求的數(shù)學(xué)期望來加以證明：既然代表單位時間里到達(dá)顧客的平均數(shù)，那么自然代表平均的顧客到達(dá)時間間隔。2.2 負(fù)指數(shù)分布的服務(wù)時間負(fù)指數(shù)分布具有如下的概率密度函數(shù)和分布函數(shù)：，假設(shè)服務(wù)臺對顧客的服務(wù)時間服從負(fù)指數(shù)分布，即；則對于每一顧客的平均服務(wù)時間為，而自然代表服務(wù)率。這一點(diǎn)可以通過如下式子加以證明：2.3 生死過程一個顧客的到達(dá)將使系統(tǒng)狀態(tài)從到，這一過程成為生；一個顧客的離開將使系統(tǒng)狀態(tài)從到，這一過程成為死。系統(tǒng)狀態(tài)的轉(zhuǎn)移可以用狀態(tài)轉(zhuǎn)移圖（圖10-2）來加以描述，圖中結(jié)點(diǎn)代表狀態(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é)點(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)移圖的各個狀態(tài)，每一狀態(tài)都可給出一個以pi為變量的線性方程。這些線性方程組成的線性方程組無條件地決定了pi的分布。¼¼¼¼流的平衡方程具有一種特別易于手工求解的形式，第一

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

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

21、服務(wù)時間的積，即在一個平均服務(wù)時間里到達(dá)的平均顧客數(shù)量。的所有這些含義，均給出了要求的邏輯解釋；簡言之，如果顧客的平均到達(dá)率大于平均服務(wù)率，那么系統(tǒng)的隊(duì)長將無限增加，從而造成系統(tǒng)永遠(yuǎn)也達(dá)不到穩(wěn)定狀態(tài)。2.4 基本模型由于系統(tǒng)中顧客的數(shù)量越多，顧客在系統(tǒng)中逗留的時間也就會越長，所以可以希望在W和L之間建立起某種關(guān)系。李特爾（Little）公式給出了L、W和三者之間的關(guān)系，即系統(tǒng)中平均顧客數(shù)等于顧客平均到達(dá)率與平均逗留時間的積。根據(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ì)系統(tǒng)，應(yīng)根據(jù)系統(tǒng)的具體情況對某些模型進(jìn)行適當(dāng)?shù)恼{(diào)整。，即代表了平均被占用的服務(wù)臺數(shù)或服務(wù)臺利用率。從式（10-8）和式（10-10）可以顯示出一個令人關(guān)心的問題，為了限制平均隊(duì)長為一個適度小的數(shù)值，那么就不得不犧牲一定的服務(wù)臺利用率。例如，要保持，那么服務(wù)臺利用率就一定不會超過90%。也就是說為了確保系統(tǒng)中的顧客數(shù)不超過9人，必須容忍服務(wù)臺有10%的空閑時間。§3排隊(duì)模型的應(yīng)用例10-1 某醫(yī)院的一個診室根據(jù)病人來診和診治的時間記錄，任意抽查100個工作小時，每小時來就診的病人數(shù)n的出現(xiàn)次數(shù)，以及任意抽查100個完成診治的病人病歷，所用時間v

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

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

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

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

27、（分鐘）（5）顧客的損失率例10-5 某醫(yī)院門前有一個出租車?？空荆驁龅氐南拗浦挥?個停車位，在沒有停車位時新來的出租車會自動離開。當(dāng)停靠站有車時，從醫(yī)院出來的病人就租車；當(dāng)停靠站無車時，病人就向出租公司要車。設(shè)出租車以平均每小時8輛（）的泊松分布到達(dá)?？空?，從醫(yī)院出來病人的間隔時間為負(fù)指數(shù)分布，平均間隔時間為6分鐘。試求（1）出租車來到醫(yī)院門前，停靠站有空位的概率；（2）進(jìn)入?？空镜某鲎廛嚨钠骄却龝r間；（3）從醫(yī)院出來的病人直接租到車的概率。解：將停靠站與到達(dá)的出租車作為一個排隊(duì)系統(tǒng)，1號車位相當(dāng)于正在接受服務(wù)的位置，2、3、4、5號車位相當(dāng)于隊(duì)列，這樣就構(gòu)建了一個排隊(duì)模型。在該排隊(duì)系統(tǒng)

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

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

30、是平均逗留時間的倒數(shù)。需要注意的是，此時的不能象以往一樣通過觀測顧客到達(dá)系統(tǒng)的時間間隔來推算，因?yàn)榇藭r的時間間隔與系統(tǒng)中的顧客數(shù)之間存在相關(guān)關(guān)系，這樣得到的到達(dá)率僅僅是整個系統(tǒng)的平均到達(dá)率而不是每一個顧客的平均到達(dá)率。34021圖10-556如果只有一個顧客在顧客源中而其他顧客均在系統(tǒng)中，很顯然此時的顧客到達(dá)率就是；如果顧客源中有兩個顧客，那么此時的顧客到達(dá)率將是2，這樣依次類推可以得到圖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ī)的平均時間和等待處理的平均時間（小時）（分鐘）（小時）（分鐘）（4） 機(jī)床停機(jī)時間占總時間的比率例10-7 如果將上例改為三名工人聯(lián)合負(fù)責(zé)看管20臺自動機(jī)床，其他各項(xiàng)數(shù)據(jù)不變，試分析系統(tǒng)的各項(xiàng)指標(biāo)。解：該例屬于顧客總體有限并聯(lián)服務(wù)臺的排隊(duì)系統(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中，由于當(dāng)時，故忽略不計。（1） 工人的平均空閑時間（2） 工人的忙期（3） 系統(tǒng)內(nèi)的平均機(jī)床數(shù)和隊(duì)列中等待的平均機(jī)床數(shù)（4） 機(jī)床停機(jī)時間占總時間的比率

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

34、成一個統(tǒng)一的隊(duì)列，從前依次向空閑的窗口購餐，試分析該排隊(duì)系統(tǒng)的各項(xiàng)指標(biāo)。解：該例屬于顧客總體無限、系統(tǒng)容量無限的并聯(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ì)列中的平均等待時間（分鐘）（5） 顧客在系統(tǒng)中的平均逗留時間（不包括就餐的時間）（分鐘）（6） 顧客到達(dá)需要等待的概率例10

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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