運籌學(xué)導(dǎo)論之排隊論(共115頁).ppt

1、1第12章 排隊系統(tǒng)2Agner Krarup Erlang1878-1929丹麥電信工程師，排隊論之父研究人們打電話的方式，發(fā)展出人們需要等待多久的公式，并于1909年出版了關(guān)于排隊理論的第一篇論文3UCLA, Leonard Kleinrock1934“互聯(lián)網(wǎng)之父” ，“影響本世紀(jì)的50人”UCLA, James R. Jackson19242011排隊網(wǎng)絡(luò)之父排隊論煥發(fā)了新的生命力，影響巨大！4生活在城市中的居民在生產(chǎn)、生活以及學(xué)習(xí)消費的過程中，存在大量的排隊現(xiàn)象，例如，食堂打飯、圖書館借還書、超市收銀臺、醫(yī)院等待看病、車輛在信號燈控制路口排隊等待通過、在銀行柜臺前很多顧客等待辦理業(yè)務(wù)、

2、城市中隨時可能有急診病人等待救護(hù)車的救援、港口外多艘萬噸級船舶等待進(jìn)港裝卸貨物、等待加工的零部件、等待裝配的汽車等等。排隊現(xiàn)象無處不在！排隊現(xiàn)象無處不在！12.1 為什么要研究排隊系統(tǒng)5排隊現(xiàn)象的特征是：顧客以某種隨機(jī)方式到達(dá)一個服務(wù)設(shè)施，之后在隊列中等待，直到他們接受服務(wù)。一旦服務(wù)結(jié)束，通常離開系統(tǒng)。不花費極大的成本，等待現(xiàn)象是不可能完全消除的，我們的目標(biāo)是要把他的不利影響減小到“可以忍受的”程度。67為什么會產(chǎn)生排隊現(xiàn)象？泛泛地說，是由于顧客需求量大于設(shè)施能提供的服務(wù)量顧客需求量大于設(shè)施能提供的服務(wù)量。究竟又是什么原因?qū)е路?wù)設(shè)施的服務(wù)不足？原因很多，例如缺少服務(wù)點、提供的更多服務(wù)則經(jīng)濟(jì)上

3、不可行、空間限制無法容納更多的服務(wù)臺。一般來說，當(dāng)然可以通過增加投資建設(shè)更多的服務(wù)設(shè)施增加投資建設(shè)更多的服務(wù)設(shè)施消除上述因素，但這需要分析“應(yīng)該再增加多少服務(wù)臺才可以消除排應(yīng)該再增加多少服務(wù)臺才可以消除排隊？隊？”。這就需要回答諸如“一個顧客必須要等待多久？一個顧客必須要等待多久？”、“排隊長度會有多長？排隊長度會有多長？”等很多問題。8例例McBurger是一家快餐店，有3個服務(wù)柜臺。該店的經(jīng)理委托他人調(diào)查顧客對服務(wù)速度慢的投訴。調(diào)查結(jié)果顯示，服務(wù)臺數(shù)量與服務(wù)等待時間之間有著如下關(guān)系：收款臺數(shù)1234567平均等待時間1.3仔細(xì)觀察這些數(shù)據(jù)，在3個柜臺

4、的情況下，平均等待時間要7分鐘。需要5個柜臺才能把等待時間減少到3分鐘。排隊分析的結(jié)果可以用在費用優(yōu)化模型中，即求兩種費用(服務(wù)費用和等待費用)之和的最小值。如下圖9顧客等待時間成本服務(wù)時間成本總費用服務(wù)水平費用最優(yōu)服務(wù)水平上圖顯示了一個典型的費用模型，使用費用模型的主要障礙就是很難估計可靠的等待費用，特別是當(dāng)人的行為成為操作的有機(jī)組成部分時。10分析排隊系統(tǒng)的最終目的是為了對排隊等待的顧客提供滿意對排隊等待的顧客提供滿意的服務(wù)的服務(wù)。排隊論主要研究服務(wù)設(shè)施的需求與用戶延誤之間的關(guān)系服務(wù)設(shè)施的需求與用戶延誤之間的關(guān)系，其在分析和規(guī)劃城市服務(wù)設(shè)施扮演重要角色，例如地鐵閘機(jī)的設(shè)置、消防站及消防車的

5、配置以及醫(yī)療救護(hù)點配置等等；在工業(yè)上的用途包括生產(chǎn)線的設(shè)計及布置、加工設(shè)備的配置；服務(wù)業(yè)中服務(wù)人員、柜臺的設(shè)置及調(diào)配。研究排隊論的目的11排隊論，作為運籌學(xué)的重要分支，并不是一種優(yōu)化理論作為運籌學(xué)的重要分支，并不是一種優(yōu)化理論。 而是用于度量排隊系統(tǒng)的性能指標(biāo)，如隊列的平均等待時間和服務(wù)設(shè)施的效率，這些度量指標(biāo)可以用來設(shè)置服務(wù)設(shè)施。排隊論的重點在于實際中排隊分析結(jié)果的實施在于實際中排隊分析結(jié)果的實施；為了充分理解排隊系統(tǒng)的實際問題，就需要了解相當(dāng)?shù)幕A(chǔ)理論背景。為此，首先介紹下構(gòu)成排隊系統(tǒng)的基本要素，然后介紹兩個重要分布(泊松和指數(shù)分布)的“完全隨機(jī)” 性質(zhì)。12n 一個排隊系統(tǒng)中的主要參與者

6、是顧客顧客和服務(wù)臺服務(wù)臺。顧客從某個輸入源輸入源產(chǎn)生，到達(dá)一個服務(wù)設(shè)施設(shè)施，他們可以立即得到服務(wù)；n 假如服務(wù)設(shè)施繁忙，也可能在隊列隊列中等待，當(dāng)一個設(shè)施完成一次服務(wù)，如果有顧客等待的話，自動地“拉出”一個等待顧客；假如隊列為空，設(shè)施就變成空閑，直到一個新的顧客到達(dá)。n 從分析隊列的角度，我們用連續(xù)兩個顧客之間的到達(dá)時間到達(dá)時間間隔間隔表示顧客的到達(dá)，用對每個顧客的服務(wù)時間服務(wù)時間來描述服務(wù)。12.2 排隊模型的要素13組成排隊系統(tǒng)的要素至少包括：顧客輸入源顧客輸入源、隊列隊列以及服務(wù)服務(wù)臺臺，而服務(wù)臺可以是單個的，也可以是多個并行聯(lián)接的。如果要全面而準(zhǔn)確的描述一個排隊系統(tǒng)，則需要有如下6個要

7、素：（1）顧客到達(dá)模式顧客到達(dá)模式（顧客發(fā)生源類型）；（2）服務(wù)臺服務(wù)模式服務(wù)臺服務(wù)模式（服務(wù)臺服務(wù)方式）；（3）排隊規(guī)則排隊規(guī)則；（4）排隊系統(tǒng)容量排隊系統(tǒng)容量；（5）服務(wù)通道數(shù)量服務(wù)通道數(shù)量；（6）服務(wù)階段數(shù)量服務(wù)階段數(shù)量。1412.2.1 顧客到達(dá)模式顧客到達(dá)模式 n 排隊系統(tǒng)的顧客輸入源常常以單位時間內(nèi)到達(dá)顧客的平均數(shù)量（mean arrival rate），兩個連續(xù)顧客之間的平均到達(dá)間隔時間（mean interarrival time）來描述。n 進(jìn)入排隊系統(tǒng)的顧客流可以是確定型的，此時完全可以用平均到達(dá)率或者平均間隔時間來表示；n 如果進(jìn)入排隊系統(tǒng)的顧客流存在不確定性，此時用平均

8、到達(dá)率或者平均間隔時間，僅能描述輸入顧客的隨機(jī)過程的集體趨勢，如果要進(jìn)一步完整地描述顧客到達(dá)模式，則需要顧客到達(dá)隨機(jī)變量的概率分布。n 顧客到達(dá)模式可能不是一次到達(dá)一個顧客，而是一批一批到達(dá)的，此時相鄰批次到達(dá)的間隔時間可能是隨機(jī)的，每批次的顧客數(shù)量也是隨機(jī)的。 15不同類型的顧客對于進(jìn)入排隊系統(tǒng)有不同的反應(yīng)不同類型的顧客對于進(jìn)入排隊系統(tǒng)有不同的反應(yīng)n 有些顧客將一直在隊列中等待直到獲得服務(wù)才離開；n 有些顧客會認(rèn)為隊列太長而不進(jìn)入排隊系統(tǒng)直接離開；n 有些顧客則是到了排隊系統(tǒng)臨時決定不參加排隊；n 有些顧客則參與排隊，但是失去耐心后決定離開系統(tǒng)；n 而有時候在服務(wù)臺前有兩列或更多的隊列，則有

9、些類型的顧客在不同隊列之間來回排隊，以縮短期望排隊時間。 （后4種情況被認(rèn)為是急躁型的顧客）n 如果顧客到達(dá)模式不隨時間改變（隨機(jī)型到達(dá)模式的參數(shù)不隨時間變化），則認(rèn)為是平穩(wěn)的；反之則為非平穩(wěn)的。 16服務(wù)率服務(wù)率以單位時間內(nèi)服務(wù)的顧客數(shù)量以服務(wù)一個顧客需要的時間當(dāng)討論服務(wù)臺服務(wù)時間當(dāng)討論服務(wù)臺服務(wù)時間（總假定排隊系統(tǒng)是存在顧客要服務(wù)）確定型隨機(jī)型，在系統(tǒng)非空條件下服務(wù)臺的概率分布服務(wù)設(shè)施中服務(wù)臺個數(shù)服務(wù)設(shè)施中服務(wù)臺個數(shù)單個，每次只能服務(wù)一個顧客多個，可以同時服務(wù)多個顧客 12.2.2 服務(wù)臺服務(wù)模式服務(wù)臺服務(wù)模式 17n 先到先服務(wù)（First come, First served），先進(jìn)先

10、出（First in, First out）n 后到先服務(wù)（Last come, First served），庫存系統(tǒng)。n 隨機(jī)順序服務(wù)（Service in random order, SIRO），該規(guī)則不考慮顧客到達(dá)先后順序，隨機(jī)地選擇顧客進(jìn)行服務(wù)。n 優(yōu)先權(quán)排隊規(guī)則l 絕對搶先式，具有最高優(yōu)先級的顧客即刻獲得服務(wù)l 非絕對搶先式，具有最高級別的顧客即刻在隊列的最前端排隊，但不能馬上接受服務(wù)，直到當(dāng)前顧客（即使其級別較低）服務(wù)結(jié)束以后才能接受服務(wù)12.2.3 排隊規(guī)則排隊規(guī)則 在出現(xiàn)顧客排隊的情況下，選擇顧客進(jìn)行服務(wù)的選擇機(jī)制。在出現(xiàn)顧客排隊的情況下，選擇顧客進(jìn)行服務(wù)的選擇機(jī)制。18在有些

11、排隊系統(tǒng)中，其排隊等候區(qū)域受到物理空間限制，當(dāng)隊列達(dá)到一定長度時，后續(xù)的顧客無法進(jìn)入等待區(qū)，除非當(dāng)前接受服務(wù)的顧客接受服務(wù)后離開系統(tǒng)，后續(xù)新到顧客才被允許進(jìn)入排隊區(qū)等待。對于有限隊列長度的排隊系統(tǒng)，其到達(dá)的顧客可視為其到達(dá)數(shù)量必須累積到排隊容量以后的成批的排隊。這是最簡單成批到達(dá)情況，原因在于顧客的批量是固定值。 12.2.4 排隊系統(tǒng)容量排隊系統(tǒng)容量19n 只有1個服務(wù)臺的系統(tǒng)為單通道服務(wù)系統(tǒng)，在服務(wù)設(shè)施內(nèi)設(shè)置多個并行的服務(wù)臺是多通道服務(wù)系統(tǒng)。n 兩類不同的多通道服務(wù)系統(tǒng)，一般來說，在排隊論中都假設(shè)服務(wù)臺是相互獨立運作的l 多個服務(wù)臺共同為一個隊列服務(wù)l 每個服務(wù)臺僅為本隊列提供服務(wù)12.2

12、.5 服務(wù)通道數(shù)量服務(wù)通道數(shù)量在同一時刻能為顧客提供服務(wù)的并行服務(wù)臺數(shù)量在同一時刻能為顧客提供服務(wù)的并行服務(wù)臺數(shù)量20排隊系統(tǒng)中，許多服務(wù)設(shè)施提供的服務(wù)級數(shù)包括兩類l單級的單級的，例如高速公路收費站、車站檢票口等；l多級的多級的，例如醫(yī)院的體檢系統(tǒng)。多級服務(wù)也可能是循環(huán)的，例如在含有產(chǎn)品質(zhì)量跟蹤控制功能的產(chǎn)品生產(chǎn)線中，一旦零部件經(jīng)過檢測不合格，則需要重新送到生產(chǎn)線再進(jìn)行處理。下圖是帶有循環(huán)（有時候也稱之為反饋）服務(wù)的排隊系統(tǒng)。12.2.6 服務(wù)級數(shù)服務(wù)級數(shù)21上述6個排隊系統(tǒng)基本特征元素，一般的可以充分的描述各種排隊過程。從上述介紹也可以看出排隊過程無處不在。排隊模型的要素的總結(jié)必須充分理解排

13、隊系統(tǒng)的這6個特征元素，以清楚掌握排隊系統(tǒng)的運作過程，具體包括排隊通道和服務(wù)設(shè)施之間是如何相互連接和影響的，顧客又是如何被分配到排隊通道中的。 2212.3 指數(shù)分布的作用在大多數(shù)排隊情況中，顧客的到達(dá)是完全隨機(jī)的。這里的隨機(jī)意味著，一個事件的發(fā)生(如一個顧客的到達(dá)或一項任務(wù)的完成)不受上一個時間發(fā)生以后所經(jīng)過的時間長度的影響。排隊模型中，隨機(jī)到達(dá)間隔時間到達(dá)間隔時間和服務(wù)時間服務(wù)時間用指數(shù)分布來定量描述，定義為 ,0tf tet對于指數(shù)分布(exponential distribution) 2011()1TttE tVar tP tTedte 為單位時間內(nèi)產(chǎn)生事件的速率。23為什么指數(shù)分布

14、是完全隨機(jī)的？如何理解？假定現(xiàn)在是上午8:20,上一個顧客到達(dá)時間是8:02，下一個到達(dá)發(fā)生在8:29之前的概率只是8:208:29這一區(qū)間的函數(shù)，與上一個事件的發(fā)生(8:02 8:20)以來所流逝的時間長度完全無關(guān)。這個結(jié)果稱之為指數(shù)分布的無記憶性(memoryless)8:028:208:29(8:298:20(8:208:02)|(8:208:02)(8:298:20)P ttP t(9 18|18)(9)PttPt 24令指數(shù)分布 f(t) 表示相繼事件之間的時間t的概率分布。如果S為上一個事件發(fā)生以來的時間區(qū)間，則遺忘性意味著(|)()P tTS tSP tT()1()TP tTP

15、tTe 而0SS+TSTt證明：注意到對于平均值為1/的指數(shù)函數(shù)，我們有()(|)()()()()TSTSP tTStSP tTS tSP tSP tTSeeP tTP tSeP(AB)=P(B|A)P(A)25指數(shù)分布的無記憶性很重要，因為它意味著如果我們希望知道下次到達(dá)的時間概率分布，那么自上次到達(dá)以后流逝的時間長短不具有影響。我們假設(shè)到達(dá)時間間隔服從=6的指數(shù)分布。那么無記憶特性意味著自上次到達(dá)以后不管經(jīng)過多長時間，那么下一次到達(dá)時間的概率分布仍然為 6e-6t. 這意味著要觀測未來到達(dá)模式，我們不需要跟蹤上一次到達(dá)之后經(jīng)過了多長時間。這種觀測可以簡化排隊系統(tǒng)的分析。這種觀測可以簡化排隊

16、系統(tǒng)的分析。26例例假設(shè)在銀行花費的時間以均值為10分鐘指數(shù)地分布，即=1/10.問一個顧客在此銀行中花費15分鐘的概率是多少？給定一個顧客10分鐘以后仍舊在銀行中，她在銀行中將花費超過15分鐘的概率是多少？解 如果X表示顧客在這個銀行中花費的時間，那么第一個概率正是第二個問題。由于指數(shù)分布，所以這個顧客已經(jīng)在銀行中花費10分鐘是沒有記憶的，這就意味著這個已經(jīng)等待10分鐘的顧客還要等5分鐘，其概率正好是153/2150.220P Xee51/250.604P Xee2712.4 生滅模型排隊系統(tǒng)中，任意時間它的狀態(tài)用這個時間在系統(tǒng)中的人數(shù)表示。則該狀態(tài)取決于各個時刻進(jìn)入進(jìn)入和離開離開人數(shù)的速率

17、，這樣的系統(tǒng)稱之為生滅過程。生滅過程例子很多，地區(qū)的人口增減、細(xì)菌或細(xì)胞的繁殖與死亡、服務(wù)臺前的顧客數(shù)量變化等等。為了簡化，只考慮只有到達(dá)的純生模型只有到達(dá)的純生模型和只有離開的純滅模只有離開的純滅模型型。純生模型的例子如為新生嬰兒制作出生證明，純滅模型的例子如一家商店對其庫存貨物的隨機(jī)提貨。2812.4.1 純生模型純生模型定義 p0(t)=t 時期內(nèi)沒有到達(dá)的概率已知到達(dá)時間間隔是指數(shù)分布的，并且每單位時間顧客到達(dá)率為，則( )()1()1 (1)=0tt p t = Pt= - Pt= -ee到達(dá)間隔時間到達(dá)間隔時間對于一個充分小的時間區(qū)間 h0, 根據(jù)泰勒級數(shù)展開，有 2201102!

18、hhphehhh 指數(shù)分布基于假設(shè)：在充分小的h0期間，最多有一個事件能夠發(fā)生。因此，當(dāng) h0， 101phphh 這一結(jié)果表示，h 期間一次到達(dá)的概率與 h 成正比例，到達(dá)率為比例常數(shù)。29定義某期間 t 內(nèi)到達(dá)數(shù)目的分布pn(t) pn(t)= t 期間內(nèi)有 n 個到達(dá)的概率在t 期間內(nèi)有 n 個顧客的組合，包括以下兩種情況： 0110010,0,01,0(1)1,0(2)nnnnnpt phpt p hnpthpt phnpthpthnpthn 101phphh t+h(0,t)(0,t+h)nn0n-11000對于充分小的 h0, 根據(jù)互不相容的全概率公式，有根據(jù)互不相容的全概率公式，

19、有30重新安排各項并取當(dāng) h0 的極限，得到 1000lim,0lim,0nnnnnxnxpt+hptptptptnhpt+hptptptnh 其中 是 pn(t) 關(guān)于 t 的一階導(dǎo)數(shù).求解上述差分-微分方程，得到 npt ,0,1,2,!ntnteptnn 這正是t期間平均有E(n|t)=t個到達(dá)的泊松分布(Poisson distribution) 上面的結(jié)果說明,若到達(dá)時間間隔服從平均值為1/的指數(shù)分布，則指定期間 t 內(nèi)的到達(dá)數(shù)服從平均值t的泊松分布. 反之亦然.31指數(shù)分布指數(shù)分布泊松分布泊松分布隨機(jī)變量相繼到達(dá)之間的時間 t指定 T 期間的到達(dá)數(shù) n取值范圍t 0n= 0,1,2

20、,密度函數(shù)平均值1/時間單元T期間有T個到達(dá)累積概率P(A期間無達(dá)到) ,0tf tet ,0,1,2,!ntnteptnn1AP tA =e 01n NNPT = pTp TpTAP tA = e 0APA = e指數(shù)分布與泊松分布之間的關(guān)系指數(shù)分布與泊松分布之間的關(guān)系32例例某人口稀少州的出生率為每12分鐘出生一個新生嬰兒。出生間隔時間服從指數(shù)分布，求下列各值：(1) 每年出生的平均數(shù). (2)任何一天內(nèi)無新生兒出生的概率.(3) 假設(shè)在3個小時時間內(nèi)前2小時已經(jīng)發(fā)出了40份出生證明，求這3個小時內(nèi)發(fā)出50份出生證明的概率。 每天的出生率為該州每年出生人口為 任意一天沒有新生兒出生的概率可

21、以用泊松分布計算為24 60120/12人 天120 36543800/t人 年 0120 11200120 1100!epe假設(shè)在3個小時內(nèi)的前2小時已經(jīng)發(fā)出了40份出生證明，計算3小時內(nèi)發(fā)出50份出生證明的概率，相當(dāng)于1小時(=3-2)內(nèi)出生10(=50-40)個新生兒，因為出生數(shù)的分布是泊松的. 105 1105 110.0181310!ep 3312.4.2 純滅模型純滅模型在純滅模型中，系統(tǒng)在0時刻開始時有N個顧客，后面沒有新的顧客到達(dá). 離開的發(fā)生率為每單位個顧客. 為了建立t時間單位后剩下n個顧客的概率pn(t)的差分-微分方程，根據(jù)出現(xiàn)n個顧客的情況，依據(jù)不相容的全概率公式，有

22、 0011100110111,011NNNnnnnnpthpt phpthpthpt phpt p hpthpthnNpthptp t p hptp tht+h(0,t)(0,t+h)NN0nn0n+11000當(dāng)h0, 得到 101,0NNNnnptptptptptnNptp t 這組方程的解得到下面的截尾泊松(Truncated Poisson)分布: 01,0,1,2,!1N ntnNnnteptnNNnptpt 經(jīng)過 t 時間還剩下 n 個顧客的概率35例例某雜貨店鮮花柜臺每周初庫存18打玫瑰花. 平均情況下，鮮花柜臺每天賣出去3打(一次一打)，但實際需求量服從泊松分布. 一旦庫存水平剩

23、下5打，就再訂貨補(bǔ)充到18打，下周一送貨。由于鮮花商品的特性，周末沒有賣出的玫瑰花就要扔掉，求下列值：(1) 該周內(nèi)任何一天訂貨的概率.(2) 周末扔掉的玫瑰花的平均數(shù)量.36因為購買的發(fā)生率為每天=3打，t 日結(jié)束前訂貨的概率為 )( )( )( )( ),1,2,718!ntnnteptp tp tp tp ttnt (星期幾)1234567t36912151821pn5(t)0.0000.00880.1242 0.4240 0.7324 0.9083 0.9755輸出結(jié)果如下：周末(t=7)扔掉的玫瑰花平均數(shù)為E(n|t=7). 為了計算這個值, 我們需要用到p

24、n(7), n=1,2,18, 計算結(jié)果為 180( |7)70.6641nnE n tnp打3712.5 廣義泊松排隊模型本節(jié)利用生滅模型，建立一個通用的排隊模型。再根據(jù)到達(dá)間隔和服務(wù)時間服從指數(shù)分布，推導(dǎo)出基于泊松分布的排隊論模型。廣義模型的建立是基于排隊情形的長期行為長期行為，或平穩(wěn)狀態(tài)行平穩(wěn)狀態(tài)行為為，這種狀態(tài)在系統(tǒng)經(jīng)過充分長時間的運行后得到的。這種分析和系統(tǒng)初期運行期間所常見的瞬時瞬時(transient)行為完全不同。本章不討論瞬時行為的一個原因是由于對它的解析過于解析過于復(fù)雜復(fù)雜；另一個原因是由于對大多數(shù)排隊系統(tǒng)都是在平穩(wěn)狀態(tài)平穩(wěn)狀態(tài)下來研究下來研究的。38廣義模型假設(shè)，到達(dá)率和

25、離開率都是與狀態(tài)相關(guān)的與狀態(tài)相關(guān)的(state dependent), 也就說系統(tǒng)的狀態(tài)以服務(wù)設(shè)施中的顧客數(shù)量來度量的。例如，在高速公路收費口，在高峰時間收費員通常會提高收費速度。道路交通網(wǎng)絡(luò)上的信號燈控制系統(tǒng)會依據(jù)交通流量的變化，信號配時作出變化，此時道路網(wǎng)絡(luò)的狀態(tài)也是依賴于狀態(tài)的。 定義 n=系統(tǒng)中的顧客總數(shù)(排隊+正在接受服務(wù)的) n=已知系統(tǒng)中有n個顧客的到達(dá)率 n=已知系統(tǒng)中有n個顧客的離開率 pn=系統(tǒng)中有n個顧客的平穩(wěn)狀態(tài)概率廣義模型中， pn作為 n 和 n 的函數(shù)，利用這些概率求出系統(tǒng)行為中的度量指標(biāo)，例如平均隊長、平均等待時間和設(shè)備利用率.39如果以系統(tǒng)中的顧客數(shù)量來表示系

26、統(tǒng)的狀態(tài)，那么令排隊系統(tǒng)中有n個用戶的概率為 pn. 那么概率pn可以用下圖的狀態(tài)轉(zhuǎn)移關(guān)狀態(tài)轉(zhuǎn)移關(guān)系圖系圖來得到. 根據(jù)第3小節(jié)的解釋，在一個時間間隔h里多于1個事件發(fā)生的概率隨著 h0而趨于0. 這就意味著，對于n0, 狀態(tài) n 只能變成兩種可能的狀態(tài): 當(dāng)以離開率 離開時變成n-1, 當(dāng)按照到達(dá)率 到達(dá)時變成n+1. 狀態(tài)0按照到達(dá)率 到達(dá)時只能變成狀態(tài)1. 注意到，假如系統(tǒng)為空時, 因為沒有離開發(fā)生， 沒有定義.nn00012n-1nn+11n01nn1n2140當(dāng)系統(tǒng)處于平穩(wěn)狀態(tài)條件下，轉(zhuǎn)入率等于轉(zhuǎn)出率，也就說單位時間進(jìn)入該狀態(tài)的平均次數(shù)和單位時間內(nèi)離開狀態(tài)的平均次數(shù)要相等。所以，狀態(tài)

27、 n 只能變成狀態(tài)(n-1)和狀態(tài)(n+1), 因此有類似地1111n-nnnnpp單位時間內(nèi)流進(jìn)狀態(tài) 的次數(shù)=nnnnp單位時間內(nèi)流出狀態(tài) 的次數(shù)=系統(tǒng)平穩(wěn)狀態(tài)下，單位時間內(nèi)轉(zhuǎn)入和轉(zhuǎn)出次數(shù)要相等1111n-nnnnnnppp=對于n=0的平衡方程為0011ppn-1nn+11nnn1n41從p0開始遞歸求解平衡方程如下：對于 n=0，有0101pp接下來，對 n=1，有0022111ppp=用 替換并化簡，得到0101pp102021pp 用歸納法可以得到如下廣義穩(wěn)態(tài)概率公式11210000nn-1211,1,2,ninninniipppn 從p0的值可以從等式 求出. 01nnp42010

28、21000001213211pppp 解得01101211100211011,2,nnnnnnpnppn 43例例 B&K食品店有3個收款臺. 經(jīng)理根據(jù)店內(nèi)顧客數(shù)量，按照下列安排決定提供服務(wù)的收款臺個數(shù)。顧客按照平均10位/小時的泊松分布來收款區(qū). 每位顧客的平均收款時間為指數(shù)分布，平均為12分鐘. 求n個顧客在收款區(qū)的平穩(wěn)狀態(tài)概率pn店內(nèi)顧客數(shù)量使用收款臺的個數(shù)1314626人以上3根據(jù)本題的信息，有10/01nn個顧客 小時， ，60/125/0,1,2,32 510/4,5,63 515/7,8nnnn顧客 小時，顧客 小時，顧客 小時，44因此 1002200330034003

29、250033600336670010/5210/5410/5810/510/10810/510/10810/510/10810/510/1010/158 2/3nnnpppppppppppppppppppppp0的值從下面的等式求出23002488888 2/38 2/38 2/31pp利用幾何級數(shù) 得到01,11iixxx450131 811 2/3p因此，p0=1/55. 知道了p0，就可以求出pn. 進(jìn)而可以計算出系統(tǒng)中使用不同收款臺個數(shù)的概率. 例如使用一個收款臺的概率就是最多出現(xiàn)3個顧客的概率=p1+p2+p34612.6 特殊泊松排隊12.6.1 排隊系統(tǒng)的Kendall-Lee的

30、符號表示下圖顯示帶有c個并行服務(wù)臺的特殊泊松排隊情形。系統(tǒng)中的顧客數(shù)定義為正在接受服務(wù)的顧客加隊列中等待服務(wù)的顧客。服務(wù)臺1服務(wù)臺1服務(wù)臺1.服務(wù)臺1服務(wù)臺1服務(wù)臺1.47為了方便表示上圖排隊的情形的特性，采用下面的格式(a/b/c):(d/e/f)其中，a=到達(dá)分布，b=離開(服務(wù)時間)分布，c=并行服務(wù)臺個數(shù)，d=排隊規(guī)則，e=系統(tǒng)中最大運行容納的顧客數(shù)，f=顧客輸入源的多少(有限或無限)表示到達(dá)和離開分布表示到達(dá)和離開分布(a和和b)的標(biāo)準(zhǔn)記號有的標(biāo)準(zhǔn)記號有M=馬爾科夫或泊松分布，D=常數(shù)(確定型)時間，Ek=參數(shù)為k的埃爾朗或分布(等價于獨立指數(shù)分布和)，GI=到達(dá)間隔時間的一般性/通

31、用分布，G=服務(wù)時間的一般性/通用分布排隊規(guī)則排隊規(guī)則(符號符號d)包括包括FCFS=先到先服務(wù)，LCFS=后到先服務(wù)，SIRO=隨機(jī)秩序服務(wù)，GD=一般/任意規(guī)則(M/D/10): (GD/20/), (M/E2/8/):(FCFS/10/)4812.6.2 隊列行為的平穩(wěn)狀態(tài)度量Ls=系統(tǒng)中顧客的期望數(shù)量Lq=隊列中顧客的期望數(shù)量Ws=系統(tǒng)中的期望等待時間Wq=隊列中的期望等待時間 =繁忙服務(wù)臺的期望數(shù)c最常用的隊列行為度量指標(biāo)有系統(tǒng)包括隊列加上服務(wù)設(shè)施。下面說明如何利用系統(tǒng)的狀態(tài) n 及其平穩(wěn)狀態(tài)概率pn得到上述的度量指標(biāo)。49首先根據(jù)數(shù)學(xué)期望得到11snnqnn cLnpLnc p 系

32、統(tǒng)中期望的顧客數(shù) 隊列中期望的顧客數(shù)(平均隊長)而Ls與Ws(以及Lq與Wq)之間的關(guān)系稱為Little公式(little formula),具體關(guān)系包括如下seffsLW系統(tǒng)中平均顧客數(shù)量與駐留系統(tǒng)的時間之間滿足：隊列中期望的顧客數(shù)(平均隊長)與排隊時間滿足：qeffqLW上述關(guān)系在相當(dāng)一般的條件下成立。參數(shù)eff 是系統(tǒng)的有效到達(dá)率，當(dāng)所有到達(dá)的顧客都可能加入時，就為；如果系統(tǒng)滿了(存在容量限制系統(tǒng))，則顧客不能加入， eff 清華版p319不準(zhǔn)確50Ws和Wq之間也存在直接的關(guān)系。由定義希望系統(tǒng)駐留時間=期望排隊時間+期望服務(wù)時間可以寫成 1sqWW對上式兩邊乘以eff ，建立Ls與Lq

33、的關(guān)系. 結(jié)合Little公式，得到effsqLL根據(jù)定義，系統(tǒng)的平均顧客數(shù)與隊列中平均的顧客數(shù)的差值等于繁忙服務(wù)臺的平均數(shù)，因此有effsqcLL因此，得到了設(shè)施利用率=cc51例Ozark學(xué)院來訪者的停車位只有5個，使用這些停車位的車輛以泊松分布到達(dá)，每小時到達(dá)6輛車。停車時間服從均值為30分鐘的指數(shù)分布。到達(dá)后找不到空泊位的來訪者可以在停車場邊臨時停車位等待，直到有停著的車輛離開。臨時車位只能放3輛車，而停不了也找不到臨時停車位的車輛必須去別的地方停車，求（1） 系統(tǒng)中有n輛車的概率；（2） 實際使用停車場的車輛的有效到達(dá)率；（3） 停車場平均的停車數(shù)量；（4） 一輛車在停車場內(nèi)等待停車

34、位的平均時間；（5） 占據(jù)停車位的平均車輛數(shù)；（6） 停車場的平均使用率。注意到，一個停車位就是一個服務(wù)臺，這樣，系統(tǒng)共有c=5個并行的服務(wù)臺. 另外，系統(tǒng)的最大容量為5+3=8輛車.可以按照之前介紹的pn計算。526/60/302/,1,2,3,4,55 60/3010/,6 7 8nnnnnnn輛車 小時， =0,1,2,8輛車 小時輛車 小時， ，將n和n代入下面的公式0503 / !,1,2,3,4,53 / 5!5,6,7,8nnnnnpnppn0110121110021111,2,nnnnnnpppn 得到p0=0.0481253有了p0, 可以計算p1到p8如下n12345678

35、pn0.144360.21654 0.21654 0.16240 0.09744 0.05847 0.03508 0.02105實際使用停車場的車輛的有效到達(dá)率的計算取決于停車場是否滿了。有效到達(dá)率可以通過如下示意圖計算車輛可以以eff 進(jìn)入停車場或者以lost離開. 假如8輛車已經(jīng)在停車場，則到達(dá)的車便不能進(jìn)入停車場的概率為p8. 因此efflost停車設(shè)施86 0.021050.1263/60.12635.8737/lostlostpeff輛車 小時輛車 小時54停車場內(nèi)車輛的平均數(shù)等于系統(tǒng)內(nèi)車輛的平均數(shù)Ls. 我們可以用pn計算出Ls01810183.1286snnLnpppp輛在臨時車

36、位等待的車輛實際上就是隊列中的車輛. 因此，等待找到車位的等待時間就是Wq. 為確定Wq ，用1qsWW因此eff3.12860.532655.87370.532650.50.03265ssqLWW小時小時占用了車位的平均車輛數(shù)就與繁忙服務(wù)臺的平均數(shù)相等/5.8737/22.9368/2.9368/558.73%sqeffcLLc c車位停車場利用率=5512.6.3 單服務(wù)臺模型本節(jié)介紹僅有一個服務(wù)臺到達(dá)率為、服務(wù)率為的排隊服務(wù)系統(tǒng). 首先討論系統(tǒng)容量無窮大的情形, 再討論系統(tǒng)容量有限情形.之前介紹的各種排隊系統(tǒng)的性能指標(biāo)與具體的排隊規(guī)則沒有關(guān)系，所以我們用一般排隊規(guī)則GD.(M/M/1):

37、(GD/)基本假設(shè)如下：efflost,0,1,2,0,nnn 所有的到達(dá)的顧客都加入系統(tǒng)與排隊系統(tǒng)狀態(tài)無關(guān)56令 ，將其稱之為服務(wù)強(qiáng)度或業(yè)務(wù)密度，則廣義模型中 pn 的表達(dá)式簡化為/ 1100021,0,1,2,nnnnppp n 為了求p0的值，用等式2011p設(shè)1, 利用幾何級數(shù)求和公式有2111所以01,1p 其中所以1,1,2,1nnpn pn的數(shù)學(xué)推導(dǎo)將用到條件1或者. 如果則幾何級發(fā)散，平穩(wěn)態(tài)概率不存在. 這個結(jié)果有直觀的意義，除非服務(wù)率大于到達(dá)率，否則隊列長度將不斷增長，不可能到達(dá)平穩(wěn)狀態(tài).57排隊系統(tǒng)的性能度量指標(biāo) Ls 可以按照下面的方式得到：000111111nnsnnn

38、ndLnpnddd 因為對于本情形 ，剩下的系統(tǒng)性能度量指標(biāo)用6.2節(jié)的關(guān)系來計算. 因此有eff111(1)ssqsLWWW 21qqsqLWcLL58例例Automata洗車房只運行一個清洗位. 車輛按照泊松分布到達(dá)，平均每小時4輛車，如果清洗位忙，則到達(dá)的車輛等在洗車房的停車場. 一輛車的清洗時間服從指數(shù)分布，平均值為10分鐘. 不能進(jìn)停車場的車輛可在洗車房的路邊等待，這意味著從實際上來說，系統(tǒng)是沒有容量限制的。為洗車房確定出停車場合適的停車泊位數(shù)量。該例中，=4輛車/小時，=60/10=6輛車/小時. 因為1,系統(tǒng)可以按照平穩(wěn)狀態(tài)運行。一般來說，不建議只用Ls來計算停車位數(shù)，因為從某種

39、意義上，停車位代表了要保證最大可能的隊列長度. 59例如，停車場的設(shè)計要使得來到的車在至少90%的時候能找到停車位。為了做到這一點，令S表示停車位數(shù)，有S個停車位等價于系統(tǒng)中有S+1個位置. 假如系統(tǒng)中最多有S個停車位，則到達(dá)的車輛90%的時候都能找到位置. 這個條件等價于下面的概率條件：即010.9sppp2110.9s根據(jù)有限項的幾何技術(shù)求和公式，有12111ss所以1110.90.1ss兩邊取對數(shù)(注意到ln(x)0, 0 x1,不等式變號)ln 0.114.6795ln 4/6S 60(M/M/1):(GD/)的等待時間分布的等待時間分布廣義模型中得到的 pn 與排隊規(guī)則完全無關(guān). 這

40、意味著, 排隊系統(tǒng)性能的平均度量指標(biāo)(Ws, Wq, Ls, Lq) 可以用于所有排隊規(guī)則.雖然平均等待時間與排隊規(guī)則無關(guān), 但它的概率密度函數(shù)卻不然. 我們基于FCFS規(guī)則的M/M/1模型導(dǎo)出等待時間的分布來說明.令為剛剛到達(dá)的一位顧客為了獲得服務(wù)必須駐留在系統(tǒng)的時間. 根據(jù)FCFS規(guī)則，假如一個剛剛到達(dá)的顧客前面還有n個顧客在系統(tǒng)中，則其中 是當(dāng)前在接受服務(wù)的顧客所需要的完成服務(wù)的時間, t2,t3,tn為隊列中的n-1個顧客的服務(wù)時間. 時間tn+1表示剛剛到達(dá)的這個顧客的服務(wù)時間.121nttt1t61定義 為已知系統(tǒng)中有n個顧客在剛剛到達(dá)的顧客之前的條件下, 的條件密度函數(shù). 因為服

41、務(wù)時間的分布是指數(shù)的，指數(shù)分布的遺忘性質(zhì)表明， 也是指數(shù)的，服從相同的分布. 因此，等于(n+1)個同分布的獨立指數(shù)隨機(jī)變量之和. 由概率論可知， 服從帶有參數(shù) 和(n+1)的分布. 因此有( |1)wn1t( |1)wn00()0()( )( |1)1!()11,0!nnnnnnnewwnpneeeen 因此， 為一指數(shù)分布，平均值為( )w1sW62例例Automata洗車房只運行一個清洗位. 車輛按照=4輛車/小時泊松分布到達(dá)，該服務(wù)根據(jù)FCFS規(guī)則進(jìn)行的，一輛車的清洗時間=60/10=6輛車/小時，如果清洗位忙，則到達(dá)的車輛等在洗車房的停車場. 不能進(jìn)停車場的車輛可在洗車房的路邊等待。

42、評價用Ws作為估計系統(tǒng)中等待時間的可靠性.回答這個問題的一個方法是，估計顧客中等待時間超過Ws的比例，注意到 ，我們得到1sW101( )0.368sWsWsPWwdee 在FCFS規(guī)則下, 大約37%的顧客的等待時間比Ws要長. 我們注意到所計算的概率e-1與任何(M/M/1):(FCFS/)的到達(dá)率和服務(wù)率都無關(guān), 這意味著它的值不能減少. 這樣, 如果我們以Ws來設(shè)計系統(tǒng)的話, 將有36.8%的顧客的等待時間長于平均等待時間63(M/M/1):(GD/N/)模型模型這個模型和(M/M/1):(GD/)不同之處在于，系統(tǒng)最多容納的顧客數(shù)(最大隊列長度為N-1)為N. 例如流水線上放置工件的

43、空間是有限的.當(dāng)系統(tǒng)中的顧客數(shù)達(dá)到 N 時，不允許再有到達(dá)，因此有,0,1,10,1,0,1,nnnNnN Nn利用 ，根據(jù)廣義模型的穩(wěn)態(tài)概率公式/ 0,0,nnpnNpnN可以從等式 求出 p0 的值，這將得到01nnp2011Np64101,111,11NpN 或因此有11,11,0,1,1,11nNnpnNN 在這個模型中, 的值不需要小于1, 因為系統(tǒng)的到達(dá)受到系統(tǒng)顧客上限 N 的限制. 這意味著在這種情況下, 重要的是到達(dá)率eff而不是. 由于系統(tǒng)中有 N 個顧客，再來的顧客就不再進(jìn)入系統(tǒng). 此時/ lostefflost(1)NNpp系統(tǒng)中期望顧客數(shù)可以計算為11000111111

44、111 (1)11,11111NNNnnsnNNnnnNNNNNdLnpndNNdd當(dāng) 時，Ls=N/2. 同樣從Ls, 利用eff求出Ws, Wq, Lq.110110(1)(1)(1),111(1)1/NNqnsNnssqsNLnPLpLWpWW66(M/M/1):(GD/m)模型模型這個模型和(M/M/1):(GD/)不同之處在于，系統(tǒng)的顧客源的顧客總數(shù)為m. 例如最常見的是機(jī)器發(fā)生故障停機(jī)待修的問題，此時總共有m臺機(jī)器，機(jī)器發(fā)生故障即表示顧客“到達(dá)”，修理工人是服務(wù)員，類似的問題還有m個打字員共有一臺打字機(jī)。雖然顧客有m個，但每個顧客到達(dá)并經(jīng)過服務(wù)以后，仍然回到原來的發(fā)生源中，所以仍然

45、會到達(dá)。顧客源總數(shù)達(dá)到m時，此時顧客單位時間內(nèi)的到達(dá)次數(shù)依賴于當(dāng)前尚未到達(dá)系統(tǒng)的顧客數(shù)，假設(shè)每個顧客進(jìn)入系統(tǒng)的到達(dá)率為,進(jìn)入系統(tǒng)的顧客為n, (0nm), 則系統(tǒng)外的顧客為m-n, 所以系統(tǒng)的到達(dá)率,1,2,nmnnm而系統(tǒng)的離開率取決于服務(wù)臺數(shù)量為1，此時有,1,2,nnm67根據(jù)廣義模型，有0!,1,2,()!0nnmpnmpmnnm根據(jù)根據(jù) ，有01mnnp001!()!imipmmi注意，此時不要求 成立/1 68根據(jù)Little公式以及系統(tǒng)期望公式，有00000(1)()(1)(1)1(1)11(1)sqssqLmppLmLpmWpmWp6912.6.4 多服務(wù)臺模型本節(jié)考慮有多個并

46、行服務(wù)臺的3個排隊模型。前兩個是上一節(jié)介紹的單服務(wù)臺的多服務(wù)臺版本，第三個模型針對自助服務(wù)的情況，等價于無限個并行服務(wù)臺情形。(M/M/c):(GD/)模型模型在這個模型中有c個并行的服務(wù)臺. 到達(dá)率為, 每個服務(wù)臺的服務(wù)率為.因為對系統(tǒng)中的排隊人數(shù)沒有限制，所以eff使用并行服務(wù)臺的效果使得設(shè)施的服務(wù)率成比例的增加. 根據(jù)廣義模型(第五節(jié))，nn和定義為,0,nnnnnccnc=70因此，根據(jù)廣義穩(wěn)態(tài)概率計算公式00001,(2 )(3 )()!,!()nnnnnnn cncn cippncnnpppncc cicp0的值可以從 求出，得到01nnp1100111,! 1kcckpkcc71

47、系統(tǒng)的運行指標(biāo)如下1100000110020()!(1)!()kk ccqnk ckn ckkkkcckLnc pkpkppkc cc ccdppc ccccdcsqLL,qsqqLLWW72例例某社區(qū)由兩家出租車公司提供服務(wù)，每家公司有2輛出租車，且兩家公司平等分享市場. 事實上，叫車電話到達(dá)每家公司的派車辦公室的到達(dá)率為每小時8次. 每次乘車的平均時間為12分鐘. 叫車電話按照泊松分布到達(dá)，乘車時間服從指數(shù)分布. 最近這個兩家公司被一個投資商購買了，他打算把這兩個派車辦公室合成一個，以便為顧客提供更為優(yōu)質(zhì)的服務(wù). 請分析老板的建議.從排隊論角度來看，出租車是服務(wù)臺，乘坐出租車就是服務(wù)，每家

48、公司都可以表示為=8次/小時，出租車=60/12=5次/小時乘坐的(M/M/2): (GD/)模型. 合并以后得到(M/M/4): (GD/)模型，其參數(shù)為=16次/小時， =5次/小時.73根據(jù)參數(shù)，利用排隊系統(tǒng)運行性能指標(biāo)計算公式得到下表cp0LsWsLqWq2850.114.4440.5562.8440.35641650.0275.5860.3492.3860.149可以看到，等待乘車的時間在兩臺出租車情況下為0.356，合并后情況為0.149小時，明顯減少了50%多，公司合并以后效果非常明顯.以上的結(jié)論是，共同分擔(dān)服務(wù)總是一種更加有效的運作模式.74(M/M/c):(GD/N/), c

49、 N 模型模型這個模型與(M/M/c):(GD/)模型不同之處在于，系統(tǒng)上限是有限的并且等于N. 這就意味著，最大隊列長度是N-c. 到達(dá)率和服務(wù)率分別是和. 因為系統(tǒng)上限是N,因此有效到達(dá)率小于.按照廣義模型，當(dāng)前模型的nn和定義為,0,0,0,nnnNnncnNccnN將上述 代入穩(wěn)態(tài)概率(第五節(jié))的公式，得到nn和00(),0,1,2!,1,!nncncpncnpccpnc cNc其中75p0的值可以從 求出，得到01Nnnp100()()!1kccNckccpkc 02()1()(1)!(1)(1)(1)1cN cN cqsqNqqNsqpcLNccLLcpLWpWW排隊系統(tǒng)的運行指標(biāo)

50、如下76例例在合并的出租車公司問題中，假設(shè)沒有新的經(jīng)費來購買更多出租車，又一個咨詢專家向老板建議，有一種減少等待時間的辦法是，一旦有6個顧客在等待用車，就讓派車辦公室通知新的顧客，告訴他們等待時間可能會很長. 這種舉動定會讓新的顧客去尋求別的公司的服務(wù)，但將會減少等式顧客的等待時間. 請評價這位專家的建議.將等待的顧客數(shù)限制在6個以內(nèi)就等價于設(shè)定N=6+4=10個顧客. 因此專家建議的排隊模型為(M/M/4):(GD/10/), 其中=16次/小時， =5次/小時.cp0LsWsLqWq41650.031214.23980.27481.15420.0748177在設(shè)置系統(tǒng)能力上限之前的平均等待

51、時間為Wq=0.149小時，大約是新的平均等待時間0.075小時的兩倍. 等待時間的大幅度減少的代價是流失了大約3.6%的潛在顧客(p10=0.03574). 這個結(jié)果還不能反映顧客對公司經(jīng)營印象的損害效果.78(M/M/):(GD/)自助服務(wù)模型自助服務(wù)模型在這個模型中，因為顧客本身也是服務(wù)臺，因此服務(wù)臺數(shù)量無限. 該模型的一個典型例子是參加進(jìn)入系統(tǒng)選課的學(xué)生人數(shù)、在某個行業(yè)的公司數(shù)量. 這個模型假設(shè)穩(wěn)定的到達(dá)率和服務(wù)率分別為和. 按照前面的廣義排隊模型，有,0,1,2,0,1,2,nnnnn因此有0,0,1,2,!nnnppnnp0的值可以從 求出，得到01Nnnp021112!pee!/

52、nnepn 7910,0,qsqsLLWW排隊系統(tǒng)的運行指標(biāo)如下例例一個投資者每月平均投入1000美元購買一種股票市場的債券. 因為這個投資者必須要等待好的“買入”機(jī)會，實際發(fā)生的購買時間是完全隨機(jī)的. 該投資者平均要把債券保留3年，但是當(dāng)好的“賣出”機(jī)會來了，他會在隨機(jī)的時間把它賣掉. 根據(jù)過去的統(tǒng)計表明，這個投資家大約25%的債券每年下跌20%左右，其余的75%每年上漲12%左右. 請估算這個投資者在股票市場的(長期)平均資產(chǎn)凈值.80從實際情況看，這位投資者并不需要排隊等待債券的買入或者賣出. 買賣間隔的平均時間是1個月，因此每年有=12只債券. 債券的銷售率為每年=1/3只債券. 此時

53、每只債券就是就是服務(wù)臺本身，有多少債券就有多少服務(wù)臺，這一情形符合(M/M/):(GD/)模型. 已知 和 ，得到36sL只債券該投資者的預(yù)計(長期)平均年度凈值為 0.25$1000 1 0.200.75$1000 1 0.12$63990ssLL81機(jī)器伺服模型機(jī)器伺服模型 (M/M/R):(GD/K/K), RK這個模型的背景是有K臺機(jī)器的車間，當(dāng)1臺機(jī)器出現(xiàn)故障時，就呼叫R個有時間的修理工之一來進(jìn)行修理. 每臺機(jī)器的故障率為每單位時間次故障，每個修理工修理故障及其的服務(wù)率為每單位時間臺機(jī)器. 所有的故障和服務(wù)假定都服從泊松分布.這個模型類似于前面介紹的(M/M/1):(GD/m)模型模

54、型，區(qū)別在于，本模型中有R個修理工。82本模型有有限個輸入源，原因在于，此時總共有K臺機(jī)器，機(jī)器發(fā)生故障即表示顧客“到達(dá)”，修理工人是服務(wù)員。雖然有K臺機(jī)器，但每個發(fā)生故障的機(jī)器經(jīng)過維修以后回到良好狀態(tài)，但是容易再次發(fā)生故障，所以仍然會有“顧客”到達(dá)。顧客源總數(shù)達(dá)到K時，此時顧客單位時間內(nèi)的到達(dá)次數(shù)依賴于當(dāng)前尚未到達(dá)系統(tǒng)的顧客數(shù)，假設(shè)每個顧客進(jìn)入系統(tǒng)的到達(dá)率為,進(jìn)入系統(tǒng)的顧客(即等待維修的機(jī)器)為n(0nm), 則此時有機(jī)器出現(xiàn)故障的發(fā)生率取決于完好狀態(tài)的機(jī)器數(shù)量K-n.即83,0nKnnK根據(jù)廣義排隊模型，,0,0,0,nnnnRKnnKRRnKnK根據(jù)廣義排隊模型的穩(wěn)態(tài)概率計算公式，可以得

55、到001001,0,!,!KnnnnKnn RnRKKnKnnn Rnn RCpnRpnCpRnKR RnpCCR R 84遺憾的是，在(M/M/R):(GD/K/K) 模型(RK)中, 沒有計算Ls、Lq、Ws和Wq的簡單的、封閉型的表達(dá)式，必須用下面的基本定義來計算：effeff0/KKsnqnssqqnn RLnpLnR pWLWL其中，effsKL例例ToolCo公司經(jīng)營一家22臺機(jī)床的工廠. 已知每臺機(jī)床平均每2小時發(fā)生一次故障，修理工作平均需要12分鐘. 故障間隔時間均服從指數(shù)分布. ToolCo想要確定修理工數(shù)量，以保證工廠能“平穩(wěn)的”運轉(zhuǎn).85要分析該情況，考察作為修理工數(shù)的函

56、數(shù)的機(jī)床生產(chǎn)率，這一生產(chǎn)率的度量可以定義為2210010022sL所有的機(jī)床故障機(jī)床機(jī)床生產(chǎn)率所有機(jī)床該情形屬于(M/M/R):(GD/K/K) 模型，其中=0.5,=5, R=1,2,3,4,系統(tǒng)上限=22, 輸入源=22. 根據(jù)前面的計算公式得到Reffp0LsLqWsWq10.554.9980.000412.00411.0042.4012.201820.558.8160.05644.36772.6040.49540.295430.559.7670.10782.4660.5120.25250.052540.559.950.11992.100.1100.21110.0111修理工R1234機(jī)

57、床生產(chǎn)率45.4480.1588.7990.45邊際增長率34.718.641.6686上述結(jié)果說明，用1個修理工時，生產(chǎn)率很低(45.44%), 把修理工增加到2個時，生產(chǎn)率增加到80.15%，上升了34.71%. 當(dāng)雇用3個修理工時，生產(chǎn)率只增加了8.64%，提高到88.79%，而4個修理工只把生產(chǎn)率增加很小量1.66%，提高到90.45%.從這些結(jié)果可以判斷出，用2個修理工最劃算，用3個修理工的效果不明顯，因為生產(chǎn)率只提高了8.64%. 當(dāng)然我們可以用經(jīng)費上的比較來確定是否劃算，這需要對第三個修理工的成本和8.64%的生產(chǎn)率提高所帶來的收入進(jìn)行比較. 至于雇用第4個修理工，生產(chǎn)率的微量增

58、長1.66%，不支持這樣的計劃。8712.7 一般服務(wù)時間M/G/1模型前面討論的排隊模型到達(dá)時間和服務(wù)時間均服從指數(shù)分布，這類系統(tǒng)的主要特征是Markov特性，即未來狀態(tài)僅由當(dāng)前系統(tǒng)的狀態(tài)決定。但是當(dāng)?shù)竭_(dá)時間間隔和服務(wù)時間間隔至少至少有一個不服從負(fù)指數(shù)分布時，僅靠當(dāng)前狀態(tài)不足以推斷未來狀態(tài)，這樣的排隊模型稱為非馬氏排隊模型。這類排隊模型非常復(fù)雜，對于這類情形的分析，我們將在以后介紹采用模擬方法來研究88(M/G/1):(GD/)排隊模型本節(jié)介紹一個很少出現(xiàn)的具有解析結(jié)果的非泊松排隊. 它所描述的情況是，服務(wù)時間 t 服從任何概率分布，平均值為Et, 方差為Vart. 這個模型的結(jié)果包括系統(tǒng)性

59、能的基本指標(biāo)Ls、Lq、Ws和Wq. 由于公式非常復(fù)雜, 這個模型沒有pn的封閉型表達(dá)式.令為單服務(wù)臺設(shè)施的到達(dá)率，已知服務(wù)時間分布的Et和Vart，并且Et/時，排隊系統(tǒng)處于穩(wěn)態(tài)，依次增加服務(wù)臺個數(shù)，計算Ls及成本，結(jié)果表明，最優(yōu)員工數(shù)為4.( )( )1250( )wsssz cc cc L ccL ccLsz27.467397.3532.217146.8541.842140.1051.769148.4561.754159.7010312.10 排隊網(wǎng)絡(luò)當(dāng)一組資源由一組顧客共享時形成了排隊網(wǎng)絡(luò)。每個資源表示一個可能有多個服務(wù)臺并行工作的服務(wù)中心。如果一個到達(dá)的顧客發(fā)現(xiàn)一個特定的中心繁忙，他

60、可能加入該中心的隊列等候服務(wù)(也可能離開該隊列去尋找其他類型的服務(wù)). 在一站服務(wù)結(jié)束后，該顧客可能轉(zhuǎn)入另一個服務(wù)中心，或者重新進(jìn)入同一個中心，或者離開系統(tǒng)。104在串連隊列中, 一旦一個顧客進(jìn)入系統(tǒng), 他將必須留在系統(tǒng)中直到接受了全套服務(wù)。通常, 每個服務(wù)臺前都運行等候, 前面討論的M/Ek/1模型是這種串連模型的特例, 在M/Ek/1模型中除了第一個服務(wù)臺前可以有等候隊列, 其他的服務(wù)臺是不允許有等候的, 在這種情況下, 必須是n個服務(wù)項目都結(jié)束以后, 一個新的顧客才運行進(jìn)入系統(tǒng)接受服務(wù)。12.10.1 開放排隊系統(tǒng)開放排隊系統(tǒng)串聯(lián)系統(tǒng)或序貫系統(tǒng)105服務(wù)網(wǎng)絡(luò)行為由輸出分布、各服務(wù)臺的服務(wù)時間分布