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

1．群體到達系統的情況；

2．系統對群體中各個部分提供服務時花費的時間長短；

3．系統提供服務的先后次序；

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

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

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

1．常數

2．指數分布

3．愛爾蘭分布

4．超指數分布

5．庫克斯類分布

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

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

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

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

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

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

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

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

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

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

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

，則每個單一服務臺的到達率就是

／n

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

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

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

FCFS：表示先到先服務的排隊規則；

LCFS：表示后到先服務的排隊規則；

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

隊長是指系統中的平均顧客數，即排隊等待的顧客數與正在接受服務的顧客數之和；

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

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

等于單位時間內接受服務完畢離開系統的平均顧客數S*，即有e

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

W該式揭示了指標L與W之間的數量關系。該式的物理意義是：平均隊長等于單位時間內到達并進入系統的平均顧客數乘以平均逗留時間，即等于平均逗留時間內進入系統的總的平均顧客數。基本關系式4Lq=e

Wq該式揭示了指標Lq與Wq之間的數量關系。該式的物理意義是：平均等待隊長等于單位時間內到達并進入系統的平均顧客數乘以平均等待時間，即等于平均等待時間內進入系統的總的平均顧客數。Little公式公式L=e

W與公式Lq=e

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

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

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

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

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

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

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

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

某一無線尋呼臺,每分鐘收到尋呼的次數X服從參數=3的泊松分布.

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

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

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

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

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

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

，方差D(T)=1/

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

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

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

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

其中>0為一常數，此種的平均服務時間為：

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

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

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

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

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

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

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

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

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

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

，則每個單一服務臺的到達率就是

／n

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

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

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

FCFS：表示先到先服務的排隊規則；

LCFS：表示后到先服務的排隊規則；

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

等于單位時間內接受服務完畢離開系統的平均顧客數S*，即有e

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

W該式揭示了指標L與W之間的數量關系。該式的物理意義是：平均隊長等于單位時間內到達并進入系統的平均顧客數乘以平均逗留時間，即等于平均逗留時間內進入系統的總的平均顧客數。基本關系式4Lq=e

Wq該式揭示了指標Lq與Wq之間的數量關系。該式的物理意義是：平均等待隊長等于單位時間內到達并進入系統的平均顧客數乘以平均等待時間，即等于平均等待時間內進入系統的總的平均顧客數。Little公式公式L=e

W與公式Lq=e

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

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

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

（有效離去率μe

）：平均每單位時間進入（離去）系統的顧客數。在穩態情況下兩者相等，因此有：e

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

/e

Wq＝

Lq

/e

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

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

Lq＝

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

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

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

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

P忙/P閑＝T閑×

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

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

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

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

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

2)平均排隊長度Ls

3)顧客在系統內平均逗留時間Ws

4)平均排隊等待人數Lq

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

6）系統內顧客人數超過4個的概率；

7)顧客在系統內逗留時間大于15分鐘的概率；

8）在六天工作日內系統中沒有顧客的小時數；

9）若決定當顧客平均逗留時間超過半小時時，就應增加一個售票窗口，試問這相當于要求顧客的平均到達率是原有的幾倍？課堂練習某維修店只有一個修理工人，來修理的顧客達到次數服從泊松分布，平均每小時4人，修理時間服從負指數分布，平均需6分鐘。求：1、修理店空閑時間概率；2、店內有三個顧客的概率3、店內至少有一個顧客的概率；4、店內顧客平均數；5、在店內平均逗留時間；6、等待服務的顧客平均數；7、平均等待服務時間；該系統為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（小時）多服務臺指數分布排隊系統M/M/C/N/∞/FCFS混合制排隊系統1、系統意義：顧客按泊松流輸入，到達率為λ；服務時間服從負指數分布，服務率為μ；有C個服務臺，先到先服務，系統容量為N（N>C），顧客源無限的混合制排隊系統。顧客到達系統時，若無空閑服務臺，系統中顧客數小于N，則排隊等待服務；若系統中顧客數等于N，則離開系統另求服務。2、系統狀態轉移速度圖：0N-112N-2λλλλμcμ2μcμNCC-1λλcμcμC+13μλ(c-1)μλcμcμλλ穩態下狀態概率方程PA=0其中：P=(P0,P1,P2,P3,……Pn)狀態轉移速度矩陣由此可得穩態概率應滿足的關系：當n<c時，有λP0＝μP1故P1＝(λ/μ)P0λP0－（μ＋λ）P1＋2μP2＝02μP2＝－λP0＋（μ＋λ）P1P2＝(λ2/2μ2)P0令ρ=λ/（cμ），稱為系統負荷強度，可得Pn的一般表達式：Pn＝λ/(nμ)Pn-1=(c/n)ρPn-1Pn＝1/n!(λ/μ)nP0Pn＝cn/n!ρn

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

P0也可以根據系統處于穩態時每個狀態的轉入率等于轉出率求得Pn的一般表達式。系統的基本數量指標由（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臺油泵為汽車加油，站內可容納4輛汽車，當站內停滿車時，后來的汽車只能到別處加油，若需加油的汽車按照泊松流到達，平均每小時4輛。每輛車加油所需時間服從負指數分布，平均每輛需12分鐘，試求系統有關運行指標。該系統是M/M/2/4/∞/FCFS混合制排隊系統；其中λ＝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