1、Chapter 8 Production Scheduling and Controlling8.1 Production Scheduling 8.2 Sequencing8.3 Production Controlling1將MRP轉(zhuǎn)化為各個(gè)車間、班組、工作地的任務(wù)綜合生產(chǎn)計(jì)劃主生產(chǎn)計(jì)劃物料需求計(jì)劃生產(chǎn)作業(yè)計(jì)劃8.1 Production Scheduling 生產(chǎn)計(jì)劃28.1 Production Scheduling 一、生產(chǎn)作業(yè)計(jì)劃的概念 The idea of Job Shop Scheduling 生產(chǎn)作業(yè)計(jì)劃（車間作業(yè)計(jì)劃）是根據(jù)企業(yè)生產(chǎn)計(jì)劃，安排零部件（作業(yè)/活動(dòng)）的出產(chǎn)數(shù)量

2、、設(shè)備及人工使用、投入時(shí)間及出產(chǎn)時(shí)間等的具體執(zhí)行計(jì)劃。 生產(chǎn)作業(yè)計(jì)劃是將生產(chǎn)計(jì)劃從空間上、時(shí)間上以及制定的單位上進(jìn)行細(xì)化，規(guī)定車間、設(shè)備或工人在什么時(shí)間、什么地點(diǎn)完成什么任務(wù)，使生產(chǎn)計(jì)劃更加具體化并具有一定的可操作性和可執(zhí)行性。 從綜合生產(chǎn)計(jì)劃到主生產(chǎn)計(jì)劃，再從主生產(chǎn)計(jì)劃到物料需求計(jì)劃，最后到生產(chǎn)作業(yè)計(jì)劃才真正把訂單任務(wù)落到實(shí)處。3二、生產(chǎn)作業(yè)計(jì)劃的工作內(nèi)容 The content of Job Shop Scheduling1、制定合理的期量標(biāo)準(zhǔn) 期量標(biāo)準(zhǔn)，又稱作業(yè)計(jì)劃標(biāo)準(zhǔn)，是指為加工對(duì)象在生產(chǎn)期限和生產(chǎn)數(shù)量方面所規(guī)定的標(biāo)準(zhǔn)數(shù)據(jù)，它是編制生產(chǎn)作業(yè)計(jì)劃的重要依據(jù)。 期：時(shí)期，如投入期、出產(chǎn)期、

3、生產(chǎn)周期、生產(chǎn)間隔期等。 量：數(shù)量，如投入量、出產(chǎn)量、在制品數(shù)量、生產(chǎn)批量等。2、編制生產(chǎn)作業(yè)計(jì)劃8.1 Production Scheduling 4三、生產(chǎn)作業(yè)計(jì)劃的分類 The Classification of Job Shop Scheduling1、大量流水生產(chǎn)的生產(chǎn)作業(yè)計(jì)劃 Scheduling in High-Volume Systems2、成批生產(chǎn)的生產(chǎn)作業(yè)計(jì)劃 Scheduling in Intermediate-Volume Systems3、單件小批生產(chǎn)的生產(chǎn)作業(yè)計(jì)劃 Scheduling in Low-Volume Systems8.1 Production Sche

4、duling 58.1 Production Scheduling （一）大量流水生產(chǎn)的生產(chǎn)作業(yè)計(jì)劃1、期量標(biāo)準(zhǔn)（1）節(jié)拍 節(jié)拍是流水線上連續(xù)出產(chǎn)相鄰的兩件相同制品的時(shí)間間隔，節(jié)拍的大小取決于計(jì)劃期生產(chǎn)任務(wù)的數(shù)量和完成該任務(wù)的時(shí)間。單一對(duì)象流水線節(jié)拍的確定： Fe：計(jì)劃期內(nèi)的有效工作時(shí)間； N：計(jì)劃期生產(chǎn)任務(wù)的數(shù)量（含廢品量）。68.1 Production Scheduling （2）流水線標(biāo)準(zhǔn)工作指示圖表 標(biāo)準(zhǔn)工作指示圖表是表明流水線上各工作地在正常條件下的具體工作制度和勞動(dòng)組織方式的一種標(biāo)準(zhǔn)圖表。包括工作地需要量、工作地負(fù)荷、人員配備、工人工作負(fù)荷等。78.1 Production Sc

5、heduling （3）在制品定額 在制品定額是指在必要的時(shí)間、地點(diǎn)和一定的生產(chǎn)技術(shù)組織條件下，保證均衡生產(chǎn)所必需的最低限度的在制品數(shù)量。在制品定額車間或流水線內(nèi)部車間或流水線之間運(yùn)輸定額周轉(zhuǎn)定額保險(xiǎn)定額周轉(zhuǎn)定額運(yùn)輸定額保險(xiǎn)定額工藝定額88.1 Production Scheduling 2、生產(chǎn)作業(yè)計(jì)劃的編制在制品定額法 大量生產(chǎn)的企業(yè)，各車間的聯(lián)系表現(xiàn)為前車間提供在制品，以保證后車間的加工，從而使生產(chǎn)協(xié)調(diào)、均衡地進(jìn)行。因此，在大量生產(chǎn)條件下，生產(chǎn)作業(yè)計(jì)劃的核心是解決各車間在生產(chǎn)數(shù)量上的銜接平衡。 在制品定額法就是根據(jù)大量生產(chǎn)的特點(diǎn)，用在制品定額作為規(guī)定生產(chǎn)任務(wù)數(shù)量的標(biāo)準(zhǔn)，按照工藝過程反順序

6、的連續(xù)計(jì)算方法，依次確定車間的投入和出產(chǎn)任務(wù)。 在制品定額法就是以增減在制品數(shù)量的方式來調(diào)整由于不合格品、工人缺勤、設(shè)備故障等因素所導(dǎo)致的生產(chǎn)量波動(dòng)。98.1 Production Scheduling （1） 具體方法按反工藝順序，從產(chǎn)品最后一個(gè)車間開始，逐級(jí)向前推算。第一步：計(jì)算各車間投入量和出產(chǎn)量（表1）某車間的出產(chǎn)量 = 后一車間投入量 + 本車間外銷量+（期末庫存半成品定額期初庫存半成品結(jié)存量）某車間的投入量 = 本車間出產(chǎn)量 +本車間預(yù)計(jì)廢品量 +（期末在制品定額期初在制品預(yù)計(jì)結(jié)存量）10表1 各車間某月份投入量與出產(chǎn)量計(jì)算某 產(chǎn) 品 10000臺(tái)零 件A： 1 ：1B： 1 ：4

7、C： 1 ：6 10000 40000 60000裝配車間 1出產(chǎn)量 10000 40000 60000 2 廢 品- 3在制品定額10005000 4期初在制品預(yù)計(jì)結(jié)存量6003500 5投入量（1+2+3-4）1040041500零件庫 6半成品外銷量-2000 7半成品定額8006000 8期初預(yù)計(jì)結(jié)存量10007100 機(jī) 加 工 車 間 9出產(chǎn)量（5+6+7-8）1020042400 10廢 品1001400 11在制品定額18004500 12期初在制品預(yù)計(jì)結(jié)存量600340 13投入量（9+10+11-12）1150044900 毛 坯 庫 14半成品外銷量5006100 15半

8、成品定額200010000 16期初預(yù)計(jì)結(jié)存量300010000 毛 坯 車 間 17出產(chǎn)量（13+14+15-16）1100051000 18廢 品800- 19在制品定額4002500 20期初在制品預(yù)計(jì)結(jié)存量3001500 21投入量（17+18+19-20）1190052000零件產(chǎn)品118.1 Production Scheduling 第二步：編制各車間月度計(jì)劃（表2）第三步：把月計(jì)劃按日分配，得到車間日歷進(jìn)度計(jì)劃（表3） 表2 某月份加工車間投入與出產(chǎn)計(jì)劃任務(wù)序號(hào) 件號(hào)名稱每臺(tái)件數(shù)裝配投入需 要 量庫存定額差額外銷量出產(chǎn)量投入量101-051軸 1 10400 -200 - 10

9、200 11500202-034齒輪 4 41500 -1100 2000 42400 449003-12零件件號(hào)名稱計(jì)劃出產(chǎn)量件計(jì)劃投入量件項(xiàng)目日 歷 進(jìn) 度 1234 31 01- 051軸1020011500計(jì)劃投入460460460460460計(jì)劃產(chǎn)出408408408408408實(shí)際出產(chǎn)累計(jì)出產(chǎn)02-034 齒輪4240044900計(jì)劃投入17961796179617961796計(jì)劃產(chǎn)出16961696169616961696實(shí)際出產(chǎn)累計(jì)出產(chǎn)其它計(jì)劃投入計(jì)劃產(chǎn)出實(shí)際出產(chǎn)累計(jì)出產(chǎn)注：（1）按全月25個(gè)工作日安排。 （2）本例按日平均投入和出產(chǎn)。 表3：某月份加工車間日歷進(jìn)度計(jì)劃138.

10、1 Production Scheduling （2） 注意事項(xiàng) 反工藝順序 最后車間出產(chǎn)量就是成品出產(chǎn)量，它與車間的半成品外銷量都是根據(jù)生產(chǎn)計(jì)劃任務(wù)確定的。 車間預(yù)計(jì)廢品量是按計(jì)劃規(guī)定的廢品率計(jì)算的。 148.1 Production Scheduling （二）成批生產(chǎn)的生產(chǎn)作業(yè)計(jì)劃1、期量標(biāo)準(zhǔn)（1）批量與生產(chǎn)間隔期批量：一次投入（或出產(chǎn)）生產(chǎn)相同產(chǎn)品或零件的數(shù)量。生產(chǎn)間隔期：相鄰兩批相同產(chǎn)品/零件投入或出產(chǎn)的時(shí)間間隔。 二者關(guān)系：批量生產(chǎn)間隔期平均日產(chǎn)量 計(jì)算方法： 以期定量法 以量定期法158.1 Production Scheduling 以量定期法（1）從生產(chǎn)的技術(shù)與經(jīng)濟(jì)兩方面考慮

11、，確定一個(gè)初始批量Q；（2）根據(jù) “批量Q= 生產(chǎn)間隔期R 平均每日產(chǎn)量nd 確定生產(chǎn)間隔期；（3）對(duì)初始批量進(jìn)行調(diào)整，求得一個(gè)與R相符的最佳值作為標(biāo)準(zhǔn)批量；（4）當(dāng)生產(chǎn)任務(wù)變化時(shí)，只對(duì)生產(chǎn)間隔期R進(jìn)行調(diào)整，而批量Q保持不變。 常用的確定初始批量Q的方法：最小批量法、經(jīng)濟(jì)批量法。168.1 Production Scheduling 以期定量法（1）首先確定生產(chǎn)間隔期；（2）根據(jù)批量Q = 生產(chǎn)間隔期R 平均每日產(chǎn)量nd確定批量；（3）當(dāng)生產(chǎn)任務(wù)發(fā)生變化時(shí)，只對(duì)批量進(jìn)行調(diào)整，而生產(chǎn)間隔期不變。178.1 Production Scheduling （2）生產(chǎn)周期從原材料投入開始到成品出產(chǎn)為止的

12、全部日歷時(shí)間(或工作日數(shù))鑄鍛毛坯生產(chǎn)周期保險(xiǎn)期毛 坯 周 期機(jī)械加工生產(chǎn)周期部件裝配生產(chǎn)周期總裝、油漆、包裝生產(chǎn)周期保險(xiǎn)期保險(xiǎn)期保險(xiǎn)期加 工 周 期部 裝 周 期總 裝 周 期產(chǎn) 品 生 產(chǎn) 周 期產(chǎn)品生產(chǎn)周期示意圖188.1 Production Scheduling （3）生產(chǎn)提前期 定義： 生產(chǎn)提前期指產(chǎn)品（零件）在各生產(chǎn)環(huán)節(jié)（工藝階段）出產(chǎn)或投入的時(shí)間與成品出產(chǎn)時(shí)間相比所要提前的時(shí)間。產(chǎn)品在每一個(gè)生產(chǎn)環(huán)節(jié)上都有投入和出產(chǎn)之分，因而生產(chǎn)提前期分為投入提前期和出產(chǎn)提前期兩種。198.1 Production Scheduling 制定方法 提前期的計(jì)算是按工藝過程相反的順序進(jìn)行的。以機(jī)械

13、企業(yè)為例，由于裝配車間出產(chǎn)的時(shí)間也就是成品出產(chǎn)的時(shí)間，所以：（1）裝配車間的出產(chǎn)提前期為零；（2）依據(jù)裝配車間的生產(chǎn)周期計(jì)算裝配車間的投入提前期；（3）根據(jù)裝配車間的投入提前期加入一定的保險(xiǎn)期計(jì)算加工車間的出產(chǎn)提前期；（4）依次反工藝類推，一直算到毛坯車間的投入提前期。208.1 Production Scheduling 裝配投入提前期機(jī)加工出產(chǎn)提前期機(jī)加工投入提前期毛坯出產(chǎn)提前期毛坯投入提前期毛坯生產(chǎn)周期機(jī)加工生產(chǎn)周期裝配生產(chǎn)周期保險(xiǎn)期保險(xiǎn)期出產(chǎn)期 限圖1 提前期與生產(chǎn)周期、保險(xiǎn)期的關(guān)系218.1 Production Scheduling 前后車間批量不相等的情況 a.某車間的出產(chǎn)提前期

14、=后車間的投入提前期 +本車間的保險(xiǎn)期 +(本車間生產(chǎn)間隔期-后車間的生產(chǎn)間隔期)； b.某車間的投入提前期 =本車間的出產(chǎn)提前期 +本車間的生產(chǎn)周期 前后車間生產(chǎn)批量相等的情況a.某車間的出產(chǎn)提前期 = 后車間的投入提前期 +本車間的保險(xiǎn)期b.某車間的投入提前期 = 本車間的出產(chǎn)提前期 +本車間的生產(chǎn)周期228.1 Production Scheduling （4）在制品定額 同大量生產(chǎn)一樣，成批生產(chǎn)的在制品定額分為車間之間的在制品和車間內(nèi)部的在制品。與大量生產(chǎn)不同的是，成批生產(chǎn)的車間內(nèi)部在制品經(jīng)常處于波動(dòng)中。238.1 Production Scheduling 2、生產(chǎn)作業(yè)計(jì)劃的編制累計(jì)

15、編號(hào)法 多品種成批生產(chǎn)條件下，產(chǎn)品輪番投入和產(chǎn)出，不可能有穩(wěn)定的在制品數(shù)量，在制品變動(dòng)不易掌握。前后車間之間的聯(lián)系主要表現(xiàn)在生產(chǎn)提前期上，因此，可以從產(chǎn)品完工期推算出各工藝階段需要投入和出產(chǎn)的日期，然后通過以期定量法，從期的銜接達(dá)到量的銜接。 累計(jì)編號(hào)法是一種基于提前期的方法，首先通過產(chǎn)品的交貨日期可以逆序計(jì)算出各工藝階段的提前期，再通過提前期與量之間的關(guān)系，將提前期轉(zhuǎn)化為投入量與產(chǎn)出量。248.1 Production Scheduling （1）相關(guān)概念累計(jì)編號(hào)：指從年初或從開始生產(chǎn)這種產(chǎn)品起，以成品出產(chǎn)的先后順序，為每一件產(chǎn)品編上一個(gè)累計(jì)號(hào)碼。提前量：在同一時(shí)間上，產(chǎn)品在某一生產(chǎn)環(huán)節(jié)上的

16、累計(jì)編號(hào)，同成品的出產(chǎn)累計(jì)編號(hào)的差稱為提前量。提前量的大小與提前期成正比，即： 提前量 = 提前期平均日產(chǎn)量提前期法：根據(jù)預(yù)先制定的提前期，通過平均日產(chǎn)量轉(zhuǎn)化為提前量，從而得出同一時(shí)期產(chǎn)品在各生產(chǎn)環(huán)節(jié)上的提前量，來保證各車間之間數(shù)量上的銜接的計(jì)劃制定方法。258.1 Production Scheduling （2）計(jì)算步驟 確定各生產(chǎn)工藝環(huán)節(jié)的提前期及批量定額； 計(jì)算產(chǎn)品在各車間計(jì)劃期末應(yīng)達(dá)到的累計(jì)出產(chǎn)和投入的號(hào)數(shù)；某車間出產(chǎn)累計(jì)號(hào)數(shù) = 最后車間出產(chǎn)累計(jì)號(hào)數(shù) + 本車間出產(chǎn)提前期定額 最后車間平均日產(chǎn)量某車間投入累計(jì)號(hào)數(shù) = 最后車間出產(chǎn)累計(jì)號(hào)數(shù) + 本車間投入提前期定額 最后車間平均日產(chǎn)

17、量268.1 Production Scheduling 計(jì)算各車間在計(jì)劃期內(nèi)應(yīng)完成的出產(chǎn)量和投入量；某車間計(jì)劃期出產(chǎn)量= 該車間計(jì)劃期末出產(chǎn)累計(jì)號(hào)數(shù) 該車間計(jì)劃期初已出產(chǎn)累計(jì)號(hào)數(shù)某車間計(jì)劃期投入量= 該車間計(jì)劃期末投入累計(jì)號(hào)數(shù) 該車間計(jì)劃期初已投入累計(jì)號(hào)數(shù) 按照零件批量進(jìn)行修正，使其和批量相等或成整數(shù)倍數(shù)。27期量標(biāo)準(zhǔn)裝配車間機(jī)加工車間毛坯車間批量(臺(tái))50100200生產(chǎn)周期(天)5510生產(chǎn)間隔期(天)51020出產(chǎn)提前期(天)投入提前期(天)三月末出產(chǎn)累計(jì)號(hào)數(shù)三月末投入累計(jì)號(hào)數(shù)例 某產(chǎn)品為成批生產(chǎn)，月工作日數(shù)25天，平均日產(chǎn)10臺(tái)。已知期量標(biāo)準(zhǔn)的數(shù)據(jù)如下表所示，保險(xiǎn)期均為0。若該產(chǎn)品三

18、月初開始投產(chǎn)，試確定三月末各車間出產(chǎn)（投入）累計(jì)號(hào)數(shù)。8.1 Production Scheduling 28期量標(biāo)準(zhǔn)裝配車間機(jī)加工車間毛坯車間批量(臺(tái))50100200生產(chǎn)周期(天)5510生產(chǎn)間隔期(天)51020出產(chǎn)提前期(天)投入提前期(天)三月末出產(chǎn)累計(jì)號(hào)數(shù)三月末投入累計(jì)號(hào)數(shù) 00+5=55+0+105=1010+5=1515+2010=2525+10=350+250250250+510300250+1010=350250+1510=400250+2510=500250+3510=600解：8.1 Production Scheduling 298.1 Production Sche

19、duling 采用提前期法安排車間生產(chǎn)任務(wù)有以下特點(diǎn)：1、它可以同時(shí)計(jì)算各車間任務(wù)，而不必按工藝順序方向依次計(jì)算，因此加快了計(jì)劃編制速度。2、由于同一臺(tái)產(chǎn)品所有零件都屬于同一個(gè)累計(jì)編號(hào)，所以，只要每個(gè)生產(chǎn)環(huán)節(jié)都能出產(chǎn)到計(jì)劃規(guī)定的累計(jì)號(hào)數(shù)，就能有效地保證零件的成套性。308.1 Production Scheduling （三）單件小批生產(chǎn)的生產(chǎn)作業(yè)計(jì)劃 單件小批生產(chǎn)的產(chǎn)品品種、數(shù)量和交貨時(shí)間都不穩(wěn)定，產(chǎn)量少，重復(fù)性生產(chǎn)少，屬于一次性生產(chǎn)，既不能采用在制品定額法，也不能采用累計(jì)編號(hào)法。 單件小批生產(chǎn)的生產(chǎn)作業(yè)計(jì)劃編制的特點(diǎn)：各種產(chǎn)品的數(shù)量和任務(wù)完全取決于訂貨的數(shù)量，無需再進(jìn)行計(jì)算。318.1 P

20、roduction Scheduling （三）單件小批生產(chǎn)的生產(chǎn)作業(yè)計(jì)劃1、期量標(biāo)準(zhǔn)（1）生產(chǎn)周期（2）總?cè)諝v進(jìn)度計(jì)劃2、生產(chǎn)作業(yè)計(jì)劃編制的方法（1）生產(chǎn)周期進(jìn)度表法（2）生產(chǎn)進(jìn)度百分比法（3）網(wǎng)絡(luò)計(jì)劃技術(shù)328.2 Sequencing 在編制生產(chǎn)（車間）作業(yè)計(jì)劃的過程中，由于生產(chǎn)多種產(chǎn)品，對(duì)生產(chǎn)設(shè)備的需求會(huì)發(fā)生沖突。因此，需要解決各個(gè)生產(chǎn)層次中生產(chǎn)任務(wù)的加工順序問題。 排序：確定工件在設(shè)備上的加工順序。 作業(yè)計(jì)劃：不僅包括確定工件的加工順序，還包括確定設(shè)備加工每個(gè)工件的開始時(shí)間與結(jié)束時(shí)間。 編制作業(yè)計(jì)劃的主要工作之一就是要確定出最佳的作業(yè)順序。33一、排序問題的分類和表示方法（一）分類

21、1、根據(jù)機(jī)器數(shù)的多少 單臺(tái)機(jī)器的排序問題、多臺(tái)機(jī)器的排序問題 2、根據(jù)工件到達(dá)車間的情況 靜態(tài)排序、動(dòng)態(tài)排序 3、根據(jù)要實(shí)現(xiàn)的目標(biāo) 單目標(biāo)排序、多目標(biāo)排序 4、根據(jù)參數(shù)的性質(zhì) 確定型排序、隨機(jī)型排序8.2 Sequencing34（二）表示方法 n / m / A / B其中，n - 工件數(shù)； m - 機(jī)器數(shù)； A - 車間類型 ( F=流水型排序；G=一般單件型排序) B - 目標(biāo)函數(shù)（評(píng)價(jià)標(biāo)準(zhǔn)） 如：6/2/F/Fmin 六個(gè)工件在兩臺(tái)機(jī)器上的流水作業(yè)排序的問題，目標(biāo)是總流程時(shí)間最短。8.2 Sequencing35單件作業(yè)排序問題n/m/G/Fmax中工序的描述加工描述矩陣D8.2 Se

22、quencing（i，j，k）：工件i的第j道工序是在機(jī)器k上進(jìn)行的。368.2 Sequencing二、排序問題的評(píng)價(jià)標(biāo)準(zhǔn) 總流程時(shí)間Fmin最短 平均流程時(shí)間Fa最短 最大延遲Lmax或最大誤期Tmax最短 平均在制品數(shù)量最少 總調(diào)整時(shí)間最小378.2 Sequencing三、排序問題的優(yōu)先調(diào)度規(guī)則FCFS（first come, first served）：優(yōu)先選擇排隊(duì)等待的工序中最早進(jìn)入的工序。SPT( shortest processing time）：優(yōu)先選擇加工時(shí)間最短的工序。EDD（earliest due date）：優(yōu)先選擇完工期限最早的工序。MWKR(most work

23、remaining)：優(yōu)先選擇余下加工時(shí)間最長的工件。LWKR(least work remaining)：優(yōu)先選擇余下加工時(shí)間最短的工件。MOPNR(most Production remaining)：優(yōu)先選擇余下工序數(shù)最多的工件。RANDOM ：隨機(jī)挑選一個(gè)工件。388.2 Sequencing四、排序問題的基本假設(shè) 一個(gè)工件不能同時(shí)在不同的設(shè)備上加工。 每道工序只在一臺(tái)設(shè)備上完成，每臺(tái)設(shè)備只完成一道工序。 每臺(tái)設(shè)備同時(shí)只能加工一個(gè)工件。 工件在加工過程中采取平行移動(dòng)方式，即上一道工序完成后立即送至下一道工序加工。 工件數(shù)n，設(shè)備數(shù)m，與加工時(shí)間均已知時(shí)，允許工件在工序之間等待，允許設(shè)備

24、在工件未到達(dá)時(shí)閑置。 不允許中斷：某工件一旦開始加工，必須一直進(jìn)行到完工，不允許中途停止而插入其他工件。39五、 排序問題常用的符號(hào) Ji-工件i，i=1,2,.n di-工件i的交貨期 Pi-工件i的加工時(shí)間, , pij-工件i在機(jī)器j上的加工時(shí)間,j=1,mWi-工件i在系統(tǒng)內(nèi)的等待時(shí)間, , wij-工件i在機(jī)器j前的等待時(shí)間, j=1,m Ci-工件i的完成時(shí)間, 在工件都已到達(dá)的情況下, Ci= Pi+ Wi Fi-工件i的流程時(shí)間，在工件都已到達(dá)的情況下, Fi= Pi+ Wi Li-工件i的延誤時(shí)間, Li= Ci- di , Li0 延誤 Ti-工件i的延期量, Ti=max

25、0, Li Ei-工件i提前完成的時(shí)間8.2 Sequencing408.2 Sequencing六、排序問題的分析（一）單臺(tái)設(shè)備的排序問題（二）多臺(tái)設(shè)備的排序問題418.2 Sequencing（一）單臺(tái)設(shè)備的排序問題 例：在一臺(tái)設(shè)備上安排6項(xiàng)加工任務(wù)，其作業(yè)時(shí)間和交貨期已知任務(wù)編號(hào)i123456作業(yè)時(shí)間P(i)1021846交貨期D(i)154614108設(shè)： i為任務(wù)編號(hào)，i=1,2,3,4.n, P(i) 為第i項(xiàng)任務(wù)的作業(yè)時(shí)間; W(i)為第i項(xiàng)任務(wù)的等待時(shí)間 F(i)為第i項(xiàng)任務(wù)的完成時(shí)間; D(i)為第i項(xiàng)任務(wù)的交貨期 L(i) 為第 i項(xiàng)任務(wù)的拖期時(shí)間； K(i) 為實(shí)際排序序

26、號(hào) 428.2 Sequencing解法一：依據(jù)“先到先安排(FCFS)”原則進(jìn)行排序i123456P(i)1021846W(i)0101213212581F(i)101213212531112D(i)154614108L(i)0877152360當(dāng) F(i) D(i)0, 則為拖期；當(dāng) F(i) D(i)0, 則為按期438.2 Sequencing解法二：依據(jù)“SPT原則”進(jìn)行排序i123456P(i)1021846K(i)325641W(i)0137132145F(i(i)641081415L(i)000571628 定理1 ：對(duì)于單臺(tái)設(shè)備排序問題， SPT規(guī)則

27、使平均流程時(shí)間最短。（即從加工時(shí)間最短的工件開始順序排序）448.2 Sequencing解法三：依據(jù)“EDD原則”進(jìn)行排序i123456D(i)154614108D(i)K(i)236541P(i)2164810W(i) 0239132148F(i)23913213179L(i)001371627 定理2: 對(duì)于單臺(tái)設(shè)備排序問題， EDD規(guī)則使最大延遲Lmax或最大誤期Tmax最小。（即從交貨期最短的工件開始順序排序）458.2 Sequencing解法四：按期完成作業(yè)項(xiàng)目最多的原則排序（又稱摩爾More法則） 這種方法使拖期項(xiàng)目達(dá)到最少，如期完成作業(yè)項(xiàng)目最多。它是在EDD原則的基礎(chǔ)上排序，

28、依次計(jì)算每項(xiàng)作業(yè)是否拖期。如果拖期，則將該作業(yè)移到最后加工，然后再檢查任務(wù)是否拖期，直到第一次向后移的任務(wù)仍然拖期為止。 實(shí)際上是在采用EDD原則的基礎(chǔ)上，再采用SPT規(guī)則，即采用組合規(guī)則。468.2 Sequencing按期完成作業(yè)項(xiàng)目最多的原則排序（又稱摩爾More法則）K(i)123456i23(6)5(4)(1)641D(i)46(8)10(14)(15)81415P(i)21(6)4(8)(10)6810W(i) 02(3)3(7)(7)7132146F(i)23(9)7(15)(17)13213177L(i)00(1)0(1)(2)57162847四種優(yōu)先原則的排序比較表優(yōu)先原則等

29、待時(shí)間W(i)完成時(shí)間F(i)拖期L(i)總天數(shù)項(xiàng)目數(shù)1. FCFS811126052. SPT45762833. EDD48792744. More4677283（1）按SPT法，可使零件的等待時(shí)間，總加工時(shí)間最短（2）按 EDD法，可使任務(wù)拖期時(shí)間減少（3）More法則可使拖期的作業(yè)項(xiàng)目數(shù)達(dá)到最少8.2 Sequencing488.2 Sequencingn/2/F/Fmax 排序問題n/3/F/Fmax 排序問題n/m/F/Fmax 排序問題（二）多臺(tái)設(shè)備的排序問題498.2 Sequencing1、 n/2/F/Fmax排序問題 n個(gè)工件都必須經(jīng)過機(jī)器1和機(jī)器2的加工，即工藝路線是一致

30、的。 n項(xiàng)任務(wù)在兩臺(tái)機(jī)床上加工的排序目標(biāo)是使最大完成時(shí)間（總加工周期）Fmax最短，即n/2/F/ Fmax問題。 該問題使用約翰遜-貝爾曼規(guī)則，可求出最優(yōu)解（總工時(shí)最小的排序）。508.2 Sequencing約翰遜法的計(jì)算步驟：（1）列出所有工件在兩臺(tái)設(shè)備上的作業(yè)時(shí)間。（2）找出作業(yè)時(shí)間最小者。（3）如果該最小值是在設(shè)備1上，將對(duì)應(yīng)的工件盡可能往前排，如果該最小值是在設(shè)備2上，則將對(duì)應(yīng)的工件盡可能往后排。（4）從加工時(shí)間矩陣中劃去已排序工件的加工時(shí)間。若最短加工時(shí)間有多個(gè)，則任挑一個(gè)；（5）排除已安排好的工件，在剩余的工件中重復(fù)步驟(2)和(3)，直到所有工件都安排完畢。 518.2 Se

31、quencing例：A，B兩臺(tái)機(jī)床，加工6種零件，單件工時(shí)如下，求最優(yōu)排序。J1J2J3J4J5J6A214713166B472051014工件機(jī)床單件工時(shí)（min）528.2 SequencingJ1J2J3J4J5J6A214713166B472051014J2J6J3J5J4J1A加工開始0410173346結(jié)束41017334667B加工開始41125455567結(jié)束112545556071排 序532、 n/3/F/Fmax 流水型排序問題 n項(xiàng)任務(wù)依次在1，2，3三臺(tái)機(jī)床上加工，設(shè) ti1, ti2 ,ti3為第 i 種任務(wù)（零件）在機(jī)床1，1，3上的單件工時(shí)。排序方法有兩種：（1

32、） 將三臺(tái)機(jī)床的排序轉(zhuǎn)化為兩臺(tái)機(jī)床排序問題仿約翰孫算法。（2） 按n/m/F/Fmax問題求解。 8.2 Sequencing54（1） 當(dāng)符合下列兩個(gè)條件之一時(shí)，可將三臺(tái)機(jī)床的排序轉(zhuǎn)化為兩臺(tái)機(jī)床排序問題，使用仿約翰孫算法求解。 min ti1 max ti2 min ti3 max ti2 設(shè)有機(jī)床G與H，設(shè) tiG, tiH分別為G與H的單件加工時(shí)間，則 tiG = ti1 + ti2 tiH = ti2 + ti3 上述問題變換為G，H兩臺(tái)機(jī)床的排序問題。8.2 Sequencing（2）若不符合上述條件下，按n/m/F/Fmax問題求解。 55例：A，B，C三臺(tái)機(jī)床，加工6種零件，單件

33、工時(shí)如下，求最優(yōu)排序。J1J2J3J4J5J6A866876B456231C6876910J1J2J3J4J5J6G12111210107H10131381211J4J6J5J2J3J18.2 Sequencing56按上列排序順序，安排三臺(tái)機(jī)床加工零件的順序：J6J5J2J3J1J4A加工開始0613192533結(jié)束61319253341B加工開始61319253341結(jié)束71624313743C加工開始71726344147結(jié)束1726344147538.2 Sequencing573、 n/m/F/Fmax流水型排序問題n/m/F/Fmax流水型排序問題常用關(guān)鍵零件法，步驟如下： （1）在n種零件中，求出總工時(shí)最大的零件，作為關(guān)鍵零件Jc。 （2）除去關(guān)鍵零件Jc，將滿足ti1tim的零件，按tim值的大小，從大到小排列在J