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

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

Krarup

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

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

16服務(wù)率以單位時間內(nèi)服務(wù)的顧客數(shù)量以服務(wù)一個顧客需要的時間當(dāng)討論服務(wù)臺服務(wù)時間（總假定排隊系統(tǒng)是存在顧客要服務(wù)）確定型隨機型，在系統(tǒng)非空條件下服務(wù)臺的概率分布服務(wù)設(shè)施中服務(wù)臺個數(shù)單個，每次只能服務(wù)一個顧客多個，可以同時服務(wù)多個顧客12.2.2服務(wù)臺服務(wù)模式17先到先服務(wù)（Firstcome,Firstserved），先進先出（Firstin,Firstout）后到先服務(wù)（Lastcome,Firstserved），庫存系統(tǒng)。隨機順序服務(wù)（Serviceinrandomorder,SIRO），該規(guī)則不考慮顧客到達先后順序，隨機地選擇顧客進行服務(wù)。優(yōu)先權(quán)排隊規(guī)則絕對搶先式，具有最高優(yōu)先級的顧客即刻獲得服務(wù)非絕對搶先式，具有最高級別的顧客即刻在隊列的最前端排隊，但不能馬上接受服務(wù)，直到當(dāng)前顧客（即使其級別較低）服務(wù)結(jié)束以后才能接受服務(wù)12.2.3排隊規(guī)則在出現(xiàn)顧客排隊的情況下，選擇顧客進行服務(wù)的選擇機制。18在有些排隊系統(tǒng)中，其排隊等候區(qū)域受到物理空間限制，當(dāng)隊列達到一定長度時，后續(xù)的顧客無法進入等待區(qū)，除非當(dāng)前接受服務(wù)的顧客接受服務(wù)后離開系統(tǒng)，后續(xù)新到顧客才被允許進入排隊區(qū)等待。對于有限隊列長度的排隊系統(tǒng)，其到達的顧客可視為其到達數(shù)量必須累積到排隊容量以后的成批的排隊。這是最簡單成批到達情況，原因在于顧客的批量是固定值。12.2.4排隊系統(tǒng)容量19只有1個服務(wù)臺的系統(tǒng)為單通道服務(wù)系統(tǒng)，在服務(wù)設(shè)施內(nèi)設(shè)置多個并行的服務(wù)臺是多通道服務(wù)系統(tǒng)。兩類不同的多通道服務(wù)系統(tǒng)，一般來說，在排隊論中都假設(shè)服務(wù)臺是相互獨立運作的多個服務(wù)臺共同為一個隊列服務(wù)每個服務(wù)臺僅為本隊列提供服務(wù)12.2.5服務(wù)通道數(shù)量在同一時刻能為顧客提供服務(wù)的并行服務(wù)臺數(shù)量20排隊系統(tǒng)中，許多服務(wù)設(shè)施提供的服務(wù)級數(shù)包括兩類單級的，例如高速公路收費站、車站檢票口等；多級的，例如醫(yī)院的體檢系統(tǒng)。 多級服務(wù)也可能是循環(huán)的，例如在含有產(chǎn)品質(zhì)量跟蹤控制功能的產(chǎn)品生產(chǎn)線中，一旦零部件經(jīng)過檢測不合格，則需要重新送到生產(chǎn)線再進行處理。下圖是帶有循環(huán)（有時候也稱之為反饋）服務(wù)的排隊系統(tǒng)。12.2.6服務(wù)級數(shù)21上述6個排隊系統(tǒng)基本特征元素，一般的可以充分的描述各種排隊過程。從上述介紹也可以看出排隊過程無處不在。排隊模型的要素的總結(jié)必須充分理解排隊系統(tǒng)的這6個特征元素，以清楚掌握排隊系統(tǒng)的運作過程，具體包括排隊通道和服務(wù)設(shè)施之間是如何相互連接和影響的，顧客又是如何被分配到排隊通道中的。2212.3指數(shù)分布的作用在大多數(shù)排隊情況中，顧客的到達是完全隨機的。這里的隨機意味著，一個事件的發(fā)生(如一個顧客的到達或一項任務(wù)的完成)不受上一個時間發(fā)生以后所經(jīng)過的時間長度的影響。排隊模型中，隨機到達間隔時間和服務(wù)時間用指數(shù)分布來定量描述，定義為對于指數(shù)分布(exponentialdistribution)λ為單位時間內(nèi)產(chǎn)生事件的速率。23為什么指數(shù)分布是完全隨機的？如何理解？假定現(xiàn)在是上午8:20,上一個顧客到達時間是8:02，下一個到達發(fā)生在8:29之前的概率只是8:20~8:29這一區(qū)間的函數(shù)，與上一個事件的發(fā)生(8:02~8:20)以來所流逝的時間長度完全無關(guān)。這個結(jié)果稱之為指數(shù)分布的無記憶性(memoryless)8:028:208:2924令指數(shù)分布f(t)表示相繼事件之間的時間t的概率分布。如果S為上一個事件發(fā)生以來的時間區(qū)間，則遺忘性意味著而0SS+TSTt證明：注意到對于平均值為1/λ的指數(shù)函數(shù)，我們有P(AB)=P(B|A)P(A)25指數(shù)分布的無記憶性很重要，因為它意味著如果我們希望知道下次到達的時間概率分布，那么自上次到達以后流逝的時間長短不具有影響。我們假設(shè)到達時間間隔服從λ=6的指數(shù)分布。那么無記憶特性意味著自上次到達以后不管經(jīng)過多長時間，那么下一次到達時間的概率分布仍然為6e-6t.這意味著要觀測未來到達模式，我們不需要跟蹤上一次到達之后經(jīng)過了多長時間。這種觀測可以簡化排隊系統(tǒng)的分析。26例假設(shè)在銀行花費的時間以均值為10分鐘指數(shù)地分布，即λ=1/10.問一個顧客在此銀行中花費15分鐘的概率是多少？給定一個顧客10分鐘以后仍舊在銀行中，她在銀行中將花費超過15分鐘的概率是多少？解如果X表示顧客在這個銀行中花費的時間，那么第一個概率正是第二個問題。由于指數(shù)分布，所以這個顧客已經(jīng)在銀行中花費10分鐘是沒有記憶的，這就意味著這個已經(jīng)等待10分鐘的顧客還要等5分鐘，其概率正好是2712.4生滅模型排隊系統(tǒng)中，任意時間它的狀態(tài)用這個時間在系統(tǒng)中的人數(shù)表示。則該狀態(tài)取決于各個時刻進入和離開人數(shù)的速率，這樣的系統(tǒng)稱之為生滅過程。生滅過程例子很多，地區(qū)的人口增減、細菌或細胞的繁殖與死亡、服務(wù)臺前的顧客數(shù)量變化等等。為了簡化，只考慮只有到達的純生模型和只有離開的純滅模型。純生模型的例子如為新生嬰兒制作出生證明，純滅模型的例子如一家商店對其庫存貨物的隨機提貨。2812.4.1純生模型定義

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

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

期間內(nèi)有n

個到達的概率在t

期間內(nèi)有n

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

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

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

上面的結(jié)果說明,若到達時間間隔服從平均值為1/λ的指數(shù)分布，則指定期間t內(nèi)的到達數(shù)服從平均值λt的泊松分布.反之亦然.31指數(shù)分布泊松分布隨機變量相繼到達之間的時間t指定T期間的到達數(shù)n取值范圍t≥0n=0,1,2,┅密度函數(shù)平均值1/λ時間單元T期間有λT個到達累積概率P(A期間無達到)指數(shù)分布與泊松分布之間的關(guān)系32例某人口稀少州的出生率為每12分鐘出生一個新生嬰兒。出生間隔時間服從指數(shù)分布，求下列各值：(1)每年出生的平均數(shù).(2)任何一天內(nèi)無新生兒出生的概率.(3)假設(shè)在3個小時時間內(nèi)前2小時已經(jīng)發(fā)出了40份出生證明，求這3個小時內(nèi)發(fā)出50份出生證明的概率。每天的出生率為該州每年出生人口為任意一天沒有新生兒出生的概率可以用泊松分布計算為假設(shè)在3個小時內(nèi)的前2小時已經(jīng)發(fā)出了40份出生證明，計算3小時內(nèi)發(fā)出50份出生證明的概率，相當(dāng)于1小時(=3-2)內(nèi)出生10(=50-40)個新生兒，因為出生數(shù)的分布是泊松的.3312.4.2純滅模型在純滅模型中，系統(tǒng)在0時刻開始時有N個顧客，后面沒有新的顧客到達.離開的發(fā)生率為每單位μ個顧客.為了建立t時間單位后剩下n個顧客的概率pn(t)的差分-微分方程，根據(jù)出現(xiàn)n個顧客的情況，依據(jù)不相容的全概率公式，有t+h(0,t)(0,t+h)NN0nn0n+11000當(dāng)h→0,得到這組方程的解得到下面的截尾泊松(TruncatedPoisson)分布:經(jīng)過t

時間還剩下n

個顧客的概率35例某雜貨店鮮花柜臺每周初庫存18打玫瑰花.平均情況下，鮮花柜臺每天賣出去3打(一次一打)，但實際需求量服從泊松分布.一旦庫存水平剩下5打，就再訂貨補充到18打，下周一送貨。由于鮮花商品的特性，周末沒有賣出的玫瑰花就要扔掉，求下列值：(1)該周內(nèi)任何一天訂貨的概率.(2)周末扔掉的玫瑰花的平均數(shù)量.36因為購買的發(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).為了計算這個值,我們需要用到pn(7),n=1,2,…,18,計算結(jié)果為3712.5廣義泊松排隊模型本節(jié)利用生滅模型，建立一個通用的排隊模型。再根據(jù)到達間隔和服務(wù)時間服從指數(shù)分布，推導(dǎo)出基于泊松分布的排隊論模型。廣義模型的建立是基于排隊情形的長期行為，或平穩(wěn)狀態(tài)行為，這種狀態(tài)在系統(tǒng)經(jīng)過充分長時間的運行后得到的。這種分析和系統(tǒng)初期運行期間所常見的瞬時(transient)行為完全不同。本章不討論瞬時行為的一個原因是由于對它的解析過于復(fù)雜；另一個原因是由于對大多數(shù)排隊系統(tǒng)都是在平穩(wěn)狀態(tài)下來研究的。38廣義模型假設(shè)，到達率和離開率都是與狀態(tài)相關(guān)的(statedependent),也就說系統(tǒng)的狀態(tài)以服務(wù)設(shè)施中的顧客數(shù)量來度量的。例如，在高速公路收費口，在高峰時間收費員通常會提高收費速度。道路交通網(wǎng)絡(luò)上的信號燈控制系統(tǒng)會依據(jù)交通流量的變化，信號配時作出變化，此時道路網(wǎng)絡(luò)的狀態(tài)也是依賴于狀態(tài)的。定義

n=系統(tǒng)中的顧客總數(shù)(排隊+正在接受服務(wù)的)

λn=已知系統(tǒng)中有n個顧客的到達率

μn=已知系統(tǒng)中有n個顧客的離開率

pn=系統(tǒng)中有n個顧客的平穩(wěn)狀態(tài)概率廣義模型中，pn作為λn和μn的函數(shù)，利用這些概率求出系統(tǒng)行為中的度量指標(biāo)，例如平均隊長、平均等待時間和設(shè)備利用率.39如果以系統(tǒng)中的顧客數(shù)量來表示系統(tǒng)的狀態(tài)，那么令排隊系統(tǒng)中有n個用戶的概率為pn.那么概率pn可以用下圖的狀態(tài)轉(zhuǎn)移關(guān)系圖來得到.

根據(jù)第3小節(jié)的解釋，在一個時間間隔h里多于1個事件發(fā)生的概率隨著h→0而趨于0.這就意味著，對于n>0,狀態(tài)n只能變成兩種可能的狀態(tài):

當(dāng)以離開率離開時變成n-1,當(dāng)按照到達率到達時變成n+1.

狀態(tài)0按照到達率到達時只能變成狀態(tài)1.注意到，假如系統(tǒng)為空時,因為沒有離開發(fā)生，沒有定義.012n-1nn+1…40當(dāng)系統(tǒng)處于平穩(wěn)狀態(tài)條件下，轉(zhuǎn)入率等于轉(zhuǎn)出率，也就說單位時間進入該狀態(tài)的平均次數(shù)和單位時間內(nèi)離開狀態(tài)的平均次數(shù)要相等。所以，狀態(tài)n

只能變成狀態(tài)(n-1)和狀態(tài)(n+1),因此有類似地系統(tǒng)平穩(wěn)狀態(tài)下，單位時間內(nèi)轉(zhuǎn)入和轉(zhuǎn)出次數(shù)要相等對于n=0的平衡方程為n-1nn+141從p0開始遞歸求解平衡方程如下：對于n=0，有接下來，對n=1，有用替換并化簡，得到用歸納法可以得到如下廣義穩(wěn)態(tài)概率公式從p0的值可以從等式求出.42解得43例

B&K食品店有3個收款臺.經(jīng)理根據(jù)店內(nèi)顧客數(shù)量，按照下列安排決定提供服務(wù)的收款臺個數(shù)。顧客按照平均10位/小時的泊松分布來收款區(qū).每位顧客的平均收款時間為指數(shù)分布，平均為12分鐘.求n個顧客在收款區(qū)的平穩(wěn)狀態(tài)概率pn店內(nèi)顧客數(shù)量使用收款臺的個數(shù)1~314~626人以上3根據(jù)本題的信息，有44因此p0的值從下面的等式求出利用幾何級數(shù)得到45因此，p0=1/55.知道了p0，就可以求出pn.進而可以計算出系統(tǒng)中使用不同收款臺個數(shù)的概率.例如使用一個收款臺的概率就是最多出現(xiàn)3個顧客的概率=p1+p2+p34612.6特殊泊松排隊12.6.1排隊系統(tǒng)的Kendall-Lee的符號表示下圖顯示帶有c個并行服務(wù)臺的特殊泊松排隊情形。系統(tǒng)中的顧客數(shù)定義為正在接受服務(wù)的顧客加隊列中等待服務(wù)的顧客。服務(wù)臺1服務(wù)臺1服務(wù)臺1...服務(wù)臺1服務(wù)臺1服務(wù)臺1...47為了方便表示上圖排隊的情形的特性，采用下面的格式(a/b/c):(d/e/f)其中，a=到達分布，b=離開(服務(wù)時間)分布，c=并行服務(wù)臺個數(shù)，d=排隊規(guī)則，e=系統(tǒng)中最大運行容納的顧客數(shù)，f=顧客輸入源的多少(有限或無限)表示到達和離開分布(a和b)的標(biāo)準(zhǔn)記號有M=馬爾科夫或泊松分布，D=常數(shù)(確定型)時間，Ek=參數(shù)為k的埃爾朗或Γ分布(等價于獨立指數(shù)分布和)，GI=到達間隔時間的一般性/通用分布，G=服務(wù)時間的一般性/通用分布排隊規(guī)則(符號d)包括FCFS=先到先服務(wù)，LCFS=后到先服務(wù)，SIRO=隨機秩序服務(wù)，GD=一般/任意規(guī)則(M/D/10):(GD/20/∞),(M/E2/8/):(FCFS/10/∞)4812.6.2隊列行為的平穩(wěn)狀態(tài)度量Ls=系統(tǒng)中顧客的期望數(shù)量Lq=隊列中顧客的期望數(shù)量Ws=系統(tǒng)中的期望等待時間Wq=隊列中的期望等待時間

=繁忙服務(wù)臺的期望數(shù)最常用的隊列行為度量指標(biāo)有系統(tǒng)包括隊列加上服務(wù)設(shè)施。下面說明如何利用系統(tǒng)的狀態(tài)n

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

是系統(tǒng)的有效到達率，當(dāng)所有到達的顧客都可能加入時，就為λ；如果系統(tǒng)滿了(存在容量限制系統(tǒng))，則顧客不能加入，λeff<λ清華版p319不準(zhǔn)確50Ws和Wq之間也存在直接的關(guān)系。由定義希望系統(tǒng)駐留時間=期望排隊時間+期望服務(wù)時間可以寫成

對上式兩邊乘以λeff

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

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

，用因此占用了車位的平均車輛數(shù)就與繁忙服務(wù)臺的平均數(shù)相等5512.6.3單服務(wù)臺模型本節(jié)介紹僅有一個服務(wù)臺到達率為λ、服務(wù)率為μ的排隊服務(wù)系統(tǒng).首先討論系統(tǒng)容量無窮大的情形,再討論系統(tǒng)容量有限情形.之前介紹的各種排隊系統(tǒng)的性能指標(biāo)與具體的排隊規(guī)則沒有關(guān)系，所以我們用一般排隊規(guī)則GD.(M/M/1):(GD/∞/∞)基本假設(shè)如下：與排隊系統(tǒng)狀態(tài)無關(guān)56令，將其稱之為服務(wù)強度或業(yè)務(wù)密度，則廣義模型中pn

的表達式簡化為為了求p0的值，用等式設(shè)ρ<1,利用幾何級數(shù)求和公式有所以所以pn的數(shù)學(xué)推導(dǎo)將用到條件ρ<1或者λ<μ.如果λ<μ則幾何級發(fā)散，平穩(wěn)態(tài)概率不存在.這個結(jié)果有直觀的意義，除非服務(wù)率大于到達率，否則隊列長度將不斷增長，不可能到達平穩(wěn)狀態(tài).57排隊系統(tǒng)的性能度量指標(biāo)Ls可以按照下面的方式得到：因為對于本情形，剩下的系統(tǒng)性能度量指標(biāo)用6.2節(jié)的關(guān)系來計算.因此有58例Automata洗車房只運行一個清洗位.車輛按照泊松分布到達，平均每小時4輛車，如果清洗位忙，則到達的車輛等在洗車房的停車場.一輛車的清洗時間服從指數(shù)分布，平均值為10分鐘.不能進停車場的車輛可在洗車房的路邊等待，這意味著從實際上來說，系統(tǒng)是沒有容量限制的。為洗車房確定出停車場合適的停車泊位數(shù)量。該例中，λ=4輛車/小時，μ=60/10=6輛車/小時.因為ρ<1,系統(tǒng)可以按照平穩(wěn)狀態(tài)運行。一般來說，不建議只用Ls來計算停車位數(shù)，因為從某種意義上，停車位代表了要保證最大可能的隊列長度.59例如，停車場的設(shè)計要使得來到的車在至少90%的時候能找到停車位。為了做到這一點，令S表示停車位數(shù)，有S個停車位等價于系統(tǒng)中有S+1個位置.假如系統(tǒng)中最多有S個停車位，則到達的車輛90%的時候都能找到位置.這個條件等價于下面的概率條件：即根據(jù)有限項的幾何技術(shù)求和公式，有所以兩邊取對數(shù)(注意到ln(x)<0,0<x<1,不等式變號)60(M/M/1):(GD/∞/∞)的等待時間分布廣義模型中得到的pn

與排隊規(guī)則完全無關(guān).這意味著,排隊系統(tǒng)性能的平均度量指標(biāo)(Ws,Wq,Ls,Lq)可以用于所有排隊規(guī)則.雖然平均等待時間與排隊規(guī)則無關(guān),但它的概率密度函數(shù)卻不然.我們基于FCFS規(guī)則的M/M/1模型導(dǎo)出等待時間的分布來說明.令τ為剛剛到達的一位顧客為了獲得服務(wù)必須駐留在系統(tǒng)的時間.根據(jù)FCFS規(guī)則，假如一個剛剛到達的顧客前面還有n個顧客在系統(tǒng)中，則其中是當(dāng)前在接受服務(wù)的顧客所需要的完成服務(wù)的時間,t2,t3,…,tn為隊列中的n-1個顧客的服務(wù)時間.時間tn+1表示剛剛到達的這個顧客的服務(wù)時間.61定義為已知系統(tǒng)中有n個顧客在剛剛到達的顧客之前的條件下,τ的條件密度函數(shù).因為服務(wù)時間的分布是指數(shù)的，指數(shù)分布的遺忘性質(zhì)表明，也是指數(shù)的，服從相同的分布.因此，τ等于(n+1)個同分布的獨立指數(shù)隨機變量之和.由概率論可知，服從帶有參數(shù)和(n+1)的Г分布.因此有因此，為一指數(shù)分布，平均值為62例Automata洗車房只運行一個清洗位.車輛按照λ=4輛車/小時泊松分布到達，該服務(wù)根據(jù)FCFS規(guī)則進行的，一輛車的清洗時間μ=60/10=6輛車/小時，如果清洗位忙，則到達的車輛等在洗車房的停車場.不能進停車場的車輛可在洗車房的路邊等待。評價用Ws作為估計系統(tǒng)中等待時間的可靠性.回答這個問題的一個方法是，估計顧客中等待時間超過Ws的比例，注意到，我們得到在FCFS規(guī)則下,大約37%的顧客的等待時間比Ws要長.我們注意到所計算的概率e-1與任何(M/M/1):(FCFS/∞/∞)的到達率和服務(wù)率都無關(guān),這意味著它的值不能減少.這樣,如果我們以Ws來設(shè)計系統(tǒng)的話,將有36.8%的顧客的等待時間長于平均等待時間63(M/M/1):(GD/N/∞)模型這個模型和(M/M/1):(GD/∞/∞)不同之處在于，系統(tǒng)最多容納的顧客數(shù)(最大隊列長度為N-1)為N.例如流水線上放置工件的空間是有限的.當(dāng)系統(tǒng)中的顧客數(shù)達到N時，不允許再有到達，因此有利用，根據(jù)廣義模型的穩(wěn)態(tài)概率公式可以從等式求出p0的值，這將得到64或因此有在這個模型中,的值不需要小于1,因為系統(tǒng)的到達受到系統(tǒng)顧客上限N的限制.這意味著在這種情況下,重要的是到達率λeff而不是λ.由于系統(tǒng)中有N個顧客，再來的顧客就不再進入系統(tǒng).此時系統(tǒng)中期望顧客數(shù)可以計算為當(dāng)時，Ls=N/2.同樣從Ls,利用λeff求出Ws,Wq,Lq.66(M/M/1):(GD/∞/m)模型這個模型和(M/M/1):(GD/∞/∞)不同之處在于，系統(tǒng)的顧客源的顧客總數(shù)為m.例如最常見的是機器發(fā)生故障停機待修的問題，此時總共有m臺機器，機器發(fā)生故障即表示顧客“到達”，修理工人是服務(wù)員，類似的問題還有m個打字員共有一臺打字機。雖然顧客有m個，但每個顧客到達并經(jīng)過服務(wù)以后，仍然回到原來的發(fā)生源中，所以仍然會到達。顧客源總數(shù)達到m時，此時顧客單位時間內(nèi)的到達次數(shù)依賴于當(dāng)前尚未到達系統(tǒng)的顧客數(shù)，假設(shè)每個顧客進入系統(tǒng)的到達率為λ,進入系統(tǒng)的顧客為n,(0<n<m),則系統(tǒng)外的顧客為m-n,所以系統(tǒng)的到達率而系統(tǒng)的離開率取決于服務(wù)臺數(shù)量為1，此時有67根據(jù)廣義模型，有根據(jù)根據(jù)，有注意，此時不要求成立68根據(jù)Little公式以及系統(tǒng)期望公式，有6912.6.4多服務(wù)臺模型本節(jié)考慮有多個并行服務(wù)臺的3個排隊模型。前兩個是上一節(jié)介紹的單服務(wù)臺的多服務(wù)臺版本，第三個模型針對自助服務(wù)的情況，等價于無限個并行服務(wù)臺情形。(M/M/c):(GD/∞/∞)模型在這個模型中有c個并行的服務(wù)臺.到達率為λ,每個服務(wù)臺的服務(wù)率為μ.因為對系統(tǒng)中的排隊人數(shù)沒有限制，所以使用并行服務(wù)臺的效果使得設(shè)施的服務(wù)率成比例的增加.根據(jù)廣義模型(第五節(jié))，70因此，根據(jù)廣義穩(wěn)態(tài)概率計算公式p0的值可以從求出，得到71系統(tǒng)的運行指標(biāo)如下72例某社區(qū)由兩家出租車公司提供服務(wù)，每家公司有2輛出租車，且兩家公司平等分享市場.事實上，叫車電話到達每家公司的派車辦公室的到達率為每小時8次.每次乘車的平均時間為12分鐘.叫車電話按照泊松分布到達，乘車時間服從指數(shù)分布.最近這個兩家公司被一個投資商購買了，他打算把這兩個派車辦公室合成一個，以便為顧客提供更為優(yōu)質(zhì)的服務(wù).請分析老板的建議.從排隊論角度來看，出租車是服務(wù)臺，乘坐出租車就是服務(wù)，每家公司都可以表示為λ=8次/小時，出租車μ=60/12=5次/小時乘坐的(M/M/2):(GD/∞/∞)模型.合并以后得到(M/M/4):(GD/∞/∞)模型，其參數(shù)為λ=16次/小時，μ=5次/小時.73根據(jù)參數(shù)，利用排隊系統(tǒng)運行性能指標(biāo)計算公式得到下表cλμp0LsWsLqWq2850.114.4440.5562.8440.35641650.0275.5860.3492.3860.149可以看到，等待乘車的時間在兩臺出租車情況下為0.356，合并后情況為0.149小時，明顯減少了50%多，公司合并以后效果非常明顯.以上的結(jié)論是，共同分擔(dān)服務(wù)總是一種更加有效的運作模式.74(M/M/c):(GD/N/∞),c≤N模型這個模型與(M/M/c):(GD/∞/∞)模型不同之處在于，系統(tǒng)上限是有限的并且等于N.這就意味著，最大隊列長度是N-c.到達率和服務(wù)率分別是λ和μ.因為系統(tǒng)上限是N,因此有效到達率小于λ.按照廣義模型，當(dāng)前模型的將上述代入穩(wěn)態(tài)概率(第五節(jié))的公式，得到75p0的值可以從求出，得到排隊系統(tǒng)的運行指標(biāo)如下76例在合并的出租車公司問題中，假設(shè)沒有新的經(jīng)費來購買更多出租車，又一個咨詢專家向老板建議，有一種減少等待時間的辦法是，一旦有6個顧客在等待用車，就讓派車辦公室通知新的顧客，告訴他們等待時間可能會很長.這種舉動定會讓新的顧客去尋求別的公司的服務(wù)，但將會減少等式顧客的等待時間.請評價這位專家的建議.將等待的顧客數(shù)限制在6個以內(nèi)就等價于設(shè)定N=6+4=10個顧客.因此專家建議的排隊模型為(M/M/4):(GD/10/∞),其中λ=16次/小時，μ=5次/小時.cλμp0LsWsLqWq41650.031214.23980.27481.15420.0748177在設(shè)置系統(tǒng)能力上限之前的平均等待時間為Wq=0.149小時，大約是新的平均等待時間0.075小時的兩倍.等待時間的大幅度減少的代價是流失了大約3.6%的潛在顧客(p10=0.03574).這個結(jié)果還不能反映顧客對公司經(jīng)營印象的損害效果.78(M/M/∞):(GD/∞/∞)——自助服務(wù)模型在這個模型中，因為顧客本身也是服務(wù)臺，因此服務(wù)臺數(shù)量無限.該模型的一個典型例子是參加進入系統(tǒng)選課的學(xué)生人數(shù)、在某個行業(yè)的公司數(shù)量.這個模型假設(shè)穩(wěn)定的到達率和服務(wù)率分別為λ和μ.

按照前面的廣義排隊模型，有因此有p0的值可以從求出，得到79排隊系統(tǒng)的運行指標(biāo)如下例一個投資者每月平均投入1000美元購買一種股票市場的債券.因為這個投資者必須要等待好的“買入”機會，實際發(fā)生的購買時間是完全隨機的.該投資者平均要把債券保留3年，但是當(dāng)好的“賣出”機會來了，他會在隨機的時間把它賣掉.根據(jù)過去的統(tǒng)計表明，這個投資家大約25%的債券每年下跌20%左右，其余的75%每年上漲12%左右.請估算這個投資者在股票市場的(長期)平均資產(chǎn)凈值.80從實際情況看，這位投資者并不需要排隊等待債券的買入或者賣出.買賣間隔的平均時間是1個月，因此每年有λ=12只債券.債券的銷售率為每年μ=1/3只債券.此時每只債券就是就是服務(wù)臺本身，有多少債券就有多少服務(wù)臺，這一情形符合(M/M/∞):(GD/∞/∞)模型.已知λ

和μ

，得到該投資者的預(yù)計(長期)平均年度凈值為81機器伺服模型——(M/M/R):(GD/K/K),R<K這個模型的背景是有K臺機器的車間，當(dāng)1臺機器出現(xiàn)故障時，就呼叫R個有時間的修理工之一來進行修理.每臺機器的故障率為每單位時間λ次故障，每個修理工修理故障及其的服務(wù)率為每單位時間μ臺機器.所有的故障和服務(wù)假定都服從泊松分布.這個模型類似于前面介紹的(M/M/1):(GD/∞/m)模型，區(qū)別在于，本模型中有R個修理工。82本模型有有限個輸入源，原因在于，此時總共有K臺機器，機器發(fā)生故障即表示顧客“到達”，修理工人是服務(wù)員。雖然有K臺機器，但每個發(fā)生故障的機器經(jīng)過維修以后回到良好狀態(tài)，但是容易再次發(fā)生故障，所以仍然會有“顧客”到達。顧客源總數(shù)達到K時，此時顧客單位時間內(nèi)的到達次數(shù)依賴于當(dāng)前尚未到達系統(tǒng)的顧客數(shù)，假設(shè)每個顧客進入系統(tǒng)的到達率為λ,進入系統(tǒng)的顧客(即等待維修的機器)為n(0<n<m),則此時有機器出現(xiàn)故障的發(fā)生率取決于完好狀態(tài)的機器數(shù)量K-n.即83根據(jù)廣義排隊模型，根據(jù)廣義排隊模型的穩(wěn)態(tài)概率計算公式，可以得到84遺憾的是，在(M/M/R):(GD/K/K)模型(R<K)中,沒有計算Ls、Lq、Ws和Wq的簡單的、封閉型的表達式，必須用下面的基本定義來計算：其中，例ToolCo公司經(jīng)營一家22臺機床的工廠.已知每臺機床平均每2小時發(fā)生一次故障，修理工作平均需要12分鐘.故障間隔時間均服從指數(shù)分布.ToolCo想要確定修理工數(shù)量，以保證工廠能“平穩(wěn)的”運轉(zhuǎn).85要分析該情況，考察作為修理工數(shù)的函數(shù)的機床生產(chǎn)率，這一生產(chǎn)率的度量可以定義為該情形屬于(M/M/R):(GD/K/K)模型，其中λ=0.5,μ=5,R=1,2,3,4,系統(tǒng)上限=22,輸入源=22.根據(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機床生產(chǎn)率45.4480.1588.7990.45邊際增長率—34.718.641.6686上述結(jié)果說明，用1個修理工時，生產(chǎn)率很低(45.44%),把修理工增加到2個時，生產(chǎn)率增加到80.15%，上升了34.71%.當(dāng)雇用3個修理工時，生產(chǎn)率只增加了8.64%，提高到88.79%，而4個修理工只把生產(chǎn)率增加很小量1.66%，提高到90.45%.從這些結(jié)果可以判斷出，用2個修理工最劃算，用3個修理工的效果不明顯，因為生產(chǎn)率只提高了8.64%.當(dāng)然我們可以用經(jīng)費上的比較來確定是否劃算，這需要對第三個修理工的成本和8.64%的生產(chǎn)率提高所帶來的收入進行比較.至于雇用第4個修理工，生產(chǎn)率的微量增長1.66%，不支持這樣的計劃。8712.7一般服務(wù)時間M/G/1模型前面討論的排隊模型到達時間和服務(wù)時間均服從指數(shù)分布，這類系統(tǒng)的主要特征是Markov特性，即未來狀態(tài)僅由當(dāng)前系統(tǒng)的狀態(tài)決定。但是當(dāng)?shù)竭_時間間隔和服務(wù)時間間隔至少至少有一個不服從負(fù)指數(shù)分布時，僅靠當(dāng)前狀態(tài)不足以推斷未來狀態(tài)，這樣的排隊模型稱為非馬氏排隊模型。這類排隊模型非常復(fù)雜，對于這類情形的分析，我們將在以后介紹采用模擬方法來研究88(M/G/1):(GD/∞/∞)排隊模型本節(jié)介紹一個很少出現(xiàn)的具有解析結(jié)果的非泊松排隊.它所描述的情況是，服務(wù)時間t

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

上述問題對應(yīng)著M/M/c模型，要確定c的最優(yōu)值.費用模型為,每小時λ=17.5個請求和每小時μ=10個請求.注意到當(dāng)c>λ/μ時，排隊系統(tǒng)處于穩(wěn)態(tài)，依次增加服務(wù)臺個數(shù)，計算Ls及成本，結(jié)果表明，最優(yōu)員工數(shù)為4.cLsz27.467397.3532.217146.8541.842140.1051.769148.4561.754159.7010312.10排隊網(wǎng)絡(luò)當(dāng)一組資源由一組顧客共享時形成了排隊網(wǎng)絡(luò)。每個資源表示一個可能有多個服務(wù)臺并行工作的服務(wù)中心。如果一個到達的顧客發(fā)現(xiàn)一個特定的中心繁忙，他可能加入該中心的隊列等候服務(wù)(也可能離開該隊列去尋找其他類型的服務(wù)).在一站服務(wù)結(jié)束后，該顧客可能轉(zhuǎn)入另一個服務(wù)中心，或者重新進入同一個中心，或者離開系統(tǒng)。104在串連隊列中,一旦一個顧客進入系統(tǒng),他將必須留在系統(tǒng)中直到接受了全套服務(wù)。通常,每個服務(wù)臺前都運行等候,前面討論的M/Ek/1模型是這種串連模型的特例,在M/Ek/1模型中除了第一個服務(wù)臺前可以有等候隊列,其他的服務(wù)臺是不允許有等候的,在這種情況下,必須是n個服務(wù)項目都結(jié)束以后,一個新的顧客才運行進入系統(tǒng)接受服務(wù)。12.10.1開放排隊系統(tǒng)串聯(lián)系統(tǒng)或序貫系統(tǒng)105服務(wù)網(wǎng)絡(luò)行為由輸出分布、各服務(wù)臺的服務(wù)時間分布以及輸入分布和各種排隊規(guī)則共同確定.在一個串連網(wǎng)絡(luò)中,由于一個服務(wù)臺的輸出是下一個服務(wù)臺的輸入,網(wǎng)絡(luò)的穩(wěn)態(tài)性質(zhì)由隊列的輸出分布共同規(guī)定.在這個方面，Burke已經(jīng)證明：在一個M/M