計(jì)算機(jī)系統(tǒng)建模與分析排隊(duì)論

計(jì)算機(jī)系統(tǒng)的建模與分析一、排隊(duì)論及其應(yīng)用二、PetriNets及其應(yīng)用排隊(duì)論及其應(yīng)用內(nèi)容框架輸入過程排隊(duì)規(guī)則服務(wù)臺(tái)排隊(duì)系統(tǒng)分類符號(hào)表示研究方式典型模型及其應(yīng)用系統(tǒng)意義畫狀態(tài)轉(zhuǎn)移速度圖寫狀態(tài)轉(zhuǎn)移速度矩陣給出狀態(tài)概率方程計(jì)算基本數(shù)量指標(biāo)應(yīng)用舉例排隊(duì)論排隊(duì)論(QueuingTheory)：又稱隨機(jī)服務(wù)系統(tǒng)理論(RandomServiceSystemTheory),是一門研究擁擠現(xiàn)象(排隊(duì)、等待)的科學(xué)。具體地說，它是在研究各種排隊(duì)系統(tǒng)概率規(guī)律性的基礎(chǔ)上，解決相應(yīng)排隊(duì)系統(tǒng)的最優(yōu)設(shè)計(jì)（靜態(tài)）和最優(yōu)控制（動(dòng)態(tài)）問題。排隊(duì)論所討論的是一個(gè)系統(tǒng)對(duì)一群體提供某種服務(wù)時(shí)該群體占用此服務(wù)系統(tǒng)時(shí)所呈現(xiàn)的狀態(tài)。在界定排隊(duì)問題中，必須交代清楚的事項(xiàng)包括：

1．群體到達(dá)系統(tǒng)的情況；

2．系統(tǒng)對(duì)群體中各個(gè)部分提供服務(wù)時(shí)花費(fèi)的時(shí)間長(zhǎng)短；

3．系統(tǒng)提供服務(wù)的先后次序；

到達(dá)系統(tǒng)的個(gè)體稱作“顧客”;提供服務(wù)的系統(tǒng)可由一個(gè)或者一個(gè)以上的“服務(wù)臺(tái)”組成;“服務(wù)時(shí)間”相當(dāng)于顧客占用服務(wù)臺(tái)的時(shí)間;而服務(wù)臺(tái)對(duì)顧客們提供服務(wù)的次序則稱作“排隊(duì)規(guī)則”。服務(wù)系統(tǒng)的狀態(tài)通常是以顧客留在服務(wù)系統(tǒng)上的數(shù)量來表示，這個(gè)數(shù)量稱作“隊(duì)列長(zhǎng)度”或者簡(jiǎn)稱為“隊(duì)長(zhǎng)”;有時(shí)也以顧客停留在系統(tǒng)上的時(shí)間表示，這段時(shí)間稱作“等待時(shí)間”。等待時(shí)間由兩個(gè)部份組成，其一為顧客等候使用服務(wù)臺(tái)的“延誤時(shí)間”,其二為占用服務(wù)臺(tái)的時(shí)間，即服務(wù)時(shí)間。排隊(duì)論的一些應(yīng)用問題1、通訊問題電話交換機(jī)通常僅有有限條電話線以溝通音汛如果在某一時(shí)刻所有的電話線均被占用，那么新的使用要求就必須等到有一條線空下來時(shí)方能滿足，這時(shí)電話線的使用要求是排隊(duì)問題電話線為服務(wù)臺(tái)，而占用電話線的時(shí)間為服務(wù)時(shí)間，而一般使用電話線的排列規(guī)則為“先到先占”．

2、公共服務(wù)問題許多公共服務(wù)事業(yè)對(duì)群眾提供服務(wù)的水平，或者公共服務(wù)設(shè)施的使用情況也可納入排隊(duì)問題。例如銀行的服務(wù)人員，郵局的服務(wù)員，醫(yī)院的病床，飯店的座位等可當(dāng)作服務(wù)臺(tái)，服務(wù)時(shí)間以及到達(dá)顧客則與實(shí)際的情形完全一致一般來說排隊(duì)規(guī)則均為先到先占．但是在某些情形下也可以有優(yōu)先權(quán)的出現(xiàn)，例如病危的患者可以有優(yōu)先占用病床的權(quán)利．3、救護(hù)、公安系統(tǒng)警察，消防人員，消防車，醫(yī)院救護(hù)車均可當(dāng)作服務(wù)臺(tái)，緊急事故的發(fā)生相當(dāng)于顧客的到達(dá)，通常這類問題都要求極低的服務(wù)臺(tái)使用率，因而當(dāng)一件緊急事故發(fā)生后有足夠的應(yīng)付能力(至少有一個(gè)服務(wù)臺(tái)可以立即使用)．4、存量問題儲(chǔ)存系統(tǒng)中存量的變化的隨機(jī)行為和排隊(duì)論中的隊(duì)列長(zhǎng)度變化的隨機(jī)行為有相似的地方。例如，零售商店貨柜上的商品，圖書館的藏書，水庫(kù)的存水量都可視作隊(duì)長(zhǎng)，賣出的商品，借出的書籍，放水灌溉或發(fā)電可視作顧客的離去，而進(jìn)貨、還書、由下雨或河水引入增加貯水量則為顧客到達(dá)。5、交通問題港口的碼頭是服務(wù)臺(tái)，船只為顧客。碼頭的使用決定了港口的吞吐量。飛機(jī)跑道或者停機(jī)坪可以作為服務(wù)臺(tái)，飛機(jī)起降為顧客的服務(wù)要求，如何安排飛機(jī)班次便利旅客并使飛機(jī)起降依次不紊是機(jī)場(chǎng)調(diào)度的重要問題。

6、生產(chǎn)線問題在工廠生產(chǎn)線上，機(jī)器、工人甚至物料運(yùn)輸設(shè)備如何安排以保證生產(chǎn)率的水平，降低生產(chǎn)過程中原料和半成品的存量往往也可通過排隊(duì)問題的研究獲得解決．在這類問題里，產(chǎn)品為顧客，機(jī)器、工人或者有關(guān)生產(chǎn)、運(yùn)輸設(shè)備為服務(wù)臺(tái)．7、計(jì)算機(jī)配置問題在計(jì)算機(jī)內(nèi)部中央處理機(jī)，輸入輸出設(shè)備可當(dāng)作服務(wù)臺(tái)，計(jì)算程序?yàn)轭櫩停谟?jì)算機(jī)網(wǎng)絡(luò)問題里計(jì)算機(jī)本身可以當(dāng)作服務(wù)臺(tái)，計(jì)算機(jī)程序或指令通過網(wǎng)絡(luò)可由一個(gè)計(jì)算機(jī)傳送至另一計(jì)算機(jī)，這類問題通常都以網(wǎng)絡(luò)隊(duì)列形式出現(xiàn)．排隊(duì)論的起源與發(fā)展排隊(duì)論起源于20世紀(jì)初的電話通話，20世紀(jì)初Bell電話公司為減少電話呼叫，研究電話線路合理配置問題。1909—1920年丹麥數(shù)學(xué)家、電氣工程師愛爾朗（A.K.Erlang）用概率論方法研究電話通話問題，從而開創(chuàng)了這門應(yīng)用數(shù)學(xué)學(xué)科，并為這門學(xué)科建立許多基本原則。他在熱力學(xué)統(tǒng)計(jì)平衡理論的啟發(fā)下，成功地建立了電話統(tǒng)計(jì)平衡模型，并由此得到一組遞推狀態(tài)方程，從而導(dǎo)出著名的埃爾朗電話損失率公式。他發(fā)表了開創(chuàng)性論文“概率論和電話通訊理論”。排隊(duì)論的起源與發(fā)展20世紀(jì)30年代中期，當(dāng)費(fèi)勒(W.Feller)引進(jìn)了生滅過程時(shí)，排隊(duì)論才被數(shù)學(xué)界承認(rèn)為一門重要的學(xué)科。20世紀(jì)50年代初，堪道爾(D.G.Kendall)對(duì)排隊(duì)論作了系統(tǒng)的研究，他用嵌入馬爾柯夫(A.A.Markov)鏈方法研究排隊(duì)論，使排隊(duì)論得到了進(jìn)一步的發(fā)展。從20世紀(jì)60年代起，主要研究大規(guī)模復(fù)雜排隊(duì)系統(tǒng)的理論分析、數(shù)值分析和近似分析，尤其注重對(duì)業(yè)務(wù)突發(fā)性和帶有各種網(wǎng)絡(luò)控制的排隊(duì)系統(tǒng)的研究。D.G.Kendall排隊(duì)問題的界定要說明一個(gè)排隊(duì)問題必須了解顧客到達(dá)的過程、服務(wù)時(shí)間、排隊(duì)規(guī)則以及服務(wù)系統(tǒng)的結(jié)構(gòu)。到達(dá)過程通常可用兩個(gè)連續(xù)到達(dá)時(shí)刻的間隔或簡(jiǎn)稱為“到達(dá)間隔”來表示。單位時(shí)間內(nèi)平均到達(dá)的個(gè)數(shù)稱為“到達(dá)率”，其值等于平均到達(dá)間隔的倒數(shù)．到達(dá)過程的形式可以是下列任何一種．1、規(guī)則到達(dá)也就是每隔一固定的時(shí)間就有一個(gè)顧客到達(dá)。例如，在自動(dòng)化生產(chǎn)線上，有時(shí)進(jìn)料問題可以是這種形式的到達(dá)過程。2、完全隨機(jī)到達(dá)又稱泊松到達(dá)過程。到達(dá)間隔為指數(shù)分布，各個(gè)間隔為相同分布而互相獨(dú)立的隨機(jī)變量，這種形式具有的特性往往使得數(shù)學(xué)推演極為簡(jiǎn)單，同時(shí)在應(yīng)用方面也頗符合實(shí)際，因此也是最為普遍采用的形式。完全隨機(jī)的假設(shè)是基于在任何時(shí)刻一個(gè)到達(dá)發(fā)生的機(jī)會(huì)完全相同，而兩個(gè)或兩個(gè)以上的到達(dá)同時(shí)發(fā)生的可能性卻極低。3、一般相同而獨(dú)立的到達(dá)或稱更新到達(dá)過程。這類形式比之第二類較具一般性，各個(gè)到達(dá)時(shí)間為相互獨(dú)立、相同分布的隨機(jī)變數(shù)，但是不一定是指數(shù)分布。在正常情形下，機(jī)器的故障發(fā)生常常用這類假設(shè)，連續(xù)兩次故障間隔即為一到達(dá)間隔。4、成批到達(dá)在實(shí)例中卻不乏成批到達(dá)的情形。工廠、商店進(jìn)貨通?？偸且淮蔚竭_(dá)許多件。有時(shí)雖然一次僅有一個(gè)顧客到達(dá)。但是在極短的時(shí)間內(nèi)有多個(gè)到達(dá)時(shí)也可以成批到達(dá)視之。(譬如連環(huán)車禍，一部車子為一個(gè)到達(dá)，車禍可能在短期內(nèi)連續(xù)出現(xiàn))。至于到達(dá)的批量可以為常數(shù)，也可以是隨機(jī)變量。5、非平穩(wěn)到達(dá)在某些情形下，到達(dá)頻率可以因時(shí)而異。最常見的實(shí)例是交通問題和電話通訊問題。上下班時(shí)車輛擁擠，而上班時(shí)間電話使用頻率也較高。6、依態(tài)到達(dá)到達(dá)頻率也可以因服務(wù)系統(tǒng)的狀態(tài)而定．例如：高朋滿座的地方也會(huì)使人不耐久候而轉(zhuǎn)往他家，在這些情況下，到達(dá)率都和隊(duì)列長(zhǎng)度有關(guān)。有時(shí)也因延誤時(shí)間長(zhǎng)短而定，高明滿座的飯店如果座位極多，那么懂得排隊(duì)論概念的人就知道飯店的隊(duì)列雖久但是因?yàn)榉?wù)臺(tái)(座位)多，那么延誤時(shí)間就會(huì)比較短，只須稍候片刻就極可能挨到座位。7、連續(xù)到達(dá)在有些排隊(duì)問題里(如水庫(kù)管理)到達(dá)卻是一個(gè)連續(xù)變數(shù)，有時(shí)為了方便起見我們也可以把離散的假定為連續(xù)到達(dá)以簡(jiǎn)化計(jì)算或推演求解，明顯的例子是大都市車輛在馬路上川流不息，由于數(shù)量龐大有時(shí)可當(dāng)作流體來處理．服務(wù)時(shí)間的類別也有多種，通常是以服務(wù)時(shí)間長(zhǎng)度的分布來表示。平均服務(wù)時(shí)間的倒數(shù)稱作“服務(wù)率”，也可視作服務(wù)臺(tái)在被占用期間，單位時(shí)間內(nèi)可以完成服務(wù)的平均次數(shù)。到達(dá)率與服務(wù)串之間的關(guān)系是度量服務(wù)系統(tǒng)負(fù)荷量的重要指標(biāo)．

1．常數(shù)

2．指數(shù)分布

3．愛爾蘭分布

4．超指數(shù)分布

5．庫(kù)克斯類分布

6．依剩余服務(wù)時(shí)間隨機(jī)變化而界定的分布第一類是指服務(wù)時(shí)間永遠(yuǎn)不變，第三、四類都具有指數(shù)分布的某些共同特性，在計(jì)算上較為簡(jiǎn)單，第五類是一般化的分布但是可以用許多指數(shù)隨機(jī)變數(shù)的隨機(jī)組合來表示，第六類主要用于隊(duì)列上下界限的研究，第五、六兩類都不具有特定的數(shù)學(xué)式子，而代表一群或一類的分布．排隊(duì)系統(tǒng)的特征及其組成排隊(duì)系統(tǒng)的特征即擁擠現(xiàn)象的共性：有請(qǐng)求服務(wù)的人或物，即顧客；有提供服務(wù)的人或物，即服務(wù)員或服務(wù)臺(tái)；具有隨機(jī)性，即各種排隊(duì)系統(tǒng)中，顧客相繼到達(dá)的時(shí)間間隔以及對(duì)每一位顧客服務(wù)的時(shí)間是隨機(jī)的。隨機(jī)性是排隊(duì)系統(tǒng)的一個(gè)重要特征。排隊(duì)系統(tǒng)的基本組成一般的排隊(duì)系統(tǒng)，都可由下圖加以描述。排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)的基本組成部分通常，排隊(duì)系統(tǒng)都有輸入過程、服務(wù)規(guī)則和服務(wù)臺(tái)等3個(gè)組成部分：

輸入過程：這是指要求服務(wù)的顧客是按怎樣的規(guī)律到達(dá)排隊(duì)系統(tǒng)的過程，有時(shí)也把它稱為顧客流．一般可以從3個(gè)方面來描述一個(gè)輸入過程。

顧客總體數(shù)，又稱顧客源、輸入源。這是指顧客的來源。顧客源可以是有限的，也可以是無限的。例如，到醫(yī)院看病的病人可以認(rèn)為是無限的，而某個(gè)工廠因故障待修的機(jī)床則是有限的。顧客到達(dá)方式：這是描述顧客是怎樣來到系統(tǒng)的，他們是單個(gè)到達(dá)，還是成批到達(dá)。病人到醫(yī)院看病是顧客單個(gè)到達(dá)的例子。在庫(kù)存問題中如將生產(chǎn)器材進(jìn)貨或產(chǎn)品入庫(kù)看作是顧客，那么這種顧客則是成批到達(dá)的。

顧客流的概率分布，或稱相繼顧客到達(dá)的時(shí)間間隔的分布：這是求解排隊(duì)系統(tǒng)有關(guān)運(yùn)行指標(biāo)問題時(shí)，首先需要確定的指標(biāo)。這也可以理解為在一定的時(shí)間間隔內(nèi)到達(dá)K個(gè)顧客(K=1、2、)的概率是多大。顧客流的概率分布一般有定長(zhǎng)分布、二項(xiàng)分布、泊松流(最簡(jiǎn)單流)、愛爾朗分布等若干種。2.服務(wù)規(guī)則:這是指服務(wù)臺(tái)從隊(duì)列中選取顧客進(jìn)行服務(wù)的順序。一般可以分為損失制、等待制和混合制等3大類。

(1)損失制:這是指如果顧客到達(dá)排隊(duì)系統(tǒng)時(shí)，所有服務(wù)臺(tái)都已被先來的顧客占用，那么他們就自動(dòng)離開系統(tǒng),永不再來。典型例子是，如電話拔號(hào)后出現(xiàn)忙音，顧客不愿等待而自動(dòng)掛斷電話，如要再打，就需重新拔號(hào)，這種服務(wù)規(guī)則即為損失制。(2)等待制：這是指當(dāng)顧客來到系統(tǒng)時(shí)，所有服務(wù)臺(tái)都不空，顧客加入排隊(duì)行列等待服務(wù)。例如，排隊(duì)等待售票，故障設(shè)備等待維修等。等待制中，服務(wù)臺(tái)在選擇顧客進(jìn)行服務(wù)時(shí)，常有如下四種規(guī)則：

①先到先服務(wù)(FCFS,FirstComeFirstServe)：按顧客到達(dá)的先后順序?qū)︻櫩瓦M(jìn)行服務(wù)，這是最普遍的情形。②后到先服務(wù)(LCFS,LastComeFirstServe)：倉(cāng)庫(kù)中迭放的鋼材，后迭放上去的都先被領(lǐng)走，就屬于這種情況。③隨機(jī)服務(wù)（SIRO，SeverInRandomOrder）：即當(dāng)服務(wù)臺(tái)空閑時(shí)，不按照排隊(duì)序列而隨意指定某個(gè)顧客去接受服務(wù)，如電話交換臺(tái)接通呼叫電話就是一例。

④優(yōu)先權(quán)服務(wù)(PR,Preference)：如老人、兒童先進(jìn)車站；危重病員先就診；遇到重要數(shù)據(jù)需要處理計(jì)算機(jī)立即中斷其他數(shù)據(jù)的處理等，均屬于此種服務(wù)規(guī)則。(3)混合制（Losingsystemandwaitingsystem）：這是等待制與損失制相結(jié)合的一種服務(wù)規(guī)則，一般是指允許排隊(duì)，但又不允許隊(duì)列無限長(zhǎng)下去。具體說來，大致有三種：①隊(duì)長(zhǎng)有限:當(dāng)排隊(duì)等待服務(wù)的顧客人數(shù)超過規(guī)定數(shù)量時(shí)，后來的顧客就自動(dòng)離去，另求服務(wù)，即系統(tǒng)的等待空間是有限的。例如最多只能容納K個(gè)顧客在系統(tǒng)中，當(dāng)新顧客到達(dá)時(shí)，若系統(tǒng)中的顧客數(shù)(又稱為隊(duì)長(zhǎng))小于K，則可進(jìn)入系統(tǒng)排隊(duì)或接受服務(wù)；否則，便離開系統(tǒng)，并不再回來。如水庫(kù)的庫(kù)容是有限的，旅館的床位是有限的。②等待時(shí)間有限:即顧客在系統(tǒng)中的等待時(shí)間不超過某一給定的長(zhǎng)度T，當(dāng)?shù)却龝r(shí)間超過T時(shí)，顧客將自動(dòng)離去，并不再回來。如易損壞的電子元器件的庫(kù)存問題，超過一定存儲(chǔ)時(shí)間的元器件被自動(dòng)認(rèn)為失效。又如顧客到飯館就餐，等了一定時(shí)間后不愿再等而自動(dòng)離去另找飯店用餐。③逗留時(shí)間(等待時(shí)間與服務(wù)時(shí)間之和)有限。例如用高射炮射擊敵機(jī)，當(dāng)敵機(jī)飛越高射炮射擊有效區(qū)域的時(shí)間為t時(shí)，若在這個(gè)時(shí)間內(nèi)未被擊落，也就不可能再被擊落了。

不難注意到，損失制和等待制可看成是混合制的特殊情形，如記s為系統(tǒng)中服務(wù)臺(tái)的個(gè)數(shù)，則當(dāng)K=s時(shí)，混合制即成為損失制；當(dāng)K=∞時(shí)，混合制即成為等待制。服務(wù)機(jī)構(gòu)（服務(wù)臺(tái)）3．服務(wù)臺(tái)情況：服務(wù)臺(tái)可以從以下3方面來描述：

(1)服務(wù)臺(tái)數(shù)量及構(gòu)成形式。從數(shù)量上說，服務(wù)臺(tái)有單服務(wù)臺(tái)和多服務(wù)臺(tái)之分。從構(gòu)成形式上看，服務(wù)臺(tái)有：

①單隊(duì)——單服務(wù)臺(tái)式；②單隊(duì)——多服務(wù)臺(tái)并聯(lián)式；③多隊(duì)——多服務(wù)臺(tái)并聯(lián)式；④單隊(duì)——多服務(wù)臺(tái)串聯(lián)式；⑤單隊(duì)——多服務(wù)臺(tái)并串聯(lián)混合式,以及多隊(duì)——多服務(wù)臺(tái)并串聯(lián)混合式等等。不同的顧客與服務(wù)組成了各式各樣的服務(wù)系統(tǒng)。顧客為了得到某種服務(wù)而到達(dá)系統(tǒng)、若不能立即獲得服務(wù)而又允許排隊(duì)等待，則加入等待隊(duì)伍，待獲得服務(wù)后離開系統(tǒng)。單一服務(wù)臺(tái)單隊(duì)列系統(tǒng)這個(gè)系統(tǒng)僅有一個(gè)服務(wù)臺(tái)，如下圖所示，方塊代表服務(wù)臺(tái)，圓圈代表顧客，箭頭表示顧客流動(dòng)的方向。圖1單隊(duì)單臺(tái)排隊(duì)系統(tǒng)多服務(wù)臺(tái)（并聯(lián)）單隊(duì)列系統(tǒng)數(shù)個(gè)完全相同的服務(wù)臺(tái)(假定為N個(gè))，到達(dá)的顧客可以使用其中任何一個(gè)服務(wù)臺(tái)．如果到達(dá)者只排一個(gè)隊(duì)列(如下圖所示)，那么在服務(wù)臺(tái)全被占滿時(shí)，該服務(wù)系統(tǒng)的排隊(duì)情形就近似于單一服務(wù)臺(tái)系統(tǒng)，如果每個(gè)服務(wù)臺(tái)的服務(wù)率為，隊(duì)列的隨機(jī)行為接近單一服務(wù)臺(tái)以服務(wù)率為n

的隨機(jī)行為。圖2單隊(duì)列——S個(gè)服務(wù)臺(tái)并聯(lián)的排隊(duì)系統(tǒng)多服務(wù)臺(tái)多隊(duì)列系統(tǒng)假設(shè)到達(dá)者被依次安排去不同的服務(wù)臺(tái)，那么服務(wù)系統(tǒng)就有n個(gè)隊(duì)列，每個(gè)隊(duì)列的隨機(jī)行為相同，整個(gè)服務(wù)系統(tǒng)就如同n個(gè)單一服務(wù)臺(tái)系統(tǒng)，如果到達(dá)率為

，則每個(gè)單一服務(wù)臺(tái)的到達(dá)率就是

／n

．若每個(gè)服務(wù)臺(tái)有自己的隊(duì)列，同時(shí)顧客可以自由移換到較短的隊(duì)列上，那么就隊(duì)列長(zhǎng)度的變化而言，這種排隊(duì)方式與單一隊(duì)列沒有什么區(qū)別．圖3S個(gè)隊(duì)列——S個(gè)服務(wù)臺(tái)的并聯(lián)排隊(duì)系統(tǒng)多服務(wù)臺(tái)（串聯(lián)）單隊(duì)列系統(tǒng)圖4多服務(wù)臺(tái)串聯(lián)排隊(duì)系統(tǒng)多服務(wù)臺(tái)混合結(jié)構(gòu)這種結(jié)構(gòu)應(yīng)用于多服務(wù)項(xiàng)目的大型系統(tǒng)。如在大型醫(yī)院的健康體檢項(xiàng)目中，每個(gè)體檢項(xiàng)目有多位醫(yī)生提供服務(wù)，不同項(xiàng)目的服務(wù)需要排隊(duì)等待。圖5多隊(duì)——多服務(wù)臺(tái)混聯(lián)、網(wǎng)絡(luò)系統(tǒng)(2)服務(wù)方式。這是指在某一時(shí)刻接受服務(wù)的顧客數(shù)，它有單個(gè)服務(wù)和成批服務(wù)兩種。如公共汽車一次就可裝載一批乘客就屬于成批服務(wù)。(3)服務(wù)時(shí)間的分布。一般來說，在多數(shù)情況下，對(duì)每一個(gè)顧客的服務(wù)時(shí)間是一隨機(jī)變量，其概率分布有定長(zhǎng)分布、負(fù)指數(shù)分布、K級(jí)愛爾朗分布、一般分布(所有顧客的服務(wù)時(shí)間都是獨(dú)立同分布的)等等。排隊(duì)系統(tǒng)的描述符號(hào)與分類為了區(qū)別各種排隊(duì)系統(tǒng)，根據(jù)輸入過程、排隊(duì)規(guī)則和服務(wù)機(jī)制的變化對(duì)排隊(duì)模型進(jìn)行描述或分類，可給出很多排隊(duì)模型。為了方便對(duì)眾多模型的描述，肯道爾（D．G．Kendall）提出了一種目前在排隊(duì)論中被廣泛采用的“Kendall記號(hào)”，完整的表達(dá)方式通常用到6個(gè)符號(hào)并取如下固定格式：A/B/C/D/E/F

各符號(hào)的意義為：Kendall記號(hào)A：表示顧客相繼到達(dá)間隔時(shí)間分布，常用下列符號(hào)：M：表示到達(dá)過程為泊松過程或負(fù)指數(shù)分布；D：表示定長(zhǎng)輸入；Ek：表示k階愛爾朗分布；G：表示一般相互獨(dú)立的隨機(jī)分布；Geo：表示幾何分布；Kendall記號(hào)B：表示服務(wù)時(shí)間分布，所用符號(hào)與表示顧客到達(dá)間隔時(shí)間分布相同。M：表示服務(wù)過程為泊松過程或負(fù)指數(shù)分布；D：表示定長(zhǎng)分布；Ek

：表示k階愛爾朗分布；G：表示一般相互獨(dú)立的隨機(jī)分布；Geo：表示幾何分布；Kendall記號(hào)C：表示服務(wù)臺(tái)(員)個(gè)數(shù)：“1”則表示單個(gè)服務(wù)臺(tái)，“s”。(s＞1)表示多個(gè)服務(wù)臺(tái)。D：表示系統(tǒng)中顧客容量限額，或稱等待空間容量；如系統(tǒng)有K個(gè)等待位子，則0<K<∞，當(dāng)K=0時(shí)，說明系統(tǒng)不允許等待，即為損失制。K=∞時(shí)為等待制系統(tǒng)，此時(shí)∞般省略不寫。K為有限整數(shù)時(shí)，表示為混合制系統(tǒng)。E：表示顧客源限額，分有限與無限兩種，∞表示顧客源無限，此時(shí)一般∞也可省略不寫。Kendall記號(hào)F：表示服務(wù)規(guī)則，常用下列符號(hào)：

FCFS：表示先到先服務(wù)的排隊(duì)規(guī)則；

LCFS：表示后到先服務(wù)的排隊(duì)規(guī)則；

PR：表示優(yōu)先權(quán)服務(wù)的排隊(duì)規(guī)則。例如：某排隊(duì)問題為M／M／S／∞／∞／FCFS，則表示顧客到達(dá)間隔時(shí)間為負(fù)指數(shù)分布(泊松流)；服務(wù)時(shí)間為負(fù)指數(shù)分布；有s(s＞1)個(gè)服務(wù)臺(tái)；系統(tǒng)等待空間容量無限(等待制)；顧客源無限，采用先到先服務(wù)規(guī)則。Kendall記號(hào)可以將Kendall記號(hào)的含義簡(jiǎn)記為：到達(dá)間隔/服務(wù)時(shí)間/服務(wù)臺(tái)數(shù)/系統(tǒng)容量/顧客源數(shù)/服務(wù)規(guī)則在Kendall記號(hào)中，一般約定如下：如果服務(wù)規(guī)則為先到先服務(wù)，則可以省略最后一項(xiàng)；如果顧客源數(shù)為∞，服務(wù)規(guī)則為先到先服務(wù)則可以省略最后兩項(xiàng)；如果系統(tǒng)容量與顧客源數(shù)均為∞，服務(wù)規(guī)則為先到先服務(wù)則可以省略最后三項(xiàng)；例子1、M／M／1／∞／∞／FCFS表示泊松輸入，服務(wù)時(shí)間服從負(fù)指數(shù)分布、1個(gè)服務(wù)臺(tái)、系統(tǒng)容量無限制、顧客源無限的先到先服務(wù)的排隊(duì)系統(tǒng)。2、G／EK／1／N／∞／FCFS表示顧客到達(dá)的時(shí)間服從一般獨(dú)立分布、服務(wù)時(shí)間服從K階愛爾朗分布、1個(gè)服務(wù)臺(tái)、系統(tǒng)容量為N、顧客源無限的先到先服務(wù)的排隊(duì)系統(tǒng)。習(xí)題試解釋以下排隊(duì)系統(tǒng)的含義。1、M/M/12、M/M/53、M/G/34、M/G/1/m/N5、Geo/Ek/S/m/N/LCFS解答1、M/M/1顧客到達(dá)系統(tǒng)的時(shí)間間隔與服務(wù)時(shí)間均服從負(fù)指數(shù)分布，服務(wù)臺(tái)數(shù)量為1；系統(tǒng)容量和顧客源數(shù)量無限制；服務(wù)規(guī)則為先到先服務(wù)；2、M/M/5顧客到達(dá)系統(tǒng)的時(shí)間間隔與服務(wù)時(shí)間均服從負(fù)指數(shù)分布，服務(wù)臺(tái)數(shù)量為5；系統(tǒng)容量和顧客源數(shù)量無限制；服務(wù)規(guī)則為先到先服務(wù)；3、M/G/3顧客到達(dá)系統(tǒng)的時(shí)間間隔服從負(fù)指數(shù)分布，對(duì)顧客的服務(wù)時(shí)間服從一般分布，服務(wù)臺(tái)數(shù)量為3；系統(tǒng)容量和顧客源數(shù)量無限制；服務(wù)規(guī)則為先到先服務(wù)；4、M/G/1/m/N顧客到達(dá)系統(tǒng)的時(shí)間間隔服從負(fù)指數(shù)分布，對(duì)顧客的服務(wù)時(shí)間服從一般分布，服務(wù)臺(tái)數(shù)量為1；系統(tǒng)容量限制為m；顧客源數(shù)量限制為N；服務(wù)規(guī)則為先到先服務(wù)；5、Geo/Ek/S/m/N/LCFS顧客到達(dá)系統(tǒng)的時(shí)間間隔服從幾何分布，對(duì)顧客的服務(wù)時(shí)間服從K階愛爾朗分布，服務(wù)臺(tái)數(shù)量為S；系統(tǒng)容量限制為m；顧客源數(shù)量限制為N；服務(wù)規(guī)則為后到先服務(wù)；排隊(duì)系統(tǒng)研究的問題1、排隊(duì)系統(tǒng)的數(shù)量指標(biāo)（特征量）研究排隊(duì)系統(tǒng)的目的是通過了解系統(tǒng)運(yùn)行的狀況，對(duì)系統(tǒng)進(jìn)行調(diào)整和控制，使系統(tǒng)處于最優(yōu)運(yùn)行狀態(tài)。因此，首先需要弄清系統(tǒng)的運(yùn)行狀況。描述一個(gè)排隊(duì)系統(tǒng)運(yùn)行狀況的主要數(shù)量指標(biāo)有：特征量平均到達(dá)率：?jiǎn)挝粫r(shí)間內(nèi)到達(dá)系統(tǒng)的顧客數(shù)的平均值，即單位時(shí)間內(nèi)顧客的平均到達(dá)率，記作，而1/表示相鄰兩個(gè)顧客到達(dá)的平均間隔時(shí)間。平均服務(wù)率：?jiǎn)挝粫r(shí)間內(nèi)一個(gè)服務(wù)臺(tái)能夠服務(wù)完的平均顧客數(shù)，記作，而1/表示每個(gè)顧客的平均服務(wù)時(shí)間；恰有n個(gè)顧客的概率：在時(shí)刻t系統(tǒng)中恰有n個(gè)顧客的概率pn(t)，顯然p0(t)為系統(tǒng)空閑概率。特征量隊(duì)長(zhǎng)和隊(duì)列長(zhǎng)

隊(duì)長(zhǎng)是指系統(tǒng)中的平均顧客數(shù)，即排隊(duì)等待的顧客數(shù)與正在接受服務(wù)的顧客數(shù)之和；

等待隊(duì)長(zhǎng)（或隊(duì)列長(zhǎng)）是指系統(tǒng)中正在排隊(duì)等待服務(wù)的平均顧客數(shù)。隊(duì)長(zhǎng)和等待隊(duì)長(zhǎng)一般都是隨機(jī)變量。我們希望能確定它們的分布，或至少能確定它們的平均值。特征量隊(duì)長(zhǎng)的分布是顧客和服務(wù)員都關(guān)心的，特別是對(duì)系統(tǒng)設(shè)計(jì)人員來說，如果能知道隊(duì)長(zhǎng)的分布，就能確定隊(duì)長(zhǎng)超過某個(gè)數(shù)的概率，從而可以改變服務(wù)方式，確定合理的等待空間。特征量等待時(shí)間和逗留時(shí)間從顧客到達(dá)時(shí)刻起到他開始接受服務(wù)止這段時(shí)間稱為等待時(shí)間，是隨機(jī)變量，也是顧客最關(guān)心的指標(biāo)，因?yàn)轭櫩屯ǔＯＭ却龝r(shí)間越短越好。從顧客到達(dá)時(shí)刻起到他接受服務(wù)完成止這段時(shí)間稱為逗留時(shí)間，也是隨機(jī)變量，同樣為顧客非常關(guān)心。對(duì)這兩個(gè)指標(biāo)的研究當(dāng)然是希望能確定它們的分布，或至少能知道顧客的平均等待時(shí)間和平均逗留時(shí)間。從服務(wù)機(jī)構(gòu)的角度來看，還關(guān)心以下指標(biāo)：絕對(duì)通過能力A：?jiǎn)挝粫r(shí)間內(nèi)被服務(wù)完顧客的平均值；系統(tǒng)的相對(duì)通過能力Q：?jiǎn)挝粫r(shí)間內(nèi)被服務(wù)完顧客數(shù)與請(qǐng)求服務(wù)顧客數(shù)之比；忙期是指從顧客到達(dá)空閑著的服務(wù)臺(tái)起，到服務(wù)臺(tái)再次成為空閑止的這段時(shí)間，即服務(wù)機(jī)構(gòu)連續(xù)忙的時(shí)間。這是個(gè)隨機(jī)變量，可以表征服務(wù)臺(tái)的服務(wù)強(qiáng)度。特征量閑期：即服務(wù)臺(tái)連續(xù)保持空閑的時(shí)間。在排隊(duì)系統(tǒng)中，忙期和閑期總是交替出現(xiàn)的；K階繁忙期：對(duì)于有n個(gè)服務(wù)臺(tái)的系統(tǒng)，從系統(tǒng)中開始有K個(gè)顧客在等待服務(wù)時(shí)起一直到有一個(gè)服務(wù)臺(tái)空閑時(shí)為止這段時(shí)間稱為系統(tǒng)的K階繁忙期，零階繁忙期又稱繁忙期。損失率：對(duì)于損失制的排隊(duì)系統(tǒng)中，系統(tǒng)滿員概率稱為系統(tǒng)的損失率。

一些數(shù)量指標(biāo)的常用記號(hào)(1)主要數(shù)量指標(biāo)平均隊(duì)長(zhǎng)L或Ls：即穩(wěn)態(tài)系統(tǒng)中正在接受服務(wù)與排隊(duì)等待服務(wù)的顧客總數(shù)的期望值；平均等待隊(duì)長(zhǎng)Lq：即穩(wěn)態(tài)系統(tǒng)中排隊(duì)等待服務(wù)的顧客數(shù)的期望值；平均逗留時(shí)間W或Ws：即顧客在系統(tǒng)中排隊(duì)等待服務(wù)的時(shí)間與接受服務(wù)的時(shí)間之和的期望值；平均等待時(shí)間Wq：即顧客在系統(tǒng)中等待服務(wù)時(shí)間的期望值。其他常用數(shù)量指標(biāo)：?jiǎn)挝粫r(shí)間內(nèi)達(dá)到系統(tǒng)的平均顧客數(shù)（平均到達(dá)率）；e:單位時(shí)間內(nèi)達(dá)到并進(jìn)入系統(tǒng)的平均顧客數(shù)（有效平均到達(dá)率），在等待制系統(tǒng)中有＝e：?jiǎn)挝粫r(shí)間內(nèi)一個(gè)服務(wù)臺(tái)能夠服務(wù)完的平均顧客數(shù)（平均服務(wù)率）；基本關(guān)系式1L=Lq+S該式揭示了指標(biāo)L與Lq之間的數(shù)量關(guān)系，式中S是平均忙的服務(wù)臺(tái)數(shù)，即正在接受服務(wù)的平均顧客數(shù)。該式的物理意義是：平均逗留隊(duì)長(zhǎng)是平均等待隊(duì)長(zhǎng)與正在接受服務(wù)的平均顧客數(shù)之和。S的計(jì)算方法：因?yàn)榕抨?duì)系統(tǒng)達(dá)到穩(wěn)態(tài)時(shí)，單位時(shí)間內(nèi)到達(dá)并進(jìn)入系統(tǒng)的平均顧客數(shù)e

等于單位時(shí)間內(nèi)接受服務(wù)完畢離開系統(tǒng)的平均顧客數(shù)S*，即有e

＝S*故S=e/基本關(guān)系式2W=Wq+V該式揭示了指標(biāo)W與Wq之間的數(shù)量關(guān)系，式中V是對(duì)每個(gè)顧客的平均服務(wù)時(shí)間。該式的物理意義是：平均逗留時(shí)間是平均等待時(shí)間與對(duì)每個(gè)顧客的平均服務(wù)時(shí)間之和。V的計(jì)算方法：因?yàn)槊總€(gè)服務(wù)臺(tái)的平均服務(wù)率為故V=1/基本關(guān)系式3L=e

W該式揭示了指標(biāo)L與W之間的數(shù)量關(guān)系。該式的物理意義是：平均隊(duì)長(zhǎng)等于單位時(shí)間內(nèi)到達(dá)并進(jìn)入系統(tǒng)的平均顧客數(shù)乘以平均逗留時(shí)間，即等于平均逗留時(shí)間內(nèi)進(jìn)入系統(tǒng)的總的平均顧客數(shù)?；娟P(guān)系式4Lq=e

Wq該式揭示了指標(biāo)Lq與Wq之間的數(shù)量關(guān)系。該式的物理意義是：平均等待隊(duì)長(zhǎng)等于單位時(shí)間內(nèi)到達(dá)并進(jìn)入系統(tǒng)的平均顧客數(shù)乘以平均等待時(shí)間，即等于平均等待時(shí)間內(nèi)進(jìn)入系統(tǒng)的總的平均顧客數(shù)。Little公式公式L=e

W與公式Lq=e

Wq統(tǒng)稱為L(zhǎng)ittle公式。其形式類似于公式“距離＝速度×?xí)r間”，它是排隊(duì)論中的一個(gè)著名公式，適用于存在穩(wěn)態(tài)分布的任何排隊(duì)系統(tǒng)。Little公式揭示了排隊(duì)系統(tǒng)中四個(gè)基本性能指標(biāo)L與W、Lq與Wq之間的數(shù)量關(guān)系。為了求得排隊(duì)系統(tǒng)的各項(xiàng)穩(wěn)態(tài)性能指標(biāo)，必須先計(jì)算出穩(wěn)態(tài)時(shí)系統(tǒng)中有j個(gè)顧客的概率Pj例子例1：一個(gè)步兵排平均有30名戰(zhàn)士，每個(gè)戰(zhàn)士平均在該排服役三年，則L＝30，W＝3，那么

＝30／3＝10，即平均每年有10個(gè)新人加入該排，也平均有10人退役轉(zhuǎn)業(yè)或調(diào)職他處。例2：一個(gè)工人在工作臺(tái)邊操作車床，如果平均有10件工作在工作臺(tái)和車床上，每小時(shí)有4件工作進(jìn)入工作臺(tái)，那么每件工作平均要等W＝L／

＝10／4＝2.5小時(shí)才能完成。排隊(duì)問題中常見的事件流（第2次課）將同類事件一個(gè)（批）個(gè)（批）隨機(jī)地來到服務(wù)窗口要求服務(wù)的序列稱作事件流。如電話局接到的呼喚流、計(jì)算機(jī)出現(xiàn)的故障流、進(jìn)站的汽車流、看病的人流、去某公司應(yīng)聘考試的考生流等均是事件流。顯然，這些事件流均為隨機(jī)變量，由于顧客（用戶）到達(dá)系統(tǒng)的間隔時(shí)間與服務(wù)時(shí)間均為非負(fù)，故它們還是非負(fù)的隨機(jī)變量。常用的有下述幾個(gè)分布：

1、二項(xiàng)分布每次試驗(yàn)成功的概率都是p，失敗的概率都是q=1-p.這樣的n次獨(dú)立重復(fù)試驗(yàn)稱作n重貝努里試驗(yàn)，簡(jiǎn)稱貝努里試驗(yàn)或貝努里概型.用X表示n重貝努里試驗(yàn)中事件A（成功）出現(xiàn)的次數(shù)，則稱隨機(jī)變量X服從參數(shù)為n和p的二項(xiàng)分布，記作X~B(n,p)注:

貝努里概型對(duì)試驗(yàn)結(jié)果沒有等可能的要求，但有下述要求：（1）每次試驗(yàn)條件相同；二項(xiàng)分布描述的是n重貝努里試驗(yàn)中出現(xiàn)“成功”次數(shù)X的概率分布.（2）每次試驗(yàn)只考慮兩個(gè)互逆結(jié)果A或，且P(A)=p

，；（3）各次試驗(yàn)相互獨(dú)立.2、泊松流又稱最簡(jiǎn)單事件流。它具有如下特點(diǎn)：（1）平穩(wěn)性。在任何一段長(zhǎng)度為t的時(shí)間區(qū)間內(nèi)，出現(xiàn)任意數(shù)量事件的概率只與t有關(guān)，而與t所處的位置（或與起始時(shí)刻）無關(guān)。記為平穩(wěn)流的強(qiáng)度。

(2)無后效性（又稱無記憶性或馬氏性）。在互不相交的兩時(shí)間區(qū)間內(nèi)所出現(xiàn)的事件數(shù)是相互獨(dú)立的。如到商店購(gòu)物的顧客，待修的機(jī)器，進(jìn)站的列車等均具有無后效性。

(3）普通性。在同一瞬間，多于一個(gè)事件出現(xiàn)的概率（或同時(shí)到達(dá)系統(tǒng)有兩個(gè)或兩個(gè)以上顧客的概率）可忽略不計(jì)。設(shè)隨機(jī)變量X所有可能取的值為0,1,2,…,且概率分布為：其中>0是常數(shù),則稱X服從參數(shù)為的泊松分布,記作X~P().易見例

某一無線尋呼臺(tái),每分鐘收到尋呼的次數(shù)X服從參數(shù)=3的泊松分布.

求:(1)一分鐘內(nèi)恰好收到3次尋的概率.(2)一分鐘內(nèi)收到2至5次尋呼的概率.解:

(1)P{X=3}=p(3;3)=(33/3!)e-3≈0.2240(2)P{2≤X≤5}=P{X=2}+P{X=3}+P{X=4}+P{X=5}=[(32/2!)+(33/3!)+(34/4!)+(35/5!)]e-3≈0.7169歷史上，泊松分布是作為二項(xiàng)分布的近似，于1837年由法國(guó)數(shù)學(xué)家泊松引入的.二項(xiàng)分布與泊松分布命題對(duì)于二項(xiàng)分布B(n,p),當(dāng)n充分大,p又很小時(shí),則對(duì)任意固定的非負(fù)整數(shù)k,有近似公式負(fù)指數(shù)分布當(dāng)顧客流為泊松流時(shí)，用T表示兩個(gè)相繼顧客到達(dá)系統(tǒng)的時(shí)間間隔，記其分布函數(shù)為由于故有相應(yīng)的分布密度為：它就是負(fù)指數(shù)分布的密度函數(shù)。易知：E(T)=1/D(T)=1/2通常，服務(wù)窗為一顧客服務(wù)所需的時(shí)間的分布函數(shù)與分布密度為其中參數(shù)為單位時(shí)間內(nèi)服務(wù)窗所完成服務(wù)的顧客均值數(shù)，且有4、愛爾蘭分布考察最簡(jiǎn)單的事件流，記各事件到達(dá)系統(tǒng)的時(shí)間間隔序列為，且它們是同負(fù)指數(shù)分布的隨機(jī)變量序列，，如下圖所示。及拉氏變換的性質(zhì)得到再查反拉氏變換表知并且指數(shù)分布若隨機(jī)變量X具有概率密度則稱X

服從參數(shù)為的指數(shù)分布常簡(jiǎn)記為X~E().輸入過程和服務(wù)時(shí)間分布一、輸入過程由前所述，輸入過程是描述各種類型的顧客以怎樣的規(guī)律到達(dá)系統(tǒng)，一般用相繼兩顧客到達(dá)時(shí)間間隔來描述系統(tǒng)輸入特征。主要輸入過程有：

1．定長(zhǎng)輸入。這是指顧客有規(guī)則地等距到達(dá)，每隔時(shí)間到達(dá)一個(gè)顧客。這時(shí)相繼顧客到達(dá)間隔的分布函數(shù)F(t)為：例如，生產(chǎn)自動(dòng)線上產(chǎn)品從傳送帶上進(jìn)入包裝箱就是這種情況．2．泊松(poisson)輸入，又稱最簡(jiǎn)單流。滿足下面3個(gè)條件的輸入稱之為最簡(jiǎn)單流。

(1)平穩(wěn)性。又稱作輸入過程是平穩(wěn)的，指在長(zhǎng)度為t的時(shí)段內(nèi)恰好到達(dá)k個(gè)顧客的概率僅與時(shí)段長(zhǎng)度有關(guān)，而與時(shí)段起點(diǎn)無關(guān)。即對(duì)任意∈(0,∞)，在(,+t]或(0,t)內(nèi)恰好到達(dá)k個(gè)顧客的概率相等：

設(shè)初始條件為,且有(2)無后效性。指在任意幾個(gè)不相交的時(shí)間區(qū)間內(nèi)，各自到達(dá)的顧客數(shù)是相互獨(dú)立的。通俗地說就是以前到達(dá)的顧客情況，對(duì)以后顧客的到來沒有影響，否則就是關(guān)聯(lián)的。(3)單個(gè)性又稱普通性。指在充分小的時(shí)段內(nèi)最多到達(dá)一個(gè)顧客。因?yàn)椴此闪鲗?shí)際應(yīng)用最廣，也最容易處理，因而研究得也較多．可以證明，對(duì)于泊松流，在長(zhǎng)度為t的時(shí)間內(nèi)到達(dá)K個(gè)顧客的概率vk(t)服從泊松分布，即其中參數(shù)>0為一常數(shù)，表示單位時(shí)間內(nèi)到達(dá)顧客的平均數(shù)，又稱為顧客的平均到達(dá)率。對(duì)于泊松流，不難證明其相繼顧客到達(dá)時(shí)間間隔i，i=1,2,…是相互獨(dú)立同分布的，其分布函數(shù)為負(fù)指數(shù)分布：泊松(poisson)輸入在排隊(duì)論中的意義：實(shí)際問題中最常見；數(shù)字處理簡(jiǎn)單；當(dāng)實(shí)際流與泊松流有較大出入時(shí)，經(jīng)過一定的變換，結(jié)果也可以達(dá)到一定的精度。負(fù)指數(shù)分布負(fù)指數(shù)分布是排隊(duì)論中最常用、最重要的一種分布。它既能代表某些達(dá)到間隔的分布，也能代表某些服務(wù)時(shí)間的分布。若隨機(jī)變量t的概率密度為式中常數(shù)

>0，則稱T服從參數(shù)為的負(fù)指數(shù)分布，其數(shù)學(xué)期望E(T)=1/

，方差D(T)=1/

2。E(T)表示顧客相繼到達(dá)時(shí)的平均間隔時(shí)間。以上負(fù)指數(shù)分布是描述輸入情況的，隨機(jī)變量是到達(dá)間隔，若將上式中的換成，則變?yōu)槊枋龇?wù)時(shí)間的參數(shù)為的負(fù)指數(shù)分布。泊松過程與負(fù)指數(shù)分布的關(guān)系：定理：隨機(jī)過程{M(t),t>=0}是強(qiáng)度為的泊松過程的充分必要條件是：顧客相繼到達(dá)的時(shí)間間隔{τk，k=1,2,3…}相互獨(dú)立，且服從參數(shù)為的負(fù)指數(shù)分布。愛爾朗輸入.這是指相繼顧客到達(dá)時(shí)間間隔相互獨(dú)立，具有相同的分布，其分布密度為

其中k為非負(fù)整數(shù)?？梢宰C明，在參數(shù)為的泊松輸人中，對(duì)任意的j與k,設(shè)第j與第j+k個(gè)顧客之間的到達(dá)間隔為：則隨機(jī)變量Tk的分布必遵從參數(shù)為的愛爾朗分布，其分布密度為：例某排隊(duì)系統(tǒng)有并聯(lián)的k個(gè)服務(wù)臺(tái)，顧客流為泊松流，規(guī)定第i,K+i,2K+i…個(gè)顧客排入第i號(hào)臺(tái)(i=1,2,…,K)，則第K臺(tái)所獲得的顧客流，即為愛爾朗輸入流，其他各臺(tái)，從它的第一個(gè)顧客到達(dá)以后開始所獲得的流也為愛爾朗輸入流。此外，愛爾朗分布中，當(dāng)K＝1時(shí)將化為負(fù)指數(shù)分布。4.一般獨(dú)立輸入，即相繼顧客到達(dá)時(shí)間間隔相互獨(dú)立、同分布，分布函數(shù)F(t)是任意分布，因此，上面所述的所有輸入都是一般獨(dú)立分布的特例。5.成批到達(dá)的輸入。這時(shí)排隊(duì)系統(tǒng)每次到達(dá)的顧客不一定是一個(gè)，而可能是一批，每批顧客的數(shù)目n是一個(gè)隨機(jī)變量。其分布為：到達(dá)時(shí)間間隔可能是上述幾類輸入中的一種。服務(wù)時(shí)間分布1．定長(zhǎng)分布。每一個(gè)顧客的服務(wù)時(shí)間都是常數(shù)，此時(shí)服務(wù)時(shí)間t的分布函數(shù)為：

2．負(fù)指數(shù)分布。即各個(gè)顧客的服務(wù)時(shí)間相互獨(dú)立，具有相同的負(fù)指數(shù)分布：

其中>0為一常數(shù)，服務(wù)時(shí)間t的數(shù)學(xué)期望稱為平均服務(wù)時(shí)間。服務(wù)時(shí)間分布3.愛爾朗分布.即每個(gè)顧客的服務(wù)時(shí)間相互獨(dú)立，具有相同的愛爾朗分布。其密度函數(shù)為

其中>0為一常數(shù)，此種的平均服務(wù)時(shí)間為：

K=1時(shí)愛爾朗分布化歸為負(fù)指數(shù)分布當(dāng)K→∞時(shí)，得到長(zhǎng)度為1/的定長(zhǎng)服務(wù)。4、一般服務(wù)分布。所有顧客的服務(wù)時(shí)間都是相互獨(dú)立具有相同分布的隨機(jī)變量，其分布函數(shù)記B(X)，前面所述的各種服務(wù)分布都是一般服務(wù)分布的特例。5、多個(gè)服務(wù)臺(tái)的服務(wù)分布?？梢约俣ǜ鱾€(gè)服務(wù)臺(tái)的服務(wù)分布參數(shù)不同或分布類型不同6、服務(wù)時(shí)間依賴于隊(duì)長(zhǎng)的情況。指服務(wù)員排隊(duì)的人愈多，服務(wù)的速度也就愈快。服務(wù)時(shí)間分布復(fù)習(xí)1、排隊(duì)系統(tǒng)的組成2、排隊(duì)系統(tǒng)的描述符號(hào)3、排隊(duì)系統(tǒng)的特征量排隊(duì)系統(tǒng)的組成一般的排隊(duì)系統(tǒng)，都可由下圖加以描述。排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)的組成排隊(duì)系統(tǒng)由輸入過程、服務(wù)規(guī)則和服務(wù)臺(tái)3個(gè)組成部分：

輸入過程：這是指要求服務(wù)的顧客是按怎樣的規(guī)律到達(dá)排隊(duì)系統(tǒng)的過程，有時(shí)也把它稱為顧客流．一般可以從3個(gè)方面來描述一個(gè)輸入過程。

顧客總體數(shù)，又稱顧客源、輸入源。這是指顧客的來源。顧客源可以是有限的，也可以是無限的。顧客到達(dá)方式：這是描述顧客是怎樣來到系統(tǒng)的，他們是單個(gè)到達(dá)，還是成批到達(dá)。顧客流的概率分布，或稱相繼顧客到達(dá)的時(shí)間間隔的分布：這是求解排隊(duì)系統(tǒng)有關(guān)運(yùn)行指標(biāo)問題時(shí)，首先需要確定的指標(biāo)。這也可以理解為在一定的時(shí)間間隔內(nèi)到達(dá)K個(gè)顧客(K=1、2、)的概率是多大。顧客流的概率分布一般有定長(zhǎng)分布、二項(xiàng)分布、泊松流(最簡(jiǎn)單流)、愛爾朗分布等若干種。2.服務(wù)規(guī)則:這是指服務(wù)臺(tái)從隊(duì)列中選取顧客進(jìn)行服務(wù)的順序。一般可以分為損失制、等待制和混合制等3大類。

(1)損失制:這是指如果顧客到達(dá)排隊(duì)系統(tǒng)時(shí)，所有服務(wù)臺(tái)都已被先來的顧客占用，那么他們就自動(dòng)離開系統(tǒng),永不再來。(2)等待制：這是指當(dāng)顧客來到系統(tǒng)時(shí)，所有服務(wù)臺(tái)都不空，顧客加入排隊(duì)行列等待服務(wù)。等待制中，服務(wù)臺(tái)在選擇顧客進(jìn)行服務(wù)時(shí)，常有如下四種規(guī)則：

①先到先服務(wù)(FCFS,FirstComeFirstServe)：按顧客到達(dá)的先后順序?qū)︻櫩瓦M(jìn)行服務(wù)，這是最普遍的情形。②后到先服務(wù)(LCFS,LastComeFirstServe)：倉(cāng)庫(kù)中迭放的鋼材，后迭放上去的都先被領(lǐng)走，就屬于這種情況。③隨機(jī)服務(wù)（SIRO，SeverInRandomOrder）：即當(dāng)服務(wù)臺(tái)空閑時(shí)，不按照排隊(duì)序列而隨意指定某個(gè)顧客去接受服務(wù)，如電話交換臺(tái)接通呼叫電話就是一例。

④優(yōu)先權(quán)服務(wù)(PR,Preference)：如老人、兒童先進(jìn)車站；危重病員先就診；遇到重要數(shù)據(jù)需要處理計(jì)算機(jī)立即中斷其他數(shù)據(jù)的處理等，均屬于此種服務(wù)規(guī)則。(3)混合制（Losingsystemandwaitingsystem）：這是等待制與損失制相結(jié)合的一種服務(wù)規(guī)則，一般是指允許排隊(duì)，但又不允許隊(duì)列無限長(zhǎng)下去。具體說來，大致有三種：①隊(duì)長(zhǎng)有限:當(dāng)排隊(duì)等待服務(wù)的顧客人數(shù)超過規(guī)定數(shù)量時(shí)，后來的顧客就自動(dòng)離去，另求服務(wù)，即系統(tǒng)的等待空間是有限的。例如最多只能容納K個(gè)顧客在系統(tǒng)中，當(dāng)新顧客到達(dá)時(shí)，若系統(tǒng)中的顧客數(shù)(又稱為隊(duì)長(zhǎng))小于K，則可進(jìn)入系統(tǒng)排隊(duì)或接受服務(wù)；否則，便離開系統(tǒng)，并不再回來。如水庫(kù)的庫(kù)容是有限的，旅館的床位是有限的。②等待時(shí)間有限:即顧客在系統(tǒng)中的等待時(shí)間不超過某一給定的長(zhǎng)度T，當(dāng)?shù)却龝r(shí)間超過T時(shí)，顧客將自動(dòng)離去，并不再回來。③逗留時(shí)間(等待時(shí)間與服務(wù)時(shí)間之和)有限。

損失制和等待制可看成是混合制的特殊情形，如記s為系統(tǒng)中服務(wù)臺(tái)的個(gè)數(shù)，則當(dāng)K=s時(shí)，混合制即成為損失制；當(dāng)K=∞時(shí)，混合制即成為等待制。服務(wù)機(jī)構(gòu)（服務(wù)臺(tái)）3．服務(wù)臺(tái)情況：服務(wù)臺(tái)可以從以下3方面來描述：

(1)服務(wù)臺(tái)數(shù)量及構(gòu)成形式。從數(shù)量上說，服務(wù)臺(tái)有單服務(wù)臺(tái)和多服務(wù)臺(tái)之分。從構(gòu)成形式上看，服務(wù)臺(tái)有：

①單隊(duì)——單服務(wù)臺(tái)式；②單隊(duì)——多服務(wù)臺(tái)并聯(lián)式；③多隊(duì)——多服務(wù)臺(tái)并聯(lián)式；④單隊(duì)——多服務(wù)臺(tái)串聯(lián)式；⑤單隊(duì)——多服務(wù)臺(tái)并串聯(lián)混合式,以及多隊(duì)——多服務(wù)臺(tái)并串聯(lián)混合式等等。單一服務(wù)臺(tái)單隊(duì)列系統(tǒng)這個(gè)系統(tǒng)僅有一個(gè)服務(wù)臺(tái)，如下圖所示，方塊代表服務(wù)臺(tái)，圓圈代表顧客，箭頭表示顧客流動(dòng)的方向。圖1單隊(duì)單臺(tái)排隊(duì)系統(tǒng)多服務(wù)臺(tái)（并聯(lián)）單隊(duì)列系統(tǒng)數(shù)個(gè)完全相同的服務(wù)臺(tái)(假定為N個(gè))，到達(dá)的顧客可以使用其中任何一個(gè)服務(wù)臺(tái)．如果到達(dá)者只排一個(gè)隊(duì)列(如下圖所示)，那么在服務(wù)臺(tái)全被占滿時(shí)，該服務(wù)系統(tǒng)的排隊(duì)情形就近似于單一服務(wù)臺(tái)系統(tǒng)，如果每個(gè)服務(wù)臺(tái)的服務(wù)率為，隊(duì)列的隨機(jī)行為接近單一服務(wù)臺(tái)以服務(wù)率為n

的隨機(jī)行為。圖2單隊(duì)列——S個(gè)服務(wù)臺(tái)并聯(lián)的排隊(duì)系統(tǒng)多服務(wù)臺(tái)多隊(duì)列系統(tǒng)假設(shè)到達(dá)者被依次安排去不同的服務(wù)臺(tái)，那么服務(wù)系統(tǒng)就有n個(gè)隊(duì)列，每個(gè)隊(duì)列的隨機(jī)行為相同，整個(gè)服務(wù)系統(tǒng)就如同n個(gè)單一服務(wù)臺(tái)系統(tǒng)，如果到達(dá)率為

，則每個(gè)單一服務(wù)臺(tái)的到達(dá)率就是

／n

．若每個(gè)服務(wù)臺(tái)有自己的隊(duì)列，同時(shí)顧客可以自由移換到較短的隊(duì)列上，那么就隊(duì)列長(zhǎng)度的變化而言，這種排隊(duì)方式與單一隊(duì)列沒有什么區(qū)別．圖3S個(gè)隊(duì)列——S個(gè)服務(wù)臺(tái)的并聯(lián)排隊(duì)系統(tǒng)多服務(wù)臺(tái)（串聯(lián)）單隊(duì)列系統(tǒng)圖4多服務(wù)臺(tái)串聯(lián)排隊(duì)系統(tǒng)多服務(wù)臺(tái)混合結(jié)構(gòu)這種結(jié)構(gòu)應(yīng)用于多服務(wù)項(xiàng)目的大型系統(tǒng)。如在大型醫(yī)院的健康體檢項(xiàng)目中，每個(gè)體檢項(xiàng)目有多位醫(yī)生提供服務(wù)，不同項(xiàng)目的服務(wù)需要排隊(duì)等待。圖5多隊(duì)——多服務(wù)臺(tái)混聯(lián)、網(wǎng)絡(luò)系統(tǒng)(2)服務(wù)方式。這是指在某一時(shí)刻接受服務(wù)的顧客數(shù)，它有單個(gè)服務(wù)和成批服務(wù)兩種。如公共汽車一次就可裝載一批乘客就屬于成批服務(wù)。(3)服務(wù)時(shí)間的分布。一般來說，在多數(shù)情況下，對(duì)每一個(gè)顧客的服務(wù)時(shí)間是一隨機(jī)變量，其概率分布有定長(zhǎng)分布、負(fù)指數(shù)分布、K級(jí)愛爾朗分布、一般分布(所有顧客的服務(wù)時(shí)間都是獨(dú)立同分布的)等等。排隊(duì)系統(tǒng)的描述符號(hào)為了區(qū)別各種排隊(duì)系統(tǒng)，根據(jù)輸入過程、排隊(duì)規(guī)則和服務(wù)機(jī)制的變化對(duì)排隊(duì)模型進(jìn)行描述或分類，可給出很多排隊(duì)模型。為了方便對(duì)眾多模型的描述，肯道爾（D．G．Kendall）提出了一種目前在排隊(duì)論中被廣泛采用的“Kendall記號(hào)”，完整的表達(dá)方式通常用到6個(gè)符號(hào)并取如下固定格式：A/B/C/D/E/F

各符號(hào)的意義為：Kendall記號(hào)A：表示顧客相繼到達(dá)間隔時(shí)間分布，常用下列符號(hào)：M：表示到達(dá)過程為泊松過程或負(fù)指數(shù)分布；D：表示定長(zhǎng)輸入；Ek：表示k階愛爾朗分布；G：表示一般相互獨(dú)立的隨機(jī)分布；Geo：表示幾何分布；Kendall記號(hào)B：表示服務(wù)時(shí)間分布，所用符號(hào)與表示顧客到達(dá)間隔時(shí)間分布相同。M：表示服務(wù)過程為泊松過程或負(fù)指數(shù)分布；D：表示定長(zhǎng)分布；Ek

：表示k階愛爾朗分布；G：表示一般相互獨(dú)立的隨機(jī)分布；Geo：表示幾何分布；Kendall記號(hào)C：表示服務(wù)臺(tái)(員)個(gè)數(shù)：“1”則表示單個(gè)服務(wù)臺(tái)，“s”。(s＞1)表示多個(gè)服務(wù)臺(tái)。D：表示系統(tǒng)中顧客容量限額，或稱等待空間容量；如系統(tǒng)有K個(gè)等待位子，則0<K<∞，當(dāng)K=0時(shí)，說明系統(tǒng)不允許等待，即為損失制。K=∞時(shí)為等待制系統(tǒng)，此時(shí)∞般省略不寫。K為有限整數(shù)時(shí)，表示為混合制系統(tǒng)。E：表示顧客源限額，分有限與無限兩種，∞表示顧客源無限，此時(shí)一般∞也可省略不寫。Kendall記號(hào)F：表示服務(wù)規(guī)則，常用下列符號(hào)：

FCFS：表示先到先服務(wù)的排隊(duì)規(guī)則；

LCFS：表示后到先服務(wù)的排隊(duì)規(guī)則；

PR：表示優(yōu)先權(quán)服務(wù)的排隊(duì)規(guī)則。例如：某排隊(duì)問題為M／M／S／∞／∞／FCFS，則表示顧客到達(dá)間隔時(shí)間為負(fù)指數(shù)分布(泊松流)；服務(wù)時(shí)間為負(fù)指數(shù)分布；有s(s＞1)個(gè)服務(wù)臺(tái)；系統(tǒng)等待空間容量無限(等待制)；顧客源無限，采用先到先服務(wù)規(guī)則。Kendall記號(hào)可以將Kendall記號(hào)的含義簡(jiǎn)記為：到達(dá)間隔/服務(wù)時(shí)間/服務(wù)臺(tái)數(shù)/系統(tǒng)容量/顧客源數(shù)/服務(wù)規(guī)則在Kendall記號(hào)中，一般約定如下：如果服務(wù)規(guī)則為先到先服務(wù)，則可以省略最后一項(xiàng)；如果顧客源數(shù)為∞，服務(wù)規(guī)則為先到先服務(wù)則可以省略最后兩項(xiàng)；如果系統(tǒng)容量與顧客源數(shù)均為∞，服務(wù)規(guī)則為先到先服務(wù)則可以省略最后三項(xiàng)；例子1、M／M／1／∞／∞／FCFS表示泊松輸入，服務(wù)時(shí)間服從負(fù)指數(shù)分布、1個(gè)服務(wù)臺(tái)、系統(tǒng)容量無限制、顧客源無限的先到先服務(wù)的排隊(duì)系統(tǒng)。2、G／EK／1／N／∞／FCFS表示顧客到達(dá)的時(shí)間服從一般獨(dú)立分布、服務(wù)時(shí)間服從K階愛爾朗分布、1個(gè)服務(wù)臺(tái)、系統(tǒng)容量為N、顧客源無限的先到先服務(wù)的排隊(duì)系統(tǒng)。排隊(duì)系統(tǒng)的特征量(1)主要數(shù)量指標(biāo)平均隊(duì)長(zhǎng)L或Ls：即穩(wěn)態(tài)系統(tǒng)中正在接受服務(wù)與排隊(duì)等待服務(wù)的顧客總數(shù)的期望值；平均等待隊(duì)長(zhǎng)Lq：即穩(wěn)態(tài)系統(tǒng)中排隊(duì)等待服務(wù)的顧客數(shù)的期望值；平均逗留時(shí)間W或Ws：即顧客在系統(tǒng)中排隊(duì)等待服務(wù)的時(shí)間與接受服務(wù)的時(shí)間之和的期望值；平均等待時(shí)間Wq：即顧客在系統(tǒng)中等待服務(wù)時(shí)間的期望值。其他常用數(shù)量指標(biāo)：?jiǎn)挝粫r(shí)間內(nèi)達(dá)到系統(tǒng)的平均顧客數(shù)（平均到達(dá)率）；e:單位時(shí)間內(nèi)達(dá)到并進(jìn)入系統(tǒng)的平均顧客數(shù)（有效平均到達(dá)率），在等待制系統(tǒng)中有＝e：?jiǎn)挝粫r(shí)間內(nèi)一個(gè)服務(wù)臺(tái)能夠服務(wù)完的平均顧客數(shù)（平均服務(wù)率）；基本關(guān)系式1L=Lq+S該式揭示了指標(biāo)L與Lq之間的數(shù)量關(guān)系，式中S是平均忙的服務(wù)臺(tái)數(shù)，即正在接受服務(wù)的平均顧客數(shù)。該式的物理意義是：平均逗留隊(duì)長(zhǎng)是平均等待隊(duì)長(zhǎng)與正在接受服務(wù)的平均顧客數(shù)之和。S的計(jì)算方法：因?yàn)榕抨?duì)系統(tǒng)達(dá)到穩(wěn)態(tài)時(shí)，單位時(shí)間內(nèi)到達(dá)并進(jìn)入系統(tǒng)的平均顧客數(shù)e

等于單位時(shí)間內(nèi)接受服務(wù)完畢離開系統(tǒng)的平均顧客數(shù)S*，即有e

＝S*故S=e/基本關(guān)系式2W=Wq+V該式揭示了指標(biāo)W與Wq之間的數(shù)量關(guān)系，式中V是對(duì)每個(gè)顧客的平均服務(wù)時(shí)間。該式的物理意義是：平均逗留時(shí)間是平均等待時(shí)間與對(duì)每個(gè)顧客的平均服務(wù)時(shí)間之和。V的計(jì)算方法：因?yàn)槊總€(gè)服務(wù)臺(tái)的平均服務(wù)率為故V=1/基本關(guān)系式3L=e

W該式揭示了指標(biāo)L與W之間的數(shù)量關(guān)系。該式的物理意義是：平均隊(duì)長(zhǎng)等于單位時(shí)間內(nèi)到達(dá)并進(jìn)入系統(tǒng)的平均顧客數(shù)乘以平均逗留時(shí)間，即等于平均逗留時(shí)間內(nèi)進(jìn)入系統(tǒng)的總的平均顧客數(shù)?；娟P(guān)系式4Lq=e

Wq該式揭示了指標(biāo)Lq與Wq之間的數(shù)量關(guān)系。該式的物理意義是：平均等待隊(duì)長(zhǎng)等于單位時(shí)間內(nèi)到達(dá)并進(jìn)入系統(tǒng)的平均顧客數(shù)乘以平均等待時(shí)間，即等于平均等待時(shí)間內(nèi)進(jìn)入系統(tǒng)的總的平均顧客數(shù)。Little公式公式L=e

W與公式Lq=e

Wq統(tǒng)稱為L(zhǎng)ittle公式。其形式類似于公式“距離＝速度×?xí)r間”，它是排隊(duì)論中的一個(gè)著名公式，適用于存在穩(wěn)態(tài)分布的任何排隊(duì)系統(tǒng)。Little公式揭示了排隊(duì)系統(tǒng)中四個(gè)基本性能指標(biāo)L與W、Lq與Wq之間的數(shù)量關(guān)系。為了求得排隊(duì)系統(tǒng)的各項(xiàng)穩(wěn)態(tài)性能指標(biāo)，必須先計(jì)算出穩(wěn)態(tài)時(shí)系統(tǒng)中有j個(gè)顧客的概率PjM/M/1/N/∞/FCFS1、系統(tǒng)意義顧客按照泊松流輸入，平均到達(dá)率為；服務(wù)時(shí)間服從負(fù)指數(shù)分布，平均服務(wù)率為；1個(gè)服務(wù)臺(tái)；系統(tǒng)容量為N，顧客源無限，排隊(duì)規(guī)則為先到先服務(wù)的混合制排隊(duì)系統(tǒng)；當(dāng)顧客來到系統(tǒng)時(shí)，若系統(tǒng)中的顧客已經(jīng)等于N，則離去M/M/1/N/∞/FCFS2、狀態(tài)轉(zhuǎn)移速度圖1）系統(tǒng)狀態(tài)：系統(tǒng)中的顧客數(shù)2）狀態(tài)轉(zhuǎn)移速度圖用圓圈表示狀態(tài)符號(hào)，箭頭表示從一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)移。0N-112N-2λλλλμμμμN(yùn)M/M/1/N/∞/FCFS3）寫出狀態(tài)轉(zhuǎn)移速度矩陣，進(jìn)而寫出系統(tǒng)穩(wěn)態(tài)條件下的狀態(tài)概率平衡方程（簡(jiǎn)稱狀態(tài)概率方程）注意：狀態(tài)轉(zhuǎn)移速度矩陣的特點(diǎn)是每一行元素之和等于0M/M/1/N/∞/FCFS狀態(tài)概率方程PA=0其中：P=(P0,P1,P2,P3,……Pn)M/M/1/N/∞/FCFS把狀態(tài)概率方程打開，寫出狀態(tài)概率方程組即可求出基本概率指標(biāo)。1、基本概率指標(biāo)PA=0第一項(xiàng)：－λP0＋μP1＝0P1＝(λ/μ)P0第二項(xiàng)：λP0－（μ＋λ）P1＋μP2＝0P2＝(λ/μ)2P0M/M/1/N/∞/FCFS依此類推：Pn＝(λ/μ)nP01≤n≤N如何求P0呢？代入（P0+P1+…+Pn)=1故有（P0＋(λ/μ)P0+…+(λ/μ)nP0）＝1P0（1＋(λ/μ)+…+(λ/μ)n）＝1于是：P0＝1/(1＋(λ/μ)+…+(λ/μ)n)當(dāng)λ＝μ時(shí)P0＝1/(N+1)當(dāng)λ≠μ時(shí)P0＝（1－λ/μ）/(1－(λ/μ)N+1)M/M/1/N/∞/FCFSPn＝(λ/μ)np0故當(dāng)λ＝μ時(shí)Pn＝1/(N+1)當(dāng)λ≠μ時(shí)Pn＝（1－λ/μ）/(1－(λ/μ)N+1)(λ/μ)nM/M/1/N/∞/FCFS得到系統(tǒng)狀態(tài)概率方程組的第二種方法：當(dāng)系統(tǒng)處于穩(wěn)態(tài)時(shí)，對(duì)每個(gè)狀態(tài)來說，轉(zhuǎn)入率應(yīng)等于轉(zhuǎn)出率。根據(jù)這個(gè)結(jié)果即可獲得系統(tǒng)穩(wěn)態(tài)條件下的狀態(tài)概率方程，進(jìn)一步即可計(jì)算穩(wěn)態(tài)系統(tǒng)的各項(xiàng)運(yùn)行數(shù)量指標(biāo)。當(dāng)系統(tǒng)狀態(tài)為0時(shí)，有λP0＝μP1故P1＝(λ/μ)P0當(dāng)系統(tǒng)狀態(tài)n≥1時(shí)，有λPn-1+μPn+1=(λ+μ)Pn當(dāng)系統(tǒng)狀態(tài)n=N時(shí)，有λPn-1=μPn于是得到簡(jiǎn)化形式的穩(wěn)態(tài)概率方程組：Pn＝(λ/μ)np01≤n≤N代入（P0+P1+…+Pn)=10N-112N-2λλλλμμμμN(yùn)故有（P0＋(λ/μ)P0+…+(λ/μ)nP0）＝1P0（1＋(λ/μ)+…+(λ/μ)n）＝1于是：P0＝1/(1＋(λ/μ)+…+(λ/μ)n)當(dāng)λ＝μ時(shí)P0＝1/(N+1)當(dāng)λ≠μ時(shí)P0＝（1－λ/μ）/(1－(λ/μ)N+1)1）P0為系統(tǒng)空閑的概率，因此系統(tǒng)不空的概率即服務(wù)臺(tái)忙的概率（系統(tǒng)滿的概率或系統(tǒng)損失的概率）P忙＝1－P02）平均隊(duì)長(zhǎng)（系統(tǒng)中顧客數(shù)的期望值）Ls和平均隊(duì)列長(zhǎng)Lq(系統(tǒng)中排隊(duì)等待服務(wù)的顧客數(shù)的期望值)∞∞

Ls=∑nPnLq=∑(n-1)Pn

n=0n=13)有效到達(dá)率e

（有效離去率μe

）：平均每單位時(shí)間進(jìn)入（離去）系統(tǒng)的顧客數(shù)。在穩(wěn)態(tài)情況下兩者相等，因此有：e

=μe=∑nPn=∑μnPn4）平均逗留時(shí)間Ws和平均等待時(shí)間Wq:由Little公式可知：Ws＝Ls

/e

Wq＝

Lq

/e

由平均服務(wù)率μ的定義可以得到每個(gè)顧客的平均服務(wù)時(shí)間為1/μ，因此有：Ws＝Wq+

1/μ5）其他公式由Little公式還可以得到：①平均隊(duì)長(zhǎng)和平均隊(duì)列長(zhǎng)的另外一組計(jì)算公式Ls＝Wse

Lq＝

Wqe②有效到達(dá)率的另外一組計(jì)算公式e

＝λ（1－PN）＋0PN即系統(tǒng)不滿時(shí)，顧客以λ的速度進(jìn)入系統(tǒng)e

＝μ（1－P0）＋0P0即系統(tǒng)不空時(shí)，顧客以μ的速度離開系統(tǒng)③系統(tǒng)平均每單位時(shí)間損失的顧客數(shù)損＝λ－e

＝λPN④閑期和忙期從服務(wù)臺(tái)閑到下一個(gè)顧客來到的平均間隔時(shí)間是1/λ，因此平均閑期長(zhǎng)為：T閑＝1/λ由于服務(wù)臺(tái)忙閑間隔出現(xiàn)，故有：T忙/T閑＝P忙/P閑＝(1-P0)/P0，于是T忙＝T閑×

P忙/P閑＝T閑×

(1-P0)/P0＝1/λ×

(1-P0)/P0例子某汽車加油站有一臺(tái)油泵為汽車加油，站內(nèi)可容納4輛汽車，當(dāng)站內(nèi)停滿車時(shí)，后來的汽車只能到別處加油，若需加油的汽車按照泊松流到達(dá)，平均每小時(shí)4輛。每輛車加油所需時(shí)間服從負(fù)指數(shù)分布，平均每輛需12分鐘，試求系統(tǒng)有關(guān)運(yùn)行指標(biāo)。1、分析為什么是M/M/1/4/∞/FCFS排隊(duì)系統(tǒng)。2、選用適當(dāng)公式計(jì)算有關(guān)指標(biāo)。λ＝4（輛/小時(shí)）μ=1/(12/60)=5（輛/小時(shí)），于是①P0＝（1－λ/μ）/(1－(λ/μ)N+1)P0＝（1－4/5)/(1-(4/5)4+1)=0.2/0.67232P0=0.2975由于Pn＝(λ/μ)np0故P1≈0.8*0.2975=0.2380P2≈0.82*0.2975=0.1904P3≈0.83*0.2975=0.1523P4≈0.84*0.2975=0.1218②平均隊(duì)長(zhǎng)Ls

4

Ls=∑nPn=P1+2P2+3P3+4P4

n=0

=0.2380+2*0.1904+3*0.1523+4*0.1218

=1.5629③有效到達(dá)率e

=λ（1－PN）＋0PN

e

=4*(1-P4）=4*(1-0.1218)=3.5128④逗留時(shí)間Ws

Ws＝Ls

/e

=1.5629/3.5128=0.4450⑤等待時(shí)間WqWq＝Ws-1/μ＝0.4450－0.2=0.2450⑥平均隊(duì)列長(zhǎng)LqLq＝

Wqe=0.2450*3.5128=0.86⑦系統(tǒng)平均每單位時(shí)間損失的顧客數(shù)損損＝λ－e

＝λPN=4*0.1218=0.4872⑧忙期T忙＝T閑×

P忙/P閑＝T閑×

(1-P0)/P0＝1/e×

(1-P0)/P0=1/3.5128*(1-0.2975)/0.2975=0.8注意M/M/1/N/∞/FCFS當(dāng)N趨于∞時(shí)為等待制系統(tǒng)；當(dāng)N趨于0時(shí)為損失制系統(tǒng)；思考題試畫出M/M/1客源無限的損失制排隊(duì)系統(tǒng)的狀態(tài)轉(zhuǎn)移速度圖，寫出相應(yīng)的狀態(tài)轉(zhuǎn)移速度矩陣及相應(yīng)的基本數(shù)量指標(biāo)表達(dá)式。1）M/M/1損失制排隊(duì)系統(tǒng)狀態(tài)轉(zhuǎn)移速度圖和狀態(tài)轉(zhuǎn)移速度矩陣01λμ2）系統(tǒng)在穩(wěn)態(tài)時(shí)的狀態(tài)概率方程：PA=0即（P0，P1）＝03）M/M/1損失制系統(tǒng)特征量計(jì)算公式P0=μ/(λ+μ)P1=λ/(λ+μ)P損=P忙=P1=λ/(λ+μ)例子某汽車加油站有一臺(tái)油泵為汽車加油，站內(nèi)可容納1輛汽車，當(dāng)站內(nèi)停滿車時(shí)，后來的汽車只能到別處加油，若需加油的汽車按照泊松流到達(dá)，平均每小時(shí)4輛。每輛車加油所需時(shí)間服從負(fù)指數(shù)分布，平均每輛需12分鐘，試求系統(tǒng)有關(guān)運(yùn)行指標(biāo)。1、該系統(tǒng)是M/M/1/1/∞/FCFS損失制排隊(duì)系統(tǒng)。2、選用適當(dāng)公式計(jì)算有關(guān)指標(biāo)。λ＝4（輛/小時(shí)）μ=1/(12/60)=5（輛/小時(shí)），于是P0=μ/(λ+μ)＝0.56P1=λ/(λ+μ)＝0.44P損=P忙=P1=λ/(λ+μ)＝0.44每小時(shí)接待的顧客數(shù)為：e

=λP0+0P1=λμ/(λ+μ)＝2.2（輛/小時(shí)）每小時(shí)損失的顧客數(shù)為：損＝λ－e=4－2.2＝1.8（輛/小時(shí)）M/M/1等待制排隊(duì)系統(tǒng)1、系統(tǒng)的意義顧客按泊松流輸入，平均到達(dá)率為λ，服務(wù)時(shí)間服從負(fù)指數(shù)分布、平均服務(wù)率為μ，1個(gè)服務(wù)臺(tái)，系統(tǒng)容量和顧客源為無限。當(dāng)顧客來到系統(tǒng)時(shí)，若服務(wù)臺(tái)忙，則顧客排隊(duì)等待服務(wù)，排隊(duì)規(guī)則為先到先服務(wù)的排隊(duì)系統(tǒng)。2、系統(tǒng)的狀態(tài)轉(zhuǎn)移速度圖0n12n-1λλλλμμμμλμ3、狀態(tài)轉(zhuǎn)移概率矩陣：4、狀態(tài)概率方程PA=0打開即得計(jì)算個(gè)概率的公式。在等待制系統(tǒng)中，要求λ/μ<1，否則系統(tǒng)將是超負(fù)荷的，不能達(dá)到穩(wěn)態(tài)和無法討論。相應(yīng)的數(shù)量指標(biāo)通過進(jìn)一步計(jì)算可簡(jiǎn)化成下面更簡(jiǎn)單的形式。M/M/1等待制系統(tǒng)特征量計(jì)算公式P0=1/((λ/μ)0+(λ/μ)1+…+(λ/μ)n+…)=1-(λ/μ)Pn=(λ/μ)nP0=(λ/μ)n(1-(λ/μ))n=0,1,2,…Ls=λ/(μ-λ)e

＝μ（1－P0)=λWs＝Ls

/e=1/(μ-λ)Wq=Ws-

1/μ=1/(μ-λ)-1/μ=λ

/μ(μ-λ)Lq＝

Wqe=

λ2

/μ(μ-λ)例子某汽車加油站有一臺(tái)油泵為汽車加油，站內(nèi)可容納汽車量無限，若需加油的汽車按照泊松流到達(dá)，平均每小時(shí)4輛。每輛車加油所需時(shí)間服從負(fù)指數(shù)分布，平均每輛需12分鐘，試求系統(tǒng)有關(guān)運(yùn)行指標(biāo)。1、該系統(tǒng)屬于M/M/1等待制排隊(duì)系統(tǒng)。2、選用適當(dāng)公式計(jì)算有關(guān)指標(biāo)。計(jì)算一般遵循以下順序：Ls=λ/(μ-λ)＝4/(5-4)=4e

＝μ（1－P0)=λ=4Lq＝

Wqe=

λ2

/μ(μ-λ)=16/5=3.2Ws＝Ls

/e=1/(μ-λ)=1Wq=Ws-

1/μ=1-1/5=0.8練習(xí)1、某音樂廳設(shè)有一個(gè)售票處，營(yíng)業(yè)時(shí)間為8時(shí)到16時(shí)，假定顧客流和服務(wù)時(shí)間均為負(fù)指數(shù)分布，且顧客到來的平均間隔時(shí)間為2.5分鐘，窗口為每位顧客服務(wù)平均需1.5分鐘，試求：

1)顧客不需等待的概率p0;

2)平均排隊(duì)長(zhǎng)度Ls

3)顧客在系統(tǒng)內(nèi)平均逗留時(shí)間Ws

4)平均排隊(duì)等待人數(shù)Lq

5)平均排隊(duì)等待時(shí)間Wq；

6）系統(tǒng)內(nèi)顧客人數(shù)超過4個(gè)的概率；

7)顧客在系統(tǒng)內(nèi)逗留時(shí)間大于15分鐘的概率；

8）在六天工作日內(nèi)系統(tǒng)中沒有顧客的小時(shí)數(shù)；

9）若決定當(dāng)顧客平均逗留時(shí)間超過半小時(shí)時(shí)，就應(yīng)增加一個(gè)售票窗口，試問這相當(dāng)于要求顧客的平均到達(dá)率是原有的幾倍？課堂練習(xí)某維修店只有一個(gè)修理工人，來修理的顧客達(dá)到次數(shù)服從泊松分布，平均每小時(shí)4人，修理時(shí)間服從負(fù)指數(shù)分布，平均需6分鐘。求：1、修理店空閑時(shí)間概率；2、店內(nèi)有三個(gè)顧客的概率3、店內(nèi)至少有一個(gè)顧客的概率；4、店內(nèi)顧客平均數(shù)；5、在店內(nèi)平均逗留時(shí)間；6、等待服務(wù)的顧客平均數(shù)；7、平均等待服務(wù)時(shí)間；該系統(tǒng)為M/M/1/∞/∞/FCFS模型，λ＝4人/小時(shí)μ＝10人/小時(shí)1、P0=1-(λ/μ)＝1－4/10=0.6Pn=(λ/μ)nP0=(λ/μ)n(1-(λ/μ))2、P3=(λ/μ)3(1-(λ/μ))=0.03843、1－P0=0.44、Ls=λ/(μ-λ)＝4/(10-4)=2/3（人）5、Ws＝1/(μ-λ)＝1/(10-4)（小時(shí)）=10(分鐘）6、Lq＝

Wqe=

λ2

/μ(μ-λ)＝16/(10*6)=4/15（人）7、Wq=Ws-

1/μ=λ

/μ(μ-λ)＝1/15（小時(shí)）多服務(wù)臺(tái)指數(shù)分布排隊(duì)系統(tǒng)M/M/C/N/∞/FCFS混合制排隊(duì)系統(tǒng)1、系統(tǒng)意義：顧客按泊松流輸入，到達(dá)率為λ；服務(wù)時(shí)間服從負(fù)指數(shù)分布，服務(wù)率為μ；有C個(gè)服務(wù)臺(tái)，先到先服務(wù)，系統(tǒng)容量為N（N>C），顧客源無限的混合制排隊(duì)系統(tǒng)。顧客到達(dá)系統(tǒng)時(shí)，若無空閑服務(wù)臺(tái)，系統(tǒng)中顧客數(shù)小于N，則排隊(duì)等待服務(wù)；若系統(tǒng)中顧客數(shù)等于N，則離開系統(tǒng)另求服務(wù)。2、系統(tǒng)狀態(tài)轉(zhuǎn)移速度圖：0N-112N-2λλλλμcμ2μcμN(yùn)CC-1λλcμcμC+13μλ(c-1)μλcμcμλλ穩(wěn)態(tài)下狀態(tài)概率方程PA=0其中：P=(P0,P1,P2,P3,……Pn)狀態(tài)轉(zhuǎn)移速度矩陣由此可得穩(wěn)態(tài)概率應(yīng)滿足的關(guān)系：當(dāng)n<c時(shí)，有λP0＝μP1故P1＝(λ/μ)P0λP0－（μ＋λ）P1＋2μP2＝02μP2＝－λP0＋（μ＋λ）P1P2＝(λ2/2μ2)P0令ρ=λ/（cμ），稱為系統(tǒng)負(fù)荷強(qiáng)度，可得Pn的一般表達(dá)式：Pn＝λ/(nμ)Pn-1=(c/n)ρPn-1Pn＝1/n!(λ/μ)nP0Pn＝cn/n!ρn

P0當(dāng)c<n≤N時(shí)λPn－1＋cμPn+1=(λ+cμ)PnPn＝cn/c!ρn

P0也可以根據(jù)系統(tǒng)處于穩(wěn)態(tài)時(shí)每個(gè)狀態(tài)的轉(zhuǎn)入率等于轉(zhuǎn)出率求得Pn的一般表達(dá)式。系統(tǒng)的基本數(shù)量指標(biāo)由（P0+P1+…+Pn)=1可得

c-1P0=[∑cn/n!ρn+(cc/c!)*((ρc-ρN+1)/(1-ρ))]-1

n=0于是：cn/n﹗ρnP0

n<cPn=

cc/c﹗ρnP0

cn

N

NN-1λe=∑

λnPn=∑

λPn+0PN=λ(1-PN)n=0n=0Ls=Lq+λe/μ=Lq+cρ

(1-PN)

NLq=∑(n-c)Pn

n=c+1Lq=(ccρc+1P0

)/(c!(1-ρ

)2)[1-ρN-c

-(N-c)

ρ

N-c(1-ρ)]Wq=Lq/λe=Lq/(λ(1-PN))Ws=Wq+1/μ例子某汽車加油站有2臺(tái)油泵為汽車加油，站內(nèi)可容納4輛汽車，當(dāng)站內(nèi)停滿車時(shí)，后來的汽車只能到別處加油，若需加油的汽車按照泊松流到達(dá)，平均每小時(shí)4輛。每輛車加油所需時(shí)間服從負(fù)指數(shù)分布，平均每輛需12分鐘，試求系統(tǒng)有關(guān)運(yùn)行指標(biāo)。該系統(tǒng)是M/M/2/4/∞/FCFS混合制排隊(duì)系統(tǒng)；其中λ＝4（輛/小時(shí)）μ=1/(12/60)=5（輛/小時(shí)）C=2,ρ=λ/（cμ）=0.4

c-1P0=[∑cn/n!ρn+(cc/c!)*((ρc-ρN+1)/(1-ρ))]-1

n=0P0=[1+2ρ+22(ρ2-ρ5)/2!(1-ρ)]-1P0=[1+0.8+2*(0.42-0.45)/(1-0.4)]-1P0=0