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

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

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

2．系統(tǒng)對群體中各個部分提供服務(wù)時花費的時間長短；

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

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

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

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

1．常數(shù)

2．指數(shù)分布

3．愛爾蘭分布

4．超指數(shù)分布

5．庫克斯類分布

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

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

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

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

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

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

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

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

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

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

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

，則每個單一服務(wù)臺的到達率就是

／n

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

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

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

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

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

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

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

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

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

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

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

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

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

W與公式Lq=e

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

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

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

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

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

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

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

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

某一無線尋呼臺,每分鐘收到尋呼的次數(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歷史上，泊松分布是作為二項分布的近似，于1837年由法國數(shù)學(xué)家泊松引入的.二項分布與泊松分布命題對于二項分布B(n,p),當(dāng)n充分大,p又很小時,則對任意固定的非負整數(shù)k,有近似公式負指數(shù)分布當(dāng)顧客流為泊松流時，用T表示兩個相繼顧客到達系統(tǒng)的時間間隔，記其分布函數(shù)為由于故有相應(yīng)的分布密度為：它就是負指數(shù)分布的密度函數(shù)。易知：E(T)=1/D(T)=1/2通常，服務(wù)窗為一顧客服務(wù)所需的時間的分布函數(shù)與分布密度為其中參數(shù)為單位時間內(nèi)服務(wù)窗所完成服務(wù)的顧客均值數(shù)，且有4、愛爾蘭分布考察最簡單的事件流，記各事件到達系統(tǒng)的時間間隔序列為，且它們是同負指數(shù)分布的隨機變量序列，，如下圖所示。及拉氏變換的性質(zhì)得到再查反拉氏變換表知并且指數(shù)分布若隨機變量X具有概率密度則稱X

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

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

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

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

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

，方差D(T)=1/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，則每個單一服務(wù)臺的到達率就是

／n

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

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

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

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

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

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

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

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

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

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

W與公式Lq=e

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

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

n=0n=13)有效到達率e

（有效離去率μe

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

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

/e

Wq＝

Lq

/e

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

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

Lq＝

Wqe②有效到達率的另外一組計算公式e

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

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

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

P忙/P閑＝T閑×

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

(1-P0)/P0例子某汽車加油站有一臺油泵為汽車加油，站內(nèi)可容納4輛汽車，當(dāng)站內(nèi)停滿車時，后來的汽車只能到別處加油，若需加油的汽車按照泊松流到達，平均每小時4輛。每輛車加油所需時間服從負指數(shù)分布，平均每輛需12分鐘，試求系統(tǒng)有關(guān)運行指標(biāo)。1、分析為什么是M/M/1/4/∞/FCFS排隊系統(tǒng)。2、選用適當(dāng)公式計算有關(guān)指標(biāo)。λ＝4（輛/小時）μ=1/(12/60)=5（輛/小時），于是①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②平均隊長Ls

4

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

n=0

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

=1.5629③有效到達率e

=λ（1－PN）＋0PN

e

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

Ws＝Ls

/e

=1.5629/3.5128=0.4450⑤等待時間WqWq＝Ws-1/μ＝0.4450－0.2=0.2450⑥平均隊列長LqLq＝

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

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

/μ(μ-λ)例子某汽車加油站有一臺油泵為汽車加油，站內(nèi)可容納汽車量無限，若需加油的汽車按照泊松流到達，平均每小時4輛。每輛車加油所需時間服從負指數(shù)分布，平均每輛需12分鐘，試求系統(tǒng)有關(guān)運行指標(biāo)。1、該系統(tǒng)屬于M/M/1等待制排隊系統(tǒng)。2、選用適當(dāng)公式計算有關(guān)指標(biāo)。計算一般遵循以下順序：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è)有一個售票處，營業(yè)時間為8時到16時，假定顧客流和服務(wù)時間均為負指數(shù)分布，且顧客到來的平均間隔時間為2.5分鐘，窗口為每位顧客服務(wù)平均需1.5分鐘，試求：

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

2)平均排隊長度Ls

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

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

5)平均排隊等待時間Wq；

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

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

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

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

Wqe=

λ2

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

1/μ=λ

/μ(μ-λ)＝1/15（小時）多服務(wù)臺指數(shù)分布排隊系統(tǒng)M/M/C/N/∞/FCFS混合制排隊系統(tǒng)1、系統(tǒng)意義：顧客按泊松流輸入，到達率為λ；服務(wù)時間服從負指數(shù)分布，服務(wù)率為μ；有C個服務(wù)臺，先到先服務(wù)，系統(tǒng)容量為N（N>C），顧客源無限的混合制排隊系統(tǒng)。顧客到達系統(tǒng)時，若無空閑服務(wù)臺，系統(tǒng)中顧客數(shù)小于N，則排隊等待服務(wù)；若系統(tǒng)中顧客數(shù)等于N，則離開系統(tǒng)另求服務(wù)。2、系統(tǒng)狀態(tài)轉(zhuǎn)移速度圖：0N-112N-2λλλλμcμ2μcμNCC-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時，有λP0＝μP1故P1＝(λ/μ)P0λP0－（μ＋λ）P1＋2μP2＝02μP2＝－λP0＋（μ＋λ）P1P2＝(λ2/2μ2)P0令ρ=λ/（cμ），稱為系統(tǒng)負荷強度，可得Pn的一般表達式：Pn＝λ/(nμ)Pn-1=(c/n)ρPn-1Pn＝1/n!(λ/μ)nP0Pn＝cn/n!ρn

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

P0也可以根據(jù)系統(tǒng)處于穩(wěn)態(tài)時每個狀態(tài)的轉(zhuǎn)入率等于轉(zhuǎn)出率求得Pn的一般表達式。系統(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臺油泵為汽車加油，站內(nèi)可容納4輛汽車，當(dāng)站內(nèi)停滿車時，后來的汽車只能到別處加油，若需加油的汽車按照泊松流到達，平均每小時4輛。每輛車加油所需時間服從負指數(shù)分布，平均每輛需12分鐘，試求系統(tǒng)有關(guān)運行指標(biāo)。該系統(tǒng)是M/M/2/4/∞/FCFS混合制排隊系統(tǒng)；其中λ＝4（輛/小時）μ=1/(12/60)=5（輛/小時）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