運(yùn)籌學(xué)排隊(duì)論新

運(yùn)籌學(xué)排隊(duì)論新第十二章排隊(duì)論到達(dá)間隔的分布和服務(wù)時(shí)間的分布本章內(nèi)容基本概念單服務(wù)臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析多服務(wù)臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析一般服務(wù)時(shí)間M/G/1模型第2頁,共128頁，2024年2月25日，星期天

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

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

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

①

有要求得到某種服務(wù)的人或物。排隊(duì)論里把要求服務(wù)的對(duì)象統(tǒng)稱為“顧客”②有提供服務(wù)的人或機(jī)構(gòu)。把提供服務(wù)的人或機(jī)構(gòu)稱為“服務(wù)臺(tái)”或“服務(wù)員”③顧客的到達(dá)、服務(wù)的時(shí)間至少有一個(gè)是隨機(jī)的，服從某種分布。第9頁,共128頁，2024年2月25日，星期天一般的排隊(duì)系統(tǒng)，都可由圖12-1加以描述。顧客源排隊(duì)結(jié)構(gòu)服務(wù)機(jī)構(gòu)排隊(duì)規(guī)則顧客到來服務(wù)規(guī)則離去圖12-1排隊(duì)系統(tǒng)第10頁,共128頁，2024年2月25日，星期天

排隊(duì)系統(tǒng)都有輸入過程、排隊(duì)規(guī)則和服務(wù)臺(tái)等3個(gè)組成部分：1、輸入過程這是指要求服務(wù)的顧客是按怎樣的規(guī)律到達(dá)排隊(duì)系統(tǒng)的過程，有時(shí)也把它稱為顧客流．一般可以從3個(gè)方面來描述輸入過程。排隊(duì)系統(tǒng)的組成第11頁,共128頁，2024年2月25日，星期天

(1)

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

顧客流的概率分布一般有定長(zhǎng)分布、二項(xiàng)分布、泊松流(最簡(jiǎn)單流)、愛爾朗分布等若干種。第13頁,共128頁，2024年2月25日，星期天2、排隊(duì)規(guī)則這是指服務(wù)臺(tái)從隊(duì)列中選取顧客進(jìn)行服務(wù)的順序。損失制混合制隊(duì)長(zhǎng)有限等待時(shí)間有限逗留時(shí)間有限排隊(duì)規(guī)則等待制先到先服務(wù)后到先服務(wù)隨機(jī)服務(wù)優(yōu)先權(quán)服務(wù)第14頁,共128頁，2024年2月25日，星期天3．服務(wù)臺(tái)情況。服務(wù)臺(tái)可以從3方面來描述：

(1)服務(wù)臺(tái)數(shù)量及構(gòu)成形式圖12-2單隊(duì)列-單服務(wù)臺(tái)排隊(duì)系統(tǒng)第15頁,共128頁，2024年2月25日，星期天圖12-3單隊(duì)列——S個(gè)服務(wù)臺(tái)并聯(lián)的排隊(duì)系統(tǒng)圖12-4S個(gè)隊(duì)列——S個(gè)服務(wù)臺(tái)的并聯(lián)排隊(duì)系統(tǒng)第16頁,共128頁，2024年2月25日，星期天圖12-5單隊(duì)——多個(gè)服務(wù)臺(tái)的串聯(lián)排隊(duì)系統(tǒng)圖12-6多隊(duì)——多服務(wù)臺(tái)混聯(lián)、網(wǎng)絡(luò)系統(tǒng)第17頁,共128頁，2024年2月25日，星期天 (2)服務(wù)方式。這是指在某一時(shí)刻接受服務(wù)的顧客數(shù)，它有單個(gè)服務(wù)和成批服務(wù)兩種。 (3)服務(wù)時(shí)間的分布。在多數(shù)情況下，對(duì)每一個(gè)顧客的服務(wù)時(shí)間是一隨機(jī)變量，其概率分布有定長(zhǎng)分布、負(fù)指數(shù)分布、K級(jí)愛爾朗分布、一般分布(所有顧客的服務(wù)時(shí)間都是獨(dú)立同分布的)等等。第18頁,共128頁，2024年2月25日，星期天

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

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

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

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

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

PR：表示優(yōu)先權(quán)服務(wù)。第23頁,共128頁，2024年2月25日，星期天例如：某排隊(duì)問題為

M／M／S／∞／∞／FCFS

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

M/M/s

第24頁,共128頁，2024年2月25日，星期天

某些情況下，排隊(duì)問題僅用上述表達(dá)形式中的前3個(gè)、4個(gè)、5個(gè)符號(hào)。如不特別說明均理解為系統(tǒng)等待空間容量無限；顧客源無限，先到先服務(wù)，單個(gè)服務(wù)的等待制系統(tǒng)。第25頁,共128頁，2024年2月25日，星期天（三）排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo)1.隊(duì)長(zhǎng)和排隊(duì)長(zhǎng)

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

排隊(duì)長(zhǎng)是指系統(tǒng)中正在排隊(duì)等待服務(wù)的顧客數(shù)。第26頁,共128頁，2024年2月25日，星期天2．等待時(shí)間和逗留時(shí)間

從顧客到達(dá)時(shí)刻起到他開始接受服務(wù)止這段時(shí)間稱為等待時(shí)間，是隨機(jī)變量。 從顧客到達(dá)時(shí)刻起到他接受服務(wù)完成止這段時(shí)間稱為逗留時(shí)間，也是隨機(jī)變量。第27頁,共128頁，2024年2月25日，星期天3．忙期和閑期

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

與忙期相對(duì)的是閑期，即服務(wù)機(jī)構(gòu)連續(xù)保持空閑的時(shí)間。在排隊(duì)系統(tǒng)中，忙期和閑期總是交替出現(xiàn)的。第28頁,共128頁，2024年2月25日，星期天

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

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

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

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

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

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

Tq(t)：時(shí)刻t到達(dá)系統(tǒng)的顧客在系統(tǒng)中的等待時(shí)間。第30頁,共128頁，2024年2月25日，星期天

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

在平衡狀態(tài)下，這些量與系統(tǒng)所處的時(shí)刻無關(guān)，而且系統(tǒng)的初始狀態(tài)的影響也會(huì)消失。因此，我們?cè)诒菊轮袑⒅饕懻撆c系統(tǒng)所處時(shí)刻無關(guān)的性質(zhì)，即統(tǒng)計(jì)平衡性質(zhì)。第31頁,共128頁，2024年2月25日，星期天L或Ls—平均隊(duì)長(zhǎng) 穩(wěn)態(tài)系統(tǒng)任一時(shí)刻的顧客數(shù)的期望值；Lq—平均等待隊(duì)長(zhǎng)或隊(duì)列長(zhǎng) 穩(wěn)態(tài)系統(tǒng)任一時(shí)刻等待服務(wù)的顧客數(shù)期望值；W或Ws—

平均逗留時(shí)間進(jìn)入穩(wěn)態(tài)系統(tǒng)的顧客逗留時(shí)間期望值；Wq—平均等待時(shí)間 進(jìn)入穩(wěn)態(tài)系統(tǒng)的顧客等待時(shí)間期望值。第32頁,共128頁，2024年2月25日，星期天Pn—系統(tǒng)的狀態(tài)Pn=P{N=n}：穩(wěn)態(tài)系統(tǒng)任一時(shí)刻狀態(tài)為n的概率。當(dāng)n=0時(shí)，Pn即P0為穩(wěn)態(tài)系統(tǒng)所有服務(wù)臺(tái)全部空閑的概率。第33頁,共128頁，2024年2月25日，星期天(2)其他常用數(shù)量指標(biāo)s——系統(tǒng)中并聯(lián)服務(wù)臺(tái)的數(shù)目

——平均到達(dá)率（單位時(shí)間內(nèi)到達(dá)的平均顧客數(shù)）1/——平均到達(dá)間隔

——平均服務(wù)率（單位時(shí)間內(nèi)可以服務(wù)完的平均顧客數(shù)）1/

——平均服務(wù)時(shí)間第34頁,共128頁，2024年2月25日，星期天

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

e

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

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

e

＝

第35頁,共128頁，2024年2月25日，星期天第二節(jié)到達(dá)間隔的分布和服務(wù)時(shí)間的分布第36頁,共128頁，2024年2月25日，星期天

一、Poisson流（Poisson過程）定義滿足以下三個(gè)條件的輸入流稱為Poisson流1、無后效性：不相交的時(shí)間區(qū)間內(nèi)到達(dá)的顧客數(shù)互相獨(dú)立。2、平穩(wěn)性：在時(shí)間區(qū)間[t,t+

t)內(nèi)到達(dá)1個(gè)顧客的概率只與

t有關(guān)。即

表示單位時(shí)間內(nèi)有一個(gè)顧客到達(dá)的概率。3、普通性：設(shè)在[t,t+

t）內(nèi)到達(dá)多于一個(gè)顧客的概率極小，即第37頁,共128頁，2024年2月25日，星期天Poisson流與Poisson分布定理1

對(duì)于一個(gè)參數(shù)為

的Poisson流，在[0，t]內(nèi)到達(dá)n個(gè)顧客的概率為

即服從以

為參數(shù)的Poisson分布。

定理1說明如果顧客的到達(dá)為Poisson流的話，則到達(dá)顧客數(shù)的分布恰好為Poisson分布。第38頁,共128頁，2024年2月25日，星期天

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

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

設(shè)隨機(jī)變量T服從以

為參數(shù)的負(fù)指數(shù)分布，它的分布函數(shù)為：第39頁,共128頁，2024年2月25日，星期天負(fù)指數(shù)分布的性質(zhì)：

性質(zhì)1

由條件概率公式容易證明

性質(zhì)2

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

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

第40頁,共128頁，2024年2月25日，星期天由性質(zhì)2可知：

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

）是等價(jià)的。

根據(jù)負(fù)指數(shù)分布與泊松流的關(guān)系可以推導(dǎo)出，當(dāng)服務(wù)機(jī)構(gòu)對(duì)顧客的服務(wù)時(shí)間服從參數(shù)為

的負(fù)指數(shù)分布，如果服務(wù)機(jī)構(gòu)處于忙期，則該服務(wù)機(jī)構(gòu)的輸出，即服務(wù)完畢離開服務(wù)機(jī)構(gòu)的顧客數(shù)將是服從泊松分布的泊松流。其中

為每個(gè)顧客的平均服務(wù)時(shí)間，也是顧客相繼離開的間隔。

第41頁,共128頁，2024年2月25日，星期天三、k階愛爾朗分布定理

設(shè)v1，v2，…，vk是k個(gè)互相獨(dú)立的隨機(jī)變量，服從相同參數(shù)k

的負(fù)指數(shù)分布，那么

S=v1+v2+…+vk服從k階Erlang分布，S的密度函數(shù)為第42頁,共128頁，2024年2月25日，星期天K=1時(shí)愛爾朗分布化歸為負(fù)指數(shù)分布，當(dāng)K→∞時(shí)，得到長(zhǎng)度為1/

的定長(zhǎng)服務(wù)。m=1k=1k=2k=4k=8第43頁,共128頁，2024年2月25日，星期天第三節(jié)單服務(wù)臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析第44頁,共128頁，2024年2月25日，星期天標(biāo)準(zhǔn)排隊(duì)模型[M/M/1]:[

/

/FCFS]顧客到達(dá)的時(shí)間間隔是負(fù)指數(shù)分布，即輸入流是參數(shù)為

的Poisson流服從參數(shù)為μ的負(fù)指數(shù)分布一個(gè)服務(wù)臺(tái)排隊(duì)系統(tǒng)的容量無限顧客源的容量無限實(shí)行先到先服務(wù)的一個(gè)服務(wù)系統(tǒng)第45頁,共128頁，2024年2月25日，星期天一、系統(tǒng)穩(wěn)態(tài)概率pn的計(jì)算

假設(shè)在t+

t時(shí)刻系統(tǒng)中顧客數(shù)為n的概率Pn(t+

t)Pn(t)Pn-1(t)Pn+1(t)Pn(t)Snt+

t時(shí)刻SnSnSn+1Sn-1t時(shí)刻無到達(dá)，無離開無到達(dá)，離開一個(gè)到達(dá)一個(gè)，無離開到達(dá)一個(gè)，離開一個(gè)第46頁,共128頁，2024年2月25日，星期天由于這四種方式互不相容，故由概率的加法定理得：該差分方程組為瞬態(tài)解，需求穩(wěn)態(tài)解。第47頁,共128頁，2024年2月25日，星期天[M/M/1]:[

/

/FCFS]穩(wěn)態(tài)時(shí)狀態(tài)轉(zhuǎn)移圖λ012n-1nn+1穩(wěn)態(tài)情況下，系統(tǒng)狀態(tài)已不隨時(shí)間發(fā)生變化：第48頁,共128頁，2024年2月25日，星期天穩(wěn)態(tài)情況下，系統(tǒng)狀態(tài)已不隨時(shí)間發(fā)生變化：第49頁,共128頁，2024年2月25日，星期天得到

令稱

為服務(wù)強(qiáng)度，則得第50頁,共128頁，2024年2月25日，星期天系統(tǒng)的過渡狀態(tài)與穩(wěn)定狀態(tài)過渡穩(wěn)定第51頁,共128頁，2024年2月25日，星期天二、系統(tǒng)的數(shù)量指標(biāo)1、服務(wù)臺(tái)空閑的概率和忙的概率：空閑的概率：P0=1-

忙的概率：1-P0=

2、系統(tǒng)中平均顧客數(shù)（隊(duì)長(zhǎng)期望值Ls）：第52頁,共128頁，2024年2月25日，星期天3、系統(tǒng)中等待的平均顧客數(shù)（隊(duì)長(zhǎng)期望值Lq）：4、系統(tǒng)中顧客逗留時(shí)間的期望值：第53頁,共128頁，2024年2月25日，星期天5、隊(duì)列中顧客逗留時(shí)間的期望值：現(xiàn)將以上公式歸納如下：它們相互關(guān)系如下：第54頁,共128頁，2024年2月25日，星期天Little公式

下列公式對(duì)任何服務(wù)系統(tǒng)均成立第55頁,共128頁，2024年2月25日，星期天例1

高速公路入口收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車到達(dá)服從Poisson分布，平均到達(dá)速率為100輛／小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒／輛。求1、收費(fèi)處空閑的概率；2、收費(fèi)處忙的概率；3、系統(tǒng)中分別有1，2，3輛車的概率。第56頁,共128頁，2024年2月25日，星期天解：根據(jù)題意,

=100輛/小時(shí),1/

=15（秒/輛）=1/240（小時(shí)/輛）,即

＝240（輛/小時(shí)）。 因此，

=

/

=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第57頁,共128頁，2024年2月25日，星期天系統(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第58頁,共128頁，2024年2月25日，星期天例2

高速公路入口收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車到達(dá)服從Poisson分布，平均到達(dá)速率為200輛／小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒／輛。求Ls、Lq、Ws和Wq。第59頁,共128頁，2024年2月25日，星期天解：根據(jù)題意，

=200輛/小時(shí)，

=240輛/小時(shí)，

=

/

=5/6。第60頁,共128頁，2024年2月25日，星期天有限隊(duì)列模型[M/M/1]:[N/

/FCFS]

如果系統(tǒng)的最大容量為N時(shí)，排隊(duì)等待的顧客最多為N-1，在某時(shí)刻一顧客到達(dá)時(shí)，如系統(tǒng)中已有N個(gè)顧客，那么這個(gè)顧客就被拒絕進(jìn)入系統(tǒng)。第61頁,共128頁，2024年2月25日，星期天系統(tǒng)的狀態(tài)概率平衡方程對(duì)于狀態(tài)0：

P1=

P0

… …對(duì)于狀態(tài)k：

Pk-1+

Pk+1=(

+

)Pk0<k<N… …對(duì)于狀態(tài)N：

PN-1=

PNλ012n-1n第62頁,共128頁，2024年2月25日，星期天系統(tǒng)的狀態(tài)概率由得到第63頁,共128頁，2024年2月25日，星期天系統(tǒng)的運(yùn)行指標(biāo)第64頁,共128頁，2024年2月25日，星期天有效到達(dá)率第65頁,共128頁，2024年2月25日，星期天Little公式第66頁,共128頁，2024年2月25日，星期天例3

一個(gè)單人理發(fā)店，除理發(fā)椅外，還有4把椅子可供顧客等候。顧客到達(dá)發(fā)現(xiàn)沒有座位空閑，就不再等待而離去。顧客到達(dá)的平均速率為4人/小時(shí)，理發(fā)的平均時(shí)間為10分鐘/人。顧客到達(dá)服從Poisson流，理發(fā)時(shí)間服從負(fù)指數(shù)分布。求：1、顧客到達(dá)不用等待就可理發(fā)的概率；2、理發(fā)店里的平均顧客數(shù)以及等待理發(fā)的平均顧客數(shù)；3、顧客來店理發(fā)一次平均花費(fèi)的時(shí)間及平均等待的時(shí)間；4、顧客到達(dá)后因客滿而離去的概率；5、增加一張椅子可以減少的顧客損失率。第67頁,共128頁，2024年2月25日，星期天解：這是一個(gè)[M/M/1]:[N/

/FCFS]系統(tǒng)，其中N=4+1=5，

=4人/小時(shí)，

=6人/小時(shí)，

=2/3。第68頁,共128頁，2024年2月25日，星期天因客滿而離去的概率為0.0048第69頁,共128頁，2024年2月25日，星期天當(dāng)N=6時(shí)P5-P6=0.0480-0.0311=0.0169=1.69%即增加一張椅子可以減少顧客損失率1.69%第70頁,共128頁，2024年2月25日，星期天[M/M/1]:[∞/m/FCFS]模型

設(shè)顧客總數(shù)為m。當(dāng)顧客需要服務(wù)時(shí)，就進(jìn)入隊(duì)列等待；服務(wù)完畢后，重新回到顧客源中。如此循環(huán)往復(fù)。服務(wù)臺(tái)...顧客源需要服務(wù)服務(wù)完畢隊(duì)列第71頁,共128頁，2024年2月25日，星期天顧客源中剩余的顧客數(shù)

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

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

λe=λ(m-Ls)第72頁,共128頁，2024年2月25日，星期天狀態(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) 第73頁,共128頁，2024年2月25日，星期天運(yùn)行指標(biāo)第74頁,共128頁，2024年2月25日，星期天(1)修理工空閑的概率；(2)五臺(tái)機(jī)器都出故障的概率；(3)出故障的平均臺(tái)數(shù)；(4)平均停工時(shí)間；(5)平均等待修理時(shí)間；(6)評(píng)價(jià)系統(tǒng)運(yùn)行情況。例4

某車間有5臺(tái)機(jī)器，每臺(tái)機(jī)器的連續(xù)運(yùn)轉(zhuǎn)時(shí)間服從負(fù)指數(shù)分布，平均連續(xù)運(yùn)行時(shí)間15分鐘。有一個(gè)修理工，每次修理時(shí)間服從負(fù)指數(shù)分布，平均每次12分鐘。求:第75頁,共128頁，2024年2月25日，星期天解根據(jù)題意，m=5，λ=1/15，μ=1/12，ρ=λ/μ=0.8

第76頁,共128頁，2024年2月25日，星期天第77頁,共128頁，2024年2月25日，星期天第4節(jié)多服務(wù)臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析第78頁,共128頁，2024年2月25日，星期天多服務(wù)臺(tái)模型[M/M/c]標(biāo)準(zhǔn)的[M/M/c]:[∞/∞/FCFS]模型系統(tǒng)容量有限的[M/M/c]:[N/∞/FCFS]模型有限顧客源的[M/M/c]:[∞/m/FCFS]模型第79頁,共128頁，2024年2月25日，星期天[M/M/c]:[∞/∞/FCFS]模型服務(wù)臺(tái)服務(wù)臺(tái)服務(wù)臺(tái)顧客到達(dá)顧客離去顧客離去顧客離去隊(duì)列

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

第80頁,共128頁，2024年2月25日，星期天

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

對(duì)狀態(tài)1: λP0+2μP2=(λ+μ)P1 …………對(duì)狀態(tài)c： λPc-1+cμPc+1=(λ+cμ)Pc …………對(duì)狀態(tài)n λPn-1+cμPn+1=(λ+cμ)Pn ………01cn第82頁,共128頁，2024年2月25日，星期天狀態(tài)概率第83頁,共128頁，2024年2月25日，星期天運(yùn)行指標(biāo)第84頁,共128頁，2024年2月25日，星期天例5

某售票處有三個(gè)窗口，顧客到達(dá)服從Poisson流，到達(dá)速率為0.9人／分，售票時(shí)間服從負(fù)指數(shù)分布，每個(gè)窗口的平均售票速率為0.4人／分。顧客到達(dá)后排成一隊(duì)，依次到空閑窗口購(gòu)票。求：(1)所有窗口都空閑的概率；(2)平均隊(duì)長(zhǎng)；(3)平均等待時(shí)間及逗留時(shí)間；(4)顧客到達(dá)后必須等待的概率。第85頁,共128頁，2024年2月25日，星期天解：λ/μ=2.25，ρ=λ/cμ=0.75(1)所有窗口都空閑的概率，即求P0的值(2)平均隊(duì)長(zhǎng)，即求Ls的值，必須先求Lq

第86頁,共128頁，2024年2月25日，星期天(3)平均等待時(shí)間和平均逗留時(shí)間，即求Wq和Ws和的值(4)顧客到達(dá)后必須等待，即n≥3第87頁,共128頁，2024年2月25日，星期天服務(wù)臺(tái)服務(wù)臺(tái)服務(wù)臺(tái)顧客到達(dá)顧客離去顧客離去顧客離去

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

這樣，原來的M/M/3系統(tǒng)就變成了3個(gè)M/M/1型的子系統(tǒng)。第88頁,共128頁，2024年2月25日，星期天 M/M/c和c個(gè)M/M/1模型的比較指標(biāo)（1）M/M/3型（2）M/M/1型售票處空閑的概率0.07480.25（各子系統(tǒng)）購(gòu)票者必須等待的概率P(N>3)=0.570.75排隊(duì)長(zhǎng)1.7（人）2.25（人）（各子系統(tǒng)）平均隊(duì)長(zhǎng)3.95（人）9（人）（整個(gè)系統(tǒng)）平均逗留時(shí)間4.39（分鐘）10（分鐘）平均等待時(shí)間1.89（分鐘）7.5（分鐘）第89頁,共128頁，2024年2月25日，星期天[M/M/c]:[N/∞/FCFS]模型離開服務(wù)臺(tái)服務(wù)臺(tái)服務(wù)臺(tái)顧客到達(dá)顧客離去顧客離去顧客離去隊(duì)列

設(shè)系統(tǒng)容量為N(N≥c)。設(shè)顧客到達(dá)的速率為λ，每個(gè)服務(wù)臺(tái)服務(wù)的速率為μ，ρ=λ/cμ。由于系統(tǒng)不會(huì)無限止地接納顧客，對(duì)ρ不必加以限制。第90頁,共128頁，2024年2月25日，星期天狀態(tài)轉(zhuǎn)移圖與狀態(tài)轉(zhuǎn)移方程對(duì)狀態(tài)0: λP0=μP1

對(duì)狀態(tài)1: λP0+2μP2=(λ+μ)P1 …………對(duì)狀態(tài)c： λPc-1+cμPc+1=(λ+cμ)Pc …………對(duì)狀態(tài)N λPN-1=cμPN ………01cN第91頁,共128頁，2024年2月25日，星期天狀態(tài)概率第92頁,共128頁，2024年2月25日，星期天運(yùn)行指標(biāo)第93頁,共128頁，2024年2月25日，星期天例6某旅館有8個(gè)單人房間，旅客到達(dá)服從Poisson流，平均速率為6人／天，旅客平均逗留時(shí)間為2天，求：(1)每天客房平均占用數(shù)；(2)旅館客滿的概率。第94頁,共128頁，2024年2月25日，星期天解：旅館8個(gè)房間全滿的概率為0.423平均占用客房數(shù)為6.9間。第95頁,共128頁，2024年2月25日，星期天[M/M/c]:[∞/m/FCFS]模型顧客到達(dá)修理速率μ發(fā)生故障等待修理的機(jī)器修理速率μ修理速率μ正在修理的機(jī)器到達(dá)速率(m-n)λ修理速率cμ運(yùn)行的機(jī)器數(shù)m-n第96頁,共128頁，2024年2月25日，星期天狀態(tài)概率其中第97頁,共128頁，2024年2月25日，星期天運(yùn)行指標(biāo)

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

λe=λ(m-Ls)第98頁,共128頁，2024年2月25日，星期天例7

車間有5臺(tái)機(jī)器，每臺(tái)機(jī)器的故障率為1次／小時(shí)，有2個(gè)修理工負(fù)責(zé)修理這5臺(tái)機(jī)器，工作效率相同，為4臺(tái)／小時(shí)。求：(1)等待修理的平均機(jī)器數(shù)；(2)正在修理的平均機(jī)器數(shù)；(3)每小時(shí)發(fā)生故障的平均機(jī)器數(shù)；(4)平均等待修理的時(shí)間；(5)平均停工時(shí)間。第99頁,共128頁，2024年2月25日，星期天解可以計(jì)算得到（算式略）：P1=0.394，P2=0.197，P3=0.074，P4=0.018，P5=0.002第100頁,共128頁，2024年2月25日，星期天由此，計(jì)算系統(tǒng)的各項(xiàng)運(yùn)行指標(biāo)如下：第101頁,共128頁，2024年2月25日，星期天第5節(jié)一般服務(wù)時(shí)間M/G/1模型第102頁,共128頁，2024年2月25日，星期天

服務(wù)時(shí)間一般分布時(shí)，需要知道服務(wù)時(shí)間的均值和方差。當(dāng)時(shí)，排隊(duì)系統(tǒng)可以達(dá)到平穩(wěn)狀態(tài)。P－K公式第103頁,共128頁，2024年2月25日，星期天1負(fù)指數(shù)服務(wù)時(shí)間M/M/1模型只有負(fù)指數(shù)分布時(shí)排隊(duì)長(zhǎng)的一半。2定長(zhǎng)服務(wù)時(shí)間M/D/1模型第104頁,共128頁，2024年2月25日，星期天3k階愛爾朗服務(wù)時(shí)間M/Ek/1模型

若顧客需接受k個(gè)串行的服務(wù)臺(tái)的服務(wù)后才離開，且每個(gè)服務(wù)臺(tái)服務(wù)時(shí)間服從負(fù)指數(shù)分布，平均服務(wù)時(shí)間相等。 則總服務(wù)時(shí)間服從k階愛爾朗分布。第105頁,共128頁，2024年2月25日，星期天Erlang分布的均值和方差總服務(wù)時(shí)間服從愛爾朗分布：每個(gè)服務(wù)臺(tái)的平均服務(wù)時(shí)間是：第106頁,共128頁，2024年2月25日，星期天M/Ek/1系統(tǒng)的運(yùn)行指標(biāo)第107頁,共128頁，2024年2月25日，星期天

例8

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

解：本例是M/G/1系統(tǒng)，且已知第108頁,共128頁，2024年2月25日，星期天

可見顧客等待時(shí)間太長(zhǎng)，隊(duì)列也太長(zhǎng)。主要原因是服務(wù)時(shí)間的方差太大！第109頁,共128頁，2024年2月25日，星期天例9

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

練習(xí)1：某修理店只有一位修理工，來修理的顧客到達(dá)過程為Poisson流，平均每小時(shí)4人；修理時(shí)間服從負(fù)指數(shù)分布，平均需要6分鐘。試求：修理店空閑的概率；店內(nèi)恰有3位顧客的概率；店內(nèi)至少有一位顧客的概率；在店內(nèi)平均顧客數(shù)；每位在店內(nèi)平均逗留時(shí)間；等待服務(wù)的平均顧客數(shù)；每位顧客平均等待服務(wù)時(shí)間；顧客在店內(nèi)逗留時(shí)間超過10分鐘的概率。第113頁,共128頁，2024年2月25日，星期天解：本例可看成一個(gè)M/M/1/

排隊(duì)問題，其中=4，=1/0.1=10(人/小時(shí)），=/=2/5<11、修理店內(nèi)空閑的概率

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

P3=

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

P{N

1}=1-P0=1-(1-)==2/5=0.4第114頁,共128頁，2024年2月25日，星期天4、在店內(nèi)平均顧客數(shù)

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

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

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

Wq=Lq/=0.27/4=0.0675小時(shí)=4分鐘第115頁,共128頁，2024年2月25日，星期天8、顧客在店內(nèi)逗留時(shí)間超過10分鐘的概率P{T>10}=e-10(1/6-1/15)=e-1=0.3677P{T>t}=e-(

-

)tt=10分鐘,

=10人/小時(shí)=10/60=1/6=4人/小時(shí)=4/60=1/15第116頁,共128頁，2024年2月25日，星期天

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

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

2、每一列車的平均逗留時(shí)間；

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

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

5、如果列車因站中2股道均被占用而停在站外或前方站時(shí)，每列車每小時(shí)費(fèi)用為a元，求每天由于列車在站外等待而造成的損失。第117頁,共128頁，2024年2月25日，星期天解：本例可看成一個(gè)M/M/1/

排隊(duì)問題，其中=2，=3，=/=2/3<11、系統(tǒng)中列車的平均數(shù)

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

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

W=L/

=2/2=1（小時(shí)）

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

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

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

Wq=Lq/=(4/3)/(1/2)=2/3（小時(shí)）第118頁,共128頁，2024年2月25日，星期天5、記列車平均延誤（由于站內(nèi)2股道均被占用而不能進(jìn)站）時(shí)間為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（小時(shí)）故每天列車由于等待而支出的平均費(fèi)用E=24W0a=24*2*0.296*a=14.2a元第119頁,共128頁，2024年2月25日，星期天

練習(xí)3：

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

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

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

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

第121頁,共128頁，2024年2月25日，星期天

所以該科室至少應(yīng)設(shè)2