運(yùn)籌學(xué)導(dǎo)論教學(xué)課件PPT 排隊(duì)系統(tǒng)教學(xué)PPT

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

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

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

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

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

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

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

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

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

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

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

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

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

14、是完全隨機(jī)的？如何理解？假定現(xiàn)在是上午8:20,上一個(gè)顧客到達(dá)時(shí)間是8:02，下一個(gè)到達(dá)發(fā)生在8:29之前的概率只是8:208:29這一區(qū)間的函數(shù)，與上一個(gè)事件的發(fā)生(8:02 8:20)以來(lái)所流逝的時(shí)間長(zhǎng)度完全無(wú)關(guān)。這個(gè)結(jié)果稱(chēng)之為指數(shù)分布的無(wú)記憶性(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) 表示相繼事件之間的時(shí)間t的概率分布。如果s為上一個(gè)事件發(fā)生以來(lái)的時(shí)間區(qū)間，則遺忘性意味著(|)()p tts tsp tt()1()tp ttp

15、tte 而0ss+tstt證明：注意到對(duì)于平均值為1/的指數(shù)函數(shù)，我們有()(|)()()()()tstsp ttstsp tts tsp tsp ttseep ttp tsep(ab)=p(b|a)p(a)25指數(shù)分布的無(wú)記憶性很重要，因?yàn)樗馕吨绻覀兿Ｍ老麓蔚竭_(dá)的時(shí)間概率分布，那么自上次到達(dá)以后流逝的時(shí)間長(zhǎng)短不具有影響。我們假設(shè)到達(dá)時(shí)間間隔服從=6的指數(shù)分布。那么無(wú)記憶特性意味著自上次到達(dá)以后不管經(jīng)過(guò)多長(zhǎng)時(shí)間，那么下一次到達(dá)時(shí)間的概率分布仍然為 6e-6t. 這意味著要觀測(cè)未來(lái)到達(dá)模式，我們不需要跟蹤上一次到達(dá)之后經(jīng)過(guò)了多長(zhǎng)時(shí)間。這種觀測(cè)可以簡(jiǎn)化排隊(duì)系統(tǒng)的分析。這種觀測(cè)可以簡(jiǎn)化排隊(duì)

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

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

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

19、，有30重新安排各項(xiàng)并取當(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個(gè)到達(dá)的泊松分布(poisson distribution) 上面的結(jié)果說(shuō)明,若到達(dá)時(shí)間間隔服從平均值為1/的指數(shù)分布，則指定期間 t 內(nèi)的到達(dá)數(shù)服從平均值t的泊松分布. 反之亦然.31指數(shù)分布指數(shù)分布泊松分布泊松分布隨機(jī)變量相繼到達(dá)之間的時(shí)間 t指定 t 期間的到達(dá)數(shù) n取值范圍t 0n= 0,1,

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

21、率可以用泊松分布計(jì)算為24 60120/12人 天120 36543800/t人 年 0120 11200120 1100!epe假設(shè)在3個(gè)小時(shí)內(nèi)的前2小時(shí)已經(jīng)發(fā)出了40份出生證明，計(jì)算3小時(shí)內(nèi)發(fā)出50份出生證明的概率，相當(dāng)于1小時(shí)(=3-2)內(nèi)出生10(=50-40)個(gè)新生兒，因?yàn)槌錾鷶?shù)的分布是泊松的. 105 1105 110.0181310!ep 3312.4.2 純滅模型純滅模型在純滅模型中，系統(tǒng)在0時(shí)刻開(kāi)始時(shí)有n個(gè)顧客，后面沒(méi)有新的顧客到達(dá). 離開(kāi)的發(fā)生率為每單位個(gè)顧客. 為了建立t時(shí)間單位后剩下n個(gè)顧客的概率pn(t)的差分-微分方程，根據(jù)出現(xiàn)n個(gè)顧客的情況，依據(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)過(guò) t 時(shí)間還剩下 n 個(gè)顧客的概率35例例某雜貨店鮮花柜臺(tái)每周初庫(kù)存18打玫瑰花. 平均情況下，鮮花柜臺(tái)每天賣(mài)出去3打(一次一打)，但實(shí)際需求量服從泊松分布. 一旦庫(kù)存水

23、平剩下5打，就再訂貨補(bǔ)充到18打，下周一送貨。由于鮮花商品的特性，周末沒(méi)有賣(mài)出的玫瑰花就要扔掉，求下列值：(1) 該周內(nèi)任何一天訂貨的概率.(2) 周末扔掉的玫瑰花的平均數(shù)量.36因?yàn)橘?gòu)買(mǎi)的發(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). 為了計(jì)算這個(gè)值, 我們需要用

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

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

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

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

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

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

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

31、分布，g=服務(wù)時(shí)間的一般性/通用分布排隊(duì)規(guī)則排隊(duì)規(guī)則(符號(hào)符號(hào)d)包括包括fcfs=先到先服務(wù)，lcfs=后到先服務(wù)，siro=隨機(jī)秩序服務(wù)，gd=一般/任意規(guī)則(m/d/10): (gd/20/), (m/e2/8/):(fcfs/10/)4812.6.2 隊(duì)列行為的平穩(wěn)狀態(tài)度量ls=系統(tǒng)中顧客的期望數(shù)量lq=隊(duì)列中顧客的期望數(shù)量ws=系統(tǒng)中的期望等待時(shí)間wq=隊(duì)列中的期望等待時(shí)間 =繁忙服務(wù)臺(tái)的期望數(shù)c最常用的隊(duì)列行為度量指標(biāo)有系統(tǒng)包括隊(duì)列加上服務(wù)設(shè)施。下面說(shuō)明如何利用系統(tǒng)的狀態(tài) n 及其平穩(wěn)狀態(tài)概率pn得到上述的度量指標(biāo)。49首先根據(jù)數(shù)學(xué)期望得到11snnqnn clnplnc p 系統(tǒng)

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

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

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

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

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

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

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

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

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

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

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

43、間是有限的.當(dāng)系統(tǒng)中的顧客數(shù)達(dá)到 n 時(shí)，不允許再有到達(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 在這個(gè)模型中, 的值不需要小于1, 因?yàn)橄到y(tǒng)的到達(dá)受到系統(tǒng)顧客上限 n 的限制. 這意味著在這種情況下, 重要的是到達(dá)率eff而不是. 由于系統(tǒng)中有 n 個(gè)顧客，再來(lái)的顧客就不再進(jìn)入系統(tǒng). 此時(shí)/ lostefflost(1)nnpp系統(tǒng)中期望顧客數(shù)可以計(jì)算為110001111111

44、11 (1)11,11111nnnnnsnnnnnnnnnnndlnpndnndd當(dāng) 時(shí)，ls=n/2. 同樣從ls, 利用eff求出ws, wq, lq.110110(1)(1)(1),111(1)1/nnqnsnnssqsnlnplplwpww66(m/m/1):(gd/m)模型模型這個(gè)模型和(m/m/1):(gd/)不同之處在于，系統(tǒng)的顧客源的顧客總數(shù)為m. 例如最常見(jiàn)的是機(jī)器發(fā)生故障停機(jī)待修的問(wèn)題，此時(shí)總共有m臺(tái)機(jī)器，機(jī)器發(fā)生故障即表示顧客“到達(dá)”，修理工人是服務(wù)員，類(lèi)似的問(wèn)題還有m個(gè)打字員共有一臺(tái)打字機(jī)。雖然顧客有m個(gè)，但每個(gè)顧客到達(dá)并經(jīng)過(guò)服務(wù)以后，仍然回到原來(lái)的發(fā)生源中，所以仍然會(huì)

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

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

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

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

49、n 模型模型這個(gè)模型與(m/m/c):(gd/)模型不同之處在于，系統(tǒng)上限是有限的并且等于n. 這就意味著，最大隊(duì)列長(zhǎng)度是n-c. 到達(dá)率和服務(wù)率分別是和. 因?yàn)橄到y(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排隊(duì)系統(tǒng)的運(yùn)行指標(biāo)如

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

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

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

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

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

55、001001,0,!,!knnnnknn rnrkknknnn rnn rcpnrpncprnkr rnpccr r 84遺憾的是，在(m/m/r):(gd/k/k) 模型(rk)中, 沒(méi)有計(jì)算ls、lq、ws和wq的簡(jiǎn)單的、封閉型的表達(dá)式，必須用下面的基本定義來(lái)計(jì)算：effeff0/kksnqnssqqnn rlnplnr pwlwl其中，effskl例例toolco公司經(jīng)營(yíng)一家22臺(tái)機(jī)床的工廠. 已知每臺(tái)機(jī)床平均每2小時(shí)發(fā)生一次故障，修理工作平均需要12分鐘. 故障間隔時(shí)間均服從指數(shù)分布. toolco想要確定修理工數(shù)量，以保證工廠能“平穩(wěn)的”運(yùn)轉(zhuǎn).85要分析該情況，考察作為修理工數(shù)的函數(shù)

56、的機(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ù)前面的計(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邊際增長(zhǎng)率34.718.641.6686上述結(jié)果說(shuō)明，用1個(gè)修理工時(shí)，生產(chǎn)率很低(45.44%), 把修理工增加到2個(gè)時(shí)，生產(chǎn)率增加到80.15%，上升了34.71%. 當(dāng)雇用3個(gè)修理工時(shí)，生產(chǎn)率只增加了8.64%，提高到88.79%，而4個(gè)修理工只把生產(chǎn)率增加很小量1.66%，提高到90.45%.從這些結(jié)果可以判斷出，用2個(gè)修理工最劃算，用3個(gè)修理工的效果不明顯，因?yàn)樯a(chǎn)率只提高了8.64%. 當(dāng)然我們可以用經(jīng)費(fèi)上的比較來(lái)確定是否劃算，這需要對(duì)第三個(gè)修理工的成本和8.64%的生產(chǎn)率提高所帶來(lái)的收入進(jìn)行比較. 至于雇用第4個(gè)修理工，生產(chǎn)率的微量增長(zhǎng)

58、1.66%，不支持這樣的計(jì)劃。8712.7 如何斷定泊松分布和指數(shù)分布之前介紹的各種排隊(duì)模型均要求到達(dá)和服務(wù)間隔時(shí)間服從指數(shù)分布，也就是到達(dá)個(gè)數(shù)服從泊松分布。在實(shí)際中，有時(shí)不能預(yù)知總體服從什么類(lèi)型的分布。那么，如何判斷到達(dá)的顧客是服從泊松分布或者是指數(shù)分布的？這就需要根據(jù)樣本來(lái)檢驗(yàn)關(guān)于分布的假設(shè)。本節(jié)介紹最常見(jiàn)的方法2分布擬合檢驗(yàn)法882檢驗(yàn)法的預(yù)處理根據(jù)樣本 x1, x2,xn 來(lái)檢驗(yàn)關(guān)于總體分布的假設(shè)h0：總體 x 的分布函數(shù)為f(x)，h1：總體 x 的分布函數(shù)不是f(x),這里被擇假設(shè)h1可以不需要寫(xiě)出. 注意，如果總體 x 為離散型則假設(shè)(1)相當(dāng)于 h0：總體 x 的分布律為px=

59、ti=pi,i=1,2,如果總體 x 為連續(xù)型，則假設(shè)(1)相當(dāng)于 h0：總體x的概率密度函數(shù)為f(x)在用 檢驗(yàn)假設(shè)h0時(shí)，若在假設(shè)h0下f(x)的形式已知，當(dāng)其參數(shù)值未知，這需要用極大似然估計(jì)法估計(jì)參數(shù)，然后做檢驗(yàn).(1)(2)(3)2檢驗(yàn)法892檢驗(yàn)法的基本思想將隨機(jī)試驗(yàn)可能結(jié)果的全體分為 k 個(gè)互不相容的事件于是在假設(shè)h0下，我們可以計(jì)算在n次試驗(yàn)中，事件ai出現(xiàn)的頻率fi/n與 往往有差異，但一般來(lái)說(shuō)，若h0為真，且試驗(yàn)的次數(shù)有較多的時(shí)，則這種差異應(yīng)該不是很大. 基于這種想法，皮爾遜使用121,., ,1,2,kkiijia aaaa aij i jk ,1,2,.iiiipp ap

60、p aik（或iipp或222211kkiiiiiiiifnpfnpnpnp或（4）90定理定理 若n充分大(n50), 則當(dāng)h0為真時(shí)(不論h0中的分布屬于什么分布)，統(tǒng)計(jì)量(4)總是近似地服從自由度為于是，若在假設(shè)h0下算得(4)有則在顯著性水平 下接受h0，否則就拒絕h0是基于上述定理得到的，所以在使用時(shí)必須注意 n 要足夠大，以及 npi不太小. 根據(jù)實(shí)踐，要求樣本容量不小于50，以及每一個(gè) npi 都不小于5，而且 npi 最好是在5以上。否則應(yīng)適當(dāng)?shù)睾喜?ai，以滿足這個(gè)要求.21.krr 的分布,其中, 是被估計(jì)的參數(shù)的個(gè)數(shù)221akr 91例例在一個(gè)實(shí)驗(yàn)中，每隔一定時(shí)間觀察一次