運(yùn)籌學(xué)導(dǎo)論資料新之排隊(duì)論(-)課件

1第12章排隊(duì)系統(tǒng)2Agner

Krarup

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

JamesR.Jackson1924—2011排隊(duì)網(wǎng)絡(luò)之父排隊(duì)論煥發(fā)了新的生命力，影響巨大！4生活在城市中的居民在生產(chǎn)、生活以及學(xué)習(xí)消費(fèi)的過(guò)程中，存在大量的排隊(duì)現(xiàn)象，例如，食堂打飯、圖書館借還書、超市收銀臺(tái)、醫(yī)院等待看病、車輛在信號(hào)燈控制路口排隊(duì)等待通過(guò)、在銀行柜臺(tái)前很多顧客等待辦理業(yè)務(wù)、城市中隨時(shí)可能有急診病人等待救護(hù)車的救援、港口外多艘萬(wàn)噸級(jí)船舶等待進(jìn)港裝卸貨物、等待加工的零部件、等待裝配的汽車等等。排隊(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ù)量。究竟又是什么原因?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)題。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)用)之和的最小值。如下圖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ì)等待的顧客提供滿意的服務(wù)。排隊(duì)論主要研究服務(wù)設(shè)施的需求與用戶延誤之間的關(guān)系，其在分析和規(guī)劃城市服務(wù)設(shè)施扮演重要角色，例如地鐵閘機(jī)的設(shè)置、消防站及消防車的配置以及醫(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)化理論。而是用于度量排隊(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ì)。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ì)模型的要素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ā)生源類型）；（2）服務(wù)臺(tái)服務(wù)模式（服務(wù)臺(tái)服務(wù)方式）；（3）排隊(duì)規(guī)則；（4）排隊(duì)系統(tǒng)容量；（5）服務(wù)通道數(shù)量；（6）服務(wù)階段數(shù)量。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ī)的。15不同類型的顧客對(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ì)列，則有些類型的顧客在不同隊(duì)列之間來(lái)回排隊(duì)，以縮短期望排隊(duì)時(shí)間。（后4種情況被認(rèn)為是急躁型的顧客）如果顧客到達(dá)模式不隨時(shí)間改變（隨機(jī)型到達(dá)模式的參數(shù)不隨時(shí)間變化），則認(rèn)為是平穩(wěn)的；反之則為非平穩(wěn)的。

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ù)模式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ī)制。18在有些排隊(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)容量19只有1個(gè)服務(wù)臺(tái)的系統(tǒng)為單通道服務(wù)系統(tǒng)，在服務(wù)設(shè)施內(nèi)設(shè)置多個(gè)并行的服務(wù)臺(tái)是多通道服務(wù)系統(tǒng)。兩類不同的多通道服務(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ù)量20排隊(duì)系統(tǒng)中，許多服務(wù)設(shè)施提供的服務(wù)級(jí)數(shù)包括兩類單級(jí)的，例如高速公路收費(fèi)站、車站檢票口等；多級(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í)候也稱之為反饋）服務(wù)的排隊(duì)系統(tǒng)。12.2.6服務(wù)級(jí)數(shù)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ì)通道中的。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)生事件的速率。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é)果稱之為指數(shù)分布的無(wú)記憶性(memoryless)8:028:208:2924令指數(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)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)的分析。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分鐘，其概率正好是2712.4生滅模型排隊(duì)系統(tǒng)中，任意時(shí)間它的狀態(tài)用這個(gè)時(shí)間在系統(tǒng)中的人數(shù)表示。則該狀態(tài)取決于各個(gè)時(shí)刻進(jìn)入和離開(kāi)人數(shù)的速率，這樣的系統(tǒng)稱之為生滅過(guò)程。生滅過(guò)程例子很多，地區(qū)的人口增減、細(xì)菌或細(xì)胞的繁殖與死亡、服務(wù)臺(tái)前的顧客數(shù)量變化等等。為了簡(jiǎn)化，只考慮只有到達(dá)的純生模型和只有離開(kāi)的純滅模型。純生模型的例子如為新生嬰兒制作出生證明，純滅模型的例子如一家商店對(duì)其庫(kù)存貨物的隨機(jī)提貨。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ù)。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ù)互不相容的全概率公式，有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的泊松分布.反之亦然.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)系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)有新生兒出生的概率可以用泊松分布計(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ù)的分布是泊松的.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+11000當(dāng)h→0,得到這組方程的解得到下面的截尾泊松(TruncatedPoisson)分布:經(jīng)過(guò)t

時(shí)間還剩下n

個(gè)顧客的概率35例某雜貨店鮮花柜臺(tái)每周初庫(kù)存18打玫瑰花.平均情況下，鮮花柜臺(tái)每天賣出去3打(一次一打)，但實(shí)際需求量服從泊松分布.一旦庫(kù)存水平剩下5打，就再訂貨補(bǔ)充到18打，下周一送貨。由于鮮花商品的特性，周末沒(méi)有賣出的玫瑰花就要扔掉，求下列值：(1)該周內(nèi)任何一天訂貨的概率.(2)周末扔掉的玫瑰花的平均數(shù)量.36因?yàn)橘?gòu)買的發(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é)果為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)研究的。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)也是依賴于狀態(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)表示系統(tǒng)的狀態(tài)，那么令排隊(duì)系統(tǒng)中有n個(gè)用戶的概率為pn.那么概率pn可以用下圖的狀態(tài)轉(zhuǎn)移關(guān)系圖來(lái)得到.

根據(jù)第3小節(jié)的解釋，在一個(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…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),因此有類似地系統(tǒng)平穩(wěn)狀態(tài)下，單位時(shí)間內(nèi)轉(zhuǎn)入和轉(zhuǎn)出次數(shù)要相等對(duì)于n=0的平衡方程為n-1nn+141從p0開(kāi)始遞歸求解平衡方程如下：對(duì)于n=0，有接下來(lái)，對(duì)n=1，有用替換并化簡(jiǎn)，得到用歸納法可以得到如下廣義穩(wěn)態(tài)概率公式從p0的值可以從等式求出.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ù)本題的信息，有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+p34612.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...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)分布(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/∞)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ù)最常用的隊(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é)期望得到系統(tǒng)中期望的顧客數(shù)隊(duì)列中期望的顧客數(shù)(平均隊(duì)長(zhǎng))而Ls與Ws(以及Lq與Wq)之間的關(guān)系稱為L(zhǎng)ittle公式(littleformula),具體關(guān)系包括如下系統(tǒng)中平均顧客數(shù)量與駐留系統(tǒng)的時(shí)間之間滿足：隊(duì)列中期望的顧客數(shù)(平均隊(duì)長(zhǎng))與排隊(duì)時(shí)間滿足：上述關(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í)間可以寫成

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

，建立Ls與Lq的關(guān)系.結(jié)合Little公式，得到根據(jù)定義，系統(tǒng)的平均顧客數(shù)與隊(duì)列中平均的顧客數(shù)的差值等于繁忙服務(wù)臺(tái)的平均數(shù)，因此有因此，得到了設(shè)施利用率=51例Ozark學(xué)院來(lái)訪者的停車位只有5個(gè)，使用這些停車位的車輛以泊松分布到達(dá)，每小時(shí)到達(dá)6輛車。停車時(shí)間服從均值為30分鐘的指數(shù)分布。到達(dá)后找不到空泊位的來(lái)訪者可以在停車場(chǎng)邊臨時(shí)停車位等待，直到有停著的車輛離開(kāi)。臨時(shí)車位只能放3輛車，而停不了也找不到臨時(shí)停車位的車輛必須去別的地方停車，求（1） 系統(tǒng)中有n輛車的概率；（2） 實(shí)際使用停車場(chǎng)的車輛的有效到達(dá)率；（3） 停車場(chǎng)平均的停車數(shù)量；（4） 一輛車在停車場(chǎng)內(nèi)等待停車位的平均時(shí)間；（5） 占據(jù)停車位的平均車輛數(shù)；（6） 停車場(chǎng)的平均使用率。注意到，一個(gè)停車位就是一個(gè)服務(wù)臺(tái)，這樣，系統(tǒng)共有c=5個(gè)并行的服務(wù)臺(tái).另外，系統(tǒng)的最大容量為5+3=8輛車.可以按照之前介紹的pn計(jì)算。52將λn和μn代入下面的公式得到p0=0.0481253有了p0,可以計(jì)算p1到p8如下n12345678pn0.144360.216540.216540.162400.097440.058470.035080.02105實(shí)際使用停車場(chǎng)的車輛的有效到達(dá)率的計(jì)算取決于停車場(chǎng)是否滿了。有效到達(dá)率可以通過(guò)如下示意圖計(jì)算車輛可以以λeff

進(jìn)入停車場(chǎng)或者以λlost離開(kāi).假如8輛車已經(jīng)在停車場(chǎng)，則到達(dá)的車便不能進(jìn)入停車場(chǎng)的概率為p8.因此停車設(shè)施54停車場(chǎng)內(nèi)車輛的平均數(shù)等于系統(tǒng)內(nèi)車輛的平均數(shù)Ls.我們可以用pn計(jì)算出Ls在臨時(shí)車位等待的車輛實(shí)際上就是隊(duì)列中的車輛.因此，等待找到車位的等待時(shí)間就是Wq.為確定Wq

，用因此占用了車位的平均車輛數(shù)就與繁忙服務(wù)臺(tái)的平均數(shù)相等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)56令，將其稱之為服務(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).57排隊(duì)系統(tǒng)的性能度量指標(biāo)Ls可以按照下面的方式得到：因?yàn)閷?duì)于本情形，剩下的系統(tǒng)性能度量指標(biāo)用6.2節(jié)的關(guān)系來(lái)計(jì)算.因此有58例Automata洗車房只運(yùn)行一個(gè)清洗位.車輛按照泊松分布到達(dá)，平均每小時(shí)4輛車，如果清洗位忙，則到達(dá)的車輛等在洗車房的停車場(chǎng).一輛車的清洗時(shí)間服從指數(shù)分布，平均值為10分鐘.不能進(jìn)停車場(chǎng)的車輛可在洗車房的路邊等待，這意味著從實(shí)際上來(lái)說(shuō)，系統(tǒng)是沒(méi)有容量限制的。為洗車房確定出停車場(chǎng)合適的停車泊位數(shù)量。該例中，λ=4輛車/小時(shí)，μ=60/10=6輛車/小時(shí).因?yàn)棣?lt;1,系統(tǒng)可以按照平穩(wěn)狀態(tài)運(yùn)行。一般來(lái)說(shuō)，不建議只用Ls來(lái)計(jì)算停車位數(shù)，因?yàn)閺哪撤N意義上，停車位代表了要保證最大可能的隊(duì)列長(zhǎng)度.59例如，停車場(chǎng)的設(shè)計(jì)要使得來(lái)到的車在至少90%的時(shí)候能找到停車位。為了做到這一點(diǎn)，令S表示停車位數(shù)，有S個(gè)停車位等價(jià)于系統(tǒng)中有S+1個(gè)位置.假如系統(tǒng)中最多有S個(gè)停車位，則到達(dá)的車輛90%的時(shí)候都能找到位置.這個(gè)條件等價(jià)于下面的概率條件：即根據(jù)有限項(xiàng)的幾何技術(shù)求和公式，有所以兩邊取對(duì)數(shù)(注意到ln(x)<0,0<x<1,不等式變號(hào))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í)間.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ù)分布，平均值為62例Automata洗車房只運(yùn)行一個(gè)清洗位.車輛按照λ=4輛車/小時(shí)泊松分布到達(dá)，該服務(wù)根據(jù)FCFS規(guī)則進(jìn)行的，一輛車的清洗時(shí)間μ=60/10=6輛車/小時(shí)，如果清洗位忙，則到達(dá)的車輛等在洗車房的停車場(chǎng).不能進(jìn)停車場(chǎng)的車輛可在洗車房的路邊等待。評(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í)間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的值，這將得到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í)系統(tǒng)中期望顧客數(shù)可以計(jì)算為當(dāng)時(shí)，Ls=N/2.同樣從Ls,利用λeff求出Ws,Wq,Lq.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ù)員，類似的問(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ù)依賴于當(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í)有67根據(jù)廣義模型，有根據(jù)根據(jù)，有注意，此時(shí)不要求成立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é))，70因此，根據(jù)廣義穩(wěn)態(tài)概率計(jì)算公式p0的值可以從求出，得到71系統(tǒng)的運(yùn)行指標(biāo)如下72例某社區(qū)由兩家出租車公司提供服務(wù)，每家公司有2輛出租車，且兩家公司平等分享市場(chǎng).事實(shí)上，叫車電話到達(dá)每家公司的派車辦公室的到達(dá)率為每小時(shí)8次.每次乘車的平均時(shí)間為12分鐘.叫車電話按照泊松分布到達(dá)，乘車時(shí)間服從指數(shù)分布.最近這個(gè)兩家公司被一個(gè)投資商購(gòu)買了，他打算把這兩個(gè)派車辦公室合成一個(gè)，以便為顧客提供更為優(yōu)質(zhì)的服務(wù).請(qǐng)分析老板的建議.從排隊(duì)論角度來(lái)看，出租車是服務(wù)臺(tái)，乘坐出租車就是服務(wù)，每家公司都可以表示為λ=8次/小時(shí)，出租車μ=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ì)算公式得到下表cλμp0LsWsLqWq2850.114.4440.5562.8440.35641650.0275.5860.3492.3860.149可以看到，等待乘車的時(shí)間在兩臺(tái)出租車情況下為0.356，合并后情況為0.149小時(shí)，明顯減少了50%多，公司合并以后效果非常明顯.以上的結(jié)論是，共同分擔(dān)服務(wù)總是一種更加有效的運(yùn)作模式.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é))的公式，得到75p0的值可以從求出，得到排隊(duì)系統(tǒng)的運(yùn)行指標(biāo)如下76例在合并的出租車公司問(wèn)題中，假設(shè)沒(méi)有新的經(jīng)費(fèi)來(lái)購(gòu)買更多出租車，又一個(gè)咨詢專家向老板建議，有一種減少等待時(shí)間的辦法是，一旦有6個(gè)顧客在等待用車，就讓派車辦公室通知新的顧客，告訴他們等待時(shí)間可能會(huì)很長(zhǎng).這種舉動(dòng)定會(huì)讓新的顧客去尋求別的公司的服務(wù)，但將會(huì)減少等式顧客的等待時(shí)間.請(qǐng)?jiān)u價(jià)這位專家的建議.將等待的顧客數(shù)限制在6個(gè)以內(nèi)就等價(jià)于設(shè)定N=6+4=10個(gè)顧客.因此專家建議的排隊(duì)模型為(M/M/4):(GD/10/∞),其中λ=16次/小時(shí)，μ=5次/小時(shí).cλμp0LsWsLqWq41650.031214.23980.27481.15420.0748177在設(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)印象的損害效果.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的值可以從求出，得到79排隊(duì)系統(tǒng)的運(yùn)行指標(biāo)如下例一個(gè)投資者每月平均投入1000美元購(gòu)買一種股票市場(chǎng)的債券.因?yàn)檫@個(gè)投資者必須要等待好的“買入”機(jī)會(huì)，實(shí)際發(fā)生的購(gòu)買時(shí)間是完全隨機(jī)的.該投資者平均要把債券保留3年，但是當(dāng)好的“賣出”機(jī)會(huì)來(lái)了，他會(huì)在隨機(jī)的時(shí)間把它賣掉.根據(jù)過(guò)去的統(tǒng)計(jì)表明，這個(gè)投資家大約25%的債券每年下跌20%左右，其余的75%每年上漲12%左右.請(qǐng)估算這個(gè)投資者在股票市場(chǎng)的(長(zhǎng)期)平均資產(chǎn)凈值.80從實(shí)際情況看，這位投資者并不需要排隊(duì)等待債券的買入或者賣出.買賣間隔的平均時(shí)間是1個(gè)月，因此每年有λ=12只債券.債券的銷售率為每年μ=1/3只債券.此時(shí)每只債券就是就是服務(wù)臺(tái)本身，有多少債券就有多少服務(wù)臺(tái)，這一情形符合(M/M/∞):(GD/∞/∞)模型.已知λ

和μ

，得到該投資者的預(yù)計(jì)(長(zhǎng)期)平均年度凈值為81機(jī)器伺服模型——(M/M/R):(GD/K/K),R<K這個(gè)模型的背景是有K臺(tái)機(jī)器的車間，當(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è)模型類似于前面介紹的(M/M/1):(GD/∞/m)模型，區(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(0<n<m),則此時(shí)有機(jī)器出現(xiàn)故障的發(fā)生率取決于完好狀態(tài)的機(jī)器數(shù)量K-n.即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).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.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)1.66%，不支持這樣的計(jì)劃。8712.7一般服務(wù)時(shí)間M/G/1模型前面討論的排隊(duì)模型到達(dá)時(shí)間和服務(wù)時(shí)間均服從指數(shù)分布，這類系統(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ì)模型稱為非馬氏排隊(duì)模型。這類排隊(duì)模型非常復(fù)雜，對(duì)于這類情形的分析，我們將在以后介紹采用模擬方法來(lái)研究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)公式.89服務(wù)設(shè)施為空閑的概率可按照下面公式求出由λeff=λ，根據(jù)Little公式可以從Ls求出來(lái).90例Automata洗車房只運(yùn)行一個(gè)清洗位.車輛按照泊松分布到達(dá),平均每小時(shí)4輛車，如果清洗位忙，則到達(dá)的車輛等在洗車房的停車場(chǎng).現(xiàn)在安裝了新的洗車系統(tǒng)，對(duì)所有車輛的服務(wù)時(shí)間均為10分鐘.該系統(tǒng)有何影響？λeff=λ=4輛車/小時(shí).服務(wù)時(shí)間為常數(shù),這樣E{t}=1/6小時(shí),方差Var{t}=0.因此91有意思的是，雖然到達(dá)率和離開(kāi)率與前面P58的泊松分布情況相同(λ=4輛車/小時(shí),μ=6輛車/小時(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é)果是合理的。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í)間越短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公式改寫為λ12…kkμkμkμ埃爾朗分布的數(shù)字特征：94例某單人裁縫店做西服，每套西服經(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，9512.8排隊(duì)系統(tǒng)最優(yōu)化排隊(duì)吸引的最優(yōu)化問(wèn)題有兩類：系統(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)題。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ù)水平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)失掉潛在的顧客的損失，只能依賴于調(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ī)劃的方法。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，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ù)曲線求出μ*/λ.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ò)比較確定μ*.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)值。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ǎ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.7010312.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ì)列去尋找其他類型的服務(wù)).在一站服務(wù)結(jié)束后，該顧客可能轉(zhuǎn)入另一個(gè)服務(wù)中心，或者重新進(jìn)入同一個(gè)中心，或者離開(kāi)系統(tǒng)。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)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