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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

11-7定長服務(wù)時間

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

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

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

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