運籌學排隊論新

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

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

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

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

①

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

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

(1)

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

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

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

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

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

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

FCFS：表示先到先服務；

LCFS：表示后到先服務；

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

M／M／S／∞／∞／FCFS

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

M/M/s

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

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

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

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

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

忙期是指從顧客到達空閑著的服務機構起，到服務機構再次成為空閑止的這段時間，即服務機構連續(xù)忙的時間。這是個隨機變量，它關系到服務員的服務強度。

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

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

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

(1)主要數(shù)量指標

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

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

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

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

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

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

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

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

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

——平均服務時間第34頁,共131頁，2024年2月25日，星期天

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

e

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

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

e

＝

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

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

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

t有關。即

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

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

對于一個參數(shù)為

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

即服從以

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

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

二、負指數(shù)分布

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

設隨機變量T服從以

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

性質(zhì)1

由條件概率公式容易證明

性質(zhì)2

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

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

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

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

）是等價的。

根據(jù)負指數(shù)分布與泊松流的關系可以推導出，當服務機構對顧客的服務時間服從參數(shù)為

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

為每個顧客的平均服務時間，也是顧客相繼離開的間隔。

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

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

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

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

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

/

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

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

假設在t+

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

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

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

/

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

令稱

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

忙的概率：1-P0=

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

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

高速公路入口收費處設有一個收費通道，汽車到達服從Poisson分布，平均到達速率為100輛／小時，收費時間服從負指數(shù)分布，平均收費時間為15秒／輛。求1、收費處空閑的概率；2、收費處忙的概率；3、系統(tǒng)中分別有1，2，3輛車的概率。第56頁,共131頁，2024年2月25日，星期天解：根據(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第57頁,共131頁，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頁,共131頁，2024年2月25日，星期天例2

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

=200輛/小時，

=240輛/小時，

=

/

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

/FCFS]

如果系統(tǒng)的最大容量為N時，排隊等待的顧客最多為N-1，在某時刻一顧客到達時，如系統(tǒng)中已有N個顧客，那么這個顧客就被拒絕進入系統(tǒng)。第61頁,共131頁，2024年2月25日，星期天系統(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第62頁,共131頁，2024年2月25日，星期天系統(tǒng)的狀態(tài)概率由得到第63頁,共131頁，2024年2月25日，星期天系統(tǒng)的運行指標第64頁,共131頁，2024年2月25日，星期天有效到達率第65頁,共131頁，2024年2月25日，星期天Little公式第66頁,共131頁，2024年2月25日，星期天例3

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

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

=4人/小時，

=6人/小時，

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

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

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

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

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

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

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

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

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

系統(tǒng)的服務速率與系統(tǒng)中的顧客數(shù)有關。當系統(tǒng)中的顧客數(shù)k不大于服務臺個數(shù)，即1≤k≤c時，系統(tǒng)中的顧客全部在服務臺中，這時系統(tǒng)的服務速率為kμ；當系統(tǒng)中的顧客數(shù)k＞c時，服務臺中正在接受服務的顧客數(shù)仍為c個，其余顧客在隊列中等待服務，這時系統(tǒng)的服務速率為cμ。只有當ρ＜1時系統(tǒng)才不會排成無限的隊列。服務強度服務機構平均利用率第81頁,共131頁，2024年2月25日，星期天狀態(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第82頁,共131頁，2024年2月25日，星期天狀態(tài)概率第83頁,共131頁，2024年2月25日，星期天運行指標第84頁,共131頁，2024年2月25日，星期天例5

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

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

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

這樣，原來的M/M/3系統(tǒng)就變成了3個M/M/1型的子系統(tǒng)。第88頁,共131頁，2024年2月25日，星期天 M/M/c和c個M/M/1模型的比較指標（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（分鐘）第89頁,共131頁，2024年2月25日，星期天[M/M/c]:[N/∞/FCFS]模型離開服務臺服務臺服務臺顧客到達顧客離去顧客離去顧客離去隊列

設系統(tǒng)容量為N(N≥c)。設顧客到達的速率為λ，每個服務臺服務的速率為μ，ρ=λ/cμ。由于系統(tǒng)不會無限止地接納顧客，對ρ不必加以限制。第90頁,共131頁，2024年2月25日，星期天狀態(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第91頁,共131頁，2024年2月25日，星期天狀態(tài)概率第92頁,共131頁，2024年2月25日，星期天運行指標第93頁,共131頁，2024年2月25日，星期天例6某旅館有8個單人房間，旅客到達服從Poisson流，平均速率為6人／天，旅客平均逗留時間為2天，求：(1)每天客房平均占用數(shù)；(2)旅館客滿的概率。第94頁,共131頁，2024年2月25日，星期天解：旅館8個房間全滿的概率為0.423平均占用客房數(shù)為6.9間。第95頁,共131頁，2024年2月25日，星期天[M/M/c]:[∞/m/FCFS]模型顧客到達修理速率μ發(fā)生故障等待修理的機器修理速率μ修理速率μ正在修理的機器到達速率(m-n)λ修理速率cμ運行的機器數(shù)m-n第96頁,共131頁，2024年2月25日，星期天狀態(tài)概率其中第97頁,共131頁，2024年2月25日，星期天運行指標

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

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

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

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

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

例8

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

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

可見顧客等待時間太長，隊列也太長。主要原因是服務時間的方差太大！第109頁,共131頁，2024年2月25日，星期天例9

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

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

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

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

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

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

Wq=Lq/=0.27/4=0.0675小時=4分鐘第115頁,共131頁，2024年2月25日，星期天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第116頁,共131頁，2024年2月25日，星期天

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

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

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

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

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

5、如果列車因站中2股道均被占用而停在站外或前方站時，每列車每小時費用為a元，求每天由于列車在站外等待而造成的損失。第117頁,共131頁，2024年2月25日，星期天解：本例可看成一個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（小時）第118頁,共131頁，2024年2月25日，星期天5、記列車平均延誤（由于站內(nèi)2股道均被占用而不能進站）時間為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元第119頁,共131頁，2024年2月25日，星期天

練習3：

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

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

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

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

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

所以該科室至少應設20個座位如果該單位24小時上班，則每天平均有病人24×4=96人，病人看病所花去的總時間為96×1=96小時，因看病平均每天損失30×96=2880元，如果醫(yī)生每小時可診6個病人，，則LLWWsqsq====2430513()().()()人人小時小時第122頁,共131頁，2024年2月25日，星期天

這樣單位每天的損失費為96×0.5×30=1440元，因而單位每天平均可減少損失2880-1440=1440元，這時為保證99%以上的病人有座，應設座位數(shù)個比原來減少了9個。第123頁,共131頁，2024年2月25日，星期天練習4:某汽車加油站有兩臺加油泵為汽車加油，加油站內(nèi)最多能容納6輛汽車。已知顧客到達的時間間隔服從負指數(shù)分布，平均每小時到達18輛汽車。若加油站中已有K輛車，當K

2時，有K/6的顧客將自動離去。加油時間服從負指數(shù)分布，平均每輛車需要5分鐘。試求：非標準的M/M/2/N模型第124頁,共131頁，20