排隊論運籌學1排隊論排隊論(queuingtheory)也稱隨機效勞系統理論(RandomServiceSystemTheory)，是為研究和解決具有擁擠現象的問題而開展起來的一門應用數學的分支。具體地說，它是在研究各種排隊系統概率規(guī)律性的根底上，解決相應排隊系統的最優(yōu)設計和最優(yōu)控制問題。2排隊論排隊論是1909年由丹麥工程師愛爾朗(A.K．Erlang)在研究電活系統時創(chuàng)立的，幾十年來排隊論的應用領域越來越廣泛，理論也日漸完善。特別是自二十世紀60年代以來，由于計算機的飛速開展，更為排隊論的應用開拓了寬闊的前景。3排隊論排隊論(queuingtheory)研究內容包括三個局部：(1)排隊系統的性態(tài)問題(2)排隊系統的最優(yōu)化問題(3)排隊系統的統計推斷問題性態(tài)問題，即研究各種排隊系統的概率規(guī)律性，主要研究隊長分布、等待時間分布和忙期分布等。最優(yōu)化，又分靜態(tài)最優(yōu)和動態(tài)最優(yōu)，前者指最優(yōu)設計，后者指現有排隊系統的最優(yōu)運營。統計推斷，即判斷一個給定的排隊系統符合哪種模型，以便根據排隊理論進行研究。解排隊問題的目的，是研究排隊系統運行的效率，估計效勞質量，確定系統參數的最優(yōu)值，以決定系統結構是否合理，研究設計改進措施等。4排隊論

第1節(jié)根本概念第2節(jié)到達間隔的分布和效勞時間的分布第3節(jié)單效勞臺負指數分布排隊系統的分析第4節(jié)多效勞臺負指數分布排隊系統的分析第5節(jié)一般效勞時間M/G/1模型第6節(jié)經濟分析——系統的最優(yōu)化第7節(jié)分析排隊系統的隨機模擬法5第1節(jié)基本概念1.1排隊過程的一般表示1.2排隊系統的組織和特征1.3排隊模型的分類1.4排隊問題的求解6不同的顧客與效勞組成了各式各樣的效勞系統。顧客為了得到某種效勞而到達系統、假設不能立即獲得效勞而又允許排隊等待，那么參加隊列排隊等待接受效勞，然后效勞臺按一定規(guī)那么從隊列中選擇顧客進行效勞，獲得效勞的顧客立即離開系統。1.1排隊過程的一般表示71.1排隊過程的一般表示各個顧客由顧客源(總體)出發(fā)，到達效勞機構(效勞臺、效勞員)前排隊等候接受效勞，效勞完成后離開。排隊結構指隊列的數目和排列方式，排隊規(guī)那么和效勞規(guī)那么是說明顧客在排隊系統中按怎樣的規(guī)那么、次序接受效勞的。排隊過程的一般模型81.1排隊過程的一般表示到達的顧客要求服務內容服務機構1.不能運轉的機器2.修理技工3.病人4.電話呼喚5.文件稿6.提貨單7.到達機場上空的飛機8.駛入港口的貨船9.上游河水進入水庫10.進入我方陣地的敵機修理領取修配零件診斷或動手術通話打字提取存貨降落裝(卸)貨裝(卸)放水，調整水位我方高射炮進行射擊修理技工發(fā)放修配零件的管理員醫(yī)生(或包括手術臺)交換臺打字員倉庫管理員跑道貨碼頭(泊位)水閘管理員我方高射炮形形色色的排隊系統9實際的排隊系統雖然千差萬別，但是它們有以下的共同特征：(1)有請求效勞的人或物——顧客；(2)有為顧客效勞的人或物，即效勞員或效勞臺；(3)顧客到達系統的時刻是隨機的，為每一位顧客提供效勞的時間是隨機的，因而整個排隊系統的狀態(tài)也是隨機的。排隊系統的這種隨機性造成某個階段顧客排隊較長，而另外一些時候效勞員(臺)又空閑無事。1.2排隊系統的組成和特征101.2排隊系統的組成和特征排隊系統由三個根本局部組成：①輸入過程②排隊規(guī)那么③效勞機構111.2排隊系統的組成和特征輸入過程輸入即指顧客到達排隊系統。輸入過程是指要求效勞的顧客是按怎樣的規(guī)律到達排隊系統的過程，有時也把它稱為顧客流。一般可以從以下幾個方面來描述—個輸入過程(1)顧客的總體數，又稱顧客源、輸入源。這是指顧客的來源。顧客源可以是有限的，也可以是無限的。例如，到售票處購票的顧客總數可以認為是無限的，而某個工廠因故障待修的機床那么是有限的。121.2排隊系統的組成和特征輸入過程(2)顧客到來的方式。這是描述顧客是怎樣來到系統的，他們是單個到達，還是成批到達。病人到醫(yī)院看病是顧客單個到達的例子。在庫存問題中如將生產器材進貨或產品入庫看作是顧客，那么這種顧客那么是成批到達的。131.2排隊系統的組成和特征輸入過程(3)顧客流的概率分布，或稱相繼顧客到達的時間間隔的分布。這是求解排隊系統有關運行指標問題時，首先需要確定的指標。這也可以理解為在一定的時間間隔內到達K個顧客(K=1、2、)的概率是多大。顧客相繼到達的間隔時間可以是確定型的，也可以是隨機型的。顧客流的概率分布一般有定長分布、二項分布、泊松流(最簡單流)、愛爾朗分布等假設干種。141.2排隊系統的組成和特征輸入過程(4)顧客的到達可以是相互獨立的。(5)輸入過程可以是平穩(wěn)的，或稱對時間是齊次的，即描述相繼到達的間隔時間分布和所含參數(如期望值、方差等)都是與時間無關的。151.2排隊系統的組成和特征排隊規(guī)那么這是指效勞臺從隊列中選取顧客進行效勞的順序。一般可以分為損失制、等待制和混合制等3大類。(1)損失制。這是指如果顧客到達排隊系統時，所有效勞臺都已被先來的顧客占用，那么他們就自動離開系統永不再來。典型例子是，如拔號后出現忙音，顧客不愿等待而自動掛斷，如要再打，就需重新拔號，這種效勞規(guī)那么即為損失制。

161.2排隊系統的組成和特征排隊規(guī)那么(2)等待制。這是指當顧客來到系統時，所有效勞臺都不空，顧客參加排隊行列等待效勞。例如，排隊等待售票，故障設備等待維修等。對于等待制，為顧客進行效勞的次序可以采用以下各種規(guī)那么：先到先效勞(FCFS)后到先效勞(LCFS)隨機效勞(RS)有優(yōu)先權的效勞171.2排隊系統的組成和特征排隊規(guī)那么(2)等待制。對于等待制，為顧客進行效勞的次序可以采用以下各種規(guī)那么：①先到先效勞。按顧客到達的先后順序對顧客進行效勞，這是最普遍的情形。②后到先效勞。倉庫中迭放的鋼材，后迭放上去的都先被領走，就屬于這種情況。③隨機效勞。即當效勞臺空閑時，不按照排隊序列而隨意指定某個顧客去接受效勞，如交換臺接通呼叫就是一例。④優(yōu)先權效勞。如老人、兒童先進車站；危重病員先就診；遇到重要數據需要處理計算機立即中斷其他數據的處理等，均屬于此種效勞規(guī)那么。181.2排隊系統的組成和特征排隊規(guī)那么(3)混合制．這是等待制與損失制相結合的一種效勞規(guī)那么，一般是指允許排隊，但又不允許隊列無限長下去。具體說來，大致有三種：①隊長有限。當排隊等待效勞的顧客人數超過規(guī)定數量時，后來的顧客就自動離去，另求效勞，即系統的等待空間是有限的。例如最多只能容納K個顧客在系統中，當新顧客到達時，假設系統中的顧客數(又稱為隊長)小于K，那么可進入系統排隊或接受效勞；否那么，便離開系統，并不再回來。如水庫的庫容是有限的，旅館的床位是有限的。191.2排隊系統的組成和特征排隊規(guī)那么(3)混合制①隊長有限。②等待時間有限。即顧客在系統中的等待時間不超過某一給定的長度T，當等待時間超過T時，顧客將自動離去，并不再回來。如易損壞的電子元器件的庫存問題，超過一定存儲時間的元器件被自動認為失效。又如顧客到飯館就餐，等了一定時間后不愿再等而自動離去另找飯店用餐。201.2排隊系統的組成和特征排隊規(guī)那么(3)混合制①隊長有限。②等待時間有限。③逗留時間(等待時間與效勞時間之和)有限。例如用高射炮射擊敵機，當敵機飛越高射炮射擊有效區(qū)域的時間為t時，假設在這個時間內未被擊落，也就不可能再被擊落了。不難注意到，損失制和等待制可看成是混合制的特殊情形，如記s為系統中效勞臺的個數，那么當K=s時，混合制即成為損失制；當K=∞時，混合制即成為等待制。211.2排隊系統的組成和特征排隊規(guī)那么〔續(xù)〕從允許排隊的空間看隊列可以排在具體的處所，也可以是抽象的。排隊空間可以有限，也可以無限。從排隊的隊列數目看，可以是單列，也可以是多列。在多列的情形，各列間的顧客有的可以互相轉移，有的不能。有的排隊顧客因等候時間過長而中途退出，有的不能退出，必須堅持到被效勞為止。221.2排隊系統的組成和特征效勞機構(效勞臺情況)效勞臺可以從以下3方面來描述：(1)效勞臺數量及構成形式。效勞機構可以沒有效勞員，也可以有一個或多個效勞員(效勞臺、通道、窗口等)。從數量上說，效勞臺有單效勞臺和多效勞臺之分。在有多個效勞臺的情形中，可以是平行排列的，也可以是前后排列的，或混合排列的。231.2排隊系統的組成和特征效勞機構(效勞臺情況)效勞臺可以從以下3方面來描述：(1)效勞臺數量及構成形式。從構成形式上看，效勞臺有：①單隊——單效勞臺式；如(a)圖②單隊——多效勞臺并聯式；如(c)圖③多隊——多效勞臺并聯式；如(b)圖④單隊——多效勞臺串聯式；如(d)圖⑤單隊——多效勞臺并串聯混合式；⑥多隊——多效勞臺并串聯混合式等等。效勞臺的各種排列方式24單隊列——S個效勞臺并聯的排隊系統S個隊列——S個效勞臺的并聯排隊系統1.2排隊系統的組成和特征25單隊——多個效勞臺的串聯排隊系統

多隊——多效勞臺混聯、網絡系統1.2排隊系統的組成和特征261.2排隊系統的組成和特征效勞機構(效勞臺情況)(2)效勞方式。這是指在某一時刻接受效勞的顧客數，它有單個效勞和成批效勞兩種。如公共汽車一次就可裝載一批乘客就屬于成批效勞。(3)效勞時間的分布。效勞時間可分為確定型和隨機型。一般來說，在多數情況下，對每一個顧客的效勞時間是一隨機變量，其概率分布有定長分布、負指數分布、K級愛爾良分布、一般分布(所有顧客的效勞時間都是獨立同分布的)等等。效勞時間的分布通常假定是平穩(wěn)的。271.3排隊模型的分類排隊模型分類方法，1953構成排隊模型的三個主要特征指標(1)相繼顧客到達間隔時間的分布；(2)效勞時間的分布；(3)效勞臺的個數。根據這三個特征對排隊模型進行分類的Kendall記號：X/Y/ZX：表示相繼到達間隔時間的分布；Y：表示效勞時間的分布；Z：并列的效勞臺的數目。281.3排隊模型的分類表示相繼到達間隔時間和效勞時間的各種分布符號M——負指數分布(M是Markov的字頭，因為負指數分布具有無記憶性，即Markov性)D——確定型(deterministic)Ek——k階愛爾朗(erlang)分布GI——一般相互獨立(generalindependent)的時間間隔的分布G——一般(general)效勞時間的分布291.3排隊模型的分類Kendall符號的擴充X/Y/Z/A/B/C其中前三項的意義不變，后三項的意義分別是：A：系統容量限制N，或稱等待空間容量。如系統有N個等待位子，那么0<N<∞。當N=0時，說明系統不允許等待，即為損失制。N=∞時為等待制系統，此時∞般省略不寫。N為有限整數時，表示為混合制系統。B：顧客源數目m。分有限與無限兩種，∞表示顧客源無限，此時一般∞也可省略不寫。C：效勞規(guī)那么，如先到先效勞(FCFS)，后到后效勞(LCFS)，優(yōu)先權效勞(PR)等。301.3排隊模型的分類Kendall符號的擴充X/Y/Z/A/B/C某些情況下，排隊問題僅用上述表達形式中的前3個、4個、5個符號。如不特別說明那么均理解為系統等待空間容量無限；顧客源無限，先到先效勞，單個效勞的等待制系統。約定：如略去后三項，即指X/Y/Z/∞/∞/FCFS的情形。例如：某排隊問題為M／M／S／∞／∞／FCFS／，那么表示顧客到達間隔時間為負指數分布(泊松流)；效勞時間為負指數分布；有s(s＞1)個效勞臺；系統等待空間容量無限(等待制)；顧客源無限，采用先到先效勞規(guī)那么。311.4排隊問題的求解首先需要確定屬于哪種排隊模型，其中顧客到達的間隔時間分布和效勞時間的分布需要實測的數據來確定確定用以判斷系統運行優(yōu)劣的根本數量指標，求出這些數量指標的概率分布或特征數321.4排隊問題的求解用于描述排隊系統運行狀況的根本數量指標(1)隊長：系統中的顧客數，是排隊等待的顧客數與正在接受效勞的顧客數之和，期望值記作Ls；排隊長〔隊列長〕：系統中排隊等待效勞的顧客數，期望值記作Lq；

隊長和排隊長一般都是隨機變量。我們希望能確定它們的分布，或至少能確定它們的平均值(即平均隊長和平均排隊長)及有關的矩(如方差等)。隊長的分布是顧客和效勞員都關心的，特別是對系統設計人員來說，如果能知道隊長的分布，就能確定隊長超過某個數的概率，從而確定合理的等待空間。331.4排隊問題的求解用于描述排隊系統運行狀況的根本數量指標(2)逗留時間：顧客在系統中的停留時間，從顧客到達時刻起到他接受效勞完成止這段時間，期望值記作Ws；是隨機變量，也是顧客最關心的指標之一。等待時間：顧客在系統中排隊等待的時間，從顧客到達時刻起到他開始接受效勞止這段時間，期望值記作Wq，是隨機變量，也是顧客最關心的指標，因為顧客通常希望等待時間越短越好。［逗留時間］＝［等待時間］＋［效勞時間］對這兩個指標的研究當然是希望能確定它們的分布，或至少能知道顧客的平均等待時間和平均逗留時間。341.4排隊問題的求解用于描述排隊系統運行狀況的根本數量指標(3)忙期：指從顧客到達空閑效勞機構起，到效勞機構再次為空閑止的時間長度，即效勞機構連續(xù)忙的時間。這是個隨機變量，是效勞員最為關心的指標，因為它關系到效勞員的效勞強度。閑期：即效勞機構連續(xù)保持空閑的時間。在排隊系統中，忙期和閑期總是交替出現的。其他一些指標，如在損失制或系統容量有限的情況下，由于顧客被拒絕，而使效勞系統受到損失的顧客損失率及效勞強度等351.4排隊問題的求解系統狀態(tài)的概率分布系統的狀態(tài)即指系統中的顧客數，它的可能取值是：(1)隊長沒有限制時，n=0，1，2，…(2)隊長有限制、最大數為N時，n=0，1，2，…，N(3)即時制且效勞臺個數為c時，n=0，1，2，…，c系統處于這些狀態(tài)的概率一般是隨時間t變化的，所以在時刻t、系統狀態(tài)為n的概率可以用Pn(t)表示。361.4排隊問題的求解求狀態(tài)概率Pn(t)的方法：

建立含Pn(t)的關系式，該關系式一般是包含Pn(t)的微分差分方程(關于t的微分方程，關于n的差分方程)。該方程的解稱為瞬態(tài)(或稱過渡狀態(tài))(transientstate)解。它的極限稱為穩(wěn)態(tài)(steadystate)解，或稱統計平衡狀態(tài)(statisticalequilibriumstate)解。371.4排隊問題的求解穩(wěn)態(tài)解的物理意義當系統運行了無限長時間后，初始(t=0)狀態(tài)的概率分布(Pn(0)，n≥0)的影響將消失，系統狀態(tài)的概率分布不再隨時間而變化。在實際應用中，大多數系統會很快趨于穩(wěn)態(tài)，而無需等到t→∞以后。求穩(wěn)態(tài)概率Pn時，不需要求t→∞時Pn(t)的極限，而只需令導數P’n(t)=0即可。381.4排隊問題的求解上面給出的這些數量指標一般都是和系統運行的時間有關的隨機變量，求這些隨機變量的瞬時分布一般是很困難的。為了分析上的簡便，并注意到相當一局部排隊系統在運行了一定時間后，都會趨于一個平衡狀態(tài)(或稱平穩(wěn)狀態(tài))。在平衡狀態(tài)下，隊長的分布、等待時間的分布和忙期的分布都和系統所處的時刻無關，而且系統的初始狀態(tài)的影響也會消失。因此，本章中將主要討論與系統所處時刻無關的性質，即統計平衡性質。39排隊論

第1節(jié)根本概念第2節(jié)到達間隔的分布和效勞時間的分布第3節(jié)單效勞臺負指數分布排隊系統的分析第4節(jié)多效勞臺負指數分布排隊系統的分析第5節(jié)一般效勞時間M/G/1模型第6節(jié)經濟分析——系統的最優(yōu)化第7節(jié)分析排隊系統的隨機模擬法402.1到達間隔的分布2.1.1經驗分布〔定長輸入〕2.1.2普阿松流〔泊松流〕2.1.3愛爾朗分布2.2效勞時間的分布2.2.1經驗分布〔定長分布〕2.2.2負指數分布2.2.3愛爾朗分布第2節(jié)到達間隔的分布和效勞時間的分布412.1.1經驗分布例1

大連港大港區(qū)1979年載貨500噸以上船舶到達(不包括定期到達的船舶)逐日記錄見書上表12-2。將表12-2整理成船舶到達數的分布表?？梢杂嬎愠觯浩骄竭_率=到達總數/總天數=1271/365=3.48(艘/天)船舶到達數n頻數頻率(%)0120.0331430.1182640.1753740.2034710.1955490.1346260.0717190.052840.011920.00510以上10.003合計3651.000422.1.1經驗分布以τi表示第i號顧客到達的時刻，以si表示對它的效勞時間，這樣可算出相繼到達的間隔時間ti(ti=τi+1-τi)和排隊等待時間wi，它們的關系如下：實際中測定相繼到達時間間隔的方法相繼到達時間間隔等待時間432.1.1經驗分布例2某效勞機構是單效勞臺，先到先效勞，對41個顧客記錄到達時刻τ和效勞時間s(單位為分鐘)如表12-4。在表中以第1號顧客到達時刻為0，對所有顧客的全部效勞時間為127分鐘。將原始記錄整理成下表。到達間隔/分鐘次數162103846536272819110以上1合計40服務時間/分鐘次數1102103745546271819以上1合計41442.1.1經驗分布例2平均間隔時間=142/40=3.55(分鐘/人)平均到達率=41/142=0.28(人/分鐘)平均效勞時間=127/41=3.12(分鐘/人)平均效勞率=41/127=0.32(人/分鐘)45普阿松流，又稱為泊松流、Poisson過程、最簡單流，是排隊論中一種常用來描述顧客到達規(guī)律的特殊的隨機過程。2.1.2普阿松流〔泊松流〕462.1.2普阿松流〔泊松流〕設表示在時間區(qū)間內到達的顧客數令表示在時間區(qū)間內有個顧客到達的概率，即當滿足以下三個條件時，我們說顧客的到達形成泊松流。(1)在不相重疊的時間區(qū)間內顧客到達數是相互獨立的，即無后效性。通俗地說就是以前到達的顧客情況，對以后顧客的到來沒有影響。否那么就是關聯的。(2)平穩(wěn)性。又稱作輸入過程是平穩(wěn)的，對充分小的，在時間區(qū)間內有1個顧客到達的概率與t無關，而與區(qū)間長度成正比，即

其中，當時，是關于的高階無窮小。

進一步地，在長度為t的時段內恰好到達k個顧客的概率僅與時段長度有關，而與時段起點無關。即對任意∈(0,∞)，在(,+t]或(0,t)內恰好到達k個顧客的概率相等：(3)單個性又稱普通性。對于充分小的，在時間區(qū)間內有2個或2個以上顧客到達的概率極小，以至于可以忽略，即

47當顧客到達為泊松流時，研究顧客到達數n的概率分布。由條件(2)，總可以取時間由0算起，并簡記由條件(2)和(3)，容易推得在區(qū)間內沒有顧客到達的概率

將區(qū)間分成兩個互不重疊的區(qū)間和。那么到達總數n分別出現在這兩個區(qū)間和上，有以下(A)(B)(C)三種情況：概率個數概率個數概率個數區(qū)間情況2.1.2普阿松流〔泊松流〕482.1.2普阿松流〔泊松流〕在內到達n個顧客應是表中(A)(B)(C)三種互不相容的情況之一，所以概率應是表中三個概率之和(各合為一項)令，得以下方程，并注意到初始條件，那么有當n=0時，沒有(B)，(C)兩種情況，所以得49解(12-5)式和(12-6)式，得表示長為t的時間區(qū)間內到達n個顧客〔即N(t)=n〕的概率，由(12-7)式得隨機變量服從泊松分布。結論：當顧客到達為泊松流時，在長度為t的時間內到達n個顧客的概率Pn(t)服從泊松分布!!它的數學期望和方差分別是2.1.2普阿松流〔泊松流〕相等！特別地，t=1時，E[N(1)]=λ

，因此λ表示單位時間平均到達的顧客數50是指相繼顧客到達時間間隔T相互獨立，其分布密度為

其中，k為非負整數。

2.1.3愛爾朗分布愛爾朗分布512.1.3愛爾朗分布設是k個相互獨立的隨機變量，服從相同參數的負指數分布，那么的概率密度是稱T服從k階愛爾朗分布，其均值和方差分別為可以證明如下結論。522.1.3愛爾朗分布愛爾朗分布的意義當k=1時，愛爾朗分布化為負指數分布，可看成是一種完全隨機的分布；當k增大時，愛爾朗分布的圖形逐漸變?yōu)閷ΨQ的；當k≥30時愛爾朗分布近似于正態(tài)分布；k→∞時，Var［T］→0，這時愛爾朗分布化為確定型分布。一般k階愛爾朗分布可看成完全隨機與完全確定的中間型，能對現實世界提供更為廣泛的適應性。532.1.3愛爾朗分布可以證明，在參數為的泊松輸人中，對任意的j與k,設第j與第j+k個顧客之間的到達間隔為。那么隨機變量Tk的分布必遵從參數為的愛爾朗分布，其分布密度為：例如：某排隊系統有并聯的k個效勞臺，顧客流為泊松流，規(guī)定第i,K+i,2K+i…個顧客排入第i號臺(i=1,2,…,K)，那么第K臺所獲得的顧客流，即為愛爾朗輸入流，其他各臺，從它的第一個顧客到達以后開始所獲得的流也為愛爾朗輸入流。542.1到達間隔的分布2.1.1經驗分布〔定長輸入〕2.1.2普阿松流〔泊松流〕2.1.3愛爾朗分布2.2效勞時間的分布2.2.1經驗分布〔定長分布〕2.2.2負指數分布2.2.3愛爾朗分布第2節(jié)到達間隔的分布和效勞時間的分布552.2效勞時間的分布

2.2.1效勞時間的定長分布。每一個顧客的效勞時間都是常數，此時效勞時間t的分布函數為：

562.2.2效勞時間的負指數分布如果隨機變量T的概率密度是那么稱T服從負指數分布。它的分布函數是數學期望為方差為標準差為負指數分布的定義57效勞時間v的分布對顧客的效勞時間，也就是在忙期相繼離開系統的兩顧客的間隔時間，有時也服從負指數分布。設它的分布函數和密度分別是其中表示單位時間能被效勞完成的顧客數，稱為平均效勞率，表示對顧客的平均效勞時間。2.2.2效勞時間的負指數分布58負指數分布的性質(1)由條件概率公式容易證明該性質稱為無記憶性或馬爾柯夫性。假設T表示排隊系統中顧客相繼到達的間隔時間，該性質說明：一個顧客到來所需的時間與過去一個顧客到來所需時間s無關，也就是說該顧客是隨機地到達。(2)當輸入過程是泊松流時，那么顧客相繼到達的間隔時間T〔注意T是隨機變量〕必然服從負指數分布。這是因為對于泊松流，在區(qū)間內至少有1個顧客到達的概率是又可表示為

根據〔12.10〕即得顧客相繼到達的間隔時間T必然服從負指數分布。2.2.2效勞時間的負指數分布59(2)當輸入過程是泊松流時，那么顧客相繼到達的間隔時間T〔注意T是隨機變量〕必然服從負指數分布。這是因為對于泊松流，在區(qū)間內至少有1個顧客到達的概率是又可表示為

根據〔12.10〕即得顧客相繼到達的間隔時間T必然服從負指數分布。上述內容還可以用如下表達！對于泊松流，其相繼顧客到達時間間隔

i，i=1,2,…是相互獨立同分布的，其分布函數為負指數分布：

2.2.2效勞時間的負指數分布60顧客相繼到達的間隔時間獨立且為同負指數分布(密度函數為)，與輸入過程為泊松流(參數為λ)是等價的。對于泊松流，λ表示單位時間平均到達的顧客數，1/λ表示相繼顧客到達平均間隔時間。相繼到達時間間隔為負指數分布與到達為泊松流的等價性2.2.2效勞時間的負指數分布61愛爾朗分布。即每個顧客的效勞時間相互獨立，具有相同的愛爾朗分布。其密度函數為

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

K=1時愛爾朗分布化歸為負指數分布當K→∞時，得到長度為1/的定長效勞。例子：串列的k個效勞臺，每臺效勞時間相互獨立，服從相同的負指數分布(參數kμ)，那么一顧客走完這k個效勞臺總共所需要效勞時間就服從k階愛爾朗分布。2.2.3效勞時間的愛爾朗分布62第1節(jié)根本概念第2節(jié)到達間隔的分布和效勞時間的分布第3節(jié)單效勞臺負指數分布排隊系統的分析第4節(jié)多效勞臺負指數分布排隊系統的分析第5節(jié)一般效勞時間M/G/1模型第6節(jié)經濟分析——系統的最優(yōu)化第7節(jié)分析排隊系統的隨機模擬法排隊論

63排隊論

排隊論研究的首要問題是排隊系統主要數量指標的概率規(guī)律，即研究系統的整體性質，然后進一步研究系統的優(yōu)化問題。與這兩個問題相關的還包括排隊系統的統計推斷問題。(1)通過研究主要數量指標在瞬時或平穩(wěn)狀態(tài)下的概率分布及其數字特征，了解系統運行的根本特征。(2)統計推斷問題，建立適當的排隊模型是排隊論研究的第一步，建立模型過程中經常會碰到如下問題：檢驗系統是否到達平穩(wěn)狀態(tài)；檢驗顧客相繼到達時間間隔的相互獨立性；確定效勞時間的分布及有關參數等。64(3)系統優(yōu)化問題，又稱為系統控制問題或系統運營問題，其根本目的是使系統處于最優(yōu)或最合理的狀態(tài)。系統優(yōu)化問題包括最優(yōu)設計問題和最優(yōu)運營問題，其內容很多，有最少費用問題、效勞率的控制問題、效勞臺的開關策略、顧客(或效勞)根據優(yōu)先權的最優(yōu)排序等方面的問題。對于一般的排隊系統運行情況的分析，通常是在給定輸入與效勞條件下，通過求解系統狀態(tài)為n(有n個顧客)的概率Pn(t)，再進行計算其主要的運行指標：排隊論

65①系統中顧客數(隊長)的期望值L或Ls；②排隊等待的顧客數(排隊長)的期望值Lq；③顧客在系統中全部時間(逗留時間)的期望值W或Ws；④顧客排隊等待時間的期望值Wq。

排隊系統中，由于顧客到達分布和效勞時間分布是多種多樣的，加之效勞臺數。顧客源有限無限，排隊容量有限無限等的不同組合，就會有不勝枚舉的不同排隊模型，假設對所有排隊模型都進行分析與計算，不但十分繁雜而且也沒有必要。下面擬分析幾種常見排隊系統模型。排隊論

663.1標準的M/M/1模型(M/M/1/∞/∞)3.2系統容量有限的情況(M/M/1/N/∞)3.3顧客源有限的情形(M/M/1/∞/m)第3節(jié)單效勞臺負指數分布排隊系統的分析本節(jié)討論輸入過程服從普阿松分布過程、效勞時間服從負指數分布單效勞臺的排隊系統。67標準的M/M/1模型(1)輸入過程——顧客源是無限的，顧客單個到來，相互獨立，一定時間內的到達數服從泊松分布，到達過程是平穩(wěn)的。(2)排隊規(guī)那么——單隊，且對隊長沒有限制，先到先效勞。(3)效勞機構——單效勞臺，各顧客的效勞時間相互獨立，服從相同的負指數分布。此外，還假定到達間隔時間和效勞時間是相互獨立的。3.1標準的M/M/1模型(M/M/1/∞/∞)即條件：λ：顧客進入系統的平均速度，即單位時間到達的顧客數。μ：顧客離開系統的平均速度，即單位時間能被效勞完成的顧客數。68首先要求出：系統在任意時刻t的狀態(tài)為n(即系統中有n個顧客)的概率，它決定了系統運行的特征。因到達規(guī)律服從參數為的泊松過程，效勞時間服從參數為的負指數分布，所以在時間區(qū)間內分為：(1)有1個顧客到達的概率為沒有顧客到達的概率就是(2)當有顧客在接受效勞時，1個顧客被效勞完了(離去)的概率是，沒有離去的概率就是。(3)多于一個顧客的到達或離去的概率是，可以忽略。3.1標準的M/M/1模型(M/M/1/∞/∞)693.1標準的M/M/1模型(M/M/1/∞/∞)在時刻，系統中有n個顧客(n＞0)存在以下四種情況(到達或離去是2個以上的沒列入)：○表示發(fā)生(1個)；×表示沒有發(fā)生。n○○n(D)n×○n-1(C)n○×n+1(B)n××n(A)離去到達在時刻顧客數在區(qū)間在時刻t顧客數情況7071這四種情況是互不相容的，所以應是這四項之和，即即令，得關于的微分差分方程3.1標準的M/M/1模型(M/M/1/∞/∞)所有的高階無窮小和并72當，那么只有上表中(A)(B)情況，且方式(A)中無離去的概率為1，即同理求得它們的概率分別是情況(A)情況(B)情況(C)情況(D)n○○n(D)n×○n-1(C)n○×n+1(B)n××n(A)離去到達在時刻顧客數在區(qū)間在時刻t顧客數情況3.1標準的M/M/1模型(M/M/1/∞/∞)73研究穩(wěn)態(tài)的情況。這時與時間t無關，可寫成，它的導數為0。由(12-15)式和(12-16)式可得這是關于的差分方程，它說明了各狀態(tài)間的轉移關系：狀態(tài)0轉移到狀態(tài)1的轉移率為，狀態(tài)1轉移到狀態(tài)0的轉移率為。3.1標準的M/M/1模型(M/M/1/∞/∞)這種系統狀態(tài)(n)隨時間變化的過程就是生滅過程〔BirthandDeathProcess〕。方程(12-15)、(12-16)解是瞬態(tài)解，無法應用。743.1標準的M/M/1模型(M/M/1/∞/∞)對狀態(tài)0必須滿足以下平衡方程同樣對任何的狀態(tài)，可得如(12-18)所示的平衡方程。由(12-17)式可得將它代入(12-18)式，令，得到同理依次推得今設(否那么隊列將排至無限遠)，又由概率的性質知將的關系代入，得到75對ρ的實際意義的解釋ρ＝λ/μ，是平均到達率與平均效勞率之比，即在相同時區(qū)內顧客到達的平均數與被效勞的平均數之比。假設將ρ表示為ρ＝(1/μ)/(1/λ)，它是一個顧客的效勞時間與到達間隔時間之比，稱ρ為效勞強度(trafficintensity)，或話務強度。由(12-19)式可知，ρ=1-P0，它刻畫了效勞機構的繁忙程度，所以ρ又稱為效勞機構的利用率。3.1標準的M/M/1模型(M/M/1/∞/∞)系統處于空閑狀態(tài)的概率：系統處于繁忙狀態(tài)的概率：76根據平穩(wěn)分布，求排隊系統的有關運行指標(1)系統中的平均顧客數〔平均隊長〕

或 (2)在隊列中等待的平均顧客數

3.1標準的M/M/1模型(M/M/1/∞/∞)期望77顧客在系統中的逗留時間W(為一個隨機變量)在M/M/1情形下，服從參數為

的負指數分布①，即

分布函數概率密度

于是，得到(3)在系統中顧客逗留時間的期望值

(4)在隊列中顧客等待時間的期望值

3.1標準的M/M/1模型(M/M/1/∞/∞)平均逗留時間減去平均效勞時間。78將以上結果歸納如下：

它們的相互關系如下：

上式稱為Little公式。3.1標準的M/M/1模型(M/M/1/∞/∞)793.1標準的M/M/1模型(M/M/1/∞/∞)Ls,Lq,λ

,Ws,Wq之間的關系：幾何解釋：穩(wěn)態(tài)時，一個顧客，進入系統后，每單位時間，平均到達λ顧客。

λλλλλ進入時刻離開時刻總時間Ws

隊長Ls由時間段內個λ組成的Ls=λWs同理：Lq=λWqWs=Wq+〔1/μ〕-------Ws與Wq只相差一段平均效勞時間1/μ

80例1：考慮一個鐵路列車編組站。設待編列車到達時間間隔服從負指數分布，平均每小時到達2列；效勞臺是編組站，編組時間服從負指數分布，平均每20分鐘可編一組。編組站上共有2股道，當均被占用時，不能接車，再來的列車只能停在站外或前方站。求在平衡狀態(tài)下系統中列車的平均數；每一列車的平均逗留時間；等待編組的列車平均數。如果列車因站中2股道均被占用而停在站外或前方站時，每列車每小時費用為a元，求每天由于列車在站外等待而造成的損失。3.1標準的M/M/1模型(M/M/1/∞/∞)81解：本例可看成一個M/M/1/排隊問題，其中=2，=3，=/=2/3<1系統中列車的平均數L=/(1-)=(2/3)/(1-2/3)=2〔列〕列車在系統中的平均停留時間W=L/=2/2=1〔小時〕系統中等待編組的列車平均數Lq=L-=2-2/3=4/3〔列〕列車在系統中的平均等待編組時間Wq=Lq/=(4/3)/(1/2)=2/3〔小時〕3.1標準的M/M/1模型(M/M/1/∞/∞)82記列車平均延誤〔由于站內2股道均被占用而不能進站〕時間為W0那么W0=WP{N>2}=W{1-P0-P1-P2}=W{1-(l-)-(l-)1-(l-)2}=1*3=3=(2/3)3=0.296〔小時〕故每天列車由于等待而支出的平均費用E=24W0a=24*2*0.296*a=14.2a元3.1標準的M/M/1模型(M/M/1/∞/∞)83例2：某修理店只有一位修理工，來修理的顧客到達過程為Poisson流，平均每小時4人；修理時間服從負指數分布，平均需要6分鐘。試求：修理店空閑的概率；店內恰有3位顧客的概率；店內至少有一位顧客的概率；在店內平均顧客數；每位在店內平均逗留時間；等待效勞的平均顧客數；每位顧客平均等待效勞時間；顧客在店內等待時間超過10分鐘的概率。3.1標準的M/M/1模型(M/M/1/∞/∞)84解：本例可看成一個M/M/1/排隊問題，其中=4，=1/0.1=10(人/小時〕，=/=2/5<1修理店內空閑的概率P0=1-=(1-2/5)=0.6店內恰有3個顧客的概率P3=3(1-)=(2/5)3(1-2/5)=0.0383.1標準的M/M/1模型(M/M/1/∞/∞)85店內至少有1位顧客的概率P{N1}=1-P0=1-(1-)==2/5=0.4在店內平均顧客數L=/(1-)=(2/5)/(1-2/5)=0.67(人〕每位顧客在店內平均逗留時間W=L/=0.67/4=10分鐘3.1標準的M/M/1模型(M/M/1/∞/∞)86等待效勞的平均顧客數Lq=L-=0.67-2/5=0.27(人)每個顧客平均等待效勞時間Wq=Lq/=0.27/4=0.0675小時=4分鐘3.1標準的M/M/1模型(M/M/1/∞/∞)87顧客在店內等待時間超過10分鐘的概率P{T>10}=e-10(1/6-1/15)=e-1=0.3677P{T>t}=e-(

-

)tt=10分鐘,

=10人/小時=10/60=1/6=4人/小時=4/60=1/153.1標準的M/M/1模型(M/M/1/∞/∞)88例3某醫(yī)院手術室根據病人來診和完成手術時間的記錄，任意抽查了100個工作小時，每小時來就診的病人數n的出現次數如下表所示；又任意抽查了100個完成手術的病歷，所用時間v(單位：小時)出現的次數如下表所示。到達的病人數n出現人數0101282316410566以上1合計100為病人完成手術時間v(小時)出現人數0.0~0.2380.2~0.4250.4~0.6170.6~0.890.8~1.061.0~1.251.2以上0合計1003.1標準的M/M/1模型(M/M/1/∞/∞)89(1)每小時病人平均到達率(人/小時)每次手術平均時間(小時/人)每小時完成手術人數(平均效勞率)(人/小時)(2)取，，可以通過統計檢驗的方法，認為病人到達數服從參數為2.1的泊松分布，手術時間服從參數為2.5的負指數分布。(3)說明效勞機構(手術室)有84%的時間是繁忙的，有16%的時間是空閑的。(4)依次代入(12-21)式，算出各指標：在病房中病人數(期望值) (人)排隊等待病人數(期望值) (人)病人在病房中逗留時間(期望值) (小時)病人排隊等待時間(期望值) (小時)3.1標準的M/M/1模型(M/M/1/∞/∞)90如果系統的最大容量為N，對于單效勞臺的情形，排隊等待的顧客最多為N-1，在某時刻一顧客到達時，如系統中已有N個顧客，那么這個顧客就被拒絕進入系統。當N=1時為即時制的情形；當N→∞時為容量無限制的情形。3.2系統的容量有限制的情況(M/M/1/N/∞)91泊松輸入—負指數分布效勞的排隊系統的一般決策過程：①根據條件繪制狀態(tài)轉移速度圖；②依據狀態(tài)轉移速度圖寫出各穩(wěn)態(tài)概率之間的關系；③求出P0及Pn；④計算各項數量運行指標；⑤用系統運行指標構造目標函數，對系統進行優(yōu)化。3.2系統的容量有限制的情況(M/M/1/N/∞)923.2系統的容量有限制的情況(M/M/1/N/∞)穩(wěn)態(tài)情形下各狀態(tài)間概率強度的轉換關系圖狀態(tài)概率的穩(wěn)態(tài)方程

∴933.2系統的容量有限制的情況(M/M/1/N/∞)穩(wěn)態(tài)情形下各狀態(tài)間概率強度的轉換關系圖狀態(tài)概率的穩(wěn)態(tài)方程其中(12-23a)也可寫成，那么有943.2系統的容量有限制的情況(M/M/1/N/∞)

由

N∑(λ/μ)nP0=1n=0

NP0=1/[∑(λ/μ)n]=

n=0(1-λ/μ)/

[(1-(λ/μ)N+1]λ

μ

1/(N+1)λ=μ

Pn=1/(N+1)λ=μ

(1-λ/μ)(λ/μ)n/[(1-(λ/μ)N+1]λ

μ

95M/M/1/N/∞排隊系統的各項指標：(1)隊長(期望值)(2)隊列長(期望值)(3)顧客逗留時間(期望值)(4)顧客等待時間(期望值)(5)有效到達率3.2系統的容量有限制的情況(M/M/1/N/∞)令，得到96(ρ≠1,n≤N)∴(1)平均隊長Ls：(ρ≠1)試證ρ=1時,Ls=N/23.2系統的容量有限制的情況(M/M/1/N/∞)97

???M/M/1/N/∞排隊系統的各項指標：(1)隊長(期望值)(2)隊列長(期望值)(3)顧客逗留時間(期望值)(4)顧客等待時間(期望值)(5)有效到達率3.2系統的容量有限制的情況(M/M/1/N/∞)令，得到返回P9898(2)有效到達率λe系統容量有限，當滿員〔n=N〕時，顧客將被拒絕，實際的顧客到達率與λ不一樣，還可驗證：∴此種情況的公式與前類似,只有Ls不同,λe與λ不同。求λe必須先求得P0或PN才行。有效到達率為λe

可以證明：Ls3.2系統的容量有限制的情況(M/M/1/N/∞)99M/M/1/N/∞排隊系統各項指標的歸納(當時)：3.2系統的容量有限制的情況(M/M/1/N/∞)100例2．某單人理發(fā)館共有六把椅子接待顧客排隊，無座時將離去，顧客平均到達率為3人/h，理發(fā)時間平均為15分鐘，求：(1)求某一顧客到達就能理發(fā)的概率;(2)求需要等待的顧客數的期望值;(3)求有效到達率;(4)求一顧客在系統中的逗留時間和排隊時間平均值;(5)在可能到來的顧客中，有百分之幾不等待就離開？3.2系統的容量有限制的情況(M/M/1/N/∞)101(1)求某一顧客到達就能理發(fā)的概率:(2)求需要等待的顧客數的期望值:(3)求有效到達率:(4)求一顧客在系統中的逗留時間和排隊時間平均值:3.2系統的容量有限制的情況(M/M/1/N/∞)102P0=0.27780P1=0.20836P2=0.15627P3=0.11720=0.9629=96.29%1-0.9629=3.71%

P4=0.08790P5=0.06593P6=0.04944(5)在可能到來的顧客中，有百分之幾不等待就離開？顧客為何不等待就離去？因為系統已經滿員3.2系統的容量有限制的情況(M/M/1/N/∞)故拒絕的概率為3.71%103例4某單人理發(fā)館為等待的顧客準備了6把椅子，當6把椅子都坐滿時，再來的顧客將不進店而離開。顧客的平均到達率為3人/小時，理發(fā)平均需要15分鐘。那么系統的容量為N=6+1=7，人/小時，人/小時。(1)某顧客一到達就能理發(fā)的概率(2)需要等待的顧客數的期望值 (3)有效到達率(人/小時)(4)一顧客在理發(fā)館內逗留的期望時間(小時)(分鐘)3.2系統的容量有限制的情況(M/M/1/N/∞)104(5)在可能到來的顧客中不等待就離開的概率這也是理發(fā)館的損失率。人/小時人/小時有限隊長2.111.390.730.480.2783.7無限隊長32.251.00.750.250以本例為例，比較隊長為有限和無限的情形：3.2系統的容量有限制的情況(M/M/1/N/∞)105背景設有m臺機器(顧客總體)，機器因故障停機表示“到達”，待修的機器形成隊列，修理工人是效勞員，本節(jié)討論單效勞員的情形。顧客總體雖只有m個，但每個顧客到來并經過效勞后，仍回到原來總體，所以仍然可以再到來。如在機器故障問題中，同一臺機器出了故障(到來)并經修好(效勞完了)仍可再出故障，形成循環(huán)。模型符號中的∞表示對系統的容量沒有限制，但實際上它不會超過m，所以可寫成(M/M/1/m/m)。3.3顧客源為有限的情形(M/M/1/∞/m)106設每個顧客的到達率相同，均為λ(這里λ的含義是單臺機器在單位時間里發(fā)生故障的概率或平均次數)；設系統內顧客數為Ls，那么系統外的顧客平均數為mLs，所以系統的有效到達率為λe=λ(mLs)(12-26)考慮穩(wěn)態(tài)情況下狀態(tài)間的轉移率由狀態(tài)0轉移到狀態(tài)1：每臺設備由正常狀態(tài)轉移為故障狀態(tài)的轉移率為λP0，m臺設備由無故障狀態(tài)轉移為有一臺設備(不管哪一臺)發(fā)生故障的轉移率為mλP0。由狀態(tài)1轉移到狀態(tài)0：其狀態(tài)轉移率為μP1。所以，狀態(tài)0時有平衡方程為：mλP0=μP13.3顧客源為有限的情形(M/M/1/∞/m)107各狀態(tài)間的轉移差分方程解得(注意到因而不要求〕系統的各項指標為3.3顧客源為有限的情形(M/M/1/∞/m)108例5某車間有5臺機器，每臺機器的連續(xù)運轉時間服從負指數分布，平均連續(xù)運轉時間15分鐘，有一個修理工，每次修理時間服從負指數分布，平均每次12分鐘。求：(1)修理工空閑的概率；(2)五臺機器都出故障的概率；(3)出故障的平均臺數；(4)等待修理的平均臺數；(5)平均停工時間；(6)平均等待修理時間；(7)評價這些結果。3.3顧客源為有限的情形(M/M/1/∞/m)109解：(1)(2)五臺機器都出現故障的概率(3)出故障的平均臺數(臺)(4)等待修理的平均臺數(臺)(5)平均停工時間(分鐘)(6)平均等待修理時間(分鐘)(7)機器停工時間過長，修理工幾乎沒有空閑時間，應當提高效勞率減少修理時間或增加修理工人。3.3顧客源為有限的情形(M/M/1/∞/m)110第1節(jié)根本概念第2節(jié)到達間隔的分布和效勞時間的分布第3節(jié)單效勞臺負指數分布排隊系統的分析第4節(jié)多效勞臺負指數分布排隊系統的分析第5節(jié)一般效勞時間M/G/1模型第6節(jié)經濟分析——系統的最優(yōu)化第7節(jié)分析排隊系統的隨機模擬法排隊論

111本節(jié)討論單隊、并列的多效勞臺〔效勞臺數為c〕的情形。4.1標準的M/M/c模型4.2M/M/c型系統和c個M/M/1型系統的比較4.3系統容量有限的情形〔M/M/c/N/〕4.4顧客源有限的情形〔M/M/c//m〕第4節(jié)多效勞臺負指數分布排隊系統的分析1124.1標準的M/M/c模型標準的M/M/c模型各種特征的規(guī)定與標準的M/M/1模型的規(guī)定相同。各效勞臺工作是相互獨立的(不搞協作)，且平均效勞率相同。整個效勞機構的平均效勞率為(當)；為(當)。令，只有當時才不會排成無限的隊列稱為系統的效勞強度或效勞機構的平均利用率。1134.1標準的M/M/c模型M/M/c排隊系統的狀態(tài)概率分布狀態(tài)1轉移到狀態(tài)0：即系統中有一名顧客被效勞完了(離去)的轉移率為。狀態(tài)2轉移到狀態(tài)1：兩個效勞臺上被效勞的顧客中有一個被效勞完成而離去。因為不限哪一個，于是狀態(tài)的轉移率為。狀態(tài)n轉移到n-1：當時，狀態(tài)轉移率為；當時，因為只有c個效勞臺，最多有c個顧客在被效勞，個顧客在等候，因此這時狀態(tài)轉移率應為。1144.1標準的M/M/c模型由圖12-13可得這里，且用遞推法解上述差分方程，可求得狀態(tài)概率。1154.1標準的M/M/c模型系統的運行指標為：平均隊長平均等待時間和逗留時間可由Little公式求得，1164.1標準的M/M/c模型例6某售票處有三個窗口，顧客的到達服從泊松過程，平均到達率每分鐘(人)，效勞(售票)時間服從負指數分布，平均效勞率每分鐘人?，F設顧客到達后排成一隊，依次向空閑的窗口購票如圖12-14(a)，這就是一個M/M/c型的系統，其中，，符合要求的條件，代入公式得：0312λλλλμ3μ2μ3μ4λ3μ1174.1標準的M/M/c模型(1)整個售票處空閑概率(2)平均隊長(3)平均等待時間和逗留時間 (分鐘) (分鐘)顧客到達后必須等待(即系統中顧客數已有3人即各效勞臺都沒有空閑)的概率 118例6.某火車站售票處有三個窗口，同時售各車次的車票。顧客到達服從泊松分布，平均每分鐘到達λ=0.9〔人〕，效勞時間服從負指數分布，平均效勞率μ=24〔人/h〕，分兩種情況：1.顧客排成一隊，依次購票；(M/M/3/∞/∞)2.顧客在每個窗口排一隊，不準串隊。(M/M/1/∞/∞三個系統并聯)求:〔1〕售票處空閑的概率?！?〕平均等待時間和逗留時間?！?〕隊長和隊列長。4.2M/M/c型系統和c個M/M/1型系統的比較1194.2M/M/c型系統和c個M/M/1型系統的比較現就例6說明，如果原題除排隊方式外其他條件不變，但顧客到達后在每個窗口前各排一隊，且進入隊列后堅持不換，這就形成3個隊列，見圖12-14(b)而每個隊列平均到達率為 (每分鐘)這樣，原來的系統就變成3個M/M/1型的子系統。μ=0.4,ρ=λ/μ=0.75,P0=1-ρ=0.251204.2M/M/c型系統和c個M/M/1型系統的比較現就例6說明，如果原題除排隊方式外其他條件不變，但顧客到達后在每個窗口前各排一隊，且進入隊列后堅持不換，這就形成3個隊列，見圖12-14(b)而每個隊列平均到達率為(每分鐘)這樣，原來的系統就變成3個M/M/1型的子系統?，F按M/M/1型解決這個問題，并與上面結果比較如下：模型指標(1)M/M/3型(2)M/M/1型服務臺空閑的概率P00.07480.25(每個子系統)顧客必須等待的概率P(n≥3)=0.570.75平均隊列長Lq

1.702.25(每個子系統)平均隊長Ls3.959.00(整個系統)平均逗留時間Ws(分鐘)4.3910平均等待時間Wq(分鐘)1.897.5從表中各指標的比照可以看出：單隊比三隊有顯著優(yōu)越性。作業(yè)?。。?214.3系統的容量有限制的情形〔M/M/c/N/〕設系統的容量最大限制為，當系統中顧客數n已到達N(即隊列中顧客數已達N-c)時，再來的顧客即被拒絕，其他條件與標準的M/M/c型相同。這時系統的狀態(tài)概率和運行指標如下： 其中，但現在已不必對加以限制。0N-112N-2λλλλμcμ2μcμNCC-1λλcμcμC+13μλ(c-1)μλcμcμλλ1224.3系統的容量有限制的情形〔M/M/c/N/〕特別當(即時制)時當即關于的公式被稱為愛爾朗損失公式。例如，停車場就不允許排隊等待空位的情形！1234.3系統的容量有限制的情形〔M/M/c/N/〕這時的運行指標如下：

1244.3系統的容量有限制的情形〔M/M/c/N/〕例7

在某風景區(qū)準備建造旅館，顧客到達為泊松流，每天平均到(=)6人，顧客平均逗留時間()為2天，試就該旅館在具有(c)1，2，3，…，8個房間的條件下，分別計算每天客房平均占用數及滿員概率。這是即時式，因為在客房滿員條件下，旅客顯然不能排隊等待。計算過程通過表12-12進行()。125(2)(3)n!(7)(5)4.3系統的容量有限制的情形〔M/M/c/N/〕6.930.580.422.52×1051.07×1044.03×1044.30×10886.140.510.491.45×1047.11×1035.04×1033.58×10775.330.440.567.46×1034.15×1037202.99×10664.480.370.633.31×1032.07×1031202.49×10553.620.300.701.24×103864242.07×10442.740.230.7737328861.73×10331.830.150.85857221.44×10220.920.080.92131211.2×101——111110(8)Ls(答)(4)(1)n第(4)欄＝(2)/(3)第(5)欄：第(4)欄各數累加(4)/(5)得滿員概率用第(5)欄同行去除上一行結果(7)×12得，為每天客房平均占用數(6)Pc

(答)1264.4顧客源為有限的情形〔M/M/c//m〕設顧客總體(顧客源)為有限數m，且m＞c，顧客到達率λ是按每個顧客來考慮的。在機器管理問題中，就是共有m臺機器，有c個修理工人，顧客到達就是機器出了故障每個顧客的到達率λ是指每臺機器每單位運轉時間出故障的期望次數系統中顧客數n就是出故障的機器臺數當n≤c時，所有的故障機器都在被修理，有(c-n)個修理工人在空閑當c＜n≤m時，有(n-c)臺機器在停機等待修理，而修理工人都在繁忙狀態(tài)假定這c個工人修理技術相同，修理(效勞)時間都服從參數為μ的負指數分布，并假定故障的修復時間和正在生產的機器是否發(fā)生故障是相互獨立的。1274.4顧客源為有限的情形〔M/M/c//m〕(1)其中 (2)平均顧客數(即平均故障臺數)1284.4顧客源為有限的情形〔M/M/c//m〕有效的到達率應等于每個顧客的到達率乘以在系統外(即正常生產的)機器的期望數： 在機器故障問題中，它是每單位時間m臺機器平均出現故障的次數。(3)可以證明

1294.4顧客源為有限的情形〔M/M/c//m〕例8設有兩個修理工人，負責5臺機器的正常運行，每臺機器平均損壞率為每運轉小時1次，兩工人能以相同的平均修復率4(次/小時)修好機器。求：①等待修理的機器平均數；②需要修理的機器平均數；③有效損壞率；④等待修理時間；⑤停工時間。解：(次/小時)，(臺/小時)，1304.4顧客源為有限的情形〔M/M/c//m〕①②

③④(小時)⑤(小時)131排隊論

第1節(jié)根本概念第2節(jié)到達間隔的分布和時間的分布第3節(jié)單效勞臺負指數分布排隊系統的分析第4節(jié)多效勞臺負指數分布排隊系統的分析第5節(jié)一般效勞時間M/G/1模型第6節(jié)經濟分析——系統的最優(yōu)化第7節(jié)分析排隊系統的隨機模擬法132第5節(jié)一般效勞時間M/G/1模型對任何情形，下面關系都是正確的：E［系統中顧客數］=E［隊列中顧客數］+E［效勞機構中顧客數］E［在系統中逗留時間］=E［排隊等候時間］+E［效勞時間］其中表示求期望值，用符號表示就是：其中T表示效勞時間(隨機變量)，當T服從負指數分布時，。而(12-22)式中的關系式： 也是常被利用的。所以上面的7個數中只要知道3個就可求出其余，不過在有限源和隊長有限制情況下，要換成有效到達率。1335.1Pollaczek-Khintchine(P-K)公式5.2定長效勞時間M/D/1模型5.3愛爾朗效勞時間M/Ek/1模型第5節(jié)一般效勞時間M/G/1模型134對于M/G/1模型，效勞時間T服從一般分布，(但要求期望值和方差存在)，其他條件和M/M/1型相同。為到達穩(wěn)態(tài)，還是必要的，其中。在上述條件下，有

這就是波拉切克-欣欽Pollaczek-Khintchine(P-K)公式。只要知道，和，不管T是什么分布，就可求出，然后通過(12-37)式和(12-22)式可求出