運籌學課件排隊論

1、第十四章 排隊論Queuing Theory,基本概念（掌握） 輸入過程和服務時間分布（掌握） 泊松到達、負指數(shù)服務排隊模型（掌握） 其他模型（了解） 排隊系統(tǒng)的優(yōu)化目標與最優(yōu)化問題（了解）,本章內(nèi)容重點,排隊是我們?nèi)粘Ｉ詈蜕a(chǎn)中經(jīng)常遇到的現(xiàn)象。例如，上、下班搭乘公共汽車；顧客到商店購買物品；病員到醫(yī)院看?。宦每偷绞燮碧庂徺I車票；學生去食堂就餐等就常常出現(xiàn)排隊和等待現(xiàn)象。除了上述有形的排隊之外，還有大量的所謂“無形”排隊現(xiàn)象，如幾個顧客打電話到出租汽車站要求派車，如果出租汽車站無足夠車輛、則部分顧客只得在各自的要車處等待，他們分散在不同地方，卻形成了一個無形隊列在等待派車。排隊的不一定是人，

2、也可以是物：,前 言,例如，通訊衛(wèi)星與地面若干待傳遞的信息；生產(chǎn)線上的原料、半成品等待加工；因故障停止運轉的機器等待工人修理；碼頭的船只等待裝卸貨物；要降落的飛機因跑道不空而在空中盤旋等等。,前 言,面對擁擠現(xiàn)象，人們總是希望盡量設法減少排隊，通常的做法是增加服務設施。但是增加的數(shù)量越多，人力、物力的支出就越大，甚至會出現(xiàn)空閑浪費，如果服務設施太少，顧客排隊等待的時間就會很長，這樣對顧客會帶來不良影響。,前 言,于是，顧客排隊時間的長短與服務設施規(guī)模的大小，就構成了隨機服務系統(tǒng)中的一對矛盾。如何做到既保證一定的服務質量指標，又使服務設施費用經(jīng)濟合理，恰當?shù)亟鉀Q顧客排隊時間與服務設施費用大小這對

3、矛盾，這就是隨機服務系統(tǒng)理論排隊論所要研究解決的問題。,排隊論是1909年由丹麥工程師愛爾朗(A.KErlang)在研究電活系統(tǒng)時創(chuàng)立的，幾十年來排隊論的應用領域越來越廣泛，理論也日漸完善。特別是自二十世紀60年代以來，由于計算機的飛速發(fā)展，更為排隊論的應用開拓了寬闊的前景。,前 言,排隊論(Queuing Theory)，又稱隨機服務系統(tǒng)理論(Random Service System Theory),是一門研究擁擠現(xiàn)象(排隊、等待)的科學。具體地說，它是在研究各種排隊系統(tǒng)概率規(guī)律性的基礎上，解決相應排隊系統(tǒng)的最優(yōu)設計和最優(yōu)控制問題。,前 言,顯然，上述各種問題雖互不相同，但卻都有要求得到某

4、種服務的人或物和提供服務的人或機構。排隊論里把要求服務的對象統(tǒng)稱為“顧客”,而把提供服務的人或機構稱為“服務臺”或“服務員”。不同的顧客與服務組成了各式各樣的服務系統(tǒng)。,前 言,圖1 單服務臺排隊系統(tǒng),前 言,顧客為了得到某種服務而到達系統(tǒng)、若不能立即獲得服務而又允許排隊等待，則加入等待隊伍，待獲得服務后離開系統(tǒng)，見圖1至圖5。,圖2 單隊列S個服務臺并聯(lián)的排隊系統(tǒng),圖3 S個隊列S個服務臺的并聯(lián)排隊系統(tǒng),前 言,圖4 單隊多個服務臺的串聯(lián)排隊系統(tǒng),圖5 多隊多服務臺混聯(lián)、網(wǎng)絡系統(tǒng),前 言,圖6-6 隨機服務系統(tǒng),前 言,一般的排隊系統(tǒng)，都可由下面圖6加以描述。,通常稱由圖6表示的系統(tǒng)為一隨機

5、聚散服務系統(tǒng)，任一排隊系統(tǒng)都是一個隨機聚散服務系統(tǒng)。這里，“聚”表示顧客的到達，“散”表示顧客的離去。所謂隨機性則是排隊系統(tǒng)的一個普遍特點，是指顧客的到達情況(如相繼到達時間間隔)與每個顧客接受服務的時間往往是事先無法確切知道的，或者說是隨機的）。 一般來說，排隊論所研究的排隊系統(tǒng)中，顧客到來的時刻和服務臺提供服務的時間長短都是隨機的，因此這樣的服務系統(tǒng)被稱為隨機服務系統(tǒng)。,前 言,1.基 本 概 念,一 排隊系統(tǒng)的描述 （一）系統(tǒng)特征和基本排隊過程 實際的排隊系統(tǒng)雖然千差萬別，但是它們 有以下的共同特征： (1)有請求服務的人或物顧客； (2)有為顧客服務的人或物，即服務員或服務臺；,(3)

6、顧客到達系統(tǒng)的時刻是隨機的，為每一位顧客提供服務的時間是隨機的，因而整個排隊系統(tǒng)的狀態(tài)也是隨機的。排隊系統(tǒng)的這種隨機性造成某個階段顧客排隊較長，而另外一些時候服務員(臺)又空閑無事。,任何一個排隊問題的基本排隊過程都可以用圖6表示。從圖6可知，每個顧客由顧客源按一定方式到達服務系統(tǒng)，首先加入隊列排隊等待接受服務，然后服務臺按一定規(guī)則從隊列中選擇顧客進行服務，獲得服務的顧客立即離開。,1.基 本 概 念,（二）排隊系統(tǒng)的基本組成部分 通常，排隊系統(tǒng)都有輸入過程、服務規(guī)則和服務臺等3個組成部分： 1輸入過程這是指要求服務的顧客是按怎樣的規(guī)律到達排隊系統(tǒng)的過程，有時也把它稱為顧客流一般可以從3個方面

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

8、、2、)的概率是多大。顧客流的概率分布一般有定長分布、二項分布、泊松流(最簡單流)、愛爾朗分布等若干種。,2.服務規(guī)則。這是指服務臺從隊列中選取顧客進行服務的順序。一般可以分為損失制、等待制和混合制等3大類。 (1)損失制。這是指如果顧客到達排隊系統(tǒng)時，所有服務臺都已被先來的顧客占用，那么他們就自動離開系統(tǒng)永不再來。典型例子是，如電話拔號后出現(xiàn)忙音，顧客不愿等待而自動掛斷電話，如要再打，就需重新拔號，這種服務規(guī)則即為損失制。,1.基 本 概 念,(2)等待制。這是指當顧客來到系統(tǒng)時，所有服務臺都不空，顧客加入排隊行列等待服務。例如，排隊等待售票，故障設備等待維修等。等待制中，服務臺在選擇顧客進

9、行服務時，常有如下四種規(guī)則： 先到先服務。按顧客到達的先后順序對顧客進行服務，這是最普遍的情形。 后到先服務。倉庫中迭放的鋼材，后迭放上去的都先被領走，就屬于這種情況。,1.基 本 概 念,隨機服務。即當服務臺空閑時，不按照排隊序列而隨意指定某個顧客去接受服務，如電話交換臺接通呼叫電話就是一例。 優(yōu)先權服務。如老人、兒童先進車站；危重病員先就診；遇到重要數(shù)據(jù)需要處理計算機立即中斷其他數(shù)據(jù)的處理等，均屬于此種服務規(guī)則。,1.基 本 概 念,(3)混合制這是等待制與損失制相結合的一種服務規(guī)則，一般是指允許排隊，但又不允許隊列無限長下去。具體說來，大致有三種： 隊長有限。當排隊等待服務的顧客人數(shù)超過

10、規(guī)定數(shù)量時，后來的顧客就自動離去，另求服務，即系統(tǒng)的等待空間是有限的。例如最多只能容納K個顧客在系統(tǒng)中，當新顧客到達時，若系統(tǒng)中的顧客數(shù)(又稱為隊長)小于K，則可進入系統(tǒng)排隊或接受服務；否則，便離開系統(tǒng)，并不再回來。如水庫的庫容是有限的，旅館的床位是有限的。,1.基 本 概 念, 等待時間有限。即顧客在系統(tǒng)中的等待時間不超過某一給定的長度T，當?shù)却龝r間超過T時，顧客將自動離去，并不再回來。如易損壞的電子元器件的庫存問題，超過一定存儲時間的元器件被自動認為失效。又如顧客到飯館就餐，等了一定時間后不愿再等而自動離去另找飯店用餐。,1.基 本 概 念, 逗留時間(等待時間與服務時間之和)有限。例如用

11、高射炮射擊敵機，當敵機飛越高射炮射擊有效區(qū)域的時間為t時，若在這個時間內(nèi)未被擊落，也就不可能再被擊落了。 不難注意到，損失制和等待制可看成是混合制的特殊情形，如記s為系統(tǒng)中服務臺的個數(shù)，則當K=s時，混合制即成為損失制；當K=時，混合制即成為等待制。,1.基 本 概 念,3服務臺情況。服務臺可以從以下3方面來描述： (1) 服務臺數(shù)量及構成形式。從數(shù)量上說，服務臺有單服務臺和多服務臺之分。從構成形式上看，服務臺有： 單隊單服務臺式； 單隊多服務臺并聯(lián)式； 多隊多服務臺并聯(lián)式； 單隊多服務臺串聯(lián)式； 單隊多服務臺并串聯(lián)混合式,以及 多隊多服務臺并串聯(lián)混合式等等。 見前面圖1至圖5所示。,1.基

12、本 概 念,(2) 服務方式。這是指在某一時刻接受服務的顧客數(shù)，它有單個服務和成批服務兩種。如公共汽車一次就可裝載一批乘客就屬于成批服務。 (3) 服務時間的分布。一般來說，在多數(shù)情況下，對每一個顧客的服務時間是一隨機變量，其概率分布有定長分布、負指數(shù)分布、K級愛爾良分布、一般分布(所有顧客的服務時間都是獨立同分布的)等等。,1.基 本 概 念,（三）排隊系統(tǒng)的描述符號與分類 為了區(qū)別各種排隊系統(tǒng)，根據(jù)輸入過程、排隊規(guī)則和服務機制的變化對排隊模型進行描述或分類，可給出很多排隊模型。為了方便對眾多模型的描述，肯道爾（DGKendall）提出了一種目前在排隊論中被廣泛采用的“Kendall記號”，

13、完整的表達方式通常用到6個符號并取如下固定格式： A/B/C/D/E/F 各符號的意義為：,1.基 本 概 念,A表示顧客相繼到達間隔時間分布，常用下列符號： M表示到達過程為泊松過程或負指數(shù)分布； D表示定長輸入； Ek表示k階愛爾朗分布； G表示一般相互獨立的隨機分布。 B表示服務時間分布，所用符號與表示顧客到達間隔時間分布相同。 M表示服務過程為泊松過程或負指數(shù)分布； D表示定長分布； Ek 表示k階愛爾朗分布； G表示一般相互獨立的隨機分布。,1.基 本 概 念,C表示服務臺(員)個數(shù)：“1”則表示單個服務臺，“s”。(s1)表示多個服務臺。 D表示系統(tǒng)中顧客容量限額，或稱等待空間容量

14、；如系統(tǒng)有K個等待位子，則 0K，當 K=0 時，說明系統(tǒng)不允許等待，即為損失制。K= 時為等待制系統(tǒng)，此時般省略不寫。K為有限整數(shù)時，表示為混合制系統(tǒng)。 E表示顧客源限額，分有限與無限兩種，表示顧客源無限，此時一般也可省略不寫。,1.基 本 概 念,F表示服務規(guī)則，常用下列符號： FCFS：表示先到先服務的排隊規(guī)則； LCFS：表示后到先服務的排隊規(guī)則； PR：表示優(yōu)先權服務的排隊規(guī)則。 例如：某排隊問題為MMSFCFS，則表示顧客到達間隔時間為負指數(shù)分布(泊松流)；服務時間為負指數(shù)分布；有s(s1)個服務臺；系統(tǒng)等待空間容量無限(等待制)；顧客源無限，采用先到先服務規(guī)則。 某些情況下，排隊

15、問題僅用上述表達形式中的前3個、4個、5個符號。如不特別說明則均理解為系統(tǒng)等待空間容量無限；顧客源無限，先到先服務，單個服務的等待制系統(tǒng)。,1.基 本 概 念,二、排隊系統(tǒng)的主要數(shù)量指標 研究排隊系統(tǒng)的目的是通過了解系統(tǒng)運行的狀況，對系統(tǒng)進行調(diào)整和控制，使系統(tǒng)處于最優(yōu)運行狀態(tài)。因此，首先需要弄清系統(tǒng)的運行狀況。描述一個排隊系統(tǒng)運行狀況的主要數(shù)量指標有：,1.基 本 概 念,1.隊長和排隊長（隊列長） 隊長是指系統(tǒng)中的平均顧客數(shù)(排隊等待的顧客數(shù)與正在接受服務的顧客數(shù)之和)， 排隊長是指系統(tǒng)中正在排隊等待服務的平均顧客數(shù)。 隊長和排隊長一般都是隨機變量。我們希望能確定它們的分布，或至少能確定它們

16、的平均值(即平均隊長和平均排隊長)及有關的矩(如方差等)。隊長的分布是顧客和服務員都關心的，特別是對系統(tǒng)設計人員來說，如果能知道隊長的分布，就能確定隊長超過某個數(shù)的概率，從而確定合理的等待空間。,1.基 本 概 念,2等待時間和逗留時間 從顧客到達時刻起到他開始接受服務止這段時間稱為等待時間，是隨機變量，也是顧客最關心的指標，因為顧客通常希望等待時間越短越好。 從顧客到達時刻起到他接受服務完成止這段時間稱為逗留時間，也是隨機變量，同樣為顧客非常關心。對這兩個指標的研究當然是希望能確定它們的分布，或至少能知道顧客的平均等待時間和平均逗留時間。,1.基 本 概 念,3忙期和閑期 忙期是指從顧客到達

17、空閑著的服務機構起，到服務機構再次成為空閑止的這段時間，即服務機構連續(xù)忙的時間。這是個隨機變量，是服務員最為關心的指標，因為它關系到服務員的服務強度。與忙期相對的是閑期，即服務機構連續(xù)保持空閑的時間。在排隊系統(tǒng)中，忙期和閑期總是交替出現(xiàn)的。,1.基 本 概 念,除了上述幾個基本數(shù)量指標外，還會用到其他一些重要的指標，如在損失制或系統(tǒng)容量有限的情況下，由于顧客被拒絕，而使服務系統(tǒng)受到損失的顧客損失率及服務強度等，也都是十分重要的數(shù)量指標。,4.一些數(shù)量指標的常用記號 (1)主要數(shù)量指標 N(t)：時刻t系統(tǒng)中的顧客數(shù)(又稱為系統(tǒng)的狀態(tài))，即隊長； Nq(t)：時刻t系統(tǒng)中排隊的顧客數(shù)，即排隊長；

18、 T(t)：時刻t到達系統(tǒng)的顧客在系統(tǒng)中的逗留時間； Tq(t)：時刻t到達系統(tǒng)的顧客在系統(tǒng)中的等待時間。,1.基 本 概 念,上面給出的這些數(shù)量指標一般都是和系統(tǒng)運行的時間有關的隨機變量，求這些隨機變量的瞬時分布一般是很困難的。為了分析上的簡便，并注意到相當一部分排隊系統(tǒng)在運行了一定時間后，都會趨于一個平衡狀態(tài)(或稱平穩(wěn)狀態(tài))。在平衡狀態(tài)下，隊長的分布、等待時間的分布和忙期的分布都和系統(tǒng)所處的時刻無關，而且系統(tǒng)的初始狀態(tài)的影響也會消失。因此，我們在本章中將主要討論與系統(tǒng)所處時刻無關的性質，即統(tǒng)計平衡性質。,1.基 本 概 念,L或Ls 平均隊長，即穩(wěn)態(tài)系統(tǒng)任一時刻的所有顧客數(shù)的期望值； Lq

19、 平均等待隊長或隊列長，即穩(wěn)態(tài)系統(tǒng)任一時刻的等待服務的顧客數(shù)的期望值； W或Ws 平均逗留時間，即(在任意時刻)進入穩(wěn)態(tài)系統(tǒng)的顧客逗留時間的期望值； Wq 平均等待時間，即(在任意時刻)進入穩(wěn)態(tài)系統(tǒng)的顧客等待時間的期望值。 這四項主要性能指標(又稱主要工作指標)的值越小，說明系統(tǒng)排隊越少，等待時間越少，因而系統(tǒng)性能越好。顯然，它們是顧客與服務系統(tǒng)的管理者都很關注的。,1.基 本 概 念,ABCDE 其中 A顧客到達的概率分布，可取M、D、G 、Ek 等； B服務時間的概率分布，可取M、D、G 、Ek 等； C服務臺個數(shù)，取正整數(shù)； D排隊系統(tǒng)的最大容量，可取正整數(shù)或 ； E顧客源的最大容量，可

20、取正整數(shù)或 。 例如 M / M / 1 / / 表示顧客到達過程服從泊松分布，服務時間服從負指數(shù)分布，一個服務臺，排隊的長度無限制和顧客的來源無限制。,2單服務臺泊松到達、負指數(shù)服務時間的排隊模型,M / M / 1 / / 設單位時間顧客平均到達數(shù)為 ，單位時間平均服務的顧客數(shù)為 ( )，則這個排隊系統(tǒng)的數(shù)量指標公式為: 1、系統(tǒng)中無顧客的概率 P0 =1 / 2、平均排隊的顧客數(shù) Lq =2/ ( ) 3、系統(tǒng)中的平均顧客數(shù) Ls = Lq + / 4、顧客花在排隊上的平均等待時間 Wq = Lq /,5、顧客在系統(tǒng)中的平均逗留時間 Ws = Wq+ 1/ 6、顧客得不到及時服務必須排隊

21、等待的概率 Pw = / 7、系統(tǒng)中恰好有 n 個顧客的概率 Pn = ( /)n P0,例某儲蓄所只有一個服務窗口。根據(jù)統(tǒng)計分析，顧客的到達過程服從泊松分布，平均每小時到達顧客 36人；儲蓄所的服務時間服從負指數(shù)分布，平均每小時能處理 48 位顧客的業(yè)務。試求這個排隊系統(tǒng)的數(shù)量指標。,解： 已知平均到達率 = 36/60 = 0.6， 平均服務率 = 48/60 = 0.8。 P0 =1 / = 10.6/0.8 = 0.25, Lq =2/ ( ) = (0.6)2 / 0.8(0.8 0.6) =2.25 (個顧客), Ls = Lq + / = 2.25+ 0.6/0.8 =3 (個顧

22、客), Wq = Lq / = 2.25/0.6 = 3.75 （分鐘）, Ws = Wq+ 1/ = 3.75+1/0.8 =5 （分鐘）, Pw = / = 0.6/0.8 = 0.75, Pn =( /)n P0 = (0.75)n 0.25, n =1, 2, 。,從以上的數(shù)據(jù)，我們知道儲蓄所這個排隊系統(tǒng)并不盡人意，到達儲蓄所有 75 的概率要排隊，排隊的長度平均為 2.25 人，排隊的平均時間為 3.75 分鐘，是平均服務時間 1.25 的 3 倍，而且在儲蓄所里有7 個或更多的顧客的概率為 13.35，這個概率太高了。 要提高服務水平，減少顧客在系統(tǒng)里的平均逗留時間，即減少顧客的平

23、均排隊時間和平均服務時間，一般可采用兩種措施：第一，減少服務時間，提高服務率；第二，增加服務臺即增加服務窗口。,如采取第一種方法，縮短平均服務時間，每小時服務的顧客數(shù)由原來的 48人提高到 60人，即每分鐘平均服務的顧客數(shù)從 0.8 人提高到 1 人，這時 仍然是 0.6， 為 1。用前面公式計算得到下表數(shù)據(jù)：,如采用第二種方法，再開設一個服務窗口，排隊的規(guī)則為每個窗口排一隊，先到先服務，并假設顧客一旦排了一個隊，就不能換到另一個隊去。這種處理方法把一個排隊系統(tǒng)分成兩個排隊系統(tǒng)，每個系統(tǒng)中有一個服務臺，每個系統(tǒng)的服務率仍然為 0.8，但到達率由于分流，只有原來的一半， 0.3，這時我們可以求得

24、：,如果在第二種方法中把排隊規(guī)則變一下，在儲蓄所里只排一個隊，這樣的排隊系統(tǒng)就變成了 M /M / 2 排隊系統(tǒng)。,3 多服務臺泊松到達、負指數(shù)服務時間的排隊模型,這種排隊模型我們記為 M / M / c / / ，這與第二節(jié)單服務臺的模型的差別，就在于服務臺的數(shù)量為 c，我們可以把這個模型簡記為 M / M / c。 在 M / M / c 模型里，其到達過程為泊松流，每個服務臺的服務時間分布為同樣的負指數(shù)分布，排隊的長度與顧客的來源都無限制，其排隊規(guī)則為只排一個隊，先到先服務，當其中一個服務臺有空時，排在第一個的顧客就上去接受服務。,M / M / c / / 單位時間顧客平均到達數(shù) ，單

25、位平均服務顧客數(shù) , 1、系統(tǒng)中無顧客的概率 2、平均排隊的顧客數(shù) 3、系統(tǒng)中的平均顧客數(shù) Ls = Lq + / ,4、顧客花在排隊上的平均等待時間 Wq = Lq / , 5、顧客在系統(tǒng)中的平均逗留時間 Ws = Wq+ 1/ , 6、系統(tǒng)中顧客必須排隊等待的概率 7、系統(tǒng)中恰好有 n 個顧客的概率,當 n c 時，,當 n c 時。,例 在前例的儲蓄所里多設一個服務窗口，即儲蓄所開設兩個服務窗口。顧客的到達過程仍服從泊松分布，平均每小時到達顧客仍是 36 人；儲蓄所的服務時間仍服從負指數(shù)分布，平均每小時仍能處理 48 位顧客的業(yè)務，其排隊規(guī)則為只排一個隊，先到先服務。試求這個排隊系統(tǒng)的數(shù)

26、量指標。 解： c = 2， 平均到達率 = 36/60 = 0.6， 平均服務率 = 48/60 = 0.8。,P0 =0.4545, Lq = 0.1227 (個顧客), Ls = Lq + / = 0.8727 (個顧客), Wq = Lq / = 0.2045（分鐘）, Ws = Wq+ 1/ = 1.4545 （分鐘）, Pw = 0.2045, P1 = 0.3409, P2 = 0.1278, P3 = 0.0479, P4 = 0.0180, P5 = 0.0067， P6 = 0.0040。,在儲蓄所里使用 M / M / 2 模型與使用兩個 M / M / 1 模型，它們的

27、服務臺數(shù)都是 2，服務率和顧客到達率都一樣，只是在 M / M / 2 中只排一隊，在 2 個 M / M / 1 中排兩隊，結果卻不一樣。 M / M / 2 使得服務水平有了很大提高。如果把 M / M / 2 與原來的一個 M / M / 1比較，那么服務水平之間的差別就更大了。,值得注意，在任何排隊模型中 Ls ， Lq， Ws，Wq 之間都有如下關系： LsLq / ， WqLq / ， Ws = Wq+ 1/ 。,4 排隊系統(tǒng)的經(jīng)濟分析,我們把一個排隊系統(tǒng)的單位時間的總費用 TC 定義為服務機構的單位時間的費用和顧客在排隊系統(tǒng)中逗留單位時間的費用之和。即 TC = cw Ls +

28、cs c 其中 cw 為一個顧客在排隊系統(tǒng)中逗留單位時間付出的費用；Ls 為在排隊系統(tǒng)中的平均顧客數(shù)；cs 為每個服務臺單位時間的費用；c 為服務臺的數(shù)目。,例 在前兩例中，設儲蓄所的每個服務臺的費用cs = 18，顧客在儲蓄所中逗留一小時的成本 cw =10。這樣，對儲蓄所 M / M / 1 模型可知 Ls = 3， c = 1，得 TC = cw Ls + cs c = 48 元 / 每小時。 對儲蓄所 M / M / 2 模型可知 Ls = 0.8727， c = 2， 得 TC = cw Ls + cs c = 44.73 元 / 每小時。 通過經(jīng)濟分析可知 M / M / 2 系統(tǒng)

29、是一個更為經(jīng)濟的模型。,5 單服務臺泊松到達、任意服務時間的排隊模型,M / G / 1 / / 單位時間顧客平均到達數(shù) ，單位平均服務顧客數(shù) ，一個顧客的平均服務時間 1 /，服務時間的均方差 。數(shù)量指標公式: 1、系統(tǒng)中無顧客的概率 P0=1 / 2、平均排隊的顧客數(shù) 3、系統(tǒng)中的平均顧客數(shù) Ls = Lq + /,4、顧客花在排隊上的平均等待時間 Wq = Lq / 5、系統(tǒng)在中顧客的平均逗留時間 Ws = Wq+ 1/ 6、系統(tǒng)中顧客必須排隊等待的概率 Pw = / 7、系統(tǒng)中恰好有 n 個顧客的概率 Pn 例1. 某雜貨店只有一名售貨員，已知顧客的到達過程服從泊松分布，平均到達率為每

30、小時 20 人；不清楚這個系統(tǒng)的服務時間服從什么分布，但從統(tǒng)計分析知道售貨員平均服務一名顧客的時間為 2 分鐘，服務時間的均方差為 1.5 分鐘。試求這個排隊系統(tǒng)的數(shù)量指標。,解：這是一個 M / G / 1 的排隊系統(tǒng)，其中 = 20/60 = 0.3333 人/分鐘，1/ = 2分鐘， = = 0.5 人/分鐘， =1.5。 P0 =1 / = 0.33334, Lq =1.0412 (人), Ls = Lq + / = 1. 7078 (人), Wq = Lq / = 2.25/0.6 = 3.1241（分鐘）, Ws = Wq+ 1/ =5.1241（分鐘）, Pw = / = 0.6

31、666。,6 單服務臺泊松到達、定長服務時間的排隊模型,M / D / 1 / / 注：它是 M / G / 1 / / 的特殊情況 = 0。 1、系統(tǒng)中無顧客的概率 P0=1 / 2、平均排隊的顧客數(shù) 3、系統(tǒng)中的平均顧客數(shù) Ls = Lq + / 4、顧客花在排隊上的平均等待時間 Wq = Lq / ,5、系統(tǒng)在中顧客的平均逗留時間 Ws = Wq+ 1/ 6、系統(tǒng)中顧客必須排隊等待的概率 Pw = / 7、系統(tǒng)中恰好有 n 個顧客的概率 Pn 例2 . 某汽車沖洗服務營業(yè)部，有一套自動沖洗設備，沖洗每輛車需要 6 分鐘，到此營業(yè)部來沖洗的汽車到達過程服從泊松分布，每小時平均到達 6 輛，

32、試求這個排隊系統(tǒng)的數(shù)量指標。,解：這是一個 M / D / 1 排隊模型，其中 = 6 輛/小時， = 60/6 =10 輛/小時，得 P0 =1 / = 0.4, Lq =0.45, Ls = Lq + / = 1.05, Wq = Lq / = 0.0750， Ws = Wq+ 1/ = 0.1750, Pw = / = 0.6。,7 多服務臺泊松到達、任意的服務時間、損失制排隊模型,這種排隊模型記為 M / G / c / c / ，是一種損失制的模型，它要解決的主要問題是在服務機構的空閑與顧客的流失之間找到平衡，找出最合適服務臺數(shù)，使得該系統(tǒng)收益最大。 下面我們給出計算該模型數(shù)量指標的

33、一些公式。 注：該排隊模型不存在平均排隊的顧客數(shù) Lq 和顧客平均的排隊等待時間 Wq。,系統(tǒng)中的平均顧客數(shù) Ls = / (1 Pc ) 其中 Pc 是系統(tǒng)中恰好有 c 個顧客的概率，也就是系統(tǒng)里 c 個服務臺都被顧客占滿的概率。 系統(tǒng)中恰好有 n 個顧客的概率,例3. 某電視商場專營店開展了電話訂貨業(yè)務，到達過程服從泊松分布，平均到達率為每小時 16 個，而一個接話員處理訂貨事宜的時間是隨著訂貨的產(chǎn)品、規(guī)格、數(shù)量及顧客的不同而變化的，但平均每個人每小時可以處理 8 個訂貨電話，在此電視商場專營店里安裝了一臺電話自動交換臺，它接到電話后可以接到任一個空閑的接話員的電話上，試問該公司應安裝多少

34、臺接話員的電話，使得訂貨電話因電話占線而損失的概率不超過 10% 。,解：這是一個 M / G / c / c / 模型。當 c =3 時，系統(tǒng)中正好有 3 位顧客的概率為 因 21.05% 10%，所以不符合要求。,當 c = 4 時，系統(tǒng)中正好有 4 位顧客的概率為 因 9.52% 10%，所以設置四個電話較合適。此時，電話系統(tǒng)里的平均顧客數(shù)為,這種形式的更一般形式為 M / G /c / N / ，這個一般形式和 M / G / c / c / 的區(qū)別在于一般形式允許排隊，但排隊長度不超過（Nc）。,8 顧客來源有限制的排隊模型,以上所介紹的排隊系統(tǒng)都是顧客來源無限制的情況，這一節(jié)我們將

35、介紹顧客來源有限制的情況。從 M / M / 1 / / m 這個記號中我們可以知道這個排隊模型的顧客的總數(shù)為有限數(shù) m。 M / M / 1 / / m 條件： 單位時間顧客平均到達數(shù) 單位平均服務顧客數(shù) ,數(shù)量指標公式: 1、系統(tǒng)中無顧客的概率 2、平均排隊的顧客數(shù) 3、系統(tǒng)中的平均顧客數(shù) Ls = Lq + (1-p0) 4、 顧客在排隊上的平均花費等待時間 Wq = Lq /（m -Ls) ,5、系統(tǒng)在中顧客的平均逗留時間 Ws = Wq+ 1/ 6、系統(tǒng)中有 n 個顧客的概率, n = 0,1,2, , m,例4. 某車間有 5 臺機器，每臺機器連續(xù)運轉時間服從負指數(shù)分布，平均連續(xù)運轉時間為 15 分鐘，有一個修理工，每次修理時間服從負指數(shù)分布，平均每次12 分鐘，假設一個機器停一個小時損失1000元,而一個機修工及其設備運行1小時費用為350元.求該排隊系統(tǒng)的數(shù)量指標 P0，Lq，Ls， Wq，Ws，以及 P5 ；并用