運籌學(xué)排隊論新

運籌學(xué)排隊論新第一頁，共一百二十八頁，編輯于2023年，星期二第十二章排隊論到達(dá)間隔的分布和服務(wù)時間的分布本章內(nèi)容基本概念單服務(wù)臺負(fù)指數(shù)分布排隊系統(tǒng)的分析多服務(wù)臺負(fù)指數(shù)分布排隊系統(tǒng)的分析一般服務(wù)時間M/G/1模型第二頁，共一百二十八頁，編輯于2023年，星期二

排隊論(QueuingTheory)，又稱隨機(jī)服務(wù)系統(tǒng)理論(RandomServiceSystemTheory)。1909年由丹麥工程師愛爾朗(A.K．Erlang)在研究電話系統(tǒng)時創(chuàng)立的。具體地說，它是在研究各種排隊系統(tǒng)概率規(guī)律性的基礎(chǔ)上，解決相應(yīng)排隊系統(tǒng)的最優(yōu)設(shè)計和最優(yōu)控制問題。特別是自二十世紀(jì)60年代以來，由于計算機(jī)的飛速發(fā)展，使排隊論的應(yīng)用有了更廣闊的前景。第三頁，共一百二十八頁，編輯于2023年，星期二WheretheTimeGoes?美國人一生中平均要花費--6年飲食5年排隊等待4年做家務(wù)2年回電話不成功1年尋找放置不當(dāng)?shù)奈锲?個月打開郵寄廣告6個月停在紅燈前第四頁，共一百二十八頁，編輯于2023年，星期二商業(yè)服務(wù)系統(tǒng)系統(tǒng)類型 顧客 服務(wù)臺理發(fā)店 人 理發(fā)師銀行出納服務(wù) 人 出納ATM機(jī)服務(wù) 人 ATM機(jī)商店收銀臺 人 收銀員管道服務(wù) 阻塞的管道 管道工電影院售票窗口 人 售票員機(jī)場檢票處 人 航空公司代理人經(jīng)紀(jì)人服務(wù) 人 股票經(jīng)紀(jì)人第五頁，共一百二十八頁，編輯于2023年，星期二運輸服務(wù)系統(tǒng)系統(tǒng)類型 顧客 服務(wù)臺公路收費站 汽車 收費員卡車裝貨地 卡車 裝貨工人港口卸貨區(qū) 輪船 卸貨工人等待起飛的飛機(jī) 飛機(jī) 跑道航班服務(wù) 人 飛機(jī)出租車服務(wù) 人 出租車電梯服務(wù) 人 電梯消防部門 火災(zāi) 消防車停車場 汽車 停車空間急救車服務(wù) 人 急救車第六頁，共一百二十八頁，編輯于2023年，星期二

面對擁擠現(xiàn)象，如何做到既保證一定的服務(wù)質(zhì)量指標(biāo)，又使服務(wù)設(shè)施費用經(jīng)濟(jì)合理，恰當(dāng)?shù)亟鉀Q顧客排隊時間與服務(wù)設(shè)施費用大小這對矛盾，這就是排隊論所要研究解決的問題之一。第七頁，共一百二十八頁，編輯于2023年，星期二第一節(jié)基本概念第八頁，共一百二十八頁，編輯于2023年，星期二（一）排隊系統(tǒng)的特征及組成

排隊系統(tǒng)的共同特征:

①

有要求得到某種服務(wù)的人或物。排隊論里把要求服務(wù)的對象統(tǒng)稱為“顧客”②有提供服務(wù)的人或機(jī)構(gòu)。把提供服務(wù)的人或機(jī)構(gòu)稱為“服務(wù)臺”或“服務(wù)員”③顧客的到達(dá)、服務(wù)的時間至少有一個是隨機(jī)的，服從某種分布。第九頁，共一百二十八頁，編輯于2023年，星期二一般的排隊系統(tǒng)，都可由圖12-1加以描述。顧客源排隊結(jié)構(gòu)服務(wù)機(jī)構(gòu)排隊規(guī)則顧客到來服務(wù)規(guī)則離去圖12-1排隊系統(tǒng)第十頁，共一百二十八頁，編輯于2023年，星期二

排隊系統(tǒng)都有輸入過程、排隊規(guī)則和服務(wù)臺等3個組成部分：1、輸入過程這是指要求服務(wù)的顧客是按怎樣的規(guī)律到達(dá)排隊系統(tǒng)的過程，有時也把它稱為顧客流．一般可以從3個方面來描述輸入過程。排隊系統(tǒng)的組成第十一頁，共一百二十八頁，編輯于2023年，星期二

(1)

顧客總體數(shù)組成(又稱顧客源)是有限的，也可以是無限的。例如，到售票處購票的顧客總數(shù)可以認(rèn)為是無限的，而某個工廠因故障待修的機(jī)床則是有限的。(2)顧客到達(dá)方式。描述顧客是怎樣來到系統(tǒng)的，他們是單個到達(dá)，還是成批到達(dá)。病人到醫(yī)院看病是顧客單個到達(dá)的例子。在庫存問題中如將生產(chǎn)器材進(jìn)貨或產(chǎn)品入庫看作是顧客，那么這種顧客則是成批到達(dá)的。第十二頁，共一百二十八頁，編輯于2023年，星期二(3)顧客流的概率分布，或稱顧客相繼到達(dá)時間間隔的分布。這是求解排隊系統(tǒng)有關(guān)運行指標(biāo)問題時，首先需要確定的指標(biāo)。

顧客流的概率分布一般有定長分布、二項分布、泊松流(最簡單流)、愛爾朗分布等若干種。第十三頁，共一百二十八頁，編輯于2023年，星期二2、排隊規(guī)則這是指服務(wù)臺從隊列中選取顧客進(jìn)行服務(wù)的順序。損失制混合制隊長有限等待時間有限逗留時間有限排隊規(guī)則等待制先到先服務(wù)后到先服務(wù)隨機(jī)服務(wù)優(yōu)先權(quán)服務(wù)第十四頁，共一百二十八頁，編輯于2023年，星期二3．服務(wù)臺情況。服務(wù)臺可以從3方面來描述：

(1)服務(wù)臺數(shù)量及構(gòu)成形式圖12-2單隊列-單服務(wù)臺排隊系統(tǒng)第十五頁，共一百二十八頁，編輯于2023年，星期二圖12-3單隊列——S個服務(wù)臺并聯(lián)的排隊系統(tǒng)圖12-4S個隊列——S個服務(wù)臺的并聯(lián)排隊系統(tǒng)第十六頁，共一百二十八頁，編輯于2023年，星期二圖12-5單隊——多個服務(wù)臺的串聯(lián)排隊系統(tǒng)圖12-6多隊——多服務(wù)臺混聯(lián)、網(wǎng)絡(luò)系統(tǒng)第十七頁，共一百二十八頁，編輯于2023年，星期二 (2)服務(wù)方式。這是指在某一時刻接受服務(wù)的顧客數(shù)，它有單個服務(wù)和成批服務(wù)兩種。 (3)服務(wù)時間的分布。在多數(shù)情況下，對每一個顧客的服務(wù)時間是一隨機(jī)變量，其概率分布有定長分布、負(fù)指數(shù)分布、K級愛爾朗分布、一般分布(所有顧客的服務(wù)時間都是獨立同分布的)等等。第十八頁，共一百二十八頁，編輯于2023年，星期二

為了區(qū)別各種排隊系統(tǒng)，根據(jù)輸入過程、排隊規(guī)則和服務(wù)機(jī)制的不同，對排隊模型進(jìn)行分類。D．G．Kendall在1953年提出了模型分類方法，1971年在排隊論符號標(biāo)準(zhǔn)化會議上，將Kendall符號擴(kuò)充為如下固定格式：

X/Y/Z/A/B/C各符號的意義為：（二）排隊模型的分類第十九頁，共一百二十八頁，編輯于2023年，星期二X—表示顧客相繼到達(dá)間隔時間分布，常用下列符號：X/Y/Z/A/B/CM—表示到達(dá)過程為泊松過程或負(fù)指數(shù)分布；D—表示定長輸入；Ek—表示k階愛爾朗分布；GI——表示一般相互獨立的時間間隔分布；G——表示一般服務(wù)時間的分布。第二十頁，共一百二十八頁，編輯于2023年，星期二Y—表示服務(wù)時間分布，常用下列符號：X/Y/Z/A/B/CM—表示服務(wù)過程為泊松過程或負(fù)指數(shù)分布；D—表示定長分布；Ek—表示k階愛爾朗分布；G—表示一般相互獨立的隨機(jī)分布。第二十一頁，共一百二十八頁，編輯于2023年，星期二Z—表示服務(wù)臺(員)個數(shù)： “1”則表示單個服務(wù)臺，“s”(s＞1)表示多個服務(wù)臺。X/Y/Z/A/B/CA—表示系統(tǒng)中顧客容量限額，或稱等待空間容量： ∞時為等待制系統(tǒng)，此時∞一般省略不寫；若為有限整數(shù)時，為混合制系統(tǒng)。第二十二頁，共一百二十八頁，編輯于2023年，星期二B—表示顧客源限額。

分有限與無限兩種，∞表示顧客源無限，此時一般∞也可省略不寫。X/Y/Z/A/B/CC—表示服務(wù)規(guī)則，常用下列符號：

FCFS：表示先到先服務(wù)；

LCFS：表示后到先服務(wù)；

PR：表示優(yōu)先權(quán)服務(wù)。第二十三頁，共一百二十八頁，編輯于2023年，星期二例如：某排隊問題為

M／M／S／∞／∞／FCFS

則表示顧客到達(dá)間隔時間為負(fù)指數(shù)分布(泊松流)； 服務(wù)時間為負(fù)指數(shù)分布； 有s(s＞1)個服務(wù)臺； 系統(tǒng)等待空間容量無限(等待制)； 顧客源無限，采用先到先服務(wù)規(guī)則。 可簡記為：

M/M/s

第二十四頁，共一百二十八頁，編輯于2023年，星期二

某些情況下，排隊問題僅用上述表達(dá)形式中的前3個、4個、5個符號。如不特別說明均理解為系統(tǒng)等待空間容量無限；顧客源無限，先到先服務(wù)，單個服務(wù)的等待制系統(tǒng)。第二十五頁，共一百二十八頁，編輯于2023年，星期二（三）排隊系統(tǒng)的主要數(shù)量指標(biāo)1.隊長和排隊長

隊長是指系統(tǒng)中的顧客數(shù)(排隊等待的顧客數(shù)與正在接受服務(wù)的顧客數(shù)之和)。

排隊長是指系統(tǒng)中正在排隊等待服務(wù)的顧客數(shù)。第二十六頁，共一百二十八頁，編輯于2023年，星期二2．等待時間和逗留時間

從顧客到達(dá)時刻起到他開始接受服務(wù)止這段時間稱為等待時間，是隨機(jī)變量。 從顧客到達(dá)時刻起到他接受服務(wù)完成止這段時間稱為逗留時間，也是隨機(jī)變量。第二十七頁，共一百二十八頁，編輯于2023年，星期二3．忙期和閑期

忙期是指從顧客到達(dá)空閑著的服務(wù)機(jī)構(gòu)起，到服務(wù)機(jī)構(gòu)再次成為空閑止的這段時間，即服務(wù)機(jī)構(gòu)連續(xù)忙的時間。這是個隨機(jī)變量，它關(guān)系到服務(wù)員的服務(wù)強(qiáng)度。

與忙期相對的是閑期，即服務(wù)機(jī)構(gòu)連續(xù)保持空閑的時間。在排隊系統(tǒng)中，忙期和閑期總是交替出現(xiàn)的。第二十八頁，共一百二十八頁，編輯于2023年，星期二

除了上述幾個基本數(shù)量指標(biāo)外，還會用到其他一些重要的指標(biāo)： 損失制或系統(tǒng)容量有限的情況下，由于顧客被拒絕，而使服務(wù)系統(tǒng)受到損失的顧客損失率及服務(wù)強(qiáng)度等，也都是十分重要的數(shù)量指標(biāo)。第二十九頁，共一百二十八頁，編輯于2023年，星期二

4.一些數(shù)量指標(biāo)的常用記號

(1)主要數(shù)量指標(biāo)

N(t)：時刻t系統(tǒng)中的顧客數(shù)(又稱為系統(tǒng)的狀態(tài))，即隊長；

Nq(t)：時刻t系統(tǒng)中排隊的顧客數(shù)，即排隊長；

T(t)：時刻t到達(dá)系統(tǒng)的顧客在系統(tǒng)中的逗留時間；

Tq(t)：時刻t到達(dá)系統(tǒng)的顧客在系統(tǒng)中的等待時間。第三十頁，共一百二十八頁，編輯于2023年，星期二

上面數(shù)量指標(biāo)一般都是和系統(tǒng)運行的時間有關(guān)的隨機(jī)變量，求它們的瞬時分布一般很困難。注意到相當(dāng)一部分排隊系統(tǒng)在運行了一定時間后，都會趨于一個平衡狀態(tài)(或稱平穩(wěn)狀態(tài))。

在平衡狀態(tài)下，這些量與系統(tǒng)所處的時刻無關(guān)，而且系統(tǒng)的初始狀態(tài)的影響也會消失。因此，我們在本章中將主要討論與系統(tǒng)所處時刻無關(guān)的性質(zhì)，即統(tǒng)計平衡性質(zhì)。第三十一頁，共一百二十八頁，編輯于2023年，星期二L或Ls—平均隊長 穩(wěn)態(tài)系統(tǒng)任一時刻的顧客數(shù)的期望值；Lq—平均等待隊長或隊列長 穩(wěn)態(tài)系統(tǒng)任一時刻等待服務(wù)的顧客數(shù)期望值；W或Ws—

平均逗留時間進(jìn)入穩(wěn)態(tài)系統(tǒng)的顧客逗留時間期望值；Wq—平均等待時間 進(jìn)入穩(wěn)態(tài)系統(tǒng)的顧客等待時間期望值。第三十二頁，共一百二十八頁，編輯于2023年，星期二Pn—系統(tǒng)的狀態(tài)Pn=P{N=n}：穩(wěn)態(tài)系統(tǒng)任一時刻狀態(tài)為n的概率。當(dāng)n=0時，Pn即P0為穩(wěn)態(tài)系統(tǒng)所有服務(wù)臺全部空閑的概率。第三十三頁，共一百二十八頁，編輯于2023年，星期二(2)其他常用數(shù)量指標(biāo)s——系統(tǒng)中并聯(lián)服務(wù)臺的數(shù)目——平均到達(dá)率（單位時間內(nèi)到達(dá)的平均顧客數(shù)）1/——平均到達(dá)間隔——平均服務(wù)率（單位時間內(nèi)可以服務(wù)完的平均顧客數(shù)）1/——平均服務(wù)時間第三十四頁，共一百二十八頁，編輯于2023年，星期二

對于損失制和混合制的排隊系統(tǒng)，顧客在到達(dá)服務(wù)系統(tǒng)時，若系統(tǒng)容量已滿，則自行消失。這就是說，到達(dá)的顧客不一定全部進(jìn)入系統(tǒng)，為此引入：e

——有效平均到達(dá)率，即每單位時間實際進(jìn)入系統(tǒng)的平均顧客數(shù)（期望值），不同于。

對于等待制的排隊系統(tǒng)，有：

e

＝第三十五頁，共一百二十八頁，編輯于2023年，星期二第二節(jié)到達(dá)間隔的分布和服務(wù)時間的分布第三十六頁，共一百二十八頁，編輯于2023年，星期二

一、Poisson流（Poisson過程）定義滿足以下三個條件的輸入流稱為Poisson流1、無后效性：不相交的時間區(qū)間內(nèi)到達(dá)的顧客數(shù)互相獨立。2、平穩(wěn)性：在時間區(qū)間[t,t+t)內(nèi)到達(dá)1個顧客的概率只與t有關(guān)。即表示單位時間內(nèi)有一個顧客到達(dá)的概率。3、普通性：設(shè)在[t,t+t）內(nèi)到達(dá)多于一個顧客的概率極小，即第三十七頁，共一百二十八頁，編輯于2023年，星期二Poisson流與Poisson分布定理1

對于一個參數(shù)為的Poisson流，在[0，t]內(nèi)到達(dá)n個顧客的概率為

即服從以為參數(shù)的Poisson分布。

定理1說明如果顧客的到達(dá)為Poisson流的話，則到達(dá)顧客數(shù)的分布恰好為Poisson分布。第三十八頁，共一百二十八頁，編輯于2023年，星期二

二、負(fù)指數(shù)分布

在實際的排隊系統(tǒng)中服務(wù)時間的概率分布可以是各種形式，但在排隊論中，最容易進(jìn)行數(shù)學(xué)處理、最常用的一種重要分布是負(fù)指數(shù)分布。

設(shè)隨機(jī)變量T服從以為參數(shù)的負(fù)指數(shù)分布，它的分布函數(shù)為：第三十九頁，共一百二十八頁，編輯于2023年，星期二負(fù)指數(shù)分布的性質(zhì)：

性質(zhì)1

由條件概率公式容易證明

性質(zhì)2

當(dāng)單位時間內(nèi)的顧客到達(dá)數(shù)服從以為平均數(shù)的泊松分布時，則顧客相繼到達(dá)的間隔時間T服從負(fù)指數(shù)分布。

這性質(zhì)稱為無記憶性。若T表示排隊系統(tǒng)中顧客到達(dá)的時間間隔，那么這個性質(zhì)說明一個顧客到來所需要的時間與過去一個顧客到來所需要的時間s無關(guān)，所以說在這種情形下的顧客到達(dá)是純隨機(jī)的。

第四十頁，共一百二十八頁，編輯于2023年，星期二由性質(zhì)2可知：

相繼到達(dá)的間隔時間是獨立且為相同參數(shù)的負(fù)指數(shù)分布，與輸入過程為泊松流（參數(shù)為）是等價的。

根據(jù)負(fù)指數(shù)分布與泊松流的關(guān)系可以推導(dǎo)出，當(dāng)服務(wù)機(jī)構(gòu)對顧客的服務(wù)時間服從參數(shù)為的負(fù)指數(shù)分布，如果服務(wù)機(jī)構(gòu)處于忙期，則該服務(wù)機(jī)構(gòu)的輸出，即服務(wù)完畢離開服務(wù)機(jī)構(gòu)的顧客數(shù)將是服從泊松分布的泊松流。其中為每個顧客的平均服務(wù)時間，也是顧客相繼離開的間隔。

第四十一頁，共一百二十八頁，編輯于2023年，星期二三、k階愛爾朗分布定理

設(shè)v1，v2，…，vk是k個互相獨立的隨機(jī)變量，服從相同參數(shù)k的負(fù)指數(shù)分布，那么

S=v1+v2+…+vk服從k階Erlang分布，S的密度函數(shù)為第四十二頁，共一百二十八頁，編輯于2023年，星期二K=1時愛爾朗分布化歸為負(fù)指數(shù)分布，當(dāng)K→∞時，得到長度為1/的定長服務(wù)。m=1k=1k=2k=4k=8第四十三頁，共一百二十八頁，編輯于2023年，星期二第三節(jié)單服務(wù)臺負(fù)指數(shù)分布排隊系統(tǒng)的分析第四十四頁，共一百二十八頁，編輯于2023年，星期二標(biāo)準(zhǔn)排隊模型[M/M/1]:[//FCFS]顧客到達(dá)的時間間隔是負(fù)指數(shù)分布，即輸入流是參數(shù)為的Poisson流服從參數(shù)為μ的負(fù)指數(shù)分布一個服務(wù)臺排隊系統(tǒng)的容量無限顧客源的容量無限實行先到先服務(wù)的一個服務(wù)系統(tǒng)第四十五頁，共一百二十八頁，編輯于2023年，星期二一、系統(tǒng)穩(wěn)態(tài)概率pn的計算

假設(shè)在t+t時刻系統(tǒng)中顧客數(shù)為n的概率Pn(t+t)Pn(t)Pn-1(t)Pn+1(t)Pn(t)Snt+t時刻SnSnSn+1Sn-1t時刻無到達(dá)，無離開無到達(dá)，離開一個到達(dá)一個，無離開到達(dá)一個，離開一個第四十六頁，共一百二十八頁，編輯于2023年，星期二由于這四種方式互不相容，故由概率的加法定理得：該差分方程組為瞬態(tài)解，需求穩(wěn)態(tài)解。第四十七頁，共一百二十八頁，編輯于2023年，星期二[M/M/1]:[//FCFS]穩(wěn)態(tài)時狀態(tài)轉(zhuǎn)移圖λ012n-1nn+1穩(wěn)態(tài)情況下，系統(tǒng)狀態(tài)已不隨時間發(fā)生變化：第四十八頁，共一百二十八頁，編輯于2023年，星期二穩(wěn)態(tài)情況下，系統(tǒng)狀態(tài)已不隨時間發(fā)生變化：第四十九頁，共一百二十八頁，編輯于2023年，星期二得到

令稱為服務(wù)強(qiáng)度，則得第五十頁，共一百二十八頁，編輯于2023年，星期二系統(tǒng)的過渡狀態(tài)與穩(wěn)定狀態(tài)過渡穩(wěn)定第五十一頁，共一百二十八頁，編輯于2023年，星期二二、系統(tǒng)的數(shù)量指標(biāo)1、服務(wù)臺空閑的概率和忙的概率：空閑的概率：P0=1-忙的概率：1-P0=2、系統(tǒng)中平均顧客數(shù)（隊長期望值Ls）：第五十二頁，共一百二十八頁，編輯于2023年，星期二3、系統(tǒng)中等待的平均顧客數(shù)（隊長期望值Lq）：4、系統(tǒng)中顧客逗留時間的期望值：第五十三頁，共一百二十八頁，編輯于2023年，星期二5、隊列中顧客逗留時間的期望值：現(xiàn)將以上公式歸納如下：它們相互關(guān)系如下：第五十四頁，共一百二十八頁，編輯于2023年，星期二Little公式

下列公式對任何服務(wù)系統(tǒng)均成立第五十五頁，共一百二十八頁，編輯于2023年，星期二例1

高速公路入口收費處設(shè)有一個收費通道，汽車到達(dá)服從Poisson分布，平均到達(dá)速率為100輛／小時，收費時間服從負(fù)指數(shù)分布，平均收費時間為15秒／輛。求1、收費處空閑的概率；2、收費處忙的概率；3、系統(tǒng)中分別有1，2，3輛車的概率。第五十六頁，共一百二十八頁，編輯于2023年，星期二解：根據(jù)題意,=100輛/小時,1/=15（秒/輛）=1/240（小時/輛）,即＝240（輛/小時）。 因此，=/=100/240=5/12。 系統(tǒng)空閑的概率為：

P0=1-=1-(5/12)=7/12=0.583

系統(tǒng)忙的概率為：

1-P0=1-(1-)==5/12=0.417第五十七頁，共一百二十八頁，編輯于2023年，星期二系統(tǒng)中有1輛車的概率為：

P1=(1-)=0.417×0.583=0.243系統(tǒng)中有2輛車的概率為：

P2=2(1-)=0.4172×0.583=0.101系統(tǒng)中有3輛車的概率為：

P3=3(1-)=0.4173×0.583=0.0421第五十八頁，共一百二十八頁，編輯于2023年，星期二例2

高速公路入口收費處設(shè)有一個收費通道，汽車到達(dá)服從Poisson分布，平均到達(dá)速率為200輛／小時，收費時間服從負(fù)指數(shù)分布，平均收費時間為15秒／輛。求Ls、Lq、Ws和Wq。第五十九頁，共一百二十八頁，編輯于2023年，星期二解：根據(jù)題意，=200輛/小時，=240輛/小時，=/=5/6。第六十頁，共一百二十八頁，編輯于2023年，星期二有限隊列模型[M/M/1]:[N//FCFS]

如果系統(tǒng)的最大容量為N時，排隊等待的顧客最多為N-1，在某時刻一顧客到達(dá)時，如系統(tǒng)中已有N個顧客，那么這個顧客就被拒絕進(jìn)入系統(tǒng)。第六十一頁，共一百二十八頁，編輯于2023年，星期二系統(tǒng)的狀態(tài)概率平衡方程對于狀態(tài)0： P1=P0

… …對于狀態(tài)k： Pk-1+Pk+1=(+)Pk0<k<N… …對于狀態(tài)N： PN-1=PNλ012n-1n第六十二頁，共一百二十八頁，編輯于2023年，星期二系統(tǒng)的狀態(tài)概率由得到第六十三頁，共一百二十八頁，編輯于2023年，星期二系統(tǒng)的運行指標(biāo)第六十四頁，共一百二十八頁，編輯于2023年，星期二有效到達(dá)率第六十五頁，共一百二十八頁，編輯于2023年，星期二Little公式第六十六頁，共一百二十八頁，編輯于2023年，星期二例3

一個單人理發(fā)店，除理發(fā)椅外，還有4把椅子可供顧客等候。顧客到達(dá)發(fā)現(xiàn)沒有座位空閑，就不再等待而離去。顧客到達(dá)的平均速率為4人/小時，理發(fā)的平均時間為10分鐘/人。顧客到達(dá)服從Poisson流，理發(fā)時間服從負(fù)指數(shù)分布。求：1、顧客到達(dá)不用等待就可理發(fā)的概率；2、理發(fā)店里的平均顧客數(shù)以及等待理發(fā)的平均顧客數(shù)；3、顧客來店理發(fā)一次平均花費的時間及平均等待的時間；4、顧客到達(dá)后因客滿而離去的概率；5、增加一張椅子可以減少的顧客損失率。第六十七頁，共一百二十八頁，編輯于2023年，星期二解：這是一個[M/M/1]:[N//FCFS]系統(tǒng)，其中N=4+1=5，=4人/小時，=6人/小時，=2/3。第六十八頁，共一百二十八頁，編輯于2023年，星期二因客滿而離去的概率為0.0048第六十九頁，共一百二十八頁，編輯于2023年，星期二當(dāng)N=6時P5-P6=0.0480-0.0311=0.0169=1.69%即增加一張椅子可以減少顧客損失率1.69%第七十頁，共一百二十八頁，編輯于2023年，星期二[M/M/1]:[∞/m/FCFS]模型

設(shè)顧客總數(shù)為m。當(dāng)顧客需要服務(wù)時，就進(jìn)入隊列等待；服務(wù)完畢后，重新回到顧客源中。如此循環(huán)往復(fù)。服務(wù)臺...顧客源需要服務(wù)服務(wù)完畢隊列第七十一頁，共一百二十八頁，編輯于2023年，星期二顧客源中剩余的顧客數(shù)

乘以每個顧客到達(dá)的速率0m-112m-2mλ(m-1)λ2λλμμμμmμμ(m-2)λ3λ

假定每一臺機(jī)器在單位時間內(nèi)發(fā)生故障的平均次數(shù)是相同的，設(shè)為λ。當(dāng)正在等待及正在接受維修的機(jī)器臺數(shù)為Ls時，則在單位時間內(nèi)發(fā)生故障的平均機(jī)器數(shù)為：

λe=λ(m-Ls)第七十二頁，共一百二十八頁，編輯于2023年，星期二狀態(tài)轉(zhuǎn)移方程λ0P0=μP1 ……[λn+μ]Pn=μPn+1+λn-1Pn-1

(n=1，2，…，m-1)

……μPm=λm-1Pm-1

(n=1，2，…，m) 第七十三頁，共一百二十八頁，編輯于2023年，星期二運行指標(biāo)第七十四頁，共一百二十八頁，編輯于2023年，星期二(1)修理工空閑的概率；(2)五臺機(jī)器都出故障的概率；(3)出故障的平均臺數(shù)；(4)平均停工時間；(5)平均等待修理時間；(6)評價系統(tǒng)運行情況。例4

某車間有5臺機(jī)器，每臺機(jī)器的連續(xù)運轉(zhuǎn)時間服從負(fù)指數(shù)分布，平均連續(xù)運行時間15分鐘。有一個修理工，每次修理時間服從負(fù)指數(shù)分布，平均每次12分鐘。求:第七十五頁，共一百二十八頁，編輯于2023年，星期二解根據(jù)題意，m=5，λ=1/15，μ=1/12，ρ=λ/μ=0.8

第七十六頁，共一百二十八頁，編輯于2023年，星期二第七十七頁，共一百二十八頁，編輯于2023年，星期二第4節(jié)多服務(wù)臺負(fù)指數(shù)分布排隊系統(tǒng)的分析第七十八頁，共一百二十八頁，編輯于2023年，星期二多服務(wù)臺模型[M/M/c]標(biāo)準(zhǔn)的[M/M/c]:[∞/∞/FCFS]模型系統(tǒng)容量有限的[M/M/c]:[N/∞/FCFS]模型有限顧客源的[M/M/c]:[∞/m/FCFS]模型第七十九頁，共一百二十八頁，編輯于2023年，星期二[M/M/c]:[∞/∞/FCFS]模型服務(wù)臺服務(wù)臺服務(wù)臺顧客到達(dá)顧客離去顧客離去顧客離去隊列

顧客到達(dá)后，進(jìn)入隊列尾端；當(dāng)某一個服務(wù)臺空閑時，隊列中的第一個顧客即到該服務(wù)臺接收服務(wù)；服務(wù)完畢后隨即離去。各服務(wù)臺互相獨立且服務(wù)速率相同，即μ1=μ2=…=μc

第八十頁，共一百二十八頁，編輯于2023年，星期二

系統(tǒng)的服務(wù)速率與系統(tǒng)中的顧客數(shù)有關(guān)。當(dāng)系統(tǒng)中的顧客數(shù)k不大于服務(wù)臺個數(shù)，即1≤k≤c時，系統(tǒng)中的顧客全部在服務(wù)臺中，這時系統(tǒng)的服務(wù)速率為kμ；當(dāng)系統(tǒng)中的顧客數(shù)k＞c時，服務(wù)臺中正在接受服務(wù)的顧客數(shù)仍為c個，其余顧客在隊列中等待服務(wù)，這時系統(tǒng)的服務(wù)速率為cμ。只有當(dāng)ρ＜1時系統(tǒng)才不會排成無限的隊列。服務(wù)強(qiáng)度服務(wù)機(jī)構(gòu)平均利用率第八十一頁，共一百二十八頁，編輯于2023年，星期二狀態(tài)轉(zhuǎn)移圖與狀態(tài)轉(zhuǎn)移方程對狀態(tài)0: λP0=μP1

對狀態(tài)1: λP0+2μP2=(λ+μ)P1 …………對狀態(tài)c： λPc-1+cμPc+1=(λ+cμ)Pc …………對狀態(tài)n λPn-1+cμPn+1=(λ+cμ)Pn ………01cn第八十二頁，共一百二十八頁，編輯于2023年，星期二狀態(tài)概率第八十三頁，共一百二十八頁，編輯于2023年，星期二運行指標(biāo)第八十四頁，共一百二十八頁，編輯于2023年，星期二例5

某售票處有三個窗口，顧客到達(dá)服從Poisson流，到達(dá)速率為0.9人／分，售票時間服從負(fù)指數(shù)分布，每個窗口的平均售票速率為0.4人／分。顧客到達(dá)后排成一隊，依次到空閑窗口購票。求：(1)所有窗口都空閑的概率；(2)平均隊長；(3)平均等待時間及逗留時間；(4)顧客到達(dá)后必須等待的概率。第八十五頁，共一百二十八頁，編輯于2023年，星期二解：λ/μ=2.25，ρ=λ/cμ=0.75(1)所有窗口都空閑的概率，即求P0的值(2)平均隊長，即求Ls的值，必須先求Lq

第八十六頁，共一百二十八頁，編輯于2023年，星期二(3)平均等待時間和平均逗留時間，即求Wq和Ws和的值(4)顧客到達(dá)后必須等待，即n≥3第八十七頁，共一百二十八頁，編輯于2023年，星期二服務(wù)臺服務(wù)臺服務(wù)臺顧客到達(dá)顧客離去顧客離去顧客離去

如果在上例中，購票者到達(dá)后在每個窗口各自排成一隊，即排成3隊，且進(jìn)入隊列后不離開，各列間也互不串換，這就形成3個隊列，而上例中的其它條件不變。假設(shè)每個隊列平均到達(dá)率相等且為：λ1＝λ2＝λ3＝0.9/3＝0.3（人/分鐘）

這樣，原來的M/M/3系統(tǒng)就變成了3個M/M/1型的子系統(tǒng)。第八十八頁，共一百二十八頁，編輯于2023年，星期二 M/M/c和c個M/M/1模型的比較指標(biāo)（1）M/M/3型（2）M/M/1型售票處空閑的概率0.07480.25（各子系統(tǒng)）購票者必須等待的概率P(N>3)=0.570.75排隊長1.7（人）2.25（人）（各子系統(tǒng)）平均隊長3.95（人）9（人）（整個系統(tǒng)）平均逗留時間4.39（分鐘）10（分鐘）平均等待時間1.89（分鐘）7.5（分鐘）第八十九頁，共一百二十八頁，編輯于2023年，星期二[M/M/c]:[N/∞/FCFS]模型離開服務(wù)臺服務(wù)臺服務(wù)臺顧客到達(dá)顧客離去顧客離去顧客離去隊列

設(shè)系統(tǒng)容量為N(N≥c)。設(shè)顧客到達(dá)的速率為λ，每個服務(wù)臺服務(wù)的速率為μ，ρ=λ/cμ。由于系統(tǒng)不會無限止地接納顧客，對ρ不必加以限制。第九十頁，共一百二十八頁，編輯于2023年，星期二狀態(tài)轉(zhuǎn)移圖與狀態(tài)轉(zhuǎn)移方程對狀態(tài)0: λP0=μP1

對狀態(tài)1: λP0+2μP2=(λ+μ)P1 …………對狀態(tài)c： λPc-1+cμPc+1=(λ+cμ)Pc …………對狀態(tài)N λPN-1=cμPN ………01cN第九十一頁，共一百二十八頁，編輯于2023年，星期二狀態(tài)概率第九十二頁，共一百二十八頁，編輯于2023年，星期二運行指標(biāo)第九十三頁，共一百二十八頁，編輯于2023年，星期二例6某旅館有8個單人房間，旅客到達(dá)服從Poisson流，平均速率為6人／天，旅客平均逗留時間為2天，求：(1)每天客房平均占用數(shù)；(2)旅館客滿的概率。第九十四頁，共一百二十八頁，編輯于2023年，星期二解：旅館8個房間全滿的概率為0.423平均占用客房數(shù)為6.9間。第九十五頁，共一百二十八頁，編輯于2023年，星期二[M/M/c]:[∞/m/FCFS]模型顧客到達(dá)修理速率μ發(fā)生故障等待修理的機(jī)器修理速率μ修理速率μ正在修理的機(jī)器到達(dá)速率(m-n)λ修理速率cμ運行的機(jī)器數(shù)m-n第九十六頁，共一百二十八頁，編輯于2023年，星期二狀態(tài)概率其中第九十七頁，共一百二十八頁，編輯于2023年，星期二運行指標(biāo)

有效到達(dá)速率λe為單位時間內(nèi)出現(xiàn)故障的機(jī)器數(shù)，有

λe=λ(m-Ls)第九十八頁，共一百二十八頁，編輯于2023年，星期二例7

車間有5臺機(jī)器，每臺機(jī)器的故障率為1次／小時，有2個修理工負(fù)責(zé)修理這5臺機(jī)器，工作效率相同，為4臺／小時。求：(1)等待修理的平均機(jī)器數(shù)；(2)正在修理的平均機(jī)器數(shù)；(3)每小時發(fā)生故障的平均機(jī)器數(shù)；(4)平均等待修理的時間；(5)平均停工時間。第九十九頁，共一百二十八頁，編輯于2023年，星期二解可以計算得到（算式略）：P1=0.394，P2=0.197，P3=0.074，P4=0.018，P5=0.002第一百頁，共一百二十八頁，編輯于2023年，星期二由此，計算系統(tǒng)的各項運行指標(biāo)如下：第一百零一頁，共一百二十八頁，編輯于2023年，星期二第5節(jié)一般服務(wù)時間M/G/1模型第一百零二頁，共一百二十八頁，編輯于2023年，星期二

服務(wù)時間一般分布時，需要知道服務(wù)時間的均值和方差。當(dāng)時，排隊系統(tǒng)可以達(dá)到平穩(wěn)狀態(tài)。P－K公式第一百零三頁，共一百二十八頁，編輯于2023年，星期二1負(fù)指數(shù)服務(wù)時間M/M/1模型只有負(fù)指數(shù)分布時排隊長的一半。2定長服務(wù)時間M/D/1模型第一百零四頁，共一百二十八頁，編輯于2023年，星期二3k階愛爾朗服務(wù)時間M/Ek/1模型

若顧客需接受k個串行的服務(wù)臺的服務(wù)后才離開，且每個服務(wù)臺服務(wù)時間服從負(fù)指數(shù)分布，平均服務(wù)時間相等。 則總服務(wù)時間服從k階愛爾朗分布。第一百零五頁，共一百二十八頁，編輯于2023年，星期二Erlang分布的均值和方差總服務(wù)時間服從愛爾朗分布：每個服務(wù)臺的平均服務(wù)時間是：第一百零六頁，共一百二十八頁，編輯于2023年，星期二M/Ek/1系統(tǒng)的運行指標(biāo)第一百零七頁，共一百二十八頁，編輯于2023年，星期二

例8

有一汽車沖洗臺，汽車按Poisson流到達(dá)，平均每小時到達(dá)18輛；沖洗時間T的平均值=0.05小時/輛，方差Var(T)=0.01(小時/輛)2，求該洗車臺的運行指標(biāo)，并對它進(jìn)行評價。

解：本例是M/G/1系統(tǒng)，且已知第一百零八頁，共一百二十八頁，編輯于2023年，星期二

可見顧客等待時間太長，隊列也太長。主要原因是服務(wù)時間的方差太大！第一百零九頁，共一百二十八頁，編輯于2023年，星期二例9

某單人裁縫店做西服，每套需經(jīng)過4個不同的工序，4個工序完成后才開始做另一套。每一工序的時間服從負(fù)指數(shù)分布，期望值為2小時。顧客到來服從泊松分布，平均訂貨率為5.5套/周（設(shè)一周6天，每天8小時）。問一顧客為等到做好一套西服期望時間有多長？解：λ=5.5套/周1/μ:平均每套所需時間1/4μ:平均每工序所需時間，為2小時μ＝1/8套/小時＝6套/周第一百一十頁，共一百二十八頁，編輯于2023年，星期二顧客為等到做好一套西服期望時間：第一百一十一頁，共一百二十八頁，編輯于2023年，星期二排隊論練習(xí)題第一百一十二頁，共一百二十八頁，編輯于2023年，星期二

練習(xí)1：某修理店只有一位修理工，來修理的顧客到達(dá)過程為Poisson流，平均每小時4人；修理時間服從負(fù)指數(shù)分布，平均需要6分鐘。試求：修理店空閑的概率；店內(nèi)恰有3位顧客的概率；店內(nèi)至少有一位顧客的概率；在店內(nèi)平均顧客數(shù)；每位在店內(nèi)平均逗留時間；等待服務(wù)的平均顧客數(shù)；每位顧客平均等待服務(wù)時間；顧客在店內(nèi)逗留時間超過10分鐘的概率。第一百一十三頁，共一百二十八頁，編輯于2023年，星期二解：本例可看成一個M/M/1/排隊問題，其中=4，=1/0.1=10(人/小時），=/=2/5<11、修理店內(nèi)空閑的概率

P0=1-=(1-2/5)=0.62、店內(nèi)恰有3個顧客的概率

P3=3(1-)=(2/5)3(1-2/5)=0.0383、店內(nèi)至少有1位顧客的概率

P{N1}=1-P0=1-(1-)==2/5=0.4第一百一十四頁，共一百二十八頁，編輯于2023年，星期二4、在店內(nèi)平均顧客數(shù)

L=/(1-)=(2/5)/(1-2/5)=0.67(人）5、每位顧客在店內(nèi)平均逗留時間

W=L/=0.67/4=10分鐘6、等待服務(wù)的平均顧客數(shù)

Lq=L-=0.67-2/5=0.27(人)7、每個顧客平均等待服務(wù)時間

Wq=Lq/=0.27/4=0.0675小時=4分鐘第一百一十五頁，共一百二十八頁，編輯于2023年，星期二8、顧客在店內(nèi)逗留時間超過10分鐘的概率P{T>10}=e-10(1/6-1/15)=e-1=0.3677P{T>t}=e-(-)tt=10分鐘,=10人/小時=10/60=1/6=4人/小時=4/60=1/15第一百一十六頁，共一百二十八頁，編輯于2023年，星期二

練習(xí)2：考慮一個鐵路列車編組站。設(shè)待編列車到達(dá)時間間隔服從負(fù)指數(shù)分布，平均每小時到達(dá)2列；服務(wù)臺是編組站，編組時間服從負(fù)指數(shù)分布，平均每20分鐘可編一組。已知編組站上共有2股道，當(dāng)均被占用時，不能接車，再來的列車只能停在站外或前方站。求：

1、在平衡狀態(tài)下系統(tǒng)中列車的平均數(shù)；

2、每一列車的平均逗留時間；

3、等待編組的列車平均數(shù)；

4、列車在系統(tǒng)中的平均等待編組時間；

5、如果列車因站中2股道均被占用而停在站外或前方站時，每列車每小時費用為a元，求每天由于列車在站外等待而造成的損失。第一百一十七頁，共一百二十八頁，編輯于2023年，星期二解：本例可看成一個M/M/1/排隊問題，其中=2，=3，=/=2/3<11、系統(tǒng)中列車的平均數(shù)

L=/(1-)=(2/3)/(1-2/3)=2（列）

2、列車在系統(tǒng)中的平均停留時間

W=L/=2/2=1（小時）

3、系統(tǒng)中等待編組的列車平均數(shù)

Lq=L-=2-2/3=4/3（列）

4、列車在系統(tǒng)中的平均等待編組時間

Wq=Lq/=(4/3)/(1/2)=2/3（小時）第一百一十八頁，共一百二十八頁，編輯于2023年，星期二5、記列車平均延誤（由于站內(nèi)2股道均被占用而不能進(jìn)站）時間為W0則

W0=WP{N>2}=W{1-P0-P1-P2}=W{1-(l-)-(l-)1-(l-)2}=1*3=3=(2/3)3=0.296（小時）故每天列車由于等待而支出的平均費用E=24W0a=24*2*0.296*a=14.2a元第一百一十九頁，共一百二十八頁，編輯于2023年，星期二

練習(xí)3：

(病人候診問題)某單位醫(yī)院的一個科室有一位醫(yī)生值班，經(jīng)長期觀察，每小平均有4個病人，醫(yī)生每小時平均可診5個病人，病人的到來服從泊松分布，醫(yī)生的診病時間服從負(fù)指數(shù)分布，試問：

1、該科室平均有病人數(shù)；平均排隊候診病人數(shù)；看一次病平均所需的時間；排隊等候看病的平均時間

2如果滿足99%以上的病人有座，此科室至少應(yīng)設(shè)多少座位?3如果該單位每天24小時上班，病人看病1小時因耽誤工作單位要損失30元，這樣單位平均每天損失多少元? 4如果該科室提高看病速度，每小時平均可診6個病人，單位每天可減少損失多少?可減少多少座位?第一百二十頁，共一百二十八頁，編輯于2023年，星期二解：該模型為M\M\1該科室平均有病人數(shù)為該科室內(nèi)排隊候診病人數(shù)為

看一次病平均所需的時間為排隊等候看病的平均時間為為滿足99%以上的病人有座，設(shè)科室應(yīng)設(shè)m個座位，則m應(yīng)滿足

第一百二十一頁，共一百二十八頁，編輯于2023年，星期二

所以該科室至少應(yīng)設(shè)20個座位如果該單位24小時上班，則每天平均有病人24×4=96人，病人看病所花去的總時間為96×