衛(wèi)生管理運(yùn)籌學(xué)排隊(duì)論

OperationalResearchonHealth

Basic

到達(dá)的時(shí)間間隔分布與服務(wù)時(shí)間Distributionof rrivalTimesand第四節(jié)OptimizationforQueuingBasicDistributionofDistributionof rrivalTimesandservice（SomeQueuing一、標(biāo)準(zhǔn)的MM1模型二、M/M/1/N模型三、MM1mm四、標(biāo)準(zhǔn)的MMC（OptimizationforQueuing（一）MM1模型中最優(yōu)服務(wù)率（二）M/M/c模型中最優(yōu)的服務(wù)臺(tái)數(shù)BasicBasicBasicBasic Basic排隊(duì)論（queuingtheory）是通過(guò)研究排隊(duì)系第一節(jié)基本概念Basic郎關(guān)于交換機(jī)的效率研究開始的，在第二次中為了對(duì)飛機(jī)場(chǎng)跑道的容納量進(jìn)行 Basic（一）輸入過(guò)程（InputBasic（二）排隊(duì)規(guī)則(Queuing排隊(duì)無(wú)限排隊(duì)與有限排隊(duì)混合制系統(tǒng)Basic排隊(duì)規(guī)則(queuing先到先服務(wù)(FCFS,firstcome,firstserved)后到先服務(wù)(LCFS,lastcome,firstserved)隨機(jī)服務(wù)(SIRO,serviceinrandomorder)有優(yōu)先權(quán)的服務(wù)(PS,priorityservice)Basic有多個(gè)服務(wù)臺(tái)的情形中，服務(wù)臺(tái)可以是串聯(lián)、并聯(lián)，也可以是混11111 2 2122cccc（并聯(lián)

（并聯(lián)Basic21c21c32121 Basic Basic X/Y/Z/A/B/BasicD確定型Ek———k GI———一般相互獨(dú)立（GeneralG一般（General）Basic如果排隊(duì)模型是：*/*/*/∞/∞/FCFS，則后兩項(xiàng)或后三項(xiàng)可以省略，只要寫：*/*/*/∞或*/*/*就可Basic對(duì)排隊(duì)問(wèn)題求解的目的在于研究排隊(duì)系統(tǒng)運(yùn)Basic n=0，1，2，…．隊(duì)長(zhǎng)有限制，最大數(shù)為Nn=0，1，C．即時(shí)制，服務(wù)臺(tái)個(gè)數(shù)是CBasictBasic Basic記忙期為B，閑期為I，平均忙期和平均閑期分別記為B、I。Basic平均到達(dá)率(Averagenumberofarrivalsenteringthesystemperunittime)Basic在平穩(wěn)狀態(tài)（Steadystate）下，隊(duì)長(zhǎng)的分布、等待時(shí)間的分布也會(huì)，系統(tǒng)的狀態(tài)概率分布不再隨時(shí)間變化。 主要數(shù)量指標(biāo)在瞬態(tài)與穩(wěn)態(tài)時(shí)的常用符 瞬 穩(wěn) 符 意N（t）時(shí)刻t時(shí)系統(tǒng)中的顧客數(shù)（又 系統(tǒng)的狀態(tài)或隊(duì)長(zhǎng) T（t）時(shí)刻t到達(dá)系統(tǒng)的顧客在系統(tǒng)

符 意系統(tǒng)處于平穩(wěn)狀態(tài)時(shí)的隊(duì)長(zhǎng)，其均值為L(zhǎng)，稱為平均隊(duì)系統(tǒng)處于平穩(wěn)狀態(tài)時(shí)的排隊(duì)系統(tǒng)處于平穩(wěn)狀態(tài)時(shí)顧客的系統(tǒng)處于平穩(wěn)狀態(tài)時(shí)顧客的等待時(shí)間，其均值記為Wq， 當(dāng)系統(tǒng)處于狀態(tài)n時(shí)，新來(lái)的顧客的平均到達(dá)率（單位時(shí)間內(nèi)來(lái)到系統(tǒng)的平均顧客數(shù) 統(tǒng)的平均服務(wù)率（ 內(nèi)可以服務(wù)完的顧客數(shù) Distributionof rrivalTimesandservice[例1]某醫(yī)院外科手術(shù)室根據(jù)就診和完成手術(shù)的時(shí)間記錄，任意100個(gè)工作小時(shí)，每小時(shí)來(lái)就診的數(shù)n的出現(xiàn)次數(shù)整理成到達(dá)數(shù)分布表，又任意100個(gè)完成手術(shù)的病例，所用時(shí)間t（小時(shí)）出現(xiàn)的次數(shù)整理成手術(shù)服務(wù)時(shí)間分布表。試計(jì)算的平均到達(dá)率、Distributionof rrivalTimesandservice 01234561完成手術(shù)時(shí)t（小時(shí)出現(xiàn)次數(shù)0.0-380.2-250.4-170.6-90.8-61.0-51.2以上0合計(jì)100Distributionof rrivalTimesandservice 01234561完成手術(shù)時(shí)t（小時(shí)出現(xiàn)次數(shù)0.0-380.2-250.4-170.6-90.8-61.0-51.2以上0合計(jì)100

Distributionof rrivalTimesandservice設(shè)：①N（t）表示在t時(shí)間區(qū)間內(nèi)到達(dá)的顧客數(shù)（t>0），且N（t）為 量，服從泊松分Distributionof rrivalTimesandservice

Var[N（t）]=λtDistributionofDistributionof rrivalTimesandservicePn(t)

eDistributionof rrivalTimesandservice無(wú)后效性——即在不相 的時(shí)間區(qū)間內(nèi)顧客到平穩(wěn)性——對(duì)充分小的△t，在時(shí)間區(qū)間[t，t+△t）內(nèi)有一個(gè)顧客到達(dá)的概率與t無(wú)關(guān)，而約與區(qū)間長(zhǎng)△t成普通性——對(duì)于充分小的△t，在時(shí)間區(qū)間[t，Distributionof rrivalTimesandservice 表9-10123456610解：依題意，患者平均到達(dá)率X

100

21.3026

P Distributionof rrivalTimesandservice隔時(shí)間T（也是隨量）服從負(fù)指數(shù)分布，反FT(t)1e

DistributionDistributionof rrivalTimesandservicef(t)etTE（T）=1/λ方差Var[T]=1/λ2DistributionofDistributionof rrivalTimesandserviceF(t)1ef(t)e

tt≥DistributionDistributionof rrivalTimesandservice成服務(wù)的顧客平均數(shù)之比，用ρDistributionof rrivalTimesandservice 服從參數(shù)為kμ的負(fù)指數(shù)分布，那么T=υ1+υ2+υ3 (t)

k(kt)k(k

e

t Distributionof rrivalTimesandservice[例]串列的k個(gè)服務(wù)臺(tái)，每臺(tái)服務(wù)時(shí)間相互獨(dú)立，服從相同的負(fù)指數(shù)分布（參數(shù)kμ），那么一顧客走完這k個(gè)服務(wù)臺(tái)總共所需要服務(wù)時(shí)間就服從上述的k階分布。Distributionof rrivalTimesandservice 當(dāng)k趨于無(wú)窮時(shí)，方差趨于0。因此，這時(shí) Distributionof rrivalTimesDistributionof rrivalTimesandservice

DistributionDistributionof rrivalTimesandservice生滅過(guò)程的性質(zhì):設(shè)N（t）（t≥0）為一個(gè)隨機(jī)（1）假設(shè)N（t）=n，那么從時(shí)刻t起到下一個(gè)顧客到達(dá)時(shí)刻止的時(shí)間服從參數(shù)為λn負(fù)指數(shù)分布，n=0，1，2，……；Distributionof rrivalTimesandservice假設(shè)N（t）=n，那么從時(shí)刻t起到下一個(gè)顧客離去時(shí)刻止的時(shí)間服從參數(shù)為μn負(fù)指數(shù)分布，n=0，1，2，……； P{N（t）=n}（n=0，1，2，……） ，因此，通常是求系統(tǒng)到達(dá)平穩(wěn)狀態(tài)時(shí)的狀態(tài)分布pn（n=0，1，一、標(biāo)準(zhǔn)的MM1—顧客源是無(wú)限的，顧客單個(gè)到來(lái)，相服務(wù)機(jī)構(gòu)—單服務(wù)臺(tái)，各顧客的服務(wù)時(shí)間相互獨(dú)通用記號(hào)為MM1或MMP0=P0=Pn=(1－ρ)n≥ ．平均隊(duì)長(zhǎng)L(Averagenumberofcustomerspresentinthequeuingsystem)L

n(1)

1

2．平均排隊(duì)長(zhǎng)Lq(Averagenumberofcustomerswaitinginline)Lq(n

L

平均逗留時(shí)間W(Averagetimeacustomerspendsinthesystem) 量），在M/M/分布函數(shù)F（w）=1-e-(μ—λ)w w≥0概率函數(shù)f（w）=（μ-λ）e-(μ—λ)wWE[T]

平均等待時(shí)間Wq(Averagetimeacustomerspendsinline) W1 q2(1（4）Wq(L

，WW ，LL B I

1B 1 1 平均逗留時(shí)間(W)P(1P(1) (1)( n

s101s112s20s21s2解：這是一個(gè)M/M/1//系統(tǒng)，單列，F(xiàn)CFS20（人小時(shí)），6024（人小時(shí)利 （9-2）

P111200.1667

2 q））L24q））

L（－

Lq4.1670.2083（小時(shí)）12.5（分鐘

W

24表9- 服務(wù)率A85B6C7D8解：M/M/1//系統(tǒng)，單列，F(xiàn)CFS規(guī)則．依題意只需計(jì)算各種機(jī)型 A

B

綜合費(fèi)f: 1

2

15L,計(jì)算后將各類指標(biāo)及綜合費(fèi)列入表9-4表9- 四種機(jī)型在1小時(shí)內(nèi)的綜合費(fèi)操作費(fèi)L逗留損失費(fèi)綜合費(fèi)A84B2CD1[課堂練習(xí)1] 某三級(jí)醫(yī)院出院處平均每5分鐘有1人辦理間服從負(fù)指數(shù)分布，平均每份需要4分鐘。如果該出院 解：該情形可視為MM/1系統(tǒng)，若取單位時(shí)間為5分 機(jī)空閑的概率；（2）放射科剛好有3名 的概 （7）每 平均等待檢查時(shí)間 λ=4μ=1/0.1=10ρ=λ/μ=0.4 數(shù):Lq=L-ρ=ρ2/（1- 時(shí)）看專家門診的平均數(shù)為12人，診治時(shí)間平均每人15分鐘。假定到達(dá)服從泊松分布，服務(wù)時(shí)間（1）這個(gè)排隊(duì)系統(tǒng)的各項(xiàng)運(yùn)行指標(biāo)（Ls，Lq，Ws，Wq）；（2）在門診室的停留時(shí)間在1小時(shí)以上的概率（在系統(tǒng)中停留時(shí)間W服從參數(shù)為μ-λ的負(fù)指數(shù)分布；（3）門診室內(nèi)有5位及以上的概二、MM1NM/M/1/N模型指顧客到達(dá)數(shù)服從參數(shù)為λ的泊單服務(wù)員，系統(tǒng)最大容量為N，先到先服務(wù)。在這種排隊(duì)模型中，排隊(duì)等待的顧客最多為N-1。在某一時(shí)刻，如果系統(tǒng)中已有N個(gè)顧客，那么再到達(dá)的顧客將被“”而離開系統(tǒng)。當(dāng)N=1時(shí)，即為即時(shí)制的情形；當(dāng)N趨于無(wú)窮時(shí)，為系統(tǒng)容當(dāng)系統(tǒng)達(dá)到平穩(wěn)狀態(tài)，M/M/1/N模型狀態(tài)P1

0n

1N1 N1N時(shí)，后來(lái)的顧客將被“ ”（即到達(dá)率為0），此概率為PN，則單位時(shí)間內(nèi)遭到“ 顧客數(shù)為λPN。故，有效到達(dá)率λe =λ有效到達(dá)率也可按λe（1-P0）M/M/1/N排隊(duì)系統(tǒng)的其它數(shù)量指標(biāo)（L

(N

L

L(1P1WL

1NL

W (1PN 111N 11- NPn 1-11[1[1(1)NNN1L(1)(1N1N2NN11N qN(2(1) LLq qee已知N4 601.2（人/小時(shí)），601.5（人/小時(shí)），0.80P0

1

1

的概率P4P0.84×0.2975 L

等待隊(duì)長(zhǎng)

LqL1P01.5610.29750.8575（人有效到達(dá)率1P1.510.29751.054（人/小時(shí) 逗留時(shí)間WL1.561.48（小時(shí)）89（分鐘 等待時(shí)間

0.85750.81（小時(shí)）49（分鐘e e[課堂練習(xí)3]某醫(yī)院體檢中心設(shè)有1臺(tái)彩色超聲心動(dòng)圖機(jī)，上午可對(duì)7個(gè)進(jìn)行檢查。如果的到達(dá)按泊松分布，平均到達(dá)率為1.5人/小時(shí)，檢查時(shí)間服從負(fù)指數(shù)分布，平均服務(wù)解：該系統(tǒng)可視為1個(gè)M/M/1/7排隊(duì)系統(tǒng)，其中 數(shù)：Lq=2.11-（1-0.2778）=1.39（人4λeμ（1-P0）2（1-0.2778）1.44（人/小WqW1/μ1.461/20.96（小時(shí)）=57.6（分鐘[課堂練習(xí)]某醫(yī)院針灸科有1名針灸師，只安置3個(gè)座位供候診，一旦滿座則后來(lái)者不再進(jìn)屋等候。已知到達(dá)間隔與治療時(shí)間均為指數(shù)25分鐘。試求任一期望候診時(shí)間及該科潛在三、MM1mmλe=λ（m-p

m i

(mi)!(

(mn)!()

1≤n≤

Lm(1P

Lqm

0

L(10)

WL

W

(1P0）(1 PP0mk1m-k! n（m-n0(1nmLm(1P0 L(1Pq0WLL qqWee1該模型是指單位時(shí)間內(nèi)每個(gè)顧客到達(dá)系統(tǒng)次數(shù)服從參數(shù)為的泊松分布，服務(wù)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布，單服務(wù)臺(tái)，顧客源總數(shù)為m，系 （9- 已知：5(人/小時(shí)），6015(人/小時(shí)）， 0m 0m6m 6(mk)

6 1 k

k

(6k)!3(19.17) 0.0522 5.22% 6Pk1P0P110.05220.10430.843584.35%6k Lm(1P615(10.0522)3.16（人 因?yàn)橛行У竭_(dá)率:e1P01510.052214.217 Lq 0.1554（小時(shí)）9（分鐘e e四、標(biāo)準(zhǔn)的MMC圖9-4MMC務(wù)機(jī)構(gòu)的平均服務(wù)率為cμ（當(dāng)n≥c）或nμ（當(dāng)n≤c）。定義ρ=λ/cμ，當(dāng)λcμc1

1

)c

k! c!1 （0≤n

n!()

（c≤n

LL

(c)cLq

c!(1)2

W

Wqc0P(nc)Pnc0

1 C!

P(1

1 P C!(1) C KK!C!111C,其中 ，且C10npnn!C!Cn1Cn ( (C)CC!(1)2LLq qWLWqC4 4 14P (3)0 (3)1 (3)2 (3)3 (3) 4!13 0.0377(43)4 40.0377 （ !(134)L1.5344

453（Wq

11.530.1275（）8（12W 12

4.530.3775（小時(shí)）23（分鐘P(n 4)1P(n3)1( PPP 1(P3P9P9P)0.509450.94% 【例7】在例2中，為了減少患者等待取藥的時(shí)間，考慮增加一名藥劑員，其現(xiàn)考慮增加一名藥劑員后系統(tǒng)為M/M/2//，此時(shí)C220（人/小時(shí)），24（人/小時(shí)）， ①系統(tǒng)空閑的概率：P 120

2!(15/12)24

K Lq0.175（人），L1.008（人），Wq32（秒），W3（分鐘該模型系統(tǒng)顧客源無(wú)限，容量為N（NC），當(dāng)系統(tǒng)中顧客數(shù)達(dá)到N時(shí)，后來(lái)的顧客被進(jìn)P0P0CK(C)KKC(cN)1(0npCCnC!n0(CnN(nN q( q(C)cC!(1)2P01NC N 1NLL1PqN qWLWqee C4，N4， 0.5（人/天）， （人/天）， K K 1K!K!

0 0

K

4.16%

L0W0W1 天 該模型系統(tǒng)有C(C1)個(gè)服務(wù)臺(tái)，顧客源為m（m C），每個(gè)顧客在單位時(shí)間內(nèi)需要服務(wù)的平均次數(shù)為，每01011C!KC1(mK)!Cm1Km0nPn PnnC 0C1nLLnm LmLWqWeee(me C3，0.5（小時(shí)），5（小時(shí)）m181

0.5K

18!K0K!(18K)!5 3!K4(18K)!15 P(n3)1P(n2)1PP 10.17010.30620.2603③系統(tǒng)工作指標(biāo)：L nPn00.170110.306220.2603L180.0000 (人n W1.83 (小時(shí))14(分鐘), 0.21 (小時(shí))1.6(分鐘 C1， (人次/小時(shí))， (人次/小時(shí) 1 10＋2 q2(1L＋2 L2(1qWqWLq

ET11小時(shí)，DT15小時(shí)2人小時(shí)

2/

P11

2

22

3 4人） 3q212 3q ③等候檢查的時(shí)間：W＝q 0.2小時(shí)）1分

份/小時(shí)），60（份/小時(shí)ET1

0，

P0110.50.52 2(1)

0.25（份）,LLq0.250.50.75（份 Lq0.25

（小時(shí)）30（秒）,WL0.750.025（小時(shí)）1.5（分鐘 考慮在M/M/1//系統(tǒng)中，進(jìn)入系統(tǒng)的顧客分為12，第i級(jí)顧客在系統(tǒng)中的平均逗留時(shí)間Wi(i=1,2),LqLq1

Wq1Wq1 LL1 11 1L 1 1W 1L 211 1 11 1W 1L L 111L 221 1 i1 12111 10%0.20（小時(shí)），90%1.8（小時(shí)）

Wq1

0.0132（小時(shí)）0.79（分鐘

1（

424 q q11 1

0.0263（q 2 q211 2

0.4737

Lq

2 1 1

0.5（人W Lq0.50.25（小時(shí)

[課堂練習(xí)]某醫(yī)院新建門診大樓，婦科門診設(shè)3個(gè)診室。已知到達(dá)服從泊松分布，平均到達(dá)

表1：MM型2MM1M/M/1∞/11NM/M/1/m/m1mmM/M/C∞/M/M/CN/NM/M/C/m/mmmM/G/11E（Tc）min=E（Wc）+ 望 用（Wc） （一）MM1模型中最優(yōu)服務(wù)率ECsCwECsCw

單位時(shí)間內(nèi)服務(wù)一個(gè)顧客的費(fèi)用；Cw為每個(gè)顧客在系統(tǒng) d

( ) ( ) ( )( ) CCs CCsCCwsCCws

C Cs因?yàn)樵跇?biāo)準(zhǔn)M/M/1模型中，要求ρ<1（即CwCw