運(yùn)籌學(xué)導(dǎo)論第八版12排隊(duì)論課件

1第12章排隊(duì)系統(tǒng)1第12章排隊(duì)系統(tǒng)2AgnerKrarupErlang1878-1929丹麥電信工程師，排隊(duì)論之父研究人們打電話的方式，發(fā)展出人們需要等待多久的公式，并于1909年出版了關(guān)于排隊(duì)理論的第一篇論文2AgnerKrarupErlang研究人們打電話的方式3UCLA,LeonardKleinrock1934—“互聯(lián)網(wǎng)之父”，“影響本世紀(jì)的50人”UCLA,

JamesR.Jackson1924—2011排隊(duì)網(wǎng)絡(luò)之父排隊(duì)論煥發(fā)了新的生命力，影響巨大！3UCLA,LeonardKleinrockUCLA,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ù)、城市中隨時(shí)可能有急診病人等待救護(hù)車(chē)的救援、港口外多艘萬(wàn)噸級(jí)船舶等待進(jìn)港裝卸貨物、等待加工的零部件、等待裝配的汽車(chē)等等。排隊(duì)現(xiàn)象無(wú)處不在！12.1為什么要研究排隊(duì)系統(tǒng)4生活在城市中的居民在生產(chǎn)、生活以及學(xué)習(xí)消費(fèi)的過(guò)程中，存在大5排隊(duì)現(xiàn)象的特征是：顧客以某種隨機(jī)方式到達(dá)一個(gè)服務(wù)設(shè)施，之后在隊(duì)列中等待，直到他們接受服務(wù)。一旦服務(wù)結(jié)束，通常離開(kāi)系統(tǒng)。不花費(fèi)極大的成本，等待現(xiàn)象是不可能完全消除的，我們的目標(biāo)是要把他的不利影響減小到“可以忍受的”程度。5排隊(duì)現(xiàn)象的特征是：顧客以某種隨機(jī)方式到達(dá)一個(gè)服務(wù)設(shè)施，之后667為什么會(huì)產(chǎn)生排隊(duì)現(xiàn)象？泛泛地說(shuō)，是由于顧客需求量大于設(shè)施能提供的服務(wù)量。究竟又是什么原因?qū)е路?wù)設(shè)施的服務(wù)不足？原因很多，例如缺少服務(wù)點(diǎn)、提供的更多服務(wù)則經(jīng)濟(jì)上不可行、空間限制無(wú)法容納更多的服務(wù)臺(tái)。一般來(lái)說(shuō)，當(dāng)然可以通過(guò)增加投資建設(shè)更多的服務(wù)設(shè)施消除上述因素，但這需要分析“應(yīng)該再增加多少服務(wù)臺(tái)才可以消除排隊(duì)？”。這就需要回答諸如“一個(gè)顧客必須要等待多久？”、“排隊(duì)長(zhǎng)度會(huì)有多長(zhǎng)？”等很多問(wèn)題。7為什么會(huì)產(chǎn)生排隊(duì)現(xià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í)間16.210.36.94.82.91.91.3仔細(xì)觀察這些數(shù)據(jù)，在3個(gè)柜臺(tái)的情況下，平均等待時(shí)間要7分鐘。需要5個(gè)柜臺(tái)才能把等待時(shí)間減少到3分鐘。排隊(duì)分析的結(jié)果可以用在費(fèi)用優(yōu)化模型中，即求兩種費(fèi)用(服務(wù)費(fèi)用和等待費(fèi)用)之和的最小值。如下圖8例收款臺(tái)數(shù)1234567平均等待時(shí)間16.210.36.99顧客等待時(shí)間成本服務(wù)時(shí)間成本總費(fèi)用服務(wù)水平費(fèi)用最優(yōu)服務(wù)水平上圖顯示了一個(gè)典型的費(fèi)用模型，使用費(fèi)用模型的主要障礙就是很難估計(jì)可靠的等待費(fèi)用，特別是當(dāng)人的行為成為操作的有機(jī)組成部分時(shí)。9顧客等待時(shí)間成本服務(wù)時(shí)間成本總費(fèi)用服務(wù)水平費(fèi)用最優(yōu)服務(wù)水平10分析排隊(duì)系統(tǒng)的最終目的是為了對(duì)排隊(duì)等待的顧客提供滿(mǎn)意的服務(wù)。排隊(duì)論主要研究服務(wù)設(shè)施的需求與用戶(hù)延誤之間的關(guān)系，其在分析和規(guī)劃城市服務(wù)設(shè)施扮演重要角色，例如地鐵閘機(jī)的設(shè)置、消防站及消防車(chē)的配置以及醫(yī)療救護(hù)點(diǎn)配置等等；在工業(yè)上的用途包括生產(chǎn)線的設(shè)計(jì)及布置、加工設(shè)備的配置；服務(wù)業(yè)中服務(wù)人員、柜臺(tái)的設(shè)置及調(diào)配。研究排隊(duì)論的目的10分析排隊(duì)系統(tǒng)的最終目的是為了對(duì)排隊(duì)等待的顧客提供滿(mǎn)意的服11排隊(duì)論，作為運(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í)施；為了充分理解排隊(duì)系統(tǒng)的實(shí)際問(wèn)題，就需要了解相當(dāng)?shù)幕A(chǔ)理論背景。為此，首先介紹下構(gòu)成排隊(duì)系統(tǒng)的基本要素，然后介紹兩個(gè)重要分布(泊松和指數(shù)分布)的“完全隨機(jī)”性質(zhì)。11排隊(duì)論，作為運(yùn)籌學(xué)的重要分支，并不是一種優(yōu)化理論。而是12一個(gè)排隊(duì)系統(tǒng)中的主要參與者是顧客和服務(wù)臺(tái)。顧客從某個(gè)輸入源產(chǎn)生，到達(dá)一個(gè)服務(wù)設(shè)施，他們可以立即得到服務(wù)；假如服務(wù)設(shè)施繁忙，也可能在隊(duì)列中等待，當(dāng)一個(gè)設(shè)施完成一次服務(wù)，如果有顧客等待的話，自動(dòng)地“拉出”一個(gè)等待顧客；假如隊(duì)列為空，設(shè)施就變成空閑，直到一個(gè)新的顧客到達(dá)。從分析隊(duì)列的角度，我們用連續(xù)兩個(gè)顧客之間的到達(dá)時(shí)間間隔表示顧客的到達(dá)，用對(duì)每個(gè)顧客的服務(wù)時(shí)間來(lái)描述服務(wù)。12.2排隊(duì)模型的要素12一個(gè)排隊(duì)系統(tǒng)中的主要參與者是顧客和服務(wù)臺(tái)。顧客從某個(gè)輸入13組成排隊(duì)系統(tǒng)的要素至少包括：顧客輸入源、隊(duì)列以及服務(wù)臺(tái)，而服務(wù)臺(tái)可以是單個(gè)的，也可以是多個(gè)并行聯(lián)接的。如果要全面而準(zhǔn)確的描述一個(gè)排隊(duì)系統(tǒng)，則需要有如下6個(gè)要素：（1）顧客到達(dá)模式（顧客發(fā)生源類(lèi)型）；（2）服務(wù)臺(tái)服務(wù)模式（服務(wù)臺(tái)服務(wù)方式）；（3）排隊(duì)規(guī)則；（4）排隊(duì)系統(tǒng)容量；（5）服務(wù)通道數(shù)量；（6）服務(wù)階段數(shù)量。13組成排隊(duì)系統(tǒng)的要素至少包括：顧客輸入源、隊(duì)列以及服務(wù)臺(tái)，1412.2.1顧客到達(dá)模式排隊(duì)系統(tǒng)的顧客輸入源常常以單位時(shí)間內(nèi)到達(dá)顧客的平均數(shù)量（meanarrivalrate），兩個(gè)連續(xù)顧客之間的平均到達(dá)間隔時(shí)間（meaninterarrivaltime）來(lái)描述。進(jìn)入排隊(duì)系統(tǒng)的顧客流可以是確定型的，此時(shí)完全可以用平均到達(dá)率或者平均間隔時(shí)間來(lái)表示；如果進(jìn)入排隊(duì)系統(tǒng)的顧客流存在不確定性，此時(shí)用平均到達(dá)率或者平均間隔時(shí)間，僅能描述輸入顧客的隨機(jī)過(guò)程的集體趨勢(shì)，如果要進(jìn)一步完整地描述顧客到達(dá)模式，則需要顧客到達(dá)隨機(jī)變量的概率分布。顧客到達(dá)模式可能不是一次到達(dá)一個(gè)顧客，而是一批一批到達(dá)的，此時(shí)相鄰批次到達(dá)的間隔時(shí)間可能是隨機(jī)的，每批次的顧客數(shù)量也是隨機(jī)的。1412.2.1顧客到達(dá)模式排隊(duì)系統(tǒng)的顧客輸入源常常以單15不同類(lèi)型的顧客對(duì)于進(jìn)入排隊(duì)系統(tǒng)有不同的反應(yīng)有些顧客將一直在隊(duì)列中等待直到獲得服務(wù)才離開(kāi)；有些顧客會(huì)認(rèn)為隊(duì)列太長(zhǎng)而不進(jìn)入排隊(duì)系統(tǒng)直接離開(kāi)；有些顧客則是到了排隊(duì)系統(tǒng)臨時(shí)決定不參加排隊(duì)；有些顧客則參與排隊(duì)，但是失去耐心后決定離開(kāi)系統(tǒng)；而有時(shí)候在服務(wù)臺(tái)前有兩列或更多的隊(duì)列，則有些類(lèi)型的顧客在不同隊(duì)列之間來(lái)回排隊(duì)，以縮短期望排隊(duì)時(shí)間。（后4種情況被認(rèn)為是急躁型的顧客）如果顧客到達(dá)模式不隨時(shí)間改變（隨機(jī)型到達(dá)模式的參數(shù)不隨時(shí)間變化），則認(rèn)為是平穩(wěn)的；反之則為非平穩(wěn)的。

15不同類(lèi)型的顧客對(duì)于進(jìn)入排隊(duì)系統(tǒng)有不同的反應(yīng)16服務(wù)率以單位時(shí)間內(nèi)服務(wù)的顧客數(shù)量以服務(wù)一個(gè)顧客需要的時(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ù)單個(gè)，每次只能服務(wù)一個(gè)顧客多個(gè)，可以同時(shí)服務(wù)多個(gè)顧客12.2.2服務(wù)臺(tái)服務(wù)模式16服務(wù)率12.2.2服務(wù)臺(tái)服務(wù)模式17先到先服務(wù)（Firstcome,Firstserved），先進(jìn)先出（Firstin,Firstout）后到先服務(wù)（Lastcome,Firstserved），庫(kù)存系統(tǒng)。隨機(jī)順序服務(wù)（Serviceinrandomorder,SIRO），該規(guī)則不考慮顧客到達(dá)先后順序，隨機(jī)地選擇顧客進(jìn)行服務(wù)。優(yōu)先權(quán)排隊(duì)規(guī)則絕對(duì)搶先式，具有最高優(yōu)先級(jí)的顧客即刻獲得服務(wù)非絕對(duì)搶先式，具有最高級(jí)別的顧客即刻在隊(duì)列的最前端排隊(duì)，但不能馬上接受服務(wù)，直到當(dāng)前顧客（即使其級(jí)別較低）服務(wù)結(jié)束以后才能接受服務(wù)12.2.3排隊(duì)規(guī)則在出現(xiàn)顧客排隊(duì)的情況下，選擇顧客進(jìn)行服務(wù)的選擇機(jī)制。17先到先服務(wù)（Firstcome,Firstserv18在有些排隊(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)容量18在有些排隊(duì)系統(tǒng)中，其排隊(duì)等候區(qū)域受到物理空間限制，當(dāng)隊(duì)列19只有1個(gè)服務(wù)臺(tái)的系統(tǒng)為單通道服務(wù)系統(tǒng)，在服務(wù)設(shè)施內(nèi)設(shè)置多個(gè)并行的服務(wù)臺(tái)是多通道服務(wù)系統(tǒng)。兩類(lèi)不同的多通道服務(wù)系統(tǒng)，一般來(lái)說(shuō)，在排隊(duì)論中都假設(shè)服務(wù)臺(tái)是相互獨(dú)立運(yùn)作的多個(gè)服務(wù)臺(tái)共同為一個(gè)隊(duì)列服務(wù)每個(gè)服務(wù)臺(tái)僅為本隊(duì)列提供服務(wù)12.2.5服務(wù)通道數(shù)量在同一時(shí)刻能為顧客提供服務(wù)的并行服務(wù)臺(tái)數(shù)量19只有1個(gè)服務(wù)臺(tái)的系統(tǒng)為單通道服務(wù)系統(tǒng)，在服務(wù)設(shè)施內(nèi)設(shè)置多20排隊(duì)系統(tǒng)中，許多服務(wù)設(shè)施提供的服務(wù)級(jí)數(shù)包括兩類(lèi)單級(jí)的，例如高速公路收費(fèi)站、車(chē)站檢票口等；多級(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ù)20排隊(duì)系統(tǒng)中，許多服務(wù)設(shè)施提供的服務(wù)級(jí)數(shù)包括兩類(lèi)12.2.21上述6個(gè)排隊(duì)系統(tǒng)基本特征元素，一般的可以充分的描述各種排隊(duì)過(guò)程。從上述介紹也可以看出排隊(duì)過(guò)程無(wú)處不在。排隊(duì)模型的要素的總結(jié)必須充分理解排隊(duì)系統(tǒng)的這6個(gè)特征元素，以清楚掌握排隊(duì)系統(tǒng)的運(yùn)作過(guò)程，具體包括排隊(duì)通道和服務(wù)設(shè)施之間是如何相互連接和影響的，顧客又是如何被分配到排隊(duì)通道中的。21上述6個(gè)排隊(duì)系統(tǒng)基本特征元素，一般的可以充分的描述各種排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í)間和服務(wù)時(shí)間用指數(shù)分布來(lái)定量描述，定義為對(duì)于指數(shù)分布(exponentialdistribution)λ為單位時(shí)間內(nèi)產(chǎn)生事件的速率。2212.3指數(shù)分布的作用在大多數(shù)排隊(duì)情況中，顧客的到達(dá)23為什么指數(shù)分布是完全隨機(jī)的？如何理解？假定現(xiàn)在是上午8:20,上一個(gè)顧客到達(dá)時(shí)間是8:02，下一個(gè)到達(dá)發(fā)生在8:29之前的概率只是8:20~8: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:2923為什么指數(shù)分布是完全隨機(jī)的？如何理解？8:028:20824令指數(shù)分布f(t)表示相繼事件之間的時(shí)間t的概率分布。如果S為上一個(gè)事件發(fā)生以來(lái)的時(shí)間區(qū)間，則遺忘性意味著而0SS+TSTt證明：注意到對(duì)于平均值為1/λ的指數(shù)函數(shù)，我們有P(AB)=P(B|A)P(A)24令指數(shù)分布f(t)表示相繼事件之間的時(shí)間t的概率分布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)的分析。25指數(shù)分布的無(wú)記憶性很重要，因?yàn)樗馕吨绻覀兿Ｍ老?6例假設(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分鐘，其概率正好是26例2712.4生滅模型排隊(duì)系統(tǒng)中，任意時(shí)間它的狀態(tài)用這個(gè)時(shí)間在系統(tǒng)中的人數(shù)表示。則該狀態(tài)取決于各個(gè)時(shí)刻進(jìn)入和離開(kāi)人數(shù)的速率，這樣的系統(tǒng)稱(chēng)之為生滅過(guò)程。生滅過(guò)程例子很多，地區(qū)的人口增減、細(xì)菌或細(xì)胞的繁殖與死亡、服務(wù)臺(tái)前的顧客數(shù)量變化等等。為了簡(jiǎn)化，只考慮只有到達(dá)的純生模型和只有離開(kāi)的純滅模型。純生模型的例子如為新生嬰兒制作出生證明，純滅模型的例子如一家商店對(duì)其庫(kù)存貨物的隨機(jī)提貨。2712.4生滅模型排隊(duì)系統(tǒng)中，任意時(shí)間它的狀態(tài)用這個(gè)時(shí)2812.4.1純生模型定義

p0(t)=t時(shí)期內(nèi)沒(méi)有到達(dá)的概率已知到達(dá)時(shí)間間隔是指數(shù)分布的，并且每單位時(shí)間顧客到達(dá)率為λ，則對(duì)于一個(gè)充分小的時(shí)間區(qū)間h>0,根據(jù)泰勒級(jí)數(shù)展開(kāi)，有指數(shù)分布基于假設(shè)：在充分小的h>0期間，最多有一個(gè)事件能夠發(fā)生。因此，當(dāng)h→0，這一結(jié)果表示，h期間一次到達(dá)的概率與h成正比例，到達(dá)率λ為比例常數(shù)。2812.4.1純生模型定義對(duì)于一個(gè)充分小的時(shí)間區(qū)間h>29定義某期間t

內(nèi)到達(dá)數(shù)目的分布pn(t)pn(t)=t

期間內(nèi)有n

個(gè)到達(dá)的概率在t

期間內(nèi)有n

個(gè)顧客的組合，包括以下兩種情況：t+h(0,t)(0,t+h)nn0n-11000對(duì)于充分小的h>0,根據(jù)互不相容的全概率公式，有29定義某期間t內(nèi)到達(dá)數(shù)目的分布pn(t)t+h(0,30重新安排各項(xiàng)并取當(dāng)h→0的極限，得到其中是pn(t)關(guān)于t的一階導(dǎo)數(shù).

求解上述差分-微分方程，得到

這正是t期間平均有E(n|t)=λt個(gè)到達(dá)的泊松分布(Poissondistribution)

上面的結(jié)果說(shuō)明,若到達(dá)時(shí)間間隔服從平均值為1/λ的指數(shù)分布，則指定期間t內(nèi)的到達(dá)數(shù)服從平均值λt的泊松分布.反之亦然.30重新安排各項(xiàng)并取當(dāng)h→0的極限，得到其中31指數(shù)分布泊松分布隨機(jī)變量相繼到達(dá)之間的時(shí)間t指定T期間的到達(dá)數(shù)n取值范圍t≥0n=0,1,2,┅密度函數(shù)平均值1/λ時(shí)間單元T期間有λT個(gè)到達(dá)累積概率P(A期間無(wú)達(dá)到)指數(shù)分布與泊松分布之間的關(guān)系31指數(shù)分布泊松分布隨機(jī)變量相繼到達(dá)之間的時(shí)間t指定T32例某人口稀少州的出生率為每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)有新生兒出生的概率可以用泊松分布計(jì)算為假設(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ù)的分布是泊松的.32例假設(shè)在3個(gè)小時(shí)內(nèi)的前2小時(shí)已經(jīng)發(fā)出了40份出生證明，計(jì)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ù)不相容的全概率公式，有t+h(0,t)(0,t+h)NN0nn0n+110003312.4.2純滅模型在純滅模型中，系統(tǒng)在0時(shí)刻開(kāi)始時(shí)有當(dāng)h→0,得到這組方程的解得到下面的截尾泊松(TruncatedPoisson)分布:經(jīng)過(guò)t

時(shí)間還剩下n

個(gè)顧客的概率當(dāng)h→0,得到這組方程的解得到下面的截尾泊松(Trunca35例某雜貨店鮮花柜臺(tái)每周初庫(kù)存18打玫瑰花.平均情況下，鮮花柜臺(tái)每天賣(mài)出去3打(一次一打)，但實(shí)際需求量服從泊松分布.一旦庫(kù)存水平剩下5打，就再訂貨補(bǔ)充到18打，下周一送貨。由于鮮花商品的特性，周末沒(méi)有賣(mài)出的玫瑰花就要扔掉，求下列值：(1)該周內(nèi)任何一天訂貨的概率.(2)周末扔掉的玫瑰花的平均數(shù)量.35例36因?yàn)橘?gòu)買(mǎi)的發(fā)生率為每天μ=3打，t日結(jié)束前訂貨的概率為t(星期幾)1234567μt36912151821pn≤5(t)0.0000.00880.12420.42400.73240.90830.9755輸出結(jié)果如下：周末(t=7)扔掉的玫瑰花平均數(shù)為E(n|t=7).為了計(jì)算這個(gè)值,我們需要用到pn(7),n=1,2,…,18,計(jì)算結(jié)果為36因?yàn)橘?gòu)買(mǎi)的發(fā)生率為每天μ=3打，t日結(jié)束前訂貨的概率為3712.5廣義泊松排隊(duì)模型本節(jié)利用生滅模型，建立一個(gè)通用的排隊(duì)模型。再根據(jù)到達(dá)間隔和服務(wù)時(shí)間服從指數(shù)分布，推導(dǎo)出基于泊松分布的排隊(duì)論模型。廣義模型的建立是基于排隊(duì)情形的長(zhǎng)期行為，或平穩(wěn)狀態(tài)行為，這種狀態(tài)在系統(tǒng)經(jīng)過(guò)充分長(zhǎng)時(shí)間的運(yùn)行后得到的。這種分析和系統(tǒng)初期運(yùn)行期間所常見(jiàn)的瞬時(shí)(transient)行為完全不同。本章不討論瞬時(shí)行為的一個(gè)原因是由于對(duì)它的解析過(guò)于復(fù)雜；另一個(gè)原因是由于對(duì)大多數(shù)排隊(duì)系統(tǒng)都是在平穩(wěn)狀態(tài)下來(lái)研究的。3712.5廣義泊松排隊(duì)模型本節(jié)利用生滅模型，建立一個(gè)通38廣義模型假設(shè)，到達(dá)率和離開(kāi)率都是與狀態(tài)相關(guān)的(statedependent),也就說(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)也是依賴(là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è)備利用率.38廣義模型假設(shè)，到達(dá)率和離開(kāi)率都是與狀態(tài)相關(guān)的(state39如果以系統(tǒng)中的顧客數(shù)量來(lái)表示系統(tǒng)的狀態(tài)，那么令排隊(duì)系統(tǒng)中有n個(gè)用戶(hù)的概率為pn.那么概率pn可以用下圖的狀態(tài)轉(zhuǎn)移關(guān)系圖來(lái)得到.

根據(jù)第3小節(jié)的解釋?zhuān)谝粋€(gè)時(shí)間間隔h里多于1個(gè)事件發(fā)生的概率隨著h→0而趨于0.這就意味著，對(duì)于n>0,狀態(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)有定義.012n-1nn+1…39如果以系統(tǒng)中的顧客數(shù)量來(lái)表示系統(tǒng)的狀態(tài)，那么令排隊(duì)系統(tǒng)中40當(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ù)要相等。所以，狀態(tài)n

只能變成狀態(tài)(n-1)和狀態(tài)(n+1),因此有類(lèi)似地系統(tǒng)平穩(wěn)狀態(tài)下，單位時(shí)間內(nèi)轉(zhuǎn)入和轉(zhuǎn)出次數(shù)要相等對(duì)于n=0的平衡方程為n-1nn+140當(dāng)系統(tǒng)處于平穩(wěn)狀態(tài)條件下，轉(zhuǎn)入率等于轉(zhuǎn)出率，也就說(shuō)單位時(shí)41從p0開(kāi)始遞歸求解平衡方程如下：對(duì)于n=0，有接下來(lái)，對(duì)n=1，有用替換并化簡(jiǎn)，得到用歸納法可以得到如下廣義穩(wěn)態(tài)概率公式從p0的值可以從等式求出.41從p0開(kāi)始遞歸求解平衡方程如下：對(duì)于n=0，有接下來(lái)，42解得42解得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ù)1~314~626人以上3根據(jù)本題的信息，有43例店內(nèi)顧客數(shù)量使用收款臺(tái)的個(gè)數(shù)1~314~626人以上344因此p0的值從下面的等式求出利用幾何級(jí)數(shù)得到44因此p0的值從下面的等式求出利用幾何級(jí)數(shù)45因此，p0=1/55.知道了p0，就可以求出pn.進(jìn)而可以計(jì)算出系統(tǒng)中使用不同收款臺(tái)個(gè)數(shù)的概率.例如使用一個(gè)收款臺(tái)的概率就是最多出現(xiàn)3個(gè)顧客的概率=p1+p2+p345因此，p0=1/55.知道了p0，就可以求出pn.4612.6特殊泊松排隊(duì)12.6.1排隊(duì)系統(tǒng)的Kendall-Lee的符號(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...4612.6特殊泊松排隊(duì)12.6.1排隊(duì)系統(tǒng)的Ken47為了方便表示上圖排隊(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)分布(a和b)的標(biāo)準(zhǔn)記號(hào)有M=馬爾科夫或泊松分布，D=常數(shù)(確定型)時(shí)間，Ek=參數(shù)為k的埃爾朗或Γ分布(等價(jià)于獨(dú)立指數(shù)分布和)，GI=到達(dá)間隔時(shí)間的一般性/通用分布，G=服務(wù)時(shí)間的一般性/通用分布排隊(duì)規(guī)則(符號(hào)d)包括FCFS=先到先服務(wù)，LCFS=后到先服務(wù)，SIRO=隨機(jī)秩序服務(wù)，GD=一般/任意規(guī)則(M/D/10):(GD/20/∞),(M/E2/8/):(FCFS/10/∞)47為了方便表示上圖排隊(duì)的情形的特性，采用下面的格式(M/D4812.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ù)最常用的隊(duì)列行為度量指標(biāo)有系統(tǒng)包括隊(duì)列加上服務(wù)設(shè)施。下面說(shuō)明如何利用系統(tǒng)的狀態(tài)n

及其平穩(wěn)狀態(tài)概率pn得到上述的度量指標(biāo)。4812.6.2隊(duì)列行為的平穩(wěn)狀態(tài)度量Ls=系統(tǒng)中顧客的49首先根據(jù)數(shù)學(xué)期望得到系統(tǒng)中期望的顧客數(shù)隊(duì)列中期望的顧客數(shù)(平均隊(duì)長(zhǎng))而Ls與Ws(以及Lq與Wq)之間的關(guān)系稱(chēng)為L(zhǎng)ittle公式(littleformula),具體關(guān)系包括如下系統(tǒng)中平均顧客數(shù)量與駐留系統(tǒng)的時(shí)間之間滿(mǎn)足：隊(duì)列中期望的顧客數(shù)(平均隊(duì)長(zhǎng))與排隊(duì)時(shí)間滿(mǎn)足：上述關(guān)系在相當(dāng)一般的條件下成立。參數(shù)λeff

是系統(tǒng)的有效到達(dá)率，當(dāng)所有到達(dá)的顧客都可能加入時(shí)，就為λ；如果系統(tǒng)滿(mǎn)了(存在容量限制系統(tǒng))，則顧客不能加入，λeff<λ清華版p319不準(zhǔn)確49首先根據(jù)數(shù)學(xué)期望得到系統(tǒng)中期望的顧客數(shù)隊(duì)列中期望的顧客50Ws和Wq之間也存在直接的關(guān)系。由定義希望系統(tǒng)駐留時(shí)間=期望排隊(duì)時(shí)間+期望服務(wù)時(shí)間可以寫(xiě)成

對(duì)上式兩邊乘以λeff

，建立Ls與Lq的關(guān)系.結(jié)合Little公式，得到根據(jù)定義，系統(tǒng)的平均顧客數(shù)與隊(duì)列中平均的顧客數(shù)的差值等于繁忙服務(wù)臺(tái)的平均數(shù)，因此有因此，得到了設(shè)施利用率=50Ws和Wq之間也存在直接的關(guān)系。由定義對(duì)上式兩邊乘以λe51例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ē)位的平均時(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ì)算。51例52將λn和μn代入下面的公式得到p0=0.0481252將λn和μn代入下面的公式得到p0=0.0481253有了p0,可以計(jì)算p1到p8如下n12345678pn0.144360.216540.216540.162400.097440.058470.035080.02105實(shí)際使用停車(chē)場(chǎng)的車(chē)輛的有效到達(dá)率的計(jì)算取決于停車(chē)場(chǎng)是否滿(mǎn)了。有效到達(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.因此停車(chē)設(shè)施53有了p0,可以計(jì)算p1到p8如下n12345678pn54停車(chē)場(chǎng)內(nèi)車(chē)輛的平均數(shù)等于系統(tǒng)內(nèi)車(chē)輛的平均數(shù)Ls.我們可以用pn計(jì)算出Ls在臨時(shí)車(chē)位等待的車(chē)輛實(shí)際上就是隊(duì)列中的車(chē)輛.因此，等待找到車(chē)位的等待時(shí)間就是Wq.為確定Wq

，用因此占用了車(chē)位的平均車(chē)輛數(shù)就與繁忙服務(wù)臺(tái)的平均數(shù)相等54停車(chē)場(chǎng)內(nèi)車(chē)輛的平均數(shù)等于系統(tǒng)內(nèi)車(chē)輛的平均數(shù)Ls.我們可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):(GD/∞/∞)基本假設(shè)如下：與排隊(duì)系統(tǒng)狀態(tài)無(wú)關(guān)5512.6.3單服務(wù)臺(tái)模型本節(jié)介紹僅有一個(gè)服務(wù)臺(tái)到達(dá)率56令，將其稱(chēng)之為服務(wù)強(qiáng)度或業(yè)務(wù)密度，則廣義模型中pn

的表達(dá)式簡(jiǎn)化為為了求p0的值，用等式設(shè)ρ<1,利用幾何級(jí)數(shù)求和公式有所以所以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).56令，將其稱(chēng)之為服務(wù)57排隊(duì)系統(tǒng)的性能度量指標(biāo)Ls可以按照下面的方式得到：因?yàn)閷?duì)于本情形，剩下的系統(tǒng)性能度量指標(biāo)用6.2節(jié)的關(guān)系來(lái)計(jì)算.因此有57排隊(duì)系統(tǒng)的性能度量指標(biāo)Ls可以按照下面的方式得到：因58例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)棣?lt;1,系統(tǒng)可以按照平穩(wěn)狀態(tài)運(yùn)行。一般來(lái)說(shuō)，不建議只用Ls來(lái)計(jì)算停車(chē)位數(shù)，因?yàn)閺哪撤N意義上，停車(chē)位代表了要保證最大可能的隊(duì)列長(zhǎng)度.58例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à)于下面的概率條件：即根據(jù)有限項(xiàng)的幾何技術(shù)求和公式，有所以?xún)蛇吶?duì)數(shù)(注意到ln(x)<0,0<x<1,不等式變號(hào))59例如，停車(chē)場(chǎng)的設(shè)計(jì)要使得來(lái)到的車(chē)在至少90%的時(shí)候能找到60(M/M/1):(GD/∞/∞)的等待時(shí)間分布廣義模型中得到的pn與排隊(duì)規(guī)則完全無(wú)關(guān).這意味著,排隊(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í)間.60(M/M/1):(GD/∞/∞)的等待時(shí)間分布廣義模型中61定義為已知系統(tǒng)中有n個(gè)顧客在剛剛到達(dá)的顧客之前的條件下,τ的條件密度函數(shù).因?yàn)榉?wù)時(shí)間的分布是指數(shù)的，指數(shù)分布的遺忘性質(zhì)表明，也是指數(shù)的，服從相同的分布.因此，τ等于(n+1)個(gè)同分布的獨(dú)立指數(shù)隨機(jī)變量之和.由概率論可知，服從帶有參數(shù)和(n+1)的Г分布.因此有因此，為一指數(shù)分布，平均值為61定義為已知系62例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)價(jià)用Ws作為估計(jì)系統(tǒng)中等待時(shí)間的可靠性.回答這個(gè)問(wèn)題的一個(gè)方法是，估計(jì)顧客中等待時(shí)間超過(guò)Ws的比例，注意到，我們得到在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í)間62例回答這個(gè)問(wèn)題的一個(gè)方法是，估計(jì)顧客中等待時(shí)間超過(guò)Ws的63(M/M/1):(GD/N/∞)模型這個(gè)模型和(M/M/1):(GD/∞/∞)不同之處在于，系統(tǒng)最多容納的顧客數(shù)(最大隊(duì)列長(zhǎng)度為N-1)為N.例如流水線上放置工件的空間是有限的.當(dāng)系統(tǒng)中的顧客數(shù)達(dá)到N時(shí)，不允許再有到達(dá)，因此有利用，根據(jù)廣義模型的穩(wěn)態(tài)概率公式可以從等式求出p0的值，這將得到63(M/M/1):(GD/N/∞)模型這個(gè)模型和(M/M/64或因此有在這個(gè)模型中,的值不需要小于1,因?yàn)橄到y(tǒng)的到達(dá)受到系統(tǒng)顧客上限N的限制.這意味著在這種情況下,重要的是到達(dá)率λeff而不是λ.由于系統(tǒng)中有N個(gè)顧客，再來(lái)的顧客就不再進(jìn)入系統(tǒng).此時(shí)64或因此有在這個(gè)模型中,系統(tǒng)中期望顧客數(shù)可以計(jì)算為當(dāng)時(shí)，Ls=N/2.同樣從Ls,利用λeff求出Ws,Wq,Lq.系統(tǒng)中期望顧客數(shù)可以計(jì)算為當(dāng)時(shí)，Ls=N/66(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ì)到達(dá)。顧客源總數(shù)達(dá)到m時(shí)，此時(shí)顧客單位時(shí)間內(nèi)的到達(dá)次數(shù)依賴(lài)于當(dāng)前尚未到達(dá)系統(tǒng)的顧客數(shù)，假設(shè)每個(gè)顧客進(jìn)入系統(tǒng)的到達(dá)率為λ,進(jìn)入系統(tǒng)的顧客為n,(0<n<m),則系統(tǒng)外的顧客為m-n,所以系統(tǒng)的到達(dá)率而系統(tǒng)的離開(kāi)率取決于服務(wù)臺(tái)數(shù)量為1，此時(shí)有66(M/M/1):(GD/∞/m)模型這個(gè)模型和(M/M/67根據(jù)廣義模型，有根據(jù)根據(jù)，有注意，此時(shí)不要求成立67根據(jù)廣義模型，有根據(jù)根據(jù)68根據(jù)Little公式以及系統(tǒng)期望公式，有68根據(jù)Little公式以及系統(tǒng)期望公式，有6912.6.4多服務(wù)臺(tái)模型本節(jié)考慮有多個(gè)并行服務(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)有限制，所以使用并行服務(wù)臺(tái)的效果使得設(shè)施的服務(wù)率成比例的增加.根據(jù)廣義模型(第五節(jié))，6912.6.4多服務(wù)臺(tái)模型本節(jié)考慮有多個(gè)并行服務(wù)臺(tái)的370因此，根據(jù)廣義穩(wěn)態(tài)概率計(jì)算公式p0的值可以從求出，得到70因此，根據(jù)廣義穩(wěn)態(tài)概率計(jì)算公式p0的值可以從71系統(tǒng)的運(yùn)行指標(biāo)如下71系統(tǒng)的運(yùn)行指標(biāo)如下72例某社區(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ù)，每家公司都可以表示為λ=8次/小時(shí)，出租車(chē)μ=60/12=5次/小時(shí)乘坐的(M/M/2):(GD/∞/∞)模型.合并以后得到(M/M/4):(GD/∞/∞)模型，其參數(shù)為λ=16次/小時(shí)，μ=5次/小時(shí).72例73根據(jù)參數(shù)，利用排隊(duì)系統(tǒng)運(yùn)行性能指標(biāo)計(jì)算公式得到下表cλμp0LsWsLqWq2850.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)作模式.73根據(jù)參數(shù)，利用排隊(duì)系統(tǒng)運(yùn)行性能指標(biāo)計(jì)算公式得到下表cλμ74(M/M/c):(GD/N/∞),c≤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)前模型的將上述代入穩(wěn)態(tài)概率(第五節(jié))的公式，得到74(M/M/c):(GD/N/∞),c≤N模型這個(gè)模75p0的值可以從求出，得到排隊(duì)系統(tǒng)的運(yùn)行指標(biāo)如下75p0的值可以從求76例在合并的出租車(chē)公司問(wèn)題中，假設(shè)沒(méi)有新的經(jīng)費(fèi)來(lái)購(gòu)買(mǎi)更多出租車(chē)，又一個(gè)咨詢(xún)專(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è)以?xún)?nèi)就等價(jià)于設(shè)定N=6+4=10個(gè)顧客.因此專(zhuān)家建議的排隊(duì)模型為(M/M/4):(GD/10/∞),其中λ=16次/小時(shí)，μ=5次/小時(shí).cλμp0LsWsLqWq41650.031214.23980.27481.15420.0748176例cλμp0LsWsLqWq41650.031214.277在設(shè)置系統(tǒng)能力上限之前的平均等待時(shí)間為Wq=0.149小時(shí)，大約是新的平均等待時(shí)間0.075小時(shí)的兩倍.等待時(shí)間的大幅度減少的代價(jià)是流失了大約3.6%的潛在顧客(p10=0.03574).這個(gè)結(jié)果還不能反映顧客對(duì)公司經(jīng)營(yíng)印象的損害效果.77在設(shè)置系統(tǒng)能力上限之前的平均等待時(shí)間為Wq=0.149小78(M/M/∞):(GD/∞/∞)——自助服務(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ì)模型，有因此有p0的值可以從求出，得到78(M/M/∞):(GD/∞/∞)——自助服務(wù)模型在這個(gè)模79排隊(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)凈值.79排隊(duì)系統(tǒng)的運(yùn)行指標(biāo)如下例80從實(shí)際情況看，這位投資者并不需要排隊(duì)等待債券的買(mǎi)入或者賣(mài)出.買(mǎi)賣(mài)間隔的平均時(shí)間是1個(gè)月，因此每年有λ=12只債券.債券的銷(xiāo)售率為每年μ=1/3只債券.此時(shí)每只債券就是就是服務(wù)臺(tái)本身，有多少債券就有多少服務(wù)臺(tái)，這一情形符合(M/M/∞):(GD/∞/∞)模型.已知λ

和μ

，得到該投資者的預(yù)計(jì)(長(zhǎng)期)平均年度凈值為80從實(shí)際情況看，這位投資者并不需要排隊(duì)等待債券的買(mǎi)入或者賣(mài)81機(jī)器伺服模型——(M/M/R):(GD/K/K),R<K這個(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)模型，區(qū)別在于，本模型中有R個(gè)修理工。81機(jī)器伺服模型——(M/M/R):(GD/K/K),R82本模型有有限個(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ù)依賴(lài)于當(dāng)前尚未到達(dá)系統(tǒng)的顧客數(shù)，假設(shè)每個(gè)顧客進(jìn)入系統(tǒng)的到達(dá)率為λ,進(jìn)入系統(tǒng)的顧客(即等待維修的機(jī)器)為n(0<n<m),則此時(shí)有機(jī)器出現(xiàn)故障的發(fā)生率取決于完好狀態(tài)的機(jī)器數(shù)量K-n.即82本模型有有限個(gè)輸入源，原因在于，此時(shí)總共有K臺(tái)機(jī)器，機(jī)器83根據(jù)廣義排隊(duì)模型，根據(jù)廣義排隊(duì)模型的穩(wěn)態(tài)概率計(jì)算公式，可以得到83根據(jù)廣義排隊(duì)模型，根據(jù)廣義排隊(duì)模型的穩(wěn)態(tài)概率計(jì)算公式，可84遺憾的是，在(M/M/R):(GD/K/K)模型(R<K)中,沒(méi)有計(jì)算Ls、Lq、Ws和Wq的簡(jiǎn)單的、封閉型的表達(dá)式，必須用下面的基本定義來(lái)計(jì)算：其中，例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).84遺憾的是，在(M/M/R):(GD/K/K)模型(R<85要分析該情況，考察作為修理工數(shù)的函數(shù)的機(jī)床生產(chǎn)率，這一生產(chǎn)率的度量可以定義為該情形屬于(M/M/R):(GD/K/K)模型，其中λ=0.5,μ=5,R=1,2,3,4,系統(tǒng)上限=22,輸入源=22.根據(jù)前面的計(jì)算公式得到Rλμλeffp0LsLqWsWq10.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ī)床生產(chǎn)率45.4480.1588.7990.45邊際增長(zhǎng)率—34.718.641.6685要分析該情況，考察作為修理工數(shù)的函數(shù)的機(jī)床生產(chǎn)率，這一生86上述結(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)1.66%，不支持這樣的計(jì)劃。86上述結(jié)果說(shuō)明，用1個(gè)修理工時(shí)，生產(chǎn)率很低(45.44%)8712.7一般服務(wù)時(shí)間M/G/1模型前面討論的排隊(duì)模型到達(dá)時(shí)間和服務(wù)時(shí)間均服從指數(shù)分布，這類(lèi)系統(tǒng)的主要特征是Markov特性，即未來(lái)狀態(tài)僅由當(dāng)前系統(tǒng)的狀態(tài)決定。但是當(dāng)?shù)竭_(dá)時(shí)間間隔和服務(wù)時(shí)間間隔至少至少有一個(gè)不服從負(fù)指數(shù)分布時(shí)，僅靠當(dāng)前狀態(tài)不足以推斷未來(lái)狀態(tài)，這樣的排隊(duì)模型稱(chēng)為非馬氏排隊(duì)模型。這類(lèi)排隊(duì)模型非常復(fù)雜，對(duì)于這類(lèi)情形的分析，我們將在以后介紹采用模擬方法來(lái)研究8712.7一般服務(wù)時(shí)間M/G/1模型前面討論的排隊(duì)模型88(M/G/1):(GD/∞/∞)排隊(duì)模型本節(jié)介紹一個(gè)很少出現(xiàn)的具有解析結(jié)果的非泊松排隊(duì).它所描述的情況是，服務(wù)時(shí)間t

服從任何概率分布，平均值為E{t},方差為Var{t}.這個(gè)模型的結(jié)果包括系統(tǒng)性能的基本指標(biāo)Ls、Lq、Ws和Wq.由于公式非常復(fù)雜,這個(gè)模型沒(méi)有pn的封閉型表達(dá)式.令λ為單服務(wù)臺(tái)設(shè)施的到達(dá)率，已知服務(wù)時(shí)間分布的E{t}和Var{t}，并且λE{t}<1,我們可以通過(guò)復(fù)雜的概率論/馬爾可夫鏈分析來(lái)證明這就是著名的Pollaczek-Kbintchine(P-K)公式.88(M/G/1):(GD/∞/∞)排隊(duì)模型本節(jié)介紹一個(gè)很少89服務(wù)設(shè)施為空閑的概率可按照下面公式求出由λeff=λ，根據(jù)Little公式可以從Ls求出來(lái).89服務(wù)設(shè)施為空閑的概率可按照下面公式求出由λeff=λ，根90例Automata洗車(chē)房只運(yùn)行一個(gè)清洗位.車(chē)輛按照泊松分布到達(dá),平均每小時(shí)4輛車(chē)，如果清洗位忙，則到達(dá)的車(chē)輛等在洗車(chē)房的停車(chē)場(chǎng).現(xiàn)在安裝了新的洗車(chē)系統(tǒng)，對(duì)所有車(chē)輛的服務(wù)時(shí)間均為10分鐘.該系統(tǒng)有何影響？λeff=λ=4輛車(chē)/小時(shí).服務(wù)時(shí)間為常數(shù),這樣E{t}=1/6小時(shí),方差Var{t}=0.因此90例91有意思的是，雖然到達(dá)率和離開(kāi)率與前面P58的泊松分布情況相同(λ=4輛車(chē)/小時(shí),μ=6輛車(chē)/小時(shí))，但是這個(gè)模型的期望等待時(shí)間要少，因?yàn)榉?wù)時(shí)間為常數(shù)，如下表.M/M/1M/G/1Ws(hr)0.50.333Ws(hr)0.3330.167因?yàn)槌?shù)服務(wù)時(shí)間表示該設(shè)施的運(yùn)行更加確定，所以這個(gè)結(jié)果是合理的。91有意思的是，雖然到達(dá)率和離開(kāi)率與前面P58的泊松分布情況92(M/D/1):(GD/∞/∞)排隊(duì)模型(M/D/1):(GD/∞/∞)排隊(duì)模型中，服務(wù)時(shí)間服從定長(zhǎng)分布，其平均服務(wù)時(shí)間為1/μ，方差為0，這時(shí)可以將P-K公式改為其余指標(biāo)為上式中的Lq是M/M/1模型排隊(duì)長(zhǎng)的1/2，即MD1模型排隊(duì)長(zhǎng)更短?？梢宰C明在一般的服務(wù)時(shí)間分布中，定長(zhǎng)分布的排隊(duì)最小，即服務(wù)時(shí)間的不確定性越小(方差越小)，等候時(shí)間越短92(M/D/1):(GD/∞/∞)排隊(duì)模型(M/D/1):93(M/Ek/1):(GD/∞/∞)排隊(duì)模型(M/Ek/1):(GD/∞/∞)排隊(duì)模型中的服務(wù)時(shí)間服從k階Erlang分布.多個(gè)服務(wù)臺(tái)串聯(lián)式，每個(gè)服務(wù)臺(tái)的服務(wù)時(shí)間相互獨(dú)立且服從相同的參數(shù)kμ的負(fù)指數(shù)分布，這就是總服務(wù)時(shí)間服從k階Erlang分布。根據(jù)P-K公式改寫(xiě)為λ12…kkμkμkμ埃爾朗分布的數(shù)字特征：93(M/Ek/1):(GD/∞/∞)排隊(duì)模型(M/Ek/194例某單人裁縫店做西服，每套西服經(jīng)過(guò)4個(gè)不同的工序，4個(gè)工序完成以后才開(kāi)始做另外一套。每一工序的時(shí)間服從負(fù)指數(shù)分布,期望值為2小時(shí)。顧客來(lái)到服從泊松分布，平均訂貨率為5.5套/周(設(shè)一周6天，每天8小時(shí)).問(wèn)顧客為等到做好一套西服期望時(shí)間要多長(zhǎng)？解顧客到達(dá)λ=5.5套/周，設(shè)：μ——平均服務(wù)率(單位時(shí)間做完的套數(shù))；1/μ——平均每套所需要的時(shí)間；1/4μ——平均每道工序所需要的時(shí)間；由題設(shè)1/4μ=2小時(shí)，μ=1/8(套/小時(shí))=6(套/周)，ρ=5.5/6，94例9512.8排隊(duì)系統(tǒng)最優(yōu)化排隊(duì)吸引的最優(yōu)化問(wèn)題有兩類(lèi)：系統(tǒng)設(shè)計(jì)的最優(yōu)化——靜態(tài)問(wèn)題，目的在于使得設(shè)備達(dá)到最大效益，在一定質(zhì)量指標(biāo)下要求機(jī)構(gòu)最為經(jīng)濟(jì)系統(tǒng)控制最優(yōu)化——?jiǎng)討B(tài)問(wèn)題，對(duì)給定的控制系統(tǒng)，如何運(yùn)營(yíng)可使得某個(gè)目標(biāo)函數(shù)得到最優(yōu)。本課程僅僅討論靜態(tài)問(wèn)題。9512.8排隊(duì)系統(tǒng)最優(yōu)化排隊(duì)吸引的最優(yōu)化問(wèn)題有兩類(lèi)：96在一般情況下，提高服務(wù)水平會(huì)降低顧客等待費(fèi)用，但增加服務(wù)機(jī)構(gòu)的成本。優(yōu)化的目的是使得顧客等待費(fèi)用和機(jī)構(gòu)服務(wù)費(fèi)用之和最小，決定到達(dá)這個(gè)最優(yōu)目標(biāo)的最優(yōu)服務(wù)水平。使得純收入或者使得利潤(rùn)(服務(wù)收入減去服務(wù)成本)為最大。顧客等待時(shí)間成本服務(wù)時(shí)間成本總費(fèi)用服務(wù)水平費(fèi)用最優(yōu)服務(wù)水平96在一般情況下，提高服務(wù)水平會(huì)降低顧客等待費(fèi)用，但增加服務(wù)97各種費(fèi)用在穩(wěn)態(tài)情形下，都是按單位時(shí)間來(lái)考慮的，一般情形，服務(wù)費(fèi)用是可以確切計(jì)算的，但是顧客等待費(fèi)用存在很多情形，比如機(jī)械故障等待費(fèi)用、病人就診等待費(fèi)用，隊(duì)列過(guò)長(zhǎng)失掉潛在的顧客的損失，只能依賴(lài)于調(diào)查和歷史數(shù)據(jù)。服務(wù)水平也可以由不同形式來(lái)表示，主要是平均服務(wù)率μ(代表服務(wù)機(jī)構(gòu)的服務(wù)能力和經(jīng)驗(yàn))、服務(wù)臺(tái)個(gè)數(shù)c，以及排隊(duì)系統(tǒng)容量，服務(wù)水平也可以以服務(wù)強(qiáng)度ρ來(lái)表示。常用的方法：離散變量常用邊際分析法，對(duì)于連續(xù)變量常用經(jīng)典的微分法，對(duì)于復(fù)雜問(wèn)題還可以用非線性規(guī)劃和動(dòng)態(tài)規(guī)劃的方法。97各種費(fèi)用在穩(wěn)態(tài)情形下，都是按單位時(shí)間來(lái)考慮的，一般情形，98M/M/1模型中最優(yōu)服務(wù)率μ1.M/M/1模型取目標(biāo)函數(shù)z為單位時(shí)間服務(wù)成本與顧客在系統(tǒng)逗留費(fèi)用之和的期望值z(mì)=csμ+cwLs其中cs為當(dāng)μ*=1時(shí)服務(wù)機(jī)構(gòu)單位時(shí)間的費(fèi)用，cw為每個(gè)顧客在系統(tǒng)停留單位時(shí)間的費(fèi)用。將上式代入Ls之值代入得為了求極值，先求,然后令其為0，98M/M/1模型中最優(yōu)服務(wù)率μ1.M/M/1模型992系統(tǒng)容量為N的情形系統(tǒng)如果已經(jīng)有N個(gè)顧客，則后來(lái)的顧客即被拒絕，則PN——被拒絕的概率(損失率)；1-PN——能接受服務(wù)的概率；λ(1-PN)——單位時(shí)間進(jìn)入服務(wù)系統(tǒng)的平均顧客數(shù)量。在穩(wěn)態(tài)下，它等于單位時(shí)間內(nèi)實(shí)際服務(wù)完成的平均顧客數(shù)。設(shè)每服務(wù)1人能收G元，則單位時(shí)間收入的期望為λ(1-PN)G元.純利潤(rùn)為了求極值，先求,然后令其為0，得求解μ*通常非常困難，可以通過(guò)數(shù)值計(jì)算的辦法來(lái)求解，或者對(duì)N做ρ的函數(shù)曲線，對(duì)于給定的G/cs，根據(jù)曲線求出μ*/λ.992系統(tǒng)容量為N的情形為了求極值，先求,1003顧客源為有限的情形仍然按照機(jī)械故障問(wèn)題來(lái)考慮。設(shè)共有m臺(tái)機(jī)器，各臺(tái)連續(xù)運(yùn)轉(zhuǎn)時(shí)間服從負(fù)指數(shù)分布。有1個(gè)修理工人，修理時(shí)間服從負(fù)指數(shù)分布。當(dāng)服務(wù)率μ=1時(shí)的修理費(fèi)用cs，單位時(shí)間每臺(tái)機(jī)器運(yùn)轉(zhuǎn)可得G元。平均運(yùn)轉(zhuǎn)臺(tái)數(shù)為m-Ls，所以單位時(shí)間純利潤(rùn)為對(duì)上式直接求解μ*通常非常困難，通常的辦法是，在服務(wù)率上依次增加一定單位的值，進(jìn)而計(jì)算出不同服務(wù)速度下的，進(jìn)而代入上式來(lái)計(jì)算純利潤(rùn)，通過(guò)比較確定μ*.1003顧客源為有限的情形對(duì)上式直接求解μ*通常非常困難，101(M/M/c):(GD/∞/∞)模型中最優(yōu)服務(wù)臺(tái)個(gè)數(shù)c在穩(wěn)態(tài)條件下，單位時(shí)間的費(fèi)用（成本、利潤(rùn)或者成本+等待費(fèi)用）函數(shù)的期望函數(shù)為G為每服務(wù)1人的收入,為單位服務(wù)成本,為顧客等待費(fèi)用。則根據(jù)問(wèn)題性質(zhì)，兩種方法確定最優(yōu)服務(wù)臺(tái)數(shù)：(1)可以運(yùn)用邊際分析方法，即在每次增加1個(gè)服務(wù)臺(tái)，即計(jì)算排隊(duì)長(zhǎng)度，根據(jù)上述公式計(jì)算目標(biāo)函數(shù)結(jié)果，再計(jì)算每增加一個(gè)服務(wù)臺(tái)的的目標(biāo)函數(shù)與前一次的目標(biāo)函數(shù)的差值，這個(gè)差值即為邊際收入，邊際收入最大的那個(gè)服務(wù)臺(tái)數(shù)即為最優(yōu)服務(wù)臺(tái)個(gè)數(shù)。(2)每次增加1個(gè)服務(wù)臺(tái)，直接計(jì)算目標(biāo)函數(shù)結(jié)果，選擇合適的函數(shù)目標(biāo)所對(duì)應(yīng)對(duì)應(yīng)的服務(wù)臺(tái)個(gè)數(shù)為最優(yōu)值。101(M/M/c):(GD/∞/∞)模型中最優(yōu)服務(wù)臺(tái)個(gè)數(shù)102一家有多個(gè)員工的工具庫(kù)，交換工具的請(qǐng)求按照泊松分布發(fā)生，每小時(shí)有17.5個(gè)請(qǐng)求.每個(gè)員工每小時(shí)平均辦理10個(gè)請(qǐng)求.工具庫(kù)雇用1名新員工的工資是$12,每小時(shí)每臺(tái)等待車(chē)床的生產(chǎn)損失為$50,求該工具庫(kù)最優(yōu)的員工數(shù)量.

上述問(wèn)題對(duì)應(yīng)著M/M/c模型，要確定c的最優(yōu)值.費(fèi)用模型為,每小時(shí)λ=17.5個(gè)請(qǐng)求和每小時(shí)μ=10個(gè)請(qǐng)求.注意到當(dāng)c>λ/μ時(shí)，排隊(duì)系統(tǒng)處于穩(wěn)態(tài)，依次增加服務(wù)臺(tái)個(gè)數(shù)，計(jì)算Ls及成本，結(jié)果表明，最優(yōu)員工數(shù)為4.cLsz27.467397.3532.217146.8541.842140.1051.769148.4561.754159.70102一家有多個(gè)員工的工具庫(kù)，交換工具的請(qǐng)求按照泊松分布發(fā)生10312.10排隊(duì)網(wǎng)絡(luò)當(dāng)一組資源由一組顧客共享時(shí)形成了排隊(duì)網(wǎng)絡(luò)。每個(gè)資源表示一個(gè)可能有多個(gè)服務(wù)臺(tái)并行工作的服務(wù)中心。如果一個(gè)到達(dá)的顧客發(fā)現(xiàn)一個(gè)特定的中心繁忙，他可能加入該中心的隊(duì)列等候服務(wù)(也可能離開(kāi)該隊(duì)列去尋找其他類(lèi)型的服務(wù)).在一站服務(wù)結(jié)束后，該顧客可能轉(zhuǎn)入另一個(gè)服務(wù)中心，或者重新進(jìn)入同一個(gè)中心，或者離開(kāi)系統(tǒng)。10312.10排隊(duì)網(wǎng)絡(luò)當(dāng)一組資源由一組顧客共享時(shí)形成了104在串連隊(duì)列中,一旦一個(gè)顧客進(jìn)入系統(tǒng),他將必須留在系統(tǒng)中直到接受了全套服務(wù)。通常,每個(gè)服務(wù)臺(tái)前都運(yùn)行等候,前面討論的M/Ek/1模型是這種串連模型的特例,在M/Ek/1模型中除了第一個(gè)服務(wù)臺(tái)前可以有等候隊(duì)列,其他的服務(wù)臺(tái)是不允許有等候的,在這種情況下,必須是n個(gè)服務(wù)項(xiàng)目都結(jié)束以后,一個(gè)新的顧客才運(yùn)行進(jìn)入系統(tǒng)接受服務(wù)。12.10.1開(kāi)放排隊(duì)系統(tǒng)串聯(lián)系統(tǒng)或序貫系統(tǒng)104在串連隊(duì)列中,一旦一個(gè)顧客進(jìn)入系統(tǒng),他將必須留在系105服務(wù)網(wǎng)絡(luò)行為由輸出分布、各服務(wù)臺(tái)的服務(wù)時(shí)間分布以及輸入分布和各種排隊(duì)規(guī)則共同確定.在一個(gè)串連網(wǎng)絡(luò)中,由于一個(gè)服務(wù)臺(tái)的輸出是下一個(gè)服務(wù)臺(tái)的輸入,網(wǎng)絡(luò)的穩(wěn)態(tài)性質(zhì)由隊(duì)列的輸出分布共同規(guī)定.在這個(gè)方面，Burke已經(jīng)證明：在一個(gè)M/M/r隊(duì)列中，穩(wěn)態(tài)時(shí)的離開(kāi)時(shí)間間隔是獨(dú)立的隨機(jī)變量.而且，這樣一個(gè)隊(duì)列的輸出構(gòu)成了一個(gè)泊松過(guò)程，其中參數(shù)λ與輸入的參數(shù)相同.按照Burke的結(jié)論，當(dāng)一個(gè)M/M/r串連網(wǎng)絡(luò)的輸入是一個(gè)參數(shù)為λ的泊松過(guò)程時(shí)，穩(wěn)態(tài)時(shí)所有后續(xù)輸入和輸出均具有相同參數(shù)λ的泊松過(guò)程。奈奎斯特定理一個(gè)具有參數(shù)λ的泊松輸入的M/M/r隊(duì)列的穩(wěn)態(tài)輸出也是一個(gè)具有參數(shù)為λ的泊松過(guò)程.105服務(wù)網(wǎng)絡(luò)行為由輸出分布、各服務(wù)臺(tái)的服務(wù)時(shí)間分布以及輸入106Jackson研究了更為一般的問(wèn)題：每個(gè)服務(wù)臺(tái)有獨(dú)立的泊松到達(dá)以及從其他服務(wù)臺(tái)輸出的反饋.穩(wěn)態(tài)時(shí)，這樣一個(gè)復(fù)雜網(wǎng)絡(luò)本質(zhì)上可以簡(jiǎn)化為一個(gè)具有獨(dú)立服務(wù)臺(tái)的串連網(wǎng)絡(luò),其中每個(gè)服務(wù)臺(tái)有等價(jià)的輸入速率和服務(wù)速率.作為研究在不同服務(wù)臺(tái)有反饋和泊松到達(dá)的排隊(duì)網(wǎng)絡(luò)的先導(dǎo),我們先研究由兩個(gè)單服務(wù)臺(tái)M/M/1隊(duì)列串聯(lián)的最簡(jiǎn)單網(wǎng)絡(luò)。考慮一個(gè)兩階段串聯(lián)網(wǎng)絡(luò)，它由服務(wù)速率分別為μ1和μ2的如下圖所示的服務(wù)臺(tái)組成。分析這個(gè)系統(tǒng)，我們需要追蹤在服務(wù)線1和2中的顧客數(shù)。這種系統(tǒng)可用一個(gè)隨機(jī)過(guò)程建模，狀態(tài)由(n,m)表示，其中nm>0表示的了第i個(gè)服務(wù)臺(tái)前的顧客數(shù)量.設(shè)p(n,m)表示為第一項(xiàng)有n個(gè)顧客，第二項(xiàng)有m個(gè)顧客的概率106Jackson研究了更為一般的問(wèn)題：每個(gè)服務(wù)臺(tái)有獨(dú)立的107n,mn+1,m-1n+1,mn,m-1n-1,mn-1,m+1n,mμ1λλμ2μ2μ1對(duì)于該串聯(lián)系統(tǒng)，我們?cè)撊绾蚊枋鲈撓到y(tǒng)的狀態(tài)？0,00,10,20,31,01,11,21,32,02,12,22,3μ2μ2μ2μ2μ2μ2μ2μ2μ2λλλλλλλλμ1μ1μ1μ1μ1μ1107n,mn+1,n+1,n,n-1,n-1,n,μ1λλ108由Burke定理知，穩(wěn)態(tài)是兩個(gè)服務(wù)臺(tái)的離開(kāi)時(shí)間間隔為指數(shù)隨機(jī)變量，且該隨機(jī)過(guò)程是馬爾科夫的。對(duì)上述微分方程的穩(wěn)態(tài)解為穩(wěn)態(tài)時(shí)第1個(gè)服務(wù)臺(tái)前有n個(gè)顧客的概率為兩個(gè)服務(wù)臺(tái)均具有λ的泊松到達(dá)和指數(shù)服務(wù)時(shí)間，類(lèi)似地，第2個(gè)服務(wù)臺(tái)前有m個(gè)顧客的概率為108由Burke定理知，穩(wěn)態(tài)是兩個(gè)服務(wù)臺(tái)的離開(kāi)時(shí)間間隔為指109從上面可以看到，系統(tǒng)中的顧客平均數(shù)Ls

由下式給出對(duì)下面的排隊(duì)系統(tǒng)如何處理？Jackson給我們作出了回答.109從上面可以看到，系統(tǒng)中的顧客平均數(shù)Ls由下式給出對(duì)110將上述結(jié)果作實(shí)質(zhì)性的推廣.考慮k個(gè)服務(wù)臺(tái)的系統(tǒng).顧客按照速率為ri的獨(dú)立泊松過(guò)程從系統(tǒng)外進(jìn)入服務(wù)臺(tái)i,i=1,2,…k,然后他們加入服務(wù)臺(tái)i

前面的隊(duì)列直到輪到他們接受服務(wù).一旦一個(gè)顧客結(jié)束了服務(wù)臺(tái)i的服務(wù)，然后他們以概率pij加入服務(wù)臺(tái)j前面的隊(duì)列，j=1,…k.因此，，而表示一個(gè)顧客在結(jié)束服務(wù)臺(tái)i

的服務(wù)以后離開(kāi)系統(tǒng)的概率.如果以λj

計(jì)為顧客到達(dá)服務(wù)臺(tái)j

的總的到達(dá)率，那么λj

可以作為上式成立是由于rj

是由系統(tǒng)外面到j(luò)

的顧客的到達(dá)率，而λj是顧客離開(kāi)服務(wù)臺(tái)i

的速度(進(jìn)去的速率等于離開(kāi)的速率),是從服務(wù)線i到達(dá)服務(wù)線j

的速率.110將上述結(jié)果作實(shí)質(zhì)性的推廣.考慮k個(gè)服務(wù)臺(tái)的系統(tǒng).顧111這表明在每個(gè)服務(wù)線的顧客數(shù)是獨(dú)立的，而且具有形式其中μj是在服務(wù)線j的指數(shù)服務(wù)速率，當(dāng)然必須對(duì)一切的j都有系統(tǒng)中的各個(gè)服務(wù)線的顧客數(shù)為n1,n2,…nk的概率為上述結(jié)果相當(dāng)有意義。它表明在服務(wù)線i

顧客數(shù)量的分布與具有速率λi和μi的M/M/1系統(tǒng)是一樣的.但是,網(wǎng)絡(luò)模型中節(jié)點(diǎn)i出的到達(dá)過(guò)程不一定是泊松過(guò)程。因?yàn)?如果一個(gè)顧客有可能訪問(wèn)一個(gè)服務(wù)線不只一次(這種情形為反饋).到達(dá)過(guò)程將不再是泊松過(guò)程.當(dāng)容許有反饋時(shí)，給定站點(diǎn)的顧客數(shù)的穩(wěn)態(tài)概率與M/M/1模型相同，即使這個(gè)模型不是M/M/1.111這表明在每個(gè)服務(wù)線的顧客數(shù)是獨(dú)立的，而且具有形式其中μ112Jackson已經(jīng)證明：穩(wěn)態(tài)時(shí)，上述存在反饋和前饋的網(wǎng)絡(luò)中，每個(gè)服務(wù)線的顧客數(shù)的分布與其他任何服務(wù)線的顧客數(shù)的分布相互獨(dú)立，并且滿(mǎn)足穩(wěn)態(tài)時(shí)，在有反饋的情況下，各個(gè)服務(wù)線的合成輸入不再是泊松過(guò)程，而服務(wù)臺(tái)輸出也不再是泊松過(guò)程。然而各個(gè)服務(wù)線是獨(dú)立的，并且他們的行為類(lèi)似于輸入速率為λi和服務(wù)速率為μi的M/M/c的排隊(duì)系統(tǒng).112Jackson已經(jīng)證明：穩(wěn)態(tài)時(shí)，上述存在反饋和前饋的網(wǎng)113根據(jù)Little公式，系統(tǒng)的平均等待時(shí)間為它是每一個(gè)M/M/1排隊(duì)系統(tǒng)的平均等待時(shí)間之和.在這個(gè)系統(tǒng)中的平均數(shù)是113根據(jù)Little公式，系統(tǒng)的平均等待時(shí)間為它是每一個(gè)M例考慮一個(gè)擁有兩條服務(wù)線的系統(tǒng),顧客從系統(tǒng)外部以速率為4的泊松過(guò)程到達(dá)服務(wù)線1,而以速率為5的泊松過(guò)程到達(dá)服務(wù)線2.服務(wù)線1和2的服務(wù)速率分別為8和10.在完成服務(wù)線1的服務(wù)的顧客等可能地到服務(wù)線2或離開(kāi)系統(tǒng)，然而從服務(wù)線2的離開(kāi)者,25%的人去服務(wù)線1,其他人離開(kāi)系統(tǒng).試確定極限概率,Ls和Ws.124525%50%50%75%810例124525%50%50%75%810115解到服務(wù)線1和2的總到達(dá)率分別計(jì)為λ1和λ2，根據(jù)下面的方程，有因此且115解到服務(wù)線1和2的總到達(dá)率分別計(jì)為λ1和λ2，根116第12章排隊(duì)系統(tǒng)1第12章排隊(duì)系統(tǒng)117AgnerKrarupErlang1878-1929丹麥電信工程師，排隊(duì)論之父研究人們打電話的方式，發(fā)展出人們需要等待多久的公式，并于1909年出版了關(guān)于排隊(duì)理論的第一篇論文2AgnerKrarupErlang研究人們打電話的方式118UCLA,LeonardKleinrock1934—“互聯(lián)網(wǎng)之父”，“影響本世紀(jì)的50人”UCLA,

JamesR.Jackson1924—2011排隊(duì)網(wǎng)絡(luò)之父排隊(duì)論煥發(fā)了新的生命力，影響巨大！3UCLA,LeonardKleinrockUCLA,119生活在城市中的居民在生產(chǎn)、生活以及學(xué)習(xí)消費(fèi)的過(guò)程中，存在大量的排隊(duì)現(xiàn)象，例如，食堂打飯、圖書(shū)館借還書(shū)、超市收銀臺(tái)、醫(yī)院等待看病、車(chē)輛在信號(hào)燈控制路口排隊(duì)等待通過(guò)、在銀行柜臺(tái)前很多顧客等待辦理業(yè)務(wù)、城市中隨時(shí)可能有急診病人等待救護(hù)車(chē)的救援、港口外多艘萬(wàn)噸級(jí)船舶等待進(jìn)港裝卸貨物、等待加工的零部件、等待裝配的汽車(chē)等等。排隊(duì)現(xiàn)象無(wú)處不在！12.1為什么要研究排隊(duì)系統(tǒng)4生活在城市中的居民在生產(chǎn)、生活以及學(xué)習(xí)消費(fèi)的過(guò)程中，存在大120排隊(duì)現(xiàn)象的特征是：顧客以某種隨機(jī)方式到達(dá)一個(gè)服務(wù)設(shè)施，之后在隊(duì)列中等待，直到他們接受服務(wù)。一旦服務(wù)結(jié)束，通常離開(kāi)系統(tǒng)。不花費(fèi)極大的成本，等待現(xiàn)象是不可能完全消除的，我們的目標(biāo)是要把他的不利影響減小到“可以忍受的”程度。5排隊(duì)現(xiàn)象的特征是：顧客以某種隨機(jī)方式到