排隊是日常生活中常見的現(xiàn)象

1、第九章 排隊論排隊是日常生活中常見的現(xiàn)象，如顧客到商店購買物品，病人到醫(yī)院看病，購買物品、看病都是顧客希望得到某種服務(wù)，但在某時刻要求服務(wù)的數(shù)量眼過服務(wù)機構(gòu)（服務(wù)臺、服務(wù)員）的容量時，出現(xiàn)排隊現(xiàn)象. 比如：電話局的占線問題，車站、碼頭的車船堵塞和疏導(dǎo)，機器的停機維修，水庫的存貯調(diào)節(jié)都是有形無形的排隊現(xiàn)象.§1 基本概念1、排隊過程的一般表示離去顧客到來服務(wù)機構(gòu)排隊結(jié)構(gòu)顧客源服務(wù)規(guī)則排隊規(guī)則圖9-1排隊系統(tǒng)排隊過程如圖9-1所示.各個顧客由顧客源（總體）出發(fā)，到達(dá)服務(wù)機構(gòu)（服務(wù)臺、服務(wù)員）前排隊等候接受服務(wù)，服務(wù)完了后就離去.排隊規(guī)則和服務(wù)規(guī)則：顧客在排隊系統(tǒng)中按怎樣的規(guī)則、次序接受服

2、務(wù).“顧客”、“服務(wù)員”是廣義的，可以是人，也可以是非生物.隊列可以是具體的排列，也可以是無形的.顧客可走向服務(wù)機構(gòu)，也可以相反（送貨上門）.表9-1 幾種排隊的例子到達(dá)的顧客要求服務(wù)的內(nèi)容服務(wù)機構(gòu)1、不能運轉(zhuǎn)的機器2、病人3、電話呼喚4、到達(dá)機場上空的飛機修理診斷或手術(shù)通話降落修理工醫(yī)生交換臺跑道2、排隊系統(tǒng)的組成和特征組成：輸入過程、排隊規(guī)則、服務(wù)機構(gòu)（1）輸入過程：指顧客到達(dá)排隊系統(tǒng).a、顧客總體的組成是有限的，如停機維修的機器，可能是無限的.如上游河水流入水庫.b、顧客到來的方式可能是一個一個的，也可能是成批的，如到餐廳就餐的顧客有單個到來，也有成批到來參加宴會.c、顧客相繼到達(dá)的間隔

3、時間可以是確定的，也可以是隨機型的，如自動裝配線上裝配的部件按確定的時間間隔到達(dá)裝配點，定期的班車，輪班、航班也是，但到商廈購物的客人、病人、通過路口的車輛，到達(dá)是隨機型的.d、顧客到達(dá)可以是相互獨立的，即到達(dá)的情況對以后顧客的到來沒有影響，也可以是關(guān)聯(lián)的.在此討論獨立的情形.e、輸入過程可以是平穩(wěn)的，即描述相繼到達(dá)的間隔時間分布和所含參數(shù)（期望值，方差）與時間無差.否則是非平穩(wěn)的.（2）排隊規(guī)則a、即時制（損失制）：顧客到達(dá)時，如所有的服務(wù)臺都正被占用，顧客可隨即離去，如市內(nèi)電話呼喚.等待制：排隊等候，如登記市外長途電話的呼喚.對于等待制：有下列各種規(guī)則：(i) 先到先服務(wù)：即按到達(dá)次序接受

4、服務(wù).(ii) 后到先服務(wù)：如乘電梯是后進(jìn)先出，在情報系統(tǒng)中，最后到達(dá)的信息往往是最有價值的，常最先被采用.(iii) 隨機服務(wù)：指服務(wù)員從等待的顧客中隨機地選取其一進(jìn)行服務(wù)，而不管到達(dá)的先后，如電話交換臺接通呼喚的電話.(iv) 有優(yōu)先權(quán)的服務(wù)：如醫(yī)院對重病患者給予優(yōu)先治療.b、從占有空間看，有的隊列是具體的，也有的是抽象的.有的系統(tǒng)要規(guī)定容量的最大限制，有的則認(rèn)為容量可以是無限的.c、從隊列的數(shù)目看，可以是單列，也可以是多列.（3）服務(wù)機構(gòu)a、服務(wù)機構(gòu)可以沒有服務(wù)員，也可以有一個或多個服務(wù)員.如自選商場，選購時沒有服務(wù)員，交款時有多個服務(wù)員.12n12nb、在有多個服務(wù)臺的情形，它們可以是

5、平行排列的，可以前后排列的，也可以是混合的.1單隊單服務(wù)臺 多隊多服務(wù)臺 單隊多服務(wù)臺1212n12n多服務(wù)臺串聯(lián) 多服務(wù)臺混合圖9-2 各種服務(wù)機構(gòu)的情況c、服務(wù)方式：單獨顧客，成批顧客（公共汽車對站臺上的顧客成批服務(wù)）.d、服務(wù)時間：確定型、隨機型.e、服務(wù)時間的分布：平穩(wěn)的，即分布的期望，方差不受時間的影響.3、排隊模型的分類上述各種特征中最主要的，影響最大的是：相繼顧客到達(dá)間隔時間分布；服務(wù)時間的分布；服務(wù)臺個數(shù).故按照上述三條分類，排隊模型的一般形式是：X/Y/Z其中：X相繼到達(dá)間隔時間的分布；Y服務(wù)時間的分布；Z并列服務(wù)臺數(shù)目.解排隊問題時，要研究它屬于哪個模型，其中X、Y需用實測

6、求得，其它因素在問題提出時給定.4、排隊問題的求解解排隊問題的目的，是研究排隊系統(tǒng)運行的效率，估計服務(wù)質(zhì)量，確定系統(tǒng)參數(shù)的最優(yōu)值，所以必須確定用以判斷系統(tǒng)運行優(yōu)劣的基本數(shù)量指標(biāo).解排隊問題首先求出這些指標(biāo)的概率分布.（1）隊長：即系統(tǒng)中的顧客數(shù)，設(shè)其期望值為Ls； 排隊長：即系統(tǒng)中排隊等待服務(wù)的顧客數(shù)，設(shè)其期望值為Lq；Ls=Lq+正被服務(wù)的顧客數(shù)Ls或Lq越大，說明服務(wù)率越低.（2）逗留時間：即一個顧客在系統(tǒng)中的停留時間，設(shè)其期望值為WS； 等待時間：一個顧客在系統(tǒng)中的排隊等待的時間，期望值Wq；Ws=Wq+服務(wù)時間在機器故障問題中，無論是機器等待修理或正在修理都使工廠受到停工損失，所以逗留

7、時間（停工時間）是主要的；購物、看病問題中僅僅等待時間是顧客關(guān)心的.（3）忙期：從顧客到達(dá)空閑服務(wù)機構(gòu)起到服務(wù)機構(gòu)再次為空閑止這段時間長度，即服務(wù)機構(gòu)連續(xù)繁忙的時間長度.忙期中平均完成服務(wù)顧客數(shù).（4）損失率：即時制或排隊有限制，由于顧客被拒絕而受到的損失.（5）服務(wù)強度：即每個服務(wù)臺單位時間內(nèi)的平均服務(wù)時間.計算上述指標(biāo)的基礎(chǔ)是表達(dá)系統(tǒng)狀態(tài)的概率.系統(tǒng)狀態(tài)：指系統(tǒng)中顧客數(shù).若系統(tǒng)狀態(tài)是n，它的可能值是：隊長無限制時，n=0，1，2，隊長有限制時，設(shè)最大數(shù)為N，n=0，1，2，N即時制，服務(wù)臺個數(shù)為C，n=0，1，2，C這些狀態(tài)的概率一般隨時刻t而變化.設(shè)Pn（t）在時刻t ，系統(tǒng)狀態(tài)為n的概

8、率.§2 到達(dá)間隔的分布和服務(wù)時間的分布解決排隊問題首先要根據(jù)原始資料做出顧客到達(dá)間隔和服務(wù)時間的經(jīng)驗分布，然后按照統(tǒng)計學(xué)的方法以確定合于哪種理論分布，并估計參數(shù)值.1、經(jīng)驗分布例9.1 某港口某年載貨500噸以上船舶以達(dá)共1271艘，按逐日記錄，可整理成船舶到達(dá)數(shù)分布表表9-2 船舶到達(dá)數(shù)分布表船舶到達(dá)數(shù)n頻率（天）頻率fn012345678910以上12436474714926194210.0330.1180.1750.2030.1950.1340.0710.0520.0110.0050.003合計3651.000例9.2 某服務(wù)機構(gòu)是單服務(wù)臺，先到先服務(wù)，對41個顧客記錄了到達(dá)

9、時刻和服務(wù)時間，如以第1個顧客到達(dá)時刻為0，最后一個顧客到達(dá)這時刻為142，全部服務(wù)時間為127分鐘，通過對原始資料的整理得到“到達(dá)間隔分布表”，“服務(wù)時間分布表”.表9-3 到達(dá)間隔分布表 表9-4 服務(wù)時間分布表到達(dá)間隔（分鐘）次數(shù)服務(wù)時間（分鐘）次數(shù)12345678910以上6108632211123456789以上合計1010754211141合計 402、普阿松流設(shè)N（t）：在時間區(qū)間內(nèi)到達(dá)的顧客數(shù)；：在時間區(qū)間內(nèi)有n個顧客到達(dá)的概率；.當(dāng)符合下列三個條件時，就說顧客的到達(dá)形成普阿松流.（1）在不相重迭的時間區(qū)間內(nèi)顧客到達(dá)數(shù)是相互獨立的，即無后效性；（2）對充分小的內(nèi)有1個顧客到達(dá)的

10、概率與t無關(guān)，而與區(qū)間長成正比，即；（3）對充分小的，在內(nèi)有2個或2個以上顧客到達(dá)的概率極小，可忽略，即.以下研究顧客到達(dá)數(shù)為n的概率分布由（2）取時間總可以由0算起，即；由（2）、（3）知，在內(nèi)沒有顧客到達(dá)的概率.設(shè)在區(qū)間，求有n個顧客到達(dá)的概率，可分成兩個區(qū)間和.分為以下三種情況：表9-5 在區(qū)間內(nèi)有n個顧客到達(dá)的情況 區(qū)間情況個數(shù)概率個數(shù)概率個數(shù)概率ABCnn-1n-2n-300123nnnnnn在內(nèi)達(dá)到n個顧客的概率應(yīng)是表中三個概率之和，即令 0 有 （9.1）當(dāng)n=0時，只有A種情況，有令 0 有 （9.2）由（9.2）得由 （9.1）兩邊乘得n=1 n=2 一般地 t>0 （

11、n=0，1，2，） 隨機變量N(t)服從普阿松分布： 例9.3 某天上午，從10:3011:47.每隔20秒鐘統(tǒng)計一次來到某長途汽車站的乘客數(shù)，共得230個記錄，整理后得到如下表所示的統(tǒng)計結(jié)果.表9-6 乘客分布數(shù)乘客數(shù)目01234頻 數(shù)100813496試用一個泊松過程描述此車站乘客的到達(dá)過程.并具體寫出它的概率分布.解：只要求出l的值即可.先求出20秒鐘內(nèi)到達(dá)顧客的平均數(shù)：每分鐘平均到達(dá)的顧客數(shù)為：（人/分鐘）概率分布為：例9.4 在某個交叉路口觀察了25輛向北行駛的汽車到達(dá)路口的時刻，其記錄如下（開始觀察時刻為0，單位為秒）：表9-7 汽車到達(dá)路口的時刻18121517192743586

12、47072739192101102103105109122123124135137試用一個泊松過程來描述該到達(dá)過程.解：該車流是一個最簡單流.因此汽車相繼到達(dá)的時間間隔相互獨立，服從同一分布負(fù)指數(shù)分布.現(xiàn)在估計負(fù)指數(shù)分布的參數(shù).汽車相繼到達(dá)路口的時間間隔為：174322816156621181911241311112它們的和為137.故平均間隔的估計值為：（秒）從而，=0.1825（輛/秒）所以，服從如下分布的獨立同分布隨機變量族描述了該車流：3、負(fù)指數(shù)分布（1）到達(dá)間隔時間T的分布當(dāng)輸入過程是普阿松流時，研究兩顧客相繼到達(dá)的間隔時間的概率分布，設(shè)T的分布函數(shù)FT(t).則 即為在區(qū)間內(nèi)至少有

13、一個顧客到達(dá)的概率.由于 t>0概率密度 t>0即到達(dá)間隔時間T服從負(fù)指數(shù)分布. 表示單位時間平均到達(dá)的顧客數(shù).表示相繼顧客到達(dá)的平均間隔時間，這與的意義相吻合.如果顧客到達(dá)是普阿松流，則到達(dá)間隔時間必為負(fù)指數(shù)分布，兩者是等價的.（2）服務(wù)時間V的分布對一顧客的服務(wù)時間也即在忙期相繼離開系統(tǒng)的兩顧客的間隔時間，一般地，也服從負(fù)指數(shù)分布.設(shè)它的分布函數(shù)和密度函數(shù)分別為 其中 單位時間能被服務(wù)完的顧客數(shù)，稱為平均服務(wù)率；顧客的平均服務(wù)時間；服務(wù)強度，即相同時間區(qū)間內(nèi)顧客到達(dá)的平均數(shù)與能被服務(wù)的平均數(shù)之比.例9.5 對200只燈炮進(jìn)行壽命檢驗，結(jié)果如表9-8所示.試問燈泡壽命是否服從負(fù)指

14、數(shù)分布？表9-8 燈炮壽命檢驗結(jié)果燈泡壽命（小時）燈泡數(shù)目（m）05005001000100015001500200020002500250030001334515421解：200只燈炮的平均壽命為：故指數(shù)分布的參數(shù) 指數(shù)分布密度函數(shù)為： 現(xiàn)在求落在各組燈泡壽命內(nèi)的燈泡數(shù)目的概率： 計算燈泡壽命的統(tǒng)計概率：0500小時內(nèi)=133/200=0.6655001000=45/200=0.22510001500=15/200=0.07515002000=4/200=0.02020002500=2/200=0.01025003000=1/200=0.005將相應(yīng)的理論概率和統(tǒng)計概率加以比較發(fā)現(xiàn)，它們之間

15、的偏差很小，因而，可以說，燈泡發(fā)光時間服從負(fù)指數(shù)分布.這種方法稱為分布的擬合度檢驗.4、愛爾朗（Erlang）分布設(shè)是k 個相互獨立的隨機變量，服從相同參數(shù)的負(fù)指數(shù)分布，令則T的概率密度為 稱T為服從k階Erlang分布 當(dāng)k=1時，即為負(fù)指數(shù)分布.例如：串列k個服務(wù)臺，每臺服務(wù)時間相互獨立，服從相同的負(fù)指數(shù)分布，那么一顧客走完k個服務(wù)臺總共所需服務(wù)時間就服從上述k階Erlang分布.§3 幾個排隊系統(tǒng)的分析當(dāng)研究系統(tǒng)運行指標(biāo)Ls, Lq, Ws, Wq時，都是以求解系統(tǒng)狀態(tài)為n（有n個顧客）的概率Pn(t)為基礎(chǔ)的.一、（M/M/1模型）（單服務(wù)臺的情形）M/M/1模型指：輸入過程

16、服從普阿松過程，服務(wù)時間服從負(fù)指數(shù)分布，單服務(wù)臺的情形.分三類：(1)標(biāo)準(zhǔn)的M/M/1模型；(2)系統(tǒng)容量有限制(N)；(3)顧客源為有限(m).1、標(biāo)準(zhǔn)的M/M/1模型 標(biāo)準(zhǔn)的M/M/1模型指： 輸入過程：顧客源無限，顧客單個到來，相互獨立，一定時間的到達(dá)數(shù)服從普阿松公布，到達(dá)過程是平穩(wěn)的. 排隊規(guī)則：單隊、隊長無限制，先到先服務(wù). 服務(wù)機構(gòu)：單服務(wù)臺，各顧客的服務(wù)時間相互獨立，服從相同的負(fù)指數(shù)分布.到達(dá)間隔時間和服務(wù)時間相互獨立.(1) 求系統(tǒng)在任意時刻t狀態(tài)為n的概率Pn(t)因為已知到達(dá)服從參數(shù)為的普阿松過程，故有 P中到達(dá)個數(shù)= k， (k = 0,1,2,) P中到達(dá)個數(shù)= 0 P

17、中到達(dá)個數(shù)= 1 P中到達(dá)個數(shù)2 故有 在（）內(nèi)有1個顧客到達(dá)的概率為； 沒有顧客到達(dá)的概率為； 有2個以上顧客到達(dá)的概率為. 又因為服務(wù)時間服從參數(shù)為的負(fù)指數(shù)分布，設(shè)第i個顧客的服務(wù)時間，獨立，同分布，則在（）內(nèi)，當(dāng)有顧客接受服務(wù)時有0個顧客服務(wù)完的概率為： P中服務(wù)完個數(shù)= 0|系統(tǒng)中有顧客= 有1個顧客服務(wù)完了的概率為： 設(shè)：A1系統(tǒng)中有1個顧客；A2系統(tǒng)中有2個以上顧客；B中服務(wù)完個數(shù)= 1. P中服務(wù)完個數(shù)= 1|系統(tǒng)中有顧客=P中服務(wù)完個數(shù)= 1|系統(tǒng)中有1個顧客系統(tǒng)中有2個以上顧客=有2個以上顧客服務(wù)完了的概率為： P中服務(wù)完個數(shù)2|系統(tǒng)中有顧客 =1- P中服務(wù)完個數(shù)= 0|系

18、統(tǒng)中有顧客- P中服務(wù)完個數(shù)= 1|系統(tǒng)中有顧客 =于是，在時刻，系統(tǒng)有n個顧客，有下列四種情況，如表9-9所示.表9-9 在時刻系統(tǒng)有n個顧客的情況情況在時刻t顧客數(shù)在區(qū)間（t，）在時刻顧客數(shù)到達(dá)離去ABCDnn+1n-1n××××nnnn它們的概率為（略去）A：B：C：D：故有 令0，得 (9.3)當(dāng)n = 0時，只有A, B, D三種情況 令有 (9.4)解（9.3）（9.4）的瞬態(tài)解很麻煩，且瞬態(tài)解不便于應(yīng)用，現(xiàn)只研究穩(wěn)態(tài)的情形，由于此時Pn(t)與t無關(guān)，記為Pn. 令 ，故有 由第二式，得 由第一式，令n = 1，得： 故 同理可得 設(shè) （否

19、則隊列將排至無限遠(yuǎn)），又 即 則有 n1 (2) 以下求系統(tǒng)運行指標(biāo)： 系統(tǒng)中的平均顧客數(shù)（隊長期望值） 或 在隊列中等待的平均顧客數(shù)（隊列長期望值）由于是單服務(wù)臺，當(dāng)系統(tǒng)中有1顧客時，隊列中無人等待，有2個顧客時，有1人等待，有3個顧客時，有2人等待，故有 顧客在系統(tǒng)中的逗留時間WS WS=Wq + 服務(wù)時間設(shè)一個顧客進(jìn)入系統(tǒng)時，發(fā)現(xiàn)他前面已有n個顧客在系統(tǒng)中，則他的平均等待時間就是這n個顧客的平均服務(wù)時間的總和.E進(jìn)入系統(tǒng)的顧客的等待時間|X = n=Wq = E進(jìn)入系統(tǒng)的顧客等待時間 綜上所述，得到如下的關(guān)系式 相互關(guān)系為： 例9.6 某醫(yī)院經(jīng)統(tǒng)計，得到病人到達(dá)數(shù)服從參數(shù)為2.1的普阿松

20、分布，手術(shù)時間服從參數(shù)為2.5的負(fù)指數(shù)分布，求1) 在病房中的病人數(shù)（期望值）；2) 排隊等待病人數(shù)（期望值）；3) 病人在病房中逗留時間；4) 病人排隊等待時間.解：1） （人）2） （人）3） （小時）4） （小時）由于，說明服務(wù)機構(gòu)有84%的時間是繁忙的（被利用的），有16%的時間是空閑的.例9.7 為估計某郵局服務(wù)系統(tǒng)的效能，現(xiàn)以3分鐘為一個時段，統(tǒng)計了100個時段中，顧客到達(dá)的情況及對100位顧客的服務(wù)時間，有關(guān)數(shù)據(jù)列于表8-4和表8-5.設(shè)此服務(wù)系統(tǒng)為排隊模型，求系統(tǒng)有關(guān)的數(shù)量指標(biāo).表8-4到達(dá)人數(shù)0 1 2 3 4 5 6時 段 數(shù)14 27 27 18 19 4 1表8-5服務(wù)

21、時間（秒）（0，12）（12，24）（24，36）（36，48）（48，60）（60，72）（72，84）顧客人數(shù)33221510643服務(wù)時間（秒）（84，96）（96,108）（108,120）（120,150）（150,180）（180,200）顧客人數(shù)211111解：先求出每時段內(nèi)到達(dá)顧客的平均數(shù)故顧客的平均到達(dá)率為（顧客/分鐘）再計算每位顧客所需的平均服務(wù)時間，采用表8-5中時間區(qū)間的中值進(jìn)行計算，可得：所以此排隊系統(tǒng)的服務(wù)率=1.89（顧客/分鐘）于是，服務(wù)臺服務(wù)強度為系統(tǒng)的空閑系數(shù)顧客需要等待的概率系統(tǒng)中平均隊伍長度和平均等待隊伍長度分別為（顧客）（顧客）顧客平均逗留時間和平均等

22、待時間分別為（分鐘）（分鐘）服務(wù)臺忙期的平均長度（分鐘）例9.8 設(shè)某醫(yī)生的私人診所平均每隔20分鐘有一位病人前來就診，醫(yī)生給每位病人診斷的時間平均需要15分鐘.現(xiàn)設(shè)它為一個排隊模型.醫(yī)生希望有足夠的座位給來就診的病人坐，使到達(dá)就診的病人站著的概率不超過0.01.試問至少應(yīng)為病人準(zhǔn)備多少個座位（包括醫(yī)生診時病人就座的一個座位）？解：設(shè)為需要的座位數(shù).因而到達(dá)的病人站著的概率于是，應(yīng)要求即要求現(xiàn)在滿足即至少應(yīng)為病人準(zhǔn)備16個座位.2、系統(tǒng)的容量有限制（N）的情形(M/M/1(N)如果系統(tǒng)最大容量為N，對于單服務(wù)臺，排隊等待的顧客最多為N-1，在某時刻，一顧客到達(dá)時，如系統(tǒng)中已有N個顧客，那么這個

23、顧客就被拒絕進(jìn)入系統(tǒng).服務(wù)臺N312被拒絕排隊系統(tǒng)圖9-3 系統(tǒng)的容量有限制的情形當(dāng)N =1時，為即時制；當(dāng)N時，為容量無限制.(1) 求系統(tǒng)在任意時刻t狀態(tài)為n的概率Pn(t)與前類似的考慮，得當(dāng)n = 0時 當(dāng)n = 1,2, n-1時 n =1,2, N-1.當(dāng)n = N時，只有二種情況，如表9-10所示.表9-10 當(dāng)n = N時的情形情況在時刻t顧客數(shù)在區(qū)間（）在時刻顧客數(shù)到達(dá)離去ABNN-1×××NNA：B： 令 0 在穩(wěn)態(tài)情況下 得 令 得 由 即 即 nN故有 (2) 求系統(tǒng)指標(biāo) 注意到此時平均到達(dá)率是在系統(tǒng)中有空時的平均到達(dá)率，當(dāng)系統(tǒng)已滿（n =

24、 N）時，則到達(dá)率為0，需要求出有效到達(dá)率.當(dāng)系統(tǒng)中只要有一個顧客存在，系統(tǒng)必定是繁忙的（被利用的），故 于是 顧客逗留時間（期望值）： 顧客等待時間： 例9.9 單人理發(fā)館有6把椅子接待人們排隊等待理發(fā).當(dāng)6把椅子都坐滿時，后到的顧客不進(jìn)店就離開，顧客平均到達(dá)率為3人/小時，理發(fā)需要時間平均為15分鐘，求：1) 求某顧客一到達(dá)就能理發(fā)的概率，此時相當(dāng)于理發(fā)館內(nèi)無顧客；2) 求需要等待的顧客數(shù)的期望值；3) 求有效到達(dá)率；4) 求一顧客在理發(fā)館內(nèi)逗留的期望時間；5) 在可能到來的顧客中有百分之幾不等待就離開.解：N = 7為系統(tǒng)中最大的顧客數(shù)；=3人/小時，=4人/小時.1） 2） 3） 人/

25、小時4） 小時=43.8分鐘5） 這相當(dāng)于系統(tǒng)中有7個顧客的概率： 例9.10 某汽車加油站只有一臺加油泵，且場地至多只能容納3輛車，當(dāng)站內(nèi)場地占滿車時，到達(dá)的汽車只能去別處加油.輸入為最簡單流，每8分鐘一輛，服務(wù)為負(fù)指數(shù)分布，每4分鐘一輛.加油站有機會租毗鄰的一塊空地，以供多停放一輛前來加油的車，租地費用每周120元，從每個顧客那里期望凈收益10元.設(shè)該站每天開放10小時，問租借場地是否有利？解: 本問題為排隊模型.現(xiàn)在已知分鐘/輛=小時/輛，分鐘/輛=小時/輛，因此，=0.5.于是，到達(dá)顧客損失率若租借場地，則問題成為排隊模型，到達(dá)顧客損失率從而，租借場地后加油站每周可增加的服務(wù)車輛數(shù)為&

26、#215;10小時/天×7天/每周=7.5×（0.067-0.032）×10×7=18.34于是，每周將增加收入10元×18.34=183.4元>120元所以，租借場地是合算的.例9-11 現(xiàn)有服務(wù)系統(tǒng)，其平均到達(dá)率=10人/小時，平均服務(wù)率=30人/小時.管理者想增加收益，擬采用兩個方案，方案A為增加等待空間，取=3；方案B為提高平均服務(wù)率，取=40人/小時.設(shè)對每個顧客服務(wù)的平均收益不變，問哪一個方案將獲得更大的收益？當(dāng)增加到每小時30人，又應(yīng)采用哪一個方案？解: 由于對每個顧客服務(wù)的平均收益不變，因此，服務(wù)機構(gòu)單位時間的平均收益，與

27、單位時間實際進(jìn)入系統(tǒng)的顧客平均數(shù)成正比.所以本問題即為比較兩個方案的有效到達(dá)率.（1）方案A為排隊模型由=10（人/小時），=30人/小時，.故 方案B為排隊模型：由=10（人/小時），=40人/小時，.故 可見，采用方案A能獲得更多的收益.（2）當(dāng)=30人/小時，對方案A來說，此時=1.因此對方案B來說，此時，因此可見，當(dāng)=30人/小時，應(yīng)采用方案B.3、顧客源為有限（m）的情形以機器故障停機待修問題來說明，設(shè)共有m臺機器（總體），機器故障停機表示“到達(dá)”，待修的機器形成隊列，修理工人是服務(wù)員（單服務(wù)員）.特點是，每個顧客到來并經(jīng)過服務(wù)后，仍回到原來總體，仍有可能到來.平均到達(dá)率：無限源情形

28、是按全體顧客考慮的，有限源時必須按每個顧客考慮. 設(shè)每臺機器單位運行時間內(nèi)發(fā)生故障的平均次數(shù).而系統(tǒng)外的顧客平均數(shù)為m -LS，故系統(tǒng)的有效到達(dá)率 服務(wù)臺········顧客源隊列mn圖9-4 顧客源為有限的情形1) 求t時刻有n個顧客的概率在時刻，系統(tǒng)有n個顧客，有下列四種情況，如表9-11所示.表9-11 在時刻系統(tǒng)有n個顧客的情形情況在時刻t顧客數(shù)在區(qū)間（t，）在時刻顧客數(shù)到達(dá)離去ABCDnn+1n-1n××××nnnnA：有1個到達(dá)時，只能從m- n個系統(tǒng)外的顧客中到

29、來，故，而沒有顧客到來的概率為. B：C：D：令 0 1nm-1當(dāng)n = 0時，只有A, B, D三種情況： A： B： D： 令 0 當(dāng)n = m時，只有二種情況，如表9-12所示.表9-12 當(dāng)n = m時的情形情況在時刻t（t，）時刻ABmm-1不離去到達(dá) 不離去mmA：B：令0 令導(dǎo)數(shù)為0，得穩(wěn)態(tài)方程 1nm-1解得 因為 即 故有 （1nm）2) 求系統(tǒng)運行指標(biāo) 例9.12 某車間有5臺機器，每臺機器的連續(xù)運轉(zhuǎn)時間服從負(fù)指數(shù)分布，平均連續(xù)運轉(zhuǎn)時間15分鐘，有一個修理工，每次修理時間服從負(fù)指數(shù)分布，平均每次12分鐘.求：1) 修理工空閑的概率；2) 五臺機器都出故障的概率；3) 出故障

30、的平均臺數(shù)；4) 等待修理的平均臺數(shù)；5) 平均停工時間；6) 平均等待修理時間；7) 評價這些結(jié)果.解：由 m = 5，1） 2） 3） （臺）4） （臺）5） （分）6） （分）7） 機器停工時間過長，修理工幾乎沒有空閑時間，應(yīng)當(dāng)提高服務(wù)率減少修理時間或增加修理工人.二、M/M/C模型（多服務(wù)臺的情形）討論單隊、并列多服務(wù)臺（C個）情形，分三種情況：1) 標(biāo)準(zhǔn)的M/M/C模型；2) 系統(tǒng)容量有限制（N）；3) 有限顧客源（m）.1、標(biāo)準(zhǔn)的M/M/C模型設(shè)各服務(wù)臺工作相互獨立且平均服務(wù)率相同，整個服務(wù)機構(gòu)的平均服務(wù)率為. 隊列服務(wù)臺圖9-5 標(biāo)準(zhǔn)的M/M/C情形1) 求系統(tǒng)狀態(tài)率Pn(t)在

31、時刻，系統(tǒng)有n個顧客，有四種情況，如表9-13所示.表9-13 在時刻系統(tǒng)有n個顧客情況在時刻t顧客數(shù)（t，）顧客數(shù)到達(dá)離去ABCDnn+1n-1n××××nnnn當(dāng)nc時 A：； B：； C：； D：. 令0 當(dāng)1n<c 此時服務(wù)機構(gòu)的平均服務(wù)率視顧客數(shù)而定，設(shè)為，則 A：； B：； C：； D：. 令0 當(dāng)n = 0時，只有A，B，D情況 令0 令導(dǎo)數(shù)為0，得穩(wěn)態(tài)差分方程： （1nc） （nc）解為 當(dāng)1nc n = 1 n = 2 一般有： （n < c）當(dāng)nc 由于 故有 一般地，有 （nc）由于 設(shè) 得 2) 求系統(tǒng)指標(biāo)： 例9.1

32、3 某售票所有三個窗口，顧客到達(dá)服從普阿松過程，平均到達(dá)率每分鐘（人），服務(wù)時間服從負(fù)指數(shù)分布，平均服務(wù)率每分鐘（人），現(xiàn)設(shè)一顧客到達(dá)后排成一隊，依次向空閑的窗口購票.求：(1) 求整個售票所空閑概率(2) 求平均隊長(3) 求平均等待時間和逗留時間(4) 求顧客到達(dá)后必須等待的概率解： C=3 123圖9-6 三個服務(wù)窗口的情形（1） = 0.0748 （2） （3） （分） （分）（4） 以下就M/M/C系統(tǒng)與c個M/M/1系統(tǒng)作一比較.就上例說明，設(shè)顧客到達(dá)后在每個窗口前各排一隊，且進(jìn)入隊列后堅持不換，這就形成3個隊列.123圖9-6 三個服務(wù)窗口的情形每個隊列的平均到達(dá)率為 現(xiàn)按M/M

33、/1解此問題，與原來的M/M/3比較如下表所示.表9-14 M/M/1模型與M/M/3模型的比較 模 型指 標(biāo)1) M/M/3型2) M/M/1型服務(wù)臺空閑的概率P0顧客必須等待的概率平均隊列長Lq平均隊長LS平均逗留時間WS平均等待時間Wq0.07480.571.703.954.391.890.25（每個子系統(tǒng)）0.752.25（每個子系統(tǒng)）9.00（整個系統(tǒng)）107.5例9.14 某超級市場，顧客從貨架上挑選各類商品，出門前到柜臺前付款.現(xiàn)有兩個收款柜臺，若都不空閑，顧客就排成一隊，否則，顧客可在任一個柜臺付款.設(shè)此服務(wù)系統(tǒng)是排隊模型.為了估計該系統(tǒng)的效能，現(xiàn)在柜臺前作了如下統(tǒng)計：以兩分鐘

34、作為一個時段，依次記下各個時段里來到的顧客數(shù)，并記下了這些顧客在柜臺旁付款所花費的時間.下面給出有關(guān)數(shù)據(jù)：(a)顧客來到數(shù)：在相繼的26個時段里依次來到付款柜臺前的顧客數(shù)為：1 3 0 1 0 0 1 1 2 1 0 1 3 2 5 1 2 2 1 0 0 1 0 3 3 1(b)付款時間（分：秒）：4:35，3:02，5:27，4:33，2:35，1:45，0:15，3:45，0:15，4:20，2:39，4:51，5:45，0:23，2:30，3:26，1:48，1:16，1:24，4:17，3:07，1:40，5:53，2:31，3:28，0:54，0:38，6:55，1:33，6:20

35、，0:59，2:03，1:29，5:24，3:50.試估計該系統(tǒng)的效能.解：由已知數(shù)據(jù)可知每時段（2分鐘）平均到來顧客，從而，該普阿松流的參數(shù)（顧客/分鐘）顧客的平均服務(wù)時間（分鐘）于是，該負(fù)指數(shù)分布的參數(shù)（顧客/分鐘）本問題為排隊模型，所以它表明這一系統(tǒng)運營一段時間后，系統(tǒng)中的顧客隊伍長度會趨于無窮大為了使這系統(tǒng)能趨于穩(wěn)定，現(xiàn)增設(shè)一個付款柜臺，于是，問題成為排隊模型，因此有由式（8-22）和（8-23）知：顧客到達(dá)系統(tǒng)后必須等待的概率系統(tǒng)中顧客平均等待隊長（顧客）.系統(tǒng)中顧客平均隊長（顧客）顧客平均等待時間（分鐘）顧客平均逗留時間（分鐘）柜臺的利用率為0.678，系統(tǒng)的空閑系數(shù)為0.106.

36、2、系統(tǒng)的容量有限制（N）的情形設(shè)系統(tǒng)的容量最大限制為N（c），當(dāng)系統(tǒng)中顧客數(shù)n已達(dá)到N（即隊列中顧客數(shù)已達(dá)N- c）時，再來的顧客即被拒絕，其他條件與標(biāo)準(zhǔn)的M/M/C相同.1) 求系統(tǒng)狀態(tài)概率Pn與M/M/C標(biāo)準(zhǔn)情況類似，得到 （1n<c） （cnN-1）當(dāng)n = N時，只有二種情況，如表9-15所示.表9-15 當(dāng)n = N時的情形情況時刻t顧客數(shù)（t，）顧客數(shù)到達(dá)離去ABNN-1××NNA：B：+ +于是得： （1n<c） （cnN-1） （n=N）與前同，解得： （0n<c） （cnN-1） （cnN）（0nc）于是有 由 即 當(dāng)時，由前面的差分方

37、程為： （1n<c） （cnN-1） （n=N）解得： （0n<c）n = c-1 cPc-cPc-1+Pc-2 = 0n = c cPc+1-(1+c)Pc+Pc-1 = 0 n = c+1 cPc+2-(1+c)Pc+1+Pc = 0 （cnN-1）n=N （n=N）于是有，當(dāng)時，有（0nc）（cnN-1） 因為 2) 求系統(tǒng)指標(biāo) 顧客到達(dá)而能進(jìn)入系統(tǒng)的概率為，故系統(tǒng)的有效到達(dá)率為. 特別，當(dāng)N=c（即時制）時，例如，停車場不允許排隊等待空位，此時， （0nc） 例9.15 某火車站的電話問訊處設(shè)有三個電話，平均每隔2分鐘有一次問訊電話（包括接通的和未接通的），每次通話的平均時

38、間為3分鐘，試問打到問訊處的電話能接通的概率為多少？解：M/M/3（3）模型 接通的概率為1-P3 = 0.8663、顧客源為有限（m）的情形設(shè)顧客總體為有限數(shù)m，m > c.顧客到達(dá)率按每個顧客來考慮.考慮機器管理問題，共有m臺機器，有c個修理工人，每臺機器每單位運轉(zhuǎn)時間出故障的期望次數(shù)，n是出故障的機器臺數(shù).當(dāng)nc時，所有的故障機器都在被修理，有（c- n）個工人空閑；當(dāng)c<nm時，有（n - c）臺機器在停機待修，工人均繁忙.設(shè)c個工人修理技術(shù)相同，服從參數(shù)為的負(fù)指數(shù)分布.1) 求t時刻系統(tǒng)狀態(tài)概率在，系統(tǒng)有n個顧客，有下列情況，如表9-16所示.表9-16 在系統(tǒng)有n個顧客

39、的情形情況t時刻顧客數(shù)（t，）時刻顧客數(shù)到達(dá)離去ABCDnn+1n-1n××××nnnn當(dāng)1<nc，此時服務(wù)機構(gòu)的平均服務(wù)率視顧客數(shù)而定，設(shè)為，由于到達(dá)是從m- n個顧客中到達(dá)，故.A：B：C：D： 當(dāng)n = 0時，只有A, B, D三種情況： 當(dāng)c+1n<m時，此時服務(wù)機構(gòu)的平均服務(wù)率為，顧客到達(dá)率仍為.A：B：C：D：當(dāng)n=m時，只有兩種情況，如表9-17所示.表9-17 當(dāng)n=m時的情形情況時刻t （t，）時刻 ABmm-1不離去到達(dá) 不離去mm A： B： 故得穩(wěn)態(tài)下的差分方程： 1nc cnm nm 1nc 1nccnm cnmn=

40、m (0nc)(c+1nm)故有 由于 其中 2) 求系統(tǒng)指標(biāo) 而 可以證明：證明： 故有 例9-16 設(shè)有2個修理工人，負(fù)責(zé)5臺機器的正常運行，每臺機器平均損壞率為每運轉(zhuǎn)小時1次，兩工人能以相同的平均修復(fù)率4（次/小時）修好機器，求：1) 等待修理的機器平均數(shù) =0.3149P1 = 0.394 P2 = 0.197 P3 = 0.074 P4 = 0.018 P5 = 0.002 2) 需要修理的機器平均數(shù) 3) 有效損壞率 4) 等待修理時間 小時5) 停工時間 小時§4 M/G/1模型（一般服務(wù)時間）考慮輸入為普阿松過程，服務(wù)時間為任意分布的情形.由于 服務(wù)時間 1、PK公式

41、：對于M/G/1，服務(wù)時間T的分布是一般的，E(T)和VarT存在，.其它條件與標(biāo)準(zhǔn)的M/M/1相同.可以證明（從略），有 例9.17 有一汽車沖洗臺，來沖洗的汽車按平均每小時18輛的普阿松分布到達(dá)，沖洗時間T根據(jù)過去經(jīng)驗表明ET=0.05小時/輛，VarT=0.01(小時/輛)2，求各運行指標(biāo)并對服務(wù)機構(gòu)評價.解： （輛） （小時） （小時） Lq = 18 × 1.125 = 20.25（輛）由于，即平時等待時間是服務(wù)時間的22.5倍，此服務(wù)機構(gòu)難以令人滿意.2、定長服務(wù)時間M/D/1模型一條裝配線上完成一件工作的時間是常數(shù)，自動汽車沖洗臺，沖洗一輛汽車的時間也是常數(shù)，此時 例9.18 某實驗室有一臺自動檢驗機器性能的儀器，要求檢驗機器的顧客按普阿松分布到達(dá)，每小時平均4個顧客，檢驗每臺機器所需時間為6分