高級運籌學-排隊論

1、Queuing Theory排隊論 第四章Where the Time Goes美國人一生中平均要花費- 6年 吃5年 排隊等待4年 做家務2年 回電話不成功 1年 尋找放置不當?shù)奈锲?個月 打開郵寄廣告6個月 停在紅燈前排隊經濟時隔10年重回國人生活 銀行排隊排隊時間：40分鐘 2007年某日，記者來到新街口招商銀行營業(yè)大廳，取了排隊號碼紙：631號。此時，剛剛排到484號，排在記者前的還有147個人。 AC尼爾森公司的調查在消費者經常遭遇排隊問題的各類場所銀行的排隊率是73%；醫(yī)院以44%居第二；零售商店的排隊率以43%居第三。在調查受訪的消費者中，超過60%的受訪者稱通常一周用于排隊的時

2、間高于30分鐘。在所有受訪的消費者中，有28%的人因排長隊而轉選其它服務提供商，66%的人因不想耽誤時間而選擇離開，而46%的人會有抱怨。 行為科學家發(fā)現(xiàn)：無序排隊是影響客戶流失的一條主要原因。研究結果表明等候時間：超過十分鐘，情緒開始急躁；超過二十分鐘，情緒表現(xiàn)厭煩；超過四十分鐘，常因惱火而離去。如何減少排隊？減少等候時間的解決方案 ：開設更多的服務點；提供自助服務解決方案；雇用更多員工。排隊管理系統(tǒng)的應用 近兩年，許多公共服務場所出現(xiàn)了排隊機(ticket dispenser unit) ，窗口秩序為之一變，一種令人耳目一新的排隊方式：進得大門，在排隊機的觸摸屏上點一下所要辦理的項目，排隊

3、機就會“吐”出一張像名片大小的號票，拿著這張?zhí)柶卑舶察o靜地坐在休息區(qū)舒適的椅子上等候，輪到自己時，大屏幕和語音系統(tǒng)會提醒你到相應的窗口辦理，井然有序。 DisneyPariss EuroDisney, Tokyos Disney Japan, and the U.S.s Disney World and Disneyland all have one feature in commonlong lines and seemingly endless waits。在游樂園中的頻頻排隊會極為掃興However, Disney is one of the worlds leading compani

4、es in the scientific analysis of queuing theory。It analyzes queuing behaviors and can predict which rides will draw what length crowds。To keep visitors happy, Disney makes lines appear to be constantly moving forward, entertains people while they wait, and posts signs telling visitors how many minut

5、es until they reach each ride。Disney在佛羅里達州Orlando的DisneyLand里,游客們依著繩子排成許多隊，指示牌可以估計出等待的時間，而許多大的電視屏幕為游客們提供消遣。DisneyLand中的FastPass系統(tǒng)就是想解決排隊問題DisneyWhat is FastPass?工作原理：到達的顧客將自己的票插入FastPass的slot中FastPass計算出建議顧客返回的時間間隔（time interval）或時間點或時間窗（time window）顧客無需排隊，在指定的時間返回就可持票進入 如何計算顧客等待時間？服務系統(tǒng)的構成排隊現(xiàn)象抽象成服務系

6、統(tǒng)，它有顧客、服務機構、隊列和服務規(guī)則等組成典型的服務系統(tǒng)Three Parts of a Queuing System at Daves Car-Wash排隊系統(tǒng)的基本特征離開排隊規(guī)則到達過程排隊結構服務過程退出需求群體什么是排隊論排隊論是研究服務系統(tǒng)中排隊現(xiàn)象隨機規(guī)律的理論與方法 因為排隊現(xiàn)象是一個隨機現(xiàn)象，因此在研究排隊現(xiàn)象的時候，主要采用的是研究隨機現(xiàn)象的概率論作為主要工具。此外，還有微分和微分方程。排隊論研究目的和內容減少顧客等待時間計算顧客平均等待時間計算顧客的平均隊長提高服務系統(tǒng)的效率計算服務強度計算忙期閑期對服務系統(tǒng)進行成本效益平衡分析增加服務臺的成本與效益分析排隊論發(fā)展簡述1

7、909年丹麥數(shù)學家A.K.Erlang(愛爾朗)服務于一家電話公司，他在解決自動電話設計問題時開始形成的，當時稱為話務理論。他在熱力學統(tǒng)計平衡理論的啟發(fā)下，成功地建立了電話統(tǒng)計平衡模型，并由此得到一組遞推狀態(tài)方程，從而導出著名的愛爾朗電話損失率公式。上世紀30年代蘇聯(lián)數(shù)學家.辛欽把處于統(tǒng)計平衡的電話呼叫流稱為最簡單流。 上世紀50年代，美國數(shù)學家關于生滅過程的研究、英國人D.G. Kendall提出嵌入馬爾可夫鏈理論，以及對排隊隊型的分類方法，為排隊論奠定了理論基礎；上世紀60年代更多的應用于生產線，交通等問題；上世紀70年代應用于計算機網絡、通信等領域；如今通信系統(tǒng)仍然是排隊論應用的主要領域

8、,同時在運輸、港口泊位設計、機器維修、庫存控制等領域得到廣泛應用，特別是服務行業(yè)。排隊論發(fā)展簡述本章大綱4.1 排隊服務系統(tǒng)的基本概念4.2 輸入與服務時間的分布4.3 生滅過程4.4 幾種不同類型排隊系統(tǒng)分析標準M/M/1/有限隊列模型 M/M/1/N/顧客為有限源系統(tǒng)M/M/1/m多服務臺系統(tǒng)M/M/s4.5 排隊系統(tǒng)的優(yōu)化4.1 排隊服務系統(tǒng)的基本概念4.1.1 排隊系統(tǒng)的一般表示一個排隊系統(tǒng)可以抽象描述為：為了獲得服務的顧客到達服務設施前排隊，等候接受服務，服務完畢后就自行離開。要求得到服務的對象稱為顧客服務者稱為服務設施或服務臺顧客的到達和離開稱為排隊系統(tǒng)的輸入和輸出。顧客的總體稱為

9、顧客源或輸入源。因此，任何一個排隊系統(tǒng)是一種輸入-輸出系統(tǒng)。排隊系統(tǒng)基本結構顧客源等候隊列服務設施到達輸入輸出離開排隊系統(tǒng)4.1 排隊服務系統(tǒng)的基本概念商業(yè)服務系統(tǒng)系統(tǒng)類型顧客服務臺理發(fā)店人理發(fā)師銀行出納服務人出納ATM機服務人ATM機商店收銀臺人收銀員電影院售票窗口人售票員機場檢票處人航空公司代理人內部服務系統(tǒng)系統(tǒng)類型顧客服務臺秘書服務雇員秘書急救中心病員護士傳真服務雇員傳真機物料處理系統(tǒng)貨物物料處理單元維護系統(tǒng)設備維修工人質檢站物件質檢員運輸服務系統(tǒng)系統(tǒng)類型顧客服務臺公路收費站汽車收費員卡車裝貨地卡車裝貨工人港口卸貨區(qū)輪船卸貨工人等待起飛的飛機飛機跑道航班服務人飛機出租車服務人出租車電梯服

10、務人電梯消防部門火災消防車停車場汽車停車空間急救車服務人急救車排隊系統(tǒng)的三個基本組成部分：輸入過程 (顧客按照怎樣的規(guī)律到達)；排隊規(guī)則 (顧客按照一定規(guī)則排隊等待服務)；服務機構 (服務機構的設置,服務臺的數(shù)量,服務的方式,服務時間分布等)4.1.2 排隊系統(tǒng)的組成一、輸入 Arrival Characteristics顧客源是有限集還是無限集（Size of the arrival population）工廠內待修的機器數(shù)是有限集，售票處購票顧客源可認為是無限集。顧客到達系統(tǒng)的方式是單個的，還是成批的（Behavior of arrivals）如到達賓館服務臺住宿有散客，也有團體相繼到達系

11、統(tǒng)的時間間隔是確定性的還是隨機性的（Pattern of arrival at the system）如自動裝配線上待裝配部件到達各工序的時間間隔是確定的。而多數(shù)顧客到達都是隨機的，隨機的服從何種概率分布：二項、負指數(shù)、愛爾朗分布等。到達過程(輸入過程)的內容顧客總體數(shù)或顧客源數(shù)有限或無限顧客的到達類型單個或成批顧客的到達間隔時間間隔時間分布二、排隊規(guī)則 Queue Discipline顧客來到排隊系統(tǒng)后如何排隊等候服務的規(guī)則1、即時制（損失制）：當顧客到達時，如果所有服務臺都已被占用，顧客可以隨即離開系統(tǒng)；如電話撥號后出現(xiàn)忙音，顧客可馬上掛上電話。2、等候制：當顧客到達時，所有服務臺都已被占

12、用，顧客就加入排隊隊列等候服務。排隊規(guī)則：FIFO /FCFS 先到先服務，最常見LIFO：乘電梯的顧客是后進先出SIRO隨機服務：從等待的顧客中隨機取一個進行服務，人工電話交換優(yōu)先權服務：重病優(yōu)先、老年人優(yōu)先等3、混合制：即時制和等候制相結合的一種排隊服務規(guī)則。隊列長度有限制時：排隊等候的人數(shù)超過預定數(shù)量，后來的顧客就自動離開。旅館的客房等排隊時間有限制時：顧客排隊等候超過一定的時間就會自動離開，不能再等；電子元器件庫存超過一定時期，就失效了二、排隊服務規(guī)則 Queue Discipline三、服務機構服務設施的結構、服務方式、服務時間：按服務設施個數(shù)分，有一個或多個之分，有并聯(lián)和串聯(lián)之分單

13、臺服務系統(tǒng)和多臺服務系統(tǒng)服務方式有單個服務和成批服務服務時間是確定和隨機的服務臺結構等候隊列服務臺單服務臺等候隊列服務臺2服務臺1并列多臺等候隊列服務臺1串列多臺服務臺2等候隊列服務臺3服務臺1混列多臺服務臺4服務臺2 服務的方式是對單個顧客進行的，還是對成批顧客進行的。公共汽車站臺等待的顧客是成批進行服務的。服務方式服務時間對顧客的服務時間是確定的還是隨機的。自動沖洗汽車的裝置對每輛汽車沖洗服務的時間是確定性的。但大多數(shù)情況下服務時間是隨機性的。對于隨機要知道它的概率分布，是定長、負指數(shù)還是愛爾朗分布。Service time distribution排隊結構-例多隊多服務臺領號 34826

14、101211579單隊多服務臺入口 4.1.3 排隊系統(tǒng)模型的分類按照排隊系統(tǒng)的輸入、排隊規(guī)則和服務機構等方面的不同，可以構成不同的排隊模型4.2 輸入與服務時間的分布 Distribution of Input and service time組成一個排隊系統(tǒng)的四要素輸入輸出排隊服務規(guī)則服務機構顧客的輸入和輸出較復雜，是隨機的研究較多且結果較好的排隊系統(tǒng)是：顧客的輸入過程服從泊松分布，而服務時間服從負指數(shù)分布的排隊系統(tǒng)若顧客輸入過程服從泊松分布，則顧客相繼到達的間隔時間服從負指數(shù)分布。 4.2.1 Poisson流（Poisson過程） 定義：滿足以下條件的輸入流稱為Poisson流（最簡單

15、流、Poisson過程）1、無后效性：不相交的時間區(qū)間內到達的顧客數(shù)互相獨立。2、平穩(wěn)性：對充分小的t，在時間區(qū)間t, t+t)內到達1個顧客的概率與t無關，只與t有關:其中：l是一個大于零的常數(shù)，表示單位時間內到達一個顧客的概率 3、守序性：設在t, t+t）內到達多于一個顧客的概率為極小o(t)。實際情況是否符合三條性質到達工廠機修車間的要維修的機器情況分析：因為每臺機器在各個時刻處的狀態(tài)大致一樣，所以在相等時間區(qū)間內各臺機器損壞的概率大致相同，即要求維修的機器的流具有平穩(wěn)性由于一臺機器的故障不會引起另一臺機器的故障，而對同一臺機器，這段時間內損壞的次數(shù)不影響到以后損壞次數(shù)多少，這表明具有

16、無后效性由于每臺機器損壞概率很小，在足夠小的時間區(qū)間內發(fā)生兩臺及以上機器損壞的概率幾乎為0，這就符合普通性。因此對到達機修車間的要維修的機器數(shù)可以認為是最簡單流,即poisson流。Poisson流與Poisson分布定理1 對于一個參數(shù)為的Poisson流，在0，t內到達n個顧客的概率為即服從以為參數(shù)的Poisson分布。 Poisson Distributions for Arrival TimesProbabilityProbability=2=4：單位時間顧客的平均到達率Poisson流與負指數(shù)分布之間的關系 定理2 在排隊系統(tǒng)中，如果單位時間內顧客到達數(shù)服從以為參數(shù)的Poisson分

17、布，則顧客相繼到達的時間間隔服從以為參數(shù)的負指數(shù)分布。 l=0.41/為平均到達間隔時間（expected interarrival time)負指數(shù)分布Negative Exponential Distribution 分布函數(shù) 負指數(shù)分布無后效性無后效性表示T顧客到達的時間間隔已經過了s后，再等t的時間與s無關。.4.2.2 服務時間的分布在排隊系統(tǒng)中，一般假設服務時間（service time) 服從參數(shù)為m的負指數(shù)分布：1/m為平均服務時間（expected service time)平均服務時間Mean service time = 1/分布函數(shù)4.2.2 服務時間的分布服務時間負指

18、數(shù)分布的性質假如服務設施對每個顧客的服務時間服從負指數(shù)分布，則對每個顧客的平均服務時間為1/m當服務設施對顧客的服務時間 t為參數(shù) m 的負指數(shù)分布時 ，則有在t, t+t 時間內，沒有顧客離去的概率為 1- mt在t, t+t 時間內，恰有一個顧客離去的概率為mt如果t足夠小，在t, t+t 時間內有多于兩個以上顧客 離去的概率趨于0若按依次到達的間隔時間統(tǒng)計，顧客流服從負指數(shù)分布，則對同一顧客流若按單位時間到達的數(shù)量統(tǒng)計，它服從泊松分布。泊松分布和負指數(shù)分布是對同一顧客流按不同方式進行統(tǒng)計時得到的兩種不同分布。服務時間負指數(shù)分布的性質4.2.3 k階Erlang分布 K個相互獨立的且具有相

19、同參數(shù)的負指數(shù)分布的隨機變量的和，其分布稱為k階Erlang分布。例如一臺自動機床上依次利用三把刀具對一個工件進行加工，若每把刀具對該工件的加工時間均為參數(shù) 相同 的負指數(shù)分布，則該工件在自動機床上總的加工時間服從3階Erlang分布愛爾朗分布比負指數(shù)分布具有更廣泛的適應性，k階愛爾朗分布（Ek)的概率密度函數(shù)為： 4.2.3 k階Erlang分布 Erlang分布的均值、方差和階數(shù)愛爾朗分布的均值和方差是由此可得愛爾朗分布的階數(shù)：m=1k=1k=2k=4k=8k階Erlang分布 定理3 設v1，v2，vk是k個互相獨立的，具有相同參數(shù)m的負指數(shù)分布的隨機變量，則隨機變量Ek=v1+v2+v

20、k服從k階Erlang分布，Ek的密度函數(shù)為均值、方差和階數(shù)總服務時間服從愛爾朗分布，其均值和方差是由此可得愛爾朗分布的階數(shù)：每個服務臺的平均服務時間是：排隊模型分類的Kendall符號 Kendall提出一個排隊系統(tǒng)的分類方法，特征可以用六個參數(shù)表示，形式為：XYZ其中X 顧客到達的概率分布，可取M、D、Ek、G等；Y 服務時間的概率分布，可取M、D、Ek、G等；Z 服務臺個數(shù)，取正整數(shù)；4.2.4 排隊系統(tǒng)模型的分類X、Y可有四種分布符號M、D、Ek、GM負指數(shù)分布所描述的隨機現(xiàn)象對于過去的事件具有無記憶性或稱馬爾可夫性MarkovD定長分布，事件以不變的方式發(fā)生Deterministic

21、Ekk階愛爾朗分布ErlangG一般隨機分布General 如M/M/1表示到達的間隔時間服從負指數(shù)分布，服務時間也服從負指數(shù)分布的單服務臺排隊系統(tǒng)模型M/D/2 表示到達的間隔時間服從負指數(shù)分布，服務時間為定長分布的雙服務臺排隊系統(tǒng)模型4.2.4 排隊系統(tǒng)模型的分類4.2.4 排隊系統(tǒng)模型的分類1971年又將Kendall符號擴展為： XYZ / ABC其中：A 排隊系統(tǒng)的最大容量，可取正整數(shù)N或；B 顧客源的最大容量，可取正整數(shù)m或；C 排隊規(guī)則，可取FCFS、LCFS等。特別約定，如略去后三項，則是指 XYZ / FCFS因為本課程只介紹FCFS, 所以略去最后一項例M/M/1/FCFS

22、表示：顧客到達的時間間隔是負指數(shù)分布服務時間是負指數(shù)分布一個服務臺排隊系統(tǒng)和顧客源的容量都是無限實行先到先服務的一個服務系統(tǒng) 4.2.5 排隊系統(tǒng)的相關名詞術語一個排隊系統(tǒng)開始運行時,系統(tǒng)的運行狀態(tài)在很大程度上取決于系統(tǒng)的初始狀態(tài)和運轉的時間。經過一段時間以后，系統(tǒng)的狀態(tài)將獨立于初始狀態(tài)和經歷時間，這時系統(tǒng)處于穩(wěn)定狀態(tài)。排隊系統(tǒng)主要研究穩(wěn)定狀態(tài)。系統(tǒng)處于穩(wěn)定狀態(tài)時，工作狀況與時刻t無關。平均到達率n ：當系統(tǒng)中有n個顧客時，新來顧客的平均到達率（單位時間內顧客的到達數(shù)）。 當對所有n值n為常數(shù)時，可用代替n1/為相鄰兩顧客到達系統(tǒng)的平均間隔時間。平均服務率n ：當系統(tǒng)中有n個顧客時，單位時間內

23、被服務完畢后離開系統(tǒng)的平均顧客數(shù)。當對所有n值， n為常數(shù)時，可用代替n1/為每個顧客的平均服務時間。c系統(tǒng)中并列服務臺數(shù)目。主要名詞術語主要名詞術語N(t) 在時刻t排隊服務系統(tǒng)的顧客數(shù)，即系統(tǒng)在時刻t的瞬時狀態(tài)。Pn(t) 在t時刻系統(tǒng)中恰好有n個顧客的概率主要分析系統(tǒng)平穩(wěn)分布,即當系統(tǒng)達到統(tǒng)計平衡狀態(tài)時處于狀態(tài)n的概率,記為Pn主要系統(tǒng)性能指標平均逗留時間Ws ：進入系統(tǒng)的顧客逗留時間的平均值，包括接受服務的時間。平均等待時間Wq ：進入系統(tǒng)的顧客等待時間的平均值。服務機構工作強度 ：服務機構累計的工作時間占全部時間的比例 ，即服務強度 平均顧客數(shù)Ls ：一個排隊系統(tǒng)的顧客平均數(shù)，包括正

24、在接受服務的顧客。平均隊長Lq ：系統(tǒng)中等待服務的顧客平均數(shù)。常用的記號c 服務臺的個數(shù)n 系統(tǒng)中的顧客數(shù),即系統(tǒng)狀態(tài) 平均到達率，即單位時間內平均到達的顧客數(shù) 平均服務率，即單位時間內服務完畢的顧客數(shù)Pn(t) 時刻t系統(tǒng)狀態(tài)n 的概率Pn 系統(tǒng)中的顧客數(shù)n（系統(tǒng)狀態(tài)n)的穩(wěn)態(tài)概率M 顧客相繼到達的時間間隔服從負指數(shù)分布D 顧客相繼到達的時間間隔服從定長分布Ek 顧客相繼到達的時間間隔服從k階Erlang分布G 顧客相繼到達的時間間隔服從一般分布4.3 生滅過程排隊系統(tǒng)隨機聚散服務系統(tǒng)顧客到達是“生”，顧客離開是“滅”生滅過程Birth-death processN(t)是系統(tǒng)t時刻的狀態(tài)（

25、顧客數(shù)），則N(t),t=0就構成一個隨機過程，若用“生”表示一個顧客的到達，“滅”代表一個顧客過程的離去，則對許多排隊過程來說， N(t),t=0也是一類特殊的隨機過程生滅過程生滅過程Birth-death process定義：設N(t),t=0是一個隨機過程，如果其概率分布滿足有如下性質：（1）給定N(t)=n,到下一個“生”（顧客到達）的間隔時間服從參數(shù)為ln的負指數(shù)分布;（2）給定N(t)=n,到下一個“滅”（顧客離去）的間隔時間服從參數(shù)為mn的負指數(shù)分布;（3）同一時刻只能到達一個或離去一個顧客； 則稱N(t),t=0 是生滅過程當顧客到達時間服從參數(shù)為l 的負指數(shù)分布時，則有:在t

26、, t+t 時間內，沒有顧客到達的概率為 1- lt在t, t+t 時間內，恰有一個顧客到達的概率為lt如果t足夠小，在t, t+t 時間內有多于兩個以上顧客到達的概率趨于0當服務設施對顧客的服務時間服從參數(shù) m 的負指數(shù)分布時，則有:在t, t+t 時間內，沒有顧客離去的概率為 1- mt在t, t+t 時間內，恰有一個顧客離去的概率為mt如果t足夠小，在t, t+t 時間內有多于兩個以上顧客離去的概率趨于0 假設在t+t時刻系統(tǒng)中顧客數(shù)為n的概率Pn(t+t) nnn+1n-1nPn(t)Pn-1(t)Pn+1(t)Pn(t)t時刻t +t時刻無到達，無離開無到達，離開一個到達一個，無離開

27、到達一個，離開一個系統(tǒng)的過渡狀態(tài)與穩(wěn)定狀態(tài)過渡穩(wěn)定生滅過程的穩(wěn)定狀態(tài)方程生滅過程的瞬時狀態(tài)一般很難求得，但可求得穩(wěn)定狀態(tài)分布生滅過程的穩(wěn)定狀態(tài)轉移圖對于穩(wěn)定的生滅狀態(tài)，從平均意義上說有：“流入速率=流出速率”穩(wěn)定的生滅過程可以用狀態(tài)轉移圖表示生滅過程的穩(wěn)態(tài)方程基本原理系統(tǒng)任意狀態(tài)n達到穩(wěn)態(tài)平衡的條件是：產生該狀態(tài)的平均速率等于該狀態(tài)轉變成其他狀態(tài)的平均速率例如，對于系統(tǒng)狀態(tài)n=0的情況，產生和破壞該狀態(tài)的可能性有兩種情況。如后圖所示。n=0的狀態(tài)的產生和破壞n=1狀態(tài)的產生和破壞n=2狀態(tài)的產生和破壞狀態(tài)(n-1)的產生和破壞任意狀態(tài)n的產生和破壞生滅過程Birth-death process

28、012n-1nn+1生滅過程的基本公式生滅過程的狀態(tài)概率因為所以即得生滅過程Birth-death process標準的排隊過程是參數(shù)不隨狀態(tài)而變的特殊的生滅過程4.4 不同類型排隊系統(tǒng)分析輸入過程為泊松流，服務時間基本服從負指數(shù)分布的排隊系統(tǒng)標準M/M/1/有限隊列模型 M/M/1/N/顧客為有限源系統(tǒng)M/M/1/m多服務臺系統(tǒng)M/M/c 4.4.1標準排隊模型 M/M/1/FCFS 顧客到達的時間間隔是負指數(shù)分布服務時間是負指數(shù)分布一個服務臺排隊系統(tǒng)和顧客源的容量都是無限實行先到先服務的一個服務系統(tǒng)M/M/1的狀態(tài)轉移分析012n-1nn+1M/M/1排隊模型 標準的排隊過程是參數(shù)不隨狀態(tài)

29、而變的特殊的生滅過程得到 令稱為服務強度，則得例高速公路入口收費處設有一個收費通道，汽車到達服從Poisson分布，平均到達速率為100輛小時，收費時間服從負指數(shù)分布，平均收費時間為15秒輛。求1、收費處空閑的概率；2、收費處忙的概率；3、系統(tǒng)中分別有1，2，3輛車的概率。解根據(jù)題意, =100輛/小時,1/=15秒=1/240（小時/輛）,即240（輛/小時）。因此，=/=100/240=5/12。系統(tǒng)空閑的概率為：P0=1-=1-(5/12)=7/12=0.583系統(tǒng)忙的概率為：1-P0=1-(1-)=5/12=0.417系統(tǒng)中有1輛車的概率為：P1=(1-)=0.4170.583=0.2

30、43系統(tǒng)中有2輛車的概率為：P2=2(1-)=0.417 20.583=0.101系統(tǒng)中有3輛車的概率為：P3=3(1-)=0.417 30.583=0.0421系統(tǒng)績效度量 系統(tǒng)中的平均顧客數(shù)Ls Expected number of customers in system 平均等待顧客個數(shù)Lq（排隊長） Expected queue length (exclude customers being served) 顧客平均逗留時間Ws Waiting time in system 顧客平均（排隊）等待時間Wq Waiting time in queue (exclude service ti

31、me)M/M/1/FCFS的系統(tǒng)指標系統(tǒng)中的平均顧客數(shù)Ls 隊列中的平均顧客數(shù)Lq 顧客在系統(tǒng)中的平均逗留時間顧客在系統(tǒng)中的逗留時間Ts服從參數(shù)為m-l的負指數(shù)分布顧客在系統(tǒng)中的平均逗留時間Ws 顧客在隊列中的平均逗留時間Wq John D. C. Little公式 例理發(fā)店空閉的概率店內有3個顧客的概率店內至少有一個顧客的概率店內顧客的平均數(shù)，等待服務顧客的平均數(shù)顧客在店內的平均逗留時間和平均等待時間必須在店內消耗15分鐘以上的概率某理發(fā)店只有一名理發(fā)師，來理發(fā)的顧客按泊松分布到達，平均每小時4人，理發(fā)時間服從負指數(shù)分布，平均需要6分鐘，求解 此為M/M/1系統(tǒng)，已知l=4/60=1/15人

32、/分 m=1/6人/分，r=l/m=(1/15)/(1/6)=0.4(1) P0=1r=1=0.4=0.6(2) P3=(1r)r3=0.60.43=0.0384(3) P(n1)=1P(n1)=1P0=0.4(4) Ls=r/(1r)=0.4/(10.4)=0.667 人 Lq=Lsr=0.667-0.4=0.227例 高速公路入口收費處設有一個收費通道，汽車到達服從Poisson分布，平均到達速率為200輛/小時，收費時間服從負指數(shù)分布，平均收費時間為15秒/輛。求Ls、Lq、Ws和Wq。解根據(jù)題意，=200輛/小時，=240輛/小時，=/=5/6。4.4.2有限隊列模型 M/M/1/N/

33、FCFS 當隊列的容量從無限值變?yōu)橛邢拗礜時，M/M/1/FCFS就轉化成為M/M/1/N/FCFS 系統(tǒng)的狀態(tài)轉移圖 012N-1N系統(tǒng)的狀態(tài)概率平衡方程對于狀態(tài)0：0P0=1P1對于狀態(tài)n：n-1Pn-1+n+1Pn+1=(n+n)Pn 0n=1)=1-P0=0.75Ls=/(-)=3Lq=Ls- =3-0.75=2.25Ws=Ls/=10 分Wq=Ws-1/=7.5 分 指標 模型M/M/3M/M/1服務臺空閑的概率P00.07480.25(每個子系統(tǒng)）顧客必須等待的概率0.570.75平均隊列長（等待顧客數(shù)）Lq1.702.25(每個子系統(tǒng)）平均隊長（顧客數(shù)）Ls3.959.00（整個系統(tǒng)）平均逗留時間Ws4.39分鐘10分鐘平均等待時間Wq1.89分鐘7.5分鐘由此可見，單隊比三隊有顯著的優(yōu)越性。M/M/c/N/FCFS模型 離開服務臺服務臺服務臺顧客到達顧客離去顧客離去顧客離去隊列分析設系統(tǒng)容量為N(Nc)，當系統(tǒng)中的顧數(shù)nN時，到達的顧客就進入系統(tǒng)；當n=N時，到達