數(shù)學建模_排隊論1

1、運運 籌籌 帷帷 幄幄 之之 中中決決 勝勝 千千 里里 之之 外外排排 隊隊 論論QueueingQueueing Theory Theory第十四章第十四章 排隊論排隊論 一、排隊論的基本概念一、排隊論的基本概念 二、二、幾類排隊論模型幾類排隊論模型 三、三、模型的建立與求解模型的建立與求解 目錄下頁返回上頁結束一、排隊論的基本知識一、排隊論的基本知識目錄下頁返回上頁結束2. 排隊系統(tǒng)描述排隊系統(tǒng)描述3. 基本組成部分基本組成部分4. 數(shù)量指標數(shù)量指標5. 排隊模型的記號排隊模型的記號1. 背景介紹背景介紹1 背景介紹背景介紹 有形的隊伍有形的隊伍 超市出口處排隊付款超市出口處排隊付款 餐

2、廳排隊買飯餐廳排隊買飯 公共電話亭打電話公共電話亭打電話 無形的隊伍無形的隊伍 114查號臺等待服務查號臺等待服務 網(wǎng)絡中數(shù)據(jù)包傳輸網(wǎng)絡中數(shù)據(jù)包傳輸 報告等首長批示報告等首長批示 文件等待打印或發(fā)送文件等待打印或發(fā)送 某些系統(tǒng)也可能根本不允許排隊某些系統(tǒng)也可能根本不允許排隊 交換機處理呼叫交換機處理呼叫排隊論研究的內(nèi)容有三部分排隊論研究的內(nèi)容有三部分1.性態(tài)問題：即研究排隊系統(tǒng)中的概率分布規(guī)律性態(tài)問題：即研究排隊系統(tǒng)中的概率分布規(guī)律2.2.最優(yōu)化問題：分為靜態(tài)最優(yōu)化和動態(tài)最優(yōu)化，即最優(yōu)化問題：分為靜態(tài)最優(yōu)化和動態(tài)最優(yōu)化，即 為系統(tǒng)的最優(yōu)設計和系統(tǒng)的最優(yōu)運營為系統(tǒng)的最優(yōu)設計和系統(tǒng)的最優(yōu)運營3.排

3、隊系統(tǒng)的統(tǒng)計推斷：排隊系統(tǒng)的統(tǒng)計推斷： 判斷一個給定的排隊系統(tǒng)符合于哪種模型，以判斷一個給定的排隊系統(tǒng)符合于哪種模型，以便于根據(jù)排隊理論進行分析研究便于根據(jù)排隊理論進行分析研究. 2.排隊系統(tǒng)描述排隊系統(tǒng)描述 排隊系統(tǒng)又稱為隨機服務系統(tǒng)，是研究排隊系統(tǒng)又稱為隨機服務系統(tǒng)，是研究服務服務 請求服務的人或者物請求服務的人或者物顧客顧客；排隊系統(tǒng)的共同特征：排隊系統(tǒng)的共同特征： 顧客到達系統(tǒng)的時刻是隨機的，為每一位顧客顧客到達系統(tǒng)的時刻是隨機的，為每一位顧客 有為顧客服務的人或者物，即有為顧客服務的人或者物，即服務員或服務臺服務員或服務臺；目錄下頁返回上頁結束過程和過程和擁擠擁擠現(xiàn)象的隨機模型現(xiàn)象的

4、隨機模型.提供服務的時間是隨機的，因而整個排隊系統(tǒng)提供服務的時間是隨機的，因而整個排隊系統(tǒng)的狀態(tài)也是的狀態(tài)也是隨機隨機的的.排隊模型服務窗服務窗服務規(guī)則服務規(guī)則排隊排隊排隊規(guī)則排隊規(guī)則顧客源顧客源排隊系統(tǒng)排隊系統(tǒng)基本排隊過程基本排隊過程： 從圖從圖6666可知，每個顧客由顧客源按一定方式可知，每個顧客由顧客源按一定方式目錄下頁返回上頁結束到達服務系統(tǒng)，首先加入隊列到達服務系統(tǒng)，首先加入隊列排隊排隊等待接受服務，等待接受服務，然后服務臺按然后服務臺按一定規(guī)則一定規(guī)則從隊列中選擇顧客進行服從隊列中選擇顧客進行服務，獲得服務的顧客立即離開務，獲得服務的顧客立即離開.排隊論所要研究解決的問題：排隊論所

5、要研究解決的問題： 面對擁擠現(xiàn)象，人們通常的做法是增加服務設施面對擁擠現(xiàn)象，人們通常的做法是增加服務設施但是增加的數(shù)量越多，人力、物力的支出就越大，甚但是增加的數(shù)量越多，人力、物力的支出就越大，甚至會出現(xiàn)空閑浪費，如果服務設施太少，顧客排隊等至會出現(xiàn)空閑浪費，如果服務設施太少，顧客排隊等待的時間就會很長，這樣對顧客會帶來不良影響待的時間就會很長，這樣對顧客會帶來不良影響.如如何做到既保證一定的服務質量指標，又使服務設施費何做到既保證一定的服務質量指標，又使服務設施費用用經(jīng)濟合理經(jīng)濟合理，恰當?shù)亟鉀Q顧客，恰當?shù)亟鉀Q顧客排隊時間排隊時間與與服務設施費服務設施費用大小用大小這對矛盾，就是隨機服務系統(tǒng)

6、理論這對矛盾，就是隨機服務系統(tǒng)理論排隊論排隊論所要研究解決的問題。所要研究解決的問題。目錄下頁返回上頁結束3.排隊系統(tǒng)的基本組成部分排隊系統(tǒng)的基本組成部分排隊系統(tǒng)是由輸入過程、排對規(guī)則和服務機構組成排隊系統(tǒng)是由輸入過程、排對規(guī)則和服務機構組成. .(1).輸入過程輸入過程 指要求服務的顧客是按怎樣的指要求服務的顧客是按怎樣的規(guī)律規(guī)律(i) 顧客總體數(shù)顧客總體數(shù). 又稱顧客源、輸入源又稱顧客源、輸入源.這是指顧客這是指顧客(ii) 顧客到達方式顧客到達方式. 這是描述顧客是怎樣來到系這是描述顧客是怎樣來到系統(tǒng)統(tǒng)目錄下頁返回上頁結束到達排隊系統(tǒng)的過程，有時也把它稱為顧客流到達排隊系統(tǒng)的過程，有時也

7、把它稱為顧客流. .一一般可以從般可以從3 3個方面來描述個方面來描述個輸入過程個輸入過程. . 的來源的來源.顧客源可以是有限的，也可以是無限的顧客源可以是有限的，也可以是無限的.的，是單個到達，還是成批到達的，是單個到達，還是成批到達. (iii) 顧客流的概率分布顧客流的概率分布. .或稱相繼顧客到達的或稱相繼顧客到達的時間時間(2).排對規(guī)則排對規(guī)則 指服務臺從隊列中選取顧客進行指服務臺從隊列中選取顧客進行 (i)損失制損失制 指如果顧客到達排隊系統(tǒng)時，所有指如果顧客到達排隊系統(tǒng)時，所有目錄下頁返回上頁結束間隔間隔的分布的分布. .這是求解排隊系統(tǒng)有關運行指標問這是求解排隊系統(tǒng)有關運行

8、指標問題題時，首先需要確定的指標時，首先需要確定的指標. .顧客流的概率分布一般顧客流的概率分布一般有定長分布、二項分布、泊松流有定長分布、二項分布、泊松流( (最簡單流最簡單流) )、愛爾、愛爾朗分布等若干種朗分布等若干種. .服務的順序服務的順序. .一般可以分為損失制、等待制和混一般可以分為損失制、等待制和混合制等合制等3 3大類大類. .服務臺都被先到的顧客占用，那么他們就自動服務臺都被先到的顧客占用，那么他們就自動離開系統(tǒng)永不再來離開系統(tǒng)永不再來. .(ii)等待制等待制 指當顧客來到系統(tǒng)時，所有服務臺指當顧客來到系統(tǒng)時，所有服務臺a.先到先服務先到先服務FCFS FCFS 按顧客到

9、達的先后順序對顧客按顧客到達的先后順序對顧客b.先到后服務先到后服務LCFSLCFSc.隨機服務隨機服務SIRO SIRO 即當服務臺空閑時，不按照排隊即當服務臺空閑時，不按照排隊d.優(yōu)先權服務優(yōu)先權服務PRPR目錄下頁返回上頁結束都不空，顧客加入排隊行列等待服務都不空，顧客加入排隊行列等待服務. .等待制中，等待制中，服務臺在選擇顧客進行服務時常有如下四種規(guī)則：服務臺在選擇顧客進行服務時常有如下四種規(guī)則：進行服務進行服務. .序列而隨意指定某個顧客接受服務序列而隨意指定某個顧客接受服務. .(iii)混合制混合制 這是等待制與損失制相結合的一種服這是等待制與損失制相結合的一種服a.隊長有限隊

10、長有限. .當排隊等待服務的顧客人數(shù)超當排隊等待服務的顧客人數(shù)超b.等待時間有限等待時間有限. .即顧客在系統(tǒng)中的等待時即顧客在系統(tǒng)中的等待時c.逗留時間逗留時間( (等待時間與服務時間之和等待時間與服務時間之和) )有限有限. .目錄下頁返回上頁結束務規(guī)則，一般是指允許排隊，但又不允許隊列無限務規(guī)則，一般是指允許排隊，但又不允許隊列無限長下去長下去.具體說來，大致有三種：具體說來，大致有三種：過過規(guī)定規(guī)定數(shù)量數(shù)量K K時，后來的顧客就自動離去，另時，后來的顧客就自動離去，另求服務，即系統(tǒng)的等待空間是有限的求服務，即系統(tǒng)的等待空間是有限的. .間不超過某一給定的間不超過某一給定的長度長度T T

11、，當?shù)却龝r間超，當?shù)却龝r間超過過T T時，顧客將自動離去，并不再回來時，顧客將自動離去，并不再回來. .(3). 服務機構服務機構 (i)服務臺服務臺數(shù)量數(shù)量及構成及構成形式形式. 從數(shù)量上說，服務臺有從數(shù)量上說，服務臺有單單(ii)服務方式服務方式. 這是指在某一時刻接受服務的顧客數(shù)，這是指在某一時刻接受服務的顧客數(shù)，(iii)服務時間的分布服務時間的分布.在多數(shù)情況下，對每一個顧客的在多數(shù)情況下，對每一個顧客的目錄下頁返回上頁結束服務臺和服務臺和多多服務臺之分服務臺之分. 從構成形式上看，服務臺有：從構成形式上看，服務臺有：單隊一單隊一-單服務臺式；單服務臺式；單隊一單隊一-多服務臺并聯(lián)多

12、服務臺并聯(lián)式；式；多隊一多隊一-多服務臺并聯(lián)式；多服務臺并聯(lián)式；單隊一單隊一-多服多服務臺串聯(lián)式；務臺串聯(lián)式；單隊一單隊一-多服務臺并串聯(lián)混合式，多服務臺并串聯(lián)混合式，以及多隊多服務臺并串聯(lián)混合式等等以及多隊多服務臺并串聯(lián)混合式等等.它有它有單個單個服務和服務和成批成批服務兩種服務兩種.服務時間是一隨機變量服務時間是一隨機變量. .排隊系統(tǒng)的幾種形式排隊系統(tǒng)的幾種形式：目錄下頁返回上頁結束目錄下頁返回上頁結束目錄下頁返回上頁結束目錄下頁返回上頁結束目錄下頁返回上頁結束 顧客到達時間間隔的分布顧客到達時間間隔的分布:：第：第n n個顧客與第個顧客與第n-1n-1個顧客到達的時間間隔；個顧客到達的

13、時間間隔；nXnT：第：第n n個顧客到達的時刻；個顧客到達的時刻；設設nTTT100, 2 , 1,1nTTXnnn令令1T2TnT1nT1nT0TnX常見顧客的服務時間分布有：常見顧客的服務時間分布有： 1. 1. 定長分布定長分布D(DeterministicD(Deterministic) )、 2 2. .負指數(shù)分布負指數(shù)分布M(MarkovM(Markov) )、 3.Possion 3.Possion分布分布 4 4.k.k階階ErlangErlang分布分布(E(Ek k) )、 5. 5. 一般相互獨立的時間間隔分布一般相互獨立的時間間隔分布 GI(GeneralGI(Gen

14、eral Independent) Independent)、顧客到達時間間隔的分布、服務時間分布顧客到達時間間隔的分布、服務時間分布:（1 1）定長分布（）定長分布（D D）：每個顧客接受服務的時間）：每個顧客接受服務的時間 是一個確定的常數(shù)。是一個確定的常數(shù)。（2 2）負指數(shù)分布（）負指數(shù)分布（M M）：每個顧客接受服務時間）：每個顧客接受服務時間 相互獨立，具有相同參數(shù)相互獨立，具有相同參數(shù) 的負指數(shù)分布：的負指數(shù)分布： 其中其中 ，為一常數(shù)。，為一常數(shù)。0 00)(ttetft0- - 單位時間平均服務完成的顧客數(shù)單位時間平均服務完成的顧客數(shù)1/1/ - - 每個顧客的平均服務時間每個

15、顧客的平均服務時間232022年年4月月18日日3、Poisson分布分布242022年年4月月18日日252022年年4月月18日日4.k4.k階愛爾朗（階愛爾朗（ErlangErlang）分布：每個顧客接受服務）分布：每個顧客接受服務 時間服從時間服從k k階愛爾朗分布，其密度函數(shù)為：階愛爾朗分布，其密度函數(shù)為：)0,0()!1()()(1tektkktftkk21)(,1)(kTDTE 如如k k個服務臺串聯(lián)（個服務臺串聯(lián)（k k個服務階段），一個顧客個服務階段），一個顧客接受接受k k個服務共需的服務時間個服務共需的服務時間T T，T T 愛爾朗分布。愛爾朗分布。4. 排隊系統(tǒng)的主要數(shù)

16、量指標排隊系統(tǒng)的主要數(shù)量指標 排隊論主要研究系統(tǒng)的性態(tài)，即與排隊有關排隊論主要研究系統(tǒng)的性態(tài)，即與排隊有關(1).排隊系統(tǒng)主要數(shù)量指標排隊系統(tǒng)主要數(shù)量指標等待時間、等待時間、 忙期、忙期、 隊長隊長.目錄下頁返回上頁結束的數(shù)量指標的概率規(guī)律性；系統(tǒng)的優(yōu)化問題；統(tǒng)的數(shù)量指標的概率規(guī)律性；系統(tǒng)的優(yōu)化問題；統(tǒng)計推斷，根據(jù)資料合理建立模型計推斷，根據(jù)資料合理建立模型. .目的是正確設目的是正確設計和有效運行各個服務系統(tǒng)，使之發(fā)揮最佳效益計和有效運行各個服務系統(tǒng)，使之發(fā)揮最佳效益. .所以必須確定判斷系統(tǒng)運行優(yōu)劣的基本數(shù)量指標所以必須確定判斷系統(tǒng)運行優(yōu)劣的基本數(shù)量指標. .(i).等待時間等待時間 從顧

17、客到達時刻起到他從顧客到達時刻起到他開始開始接受服務止這接受服務止這(ii).忙期忙期 忙期忙期是指從顧客到達空閑著的服務機構起，到是指從顧客到達空閑著的服務機構起，到(iii).隊長隊長 隊長隊長是指系統(tǒng)中的顧客數(shù)是指系統(tǒng)中的顧客數(shù)(排隊等待的顧客數(shù)與排隊等待的顧客數(shù)與目錄下頁返回上頁結束段時間稱為等待時間段時間稱為等待時間.等待時間是個隨機變量等待時間是個隨機變量.從顧客從顧客到達時刻起到他接受服務到達時刻起到他接受服務完成完成止這段時間稱為逗留時止這段時間稱為逗留時間，也是隨機變量間，也是隨機變量.服務機構再次成為空閑止的這段時間，即服務機構服務機構再次成為空閑止的這段時間，即服務機構連

18、續(xù)忙連續(xù)忙的時間的時間. .這是個隨機變量，是服務員最為關心的指標，因這是個隨機變量，是服務員最為關心的指標，因為它關系到服務員的為它關系到服務員的服務強度服務強度. .與忙期相對的是與忙期相對的是閑期閑期, ,即即服務機構連續(xù)保持空閑的時間服務機構連續(xù)保持空閑的時間. .在排隊系統(tǒng)中，忙期和閑在排隊系統(tǒng)中，忙期和閑期總是期總是交替交替出現(xiàn)的出現(xiàn)的. .正在接受服務的顧客數(shù)之和正在接受服務的顧客數(shù)之和)；排隊長排隊長是指系統(tǒng)中正在排隊是指系統(tǒng)中正在排隊等待服務的顧客數(shù)等待服務的顧客數(shù).隊長和排隊長一般都是隨機變量隊長和排隊長一般都是隨機變量. 記時刻記時刻 t 時，系統(tǒng)狀態(tài)取值為時，系統(tǒng)狀態(tài)取

19、值為n的概率記為的概率記為Pn(t) 則稱為穩(wěn)態(tài)（或統(tǒng)計平衡狀態(tài)解則稱為穩(wěn)態(tài)（或統(tǒng)計平衡狀態(tài)解)解。解。nntPtP)(lim如果(2).數(shù)量指標的常用記號數(shù)量指標的常用記號(i).主要數(shù)量指標主要數(shù)量指標WsWs平均逗留時間，即平均逗留時間，即( (在任意時刻在任意時刻) )進入進入目錄下頁返回上頁結束的所有顧客數(shù)的期望值；的所有顧客數(shù)的期望值；等待服務的顧客數(shù)的期望值；等待服務的顧客數(shù)的期望值；穩(wěn)態(tài)系統(tǒng)的顧客逗留時間的期望值；穩(wěn)態(tài)系統(tǒng)的顧客逗留時間的期望值；穩(wěn)態(tài)系統(tǒng)的顧客等待時間的期望值穩(wěn)態(tài)系統(tǒng)的顧客等待時間的期望值. .Ls-Ls-平均隊長，平均隊長， 即穩(wěn)態(tài)系統(tǒng)任一時刻即穩(wěn)態(tài)系統(tǒng)任一時

20、刻平均等待時間，即平均等待時間，即( (在任意時刻在任意時刻) )進入進入qW 平均等待隊長，即穩(wěn)態(tài)系統(tǒng)任一時刻平均等待隊長，即穩(wěn)態(tài)系統(tǒng)任一時刻qL(ii).其它常用數(shù)量指標其它常用數(shù)量指標s 系統(tǒng)中并聯(lián)服務臺的數(shù)目系統(tǒng)中并聯(lián)服務臺的數(shù)目；N 穩(wěn)態(tài)系統(tǒng)任一時刻的狀態(tài)（即系統(tǒng)中穩(wěn)態(tài)系統(tǒng)任一時刻的狀態(tài)（即系統(tǒng)中Ws任一顧客在穩(wěn)態(tài)系統(tǒng)中的逗留時間；任一顧客在穩(wěn)態(tài)系統(tǒng)中的逗留時間；Wq任一顧客在穩(wěn)態(tài)系統(tǒng)中的排隊等待時間；任一顧客在穩(wěn)態(tài)系統(tǒng)中的排隊等待時間；目錄下頁返回上頁結束所有顧客數(shù)）；所有顧客數(shù)）；平均到達率；平均到達率； 平均到達間隔；平均到達間隔；1 平均服務率；平均服務率；平均服務時間；平均

21、服務時間；1 有服務臺全部空閑的概率；有服務臺全部空閑的概率；目錄下頁返回上頁結束繁忙程度的重要尺度繁忙程度的重要尺度. .服務強度，即每個服務臺單位時間內(nèi)的平服務強度，即每個服務臺單位時間內(nèi)的平均服務時間，一般有均服務時間，一般有 ，這是衡量排隊系統(tǒng)，這是衡量排隊系統(tǒng) s : :穩(wěn)態(tài)系統(tǒng)任意時刻狀態(tài)為穩(wěn)態(tài)系統(tǒng)任意時刻狀態(tài)為n n的概率；的概率；nPP Nn特別當特別當n=0n=0時時( (系統(tǒng)中顧客數(shù)為系統(tǒng)中顧客數(shù)為0)0)， 即穩(wěn)態(tài)系統(tǒng)所即穩(wěn)態(tài)系統(tǒng)所0P損失率：由于系統(tǒng)的條件限制，使顧客被拒絕服損失率：由于系統(tǒng)的條件限制，使顧客被拒絕服 務而使服務部門受到損失的概率。務而使服務部門受到損失

22、的概率。 5. 排隊系統(tǒng)的描述符號排隊系統(tǒng)的描述符號 描述符號：描述符號：X/Y/Z/A/B/CX/Y/Z/A/B/CXX顧客相繼到達的間隔時間的分布顧客相繼到達的間隔時間的分布 ；常用下；常用下MM表示到達的過程為泊松過程或負指數(shù)分布；表示到達的過程為泊松過程或負指數(shù)分布；DD表示定長輸入；表示定長輸入；GIGI表示一般相互獨立的時間間隔分布表示一般相互獨立的時間間隔分布. .YY服務時間的分布；所用符號與表示顧客服務時間的分布；所用符號與表示顧客目錄下頁返回上頁結束列符號：列符號：到達間隔時間分布相同到達間隔時間分布相同. . 表示表示K K階愛爾朗分布；階愛爾朗分布；kEZZ服務臺個數(shù)服

23、務臺個數(shù) ； “ “1”1”表示單個服務臺，表示單個服務臺，“s” (s1)s” (s1)A A系統(tǒng)容量限制系統(tǒng)容量限制( (默認為默認為)；如系統(tǒng)有；如系統(tǒng)有K K個等待位子，則個等待位子，則B B顧客源數(shù)目（默認為顧客源數(shù)目（默認為）；分有限與無限兩種，）；分有限與無限兩種，表表C C服務規(guī)則；服務規(guī)則； 常用下列符號：常用下列符號：FCFSFCFS：表示先到先服務的排隊規(guī)則；：表示先到先服務的排隊規(guī)則；LCFSLCFS：表示后到先服務的排隊規(guī)則；：表示后到先服務的排隊規(guī)則；PRPR： 表示優(yōu)先權服務的排隊規(guī)則表示優(yōu)先權服務的排隊規(guī)則。目錄下頁返回上頁結束表示多個服務臺表示多個服務臺.0K

24、0K1)s (s1)個服務臺；系個服務臺；系統(tǒng)等待空間容量無限統(tǒng)等待空間容量無限( (等待制等待制) )；顧客源無限，采；顧客源無限，采用先到先服務規(guī)則用先到先服務規(guī)則. .中的前中的前3 3個符號個符號. .例如，某排隊問題為例如，某排隊問題為M MM MS S.無限；顧客源無限，先到先服務，單個服務的等無限；顧客源無限，先到先服務，單個服務的等待制系統(tǒng)待制系統(tǒng). 定義：定義：設設 為一個隨機過程，若為一個隨機過程，若N(tN(t) )的概率分布具有以下性質：的概率分布具有以下性質： (1)(1)假設假設N(tN(t)=n)=n，則從時刻到下一個顧客，則從時刻到下一個顧客到達到達時刻止的時間

25、服從參數(shù)為時刻止的時間服從參數(shù)為 的負指數(shù)分布；的負指數(shù)分布； (2) (2)假設假設N(tN(t)=n)=n，則從時刻到下一個顧客，則從時刻到下一個顧客離開離開時刻止的時間服從參數(shù)為時刻止的時間服從參數(shù)為 的負指數(shù)分布；的負指數(shù)分布； (3) (3)同一時刻是只有一個同一時刻是只有一個 顧客到達或離去。顧客到達或離去。 則稱則稱 為一個為一個生滅過程生滅過程。 0),(ttN0),(ttNnn4、生滅、生滅過程過程1 10 001nn-1n+11nnn1n平穩(wěn)生滅過程系統(tǒng)狀態(tài)平穩(wěn)生滅過程系統(tǒng)狀態(tài)n n平衡方程：平衡方程：“流入流入= =流出流出”nnnnnnnppppp)(011111100

26、系統(tǒng)達到平穩(wěn)狀態(tài)時：系統(tǒng)達到平穩(wěn)狀態(tài)時：.)2 , 1 , 0(),(ntppnn)(tN的分布的分布.)2 , 1 , 0(,)()(nntNPtpn系統(tǒng)達到平穩(wěn)狀態(tài)時：系統(tǒng)達到平穩(wěn)狀態(tài)時：100110210111.,.2 , 1,nnnnnnnnnnnCppCnpCp其中其中nnnnnnnppppp)(011111100平衡方程：平衡方程： 當當 時才有意義時才有意義1nnC.)2 , 1 , 0(,)()(nntNPtppnn 已知: 顧客到達間隔時間分布, 服務時間分布. 求: 隊長隊長: Ls - 系統(tǒng)中的顧客數(shù)系統(tǒng)中的顧客數(shù). 排隊長排隊長(隊列長隊列長): Lq - 隊列中的顧客

27、數(shù)隊列中的顧客數(shù). Ls = Lq + 正在接受服務的顧客數(shù)正在接受服務的顧客數(shù) 逗留時間逗留時間: W S- 顧客在系統(tǒng)中的停留時間顧客在系統(tǒng)中的停留時間 等待時間等待時間: Wq - 顧客在隊列中的等待時間顧客在隊列中的等待時間. WS = Wq + 服務時間服務時間 忙期忙期, 損失率損失率, 服務強度服務強度.排隊問題的求解排隊問題的求解三、幾類排隊論模型三、幾類排隊論模型1. M/M/S M/M/S 模型模型2. GI/M/n GI/M/n 模型模型目錄下頁返回上頁結束1. M/M/s M/M/s排隊模型排隊模型 M/M/sM/M/s排隊模型是指排隊模型是指s s個服務員的排隊系統(tǒng)，

28、個服務員的排隊系統(tǒng)，顧客到來間隔時間是獨立同分布的；顧客到來間隔時間是獨立同分布的；服務時間也是獨立同分布的；服務時間也是獨立同分布的；并且獨立于輸入過程；并且獨立于輸入過程；排隊規(guī)則是等待制；排隊規(guī)則是等待制；目錄下頁返回上頁結束含假定：含假定：顧客到來間隔時間服從參數(shù)為顧客到來間隔時間服從參數(shù)為 的指數(shù)分布，的指數(shù)分布，服務時間服從參數(shù)為服務時間服從參數(shù)為 的負指數(shù)分布，且有隱的負指數(shù)分布，且有隱 按排隊論的基本構成特征，來求解該排隊模型按排隊論的基本構成特征，來求解該排隊模型(1).基本構成基本構成(i) 顧客到達規(guī)律顧客到達規(guī)律()( ),0,1,2!kttP X tkekk 目錄下頁

29、返回上頁結束的主要數(shù)量指標：的主要數(shù)量指標：平均到達率平均到達率.表示在表示在 時間到達的顧客數(shù)，稱為排隊系統(tǒng)的輸入過程時間到達的顧客數(shù)，稱為排隊系統(tǒng)的輸入過程.()Xt( ,)t tt 其平均值為其平均值為 ，即單位時間內(nèi)到達的顧客數(shù)為，即單位時間內(nèi)到達的顧客數(shù)為 ，并稱為，并稱為t它服從參數(shù)為它服從參數(shù)為 的泊松分布，即的泊松分布，即：t(ii) 服務時間服務時間目錄下頁返回上頁結束服務率服務率 . .表示顧客到達間隔時間序列，其表示顧客到達間隔時間序列，其1|nnnnss 中中 表示第表示第n個顧客的到來時刻個顧客的到來時刻. .n 可以證明可以證明： 服從參數(shù)服從參數(shù) 為的泊松分布的充

30、為的泊松分布的充( )X tt負指數(shù)分布負指數(shù)分布. .要條件是到要條件是到達間隔時間序列達間隔時間序列 獨立同分布且服從獨立同分布且服從ns記記Z Z為服務時間，為服務時間，Z Z服從參數(shù)為服從參數(shù)為 的負指數(shù)分布的負指數(shù)分布：01()00tteP Ztt 則則 ，即為每個顧客平均服務時間為，即為每個顧客平均服務時間為 ，從，從1EZ 1 而單位時間內(nèi)被服務的顧客的平均數(shù)為而單位時間內(nèi)被服務的顧客的平均數(shù)為 ，稱為平均，稱為平均 (iii) 排隊規(guī)則排隊規(guī)則按顧客的到達的先后順序服務，即先到先服務按顧客的到達的先后順序服務，即先到先服務. . 滿足以上三個條件的模型在排隊論中記為模型滿足以上

31、三個條件的模型在排隊論中記為模型(2).數(shù)量特征數(shù)量特征( (只討論只討論s=1s=1情形情形) )(i) 平均隊長平均隊長 穩(wěn)態(tài)下系統(tǒng)內(nèi)等待服務的顧客數(shù)，其數(shù)學期穩(wěn)態(tài)下系統(tǒng)內(nèi)等待服務的顧客數(shù)，其數(shù)學期目錄下頁返回上頁結束望稱為平均等待隊長，即望稱為平均等待隊長，即M/M/s模模型，其中型，其中s s為服務員的個數(shù)為服務員的個數(shù). .1L( (其中其中稱為服務強度稱為服務強度.).)21qL (1)(ii)平均逗留時間和平均等待時間平均逗留時間和平均等待時間平均逗留時間為平均逗留時間為平均等待時間為平均等待時間為則公式則公式稱為稱為LittleLittle公式公式. .目錄下頁返回上頁結束1L

32、W 11()qW LW qqLW qLL1qWW(3). M/M/s M/M/s 排隊模型排隊模型(i) 當當s=2s=2時時 服務強度服務強度平均隊長平均隊長平均等待時間平均等待時間 (ii) 當當s s是任意的是任意的服務強度服務強度平均隊長平均隊長平均等待時間平均等待時間 目錄下頁返回上頁結束212222221L 22222(1)LW s 02()!(1)sssLsps ssLW 其中其中為所有服務員均空閑的概率為所有服務員均空閑的概率.1100()()!(1)sksksspks 例例1.某醫(yī)院急診室同時只能診治一個病人，診治時間某醫(yī)院急診室同時只能診治一個病人，診治時間服從指數(shù)分布，每

33、個病人平均需要服從指數(shù)分布，每個病人平均需要1515分鐘。病人按泊分鐘。病人按泊松分布到達，平均每小時到達松分布到達，平均每小時到達3 3人。試對此排隊系統(tǒng)人。試對此排隊系統(tǒng)進行分析進行分析. .解解對此排隊系統(tǒng)分析如下：對此排隊系統(tǒng)分析如下： 先確定參數(shù)值：這是單服務系統(tǒng)有，先確定參數(shù)值：這是單服務系統(tǒng)有，目錄下頁返回上頁結束= 3= 3人人/h/h= 60/15 = 60/15 人人/h=4/h=4人人/h/h故服務強度為：故服務強度為： 計算穩(wěn)態(tài)概率：計算穩(wěn)態(tài)概率：010.75PP目錄下頁返回上頁結束0.750110.750.25P 計算系統(tǒng)主要工作指標計算系統(tǒng)主要工作指標3343L 人

34、人人人30.752.25qLLP 人人人人11160min43Whh1 0.750.7545minqWWPhh 目錄下頁返回上頁結束 15-12=3min15-12=3min目錄下頁返回上頁結束由于由于112W 代入代入 解得：解得：3 5 平均服務時間為：平均服務時間為：1112min5h (1)1(1)0.9P NxP Nx 目錄下頁返回上頁結束(1)0.1P Nx(1) 120.1xx上式兩邊取對數(shù)上式兩邊取對數(shù)目錄下頁返回上頁結束(2)loglog0.1x因為因為故故1 log0.1128loglog0.75x 所以所以6x 解解 這相當于增加了一個服務臺，故有這相當于增加了一個服務臺

35、，故有: :S S30.75,0.37524 120(0.75)1510.750.452!(10.375)2.211P 目錄下頁返回上頁結束2s 3 4 人人/h/h人人/h/h22(0.75)0.375550.270.1211112!(10.375)qL 人人人人(0.120.75)0.87qLL 人人人人0.870.2917.4min3LWh 0.120.042.4min3qqLWh病人必須等候的概率病人必須等候的概率, ,即系統(tǒng)狀態(tài)即系統(tǒng)狀態(tài)N2N2的概率：的概率：2(0.75)5(2)0.202!(10.375)11P N 目錄下頁返回上頁結束表表6-1 6-1 兩個系統(tǒng)的比較兩個系統(tǒng)

36、的比較目錄下頁返回上頁結束2. GI/M/n GI/M/n排隊模型排隊模型滿足下述三個條件的隨機服務系統(tǒng)稱為滿足下述三個條件的隨機服務系統(tǒng)稱為GI/M/nGI/M/n排隊模型排隊模型(1).GI/M/sGI/M/s系統(tǒng)的構成系統(tǒng)的構成b. 服務系統(tǒng)由服務系統(tǒng)由n n個并聯(lián)的服務臺所組成個并聯(lián)的服務臺所組成. . c. .各顧客的服務時間之間是相互獨立同分布的，服各顧客的服務時間之間是相互獨立同分布的，服目錄下頁返回上頁結束是相互獨立同分布的隨機變量是相互獨立同分布的隨機變量. .務時間與到達間隔時間相互獨立務時間與到達間隔時間相互獨立, ,且服務時間的分且服務時間的分a. 顧客到達時刻的間隔顧

37、客到達時刻的間隔10(0,1,2;0)nnn 布服從參數(shù)為布服從參數(shù)為 的負指數(shù)分布的負指數(shù)分布 . .(2).數(shù)量特征數(shù)量特征存在且與初始條件無關，其表達式為：存在且與初始條件無關，其表達式為： (i) 隊長隊長目錄下頁返回上頁結束定理定理6.1 設設 為第為第m m個乘客到達時系統(tǒng)的隊長，當個乘客到達時系統(tǒng)的隊長，當mq時，隊長的分布極限時，隊長的分布極限 1nlim()mjmP qjK K1( 1),0,1,1,1,nrjrrjjj nrUjnjjn n 其中其中 為方程為方程的唯一解，而的唯一解，而(1)An 目錄下頁返回上頁結束1 (1),0,1,1(1) (1)knrrkkk rn

38、nkkUKCrnCnk 11 (1)11(1) (1)knkkknnkkKCnk 011,1,2,1()kikiilCCknAl a. 該系統(tǒng)的平穩(wěn)分布下的平均隊長為該系統(tǒng)的平穩(wěn)分布下的平均隊長為b. 系統(tǒng)的平均隊長為系統(tǒng)的平均隊長為c. 系統(tǒng)服務臺平均占有數(shù)系統(tǒng)服務臺平均占有數(shù)目錄下頁返回上頁結束1121(1) (1)(1)jnjnE qjKU 其中其中11101nnn 2(1)KE qw E lE qE qw(ii) 等待時間等待時間存在且與初始條件無關，其表達式為存在且與初始條件無關，其表達式為 目錄下頁返回上頁結束令第令第m m個顧客的等待時間為個顧客的等待時間為 ，其分布為，其分布為

39、mw()( )mmP wxWx定理定理6.2 對對GI/M/nGI/M/n系統(tǒng)，當系統(tǒng)，當 時，隊長的分布極限時，隊長的分布極限1nlim( )( )mmWxW x (1)( )1,01n xKeW xx 其中其中 都與定理都與定理(6.1)(6.1)中的一致中的一致.,K 定理定理6.3 在在GI/M/n系統(tǒng)中，設各顧客服務的時間相互獨系統(tǒng)中，設各顧客服務的時間相互獨在平衡狀態(tài)下，顧客到達是不需要等待的概率為在平衡狀態(tài)下，顧客到達是不需要等待的概率為平均等待時間為平均等待時間為目錄下頁返回上頁結束等待的時間內(nèi)，每臺服務設施的輸出過程（即服務完成等待的時間內(nèi)，每臺服務設施的輸出過程（即服務完成

40、(0)11KW 20( )(1)KWxdW xn 離開服務機構的顧客）是一個以離開服務機構的顧客）是一個以 為強度的泊松過程為強度的泊松過程.立且具有公共的以立且具有公共的以 為參數(shù)的負指數(shù)分布，則在該顧客為參數(shù)的負指數(shù)分布，則在該顧客四、模型建立與求解四、模型建立與求解目錄下頁返回上頁結束1. 問題分析問題分析 2. 基本假設基本假設3. 模型的建立與求解模型的建立與求解 1. 問題分析問題分析 將公交車的運行看作是提供服務，即服務機構；將公交車的運行看作是提供服務，即服務機構； 將乘客看作顧客，乘客乘坐公交車看作是接受公交將乘客看作顧客，乘客乘坐公交車看作是接受公交的服務的服務. . 公交車運行中乘客的數(shù)目描述了系統(tǒng)的狀公交車運