作業(yè)計(jì)劃主講季建華教授.ppt

第12章 作業(yè)計(jì)劃 主講：季建華教授,運(yùn)營(yíng)管理(Operations Management),等待是日常生活的一部分,什么時(shí)候需要排隊(duì)？,有趣嗎？,為什么會(huì)出現(xiàn)排隊(duì)現(xiàn)象？,假定每小時(shí)平均有4位顧客到達(dá)，服務(wù)人員為每位顧客的平均服務(wù)時(shí)間為15分鐘。如果顧客到達(dá)的間隔時(shí)間正好是15分鐘，而服務(wù)人員為每位顧客的服務(wù)時(shí)間也正好是15分鐘，那么，就只需要一名服務(wù)人員，顧客也根本用不著等待。 在以下情況將出現(xiàn)排隊(duì)現(xiàn)象： 平均到達(dá)率（顧客/小時(shí)）高于平均服務(wù)率（顧客/小時(shí)），就像紅酸果案例中的情況一樣。 顧客到達(dá)的間隔時(shí)間不一樣（隨機(jī)）。 服務(wù)時(shí)間不一樣 （隨機(jī)）。,顧客 到達(dá),服務(wù)設(shè)施,顧客排隊(duì),顧客 離開,你覺得應(yīng)以怎樣的準(zhǔn)則排隊(duì)？,超市收銀 交貨期不同時(shí) 病人看病 ,一個(gè)排序的例子,四種型號(hào)的電視機(jī)的裝配工時(shí)定額,（a）裝配順序?yàn)锳BCD，總裝配時(shí)間為48小時(shí),（b）裝配順序?yàn)镃BDA，總裝配時(shí)間為45小時(shí),（c）裝配順序?yàn)镈CAB，總裝配時(shí)間為51小時(shí),D(12),一個(gè)排序的例子,為什么要排序？,排序的目標(biāo),排序分類,制造業(yè)中的排序問(wèn)題(Schedule Problem in Manufacturing),(一)n種工件在單臺(tái)設(shè)備上加工的排序 1、平均流程時(shí)間最短（SOT,SPT, Shortest Operating Time Shortest Processing Time） Fi：流程(Flow Time) wi+ti wi：i工件的等待時(shí)間 ti：i工件的加工時(shí)間 平均流程 F 總流程：最大流程 Fmax=max(Fi) 優(yōu)化目標(biāo)：平均流程 t1t2tn,F=13.8 Dmax=8 di: i工件規(guī)定交貨時(shí)間(Due Time) Di:交貨延期量(Delay Time),制造業(yè)中的排序問(wèn)題(Schedule Problem in Manufacturing),2、使最大交貨延期量最小 （EDD規(guī)則，Early Delivery Date） d1d2dn F=15.5 Dmax=0,制造業(yè)中的排序問(wèn)題(Schedule Problem in Manufacturing),3、混合法 1) 先按EDD排序 2) 找出dimaxFi的，按SPT排 去掉找出的工件，剩下部分繼續(xù)循環(huán) . F=14.8,Dmax=0,單臺(tái)設(shè)備的使用場(chǎng)合：維修、單工藝，加工中心等,制造業(yè)中的排序問(wèn)題(Schedule Problem in Manufacturing),甘特圖,約翰遜貝爾曼規(guī)則(Johnson-Bellmans Rule) J4 J1 J2 J3 J5 Fmax=40 最優(yōu)解,(二) n種工件在兩臺(tái)設(shè)備上的流水型排序問(wèn)題 (Scheduling n Jobs on 2 Machines),制造業(yè)中的排序問(wèn)題(Schedule Problem in Manufacturing),轉(zhuǎn)換條件：若min tiAmax tiB 或min tiCmax tiB 可得最優(yōu)解，否則較優(yōu)解,(三) n種工件在3臺(tái)機(jī)床上加工的流水型排序問(wèn)題及解法,制造業(yè)中的排序問(wèn)題(Schedule Problem in Manufacturing),min tiA=6max tiB=6 可轉(zhuǎn)換 排序方案為：J2 J4 J3 J1 Fmax=48 最優(yōu)解,制造業(yè)中的排序問(wèn)題(Schedule Problem in Manufacturing),(四) n種工件在m臺(tái)機(jī)床上加工的流水型排序問(wèn)題及解法(Scheduling n Jobs on m Machines),1、約翰遜規(guī)則的擴(kuò)展法 組合原則為： tiA= (h=1, 2, ,m1) tiB= ,mk+1 共組合m1次，每一次組合對(duì)應(yīng)一個(gè)順序，從m1種順序的加工周期中挑最小的。,制造業(yè)中的排序問(wèn)題(Schedule Problem in Manufacturing),2、關(guān)鍵零件法(Key Parts Model) 把總工時(shí)（ ）最大的零件作為關(guān)鍵零件，記為Jc, 若Max( )= , 則k零件為Jc 1) 除Jc外，凡ti1tim的零件，按ti1從小到大排在Jc前 ; 2) 除Jc外，凡滿足ti1tim的零件，按tim從大到小排在Jc后。 3) 若ti1=tim，相應(yīng)零件既可排在Jc前，又可排在Jc后 ,得到多個(gè)方案，從中選最優(yōu)。,制造業(yè)中的排序問(wèn)題(Schedule Problem in Manufacturing),制造業(yè)中的排序問(wèn)題(Schedule Problem in Manufacturing),用表格法計(jì)算總流程,右上角零件等待 左下角機(jī)床空閑,制造業(yè)中的排序問(wèn)題(Schedule Problem in Manufacturing),以上規(guī)則也有一些局限性 1) 生產(chǎn)系統(tǒng)(Production System)是動(dòng)態(tài)的，規(guī)則不可能考慮到各種變化 2) 規(guī)則看不到上游或下游的情況（設(shè)備的忙閑等） 3) 看不到其他許多重要因素 如延期交貨(Delayed Delivery)所造成的損失 因此可根據(jù)規(guī)則無(wú)法考慮的因素作調(diào)整，用專家系統(tǒng)(Expert System)或有交互功能的排序軟件,制造業(yè)中的排序問(wèn)題(Schedule Problem in Manufacturing),服務(wù)業(yè)中的排序問(wèn)題(Schedule Problem in Service Industry),排序的對(duì)象是人而不是物；系統(tǒng)動(dòng)態(tài)與隨機(jī)性特點(diǎn)比制造業(yè)更突出；排序問(wèn)題與排隊(duì)模型結(jié)合在一起而產(chǎn)生作用 例：,(一) 劃分需求，進(jìn)行排序,需求的分類 隨機(jī) 計(jì)劃（通過(guò)排序，平衡負(fù)荷(Load Balance)） 航空公司將乘客劃分為工作日商務(wù)乘客和周未旅游乘客。 美國(guó)某醫(yī)院對(duì)需求分析顯示： 非預(yù)約病人周一看病人數(shù)最多，而其他時(shí)間來(lái)的相對(duì)較少。 非預(yù)約隨機(jī) 預(yù)約可控安排在每周后幾天，使負(fù)荷穩(wěn)定，減少等待時(shí)間。,服務(wù)業(yè)中的排序問(wèn)題(Schedule Problem in Service Industry),(二) 排隊(duì)管理(Waiting Line Management),1、排隊(duì)系統(tǒng)的基本特征,服務(wù)業(yè)中的排序問(wèn)題(Schedule Problem in Service Industry),2、需求群體 不同群體需求不同，每一類需求的預(yù)期等待時(shí)間(Expected Waiting Time)不同 3、排隊(duì)結(jié)構(gòu) 1) 多條排隊(duì)(Multi-Line) 2) 單一排隊(duì)(Single-Line) 3) 領(lǐng)號(hào),服務(wù)業(yè)中的排序問(wèn)題(Schedule Problem in Service Industry),服務(wù)業(yè)中的排序問(wèn)題(Schedule Problem in Service Industry),有限排隊(duì)(Waiting Line with Limited Capacity) 若等待場(chǎng)所無(wú)法容納所有需求服務(wù)的顧客，一些人會(huì)離去， 這種情況稱為有限排隊(duì),服務(wù)業(yè)中的排序問(wèn)題(Schedule Problem in Service Industry),2、需求群體 不同群體需求不同，每一類需求的預(yù)期等待時(shí)間(Expected Waiting Time)不同 3、排隊(duì)結(jié)構(gòu) 1) 多條排隊(duì)(Multi-Line) 2) 單一排隊(duì)(Single-Line) 3) 領(lǐng)號(hào),服務(wù)業(yè)中的排序問(wèn)題(Schedule Problem in Service Industry),服務(wù)業(yè)中的排序問(wèn)題(Schedule Problem in Service Industry),優(yōu)點(diǎn) 多條排隊(duì) a) 提供差別服務(wù)(Differentiate Service)（超市快速結(jié)帳） b) 顧客可選擇 c) 有助于減少不加入隊(duì)伍的現(xiàn)象,服務(wù)業(yè)中的排序問(wèn)題(Schedule Problem in Service Industry),單一排隊(duì) a) 先到先服務(wù)(FCFS,First Come First Serve) b) 顧客不會(huì)看到別的隊(duì)伍移動(dòng)得快而著急 c) 插隊(duì)困難 d) 提高了服務(wù)的私密性（一米線 ）,服務(wù)業(yè)中的排序問(wèn)題(Schedule Problem in Service Industry),領(lǐng)號(hào) a) 顧客可四處走動(dòng)，但必須警覺是否叫到號(hào)。 b) 商店可利用“領(lǐng)號(hào)”系統(tǒng)增加顧客沖動(dòng)購(gòu)物，瀏覽、多買,服務(wù)業(yè)中的排序問(wèn)題(Schedule Problem in Service Industry),服務(wù)業(yè)中的排序問(wèn)題(Schedule Problem in Service Industry),4、服務(wù)結(jié)構(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),5、排隊(duì)規(guī)則,1) FCFS(First Come First Serve) 常用到SPT規(guī)則，但服務(wù)時(shí)間長(zhǎng)的不斷讓位于后到達(dá)者，所以先用SPT分類，然后FCFS（超市，快速通道） 2) 最高優(yōu)先權(quán)法則(Highest Priority Principle) 火警、救護(hù)車 為減少等待顧客離隊(duì)可能，應(yīng)讓顧客知道預(yù)期等待時(shí)間的信息，并使顧客得到定期更新的信息。,服務(wù)業(yè)中的排序問(wèn)題(Schedule Problem in Service Industry),6、調(diào)整顧客到達(dá)率的措施 1）利用預(yù)約系統(tǒng) 控制顧客到達(dá)時(shí)間 實(shí)現(xiàn)最高程度的服務(wù)能力利用率 減少顧客等待的時(shí)間 提高服務(wù)水平 2）采用預(yù)訂系統(tǒng) 對(duì)特定期間的服務(wù)需求做出較準(zhǔn)確的估計(jì) 3）采用差異定價(jià)措施,服務(wù)業(yè)中的排序問(wèn)題(Schedule Problem in Service Industry),7、調(diào)整服務(wù)能力的策略 1）進(jìn)行有效的人員班次排序 2）利用臨時(shí)工或兼職人員 3）招聘和培養(yǎng)多技能的員工 4）對(duì)組織結(jié)構(gòu)、體制與服務(wù)流程進(jìn)行重組（重復(fù)工作 如多封同一信件廣告或流程重疊空檔 造成能力浪費(fèi)）（“醫(yī)患關(guān)系緊張的責(zé)任”的辯論：仁濟(jì)醫(yī)院院長(zhǎng)，律師）,服務(wù)業(yè)中的排序問(wèn)題(Schedule Problem in Service Industry),排隊(duì)理論,是二十世紀(jì)初在研究電話系統(tǒng)時(shí)提出的方法 排隊(duì)是指顧客或工件排隊(duì)等待服務(wù)或加工,隨機(jī)到達(dá),我們假設(shè)，在某段時(shí)間內(nèi)顧客到達(dá)是隨機(jī)的，互不相關(guān)，但平均到達(dá)率不變。 顧客到達(dá)有許多來(lái)源 每個(gè)來(lái)源到達(dá)率很低 顧客到達(dá)互不相關(guān) 例如，假定平均到達(dá)率是每小時(shí)16位顧客。但每個(gè)小時(shí)的實(shí)際到達(dá)人數(shù)是不一樣的。,為什么會(huì)出現(xiàn)排隊(duì)現(xiàn)象？,假定每小時(shí)平均有4位顧客到達(dá)，服務(wù)人員為每位顧客的平均服務(wù)時(shí)間為15分鐘。如果顧客到達(dá)的間隔時(shí)間正好是15分鐘，而服務(wù)人員為每位顧客的服務(wù)時(shí)間也正好是15分鐘，那么，就只需要一名服務(wù)人員，顧客也根本用不著等待。 在以下情況將出現(xiàn)排隊(duì)現(xiàn)象： 平均到達(dá)率（顧客/小時(shí)）高于平均服務(wù)率（顧客/小時(shí)），就像紅酸果案例中的情況一樣。 顧客到達(dá)的間隔時(shí)間不一樣（隨機(jī)）。 服務(wù)時(shí)間不一樣 （隨機(jī)）。,顧客 到達(dá),服務(wù)設(shè)施,顧客排隊(duì),顧客 離開,衡量服務(wù)系統(tǒng)表現(xiàn)的尺度,輸出率 =單位時(shí)間內(nèi)系統(tǒng)所服務(wù)的平均顧客數(shù)。 r = 利用率 = 服務(wù)時(shí)間所占的比例 L = 系統(tǒng)中的平均顧客數(shù) (包括正被服務(wù)的) W = 每位顧客在系統(tǒng)中平均逗留時(shí)間，即流程時(shí)間 (包括接受服務(wù)時(shí)間) Lq = 在隊(duì)列中等待的平均顧客數(shù) Wq = 每位顧客的平均等待時(shí)間，即排隊(duì)時(shí)間,影響等待時(shí)間的因素,顧客：以泊松分布方式到達(dá) l = 平均到達(dá)率 (單位時(shí)間到達(dá)的顧客數(shù)） 服務(wù)時(shí)間： M = 平均服務(wù)時(shí)間 s = 服務(wù)時(shí)間的方差 服務(wù)率（人/小時(shí)） ：,服務(wù)臺(tái)數(shù)： c,zz,排隊(duì)理論是設(shè)計(jì)和改進(jìn)生產(chǎn)系統(tǒng)的重要工具,排隊(duì)理論的主要目標(biāo)是： 由系統(tǒng)的參數(shù)（顧客到達(dá)率、服務(wù)時(shí)間、服務(wù)臺(tái)數(shù)等等）出發(fā)，估計(jì)系統(tǒng)的表現(xiàn)，特別是在時(shí)間方面的表現(xiàn)。 主要方法： 公式 近似公式 電腦模擬,服務(wù)臺(tái)利用率就是每個(gè)服務(wù)臺(tái)實(shí)際工作時(shí)間所占比例。 服務(wù)臺(tái)利用率 =,服務(wù)臺(tái)利用率是衡量表現(xiàn)的重要指標(biāo),實(shí)例： 平均到達(dá)率為每小時(shí)10位顧客； 每位顧客平均要求10分鐘的服務(wù)（服務(wù)時(shí)間），這樣在一個(gè)小時(shí)內(nèi)，平均就有100分鐘或者說(shuō) 1.667個(gè)小時(shí)的工作量； 共有兩個(gè)服務(wù)臺(tái)，每個(gè)可利用的時(shí)間為一個(gè)小時(shí)，這樣總計(jì)可利用時(shí)間為兩個(gè)小時(shí)。 因此服務(wù)臺(tái)利用率為1.667/2 = 83.3%.,另一種計(jì)算服務(wù)臺(tái)利用率的方法,服務(wù)臺(tái)利用率 =,實(shí)例： 平均到達(dá)率為每小時(shí)10位顧客； 每個(gè)服務(wù)臺(tái)的平均服務(wù)時(shí)間為10分鐘，這樣一個(gè)服務(wù)臺(tái)平均一小時(shí)可以為6位顧客提供服務(wù)； 共有兩個(gè)服務(wù)臺(tái)； 因此服務(wù)臺(tái)利用率為 10/(2*6) = 0.833 或者說(shuō)83.3%,三種重要的關(guān)系,“管道原理”: 在一個(gè)穩(wěn)定系統(tǒng)中 平均輸出 = 平均輸入，或者輸出率 = l 利特爾法則：,時(shí)間的可加性：在系統(tǒng)中逗留的時(shí)間等于服務(wù)時(shí)間加排隊(duì)時(shí)間：,利特爾法則,根據(jù)利特爾法則： 實(shí)例1：某醫(yī)療機(jī)構(gòu)的平均到達(dá)率為每個(gè)月50位患者，平均逗留時(shí)間為兩個(gè)月。該醫(yī)院內(nèi)的平均患者數(shù)為多少？ 實(shí)例2：某銀行平均每天收到支票金額50萬(wàn)元，支票的平均傳送、處理時(shí)間為三天。假定年利率為10%，該銀行每年在支票交易上的利息損失是多少？ 利特爾法則不僅適用于整個(gè)系統(tǒng)，而且也適用于系統(tǒng)的任何一部分。,系統(tǒng)內(nèi)的平均顧客數(shù) = 平均到達(dá)率 平均逗留時(shí)間,單個(gè)服務(wù)臺(tái); 任意服務(wù)時(shí)間分布,一個(gè)穩(wěn)定系統(tǒng)的條件： 利用率小于 1： 計(jì)算公式：,s 數(shù)值增大就意味著服務(wù)時(shí)間有更多的可變性。而更多的可變性則會(huì)造成更多的擁塞和延誤，這樣就要等待更長(zhǎng)的時(shí)間。,實(shí)例,以下是兩個(gè)計(jì)算機(jī)系統(tǒng)的有關(guān)數(shù)據(jù)： 顧客的到達(dá)率為每小時(shí)15位。也就是說(shuō) l = 15/60 = 0.25 位顧客/分鐘 (注意:使用相同的時(shí)間單位！),實(shí)例（續(xù)）,1號(hào)計(jì)算機(jī)系統(tǒng)：,2號(hào)計(jì)算機(jī)系統(tǒng)：,慢的反而好！,實(shí)例（續(xù)）,單個(gè)服務(wù)臺(tái)；服務(wù)時(shí)間為指數(shù)分布,服務(wù)時(shí)間為指數(shù)分布，那么， M = s =1/m 利用率： 計(jì)算公式：,如果把到達(dá)數(shù)量增加一倍(2l)，再把服務(wù)率增加一倍 (2m), 等待時(shí)間就會(huì)減少一半 。這就是排隊(duì)論的規(guī)模經(jīng)濟(jì)學(xué)。,平均隊(duì)長(zhǎng)與利用率的關(guān)系,平均隊(duì)長(zhǎng)（和平均等待時(shí)間）與服務(wù)臺(tái)利用率之間的關(guān)系不是線性的關(guān)系。資產(chǎn)利用率太高會(huì)造成服務(wù)質(zhì)量急速下降，因而要權(quán)衡利弊。要保證服務(wù)質(zhì)量，就必須保持“過(guò)剩的”生產(chǎn)或服務(wù)能力。,平均隊(duì)長(zhǎng),利用率,實(shí)例,一個(gè)服務(wù)臺(tái)：指數(shù)服務(wù)時(shí)間 到達(dá)率 = 10/小時(shí),多個(gè)服務(wù)臺(tái);服務(wù)時(shí)間為指數(shù)分布,利用率： 計(jì)算公式較為復(fù)雜。我們可使用教材（Chase第8版）中的表 S5-4 或電子表格程序。,如果把到達(dá)數(shù)量增加一倍(2l)，再把服務(wù)人員增加一倍(2c), 等待時(shí)間就會(huì)減少一半以上。這就是排隊(duì)論的規(guī)模經(jīng)濟(jì)學(xué)。,為何“集中使用”可以提高服務(wù)質(zhì)量？,獨(dú)立的系統(tǒng),在此等待,在此等待,“集中使用”系統(tǒng),有關(guān)排隊(duì)模型的要點(diǎn),集中使用的優(yōu)點(diǎn) 將資源組合在一