運籌學(xué)排隊論新詳解

運籌學(xué)排隊論新詳解演示文稿當(dāng)前1頁，總共126頁。優(yōu)選運籌學(xué)排隊論新當(dāng)前2頁，總共126頁。

排隊論(QueuingTheory)，又稱隨機服務(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)控制問題。特別是自二十世紀60年代以來，由于計算機的飛速發(fā)展，使排隊論的應(yīng)用有了更廣闊的前景。當(dāng)前3頁，總共126頁。WheretheTimeGoes?美國人一生中平均要花費--6年飲食5年排隊等待4年做家務(wù)2年回電話不成功1年尋找放置不當(dāng)?shù)奈锲?個月打開郵寄廣告6個月停在紅燈前當(dāng)前4頁，總共126頁。商業(yè)服務(wù)系統(tǒng)系統(tǒng)類型 顧客 服務(wù)臺理發(fā)店 人 理發(fā)師銀行出納服務(wù) 人 出納ATM機服務(wù) 人 ATM機商店收銀臺 人 收銀員管道服務(wù) 阻塞的管道 管道工電影院售票窗口 人 售票員機場檢票處 人 航空公司代理人經(jīng)紀人服務(wù) 人 股票經(jīng)紀人當(dāng)前5頁，總共126頁。運輸服務(wù)系統(tǒng)系統(tǒng)類型 顧客 服務(wù)臺公路收費站 汽車 收費員卡車裝貨地 卡車 裝貨工人港口卸貨區(qū) 輪船 卸貨工人等待起飛的飛機 飛機 跑道航班服務(wù) 人 飛機出租車服務(wù) 人 出租車電梯服務(wù) 人 電梯消防部門 火災(zāi) 消防車停車場 汽車 停車空間急救車服務(wù) 人 急救車當(dāng)前6頁，總共126頁。

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

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

①

有要求得到某種服務(wù)的人或物。排隊論里把要求服務(wù)的對象統(tǒng)稱為“顧客”②有提供服務(wù)的人或機構(gòu)。把提供服務(wù)的人或機構(gòu)稱為“服務(wù)臺”或“服務(wù)員”③顧客的到達、服務(wù)的時間至少有一個是隨機的，服從某種分布。當(dāng)前9頁，總共126頁。一般的排隊系統(tǒng)，都可由圖12-1加以描述。顧客源排隊結(jié)構(gòu)服務(wù)機構(gòu)排隊規(guī)則顧客到來服務(wù)規(guī)則離去圖12-1排隊系統(tǒng)當(dāng)前10頁，總共126頁。

排隊系統(tǒng)都有輸入過程、排隊規(guī)則和服務(wù)臺等3個組成部分：1、輸入過程這是指要求服務(wù)的顧客是按怎樣的規(guī)律到達排隊系統(tǒng)的過程，有時也把它稱為顧客流．一般可以從3個方面來描述輸入過程。排隊系統(tǒng)的組成當(dāng)前11頁，總共126頁。

(1)

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

顧客流的概率分布一般有定長分布、二項分布、泊松流(最簡單流)、愛爾朗分布等若干種。當(dāng)前13頁，總共126頁。2、排隊規(guī)則這是指服務(wù)臺從隊列中選取顧客進行服務(wù)的順序。損失制混合制隊長有限等待時間有限逗留時間有限排隊規(guī)則等待制先到先服務(wù)后到先服務(wù)隨機服務(wù)優(yōu)先權(quán)服務(wù)當(dāng)前14頁，總共126頁。3．服務(wù)臺情況。服務(wù)臺可以從3方面來描述：

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

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

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

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

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

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

PR：表示優(yōu)先權(quán)服務(wù)。當(dāng)前23頁，總共126頁。例如：某排隊問題為

M／M／S／∞／∞／FCFS

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

M/M/s

當(dāng)前24頁，總共126頁。

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

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

排隊長是指系統(tǒng)中正在排隊等待服務(wù)的顧客數(shù)。當(dāng)前26頁，總共126頁。2．等待時間和逗留時間

從顧客到達時刻起到他開始接受服務(wù)止這段時間稱為等待時間，是隨機變量。 從顧客到達時刻起到他接受服務(wù)完成止這段時間稱為逗留時間，也是隨機變量。當(dāng)前27頁，總共126頁。3．忙期和閑期

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

與忙期相對的是閑期，即服務(wù)機構(gòu)連續(xù)保持空閑的時間。在排隊系統(tǒng)中，忙期和閑期總是交替出現(xiàn)的。當(dāng)前28頁，總共126頁。

除了上述幾個基本數(shù)量指標(biāo)外，還會用到其他一些重要的指標(biāo)： 損失制或系統(tǒng)容量有限的情況下，由于顧客被拒絕，而使服務(wù)系統(tǒng)受到損失的顧客損失率及服務(wù)強度等，也都是十分重要的數(shù)量指標(biāo)。當(dāng)前29頁，總共126頁。

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到達系統(tǒng)的顧客在系統(tǒng)中的逗留時間；

Tq(t)：時刻t到達系統(tǒng)的顧客在系統(tǒng)中的等待時間。當(dāng)前30頁，總共126頁。

上面數(shù)量指標(biāo)一般都是和系統(tǒng)運行的時間有關(guān)的隨機變量，求它們的瞬時分布一般很困難。注意到相當(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ì)。當(dāng)前31頁，總共126頁。L或Ls—平均隊長 穩(wěn)態(tài)系統(tǒng)任一時刻的顧客數(shù)的期望值；Lq—平均等待隊長或隊列長 穩(wěn)態(tài)系統(tǒng)任一時刻等待服務(wù)的顧客數(shù)期望值；W或Ws—

平均逗留時間進入穩(wěn)態(tài)系統(tǒng)的顧客逗留時間期望值；Wq—平均等待時間 進入穩(wěn)態(tài)系統(tǒng)的顧客等待時間期望值。當(dāng)前32頁，總共126頁。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ù)臺全部空閑的概率。當(dāng)前33頁，總共126頁。(2)其他常用數(shù)量指標(biāo)s——系統(tǒng)中并聯(lián)服務(wù)臺的數(shù)目——平均到達率（單位時間內(nèi)到達的平均顧客數(shù)）1/——平均到達間隔——平均服務(wù)率（單位時間內(nèi)可以服務(wù)完的平均顧客數(shù)）1/——平均服務(wù)時間當(dāng)前34頁，總共126頁。

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

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

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

e

＝當(dāng)前35頁，總共126頁。第二節(jié)到達間隔的分布和服務(wù)時間的分布當(dāng)前36頁，總共126頁。

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

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

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

定理1說明如果顧客的到達為Poisson流的話，則到達顧客數(shù)的分布恰好為Poisson分布。當(dāng)前38頁，總共126頁。

二、負指數(shù)分布

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

設(shè)隨機變量T服從以為參數(shù)的負指數(shù)分布，它的分布函數(shù)為：當(dāng)前39頁，總共126頁。負指數(shù)分布的性質(zhì)：

性質(zhì)1

由條件概率公式容易證明

性質(zhì)2

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

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

當(dāng)前40頁，總共126頁。由性質(zhì)2可知：

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

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

當(dāng)前41頁，總共126頁。三、k階愛爾朗分布定理

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

S=v1+v2+…+vk服從k階Erlang分布，S的密度函數(shù)為當(dāng)前42頁，總共126頁。K=1時愛爾朗分布化歸為負指數(shù)分布，當(dāng)K→∞時，得到長度為1/的定長服務(wù)。m=1k=1k=2k=4k=8當(dāng)前43頁，總共126頁。第三節(jié)單服務(wù)臺負指數(shù)分布排隊系統(tǒng)的分析當(dāng)前44頁，總共126頁。標(biāo)準排隊模型[M/M/1]:[//FCFS]顧客到達的時間間隔是負指數(shù)分布，即輸入流是參數(shù)為的Poisson流服從參數(shù)為μ的負指數(shù)分布一個服務(wù)臺排隊系統(tǒng)的容量無限顧客源的容量無限實行先到先服務(wù)的一個服務(wù)系統(tǒng)當(dāng)前45頁，總共126頁。一、系統(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āng)前46頁，總共126頁。由于這四種方式互不相容，故由概率的加法定理得：該差分方程組為瞬態(tài)解，需求穩(wěn)態(tài)解。當(dāng)前47頁，總共126頁。[M/M/1]:[//FCFS]穩(wěn)態(tài)時狀態(tài)轉(zhuǎn)移圖λ012n-1nn+1穩(wěn)態(tài)情況下，系統(tǒng)狀態(tài)已不隨時間發(fā)生變化：當(dāng)前48頁，總共126頁。穩(wěn)態(tài)情況下，系統(tǒng)狀態(tài)已不隨時間發(fā)生變化：當(dāng)前49頁，總共126頁。得到

令稱為服務(wù)強度，則得當(dāng)前50頁，總共126頁。系統(tǒng)的過渡狀態(tài)與穩(wěn)定狀態(tài)過渡穩(wěn)定當(dāng)前51頁，總共126頁。二、系統(tǒng)的數(shù)量指標(biāo)1、服務(wù)臺空閑的概率和忙的概率：空閑的概率：P0=1-忙的概率：1-P0=2、系統(tǒng)中平均顧客數(shù)（隊長期望值Ls）：當(dāng)前52頁，總共126頁。3、系統(tǒng)中等待的平均顧客數(shù)（隊長期望值Lq）：4、系統(tǒng)中顧客逗留時間的期望值：當(dāng)前53頁，總共126頁。5、隊列中顧客逗留時間的期望值：現(xiàn)將以上公式歸納如下：它們相互關(guān)系如下：當(dāng)前54頁，總共126頁。Little公式

下列公式對任何服務(wù)系統(tǒng)均成立當(dāng)前55頁，總共126頁。例1

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

高速公路入口收費處設(shè)有一個收費通道，汽車到達服從Poisson分布，平均到達速率為200輛／小時，收費時間服從負指數(shù)分布，平均收費時間為15秒／輛。求Ls、Lq、Ws和Wq。當(dāng)前59頁，總共126頁。解：根據(jù)題意，=200輛/小時，=240輛/小時，=/=5/6。當(dāng)前60頁，總共126頁。有限隊列模型[M/M/1]:[N//FCFS]

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

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

設(shè)顧客總數(shù)為m。當(dāng)顧客需要服務(wù)時，就進入隊列等待；服務(wù)完畢后，重新回到顧客源中。如此循環(huán)往復(fù)。服務(wù)臺...顧客源需要服務(wù)服務(wù)完畢隊列當(dāng)前71頁，總共126頁。顧客源中剩余的顧客數(shù)

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

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

λe=λ(m-Ls)當(dāng)前72頁，總共126頁。狀態(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) 當(dāng)前73頁，總共126頁。運行指標(biāo)當(dāng)前74頁，總共126頁。(1)修理工空閑的概率；(2)五臺機器都出故障的概率；(3)出故障的平均臺數(shù)；(4)平均停工時間；(5)平均等待修理時間；(6)評價系統(tǒng)運行情況。例4

某車間有5臺機器，每臺機器的連續(xù)運轉(zhuǎn)時間服從負指數(shù)分布，平均連續(xù)運行時間15分鐘。有一個修理工，每次修理時間服從負指數(shù)分布，平均每次12分鐘。求:當(dāng)前75頁，總共126頁。解根據(jù)題意，m=5，λ=1/15，μ=1/12，ρ=λ/μ=0.8

當(dāng)前76頁，總共126頁。當(dāng)前77頁，總共126頁。第4節(jié)多服務(wù)臺負指數(shù)分布排隊系統(tǒng)的分析當(dāng)前78頁，總共126頁。多服務(wù)臺模型[M/M/c]標(biāo)準的[M/M/c]:[∞/∞/FCFS]模型系統(tǒng)容量有限的[M/M/c]:[N/∞/FCFS]模型有限顧客源的[M/M/c]:[∞/m/FCFS]模型當(dāng)前79頁，總共126頁。[M/M/c]:[∞/∞/FCFS]模型服務(wù)臺服務(wù)臺服務(wù)臺顧客到達顧客離去顧客離去顧客離去隊列

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

當(dāng)前80頁，總共126頁。

系統(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ù)強度服務(wù)機構(gòu)平均利用率當(dāng)前81頁，總共126頁。狀態(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當(dāng)前82頁，總共126頁。狀態(tài)概率當(dāng)前83頁，總共126頁。運行指標(biāo)當(dāng)前84頁，總共126頁。例5

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

當(dāng)前86頁，總共126頁。(3)平均等待時間和平均逗留時間，即求Wq和Ws和的值(4)顧客到達后必須等待，即n≥3當(dāng)前87頁，總共126頁。服務(wù)臺服務(wù)臺服務(wù)臺顧客到達顧客離去顧客離去顧客離去

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

這樣，原來的M/M/3系統(tǒng)就變成了3個M/M/1型的子系統(tǒng)。當(dāng)前88頁，總共126頁。 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（分鐘）當(dāng)前89頁，總共126頁。[M/M/c]:[N/∞/FCFS]模型離開服務(wù)臺服務(wù)臺服務(wù)臺顧客到達顧客離去顧客離去顧客離去隊列

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

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

λe=λ(m-Ls)當(dāng)前98頁，總共126頁。例7

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

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

若顧客需接受k個串行的服務(wù)臺的服務(wù)后才離開，且每個服務(wù)臺服務(wù)時間服從負指數(shù)分布，平均服務(wù)時間相等。 則總服務(wù)時間服從k階愛爾朗分布。當(dāng)前105頁，總共126頁。Erlang分布的均值和方差總服務(wù)時間服從愛爾朗分布：每個服務(wù)臺的平均服務(wù)時間是：當(dāng)前106頁，總共126頁。M/Ek/1系統(tǒng)的運行指標(biāo)當(dāng)前107頁，總共126頁。

例8

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

解：本例是M/G/1系統(tǒng)，且已知當(dāng)前108頁，總共126頁。

可見顧客等待時間太長，隊列也太長。主要原因是服務(wù)時間的方差太大！當(dāng)前109頁，總共126頁。例9

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

練習(xí)1：某修理店只有一位修理工，來修理的顧客到達過程為Poisson流，平均每小時4人；修理時間服從負指數(shù)分布，平均需要6分鐘。試求：修理店空閑的概率；店內(nèi)恰有3位顧客的概率；店內(nèi)至少有一位顧客的概率；在店內(nèi)平均顧客數(shù)；每位在店內(nèi)平均逗留時間；等待服務(wù)的平均顧客數(shù)；每位顧客平均等待服務(wù)時間；顧客在店內(nèi)逗留時間超過10分鐘的概率。當(dāng)前113頁，總共126頁。解：本例可看成一個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當(dāng)前114頁，總共126頁。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分鐘當(dāng)前115頁，總共126頁。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當(dāng)前116頁，總共126頁。

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

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

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

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

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

5、如果列車因站中2股道均被占用而停在站外或前方站時，每列車每小時費用為a元，求每天由于列車在站外等待而造成的損失。當(dāng)前117頁，總共126頁。解：本例可看成一個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（小時）當(dāng)前118頁，總共126頁。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元當(dāng)前119頁，總共126頁。

練習(xí)3：

(病人候診問題)某單