生產(chǎn)與運作管理課件：第十四章 作業(yè)排序

1、第十四章 作業(yè)排序 第一節(jié) 排序問題的基本概念第二節(jié) 單臺設(shè)備加工排序問題第三節(jié) 流水型作業(yè)排序問題第四節(jié) 單件作業(yè)排序問題第一節(jié) 排序問題的基本概念1 排序：確定零件在設(shè)備上的加工順序2 編制作業(yè)計劃：不僅包括確定零件的加工順序，而且還包括確定設(shè)備加工每一個零件的開始時間和完工時間。3 排序問題的分類1)按零件加工路線的特征不同： 流水作業(yè)排序問題：零件的加工路線相同 單件作業(yè)排序問題：零件的加工路線不同 2)按設(shè)備種類和數(shù)量不同：單臺設(shè)備排序問題、 多臺設(shè)備排序問題3)按零件到達(dá)車間的情況：靜態(tài)作業(yè)排序問題、動態(tài)作業(yè)排序問題 靜態(tài)作業(yè)排序問題：零件一次性到達(dá)車間，一次性排序 動態(tài)作業(yè)排序問

2、題：零件陸續(xù)到達(dá)車間，隨時排序4)按參數(shù)性質(zhì)不同：確定型排序問題、隨機性排序問題 參數(shù)：指加工時間和其他有關(guān)參數(shù)5)按目標(biāo)函數(shù)的性質(zhì)不同：單目標(biāo)排序問題、多目標(biāo)排序問題 目標(biāo)函數(shù)：加工周期最短、平均流程時間最短、誤期完工時間最少等 4 幾個概念 時間 J1 J2 J3 J4 C1 C2 C3 C4t1 t2 t3 t4F1F2F3F4作業(yè)時間ti流程時間：任務(wù)在 車間的停留時間Fi總流程時間：Fi最大流程時間： Fmax=maxFi平均流程時間： Fi/n等待時間：總等待時間：平均等待時間：加工周期： 交貨期： Ci延期量：交貨期拖延 的時間（D）最大延期量: Dmax=maxDi總延期量：

3、Di5 排序問題的表示法 n/m/A/B 其中：n零件數(shù) m設(shè)備數(shù) A車間類型 流水作業(yè)排序F 單件作業(yè)排序G 當(dāng)m=1時，A處為空白，因為對于單臺設(shè)備的排序問題，無所謂加工路線問題，也談不上流水型或單件作業(yè) B目標(biāo)函數(shù) ,通常是使其值最小 例：5個工件經(jīng)過4臺設(shè)備加工，目標(biāo)是使加工周期最短的流水型作業(yè)排序可以表示為：5/4/F/ Fmax1 單臺設(shè)備排序問題的特點 無論n個零件加工任務(wù)作何種排序，n項任務(wù)中的最大流程時間(加工周期)總是一個固定值第二節(jié) 單臺設(shè)備加工排序問題零件號 作業(yè)時間 4 82 5 9 加工周期=4+8+2+5+9=28目標(biāo)函數(shù)？1)目標(biāo): 使平均流程時間最短或平均等待

4、時間最短2)方法：按任務(wù)所需時間長短，從短到長順序排列。例： 零件號 作業(yè)時間1.750.250.701.302.251.00.75排序：一一一一一一 2 SPT法例題:已知條件如表所示,求平均流程時間,平均等待時間，最大交貨延期 零件號 作業(yè)時間 4 82 5 9 3 預(yù)定交貨期24 23 8 6 32 13解：列表如下 加工順序 1 2 3 4 5 6 零件號 作業(yè)時間 2 3 4 5 8 9 流程時間 2 5 9 14 22 31 等待時間 0 2 5 9 14 22 預(yù)定交貨期 8 13 24 6 23 32 交貨延期 0 0 0 8 0 0答：最大流程時間：31 最大等待時間：22

5、平均流程時間=(2+5+9+14+22+31)613.83 平均等待時間=(0+2+5+9+1+14+22)/6=8.67 最大交貨延期：8 總交貨延期：( 0+0+0+8+0+0)=8缺點：可能發(fā)生交貨延期； 優(yōu)點：平均流程時間短 加工順序 1 2 3 4 5 6 零件號 作業(yè)時間 2 3 4 5 8 9 流程時間 2 5 9 14 22 31 等待時間 0 2 5 9 14 22 預(yù)定交貨期 8 13 24 6 23 32 交貨延期 0 0 0 8 0 01)目標(biāo)：最大交貨延期時間最小。2)方法：按預(yù)定交貨期(生產(chǎn)任務(wù)規(guī)定完成時刻)的先后，從先到后按次序排列，即按預(yù)定交貨期非減的次序排序3

6、 EDD法零件號 作業(yè)時間 4 82 5 9 3 預(yù)定交貨期24 23 8 6 32 13排序： 一一 一 一 一 例題1:已知條件如表所示,用EDD法排序，并求平均流程時間,平均等待時間，最大交貨延期 答：最大流程時間：31 最大等待時間：22 平均流程時間=(5+7+10+18+22+31)615.5 平均等待時間=(0+5+7+10+18+22)/6=10.33 最大交貨延期：0 總交貨延期：( 0+0+0+0+0+0)=0缺點：平均流程時間較長 優(yōu)點：最大交貨延期最小 加工順序 1 2 3 4 5 6 零件號 作業(yè)時間 5 2 3 8 4 9 流程時間 5 7 10 18 22 31

7、等待時間 0 5 7 10 18 22 預(yù)定交貨期 6 8 13 23 24 32 交貨延期 0 0 0 0 0 0例題2：已知如表，用EDD法求最大流程時間和總延期時間零件號 作業(yè)時間 10 63 148 7 6 預(yù)定交貨期3520118625289加工順序12345678零件編號作業(yè)時間416368710流程時間45111420283545預(yù)定交貨期6891120252835交貨延期002303710解： 答：最大流程時間45 最大延期時間10 總延期時間：2+3+3+7+10=25 第三節(jié) 流水型作業(yè)排序問題1 流水型作業(yè)排序問題的特點： 零件的加工路線相同設(shè)備零件 A車床158612

8、B銑床3156 C磨床41057兩臺設(shè)備的流水型排序問題三臺設(shè)備的流水型排序問題m臺設(shè)備的流水型排序問題2.兩臺設(shè)備流水型排序問題及解法2)目標(biāo)：使完成任務(wù)的最大流程時間最短3)方法：約翰遜法 設(shè)ti1和ti2分別是零件i在第一臺設(shè)備和第二臺設(shè)備上的加工時間。首先：以零件編號為行，以設(shè)備編號為列，建立加工時間矩陣。其次：從加工時間矩陣中找出最短的加工時間。第三：若最短的加工時間出現(xiàn)在第一臺設(shè)備上，則對應(yīng)的零件盡可能往前排，若最短的時間出現(xiàn)在第二臺設(shè)備上，則對應(yīng)的零件盡可能往后排若最短的加工時間有多個，任選一個。最后：若所有工件都已排序，停止，否則，轉(zhuǎn)步驟“第三” 。1）問題：n個零件在兩臺設(shè)備

9、上加工，它們的工藝順序相同4)例： 已知如表，求加工周期 解：首先進(jìn)行排序 方案一：一一一一 方案二；一一一一 有兩個方案 設(shè)備 零件(1)車床 ti1681237(2)銑床 ti2119534其次計算加工周期 :設(shè)備零件(1)車床681237(2)銑床119534Fi1 計算的根據(jù)：一個零件在設(shè)備(1)上加工必須等到它前面的零 件在設(shè)備(1)上加工完成之后才能進(jìn)行。加工順序(1)(2)ti1ti2Fi1Fi2336812745911336 29179640342920故:從表中可以看出，最大流程時間( 零件的總加工周期）為40Fi2 計算的根據(jù)：一個零件在設(shè)備(2)上加工必須等到該零件在設(shè)

10、備(1)上加工完并且設(shè)備(2)加工完前一個零件之后才能開始 4)使用條件：minti1maxti2:即各零件在第一臺設(shè)備上的最短加工時間大于或等于各零件在第二臺設(shè)備上的最長加工時間。 或： minti3maxti2：即各零件在第三臺設(shè)備上的最短加工時間大于或等于各零件在第二臺設(shè)備上的最長加工時間設(shè)備零件 A車床158612 B銑床3156 C磨床410573 三臺設(shè)備流水型排序問題及解法1）問題：n種零件在三臺 設(shè)備上加工，其工藝順 序均相同。2) 目標(biāo)：加工周期最短， 即最大流程時間最小。3) 方法：約翰遜擴(kuò)展法第一步：檢查各零件在設(shè)備(1)、(2)、(3)的加工時間是否滿 足使用條件的其中

11、一個，若滿足，進(jìn)行第二步；第二步：將第一臺設(shè)備和第二臺設(shè)備加工時間按零件依次相 加，令tG= ti1+ ti2第三步：將第三臺設(shè)備和第二臺設(shè)備加工時間按零件依次相 加，令tH= ti3+ ti2第四步：將得到的tG和tH看作兩臺假想設(shè)備G和H的加工時間第五步；按兩臺設(shè)備的流水型排序問題及解法得出最優(yōu)排序 此排序就是三臺設(shè)備的流水型排序的最優(yōu)解。設(shè)備零件 A車床158612 B銑床3156C磨床410575）步驟 按約翰遜法： 可得最優(yōu)解為：一一 一 設(shè)備零件 A車床158612 B銑床3156C磨床41057設(shè)備零件G1891118H71110136)例題：已知如表，求加工周期。解：判定是否滿

12、足使用條件： minti1=6 maxti2=6滿足： minti1 maxti2可得右下表：計算加工周期：設(shè)備零件 A車床158612 B銑床3156C磨床41057最優(yōu)排序為：一一 一 加工順序 (1)(2)（3）8 4126209443126ti1ti2Fi1Fi2ti3Fi3 8 1 12615 35 61075419333848課堂練習(xí)： 1. 用SPT法和EDD法對下列問題排序，并求最大流程時間、平均流程時間、最大交貨延期和總交貨延期。零件號 作業(yè)時間 8 1256410 預(yù)定交貨期3513421925102. 對下列問題排序，使完成任務(wù)的最大流程時間最短，并求最短加工周期。(1)

13、(2)設(shè)備 零件(1)車床 ti1108642(2)銑床 ti213579設(shè)備 零件(1)車床 ti1734897(2)銑床 ti28551012 1.用SPT法和EDD法對下列問題排序。零件號 作業(yè)時間 8 1256410 預(yù)定交貨期351342192510加工順序123456零件編號作業(yè)時間45681012流程時間4915233345預(yù)定交貨期254219351013交貨延期00002332答：最大流程時間：45 平均流程時間=(4+9+15+23+33+45)621.5 最大交貨延期：32 總延期時間：23+32=55 解： SPT法：零件號 作業(yè)時間 8 1256410 預(yù)定交貨期35

14、1342192510加工順序123456零件編號作業(yè)時間10126485流程時間102228324045預(yù)定交貨期101319253542交貨延期099753答：最大流程時間：45 平均流程時間=(10+22+28+32+40+45)629.5 最大交貨延期：9 總延期時間：9+9+7+5+3=33 解： EDD法 1.用SPT法和EDD法對下列問題排序。加工順序(1)(2)ti1ti2Fi1Fi229468101357230 201261131262318設(shè)備 零件(1)車床 ti1108642(2)銑床 ti213579解：排序方案：一一 一一Fmax=312.對下列問題排序，使完成任務(wù)的

15、最大流程時 間最短，并求最短加工周期。(1)解：排序 一一一一一設(shè)備 零件(1)車床 ti1734897(2)銑床 ti28551012加工順序(1)(2)ti1ti2Fi1Fi235478 7 21085 1 9329 22147834322213 39382.對下列問題排序，使完成任務(wù)的最大流程時間最短，并求最短加工周期。(2)加工順序(1)(2)ti1ti2Fi1Fi2611831274589636 2917141743393426設(shè)備 零件(1)車床 ti1681237(2)銑床 ti2119584排序方案1（按照ti2 從大到?。?一一 一一對下列問題排序，使完成任務(wù)的最大流程時間

16、最短.排序方案2（按照約翰遜法）： 一 一 一一加工順序(1)(2)ti1ti2Fi1Fi2386812745911336 2917911403631224 m臺設(shè)備的流水型排序問題及解法問題：n種零件在m臺設(shè)備上加工，其工藝順序相同式中： i表示i零件的斜度指標(biāo) m為設(shè)備數(shù) tik為i零件在k設(shè)備上的加工時間k=1,2,m設(shè)備零件(1)1263(2)8429(3)45824.1 零件的斜率指標(biāo)法(palmer)第一步：求各零件的斜度指標(biāo) 則: 1= -t11+t13=-1+4=3 2= -t21+t23=-2+5=3 3= -t31+t33=-6+8=2 4= -t41+t43=-3+2=-

17、1設(shè)備零件(1)1263(2)8429(3)4582k=1,2,m解：對于本例 i第二步：按不增的順序排列零件，即得滿意解 故排序：一一一或一一一= -ti1+ti34.2 關(guān)鍵零件法 第一步：計算各零件的 總加工時間ti，找出加 工時間最長的零件, 將其作為關(guān)鍵零件。第二步：除之外，將滿足ti1 tim的零件，按ti1的值從小到大把對應(yīng)的零件排在之前.第三步：除之外，將滿足ti1 tim的零件，按tim的值從大到小把對應(yīng)的零件排在之后.第四步：滿足ti1 = tim的零件，既可放在的緊前，又可放在的緊后.第五步：如果得到多個排序方案，選優(yōu)即可設(shè)備零件(1)1263(2)8429(3)4582

18、ti13111614tik為i零件在k設(shè)備上的 加工時間,m為設(shè)備數(shù).例：已知如下表求使加工周期最短的排序方案 設(shè)備零件(1)1263(2)8429(3)4582ti13111614解：計算此例中ti=ti1+ ti2+ti3 總加工時間最長的為零件，故關(guān)鍵零件選擇 ti1 ti3的零件為， 按ti1的值從小到大排 在之前，即為 一一 ti1 ti3的零件為 ， 排在之后，即為一 故排序為一一一 4.3 CDS法第一步:當(dāng)L=1,2, ,m-1時,分別計算加工時間:設(shè)備零件(1)1263(2)8429(3)4582tikk=1L tikk=m+1-Lm和第二步:對于每個L,用上述兩組數(shù)據(jù)構(gòu)成一

19、個兩臺設(shè)備的流水型排序問題,并用約翰遜法進(jìn)行排序。第三步:對所得（ m-1）個排序比較選優(yōu)。i L=1ti11263ti34582L=2ti1+ ti296812ti2+ ti31291011i1234L=1ti11263ti34582L=2ti1+ ti296812ti2+ ti31291011當(dāng)L=1時，排序為一一一 Fmax=28加工順序 (1)(2)（3）1 12939241513ti1ti2Fi1Fi2ti3Fi3 1 8 263 92 4458213182628加工順序(1)(2)（3）2 12986271810ti1ti2Fi1Fi2ti3Fi3 2 4 613 98 25842

20、11192329當(dāng)L=2時，排序為一一一 Fmax=29故按CDS法排序結(jié)果為：一一一 Fmax=28 i1234L=1ti11263ti34582L=2ti1+ ti296812ti2+ ti31291011第一步：將各零件在設(shè)備上的加工時間按設(shè)備的數(shù)量從中間一分為二，當(dāng)設(shè)備為奇數(shù)時，加工時間上下各半第二步：計算前半部分加工時間之和與后半部分加工時間之和的比值i第三步：按比值i的大小由小到大排列，即得排序方案 設(shè)備零件(1)8610144(2)128736(3)845108(4)6147107排序系數(shù)i20/1414/1817/1217/2010/154.4 最小排序系數(shù)法(中間分割法)故排

21、序一一一一 設(shè)備 零件 （1）4 82 5 9 （2）2 3 6 4 1 （3）57384 （4）621678課堂練習(xí)： 分別用零件的斜率指標(biāo)法、關(guān)鍵零件法、 CDS法和中間分割法對下列問題排序。 則: 1= -1.5ti1-0.5ti2 +0.5ti3+1.5ti4 = -1.5 4-0.5 2 +0.5 5+1.5 6=4.5 2= -1.5t21-0.5t22 +0.5t23+1.5t24 =-7 3= -1.5t31-0.5t32 +0.5t33+1.5t34 =19.5 4= -1.5t41-0.5t42 +0.5t43+1.5t44 =5 5= -1.5t51-0.5t52 +0.

22、5t53+1.5t54 =0按不增的順序排列零件，即得滿意解 故排序： 一一一 一= -1.5ti1-0.5ti2 +0.5ti3+1.5ti4（1）斜率指標(biāo)法設(shè)備 零件 （1）4 82 5 9 （2）2 3 6 4 1 （3）57384 （4）621678（2） 關(guān)鍵零件法設(shè)備 零件 （1）4 82 5 9 （2）2 3 6 4 1 （3）57384 （4）621678ti1720272422解：計算此例中 ti=ti1+ ti2+ti3 +ti4 總加工時間最長的 為零件，故關(guān)鍵 零件為 ti1 ti4的零件為 ， 按ti1的值從小到大排 在之前，即為 一一 ti1 ti4的零件為 ， 按

23、ti4的值從大到小排 在之后，即為一一 故排序 一 一一一（3 ）CDS法設(shè)備 零件 （1）4 82 5 9 （2）2 3 6 4 1 （3）57384 （4）621678解：當(dāng)L=1,2, 3(m-1)時,分別計算加工時間:tikk=1L tikk=m+1-Lm和iL=1ti14 82 5 9 ti4621678L=2ti1+ ti26118910ti3+ ti4119191512L=3ti1+ ti2+ ti31118111714ti2+ ti3+ ti41312251913iL=1ti14 82 5 9 ti4621678L=2ti1+ ti26118910ti3+ ti41191915

24、12L=3ti1+ ti2+ ti31118111714ti2+ ti3+ ti41312251913當(dāng)L=1時，排序為一一一一加工順序(1)(2)（3）（4）ti1ti2Fi1Fi2ti3Fi3ti4Fi4 2 6316 4 256 5 487 9 1488 3722 20116 288 211510 3111 282416 3827 484033 50Fmax=50iL=1ti14 82 5 9 ti4621678L=2ti1+ ti26118910ti3+ ti4119191512L=3ti1+ ti2+ ti31118111714ti2+ ti3+ ti41312251913當(dāng)L=2時

25、，排序為一一一一加工順序(1)(2)（3）（4）ti1ti2Fi1Fi2ti3Fi3ti4Fi4 4 256 2 6316 5 487 9 1488 3724 20116286 211612 3111 282415 3817 484033 50Fmax=50iL=1ti14 82 5 9 ti4621678L=2ti1+ ti26118910ti3+ ti4119191512L=3ti1+ ti2+ ti31118111714ti2+ ti3+ ti41312251913當(dāng)L=3時，排序為一一一一 或一一一一Fmax=50最終排序結(jié)果為：一一一一 或一一一一（4）中間分割法設(shè)備 零件 （1）4

26、 82 5 9 （2）2 3 6 4 1 （3）57384 （4）621678排序系數(shù)i6/1111/98/199/1510/12按比值i的大小由小到大排列，即得排序方案: 一 一 一一5 實際應(yīng)用例題例：東風(fēng)汽車維修和上漆公司正在爭取一份名為“風(fēng)暴的合同，這個合同的一個主要要求就是迅速交貨，即如果能夠?qū)?輛需要維修和噴漆的車在24小時內(nèi)整修并重新噴漆，這份合同就成交下面是東風(fēng)汽車維修和上漆公司對這5輛車進(jìn)行整修和上漆分別所需的作業(yè)時間問東風(fēng)汽車維修和上漆公司能否取得這份名為風(fēng)暴”的合同工藝要求在噴漆之前必須先進(jìn)行整修汽車整修時間(小時)噴漆時間(小時)A63B04C52D86E21解:這個問

27、題可以看作是一個n種零件二臺設(shè)備流水型排序問題，用約翰遜法很容易就可解決首先進(jìn)行排序： 設(shè)備 零件ABCDE整修60582上漆34261最終排序結(jié)果：BD A CE 其次計算加工周期 設(shè)備零件ABCDE整修60584上漆34261答：東風(fēng)汽車維修和上漆公司能取得這份名為“風(fēng)暴”的合同。 加工順序BCADE整修上漆t(yī)i1ti2Fi1Fi20486521236021 19148422211714流水型作業(yè)排序問題：加工路線相同設(shè)備零件 A車床158612 B銑床3156 C磨床41057第四節(jié) 單件作業(yè)排序問題(零件1，工序1，車床)(零件1，工序2，銑床)(零件1，工序3，磨床)(零件2，工序1

28、，車床)(零件2，工序2，銑床)(零件2，工序3，磨床)單件作業(yè)排序問題問題：加工路線不同(零件1，工序1，車床)(零件1，工序2，銑床)(零件1，工序3，磨床)(零件2，工序1，銑床)(零件2，工序2，磨床)(零件2，工序3，車床)1 問題的描述2 排序方法3 優(yōu)選調(diào)度法則第四節(jié) 單件作業(yè)排序問題1 問題的描述(1)對于流水型作業(yè)排序問題，第K道工序永遠(yuǎn)在MK上加工，沒有必要將工序號與機器號分開.(2)對于單件作業(yè)排序問題，每個工件都有其獨特的加工路線，工件沒有一定的流向，要描述一道工序，必須將工件號、工序號和機器號結(jié)合在一起。(3)為了能夠準(zhǔn)確地表達(dá)上述信息，引入事件這一概念。(4)事件的

29、表達(dá)方式為：(i，j，k)，i表示工件號，j表示工序號，k表示完成i工件的第j道工序的機器代號。試說明事件 (3，4，1)和事件(2，3，3)的含義(5)用加工描述矩陣D來描述所有工件的加工 每一行描述一個工件的加工，故每一行的工件號相同，每一列的工序號相同(6)加工時間矩陣 2 4 2 3 5 4T 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2D單件作業(yè)計劃種類: 半能動作業(yè)計劃（Semi-active schedule） 各工序都按最早可能開（完）工時間安排的作業(yè)計劃。 能動作業(yè)計劃（Active schedule） 任何一臺機器的每段空閑時間都不足以加工一道可加

30、工工序的半能動作業(yè)計劃。無延遲作業(yè)計劃（Non-delay schedu1e） 沒有任何延遲出現(xiàn)的能動作業(yè)計劃。“延遲”： 有工件等待加工時，機器出現(xiàn)空閑，即使這段空閑時間不足于完成一道工序。2 兩種單件作業(yè)排序方法2 兩種單件作業(yè)排序方法例：加工描述矩陣和加工時間矩陣如下，分別按下列兩種方法進(jìn)行作業(yè)排序(1)最小最早完工時間法（能動作業(yè)計劃）(2)最小最早開工時間法（無延遲作業(yè)計劃） 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2D 2 4 2 3 5 4T(l)最小最早完工時間法 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2D 2 4 2

31、3 5 4T序列可排事件最早可能開工時間最早可能完工時間最小最早可能完工時間所需機器排定事件1234561,3,2M2141412 1,3,22,3,2M29912781,3,22,3,22,2,1M1898731,3,22,2,11,2,3M3778331,2,32,2,12,1,3M3363201,2,32,1,31,1,1M1223001,1,12,1,3排定事件條件最小最早完工時間法選擇排定事件的條件：（1）屬于可排事件（2）符合所需機器（3）最早可能開工時間小于最小最早可能完工時間返回按此方法編制出的作業(yè)計劃叫做：能動作業(yè)計劃 1,1,1 1,2,3 1,3,2 2,1,3 2,2,

32、1 2,3,2D 2 4 2 3 5 4T排定事件1,1,12,1,31,2,32,2,12,3,21,3,2時間機器機器1機器2機器31,1,12,1,31,2,32,2,12,3,21,3,2003237812148(2)最小最早開工時間法 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2D 2 4 2 3 5 4T序列可排事件最早可能開工時間最早可能完工時間最小最早可能開工時間所需機器排定事件1234562,3,2M29139 2,3,2 1,3,2M27912781,3,22,3,22,2,1M1398731,3,22,2,11,2,3M3M133 78331,2

33、,32,2,12,1,3M3063201,2,32,1,31,1,1M1M300 23001,1,12,1,3排定事件條件最小最早開工時間法選擇排定事件的條件：（1）屬于可排事件（2）符合所需機器（3）最早可能開工時間等于最小最早可能開工時間返回時間機器機器1機器2機器3 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2D 2 4 2 3 5 4T排定事件1,1,12,1,31,2,32,2,11,3,22,3,2按此方法編制出的作業(yè)計劃叫做：無延遲作業(yè)計劃 1,1,12,1,31,2,32,2,12,3,21,3,200323789137(1)最小最早完工時間法 序列可

34、排事件最早可能開工時間最早可能完工時間最小最早可能完工時間所需機器排定事件1234561,3,2M2141412 1,3,22,3,2M29912781,3,22,3,22,2,1M1898731,3,22,2,11,2,3M3778331,2,32,2,12,1,3M3363201,2,32,1,31,1,1M1223001,1,12,1,33 優(yōu)選調(diào)度法則(2)最小最早開工時間法 序列可排事件最早可能開工時間最早可能完工時間最小最早可能開工時間所需機器排定事件1234562,3,2M29139 2,3,2 1,3,2M27912781,3,22,3,22,2,1M1398731,3,22,

35、2,11,2,3M3M133 78331,2,32,2,12,1,3M3063201,2,32,1,31,1,1M1M300 23001,1,12,1,33 優(yōu)選調(diào)度法則 SPT：優(yōu)先選擇加工時間最短的事件 PCFS：優(yōu)先選擇最早進(jìn)入可排事件集合的事件 EDD：優(yōu)先選擇完工期限緊的事件 MWKR：優(yōu)先選擇余下加工時間最長的事件 LWKR：優(yōu)先選擇余下加工時間最小的事件 MOPNR：優(yōu)先選擇余下工序數(shù)最多的事件 RANDOM：隨機地挑選一個 1,1,1 1,2,2 1,3,3 1,4,4 2,1,3 2,2,1 2,3,4 2,4,3 3,1,1 3,2,4 3,3,3 3,4,2 4,1,2

36、4,2,4 4,3,1 4,4,3 D 5 7 6 2 8 3 4 9 4 4 5 1 6 2 7 3T例 ：有一個4/4/G/ Fmax問題，其加工描述矩陣和加工時間矩陣為：試用優(yōu)選調(diào)度法則求近優(yōu)解（用最小最早開工時間法） 。優(yōu)選調(diào)度法則的層次為： MWKR：優(yōu)先選擇余下加工時間最長的事件； SPT：優(yōu)先選擇加工時間最短的事件； RANDOM：隨機地挑選一個。 序列可排事件最早可能開工時間最早可能完工時間最小最早可能開工時間所需機器排定事件1234,1,2M2012119658501,2,22,2,1 3,1,14,1,21,1,12,2,1 3,1,14,1,21,1,1M1M1M2000511460800M1M3M1M22,1,30000 58 4600 001,1,12,1,3 3,1,14,1,2 1,1,1 1,2,2 1,3,3 1,4,4 2,1,3 2,2,1 2,3,4 2,4,3 3,1,1 3,2,4 3,3,3 3,4,2 4,1,2 4,2,4 4,3,1 4,4,3 D 5 7 6 2 8 3 4 9 4 4 5 1 6 2 7 3T MWKR SPT RANDOM序列可排事件最早可能開工時間最早可能完工時間最小最早可能開工時間所需機器排定事件456 4,2,4M461912138139961,3,32,2,1 3,2,44,2,4