高級(jí)運(yùn)籌學(xué)-排隊(duì)論

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

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

3、機(jī)就會(huì)“吐”出一張像名片大小的號(hào)票，拿著這張?zhí)柶卑舶察o靜地坐在休息區(qū)舒適的椅子上等候，輪到自己時(shí)，大屏幕和語(yǔ)音系統(tǒng)會(huì)提醒你到相應(yī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。在游樂(lè)園中的頻頻排隊(duì)會(huì)極為掃興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在佛羅里達(dá)州Orlando的DisneyLand里,游客們依著繩子排成許多隊(duì)，指示牌可以估計(jì)出等待的時(shí)間，而許多大的電視屏幕為游客們提供消遣。DisneyLand中的FastPass系統(tǒng)就是想解決排隊(duì)問(wèn)題DisneyWhat is FastPass?工作原理：到達(dá)的顧客將自己的票插入FastPass的slot中FastPass計(jì)算出建議顧客返回的時(shí)間間隔（time interval）或時(shí)間點(diǎn)或時(shí)間窗（time window）顧客無(wú)需排隊(duì)，在指定的時(shí)間返回就可持票進(jìn)入 如何計(jì)算顧客等待時(shí)間？服務(wù)系統(tǒng)的構(gòu)成排隊(duì)現(xiàn)象抽象成服務(wù)系

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

28、012n-1nn+1生滅過(guò)程的基本公式生滅過(guò)程的狀態(tài)概率因?yàn)樗约吹蒙鷾邕^(guò)程Birth-death process標(biāo)準(zhǔn)的排隊(duì)過(guò)程是參數(shù)不隨狀態(tài)而變的特殊的生滅過(guò)程4.4 不同類型排隊(duì)系統(tǒng)分析輸入過(guò)程為泊松流，服務(wù)時(shí)間基本服從負(fù)指數(shù)分布的排隊(duì)系統(tǒng)標(biāo)準(zhǔn)M/M/1/有限隊(duì)列模型 M/M/1/N/顧客為有限源系統(tǒng)M/M/1/m多服務(wù)臺(tái)系統(tǒng)M/M/c 4.4.1標(biāo)準(zhǔn)排隊(duì)模型 M/M/1/FCFS 顧客到達(dá)的時(shí)間間隔是負(fù)指數(shù)分布服務(wù)時(shí)間是負(fù)指數(shù)分布一個(gè)服務(wù)臺(tái)排隊(duì)系統(tǒng)和顧客源的容量都是無(wú)限實(shí)行先到先服務(wù)的一個(gè)服務(wù)系統(tǒng)M/M/1的狀態(tài)轉(zhuǎn)移分析012n-1nn+1M/M/1排隊(duì)模型 標(biāo)準(zhǔn)的排隊(duì)過(guò)程是參數(shù)不隨狀態(tài)

29、而變的特殊的生滅過(guò)程得到 令稱為服務(wù)強(qiáng)度，則得例高速公路入口收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車到達(dá)服從Poisson分布，平均到達(dá)速率為100輛小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒輛。求1、收費(fèi)處空閑的概率；2、收費(fèi)處忙的概率；3、系統(tǒng)中分別有1，2，3輛車的概率。解根據(jù)題意, =100輛/小時(shí),1/=15秒=1/240（小時(shí)/輛）,即240（輛/小時(shí)）。因此，=/=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)績(jī)效度量 系統(tǒng)中的平均顧客數(shù)Ls Expected number of customers in system 平均等待顧客個(gè)數(shù)Lq（排隊(duì)長(zhǎng)） Expected queue length (exclude customers being served) 顧客平均逗留時(shí)間Ws Waiting time in system 顧客平均（排隊(duì)）等待時(shí)間Wq Waiting time in queue (exclude service ti

31、me)M/M/1/FCFS的系統(tǒng)指標(biāo)系統(tǒng)中的平均顧客數(shù)Ls 隊(duì)列中的平均顧客數(shù)Lq 顧客在系統(tǒng)中的平均逗留時(shí)間顧客在系統(tǒng)中的逗留時(shí)間Ts服從參數(shù)為m-l的負(fù)指數(shù)分布顧客在系統(tǒng)中的平均逗留時(shí)間Ws 顧客在隊(duì)列中的平均逗留時(shí)間Wq John D. C. Little公式 例理發(fā)店空閉的概率店內(nèi)有3個(gè)顧客的概率店內(nèi)至少有一個(gè)顧客的概率店內(nèi)顧客的平均數(shù)，等待服務(wù)顧客的平均數(shù)顧客在店內(nèi)的平均逗留時(shí)間和平均等待時(shí)間必須在店內(nèi)消耗15分鐘以上的概率某理發(fā)店只有一名理發(fā)師，來(lái)理發(fā)的顧客按泊松分布到達(dá)，平均每小時(shí)4人，理發(fā)時(shí)間服從負(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例 高速公路入口收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車到達(dá)服從Poisson分布，平均到達(dá)速率為200輛/小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒/輛。求Ls、Lq、Ws和Wq。解根據(jù)題意，=200輛/小時(shí)，=240輛/小時(shí)，=/=5/6。4.4.2有限隊(duì)列模型 M/M/1/N/

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