08排隊(duì)論講義

1、第八章 排隊(duì)論第八章 排隊(duì)論第八章 排隊(duì)論第八章 排隊(duì)論學(xué)習(xí)目標(biāo)通過本章的學(xué)習(xí)，你應(yīng)該能夠：掌握 單效勞臺排隊(duì)系統(tǒng)的評價指標(biāo)，能熟練解決 衛(wèi)生效勞排隊(duì)系統(tǒng)中的一些簡單實(shí)際問題。熟悉 多效勞臺排隊(duì)模型、其他類型排隊(duì)模型特征 及求解指標(biāo)，理解排隊(duì)系統(tǒng)最優(yōu)化設(shè)計(jì)思想。了解 隨機(jī)效勞系統(tǒng)根本理論，常見排隊(duì)效勞系統(tǒng) 結(jié)構(gòu)和概率特性。第八章 排隊(duì)論章前案例 某醫(yī)院藥房只有一名藥劑員，患者隨機(jī)到達(dá)取藥窗口，平均每小時20人，藥劑員配藥時間是一隨機(jī)分布，平均每人為2.5分鐘。當(dāng)取藥窗口已有患者取藥時，陸續(xù)到達(dá)的取藥患者必須排隊(duì)等待。在這個隨機(jī)性效勞的排隊(duì)系統(tǒng)中，管理者想要了解系統(tǒng)的運(yùn)行效率。如患者取藥平均等待

2、多長時間？平均有多少患者在排隊(duì)等待？假設(shè)藥劑員配藥時間由原來的2.5分鐘減少到2分鐘，患者取藥的排隊(duì)現(xiàn)象有多大改善？假設(shè)增加一名藥劑員，取藥的排隊(duì)現(xiàn)象又有多大改善等？第八章 排隊(duì)論 章前案例是一個由排隊(duì)現(xiàn)象引起的衛(wèi)生效勞系統(tǒng)資源配置優(yōu)化問題。如何合理設(shè)置藥劑員數(shù)，既能有效減少患者排隊(duì)取藥時間，又能提供較高的效勞效率，使衛(wèi)生效勞供需雙方均到達(dá)最正確滿意度，就是本章排隊(duì)論需要解決的問題。 第八章 排隊(duì)論排隊(duì)是我們?nèi)粘Ｉ詈蜕a(chǎn)中經(jīng)常遇到的現(xiàn)象。例如有形排隊(duì)顧客到商店排隊(duì)購置物品病員到醫(yī)院排隊(duì)看病學(xué)生去食堂排隊(duì)就餐生產(chǎn)線上半成品排隊(duì)等待加工無形排隊(duì)患者打120 請求救護(hù)車前 言第八章 排隊(duì)論顧客與效

3、勞臺 上述各種問題雖互不相同，但卻都有要求得到某種效勞的人或物和提供效勞的人或機(jī)構(gòu)。要求效勞的對象顧客效勞臺提供效勞的人或機(jī)構(gòu)第八章 排隊(duì)論既保證一定的服務(wù)質(zhì)量指標(biāo)又使服務(wù)設(shè)施費(fèi)用經(jīng)濟(jì)合理排隊(duì)論所要研究解決的問題顧客可能出現(xiàn)空閑浪費(fèi)增加服務(wù)設(shè)施支出增大減少排隊(duì)時間服務(wù)臺對顧客帶來不良影響減少服務(wù)設(shè)施等待時間長減少支出避免浪費(fèi)顧客排隊(duì)時間服務(wù)設(shè)施成本前 言第八章 排隊(duì)論第八章 排隊(duì)論第一節(jié) 排隊(duì)系統(tǒng)的根本概念第二節(jié) 單效勞臺M/M/1排隊(duì)模型第三節(jié) 多效勞臺M/M/C排隊(duì)模型第四節(jié) 其他類型的排隊(duì)模型第五節(jié) 排隊(duì)系統(tǒng)的最優(yōu)化設(shè)計(jì)第六節(jié) 案例分析 本章小結(jié)第八章 排隊(duì)論一、排隊(duì)系統(tǒng)的組成二、排隊(duì)系

4、統(tǒng)的評價指標(biāo)第一節(jié) 排隊(duì)系統(tǒng)的根本概念三、排隊(duì)模型的符號表示 四、排隊(duì)系統(tǒng)的常見分布 第八章 排隊(duì)論一、排隊(duì)系統(tǒng)的組成 一個排隊(duì)系統(tǒng)或稱效勞系統(tǒng)，有三個根本組成局部：輸入過程、排隊(duì)規(guī)那么和效勞規(guī)那么。圖8-1給出了排隊(duì)系統(tǒng)的一般結(jié)構(gòu)。 圖8-1 排隊(duì)模型結(jié)構(gòu)圖 第八章 排隊(duì)論1輸入過程 (1)顧客總體數(shù): 顧客的來源(顧客源)。顧客源可以是 有限的，也可以是無限的。 (2)顧客流的概率分布: 顧客相繼到達(dá)的時間間隔的分 布,有確定的時間間隔和隨機(jī)的時間間隔。顧客流 的概率分布一般有定長分布、二項(xiàng)分布、泊松分布 (泊松流,最簡單流)、愛爾朗分布等。 (3)顧客到達(dá)方式: 顧客是怎樣來到系統(tǒng)的，是

5、單個到 達(dá)，還是成批到達(dá)。 指要求效勞的顧客是按怎樣的規(guī)律到達(dá)排隊(duì)系統(tǒng)的過程，也稱為顧客流。包含3個方面的內(nèi)容。第八章 排隊(duì)論2排隊(duì)規(guī)那么1等待制2損失制3混合制排隊(duì)規(guī)那么一般分為:第八章 排隊(duì)論2排隊(duì)規(guī)那么(1) 等待制 顧客到達(dá)系統(tǒng)時，如果效勞臺沒有空閑， 那么顧客排隊(duì)等候效勞。等待制效勞的方式有： 先到先效勞(FCFS)：按顧客到達(dá)先后給予效勞。 后到先效勞(LCFS)：情報(bào)收集中最后到達(dá)的信息 最有價值，往往最先采用。 優(yōu)先權(quán)效勞(PR)：醫(yī)院對危重病人給予優(yōu)先治療。 隨機(jī)效勞(SIRO)：隨機(jī)抽取等待效勞的顧客。第八章 排隊(duì)論(3) 混合制 介于等待制和損失制之間。方式有： 隊(duì)伍長度

6、有限，當(dāng)隊(duì)伍長度小于N 時，新到顧客就 排隊(duì)等待；當(dāng)隊(duì)伍長度為N 時，新來顧客離去。 等待時間有限，顧客排隊(duì)等候一段時間后仍未得到效勞，顧客離去。 逗留時間等待時間與效勞時間之和有限，顧客在系統(tǒng)中的逗留時間不得超過確定的時間。2排隊(duì)規(guī)那么(2) 損失制 顧客到達(dá)系統(tǒng)時，如果效勞臺沒有空閑，那么顧客離去，另求效勞。第八章 排隊(duì)論3效勞規(guī)那么 指排隊(duì)系統(tǒng)中效勞臺的個數(shù)、排列及效勞方式。 效勞方式上有單個效勞，也有成批效勞的，如醫(yī)院里的上下電梯。 效勞臺的個數(shù)可以是一個或多個。多個效勞臺可以是串聯(lián)或并聯(lián)。 第八章 排隊(duì)論圖8-2 單效勞臺排隊(duì)系統(tǒng)1單效勞臺、單隊(duì)列 排 列 結(jié) 構(gòu)第八章 排隊(duì)論圖8-

7、3 單隊(duì)列S個效勞臺并聯(lián)的排隊(duì)系統(tǒng)2多效勞臺、單隊(duì)列排 列 結(jié) 構(gòu)第八章 排隊(duì)論圖8-4 S個隊(duì)列S個效勞臺的并聯(lián)排隊(duì)系統(tǒng)3多效勞臺、多隊(duì)列 排 列 結(jié) 構(gòu)第八章 排隊(duì)論圖8-5 單隊(duì)多個效勞臺的串聯(lián)排隊(duì)系統(tǒng)4多效勞臺串列 排 列 結(jié) 構(gòu)第八章 排隊(duì)論圖8-6 多隊(duì)多效勞臺混聯(lián)、網(wǎng)絡(luò)系統(tǒng) 5多效勞臺混合 排 列 結(jié) 構(gòu)第八章 排隊(duì)論二、排隊(duì)系統(tǒng)的評價指標(biāo) 第一類:在效勞設(shè)施設(shè)置之前，根據(jù)顧客輸入過程 與效勞過程要求，確定效勞設(shè)施的規(guī)模；第二類:對已有的效勞系統(tǒng)施以最優(yōu)控制，改進(jìn)和 提高排隊(duì)系統(tǒng)工作效率。 排隊(duì)論研究的問題，可以分成兩大類:第八章 排隊(duì)論二、排隊(duì)系統(tǒng)的評價指標(biāo) 排隊(duì)系統(tǒng)的數(shù)量指標(biāo)

8、主要有：1單位時間內(nèi)到達(dá)的顧客數(shù)的期望值平均到達(dá)率。 1/ 表示相鄰兩個顧客到達(dá)的平均間隔時間。2單位時間內(nèi)效勞的顧客數(shù)的期望值平均離去率。 1/ 表示每個顧客的平均效勞時間。第八章 排隊(duì)論二、排隊(duì)系統(tǒng)的評價指標(biāo) 4系統(tǒng)內(nèi)的平均顧客數(shù)隊(duì)長L 5排隊(duì)等待效勞的平均顧客數(shù)排隊(duì)長Lq6顧客在系統(tǒng)中平均逗留時間逗留時間W7顧客排隊(duì)等待的平均時間等待時間Wq 3系統(tǒng)有n 個顧客的概率Pn 系統(tǒng)空閑的概率P0系統(tǒng)的狀態(tài)概率主要運(yùn)行指標(biāo)第八章 排隊(duì)論 排隊(duì)系統(tǒng)有許許多多的組合，從而形成不同的排隊(duì)模型。采用X/Y/Z/A/B/C 形式表示不同排隊(duì)模型。其中： X 顧客到達(dá)間隔時間概率分布 Y 效勞時間的概率分

9、布 Z 效勞臺個數(shù) A 系統(tǒng)內(nèi)顧客的容量 B 顧客源總數(shù) C 排隊(duì)規(guī)那么三、排隊(duì)模型的符號表示 第八章 排隊(duì)論 例如： M/M/ 3/20/FCFS排隊(duì)模型的特點(diǎn)是：顧客到達(dá)間隔時間和效勞時間均服從負(fù)指數(shù)分布，有3個效勞臺，系統(tǒng)的顧客容量為20，顧客總體數(shù)無限，先到先效勞的排隊(duì)系統(tǒng) 當(dāng)系統(tǒng)等待空間容量無限, 顧客源無限時也可以簡單記為 MM1。三、排隊(duì)模型的符號表示 第八章 排隊(duì)論 顧客到達(dá)和離開分別構(gòu)成排隊(duì)系統(tǒng)的輸入與輸出過程流。到達(dá)分布和離開分布確定了到達(dá)系統(tǒng)和離開系統(tǒng)的顧客數(shù)這兩個隨機(jī)變量的分布。四、排隊(duì)系統(tǒng)的常見分布第八章 排隊(duì)論1. 確定顧客到達(dá)流概率分布在一定 時間間隔內(nèi)來 n 個

10、顧客的概率是多大？2. 確定顧客離開流概率分布在一定 時間內(nèi)效勞完 m 個顧客的概率是多大？求解排隊(duì)系統(tǒng)數(shù)量指標(biāo)四、排隊(duì)系統(tǒng)的常見分布第八章 排隊(duì)論1泊松分布 最根本的排隊(duì)模型是在給定時間內(nèi)到達(dá)系統(tǒng)的顧客數(shù)服從泊松分布顧客到達(dá)流是泊松流最簡單流。四、排隊(duì)系統(tǒng)的常見分布 第八章 排隊(duì)論單位時間t =1內(nèi)到達(dá) n 個顧客的概率為： 四、排隊(duì)系統(tǒng)的常見分布 其中 為單位時間內(nèi)到達(dá)系統(tǒng)的顧客的期望值，也稱平均到達(dá)率。證明知，在 t 時間內(nèi)到達(dá) n 個顧客的概率為：第八章 排隊(duì)論四、排隊(duì)系統(tǒng)的常見分布 間隔時間T 的期望值 負(fù)指數(shù)分布的概率密度為：顧客單位時間內(nèi)到達(dá)的個數(shù)X 服從參數(shù)為 的泊松分布同一隨

11、機(jī)過程可從兩種不同角度用兩種分布來描述顧客到達(dá)的間隔時間T 服從參數(shù)為 的負(fù)指數(shù)分布2負(fù)指數(shù)分布到達(dá)分布第八章 排隊(duì)論 對顧客效勞時間常用的概率分布也是負(fù)指數(shù)分布，概率密度為： 其中 表示單位時間內(nèi)完成效勞的顧客數(shù)，也稱平均效勞率。 四、排隊(duì)系統(tǒng)的常見分布 效勞時間(離開)分布第八章 排隊(duì)論例 8-1 某醫(yī)院外科手術(shù)室任意抽查了100個工作小時，每小時患者到達(dá)數(shù)的出現(xiàn)次數(shù)如表8-1，問每小時患者的到達(dá)數(shù)是否服從泊松分布。 表8-1 患者在單位時間內(nèi)到達(dá)數(shù)的頻數(shù)分布到達(dá)數(shù)n01234567出現(xiàn)次數(shù)fn1028291610610四、排隊(duì)系統(tǒng)的常見分布 第八章 排隊(duì)論解 每小時患者平均到達(dá)率： 現(xiàn)檢

12、驗(yàn)這個經(jīng)驗(yàn)分布是否適合 = 2.1 的泊松分布，利用 檢驗(yàn)法： 假設(shè)該經(jīng)驗(yàn)分布適合 = 2.1 的泊松分布計(jì)算統(tǒng)計(jì)量 結(jié)果如表8-2 四、排隊(duì)系統(tǒng)的常見分布 第八章 排隊(duì)論到達(dá)數(shù)(n)出現(xiàn)次數(shù) fn理論頻數(shù)100 Pn0100.122412.240.40991280.257125.710.20392290.270027.000.14813160.189018.900.44494100.09929.920.00065 70.04160.095260.02071001.00001001.3026 表8-2 泊松分布的擬合檢驗(yàn)第八章 排隊(duì)論接受假設(shè)，即患者到達(dá)數(shù)的經(jīng)驗(yàn)分布適合 = 2.1 的泊松分布

13、 。四、排隊(duì)系統(tǒng)的常見分布 第八章 排隊(duì)論一、M/M/1/模型 二、M/M/1/N/模型第二節(jié) 單效勞臺 M /M /1 排隊(duì)模型三、M/M/1/m/m模型第八章 排隊(duì)論 M /M /1 排隊(duì)系統(tǒng)是指顧客的到達(dá)為最簡單流，即顧客到達(dá)間隔時間和效勞時間均服從負(fù)指數(shù)分布的單效勞臺排隊(duì)系統(tǒng)。根據(jù)顧客源和系統(tǒng)容量的不同情況，該模型主要有M /M /1/ / 型、M /M /1 / N / 型、M /M /1/ m /m 型三種。排隊(duì)規(guī)那么適用于FCFS、LCFS 和 SIRO。 第二節(jié) 單效勞臺 M /M /1 排隊(duì)模型第八章 排隊(duì)論1模型條件 1平均到達(dá)率 2平均效勞率 ( )3顧客的到達(dá)為最簡單流

14、(泊松分布) 到達(dá)間隔時間服從負(fù)指數(shù)分布4效勞時間服從負(fù)指數(shù)分布5單效勞臺一、M/M/1/模型 顧客源無限，容量無限，F(xiàn)CFS排隊(duì)規(guī)那么第八章 排隊(duì)論一、M/M/1/模型 2系統(tǒng)的狀態(tài)概率和主要運(yùn)行指標(biāo) 系統(tǒng)的狀態(tài)概率設(shè)則有 稱P0 為系統(tǒng)的空閑概率 為利用率服務(wù)臺處于繁忙狀態(tài)的概率 第八章 排隊(duì)論(2) 系統(tǒng)的主要運(yùn)行指標(biāo) 它們之間的關(guān)系為 一、M/M/1/模型 第八章 排隊(duì)論例8-2 章前案例設(shè)某醫(yī)院藥房只有一名藥劑員，取藥的患者按泊松分布到達(dá)，平均每小時20人，藥劑員配藥時間服從指數(shù)分布，平均每人為2.5分鐘。試分析該藥房排隊(duì)系統(tǒng)的狀態(tài)概率和運(yùn)行指標(biāo)。 (1)試對此排隊(duì)系統(tǒng)進(jìn)行分析。 (

15、2)如果醫(yī)院希望有足夠的座位給取藥的病人坐，或者說病人來取藥沒有座位的概率不超過5%，試問至少應(yīng)為病人準(zhǔn)備多少個座位？ 一、M/M/1/模型 第八章 排隊(duì)論一、M/M/1/模型 解 這是一個M/M/1/系統(tǒng)，依題意知：藥劑員空閑概率，也是病人不必等待立即能取藥的概率。(1) 效勞強(qiáng)度為：第八章 排隊(duì)論這也是藥房繁忙的概率。而病人需要等待的概率那么為：一、M/M/1/模型 藥房外的病人平均數(shù)：第八章 排隊(duì)論病人平均等候時間：病人在藥房外平均逗留時間：藥房外排隊(duì)等待的病人平均數(shù)：一、M/M/1/模型 第八章 排隊(duì)論 如果醫(yī)院希望有足夠的座位給取藥的病人坐，或者說病人來取藥沒有座位的概率不超過5%，

16、試問至少應(yīng)為病人準(zhǔn)備多少個座位？ 設(shè)安排n-1個座位數(shù)。那么系統(tǒng)中不超過n個病人的概率應(yīng)不小于95%，即 ：一、M/M/1/模型 第八章 排隊(duì)論因此應(yīng)至少為病人準(zhǔn)備15個座位正在取藥的病人除外。 一、M/M/1/模型 第八章 排隊(duì)論二、M/M/1/N/模型 1模型條件 單位時間顧客平均到達(dá)率和平均效勞率，顧客到達(dá)為最簡單流，顧客到達(dá)間隔時間和效勞時間均服從負(fù)指數(shù)分布，單效勞臺，顧客源無限，容量為N 。 由于排隊(duì)等待的顧客數(shù)最多為N -1，所以在某一時刻某顧客到達(dá)時，如果系統(tǒng)中已有N 位顧客，那么該顧客被拒絕進(jìn)入系統(tǒng)考慮有效到達(dá)，該排隊(duì)規(guī)那么是混合制。 第八章 排隊(duì)論二、M/M/1/N/模型 1

17、模型條件 1平均到達(dá)率 2平均效勞率 ( ),3顧客的到達(dá)為最簡單流 到達(dá)間隔時間服從負(fù)指數(shù)分布4效勞時間服從負(fù)指數(shù)分布5單效勞臺6系統(tǒng)的容量為N 考慮有效到達(dá)eM/M/1/模型第八章 排隊(duì)論(1)系統(tǒng)的狀態(tài)概率系統(tǒng)空閑概率P0 和系統(tǒng)內(nèi)有n 個顧客的概率Pn 為： 二、M/M/1/N/模型 2系統(tǒng)的狀態(tài)概率和主要運(yùn)行指標(biāo)第八章 排隊(duì)論(2) 系統(tǒng)的主要運(yùn)行指標(biāo) 二、M/M/1/N 模型 8-7第八章 排隊(duì)論顧客到達(dá)又能進(jìn)入系統(tǒng)的概率為1-PN ，故系統(tǒng)的平均有效到達(dá)率e 為： 平均逗留時間:平均等待時間:二、M/M/1/N 模型 第八章 排隊(duì)論二、M/M/1/N/ 模型 例8-3 某私人牙科

18、診所配備一臺牙科綜合治療臺，由于診療室面積有限，只能安置 3 個座位供患者等候，一旦滿座那么后來者不再進(jìn)屋等候?；颊叩竭_(dá)診所的時間間隔和診斷時間均為負(fù)指數(shù)分布，平均到達(dá)時間間隔為50分鐘，平均治療時間為40分鐘。試分析系統(tǒng)的狀態(tài)概率和運(yùn)行指標(biāo)。 單效勞臺系統(tǒng)容量為4第八章 排隊(duì)論解： 這是一個M /M /1 /4 排隊(duì)系統(tǒng)二、M/M/1/N/模型 第八章 排隊(duì)論二、M/M/1/N/ 模型 結(jié)果：第八章 排隊(duì)論二、M/M/1/N/ 模型 第八章 排隊(duì)論三、M /M /1/ m / m 模型 1模型條件 單位時間平均每位顧客需要效勞的次數(shù)與平均效勞率，顧客的到達(dá)為最簡單流，顧客到達(dá)間隔時間和效勞時

19、間均服從負(fù)指數(shù)分布，單效勞臺，系統(tǒng)容量等于顧客源總數(shù)m ，混合制效勞規(guī)那么。 該模型常用于機(jī)器故障維修系統(tǒng)和醫(yī)院病房醫(yī)護(hù)人員對住院病人的護(hù)理工作等。 第八章 排隊(duì)論 1模型條件 1平均到達(dá)率 2平均效勞率 ( ),3顧客的到達(dá)為最簡單流 到達(dá)間隔服從負(fù)指數(shù)分布4效勞時間服從負(fù)指數(shù)分布5單效勞臺6系統(tǒng)容量等于顧客源總數(shù)mM/M/1/模型三、M /M /1/ m / m 模型 第八章 排隊(duì)論 (1)系統(tǒng)的狀態(tài)概率系統(tǒng)空閑概率P0 和系統(tǒng)內(nèi)有n 個顧客的概率Pn 為： 2系統(tǒng)的狀態(tài)概率和主要運(yùn)行指標(biāo)三、M /M /1/ m / m 模型 第八章 排隊(duì)論(2) 系統(tǒng)的主要運(yùn)行指標(biāo) 三、M /M /1/

20、 m / m 模型 第八章 排隊(duì)論例8-4 一名護(hù)士在ICU病房護(hù)理6位危重病人，病人一小時內(nèi)平均呼叫5次，每次護(hù)理時間平均為4分鐘，呼叫的時間間隔和護(hù)理時間服從負(fù)指數(shù)分布。單效勞臺試分析： 護(hù)士空閑的概率； 2人及以上需要護(hù)理的概率； 等待護(hù)理的病人數(shù)； 每位病人等待護(hù)理的平均時間。顧客源和系統(tǒng)容量為6三、M /M /1/ m / m 模型 第八章 排隊(duì)論解： 這是一個M /M /1/6/6 排隊(duì)系統(tǒng)，m = 6 , 單列，F(xiàn)CFS規(guī)那么。 護(hù)士空閑的概率 三、M /M /1/ m / m 模型 第八章 排隊(duì)論 2人及以上病人需要護(hù)理的概率 呼叫護(hù)理的病人數(shù) 三、M /M /1/ m / m

21、 模型 第八章 排隊(duì)論 等待護(hù)理的平均時間 三、M /M /1/ m / m 模型 等待護(hù)理的病人數(shù) 有效到達(dá)率 第八章 排隊(duì)論 結(jié)果顯示，患者護(hù)理的時間只有4分鐘，而等待護(hù)理的平均時間卻要9分鐘；病人住院期間護(hù)士能隨時效勞的可能性只有5.22%；系統(tǒng)內(nèi)通常約有2位及以上的病人在等待護(hù)理。根據(jù)這些情況，建議院方應(yīng)考慮增加一名護(hù)士或減少護(hù)理的病人數(shù)。 三、M /M /1/ m / m 模型 第八章 排隊(duì)論二、M /M /C/ N / 模型 三、M /M /C/ m / m 模型 一、M/M/C/模型第三節(jié) 多效勞臺M/M/C排隊(duì)模型第八章 排隊(duì)論第三節(jié) 多效勞臺M/M/C排隊(duì)模型 此模型與M/M

22、/1模型不同之處在于有C個效勞臺，各效勞臺的工作相互獨(dú)立，效勞率相等，如果顧客到達(dá)時,C個效勞臺都忙著，那么排成一隊(duì)等待，先到先效勞的單隊(duì)模型。根據(jù)顧客源和系統(tǒng)容量的不同情況，該模型主要有M/M/C/模型、M/M/C/N/模型和 M/M/C/m/m 模型。排隊(duì)規(guī)那么適用于FCFS、LCFS 和 SIRO。第八章 排隊(duì)論一、M/M/C/模型1模型條件 1顧客的到達(dá)為最簡單流 到達(dá)間隔時間服從負(fù)指數(shù)分布2平均到達(dá)率 3效勞時間服從負(fù)指數(shù)分布4平均效勞率 ( ),5C個效勞臺，每個效勞臺的工作相互獨(dú)立且平均 效勞率相同，都等于 ( c ),顧客源無限，容量無限，排隊(duì)規(guī)那么為等待制。第八章 排隊(duì)論2系

23、統(tǒng)的狀態(tài)概率和主要運(yùn)行指標(biāo) (1) 系統(tǒng)的狀態(tài)概率 系統(tǒng)的空閑概率P0，系統(tǒng)內(nèi)有n個顧客的概率Pn 以及利用率 分別為： 一、M/M/C/模型第八章 排隊(duì)論(2) 系統(tǒng)的主要運(yùn)行指標(biāo) (8-11)一、M/M/C/模型第八章 排隊(duì)論例8-5 某醫(yī)院康復(fù)科有4臺超短波理療儀，患者到達(dá)服從泊松分布。平均每小時到達(dá)12人，每人理療時間服從負(fù)指數(shù)分布，每臺每小時平均效勞4人，患者到達(dá)后排成一列依次就診。求： 4臺儀器同時空閑的概率； 計(jì)算系統(tǒng)的各項(xiàng)指標(biāo)； 患者到達(dá)后必須等待的概率。一、M/M/C/模型第八章 排隊(duì)論 4臺儀器同時空閑的概率 一、M/M/C/模型解 該排隊(duì)系統(tǒng)是M/M/4/ 模型，依題意：

24、 第八章 排隊(duì)論 按8-11分別計(jì)算 一、M/M/C/模型第八章 排隊(duì)論 患者到達(dá)后必須等待的概率 一、M/M/C/模型第八章 排隊(duì)論M/M/C/模型1模型條件 1顧客的到達(dá)為最簡單流 到達(dá)間隔時間服從負(fù)指數(shù)分布2平均到達(dá)率 3效勞時間服從負(fù)指數(shù)分布4平均效勞率 ( ),5C個效勞臺，每個效勞臺的工作相互獨(dú)立且 平均效勞率相同，都等于 (c ),6容量為N ( N C )，即系統(tǒng)中顧客數(shù)到達(dá)N 時， 后來顧客被拒絕進(jìn)入系統(tǒng)，效勞規(guī)那么為混合制。二、M /M /C/N/模型 第八章 排隊(duì)論8-12 2系統(tǒng)的狀態(tài)概率和主要運(yùn)行指標(biāo) (1) 系統(tǒng)的狀態(tài)概率 系統(tǒng)的空閑概率P0，系統(tǒng)內(nèi)有n個顧客的概率

25、Pn 以及利用率 分別為： 二、M /M /C/N/模型 第八章 排隊(duì)論(2) 系統(tǒng)的主要運(yùn)行指標(biāo) 二、M /M /C/N/模型 第八章 排隊(duì)論例8-7 某鄉(xiāng)鎮(zhèn)衛(wèi)生院只有4張病床，患者的到達(dá)和輸出服從最簡單流，平均每兩天有1名新患者住院，每名患者平均住7天。求此系統(tǒng)的有關(guān)運(yùn)行指標(biāo)。 解 該排隊(duì)系統(tǒng)是M/M/4/ 4 / 模型，C=N=4為混合制情形。依題意： 二、M /M /C/N/模型 第八章 排隊(duì)論1. 狀態(tài)概率 患者不能立即住院的概率 容量為N 系統(tǒng)空閑的概率二、M /M /C/N/模型 第八章 排隊(duì)論平均住院病人數(shù) 2. 主要運(yùn)行指標(biāo) 二、M /M /C/N/模型 第八章 排隊(duì)論三、M

26、 /M /C/ m / m 模型 1模型條件 系統(tǒng)顧客源為m，且(m C ) 。即一旦系統(tǒng)中已有m個顧客，就不會再有新的顧客到達(dá)，除非系統(tǒng)中的顧客得到效勞后又返回憶客源，系統(tǒng)才可能有顧客繼續(xù)到來。每個效勞臺在單位時間內(nèi)效勞的平均顧客數(shù)為 ，每個顧客在單位時間內(nèi)需要效勞的平均次數(shù)為 。顧客的到達(dá)時間間隔和效勞時間均服從負(fù)指數(shù)分布。 第八章 排隊(duì)論2系統(tǒng)的狀態(tài)概率和主要運(yùn)行指標(biāo)(1) 系統(tǒng)的狀態(tài)概率系統(tǒng)的空閑概率P0，系統(tǒng)內(nèi)有n個顧客的概率Pn： 三、M /M /C/ m / m 模型 第八章 排隊(duì)論(2) 系統(tǒng)的主要運(yùn)行指標(biāo) 三、M /M /C/ m / m 模型 第八章 排隊(duì)論例8-8 某醫(yī)院

27、病房有3名護(hù)士和18位病人，平均每位病人每2小時需要護(hù)理1次，每次12分鐘，護(hù)理時間間隔與護(hù)理時間均服從泊松分布?，F(xiàn)在醫(yī)院考慮兩種工作方案：方案為3名護(hù)士共同護(hù)理18位病人；方案為3名護(hù)士各自獨(dú)立工作，每人固定負(fù)責(zé)6位病人。試比較兩個方案的工作情況。 分析：方案是 M/M/3/18/18 系統(tǒng)，依題意： 第八章 排隊(duì)論系統(tǒng)空閑的概率： 病人不能馬上得到護(hù)理的概率： 方案的系統(tǒng)運(yùn)行結(jié)果： 第八章 排隊(duì)論系統(tǒng)工作指標(biāo)：方案的系統(tǒng)運(yùn)行結(jié)果： 第八章 排隊(duì)論系統(tǒng)空閑的概率： 病人不能馬上得到護(hù)理的概率： 其他系統(tǒng)工作指標(biāo)見表8-3。依題意： 方案是3個M/M/1/6/6 系統(tǒng)第八章 排隊(duì)論方案與方案的

28、比較表8-3 方案與方案排隊(duì)系統(tǒng)的工作指標(biāo) 指標(biāo)方案方案系統(tǒng)空閑率（%）17.0148.45平均隊(duì)長（人）1.830.85平均等待隊(duì)長（人）0.210.33平均逗留時間（分鐘）1419.67平均等待時間（分鐘）1.67.67等待概率（%）26.3451.55第八章 排隊(duì)論 從上面例子得知，3個M/M/1 模型和 1個M/M/3 模型盡管系統(tǒng)內(nèi)效勞臺數(shù)沒有變化，但采用不同的隊(duì)列方式的系統(tǒng)運(yùn)行狀態(tài)和指標(biāo)是不一樣的，聯(lián)合效勞單隊(duì)列要比分散效勞多隊(duì)列更為有效，所以在籌劃一個排隊(duì)系統(tǒng)時應(yīng)考慮隊(duì)列因素。C 個M/M/1模型與M/M/C 模型的比較第八章 排隊(duì)論第四節(jié) 其他類型的排隊(duì)模型一、M / G /

29、1 排隊(duì)模型二、M / D / 1 排隊(duì)模型三、具有優(yōu)先效勞權(quán)的M / M /1/模型 第八章 排隊(duì)論 M / G / 1 排隊(duì)系統(tǒng)是指顧客的到達(dá)為泊松流，單效勞臺，效勞時間為一般分布的排隊(duì)系統(tǒng)。由于該系統(tǒng)不符合生滅過程的定義，因而不能用前面的方法，而是通過觀察系統(tǒng)中各個顧客效勞完畢后離開系統(tǒng)的一瞬間的狀態(tài)來進(jìn)行研究。一、M / G / 1 排隊(duì)模型第八章 排隊(duì)論1模型條件 M / G / 1排隊(duì)模型是單效勞臺的等待制系統(tǒng)，到達(dá)系統(tǒng)的顧客數(shù)服從泊松分布，單位時間平均到達(dá)率 ，而各顧客的效勞時間是相互獨(dú)立且具有相同分布的隨機(jī)變量T。顧客源無限，容量無限，F(xiàn)CFS效勞規(guī)那么服務(wù)時間的期望值方差一、

30、M / G / 1 排隊(duì)模型第八章 排隊(duì)論2系統(tǒng)的狀態(tài)概率和主要運(yùn)行指標(biāo)設(shè)則有一、M / G / 1 排隊(duì)模型第八章 排隊(duì)論 從上述公式可見， L、Lq、W、Wq等由 和服務(wù)時間的 方差決定，而與分布的類型沒有關(guān)系。 當(dāng)服務(wù)率 給定后，隨著服務(wù)時間的方差的減少，平均 隊(duì)長和等待時間也將減少。 可通過改變服務(wù)時間的方差（即使服務(wù)時間規(guī)律化）， 來降低平均隊(duì)長和顧客等待時間。 在一般服務(wù)時間分布的Lq、Wq中以定長服務(wù)時間的為最小， 即當(dāng)且僅當(dāng) = 0 時，系統(tǒng)的平均隊(duì)長最小。一、M / G / 1 排隊(duì)模型第八章 排隊(duì)論例8-9 某醫(yī)院放射科有一臺CT，患者的到來服從泊松分布，平均每小時2人，每

31、位患者使用CT的平均時間為20分鐘，標(biāo)準(zhǔn)差為15分鐘。據(jù)患者反映等候CT檢查的時間較長，而管理人員認(rèn)為是設(shè)備的利用率不高，試對雙方所提問題進(jìn)行簡要分析。一、M / G / 1 排隊(duì)模型第八章 排隊(duì)論解 由題意可知：患者的效勞時間是相互獨(dú)立且具 有相同分布的隨機(jī)變量，標(biāo)準(zhǔn)差服務(wù)時間的期望值顧客到達(dá)率一、M / G / 1 排隊(duì)模型第八章 排隊(duì)論 設(shè)備的空閑率： 等待隊(duì)長： 等候檢查的時間： 一、M / G / 1 排隊(duì)模型第八章 排隊(duì)論結(jié)論： 設(shè)備的空閑率為33.33%，假設(shè)按每天工作8小時計(jì),幾乎有2.67個小時是空閑的；患者等候檢查的時間平均為31分鐘(比平均效勞時間要長)，因此，雙方所提問

32、題根本存在。一、M / G / 1 排隊(duì)模型第八章 排隊(duì)論1模型條件 M / D / 1排隊(duì)模型是單效勞臺等待制系統(tǒng)，到達(dá)系統(tǒng)顧客數(shù)服從泊松分布，單位時間平均到達(dá)率 ，而系統(tǒng)對顧客效勞時間為確定常數(shù)顧客源無限，容量無限，F(xiàn)CFS效勞規(guī)那么服務(wù)時間的期望值方差2可根據(jù)M / G / 1排隊(duì)模型的公式求得系統(tǒng)中的各項(xiàng)運(yùn)行指標(biāo) 二、M / D / 1 排隊(duì)模型第八章 排隊(duì)論系統(tǒng)的狀態(tài)概率和主要運(yùn)行指標(biāo)二、M / D / 1 排隊(duì)模型第八章 排隊(duì)論例8-10 某醫(yī)院檢驗(yàn)科有一臺全自動血液分析儀，每個血樣分析需要1分鐘，送檢樣品按泊松分布到達(dá)，平均每小時30份。試求該系統(tǒng)的主要運(yùn)行指標(biāo)。解：由題意知，這

33、是一個M / D / 1 排隊(duì)系統(tǒng)，且有二、M / D / 1 排隊(duì)模型第八章 排隊(duì)論按公式8-16計(jì)算，求出系統(tǒng)運(yùn)行指標(biāo) 二、M / D / 1 排隊(duì)模型第八章 排隊(duì)論三、具有優(yōu)先效勞權(quán)的M/M/1/模型 考慮在M/M/1/系統(tǒng)中，進(jìn)入系統(tǒng)的顧客分為兩級：第一級是優(yōu)先類，到達(dá)率為 1；第二級是普通類，到達(dá)率為2。兩類顧客的效勞時間均為相同1/ 的負(fù)指數(shù)分布。當(dāng)系統(tǒng)中有第一級顧客到達(dá)時，正在接受效勞的第二級顧客將被中斷效勞，重新等待，第一級顧客搶先接受效勞搶占優(yōu)先權(quán)；當(dāng)系統(tǒng)中只有同一級別顧客時，按先來先效勞的原那么。第八章 排隊(duì)論 設(shè)： = 1+2，第i 級顧客在系統(tǒng)中的平均逗留時間Wi (i

34、 =1, 2),第i級顧客的平均等待隊(duì)長和平均等待時間Lqi 和Wqi 。兩級綜合在一起的每個顧客在系統(tǒng)中的平均等待隊(duì)長Lq 和平均等待時間 Wq，滿足:模型分析第八章 排隊(duì)論8-18系統(tǒng)的主要運(yùn)行指標(biāo)第八章 排隊(duì)論 當(dāng)系統(tǒng)中兩類顧客效勞時間不相同時，設(shè)第一級為1，第二級為2 ，其他條件不變，那么系統(tǒng)中兩類顧客的隊(duì)長分別為： 效勞時間不相同的優(yōu)先效勞第八章 排隊(duì)論例8-11 某私人診所只有一名醫(yī)生，來就診的患者按每小時2人的泊松分布到達(dá)，每個患者的效勞時間服從均數(shù)為15分鐘的負(fù)指數(shù)分布。假設(shè)患者中90%屬一般病人，10%屬危重患者。該診所的效勞規(guī)那么是先治療危重病人，然后是一般患者。試計(jì)算兩類

35、患者等候治病的平均時間。 第八章 排隊(duì)論解：依題意知，危重病人是第一級，一般病人是第二級， = 2危重患者等待時間： 由8-18算出：第八章 排隊(duì)論一般患者等待時間： 危重患者等待隊(duì)長：一般患者等待隊(duì)長：第八章 排隊(duì)論二、確定系統(tǒng)最優(yōu)效勞臺 一、確定系統(tǒng)最優(yōu)效勞率 第五節(jié) 排隊(duì)系統(tǒng)的最優(yōu)化設(shè)計(jì) 第八章 排隊(duì)論第五節(jié) 排隊(duì)系統(tǒng)的最優(yōu)化設(shè)計(jì) 二是系統(tǒng)的最優(yōu)控制動態(tài)最優(yōu)，研究如何對給定的系統(tǒng)實(shí)施最優(yōu)運(yùn)營戰(zhàn)略，使目標(biāo)函數(shù)到達(dá)最優(yōu)的問題效勞機(jī)構(gòu)的純收入或利潤效勞收入與效勞本錢之差為最大。 一是系統(tǒng)的最優(yōu)設(shè)計(jì)靜態(tài)最優(yōu)，在系統(tǒng)設(shè)置之前，找出使系統(tǒng)到達(dá)最大效益的參數(shù)最優(yōu)值顧客的等待費(fèi)用與效勞機(jī)構(gòu)的本錢之和為最

36、?。慌抨?duì)系統(tǒng)的優(yōu)化包括兩方面的內(nèi)容：第八章 排隊(duì)論總費(fèi)用等待費(fèi)用效勞費(fèi)用效勞水平最優(yōu)解期望費(fèi)用總的期望費(fèi)用=效勞費(fèi)用+等待費(fèi)用排隊(duì)系統(tǒng)最優(yōu)設(shè)計(jì)的目標(biāo)就是要確定適當(dāng)?shù)男谒?，使總的期望費(fèi)用到達(dá)最小。第五節(jié) 排隊(duì)系統(tǒng)的最優(yōu)化設(shè)計(jì)第八章 排隊(duì)論一、M / M / 1 模型中最優(yōu)效勞率* 費(fèi)用函數(shù) f 為單位時間效勞本錢與顧客在系統(tǒng)中逗留所致?lián)p失費(fèi)用之和的期望值。假定效勞率 是一個連續(xù)值。那么費(fèi)用函數(shù)可為： a 表示當(dāng) =1時效勞機(jī)構(gòu)單位時間費(fèi)用，即單位時間內(nèi)效勞一個顧客的費(fèi)用；b為每個顧客在系統(tǒng)停留單位時間的費(fèi)用；L為系統(tǒng)內(nèi)逗留的顧客數(shù)； 為平均效勞率。第八章 排隊(duì)論考慮，解得將* 的表達(dá)式代入費(fèi)

37、用函數(shù) f ，那么最小總平均費(fèi)用:一、M / M / 1 模型中最優(yōu)效勞率* 第八章 排隊(duì)論例8-12 到某設(shè)備維修站維修的設(shè)備數(shù)為泊松流，平均每小時3臺。假設(shè)一臺設(shè)備停留在維修站1個小時，修理站要支付4元。假設(shè)維修站只有一名維修人員，他的工資是每小時每臺12元。為使工資與設(shè)備逗留費(fèi)之和最小，該維修員每小時應(yīng)維修多少臺？一、M / M / 1 模型中最優(yōu)效勞率* 第八章 排隊(duì)論解 一、M / M / 1 模型中最優(yōu)效勞率* 即每小時應(yīng)維修4臺設(shè)備。此時單位時間支出費(fèi)用為： 第八章 排隊(duì)論h為每個效勞臺單位時間本錢；C為效勞臺數(shù)；b為每個顧客逗留單位時間的費(fèi)用；LC為系統(tǒng)中有C個效勞臺時逗留的顧

38、客平均數(shù)。二、M / M / C 模型中最優(yōu)的效勞臺數(shù)C* 此處僅討論標(biāo)準(zhǔn)的 M / M / C 模型，當(dāng)系統(tǒng)處于穩(wěn)態(tài)，單位時間的全部費(fèi)用的期望值 f 為：因?yàn)镃是離散型變量，不能直接對 fC求微分。根據(jù)費(fèi)用函數(shù)存在最小值的必要條件，有第八章 排隊(duì)論將式中 f 代入，得hC* + bLC* hC* - 1+ bLC* - 1hC* + bLC* hC* + 1+ bLC* + 1依次求C =1、2、3時的 L 值，并作兩相鄰的 L 值的差，因?yàn)閔/b是數(shù)，根據(jù)這個數(shù)落在哪個不等式區(qū)間內(nèi)，就可求出C*。二、M / M / C 模型中最優(yōu)的效勞臺數(shù)C*第八章 排隊(duì)論例8-13 某醫(yī)院要確定試驗(yàn)設(shè)備

39、的最優(yōu)套數(shù)，經(jīng)統(tǒng)計(jì)平均每天來做試驗(yàn)有48人，泊松分布到達(dá)。假設(shè)每個做試驗(yàn)的人的停留損失為每天6元，試驗(yàn)時間服從指數(shù)分布，每臺設(shè)備效勞率為每天25人。提供一套試驗(yàn)設(shè)備的費(fèi)用每天4元。要求確定該院試驗(yàn)設(shè)備的最正確套數(shù)，使單位時間效勞本錢與逗留費(fèi)用之和最小。解 二、M / M / C 模型中最優(yōu)的效勞臺數(shù)C*第八章 排隊(duì)論將數(shù)據(jù)代入公式8-11求出：第八章 排隊(duì)論結(jié)果見表8-4 由第八章 排隊(duì)論 表8-4 f (C)的邊際分析設(shè)備套數(shù)C逗留人數(shù)L(C)L(C)-L(C+1)L(C-1)-L(C)f(c)20.020424.49021.845154.9430.12442.6450.58221.8452

40、7.8740.14222.0630.1110.58228.3850.14571.9520.11131.71 因?yàn)閔/b=0.667落在區(qū)間(0.582，21.845)內(nèi)，所以C=3時 第八章 排隊(duì)論例8-14 某醫(yī)院為了解決看病難問題，想增添B超設(shè)備，現(xiàn)已統(tǒng)計(jì)出平均每6分鐘就有1人做B超檢查，每人平均做20分鐘。假設(shè)假定患者到達(dá)的時間間隔和檢查時間均服從負(fù)指數(shù)分布，管理人員要求合理確定B超臺數(shù),使得系統(tǒng)滿足兩個目標(biāo)：每臺設(shè)備空閑率不大于40%；每位患者平均等待檢查的時間不超過5分鐘。試確定最正確B超設(shè)備臺數(shù)C。 解：第八章 排隊(duì)論滿足第一個目標(biāo)的條件是： 滿足第二個目標(biāo)的條件是： 所以，同時滿足兩個目標(biāo)的條件是：C = 5 第八章 排隊(duì)論第六節(jié) 案例分析案例8-1 某醫(yī)院欲購一臺X光機(jī)，現(xiàn)有四種可供選擇的機(jī)型。就診者按泊松分布到達(dá)，到達(dá)率每小時4人。四種機(jī)型效勞時間均服從指數(shù)分布，不同機(jī)型的固定費(fèi)用，操作費(fèi)，效勞率見表8-5。假設(shè)每位就診者在系統(tǒng)中逗留所造成的損失費(fèi)為每小時15元，試確定選購哪一類機(jī)型可使綜合費(fèi)固