作業(yè)計(jì)劃-運(yùn)營與物流管理研究中心

第12章作業(yè)打算主講：季建華教授運(yùn)營治理(OperationsManagement)等待是日常生活的一局部什么時(shí)候需要排隊(duì)？好玩嗎？為什么會(huì)消失排隊(duì)現(xiàn)象？假定每小時(shí)平均有4位顧客到達(dá)，效勞人員為每位顧客的平均效勞時(shí)間為15分鐘。假設(shè)顧客到達(dá)的間隔時(shí)間正好是15分鐘，而效勞人員為每位顧客的效勞時(shí)間也正好是15分鐘，那么，就只需要一名效勞人員，顧客也根本用不著等待。在以下狀況將消失排隊(duì)現(xiàn)象：平均到達(dá)率〔顧客/小時(shí)〕高于平均效勞率〔顧客/小時(shí)〕，就像紅酸果案例中的狀況一樣。顧客到達(dá)的間隔時(shí)間不一樣〔隨機(jī)〕。效勞時(shí)間不一樣〔隨機(jī)〕。顧客到達(dá)效勞設(shè)施顧客排隊(duì)顧客離開你覺得應(yīng)以怎樣的準(zhǔn)則排隊(duì)？超市收銀交貨期不同時(shí)病人看病………一個(gè)排序的例子四種型號(hào)的電視機(jī)的裝配工時(shí)定額型號(hào)部裝定額工時(shí)（小時(shí)）總裝定額工時(shí)（小時(shí)）ABC裝B（8）C(6)D（12）

總裝

A(4)

B（10）C(5)

D(7)〔a〕裝配挨次為A→B→C→D，總裝配時(shí)間為48小時(shí)部裝C（6）B（8）

總裝

C(5)

B（10）D（7）

〔b〕裝配挨次為C→B→D→A，總裝配時(shí)間為45小時(shí)部裝C（6）B（8）

總裝

D（7）C(5)

B(10)〔c〕裝配挨次為D→C→A→B，總裝配時(shí)間為51小時(shí)A（15）A（15）A（15）A(4)A(4)D（12）D(12)一個(gè)排序的例子為什么要排序？排序的目標(biāo)滿足交貨期縮短提前期降低準(zhǔn)備成本降低在制品庫存充分利用資源作業(yè)排序排序分類排序問題的分類服務(wù)業(yè)的排序問題流水作業(yè)排序問題制造業(yè)的排序問題服務(wù)者排序問題服務(wù)對(duì)象排序問題多服務(wù)者排序問題單服務(wù)者排序問題非流水作業(yè)排序問題靜態(tài)作業(yè)排序問題動(dòng)態(tài)作業(yè)排序問題排序?qū)ο笮袠I(yè)服務(wù)者數(shù)量加工路線服務(wù)對(duì)象到達(dá)制造業(yè)中的排序問題(ScheduleProbleminManufacturing)(一)n種工件在單臺(tái)設(shè)備上加工的排序1、平均流程時(shí)間最短〔SOT,SPT, ShortestOperatingTime ShortestProcessingTime〕Fi：流程(FlowTime) wi+tiwi：i工件的等待時(shí)間ti：i工件的加工時(shí)間平均流程F總流程：最大流程 Fmax=max(Fi)優(yōu)化目標(biāo)：平均流程↓t1≤t2≤……tnF=13.8Dmax=8di:i工件規(guī)定交貨時(shí)間(DueTime)Di:交貨延期量(DelayTime)J1J2J3J4J5J6ti482593di2423863213J3J6J1J4J2J5ti234589Di000800制造業(yè)中的排序問題(ScheduleProbleminManufacturing)2、使最大交貨延期量最小〔EDD規(guī)章，EarlyDeliveryDate〕d1≤d2≤……dn F=15.5Dmax=0J4J3J6J2J1J5ti523849Fi5710182231di6813232432Di000000制造業(yè)中的排序問題(ScheduleProbleminManufacturing)3、混合法1)先按EDD排序2)找出di＞maxFi的，按SPT排去掉找出的工件，剩下局部連續(xù)循環(huán)……….F=14.8,Dmax=0

單臺(tái)設(shè)備的使用場合：修理、單工藝，加工中心等J4J3J6J1J2J5ti523489Fi5710142231di6813242332Di000000制造業(yè)中的排序問題(ScheduleProbleminManufacturing)甘特圖

約翰遜——貝爾曼規(guī)章(Johnson-Bellman’sRule)J4 J1J2J3J5Fmax=40最優(yōu)解(二)n種工件在兩臺(tái)設(shè)備上的流水型排序問題

(SchedulingnJobson2Machines)J1J2J3J4J5tiA681237tiB119534制造業(yè)中的排序問題(ScheduleProbleminManufacturing)轉(zhuǎn)換條件：假設(shè)mintiA≥maxtiB或mintiC≥maxtiB可得最優(yōu)解，否則較優(yōu)解

零件機(jī)床及工時(shí)J1J2J3J4AtiA158612BtiB3156CtiC41057(三)n種工件在3臺(tái)機(jī)床上加工的流水型排序問題及解法制造業(yè)中的排序問題(ScheduleProbleminManufacturing)∵mintiA=6≥maxtiB=6∴可轉(zhuǎn)換

排序方案為：J2J4J3J1 Fmax=48 最優(yōu)解零件機(jī)床及工時(shí)J1J2J3J4GtiG1891118HtiH7111013制造業(yè)中的排序問題(ScheduleProbleminManufacturing)(四)n種工件在m臺(tái)機(jī)床上加工的流水型排序問題及解法(SchedulingnJobsonmMachines)1、約翰遜規(guī)章的擴(kuò)展法組合原則為：tiA= (h=1,2,……,m－1)tiB=,m－k+1共組合m－1次，每一次組合對(duì)應(yīng)一個(gè)挨次，從m－1種挨次的加工周期中挑最小的。?=h1kikt?=h1kit制造業(yè)中的排序問題(ScheduleProbleminManufacturing)2、關(guān)鍵零件法(KeyPartsModel)把總工時(shí)〔〕最大的零件作為關(guān)鍵零件，記為Jc,假設(shè)Max()=,則k零件為Jc1)除Jc外，凡ti1＜tim的零件，按ti1從小到大排在Jc前;2)除Jc外，凡滿足ti1＞tim的零件，按tim從大到小排在Jc后。3)假設(shè)ti1=tim，相應(yīng)零件既可排在Jc前，又可排在Jc后,得到多個(gè)方案，從中選最優(yōu)。?=m1jijt?=m1jkjt?=m1jijt制造業(yè)中的排序問題(ScheduleProbleminManufacturing)

零件機(jī)床工時(shí)J1J2J3J4J5J6M1ti15541210M2ti25553610M3ti3833474M4ti4282156M5ti55212810?=51jijt252315112840制造業(yè)中的排序問題(ScheduleProbleminManufacturing)用表格法計(jì)算總流程右上角零件等待左下角機(jī)床空閑

零件機(jī)床J4J5J1J6J2J3M1138182327M241015283338M381725323641M492227384648M5113035485051125622222281153335331制造業(yè)中的排序問題(ScheduleProbleminManufacturing)以上規(guī)章也有一些局限性1)生產(chǎn)系統(tǒng)(ProductionSystem)是動(dòng)態(tài)的，規(guī)章不行能考慮到各種變化2)規(guī)章看不到上游或下游的狀況〔設(shè)備的忙閑等〕3)看不到其他很多重要因素如延期交貨(DelayedDelivery)所造成的損失因此可依據(jù)規(guī)章無法考慮的因素作調(diào)整，用專家系統(tǒng)(ExpertSystem)或有交互功能的排序軟件制造業(yè)中的排序問題(ScheduleProbleminManufacturing)效勞業(yè)中的排序問題(ScheduleProbleminServiceIndustry)醫(yī)院病人等待問題人流、信息流分離與否可否挑選醫(yī)生價(jià)值觀顧客生產(chǎn)者長遠(yuǎn)市場

排序的對(duì)象是人而不是物；系統(tǒng)動(dòng)態(tài)與隨機(jī)性特點(diǎn)比制造業(yè)更突出；排序問題與排隊(duì)模型結(jié)合在一起而產(chǎn)生作用例：(一)劃分需求，進(jìn)展排序需求的分類隨機(jī)打算〔通過排序，平衡負(fù)荷(LoadBalance)〕 航空公司將乘客劃分為工作日商務(wù)乘客和周未旅游乘客。美國某醫(yī)院對(duì)需求分析顯示：非預(yù)約病人周一看病人數(shù)最多，而其他時(shí)間來的相對(duì)較少。非預(yù)約——隨機(jī)預(yù)約——可控——安排在每周后幾天，使負(fù)荷穩(wěn)定，削減等待時(shí)間。效勞業(yè)中的排序問題(ScheduleProbleminServiceIndustry)(二)排隊(duì)治理(WaitingLineManagement)1、排隊(duì)系統(tǒng)的根本特征需求群體排隊(duì)結(jié)構(gòu)服務(wù)結(jié)構(gòu)不再有服務(wù)需求與需求的時(shí)間分布空間分布有關(guān)到達(dá)過程退出排隊(duì)規(guī)則服務(wù)離開效勞業(yè)中的排序問題(ScheduleProbleminServiceIndustry)2、需求群體不同群體需求不同，每一類需求的預(yù)期等待時(shí)間(ExpectedWaitingTime)不同3、排隊(duì)構(gòu)造1)多條排隊(duì)(Multi-Line)2)單一排隊(duì)(Single-Line)3)領(lǐng)號(hào)效勞業(yè)中的排序問題(ScheduleProbleminServiceIndustry)需求群體同質(zhì)群體亞群體有限的無限的有限的無限的效勞業(yè)中的排序問題(ScheduleProbleminServiceIndustry)有限排隊(duì)(WaitingLinewithLimitedCapacity)假設(shè)等待場所無法容納全部需求效勞的顧客，一些人會(huì)離去，這種狀況稱為有限排隊(duì)效勞業(yè)中的排序問題(ScheduleProbleminServiceIndustry)2、需求群體不同群體需求不同，每一類需求的預(yù)期等待時(shí)間(ExpectedWaitingTime)不同3、排隊(duì)構(gòu)造1)多條排隊(duì)(Multi-Line)2)單一排隊(duì)(Single-Line)3)領(lǐng)號(hào)效勞業(yè)中的排序問題(ScheduleProbleminServiceIndustry)排隊(duì)結(jié)構(gòu)領(lǐng)號(hào)單一排隊(duì)多條排隊(duì)有限的無限的有限或無限允許/不允許移動(dòng)快速通道效勞業(yè)中的排序問題(ScheduleProbleminServiceIndustry)優(yōu)點(diǎn)多條排隊(duì)a)供給差異效勞(DifferentiateService)〔超市快速結(jié)帳〕b)顧客可選擇c)有助于削減不參加隊(duì)伍的現(xiàn)象效勞業(yè)中的排序問題(ScheduleProbleminServiceIndustry)單一排隊(duì)a)先到先效勞(FCFS,FirstComeFirstServe)b)顧客不會(huì)看到別的隊(duì)伍移動(dòng)得快而焦急c)插隊(duì)困難d)提高了效勞的私密性〔一米線〕效勞業(yè)中的排序問題(ScheduleProbleminServiceIndustry)領(lǐng)號(hào)a)顧客可四處走動(dòng)，但必需警覺是否叫到號(hào)。b)商店可利用“領(lǐng)號(hào)”系統(tǒng)增加顧客沖動(dòng)購物，掃瞄、多買效勞業(yè)中的排序問題(ScheduleProbleminServiceIndustry)效勞業(yè)中的排序問題(ScheduleProbleminServiceIndustry)4、效勞構(gòu)造單隊(duì)單服務(wù)臺(tái)單階段的服務(wù)排隊(duì)系統(tǒng)多隊(duì)多服務(wù)臺(tái)單階段的服務(wù)排隊(duì)系統(tǒng)單隊(duì)多服務(wù)臺(tái)單階段的服務(wù)排隊(duì)系統(tǒng)單隊(duì)單服務(wù)臺(tái)多階段的服務(wù)排隊(duì)系統(tǒng)單隊(duì)多服務(wù)臺(tái)多階段的服務(wù)排隊(duì)系統(tǒng)單隊(duì)單效勞臺(tái)單階段的效勞排隊(duì)系統(tǒng)多隊(duì)多效勞臺(tái)單階段的效勞排隊(duì)系統(tǒng)單隊(duì)多效勞臺(tái)單階段的效勞排隊(duì)系統(tǒng)單隊(duì)單效勞臺(tái)多階段的效勞排隊(duì)系統(tǒng)單隊(duì)多效勞臺(tái)多階段的效勞排隊(duì)系統(tǒng)5、排隊(duì)規(guī)章1)FCFS(FirstComeFirstServe)常用到SPT規(guī)章，但效勞時(shí)間長的不斷讓位于后到達(dá)者，所以先用SPT分類，然后FCFS〔超市，快速通道〕2)最高優(yōu)先權(quán)法則(HighestPriorityPrinciple)火警、搶救車為削減等待顧客離隊(duì)可能，應(yīng)讓顧客知道預(yù)期等待時(shí)間的信息，并使顧客得到定期更新的信息。效勞業(yè)中的排序問題(ScheduleProbleminServiceIndustry)6、調(diào)整顧客到達(dá)率的措施1〕利用預(yù)約系統(tǒng)掌握顧客到達(dá)時(shí)間實(shí)現(xiàn)最高程度的效勞力量利用率削減顧客等待的時(shí)間提高效勞水平2〕承受預(yù)訂系統(tǒng)對(duì)特定期間的效勞需求做出較準(zhǔn)確的估量3〕承受差異定價(jià)措施效勞業(yè)中的排序問題(ScheduleProbleminServiceIndustry)7、調(diào)整效勞力量的策略1〕進(jìn)展有效的人員班次排序2〕利用臨時(shí)工或兼職人員3〕聘請(qǐng)和培育多技能的員工4〕對(duì)組織構(gòu)造、體制與效勞流程進(jìn)展重組〔重復(fù)工作如多封同一信件廣告或流程重疊空檔造成力量鋪張〕〔“醫(yī)患關(guān)系緊急的責(zé)任”的辯論：仁濟(jì)醫(yī)院院長，律師〕效勞業(yè)中的排序問題(ScheduleProbleminServiceIndustry)排隊(duì)理論是二十世紀(jì)初在爭論系統(tǒng)時(shí)提出的方法排隊(duì)是指顧客或工件排隊(duì)等待效勞或加工隨機(jī)到達(dá)我們假設(shè)，在某段時(shí)間內(nèi)顧客到達(dá)是隨機(jī)的，互不相關(guān)，但平均到達(dá)率不變。顧客到達(dá)有很多來源每個(gè)來源到達(dá)率很低顧客到達(dá)互不相關(guān)例如，假定平均到達(dá)率是每小時(shí)16位顧客。但每個(gè)小時(shí)的實(shí)際到達(dá)人數(shù)是不一樣的。為什么會(huì)消失排隊(duì)現(xiàn)象？假定每小時(shí)平均有4位顧客到達(dá)，效勞人員為每位顧客的平均效勞時(shí)間為15分鐘。假設(shè)顧客到達(dá)的間隔時(shí)間正好是15分鐘，而效勞人員為每位顧客的效勞時(shí)間也正好是15分鐘，那么，就只需要一名效勞人員，顧客也根本用不著等待。在以下狀況將消失排隊(duì)現(xiàn)象：平均到達(dá)率〔顧客/小時(shí)〕高于平均效勞率〔顧客/小時(shí)〕，就像紅酸果案例中的狀況一樣。顧客到達(dá)的間隔時(shí)間不一樣〔隨機(jī)〕。效勞時(shí)間不一樣〔隨機(jī)〕。顧客到達(dá)效勞設(shè)施顧客排隊(duì)顧客離開衡量效勞系統(tǒng)表現(xiàn)的尺度輸出率=單位時(shí)間內(nèi)系統(tǒng)所效勞的平均顧客數(shù)。r=利用率=效勞時(shí)間所占的比例L=系統(tǒng)中的平均顧客數(shù)(包括正被效勞的)W=每位顧客在系統(tǒng)中平均逗留時(shí)間，即流程時(shí)間(包括承受效勞時(shí)間)Lq=在隊(duì)列中等待的平均顧客數(shù)Wq=每位顧客的平均等待時(shí)間，即排隊(duì)時(shí)間影響等待時(shí)間的因素顧客：以泊松分布方式到達(dá)l=平均到達(dá)率(單位時(shí)間到達(dá)的顧客數(shù)〕效勞時(shí)間：M=平均效勞時(shí)間s=效勞時(shí)間的方差效勞率〔人/小時(shí)〕：效勞臺(tái)數(shù)：czz排隊(duì)理論是設(shè)計(jì)和改進(jìn)生產(chǎn)系統(tǒng)的重要工具排隊(duì)理論的主要目標(biāo)是：由系統(tǒng)的參數(shù)〔顧客到達(dá)率、效勞時(shí)間、效勞臺(tái)數(shù)等等〕動(dòng)身，估量系統(tǒng)的表現(xiàn)，特殊是在時(shí)間方面的表現(xiàn)。主要方法：公式近似公式電腦模擬效勞臺(tái)利用率就是每個(gè)效勞臺(tái)實(shí)際工作時(shí)間所占比例。效勞臺(tái)利用率=

效勞臺(tái)利用率是衡量表現(xiàn)的重要指標(biāo)實(shí)例：平均到達(dá)率為每小時(shí)10位顧客；每位顧客平均要求10分鐘的效勞〔效勞時(shí)間〕，這樣在一個(gè)小時(shí)內(nèi)，平均就有100分鐘或者說1.667個(gè)小時(shí)的工作量；共有兩個(gè)效勞臺(tái)，每個(gè)可利用的時(shí)間為一個(gè)小時(shí)，這樣總計(jì)可利用時(shí)間為兩個(gè)小時(shí)。因此效勞臺(tái)利用率為1.667/2=83.3%.

另一種計(jì)算效勞臺(tái)利用率的方法效勞臺(tái)利用率=實(shí)例：平均到達(dá)率為每小時(shí)10位顧客；每個(gè)效勞臺(tái)的平均效勞時(shí)間為10分鐘，這樣一個(gè)效勞臺(tái)平均一小時(shí)可以為6位顧客供給效勞；共有兩個(gè)效勞臺(tái)；因此效勞臺(tái)利用率為10/(2*6)=0.833或者說83.3%

三種重要的關(guān)系“管道原理”:在一個(gè)穩(wěn)定系統(tǒng)中

平均輸出=平均輸入，或者輸出率=l利特爾法則：時(shí)間的可加性：在系統(tǒng)中逗留的時(shí)間等于效勞時(shí)間加排隊(duì)時(shí)間：利特爾法則依據(jù)利特爾法則：

實(shí)例1：某醫(yī)療機(jī)構(gòu)的平均到達(dá)率為每個(gè)月50位患者，平均逗留時(shí)間為兩個(gè)月。該醫(yī)院內(nèi)的平均患者數(shù)為多少？ 實(shí)例2：某銀行平均每天收到支票金額50萬元，支票的平均傳送、處理時(shí)間為三天。假定年利率為10%，該銀行每年在支票交易上的利息損失是多少？利特爾法則不僅適用于整個(gè)系統(tǒng)，而且也適用于系統(tǒng)的任何一局部。系統(tǒng)內(nèi)的平均顧客數(shù)=平均到達(dá)率

平均逗留時(shí)間單個(gè)效勞臺(tái);任意效勞時(shí)間分布一個(gè)穩(wěn)定系統(tǒng)的條件：利用率小于1：計(jì)算公式：s數(shù)值增大就意味著效勞時(shí)間有更多的可變性。而更多的可變性則會(huì)造成更多的擁塞和延誤，這樣就要等待更長的時(shí)間。實(shí)例以下是兩個(gè)計(jì)算機(jī)系統(tǒng)的有關(guān)數(shù)據(jù)：顧客的到達(dá)率為每小時(shí)15位。也就是說l=15/60=0.25位顧客/分鐘(留意:使用一樣的時(shí)間單位！)1號(hào)系統(tǒng)2號(hào)系統(tǒng)M(分鐘)3.03.1s(分鐘)2.11.0實(shí)例〔續(xù)〕1號(hào)計(jì)算機(jī)系統(tǒng)：2號(hào)計(jì)算機(jī)系統(tǒng)：慢的反而好！實(shí)例〔續(xù)〕單個(gè)效勞臺(tái)；效勞時(shí)間為指數(shù)分布效勞時(shí)間為指數(shù)分布，那么，M=s=1/m利用率：計(jì)算公式：假設(shè)把到達(dá)數(shù)量增加一倍(2l)，再把效勞率增加一倍(2m),等待時(shí)間就會(huì)削減一半。這就是排隊(duì)論的規(guī)模經(jīng)濟(jì)學(xué)。平均隊(duì)長與利用率的關(guān)系平均隊(duì)長〔和平均等待時(shí)間〕與效勞臺(tái)利用率之間的關(guān)系不是線性的關(guān)系。資產(chǎn)利用率太高會(huì)造成效勞質(zhì)量急速下降，因而要權(quán)衡利弊。要保證效勞質(zhì)量，就必需保持“過剩的”生產(chǎn)或效勞力量。平均隊(duì)長利用率實(shí)例一個(gè)效勞臺(tái)：指數(shù)效勞時(shí)間到達(dá)率=10/小時(shí)利用率平均排隊(duì)長度平均等待時(shí)間0.20.050.005小時(shí)(0.3分鐘)0.50.500.05小時(shí)(3.0分鐘)0.83.200.32小時(shí)

(19.2分鐘)0.98.100.81小時(shí)(48.6分鐘)0.9518.05