數(shù)據(jù)、模型與決策（原書第16版）課件 第11章、排隊(duì)模型

AnIntroductiontoManagementScience,16e第十一章、排隊(duì)模型章節(jié)內(nèi)容11-1 排隊(duì)系統(tǒng)的結(jié)構(gòu)11-2 到達(dá)服從泊松分布、服務(wù)時(shí)間服從指數(shù)分布的單服務(wù)臺(tái)排隊(duì)模型11-3 到達(dá)服從泊松分布、服務(wù)時(shí)間服從指數(shù)分布的多服務(wù)臺(tái)排隊(duì)模型11-4 排隊(duì)模型中的一般關(guān)系11-5 排隊(duì)的經(jīng)濟(jì)性分析11-6 肯德爾排隊(duì)模型分類法11-7 到達(dá)服從泊松分布、服務(wù)時(shí)間為任意的單服務(wù)臺(tái)排隊(duì)模型11-8 到達(dá)服從泊松分布、服務(wù)時(shí)間任意且不排隊(duì)的多服務(wù)臺(tái)模型11-9 有限客源的排隊(duì)模型

本章小結(jié)章節(jié)目標(biāo)(1/2)完成本章后，你將能夠:LO11.1 使用泊松分布描述到達(dá)時(shí)間，使用指數(shù)分布描述服務(wù)時(shí)間LO11.2 計(jì)算泊松到達(dá)和指數(shù)服務(wù)時(shí)間的單服務(wù)臺(tái)排隊(duì)的穩(wěn)態(tài)運(yùn)行參數(shù)LO11.3 計(jì)算泊松到達(dá)和指數(shù)服務(wù)時(shí)間的多服務(wù)臺(tái)排隊(duì)的穩(wěn)態(tài)運(yùn)行參數(shù)LO11.4 用里特導(dǎo)出方程來描述任何排隊(duì)系統(tǒng)的運(yùn)行參數(shù)之間的關(guān)系章節(jié)目標(biāo)(2/2)LO11.5 使用排隊(duì)的經(jīng)濟(jì)性分析做出排隊(duì)系統(tǒng)決策LO11.6 計(jì)算泊松到達(dá)和一般服務(wù)時(shí)間的單服務(wù)臺(tái)排隊(duì)的穩(wěn)態(tài)運(yùn)行參數(shù).LO11.7 計(jì)算泊松到達(dá)、一般服務(wù)時(shí)間和無等待的多服務(wù)臺(tái)排隊(duì)的穩(wěn)態(tài)運(yùn)行參數(shù)

LO11.8 計(jì)算有限客源的泊松到達(dá)和指數(shù)服務(wù)時(shí)間的單服務(wù)臺(tái)排隊(duì)的穩(wěn)態(tài)運(yùn)行參數(shù)介紹回想一下上一次你不得不排隊(duì)的情形，比如在超市的收銀臺(tái)排隊(duì)、在銀行排隊(duì)、在快餐店排隊(duì)等。在類似上述需要排隊(duì)的情況下，把時(shí)間用于等待是令人非常不愉快的。然而增加更多的收銀員、銀行出納員或服務(wù)生并不總是改變服務(wù)水平的最經(jīng)濟(jì)的策略。因此，各行各業(yè)需要采取相應(yīng)的措施，把排隊(duì)時(shí)間控制在顧客所能容忍的限度內(nèi)。人們已經(jīng)設(shè)計(jì)建立了一些模型來幫助管理者理解等候線的運(yùn)作，并幫助管理者做出更好的決策。用管理科學(xué)的術(shù)語(yǔ)來講，等候線也稱排隊(duì)，與等候線相關(guān)的知識(shí)體系被稱為排隊(duì)論。排隊(duì)模型包括一些數(shù)學(xué)公式以及可用于確定排隊(duì)運(yùn)行參數(shù)(系統(tǒng)指標(biāo))的關(guān)系式。相關(guān)運(yùn)行參數(shù)如下：(1)系統(tǒng)中沒有顧客的概率(2)排隊(duì)的顧客平均數(shù)(3)系統(tǒng)中的顧客平均數(shù)(排隊(duì)的顧客數(shù)加上接受服務(wù)的顧客數(shù))(4)每位顧客排隊(duì)花費(fèi)的平均時(shí)間(5)每位顧客在系統(tǒng)中花費(fèi)的平均時(shí)間(排隊(duì)時(shí)間加上服務(wù)時(shí)間)(6)顧客到達(dá)以后不得不排隊(duì)以接受服務(wù)的概率11-1排隊(duì)系統(tǒng)的結(jié)構(gòu)伯格·度姆快餐店我們以伯格·度姆快餐店的等候線為例。伯格·度姆快餐店出售火腿漢堡、奶酪漢堡、法式油炸食品、軟飲料和奶昔，同時(shí)還有一些特色食品和甜點(diǎn)可供選擇。雖然伯格·度姆快餐店希望能為每位顧客提供即時(shí)的服務(wù)，但是很多時(shí)候，到達(dá)的顧客遠(yuǎn)遠(yuǎn)多于快餐店的服務(wù)人員所能接待的人數(shù)。因此，顧客不得不排隊(duì)等候點(diǎn)餐和取餐。伯格·度姆快餐店擔(dān)心它目前所用的顧客服務(wù)方式導(dǎo)致了過長(zhǎng)的排隊(duì)時(shí)間。管理層希望通過對(duì)等候線進(jìn)行研究，開發(fā)一個(gè)能夠減少排隊(duì)時(shí)間、提高服務(wù)質(zhì)量的最佳方式。單服務(wù)臺(tái)等候線在伯格·度姆快餐店目前所實(shí)行的運(yùn)作方式中，一名服務(wù)生為一位顧客點(diǎn)餐，計(jì)算總費(fèi)用，向顧客收取餐費(fèi)，然后上菜。為第一位顧客上菜之后，這名服務(wù)生就可以為下一位排隊(duì)的顧客服務(wù)。這種運(yùn)作方式就是一個(gè)單服務(wù)臺(tái)排隊(duì)模型的例子。11-1到達(dá)間隔分布

11-1服務(wù)時(shí)間分布

11-1排隊(duì)原則和穩(wěn)態(tài)運(yùn)行就伯格·度姆快餐店的排隊(duì)（推廣到一般來講，可以是所有面向顧客的排隊(duì)）來說，我們是以先到先服務(wù)的原則來安排等候服務(wù)的顧客的，這種方式被稱作“FCFS排隊(duì)原則”。然而，有些情況要求有不同的排隊(duì)原則：在乘坐飛機(jī)時(shí)，最后登機(jī)的顧客往往會(huì)最先下飛機(jī)，因?yàn)橛性S多航空公司都是讓座位在飛機(jī)后排的乘客先登機(jī)。醫(yī)院急診室不會(huì)采用前面所述的任何一種排隊(duì)原則，而是賦予等候個(gè)體優(yōu)先次序，然后為具有最高優(yōu)先權(quán)的顧客最先提供服務(wù)。在本章中，我們只討論采用先到先服務(wù)排隊(duì)原則的排隊(duì)。當(dāng)伯格·度姆快餐店早上開始營(yíng)業(yè)時(shí)，店里沒有顧客，每位顧客從到達(dá)到最終被服務(wù)的時(shí)間存在明顯差別，因而沒有一定的排隊(duì)原則。漸漸地，營(yíng)業(yè)開始正?；虺史€(wěn)定狀態(tài)。我們將開始或起始階段稱為過渡（瞬時(shí)）階段。當(dāng)系統(tǒng)正?；蚍€(wěn)態(tài)運(yùn)行時(shí)，過渡（瞬時(shí)）階段結(jié)束。排隊(duì)模型描述了排隊(duì)的穩(wěn)態(tài)運(yùn)行特征。11-2到達(dá)服從泊松分布、服務(wù)時(shí)間服從指數(shù)分布的單服務(wù)臺(tái)排隊(duì)模型

11-2伯格·度姆快餐店問題的運(yùn)行參數(shù)

伯格·度姆快餐店的單列服務(wù)臺(tái)排隊(duì)的計(jì)算結(jié)果給出了一些關(guān)于排隊(duì)運(yùn)作的重要信息：11-2伯格·度姆快餐店問題的結(jié)果和改進(jìn)管理者對(duì)排隊(duì)模型的應(yīng)用伯格·度姆快餐店的單列服務(wù)臺(tái)排隊(duì)的計(jì)算結(jié)果表明顧客在點(diǎn)餐前的平均等待時(shí)間為3分鐘，這對(duì)以快速服務(wù)為宗旨的行業(yè)來說，多少有些長(zhǎng)了點(diǎn)。此外，我們還注意到：等待中的顧客平均人數(shù)為2.25位。顧客不得不等待的概率為75%。有7個(gè)或更多顧客等待的概率為0.1335。這一數(shù)字表明，伯格·度姆快餐店的管理者應(yīng)當(dāng)考慮采取其他設(shè)計(jì)或計(jì)劃來改善單服務(wù)臺(tái)排隊(duì)運(yùn)作方式。改善排隊(duì)運(yùn)作伯格·度姆快餐店的管理者決定讓顧客在排隊(duì)的同時(shí)將自己的點(diǎn)餐單直接交給廚房，這樣等到顧客繳費(fèi)的時(shí)候就可以同時(shí)獲得自己的餐點(diǎn)。按照這一設(shè)計(jì)，伯格·度姆快餐店的管理者預(yù)測(cè)：改變后的系統(tǒng)的平均服務(wù)率提高到1.25（位顧客/分鐘）。顧客排隊(duì)等候所花費(fèi)的平均時(shí)間從3分鐘下降到了1.2分鐘。11-3到達(dá)服從泊松分布、服務(wù)時(shí)間服從指數(shù)分布的多服務(wù)臺(tái)排隊(duì)模型一個(gè)多服務(wù)臺(tái)排隊(duì)包括兩個(gè)或兩個(gè)以上服務(wù)臺(tái)，假設(shè)這些服務(wù)臺(tái)就服務(wù)能力而言是相同的。在多服務(wù)臺(tái)服務(wù)系統(tǒng)中存在兩種典型的情況：①顧客先是排在同一等候線里（也叫一個(gè)“集中”或“共享”隊(duì)列），等到自己接受服務(wù)的時(shí)候，就轉(zhuǎn)移到一個(gè)可以直接被服務(wù)的口那里去；②每個(gè)服務(wù)窗口有自己的隊(duì)列，新來的顧客選擇其中一個(gè)隊(duì)列排隊(duì)等候服務(wù)。在本章中，我們重點(diǎn)關(guān)注針對(duì)所有服務(wù)窗口的單個(gè)共享隊(duì)列的系統(tǒng)設(shè)計(jì)。本節(jié)中，我們將介紹確定多服務(wù)臺(tái)排隊(duì)穩(wěn)態(tài)運(yùn)行參數(shù)的公式。這些公式的應(yīng)用前提為下列條件成立：（1）到達(dá)服從泊松分布。（2）各個(gè)服務(wù)臺(tái)的服務(wù)時(shí)間服從指數(shù)分布。（3）各個(gè)服務(wù)臺(tái)的平均服務(wù)率μ相同。（4）到達(dá)者在單服務(wù)臺(tái)中排隊(duì)，然后移動(dòng)到最先空閑下來的服務(wù)臺(tái)接受服務(wù)。11-3運(yùn)行參數(shù)

11-3伯格·度姆快餐店問題的運(yùn)行參數(shù)

我們可以計(jì)算出系統(tǒng)中有n位顧客的概率：

11-3穩(wěn)態(tài)運(yùn)行參數(shù)現(xiàn)在，我們可以將雙服務(wù)臺(tái)系統(tǒng)的穩(wěn)態(tài)運(yùn)行參數(shù)與11.2節(jié)中所討論過的原始的單服務(wù)臺(tái)系統(tǒng)的運(yùn)行參數(shù)進(jìn)行對(duì)比：（1）一位顧客在系統(tǒng)中所花費(fèi)的平均時(shí)間（等候時(shí)間加上接受服務(wù)時(shí)間）從W=4分鐘減少到W=1.1636分鐘。（2）排隊(duì)顧客的平均數(shù)從Lq=2.25位減少到Lq=0.1227位。（3）一位顧客排隊(duì)所花費(fèi)的平均時(shí)間從Wq=3分鐘減少到Wq=0.1636分鐘。（4）某位剛到達(dá)的顧客必須等待的概率從Pw=0.75下降到Pw=0.2045。雙服務(wù)臺(tái)系統(tǒng)可以極大地改善排隊(duì)運(yùn)行參數(shù)。排隊(duì)研究展示了三種排隊(duì)結(jié)構(gòu)的運(yùn)行特征：原始的單服務(wù)臺(tái)系統(tǒng)、直接向廚房提交訂單的單服務(wù)臺(tái)系統(tǒng)和由兩個(gè)服務(wù)生處理訂單構(gòu)成的雙服務(wù)臺(tái)系統(tǒng)?？疾炝松鲜鼋Y(jié)果之后，伯格·度姆快餐店采用了下面的策略：在預(yù)計(jì)到達(dá)顧客為平均每小時(shí)45位的時(shí)間段內(nèi)，伯格·度姆快餐店將安排2個(gè)點(diǎn)餐臺(tái)，每個(gè)點(diǎn)餐臺(tái)有1個(gè)服務(wù)生。11-4排隊(duì)模型中的一般關(guān)系約翰·里特證明了下列4個(gè)參數(shù)之間存在幾種關(guān)系，并且這些關(guān)系適用于各種不同的排隊(duì)系統(tǒng)，無論到達(dá)是否服從泊松分布和服務(wù)時(shí)間是否服從指數(shù)概率分布。相關(guān)的運(yùn)行參數(shù)如下：Lq=排隊(duì)顧客的平均數(shù)L

=系統(tǒng)中顧客的平均數(shù)Wq=一位顧客排隊(duì)所花費(fèi)的平均時(shí)間W

=一位顧客在系統(tǒng)中所花費(fèi)的平均時(shí)間

11-5排隊(duì)的經(jīng)濟(jì)性分析經(jīng)理可能會(huì)做出決定：將系統(tǒng)中的平均等待時(shí)間控制在1分鐘或1分鐘以內(nèi)，并把等待服務(wù)的顧客的平均數(shù)控制在2位或2位以內(nèi)。利用前幾節(jié)中所討論的排隊(duì)模型，可以為實(shí)現(xiàn)該經(jīng)理的目標(biāo)確定服務(wù)臺(tái)的數(shù)量。此外，經(jīng)理可能還會(huì)希望計(jì)算出運(yùn)行排隊(duì)系統(tǒng)的成本，然后在每小時(shí)或每天的運(yùn)行成本最小化的條件下，決定如何設(shè)計(jì)系統(tǒng)。在進(jìn)行排隊(duì)的經(jīng)濟(jì)性分析之前，必須首先建立一個(gè)總成本模型，包括等候成本和服務(wù)成本。

11-5伯格·度姆快餐店問題的經(jīng)濟(jì)性分析

我們可以看出，服務(wù)成本隨著服務(wù)臺(tái)數(shù)的增加而提高；然而，更多的服務(wù)臺(tái)會(huì)帶來更好的服務(wù)，即等候時(shí)間及等候成本是隨著服務(wù)臺(tái)數(shù)量的增加而減少的。因此，我們可以通過對(duì)幾個(gè)設(shè)計(jì)方案進(jìn)行評(píng)估求得最佳的服務(wù)臺(tái)數(shù)量，使得其對(duì)應(yīng)的總成本接近于最低。11-6肯德爾排隊(duì)模型分類法D.G.肯德爾提出了一套符號(hào)，這套符號(hào)有助于對(duì)已有的許多不同的排隊(duì)模型進(jìn)行分類。肯德爾符號(hào)系統(tǒng)包含3個(gè)字母，具體形式如下：A/B/k其中：A=到達(dá)的概率分布B=服務(wù)時(shí)間的概率分布k=服務(wù)臺(tái)數(shù)根據(jù)在A或B的位置上出現(xiàn)的不同字母，可以描述出許多排隊(duì)系統(tǒng)。通常使用的標(biāo)記字母如下：M=到達(dá)服從泊松分布或服務(wù)時(shí)間服從指數(shù)分布D=到達(dá)或服務(wù)時(shí)間是確定的或持續(xù)不變的G=到達(dá)或服務(wù)時(shí)間服從某種已知均值和標(biāo)準(zhǔn)差的一般概率分布例如，利用肯德爾符號(hào)法，我們可以將：到達(dá)服從泊松分布、服務(wù)時(shí)間服從指數(shù)分布的單服務(wù)臺(tái)排隊(duì)模型可以劃為M/M/1模型。到達(dá)服從泊松分布、服務(wù)時(shí)間服從指數(shù)分布的雙服務(wù)臺(tái)排隊(duì)模型可以劃為M/M/2模型。11-7到達(dá)服從泊松分布、服務(wù)時(shí)間為任意的單服務(wù)臺(tái)排隊(duì)模型

11-7哈氏海貨供應(yīng)公司：M/G/1模型的示例

11-7定長(zhǎng)服務(wù)時(shí)間

11-8到達(dá)服從泊松分布、服務(wù)時(shí)間任意且不排隊(duì)的多服務(wù)臺(tái)模型本節(jié)要講的排隊(duì)系統(tǒng)中，當(dāng)系統(tǒng)滿載時(shí)，到達(dá)的個(gè)體受阻，并會(huì)離開系統(tǒng)。本節(jié)中所講到的這個(gè)特定模型是建立在下列假設(shè)基礎(chǔ)上的：（1）系統(tǒng)中有k個(gè)服務(wù)臺(tái)。（2）到達(dá)服從平均到達(dá)率為λ的泊松分布。（3）每個(gè)服務(wù)臺(tái)的服務(wù)時(shí)間可能服從某種概率分布。（4）每個(gè)服務(wù)臺(tái)的平均服務(wù)率μ是相同的。（5）當(dāng)至少有一個(gè)服務(wù)臺(tái)空閑時(shí)，到達(dá)者才會(huì)進(jìn)入系統(tǒng)。如果某個(gè)顧客在所有服務(wù)臺(tái)都繁忙時(shí)到達(dá)，則他會(huì)受到阻礙。在上述條件下的模型被稱為“即時(shí)制”M/G/K模型，其中，G表示服務(wù)時(shí)間服從一般或者某種不確定的分布。這種模型主要應(yīng)用在電話系統(tǒng)和其他通信系統(tǒng)的設(shè)計(jì)中。其中，到達(dá)者是打進(jìn)的電話，服務(wù)臺(tái)是可用的電話數(shù)或通信線路的數(shù)目。在這樣一個(gè)系統(tǒng)中，所有電話撥打的是同一個(gè)號(hào)碼。當(dāng)所有的服務(wù)臺(tái)都忙碌時(shí)，再打進(jìn)來的電話將接收到一個(gè)繁忙信號(hào)，并且不能進(jìn)入系統(tǒng)。在這種情況下，要解決的問題是:“應(yīng)該使用多少服務(wù)臺(tái)?”更重要的設(shè)計(jì)考慮因素包括確定服務(wù)臺(tái)數(shù)量如何影響受阻顧客的百分比。11-8即時(shí)制M/G/k模型的運(yùn)行參數(shù)

11-8微型資料軟件公司：無等待的M/G/k模型微型資料軟件公司利用一套電話訂貨系統(tǒng)來為其計(jì)算機(jī)軟件產(chǎn)品進(jìn)行相關(guān)服務(wù)。來電者可以通過撥打公司的800免費(fèi)電話向公司訂貨。假設(shè)撥打該號(hào)碼的來電以λ=12個(gè)電話/小時(shí)的平均頻率到達(dá)。處理一個(gè)電話訂貨所需要的時(shí)間因訂貨要求不同而有很大不同。然而，預(yù)計(jì)微型資料軟件公司的每個(gè)銷售代表平均每小時(shí)處理6個(gè)電話，即μ=6個(gè)電話/小時(shí)。目前，該公司的800免費(fèi)電話有3條內(nèi)線，每條內(nèi)線由一個(gè)銷售代表來操作。打進(jìn)的800免費(fèi)電話會(huì)自動(dòng)切換到一條空閑的內(nèi)線。當(dāng)3條內(nèi)線都繁忙時(shí)，來電者就會(huì)聽到一個(gè)表示系統(tǒng)繁忙的信號(hào)。過去，微型資料軟件公司的管理者曾假設(shè)，聽到忙音的來電者過些時(shí)候會(huì)再打過來。然而，最近對(duì)電話訂貨的一項(xiàng)研究表明，許多沒有打通電話的來電者并不一定會(huì)在稍后的時(shí)間再打一次。這些未打進(jìn)的電話說明公司會(huì)遭受到利潤(rùn)上的損失。因此公司的管理者提出要求，要對(duì)電話訂貨體系進(jìn)行分析。公司管理者最想知道的是聽到忙音并且受到阻礙無法進(jìn)入系統(tǒng)的來電者的比率。如果管理者的目的是讓此系統(tǒng)的能力達(dá)到能夠處理90%的來電者，那么，公司應(yīng)該有多少條電話線、多少名銷售代表？11-8微型資料軟件公司的解決方案

11-9有限客源的排隊(duì)模型當(dāng)對(duì)要求服務(wù)的顧客數(shù)量不加限制時(shí)，我們稱該模型為無限客源模型。在這種假設(shè)下，不管有多少顧客排隊(duì)，平均到達(dá)率λ均保持不變。大多數(shù)排隊(duì)模型都假設(shè)有無限客源。然而在有些時(shí)候，需要假設(shè)服務(wù)的個(gè)體或顧客的最高人數(shù)是限定的。此時(shí)，系統(tǒng)的平均到達(dá)率是變化的，并且取決于排隊(duì)顧客的數(shù)量，我們稱這種模型為有限客源模型。為了說明有限客源造成的影響，我們需要對(duì)前面講到的排隊(duì)模型的運(yùn)行參數(shù)的計(jì)算公式進(jìn)行修改。本節(jié)中所討論的有限客源模型基于以下假設(shè)：1.每位顧客的到達(dá)服從平均到達(dá)率為λ的泊松分布。2.服務(wù)時(shí)間服從平均服務(wù)率為μ的指數(shù)分布。3.有服務(wù)要求的顧客的人數(shù)是有限的。在前面所講的排隊(duì)模型中，λ是系統(tǒng)的平均到達(dá)率。在有限客源的情況下，系統(tǒng)的平均到達(dá)率因系統(tǒng)中顧客的數(shù)量不同而有所差別。對(duì)于每位顧客，我們假設(shè)服務(wù)完成后需要再服務(wù)的時(shí)間間隔平均為1/λ。11-9有限客源的M/M/1模型的運(yùn)行參數(shù)

11-9可可美制造公司：機(jī)器維修問題在機(jī)器維修問題中，我們將一組機(jī)器看作有限客源的“顧客”，它們要求維修服務(wù)。當(dāng)一臺(tái)機(jī)器出現(xiàn)故障時(shí)，就會(huì)要求一次新的維修，在這里就是指出現(xiàn)了新的到達(dá)者。如果第一臺(tái)機(jī)器的維修尚未完成，又有一臺(tái)機(jī)器出現(xiàn)故障，那么從第二臺(tái)機(jī)器開始形成一條排隊(duì)接受維修服務(wù)的“等候線”。如果更多機(jī)器出現(xiàn)故障，排隊(duì)的長(zhǎng)度會(huì)加長(zhǎng)。先到先服務(wù)的假設(shè)說明，這組機(jī)器按照它們出現(xiàn)故障的先后順序接受維修。M/M/1表明只有一人或一個(gè)服務(wù)臺(tái)可以提供維修服務(wù)。也就是說，為了使機(jī)器恢復(fù)正常運(yùn)轉(zhuǎn)，必須以單服務(wù)臺(tái)的運(yùn)作方式來維修出現(xiàn)故障的每臺(tái)機(jī)器。可可美制造公司有一組6臺(tái)相同的機(jī)器。每臺(tái)機(jī)器在維修后到再次遇到故障之前，平均運(yùn)轉(zhuǎn)20個(gè)小時(shí)。因此，每臺(tái)機(jī)器的平均到達(dá)率（或稱每臺(tái)機(jī)器的維修服務(wù)要求次數(shù)）是λ=1/20=0.05/小時(shí)。在機(jī)器隨時(shí)會(huì)發(fā)生故障的情況下，我們可以