第十一章排隊(duì)論(運(yùn)籌學(xué)-重慶大學(xué),熊中楷)

運(yùn)籌學(xué)排隊(duì)論第十一章：排隊(duì)論應(yīng)用

老板開(kāi)一個(gè)香辣螃蟹連鎖店，要多少服務(wù)員？排隊(duì)論幫助公司進(jìn)行決策:第十一章：排隊(duì)論應(yīng)用

排隊(duì)過(guò)程服務(wù)過(guò)程離開(kāi)過(guò)程進(jìn)入的速度和離開(kāi)的速度決定系統(tǒng)擁擠的程度而進(jìn)入的速度取決于服務(wù)的速度和服務(wù)員人數(shù)服務(wù)系統(tǒng)忙閑程度顧客進(jìn)入系統(tǒng)的速度顧客離開(kāi)系統(tǒng)的速度到達(dá)的顧客要求服務(wù)的內(nèi)容服務(wù)的機(jī)構(gòu)1不能運(yùn)轉(zhuǎn)的機(jī)器修理修理技工2修理工領(lǐng)取修配零件分發(fā)修配零件的管理員3病人診斷或者手術(shù)醫(yī)生4電話(huà)呼喚通話(huà)交換臺(tái)5文件稿打印打字員6提貨單提貨倉(cāng)庫(kù)保管員7到達(dá)機(jī)場(chǎng)上空的飛機(jī)降落跑道8進(jìn)入港口的貨船裝貨碼頭9進(jìn)入我方陣地的敵機(jī)被打我方高炮10

應(yīng)用范圍

第十一章：排隊(duì)論應(yīng)用

決策目標(biāo)：分析系統(tǒng)，系統(tǒng)不能太忙，也不能太空閑決策變量：系統(tǒng)服務(wù)員的個(gè)數(shù)如果系統(tǒng)太忙，則有的顧客將不愿意等待而離開(kāi)，失去商機(jī)如果系統(tǒng)太閑，也不經(jīng)濟(jì)引例：服務(wù)系統(tǒng)忙閑程度顧客進(jìn)入系統(tǒng)的速度顧客離開(kāi)系統(tǒng)的速度第十一章：排隊(duì)論應(yīng)用

已知隨機(jī)服務(wù)系統(tǒng)，有三個(gè)服務(wù)員，平均每分鐘到達(dá)顧客數(shù)約為0.9人，每位顧客的平均服務(wù)時(shí)間約為2.5分鐘。問(wèn)服務(wù)員有多忙？（復(fù)旦大學(xué)研究生考題）第十一章：排隊(duì)論應(yīng)用

第十一章：排隊(duì)論應(yīng)用

（復(fù)旦大學(xué)研究生考題）分析：有三個(gè)服務(wù)員，平均每分鐘到達(dá)顧客數(shù)約為0.9人，相對(duì)于一個(gè)服務(wù)員來(lái)說(shuō)，平均每分鐘到達(dá)顧客數(shù)約為0.3人每位顧客的平均服務(wù)時(shí)間約為2.5分鐘，每分鐘服務(wù)顧客人數(shù)（1/2.5）即每分鐘有（1/2.5）＝0.4人離開(kāi)系統(tǒng)即每10分鐘有3人進(jìn)來(lái)，可以服務(wù)4人，因此三名服務(wù)員平均75％時(shí)間用于為顧客服務(wù)，有25％時(shí)間空閑服務(wù)系統(tǒng)忙閑程度顧客進(jìn)入系統(tǒng)的速度顧客離開(kāi)系統(tǒng)的速度1輸入過(guò)程(1)顧客的數(shù)目有限或者無(wú)限（2）顧客到達(dá)的方式可能是單個(gè)的，也可能是成批的這里不考慮成批的情況（3）顧客到達(dá)的過(guò)程隨機(jī)的第十一章：排隊(duì)論應(yīng)用

2排隊(duì)過(guò)程:（1）顧客有的有耐心，有的沒(méi)有耐心（2）先到先服務(wù)（3）后到先服務(wù)（4）隨機(jī)服務(wù)（5）有優(yōu)先權(quán)的服務(wù)3服務(wù)機(jī)構(gòu)：（1）服務(wù)員可能為0，1，2……（2）服務(wù)時(shí)間隨機(jī)（3）服務(wù)方式可能是單個(gè)的，也可能是成批的

排隊(duì)系統(tǒng)的組成：第十一章：排隊(duì)論應(yīng)用

X/Y/Z/A/B/C排隊(duì)模型的分類(lèi):顧客到達(dá)間隔時(shí)間分布不可控服務(wù)時(shí)間分布服務(wù)臺(tái)個(gè)數(shù)決策變量例：M/M/1//m/FCFSM/M/C/M/G/1M：負(fù)指數(shù)分布D:確定型G：一般服務(wù)時(shí)間分布FCFS:先到先服務(wù)系統(tǒng)容量限制顧客源數(shù)目服務(wù)規(guī)則如先到先服務(wù)titi+1到達(dá)間隔時(shí)間第i人服務(wù)時(shí)間Si第i人等待時(shí)間Wi第(i+1)人等待時(shí)間Wi+1等待時(shí)間Wi+1＝Max{0,Wi＋Si－ti}第十一章：排隊(duì)論應(yīng)用

第i-1人服務(wù)結(jié)束時(shí)間第i-1人到達(dá)時(shí)間ti第i人服務(wù)結(jié)束時(shí)間一天中船到達(dá)數(shù)n頻數(shù)（天）頻率01212/365=0.0331430.1182640.1753740.2034710.1955490.1346260.0717190.052840.011920.00510以上10.003合計(jì)3651.000第十一章：排隊(duì)論應(yīng)用

平均到達(dá)率＝（全年到達(dá)總數(shù)）/（365）＝3.48/天第十一章：排隊(duì)論應(yīng)用

顧客編號(hào)到達(dá)時(shí)間服務(wù)時(shí)間間隔時(shí)間等待時(shí)間顧客編號(hào)到達(dá)時(shí)間服務(wù)時(shí)間間隔時(shí)間等待時(shí)間顧客編號(hào)到達(dá)時(shí)間服務(wù)時(shí)間間隔時(shí)間等待時(shí)間10570142274315361561641191217512271018619435722346826310593612010382701145520124742313第十一章：排隊(duì)論應(yīng)用

到達(dá)間隔次數(shù)162103846536272819110以上1合計(jì)40服務(wù)時(shí)間次數(shù)1102103745546271819以上1合計(jì)41到達(dá)時(shí)間間隔分布表服務(wù)時(shí)間分布表P318平均間隔時(shí)間＝（最后一個(gè)到達(dá)時(shí)間142）/最人數(shù)40＝355分鐘/人平均到達(dá)率＝41/142＝0.28人/分鐘平均服務(wù)時(shí)間＝127/41＝3.12分鐘/人平均服務(wù)率＝41/127＝0.32人/分鐘服務(wù)臺(tái)平均到達(dá)率＝0.28人/分鐘平均服務(wù)率＝0.32人/分鐘服務(wù)強(qiáng)度＝0.28/

0.32＝第十一章：排隊(duì)論應(yīng)用

標(biāo)準(zhǔn)M/M/1///FCFSp322（1）輸入過(guò)程：顧客源無(wú)限，顧客單個(gè)到達(dá)，普阿松分布（2）排隊(duì)規(guī)則：?jiǎn)侮?duì)，隊(duì)長(zhǎng)無(wú)限制，先到先服務(wù)（3）服務(wù)機(jī)構(gòu)：?jiǎn)畏?wù)臺(tái)，服務(wù)時(shí)間獨(dú)立，負(fù)指數(shù)分布服務(wù)臺(tái)平均到達(dá)率a平均服務(wù)率b服務(wù)強(qiáng)度p＝a/

b<1(系統(tǒng)忙的概率)系統(tǒng)空閑概率＝1－服務(wù)強(qiáng)度系統(tǒng)狀態(tài)為n的概率＝（1－服務(wù)強(qiáng)度p）（服務(wù)強(qiáng)度p）n次方第十一章：排隊(duì)論應(yīng)用

一.系統(tǒng)中平均顧客數(shù)＝對(duì)n求和{（系統(tǒng)中n個(gè)顧客）（系統(tǒng)中有n個(gè)顧客的概率）}＝（系統(tǒng)忙的概率）/（系統(tǒng)閑的概率）二.系統(tǒng)中等待的平均顧客數(shù)＝對(duì)n求和{（系統(tǒng)中n－1個(gè)顧客）（系統(tǒng)中有n個(gè)顧客的概率）}＝（系統(tǒng)忙的概率）的平方/（系統(tǒng)閑的概率）三.系統(tǒng)中顧客逗留時(shí)間的期望值＝1/(平均服務(wù)率－平均到達(dá)率)四系統(tǒng)中顧客等待時(shí)間的期望值＝系統(tǒng)中顧客逗留時(shí)間的期望值－服務(wù)時(shí)間＝1/(平均服務(wù)率－平均到達(dá)率)－1/平均服務(wù)率P325排隊(duì)系統(tǒng)重要參數(shù)：第十一章：排隊(duì)論應(yīng)用

P326例3第十一章：排隊(duì)論應(yīng)用

案例分析：某港口提出四個(gè)擴(kuò)建方案，各個(gè)方案裝卸能力,各個(gè)方案的設(shè)備有固定費(fèi)用C1，（包括工資，設(shè)備折舊等）,運(yùn)行費(fèi)用C2

（包括燃料，電力等消耗）如下表：M為裝卸一艘貨船的平均時(shí)間

方案A方案B方案C方案D單位裝卸一艘貨船的平均時(shí)間1234小時(shí)固定費(fèi)用C1161051萬(wàn)元/小時(shí)運(yùn)行費(fèi)用C2114604830萬(wàn)元/小時(shí)第十一章：排隊(duì)論應(yīng)用

設(shè)貨船隨機(jī)達(dá)到，平均間隔為6小時(shí)，每艘貨船在港口停留一小時(shí)10萬(wàn)元，求總費(fèi)用最小的方案解答：總費(fèi)用=固定費(fèi)用+運(yùn)行費(fèi)用+停留費(fèi)用時(shí)間單位取作小時(shí)，則達(dá)到率λ＝1/6（單位時(shí)間到達(dá)船只數(shù)）四個(gè)方案的服務(wù)率分別為μA=1,μB=1/2,μC=1/3,μD=?（就是單位時(shí)間服務(wù)船只數(shù)，例如B方案每船服務(wù)時(shí)間2小時(shí)，因此B方案單位時(shí)間服務(wù)船只數(shù)1/2）因此服務(wù)強(qiáng)度分別為（例如B方案單位時(shí)間進(jìn)1/6,出1/2，忙期：1/3）ρA=1/6ρB=1/3ρC=1/2ρD=2/3根據(jù)L=ρ/(1-ρ)港口停留的貨輪平均數(shù)分別為：LA=1/5LB=1/2LC=1LD=2計(jì)算費(fèi)用如下表：第十一章：排隊(duì)論應(yīng)用

方案固定費(fèi)用C1ρ運(yùn)行費(fèi)ρC2L停留費(fèi)10L總費(fèi)用A161/61/6×114=191/5237B101/31/3×60=201/2535C51/21/2×48=2411039D12/32/3×30=2022041因此方案B費(fèi)用最少

第十一章：排隊(duì)論應(yīng)用

例：M/M/1排隊(duì)系統(tǒng)費(fèi)用分析。某港口提出四個(gè)擴(kuò)建方案，各個(gè)方案裝卸能力,各個(gè)方案的設(shè)備有固定費(fèi)用C1，（包括工資，設(shè)備折舊等）,運(yùn)行費(fèi)用C2（包括燃料，電力等消耗）如下表：M為裝卸一艘貨船的平均時(shí)間

方案A方案B方案C方案D單位平均時(shí)間M1234小時(shí)固定費(fèi)用C1161051萬(wàn)元/小時(shí)運(yùn)行費(fèi)用C2114604830萬(wàn)元/小時(shí)設(shè)貨船達(dá)到服從普阿松分布，平均間隔為6小時(shí)，每艘貨船在港口停留一小時(shí)10萬(wàn)元，求總費(fèi)用最小的方案第十一章：排隊(duì)論應(yīng)用

解:總費(fèi)用=固定費(fèi)用+運(yùn)行費(fèi)用+停留費(fèi)用時(shí)間單位取作小時(shí)，則達(dá)到率λ＝1/6四個(gè)方案的服務(wù)率分別為μA=1,μB=1/2,μC=1/3,μD=1/4因此服務(wù)強(qiáng)度分別為ρA=1/6ρB=1/3ρC=1/2ρD=2/3根據(jù)L=ρ/(1-ρ)港口停留的貨輪平均數(shù)分別為：LA