第11章排隊(duì)論

1、第第11章章 排隊(duì)論排隊(duì)論重慶三峽學(xué)院重慶三峽學(xué)院 關(guān)文忠關(guān)文忠http:/ 【知識(shí)結(jié)構(gòu)】【知識(shí)結(jié)構(gòu)】導(dǎo)入案例：主任醫(yī)師招聘問題導(dǎo)入案例：主任醫(yī)師招聘問題某三甲醫(yī)院肝膽內(nèi)科有主任醫(yī)師某三甲醫(yī)院肝膽內(nèi)科有主任醫(yī)師1名，由于他的存在而使前來診療的患名，由于他的存在而使前來診療的患者大增。根據(jù)一個(gè)月的統(tǒng)計(jì)，平均每者大增。根據(jù)一個(gè)月的統(tǒng)計(jì)，平均每h到達(dá)醫(yī)院的患者到達(dá)醫(yī)院的患者6名，并對(duì)各時(shí)名，并對(duì)各時(shí)間段統(tǒng)計(jì)，經(jīng)回歸符合泊松分布；該醫(yī)生每間段統(tǒng)計(jì)，經(jīng)回歸符合泊松分布；該醫(yī)生每h可診療可診療4名，但患者病情名，但患者病情不同，分布也不是均勻的，對(duì)每位患者就診時(shí)間的統(tǒng)計(jì)，經(jīng)回歸，符合不同，分布也不是均勻的

2、，對(duì)每位患者就診時(shí)間的統(tǒng)計(jì)，經(jīng)回歸，符合指數(shù)分布。指數(shù)分布。醫(yī)院配備有電子回饋信息系統(tǒng)，及時(shí)觀察到已掛號(hào)排隊(duì)等候的患者數(shù)量。醫(yī)院配備有電子回饋信息系統(tǒng)，及時(shí)觀察到已掛號(hào)排隊(duì)等候的患者數(shù)量。當(dāng)排隊(duì)等候人數(shù)少于當(dāng)排隊(duì)等候人數(shù)少于5人時(shí)，掛號(hào)系統(tǒng)可以掛號(hào)。當(dāng)前來就診的患者掛人時(shí)，掛號(hào)系統(tǒng)可以掛號(hào)。當(dāng)前來就診的患者掛上號(hào)若醫(yī)生空閑則可直接就診，否則排隊(duì)等候。醫(yī)生采取先到先服務(wù)的上號(hào)若醫(yī)生空閑則可直接就診，否則排隊(duì)等候。醫(yī)生采取先到先服務(wù)的規(guī)則。若前來就診的患者掛不上號(hào)，則立即到鄰近的一家醫(yī)院就診。規(guī)則。若前來就診的患者掛不上號(hào)，則立即到鄰近的一家醫(yī)院就診。經(jīng)統(tǒng)計(jì)，經(jīng)該主任醫(yī)師診療的患者，其診療費(fèi)、檢驗(yàn)

3、費(fèi)、醫(yī)藥費(fèi)等醫(yī)院經(jīng)統(tǒng)計(jì)，經(jīng)該主任醫(yī)師診療的患者，其診療費(fèi)、檢驗(yàn)費(fèi)、醫(yī)藥費(fèi)等醫(yī)院可獲純收入可獲純收入100元；主任醫(yī)師可高薪聘請(qǐng)，其薪金及住房和各種福利年元；主任醫(yī)師可高薪聘請(qǐng)，其薪金及住房和各種福利年均均25萬元，醫(yī)院實(shí)行每周萬元，醫(yī)院實(shí)行每周5天工作制，年工作日天工作制，年工作日250天，平均每天支付天，平均每天支付1000元的成本。當(dāng)醫(yī)生過少，由于患者得不到服務(wù)離去而產(chǎn)生的損失元的成本。當(dāng)醫(yī)生過少，由于患者得不到服務(wù)離去而產(chǎn)生的損失增加；當(dāng)醫(yī)生過多，由于醫(yī)生空閑時(shí)間的增加也使醫(yī)院的成本增加。問：增加；當(dāng)醫(yī)生過多，由于醫(yī)生空閑時(shí)間的增加也使醫(yī)院的成本增加。問：醫(yī)院應(yīng)招聘多少名肝膽內(nèi)科主任醫(yī)師

4、可使得盈利最大？醫(yī)院應(yīng)招聘多少名肝膽內(nèi)科主任醫(yī)師可使得盈利最大？導(dǎo)入案例：主任醫(yī)師招聘問題導(dǎo)入案例：主任醫(yī)師招聘問題此類排隊(duì)現(xiàn)象在日常生活中經(jīng)常遇到，如客戶到銀行排隊(duì)辦理存貸款業(yè)此類排隊(duì)現(xiàn)象在日常生活中經(jīng)常遇到，如客戶到銀行排隊(duì)辦理存貸款業(yè)務(wù)，出納員為客戶提供服務(wù)；汽車到加油站排隊(duì)，加注系統(tǒng)為汽車提供務(wù)，出納員為客戶提供服務(wù)；汽車到加油站排隊(duì)，加注系統(tǒng)為汽車提供加油服務(wù)；超市顧客到收銀臺(tái)前排隊(duì)，收款員為顧客提供交款服務(wù)；旅加油服務(wù)；超市顧客到收銀臺(tái)前排隊(duì)，收款員為顧客提供交款服務(wù)；旅客到公交車站排隊(duì)，公交車為旅客提供位移服務(wù)?？偷焦卉囌九抨?duì)，公交車為旅客提供位移服務(wù)。排隊(duì)論的基本思想是排隊(duì)論

5、的基本思想是1910年丹麥電話工程師年丹麥電話工程師A.K.埃爾朗在解決自動(dòng)電埃爾朗在解決自動(dòng)電話設(shè)計(jì)問題時(shí)開始形成的，當(dāng)時(shí)稱為話務(wù)理論。他在熱力學(xué)統(tǒng)計(jì)平衡理話設(shè)計(jì)問題時(shí)開始形成的，當(dāng)時(shí)稱為話務(wù)理論。他在熱力學(xué)統(tǒng)計(jì)平衡理論的啟發(fā)下，成功地建立了電話統(tǒng)計(jì)平衡模型，并由此得到一組遞推狀論的啟發(fā)下，成功地建立了電話統(tǒng)計(jì)平衡模型，并由此得到一組遞推狀態(tài)方程，從而導(dǎo)出著名的埃爾朗電話損失率公式。態(tài)方程，從而導(dǎo)出著名的埃爾朗電話損失率公式。自自20世紀(jì)初以來，電話系統(tǒng)的設(shè)計(jì)一直在應(yīng)用這個(gè)公式。世紀(jì)初以來，電話系統(tǒng)的設(shè)計(jì)一直在應(yīng)用這個(gè)公式。20世紀(jì)世紀(jì)30年年代前蘇聯(lián)數(shù)學(xué)家欣欽把處于統(tǒng)計(jì)平衡的電話呼叫流稱為

6、最簡單流；瑞典代前蘇聯(lián)數(shù)學(xué)家欣欽把處于統(tǒng)計(jì)平衡的電話呼叫流稱為最簡單流；瑞典數(shù)學(xué)家巴爾姆又引入有限后效流等概念和定義；美國數(shù)學(xué)家費(fèi)勒數(shù)學(xué)家巴爾姆又引入有限后效流等概念和定義；美國數(shù)學(xué)家費(fèi)勒(W.Feller)關(guān)于生滅過程的研究；關(guān)于生滅過程的研究；20世紀(jì)世紀(jì)50年代初，英國數(shù)學(xué)家年代初，英國數(shù)學(xué)家D.G.肯肯德爾提出嵌入馬爾可夫鏈理論，以及對(duì)排隊(duì)隊(duì)型的分類方法，為排隊(duì)論德爾提出嵌入馬爾可夫鏈理論，以及對(duì)排隊(duì)隊(duì)型的分類方法，為排隊(duì)論奠定了理論基礎(chǔ)；奠定了理論基礎(chǔ)；20世紀(jì)世紀(jì)70年代以來，人們開始研究排隊(duì)網(wǎng)絡(luò)和復(fù)雜年代以來，人們開始研究排隊(duì)網(wǎng)絡(luò)和復(fù)雜排隊(duì)問題的漸近解等，成為研究現(xiàn)代排隊(duì)論的新趨

7、勢。排隊(duì)問題的漸近解等，成為研究現(xiàn)代排隊(duì)論的新趨勢。本章主要內(nèi)容本章主要內(nèi)容11.1 基本概念基本概念11.1.1 排隊(duì)系統(tǒng)的一般表示排隊(duì)系統(tǒng)的一般表示11.1.2 排隊(duì)系統(tǒng)的三個(gè)特征排隊(duì)系統(tǒng)的三個(gè)特征11.1.3 排隊(duì)系統(tǒng)模型的分類排隊(duì)系統(tǒng)模型的分類11.1.4 排隊(duì)系統(tǒng)的主要性能指標(biāo)排隊(duì)系統(tǒng)的主要性能指標(biāo)11.1.5 排隊(duì)系統(tǒng)的輸入和輸出排隊(duì)系統(tǒng)的輸入和輸出11.2 生死過程生死過程11.3 單服務(wù)臺(tái)排隊(duì)系統(tǒng)模型單服務(wù)臺(tái)排隊(duì)系統(tǒng)模型11.3.1 M/M/1/（標(biāo)準(zhǔn)系統(tǒng)）（標(biāo)準(zhǔn)系統(tǒng)）11.3.2 M/M/1/N/（系統(tǒng)容量有限）（系統(tǒng)容量有限）11.3.3 M/M/1/m（顧客源有限）（顧客

8、源有限）11.4 多服務(wù)臺(tái)排隊(duì)系統(tǒng)模型多服務(wù)臺(tái)排隊(duì)系統(tǒng)模型11.4.1 M/M/s/系統(tǒng)系統(tǒng)11.4.2 M/M/s/N/系統(tǒng)系統(tǒng)11.4.3 M/M/s/m系統(tǒng)系統(tǒng)11.5 其他排隊(duì)系統(tǒng)模型其他排隊(duì)系統(tǒng)模型11.5.1 一般服務(wù)時(shí)間一般服務(wù)時(shí)間M/G/1模型模型11.5.2 定長服務(wù)時(shí)間定長服務(wù)時(shí)間M/D/1模型模型11.5.3 埃爾朗服務(wù)時(shí)間埃爾朗服務(wù)時(shí)間M/Ek/1模型模型11.5.3 具有優(yōu)先服務(wù)權(quán)的排隊(duì)具有優(yōu)先服務(wù)權(quán)的排隊(duì)模型模型11.6 排隊(duì)系統(tǒng)的優(yōu)化排隊(duì)系統(tǒng)的優(yōu)化11.6.1 M/M/1模型中的最優(yōu)服務(wù)模型中的最優(yōu)服務(wù)率率11.6.2 M/M/s模型中的最優(yōu)服務(wù)模型中的最優(yōu)服務(wù)臺(tái)

9、數(shù)臺(tái)數(shù)本章小結(jié)本章小結(jié)11.1.1 排隊(duì)系統(tǒng)的一般表示排隊(duì)系統(tǒng)的一般表示11.1.2 排隊(duì)系統(tǒng)的三個(gè)特征排隊(duì)系統(tǒng)的三個(gè)特征排除系統(tǒng)的三個(gè)特征是指：輸入過程、排隊(duì)規(guī)則、服務(wù)機(jī)構(gòu)。排除系統(tǒng)的三個(gè)特征是指：輸入過程、排隊(duì)規(guī)則、服務(wù)機(jī)構(gòu)。1輸入過程輸入過程輸入是指顧客到達(dá)服務(wù)系統(tǒng)的情況?？赡苡邢铝星闆r，但并不相互排斥：輸入是指顧客到達(dá)服務(wù)系統(tǒng)的情況?？赡苡邢铝星闆r，但并不相互排斥：（1）按顧客源總數(shù)劃分為有限和無限兩大類。如工廠需要檢修的機(jī)器是有）按顧客源總數(shù)劃分為有限和無限兩大類。如工廠需要檢修的機(jī)器是有限的，準(zhǔn)備進(jìn)京觀光旅游的游客是無限的。限的，準(zhǔn)備進(jìn)京觀光旅游的游客是無限的。（2）按顧客到達(dá)的人

10、數(shù)可以劃分為單個(gè)到達(dá)和成批到達(dá)。如到超市購買商）按顧客到達(dá)的人數(shù)可以劃分為單個(gè)到達(dá)和成批到達(dá)。如到超市購買商品的顧客是單個(gè)的，到港國際航班等待安檢的旅客是成批的。品的顧客是單個(gè)的，到港國際航班等待安檢的旅客是成批的。（3）按顧客到達(dá)時(shí)間間隔是否固定可以劃分為確定型和隨機(jī)型。如定期運(yùn)）按顧客到達(dá)時(shí)間間隔是否固定可以劃分為確定型和隨機(jī)型。如定期運(yùn)行的班車、班輪、班機(jī)是確定的，到加油站加油的汽車是隨機(jī)的。對(duì)隨機(jī)行的班車、班輪、班機(jī)是確定的，到加油站加油的汽車是隨機(jī)的。對(duì)隨機(jī)的顧客到達(dá)需要知道單位時(shí)間到達(dá)的顧客數(shù)或時(shí)間間隔的概率分布。的顧客到達(dá)需要知道單位時(shí)間到達(dá)的顧客數(shù)或時(shí)間間隔的概率分布。（4）按

11、接受過服務(wù)的顧客對(duì)顧客到達(dá)數(shù)是否有影響，劃分為相互獨(dú)立到達(dá)）按接受過服務(wù)的顧客對(duì)顧客到達(dá)數(shù)是否有影響，劃分為相互獨(dú)立到達(dá)和非相互獨(dú)立到達(dá)。如提供優(yōu)質(zhì)服務(wù)的餐飲業(yè)所產(chǎn)生了大量和非相互獨(dú)立到達(dá)。如提供優(yōu)質(zhì)服務(wù)的餐飲業(yè)所產(chǎn)生了大量“回頭客回頭客”，就屬于非相互獨(dú)立到達(dá)。我們只討論獨(dú)立到達(dá)情況。就屬于非相互獨(dú)立到達(dá)。我們只討論獨(dú)立到達(dá)情況。（5）按顧客相繼到達(dá)間隔時(shí)間的分布及其數(shù)字特征是否與時(shí)間有關(guān)可分為）按顧客相繼到達(dá)間隔時(shí)間的分布及其數(shù)字特征是否與時(shí)間有關(guān)可分為平穩(wěn)與非平穩(wěn)的。相繼到達(dá)的間隔時(shí)間分布及其數(shù)學(xué)期望、方差等數(shù)字特平穩(wěn)與非平穩(wěn)的。相繼到達(dá)的間隔時(shí)間分布及其數(shù)學(xué)期望、方差等數(shù)字特征都與時(shí)間

12、無關(guān)，稱為平穩(wěn)的，否則是非平穩(wěn)的。一般非平穩(wěn)情況的數(shù)學(xué)征都與時(shí)間無關(guān)，稱為平穩(wěn)的，否則是非平穩(wěn)的。一般非平穩(wěn)情況的數(shù)學(xué)處理很困難，我們只討論平穩(wěn)狀況。處理很困難，我們只討論平穩(wěn)狀況。11.1.2 排隊(duì)系統(tǒng)的三個(gè)特征排隊(duì)系統(tǒng)的三個(gè)特征2排隊(duì)規(guī)則排隊(duì)規(guī)則排隊(duì)規(guī)則指到達(dá)排隊(duì)系統(tǒng)的顧客按怎樣的規(guī)則排隊(duì)等待。排隊(duì)規(guī)則指到達(dá)排隊(duì)系統(tǒng)的顧客按怎樣的規(guī)則排隊(duì)等待。（1）按顧客到達(dá)排隊(duì)系統(tǒng)時(shí)發(fā)現(xiàn)服務(wù)設(shè)施已被占用是否離去可分為損失制，）按顧客到達(dá)排隊(duì)系統(tǒng)時(shí)發(fā)現(xiàn)服務(wù)設(shè)施已被占用是否離去可分為損失制，等待制和混合制三種。當(dāng)顧客到達(dá)時(shí)，所有的服務(wù)臺(tái)均被占用，顧客隨即等待制和混合制三種。當(dāng)顧客到達(dá)時(shí)，所有的服務(wù)臺(tái)均被占用

13、，顧客隨即離去，稱為損失制（或稱即時(shí)制、消失制）；當(dāng)顧客到達(dá)時(shí)，所有的服務(wù)離去，稱為損失制（或稱即時(shí)制、消失制）；當(dāng)顧客到達(dá)時(shí)，所有的服務(wù)臺(tái)均被占用，顧客就排隊(duì)等待，直到接受完服務(wù)才離去，稱為等待制，例臺(tái)均被占用，顧客就排隊(duì)等待，直到接受完服務(wù)才離去，稱為等待制，例如出故障的機(jī)器排隊(duì)等待維修就是這種情況；介于損失制和等待制之間的如出故障的機(jī)器排隊(duì)等待維修就是這種情況；介于損失制和等待制之間的是混合制。是混合制。對(duì)于等待制，有下列服務(wù)規(guī)則：先到先服務(wù)（對(duì)于等待制，有下列服務(wù)規(guī)則：先到先服務(wù)（FCFS） 、先到后服務(wù)、先到后服務(wù)（LCFS） 、帶優(yōu)先服務(wù)權(quán)（、帶優(yōu)先服務(wù)權(quán)（PR） 、隨機(jī)服務(wù)（、隨

14、機(jī)服務(wù)（SIRO）等。）等。在后面研究的問題中均假設(shè)采取在后面研究的問題中均假設(shè)采取FCFS服務(wù)規(guī)則。服務(wù)規(guī)則。（2）按隊(duì)列長度是否有限，可分為隊(duì)長有限和隊(duì)長無限兩種情況。在限度）按隊(duì)列長度是否有限，可分為隊(duì)長有限和隊(duì)長無限兩種情況。在限度以內(nèi)就排隊(duì)等待，超過一定限度就離去。以內(nèi)就排隊(duì)等待，超過一定限度就離去。（3）按排隊(duì)方式分為單列、多列。對(duì)于多列排隊(duì)的顧客有的可以相互轉(zhuǎn)移，）按排隊(duì)方式分為單列、多列。對(duì)于多列排隊(duì)的顧客有的可以相互轉(zhuǎn)移，有的則不能（用欄桿等隔開）；有的排隊(duì)顧客因等候時(shí)間過長而離開，有有的則不能（用欄桿等隔開）；有的排隊(duì)顧客因等候時(shí)間過長而離開，有的則不能（如在高速公路行駛的

15、汽車必須堅(jiān)持到高速出口）。我們所討論的則不能（如在高速公路行駛的汽車必須堅(jiān)持到高速出口）。我們所討論的問題限制在隊(duì)列間不能相互轉(zhuǎn)移，中途不能退出的情形。的問題限制在隊(duì)列間不能相互轉(zhuǎn)移，中途不能退出的情形。11.1.2 排隊(duì)系統(tǒng)的三個(gè)特征排隊(duì)系統(tǒng)的三個(gè)特征3服務(wù)機(jī)構(gòu)服務(wù)機(jī)構(gòu)從機(jī)構(gòu)形式和工作情況來看有以下幾種：從機(jī)構(gòu)形式和工作情況來看有以下幾種：（1）服務(wù)機(jī)構(gòu)可以沒有服務(wù)員，也可以有一個(gè)或多個(gè)服務(wù)員）服務(wù)機(jī)構(gòu)可以沒有服務(wù)員，也可以有一個(gè)或多個(gè)服務(wù)員（服務(wù)臺(tái)、窗口）。如超市的貨架可以沒有服務(wù)員，但交款時(shí)可（服務(wù)臺(tái)、窗口）。如超市的貨架可以沒有服務(wù)員，但交款時(shí)可能有多個(gè)服務(wù)員。能有多個(gè)服務(wù)員。（2）多

16、個(gè)服務(wù)臺(tái)的情況中，可以是平行排列的（并聯(lián)），也可）多個(gè)服務(wù)臺(tái)的情況中，可以是平行排列的（并聯(lián)），也可以是前后排列的（串聯(lián)），也可以是混合的。以是前后排列的（串聯(lián)），也可以是混合的。（3）服務(wù)方式可以對(duì)單個(gè)顧客進(jìn)行，也可成批進(jìn)行。我們只討）服務(wù)方式可以對(duì)單個(gè)顧客進(jìn)行，也可成批進(jìn)行。我們只討論單個(gè)服務(wù)情況。論單個(gè)服務(wù)情況。（4）服務(wù)時(shí)間可分為確定型的和隨機(jī)型的。如旅客列車對(duì)乘客）服務(wù)時(shí)間可分為確定型的和隨機(jī)型的。如旅客列車對(duì)乘客的服務(wù)是按列車時(shí)刻表進(jìn)行位移服務(wù)的，是確定型的；因患者病的服務(wù)是按列車時(shí)刻表進(jìn)行位移服務(wù)的，是確定型的；因患者病情不同，醫(yī)生診斷的時(shí)間不是確定的，是隨機(jī)型的。情不同，醫(yī)生診

17、斷的時(shí)間不是確定的，是隨機(jī)型的。（5）服務(wù)時(shí)間的分布總假定是平穩(wěn)的，即分布的期望值、方差）服務(wù)時(shí)間的分布總假定是平穩(wěn)的，即分布的期望值、方差等參數(shù)不受時(shí)間的影響。等參數(shù)不受時(shí)間的影響。S S1 S2 S3 S1 S2 S3 S1 S2 S1 S2 S3 S4 S5 (a)單臺(tái)單隊(duì) (b)多隊(duì)多臺(tái)并聯(lián) (c)單隊(duì)多臺(tái)并聯(lián) (d)單隊(duì)多臺(tái)串聯(lián) (e)多臺(tái)混合 11.1.3 排隊(duì)系統(tǒng)模型的分類排隊(duì)系統(tǒng)模型的分類肯德爾（肯德爾（Kendall）于）于1953年提出了排隊(duì)服務(wù)系統(tǒng)的分類記號(hào)年提出了排隊(duì)服務(wù)系統(tǒng)的分類記號(hào) ： 輸入輸入/輸出輸出/并聯(lián)的服務(wù)站數(shù)并聯(lián)的服務(wù)站數(shù)1971年國際排隊(duì)符號(hào)標(biāo)準(zhǔn)會(huì)上肯

18、德爾將上述分類記號(hào)擴(kuò)充到六項(xiàng)，記年國際排隊(duì)符號(hào)標(biāo)準(zhǔn)會(huì)上肯德爾將上述分類記號(hào)擴(kuò)充到六項(xiàng)，記為：輸入為：輸入/輸出輸出/并聯(lián)的服務(wù)站數(shù)并聯(lián)的服務(wù)站數(shù)/系統(tǒng)容量（隊(duì)長）系統(tǒng)容量（隊(duì)長）/系統(tǒng)狀態(tài)（顧客源數(shù)）系統(tǒng)狀態(tài)（顧客源數(shù)）/服務(wù)規(guī)則服務(wù)規(guī)則11.1.4 排隊(duì)系統(tǒng)的主要性能指標(biāo)排隊(duì)系統(tǒng)的主要性能指標(biāo) 求解排隊(duì)問題的目的，是研究排隊(duì)系統(tǒng)運(yùn)行的效率，估計(jì)服務(wù)質(zhì)量，確求解排隊(duì)問題的目的，是研究排隊(duì)系統(tǒng)運(yùn)行的效率，估計(jì)服務(wù)質(zhì)量，確定系統(tǒng)參數(shù)的最優(yōu)值，以決定系統(tǒng)結(jié)構(gòu)是否合理、研究設(shè)計(jì)改進(jìn)措施等。定系統(tǒng)參數(shù)的最優(yōu)值，以決定系統(tǒng)結(jié)構(gòu)是否合理、研究設(shè)計(jì)改進(jìn)措施等。因此必須確定用以判斷系統(tǒng)運(yùn)行優(yōu)劣的基本數(shù)量指標(biāo)。因

19、此必須確定用以判斷系統(tǒng)運(yùn)行優(yōu)劣的基本數(shù)量指標(biāo)。1常用指標(biāo)常用指標(biāo)（1）隊(duì)長（）隊(duì)長（Ls）和排隊(duì)長（）和排隊(duì)長（Lq）：隊(duì)長指系統(tǒng)內(nèi)顧客數(shù)，包括正在接）：隊(duì)長指系統(tǒng)內(nèi)顧客數(shù)，包括正在接受服務(wù)的顧客與排隊(duì)等待服務(wù)的顧客數(shù)（排隊(duì)長），即受服務(wù)的顧客與排隊(duì)等待服務(wù)的顧客數(shù)（排隊(duì)長），即系統(tǒng)中的顧客數(shù)系統(tǒng)中的顧客數(shù)=排隊(duì)等候服務(wù)的顧客數(shù)排隊(duì)等候服務(wù)的顧客數(shù) + 正在接受服務(wù)的顧客數(shù)正在接受服務(wù)的顧客數(shù)（2）逗留時(shí)間（）逗留時(shí)間（Ws）和等待時(shí)間（）和等待時(shí)間（Wq）：逗留時(shí)間指顧客在排隊(duì)服）：逗留時(shí)間指顧客在排隊(duì)服務(wù)系統(tǒng)中從進(jìn)入到服務(wù)完畢離去的平均逗留時(shí)間；等待時(shí)間指顧客排隊(duì)務(wù)系統(tǒng)中從進(jìn)入到服務(wù)完畢離

20、去的平均逗留時(shí)間；等待時(shí)間指顧客排隊(duì)等待服務(wù)的平均等待時(shí)間。這對(duì)顧客來講是最關(guān)心的，每個(gè)顧客希望逗等待服務(wù)的平均等待時(shí)間。這對(duì)顧客來講是最關(guān)心的，每個(gè)顧客希望逗留時(shí)間或等待時(shí)間越短越好。留時(shí)間或等待時(shí)間越短越好。（3）服務(wù)機(jī)構(gòu)工作強(qiáng)度：指服務(wù)機(jī)構(gòu)累計(jì)的工作時(shí)間占全部時(shí)間的比）服務(wù)機(jī)構(gòu)工作強(qiáng)度：指服務(wù)機(jī)構(gòu)累計(jì)的工作時(shí)間占全部時(shí)間的比例，是衡量服務(wù)機(jī)構(gòu)利用效率的指標(biāo)。即：例，是衡量服務(wù)機(jī)構(gòu)利用效率的指標(biāo)。即：1服務(wù)機(jī)構(gòu)用于服務(wù)顧客的時(shí)間服務(wù)設(shè)施總的空閑時(shí)間工作強(qiáng)度服務(wù)設(shè)施總的服務(wù)時(shí)間服務(wù)設(shè)施總的服務(wù)時(shí)間11.1.4 排隊(duì)系統(tǒng)的主要性能指標(biāo)排隊(duì)系統(tǒng)的主要性能指標(biāo) 2指標(biāo)間的關(guān)系指標(biāo)間的關(guān)系設(shè)：設(shè)：表

21、示單位時(shí)間內(nèi)表示單位時(shí)間內(nèi)顧客的平均到達(dá)數(shù)，則顧客的平均到達(dá)數(shù)，則1/表示相鄰兩個(gè)顧客表示相鄰兩個(gè)顧客到達(dá)的平均間隔時(shí)間；到達(dá)的平均間隔時(shí)間；表示單位時(shí)間內(nèi)被服表示單位時(shí)間內(nèi)被服務(wù)完畢離去的平均顧客務(wù)完畢離去的平均顧客數(shù)，則數(shù)，則1/表示對(duì)每個(gè)表示對(duì)每個(gè)顧客的平均服務(wù)時(shí)間；顧客的平均服務(wù)時(shí)間；s表示服務(wù)系統(tǒng)中并聯(lián)表示服務(wù)系統(tǒng)中并聯(lián)的服務(wù)臺(tái)數(shù)，的服務(wù)臺(tái)數(shù)，Pn(t)在時(shí)刻在時(shí)刻t系統(tǒng)中恰系統(tǒng)中恰好有好有n個(gè)顧客的概率。個(gè)顧客的概率。則有下列關(guān)系：則有下列關(guān)系：,ssLWssLW或,qqLWqqLW或1sqWWsqLL0snnLnP1()qnn sLns P (Little公式)11.1.5 排隊(duì)

22、系統(tǒng)的輸入和輸出排隊(duì)系統(tǒng)的輸入和輸出排隊(duì)系統(tǒng)的輸入和輸出是指顧客到達(dá)流和服務(wù)時(shí)間流，它們的分排隊(duì)系統(tǒng)的輸入和輸出是指顧客到達(dá)流和服務(wù)時(shí)間流，它們的分布一般都是非負(fù)的隨機(jī)變量。最常見的是泊松分布、指數(shù)分布和布一般都是非負(fù)的隨機(jī)變量。最常見的是泊松分布、指數(shù)分布和埃爾朗分布。然而在研究具體問題時(shí)，究竟是服從哪種分布呢？埃爾朗分布。然而在研究具體問題時(shí)，究竟是服從哪種分布呢？通常抽取到達(dá)時(shí)間間隔和服務(wù)時(shí)間樣本，統(tǒng)計(jì)其分布（經(jīng)驗(yàn)分通常抽取到達(dá)時(shí)間間隔和服務(wù)時(shí)間樣本，統(tǒng)計(jì)其分布（經(jīng)驗(yàn)分布），并按照統(tǒng)計(jì)學(xué)的方法進(jìn)行檢驗(yàn)（如布），并按照統(tǒng)計(jì)學(xué)的方法進(jìn)行檢驗(yàn)（如 檢驗(yàn)），以確定服從檢驗(yàn)），以確定服從哪種理論分

23、布。為此，我們先介紹常用的泊松分布、指數(shù)分布和哪種理論分布。為此，我們先介紹常用的泊松分布、指數(shù)分布和埃爾朗分布，之后介紹經(jīng)驗(yàn)分布檢驗(yàn)的埃爾朗分布，之后介紹經(jīng)驗(yàn)分布檢驗(yàn)的Excel操作。操作。1.泊松分布（最簡單流）泊松分布（最簡單流）2.指數(shù)分布指數(shù)分布3.埃爾朗分布埃爾朗分布4.經(jīng)驗(yàn)分布經(jīng)驗(yàn)分布21.最簡單流（泊松分布）最簡單流（泊松分布）所謂最簡單流，是指在所謂最簡單流，是指在t這段時(shí)間內(nèi)有這段時(shí)間內(nèi)有k個(gè)顧客來到個(gè)顧客來到服務(wù)系統(tǒng)服務(wù)系統(tǒng)的概率的概率服從泊松（服從泊松（Poisson）分布，故也稱為泊松流。即：）分布，故也稱為泊松流。即：1.最簡單流（泊松分布）最簡單流（泊松分布）最簡

24、單流需要滿足以下三個(gè)條件：最簡單流需要滿足以下三個(gè)條件：（1）平穩(wěn)性）平穩(wěn)性 指在一定時(shí)間間隔內(nèi)，來到服務(wù)系統(tǒng)有指在一定時(shí)間間隔內(nèi)，來到服務(wù)系統(tǒng)有k個(gè)顧客的概個(gè)顧客的概率僅與這段時(shí)間間隔的長短有關(guān)，而與這段時(shí)間的起始時(shí)刻無關(guān)；率僅與這段時(shí)間間隔的長短有關(guān)，而與這段時(shí)間的起始時(shí)刻無關(guān)；（2）無后效性）無后效性 指在不相交的時(shí)間區(qū)間內(nèi)到達(dá)的顧客數(shù)是相互獨(dú)指在不相交的時(shí)間區(qū)間內(nèi)到達(dá)的顧客數(shù)是相互獨(dú)立的，或者說在區(qū)間立的，或者說在區(qū)間a, a+t來到來到k個(gè)顧客的概率與時(shí)間個(gè)顧客的概率與時(shí)間a之前來到之前來到多少個(gè)顧客無關(guān)；多少個(gè)顧客無關(guān)；（3）普通性）普通性 指在足夠小的時(shí)間區(qū)間內(nèi)只能有一個(gè)顧客到達(dá)

25、，不指在足夠小的時(shí)間區(qū)間內(nèi)只能有一個(gè)顧客到達(dá)，不可能有兩個(gè)以上顧客同時(shí)到達(dá)?？赡苡袃蓚€(gè)以上顧客同時(shí)到達(dá)。1.最簡單流（泊松分布）最簡單流（泊松分布）最簡單流的一些性質(zhì)：最簡單流的一些性質(zhì)：（1）參數(shù)）參數(shù)代表單位時(shí)間內(nèi)到達(dá)顧客的平均數(shù)代表單位時(shí)間內(nèi)到達(dá)顧客的平均數(shù)證證 由于考慮單位時(shí)間，取由于考慮單位時(shí)間，取t=1，其數(shù)學(xué)期望為：，其數(shù)學(xué)期望為： （2）在）在t,t+t 沒有顧客到達(dá)的概率為沒有顧客到達(dá)的概率為1-t +o(t)證證 在時(shí)間在時(shí)間t 沒有顧客到達(dá)的概率為沒有顧客到達(dá)的概率為 ，將右端展開為麥克勞，將右端展開為麥克勞林級(jí)數(shù)有：林級(jí)數(shù)有： 當(dāng)當(dāng)t0 時(shí)，從第時(shí)，從第3項(xiàng)開始為項(xiàng)開始

26、為t 的高階無窮小，故結(jié)論得證。的高階無窮小，故結(jié)論得證。（3）在）在t,t+t 內(nèi)恰好有內(nèi)恰好有1個(gè)顧客到達(dá)的概率為個(gè)顧客到達(dá)的概率為 t +o(t)證證 在在 t,t+t內(nèi)恰好有內(nèi)恰好有1個(gè)顧客到達(dá)的概率為個(gè)顧客到達(dá)的概率為 ，將，將的麥克勞林級(jí)數(shù)代入，結(jié)論得證。的麥克勞林級(jí)數(shù)代入，結(jié)論得證。1001(1)!(1)!kkkkkkkPkeekk0( )tP te23()()1().2!3!tttet 1()tPtet te2指數(shù)分布的服務(wù)時(shí)間指數(shù)分布的服務(wù)時(shí)間 指數(shù)分布的性質(zhì)指數(shù)分布的性質(zhì) 3階埃爾朗（階埃爾朗（Erlang）分布）分布4經(jīng)驗(yàn)分布經(jīng)驗(yàn)分布例例:大連港大連港1979年年500噸

27、以上非定期進(jìn)港航班噸以上非定期進(jìn)港航班(數(shù)據(jù)見下頁數(shù)據(jù)見下頁)(1)統(tǒng)計(jì)頻數(shù)分布統(tǒng)計(jì)頻數(shù)分布(2)檢驗(yàn)符合泊松分布嗎檢驗(yàn)符合泊松分布嗎?1979年大連港非定期年大連港非定期500萬噸以上貨船進(jìn)港航班萬噸以上貨船進(jìn)港航班第第1步步:求相關(guān)參數(shù)求相關(guān)參數(shù).=AVERAGE(B2:M32)求平均值求平均值=STDEV(B2:M32)求標(biāo)準(zhǔn)差求標(biāo)準(zhǔn)差=MAX(B2:M32)求最大值求最大值第第2步步:統(tǒng)計(jì)頻數(shù)統(tǒng)計(jì)頻數(shù)由最大值列出區(qū)間點(diǎn)由最大值列出區(qū)間點(diǎn)由由=frequency(B2:M32,N6:N16)統(tǒng)計(jì)頻數(shù)統(tǒng)計(jì)頻數(shù)(Ctrl+Shift+Enter)由由=365poisson(O6,N$3,0)

28、求求泊松律泊松律第第3頻頻:假設(shè)檢驗(yàn)假設(shè)檢驗(yàn)由由=Q6:Q16*O17:P17/Q17求理求理論頻數(shù)論頻數(shù)由由=chitest(O6:P16,R6:S16)求卡求卡方檢驗(yàn)的方檢驗(yàn)的P值值推斷推斷:當(dāng)當(dāng)P值值0.05不拒絕泊松分布不拒絕泊松分布的原假設(shè)的原假設(shè)數(shù)據(jù)文檔數(shù)據(jù)文檔(雙擊打開講解演示雙擊打開講解演示)11.2 生死過程生死過程nn+1n-1 t期間期間 t后后(1)生生0死死0 n(2)生生1死死0 n+1(3)生生0死死1 n-1(4)生生1死死1 n生死過程的平衡方程生死過程的平衡方程1 100PP0101PP00221 11 1PPPP221 11 100PPPP11 11 10

29、10PPP1 1P1212PP102021PP 110021nnnPP 同理依次推得11.3.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1/系統(tǒng)系統(tǒng)1M/M/1/模型需要滿足的條件模型需要滿足的條件標(biāo)準(zhǔn)的M/M/1/模型是指滿足下列條件的排隊(duì)系統(tǒng)：（1）輸入過程：顧客源無限，單個(gè)到來，相互獨(dú)立，到達(dá)平均數(shù)為常數(shù)，且服從泊松分布，到達(dá)過程是平穩(wěn)的。（2）排隊(duì)規(guī)則：單隊(duì)，隊(duì)長不受限制，先到先服務(wù)。（3）服務(wù)機(jī)構(gòu)：單服務(wù)臺(tái)、平均服務(wù)率為常數(shù)，對(duì)各顧客服務(wù)時(shí)間相互獨(dú)立，服從相同的指數(shù)分布，服務(wù)過程也是平穩(wěn)的。2M/M/1/系統(tǒng)運(yùn)行指標(biāo)系統(tǒng)運(yùn)行指標(biāo)由于到達(dá)平均數(shù)和服務(wù)平均數(shù)均為常數(shù)，即01112.,.nn11021nnn

30、nnC 于是有1式中稱為業(yè)務(wù)密度0011nnnnC001/1nnPC 00(1)nnnnPC PP0snnLnP0(1)nnn10(1)nnn 0(1)nndd 0(1)nndd 1(1)1dd 11ssLW111()qsWW qqLW案例案例11-1（請(qǐng)閱讀教材案例11-1）到達(dá)率3臺(tái)/天，服務(wù)率4臺(tái)/天，150臺(tái)設(shè)備（顧客源150可視為無限）。問題：等待時(shí)間過長。要求：顧客的平均等待時(shí)間不應(yīng)超過2h?，F(xiàn)問：應(yīng)如何對(duì)問題進(jìn)行分析？分析分析 每個(gè)地區(qū)只有一個(gè)技術(shù)服務(wù)代表，為單服務(wù)臺(tái)；該地區(qū)用戶150戶，可近似于無窮大，采用M/M/1/排隊(duì)系統(tǒng)模型。3343sL0.75 32.25qsLL111

31、43sW0.75qsWW可見，當(dāng)每天維修電話從3個(gè)減少到2個(gè)時(shí)，顧客平均等待時(shí)間為8h的0.25倍，即2h，滿足管理層的要求。排隊(duì)等待的顧客數(shù)也從平均2.25減少到0.5。決策決策 維修量與顧客總體成正比例，目前每個(gè)服務(wù)代表負(fù)責(zé)150個(gè)顧客總體，減少到100個(gè)，可增加技術(shù)服務(wù)代表，每個(gè)負(fù)責(zé)有100個(gè)用戶的區(qū)域。11.3.2 系統(tǒng)容量有限的系統(tǒng)容量有限的M/M/1/N/系統(tǒng)系統(tǒng)M/M/1/N/模型，由于系統(tǒng)容量有限，當(dāng)nN，顧客不再進(jìn)入系統(tǒng)，其他條件同M/M/1/模型。其速率圖如下：01112.,.nn由于 有狀態(tài)轉(zhuǎn)移差分方程：110210nnnnnnNCnN 當(dāng)時(shí)10nnNCnN0011/1N

32、nnPCN1/(1),0nNnNPnN當(dāng)時(shí)1011NNnnC01011/1NnNnPC10110nNnnnNPC PnN0NsnnLnP11011NnNnn1011NnNndd1011NnNndd111111NNdd11(1)11NNN11(1)limlim111NsNNNNL因所以所以M/M/1/模型是模型是M/M/1/N/的特例。的特例。M/M/1/N/主要指標(biāo)的計(jì)算主要指標(biāo)的計(jì)算11(1)11NsNNLLittle公式是否還適用？答案是肯定的，但由于隊(duì)長受限，真正進(jìn)入服公式是否還適用？答案是肯定的，但由于隊(duì)長受限，真正進(jìn)入服務(wù)系統(tǒng)的顧客要小于到達(dá)率務(wù)系統(tǒng)的顧客要小于到達(dá)率，我們稱為有效到

33、達(dá)率，我們稱為有效到達(dá)率eff1()Nqnn sLns P 2(1)NnnnP22NNnnnnnPP101022NNnnnnPnPPPPP000NNnnnnnPPP0(1)qsLLP0(1)effPsseffLWqqeffLWeffsqLL由前所述由前所述【例【例11-1】某單人美發(fā)店】某單人美發(fā)店有有3把椅子以備顧客休息把椅子以備顧客休息等待。后來的顧客發(fā)現(xiàn)等待。后來的顧客發(fā)現(xiàn)3把椅子都坐滿時(shí)就不進(jìn)店把椅子都坐滿時(shí)就不進(jìn)店等待而離開。顧客平均到等待而離開。顧客平均到達(dá)達(dá)3人人/h，理發(fā)時(shí)間平均，理發(fā)時(shí)間平均15min/人。要求：人。要求：（1）某顧客一到達(dá)就能）某顧客一到達(dá)就能理發(fā)的概率；理

34、發(fā)的概率；（2）有效到達(dá)率；）有效到達(dá)率； （3）排隊(duì)等待顧客的平）排隊(duì)等待顧客的平均數(shù)；均數(shù)；（4）顧客在理發(fā)店平均）顧客在理發(fā)店平均等待時(shí)間；等待時(shí)間；（5）顧客一到就離開的）顧客一到就離開的概率。概率。11.3.3 顧客源有限的顧客源有限的M/M/1/m系統(tǒng)系統(tǒng)M/M/1/m系統(tǒng)除顧客源有限制外，其余條件與M/M/1/系統(tǒng)相同。設(shè)顧客源數(shù)（設(shè)備數(shù)）m，系統(tǒng)中顧客數(shù)（等待維修和正在維修的設(shè)備數(shù)）n，故障率平均服務(wù)率011,(1) ,(1)nmmmn 由于11021!,()!0nnnnmnmCmnnm 0001/(1)miinnPCPC Pnm001/mnnPC0nnPC P,(1)nnnP

35、nP0msnnLnP1()mqnn sLns P 0()mnnsnPmL/qqWL/ssWL 主要指標(biāo)計(jì)算過程：【例【例11-2】一名工人負(fù)責(zé)看管】一名工人負(fù)責(zé)看管10臺(tái)自動(dòng)機(jī)床，在加料或刀具更換時(shí)就臺(tái)自動(dòng)機(jī)床，在加料或刀具更換時(shí)就自動(dòng)停車，等待工人照管。設(shè)平均每臺(tái)機(jī)床兩次停車間隔時(shí)間自動(dòng)停車，等待工人照管。設(shè)平均每臺(tái)機(jī)床兩次停車間隔時(shí)間2h，需，需要工人照管的平均時(shí)間為要工人照管的平均時(shí)間為12min，設(shè)以上兩項(xiàng)時(shí)間均服從指數(shù)分布，設(shè)以上兩項(xiàng)時(shí)間均服從指數(shù)分布，計(jì)算該系統(tǒng)的各項(xiàng)指標(biāo)。計(jì)算該系統(tǒng)的各項(xiàng)指標(biāo)。解解 單臺(tái)平均停車間隔時(shí)間單臺(tái)平均停車間隔時(shí)間2h，則每臺(tái)單位時(shí)間停車率為，則每臺(tái)單位時(shí)

36、間停車率為0.5（=0.5）；）；對(duì)每臺(tái)停車的機(jī)床平均照管時(shí)間對(duì)每臺(tái)停車的機(jī)床平均照管時(shí)間12min，單位時(shí)間照管的臺(tái)數(shù)為，單位時(shí)間照管的臺(tái)數(shù)為5（=5）,/=0.5/5=0.1!,()!nnmCnmmn11.4.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/s/系統(tǒng)系統(tǒng)1模型需滿足的前提條件標(biāo)準(zhǔn)的多服務(wù)設(shè)施排隊(duì)系統(tǒng)規(guī)定的條件：（1）顧客到達(dá)率為常數(shù)（n=），服從泊松分布；（2）每臺(tái)服務(wù)率為常數(shù)，服從指數(shù)分布；（3）單隊(duì)排隊(duì)，隊(duì)長不受限制，排隊(duì)規(guī)則FCFS；（4）各服務(wù)臺(tái)相互獨(dú)立，不搞協(xié)作。11.4.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/s/系統(tǒng)系統(tǒng)2模型指標(biāo)的計(jì)算設(shè)服務(wù)臺(tái)數(shù)為s，則有：,nnnssns110211101211!

37、1()()()( !)!nnnnnnnn ssn snssnsnCnssss s 【例11-3】有2個(gè)油泵的加油站，平均加注一輛汽車需要1.2min，平均每h有80臺(tái)汽車前來加油。到達(dá)時(shí)間服從泊松分布，服務(wù)時(shí)間間隔服從指數(shù)分布。要求確定：（1）預(yù)期在加油站的汽車數(shù)；（2）預(yù)期汽車在加油站停留多長時(shí)間；（3）某個(gè)油泵空閑的概率。解 每個(gè)油泵服務(wù)率50輛/h，到達(dá)率80輛/h。1!1!nnnn snsnCnss s11.4.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/s/系統(tǒng)系統(tǒng)31個(gè)M/M/s/系統(tǒng)與多個(gè)M/M/1/系統(tǒng)運(yùn)行指標(biāo)的比較11.4.2 系統(tǒng)容量有限的系統(tǒng)容量有限的M/M/s/N/系統(tǒng)系統(tǒng)對(duì)于容量有限的對(duì)于容量有限的M/M/s/N/系統(tǒng)，由于多于系統(tǒng)，由于多于N個(gè)時(shí)不允許進(jìn)入服務(wù)系統(tǒng)，個(gè)時(shí)不允許進(jìn)入服務(wù)系統(tǒng)，故有故有1!1!0nnnn snsnCsnNs snN11.4.3 顧客源有限的顧客源有限的M/M/s/m系統(tǒng)系統(tǒng)如如m臺(tái)設(shè)備臺(tái)設(shè)備,s個(gè)工人看管個(gè)工人看管,故障率相同故障率相同,維修水平一樣維修水平一樣.()0nmnnmnm0nnnsssnmnm11021!()! !()! !0nnnnnn smnsmn nCmsnmmn s snm