【文章內容簡介】 (i) 4 6 8 10 14 15 P(i) 2 1 6 4 8 10 W(i) 0 2 3 9 13 21 48 F(i) 2 3 9 13 21 31 79 L(i) 0 0 1 3 7 16 27 按期完成作業(yè)項目最多的原則排序（又稱摩爾 (More)法則） 這種方法使拖期項目達到最少，如期完成作業(yè)項目最多。它是在 EDD原則的基礎上排序，依次計算每項作業(yè)是否拖期。如果拖期，則將該作業(yè)移到最后加工，然后再檢查任務是否拖期，直到第一次向后移的任務仍然拖期為止。 K(i) 1 2 3 4 5 6 ? i 2 3 (6)5 (4) (1) 6 4 1 D(i) 4 6 (8)10 (14) (15) 8 14 15 P(i) 2 1 (6)4 (8) (10) 6 8 10 W(i) 0 2 (3)3 (7) (7) 7 13 21 46 F(i) 2 3 (9)7 (15) (17) 13 21 31 77 L(i) 0 0 (1)0 (1) (2) 5 7 16 28 四種優(yōu)先原則的排序比較表 優(yōu)先原則 等待時間 W(i) 完成時間F(i) 拖期 L(i) 總天數 項目數 1先到先安排 81 112 60 5 2 SPT 45 76 28 3 3 EDD 48 79 27 4 4 More 46 77 28 3 （ 1）按 SPT法，可使零件的等待時間，總加工時間最短 （ 2）按 EDD法，可使任務拖期時間減少 （ 3） More法則可使拖期的作業(yè)項目達到最少 多臺設備的排序問題 2 n 排序問題 3 n 排序問題 m n 排序問題 序：多臺設備完工時間的計算 設 n個工件的加工順序為Ｓ (Ｓ 1,Ｓ 2,Ｓ 3,…., Ｓ n)其中Ｓ i為排在第 i位加工的工件代號．以 表示工件 Si在機器 Mk上的完工時間， 表示工件 Si在上 Mk的加工時間，則可按以下公式計算 iSkC kisp 在熟悉以上計算公式以后，可以直接在加工時間矩陣上從左向右計算完工時間并標注在加工時間的右上角 nimkpCCCpCCkikiSiSiSkiiSiSskkkS,... ...2,1。,... ,3,2},max{11)1(11????????? 由遞推公式可知，對于第一行第一列，只需將加工時間的數值作為完工時間標在加工時間的右上角，對于第一行的其它元素，只需從左到右依次將前一列右上角的數字加上計算列的加工時間，并將結果填在計算列加工時間的右上角．對于從第二行到第 m行第一列，只要把上一行右上角的數字和本行的加工時間相加，將結果填在本行加工時間的右上角，從第二列到第 n列，則要從本行前一列右上角和本列上一行的右上角數字中取大者，再加上本列的加工時間，將結果填在本列加工時間的右上角．最后一行的最后一列右上角數字即為整個完工時間 iSkkiCSp i 1 2 3 4 5 6 Pi1 4 2 3 1 4 2 Pi2 4 5 6 7 4 5 Pi3 5 8 7 5 5 5 pi4 4 2 4 3 3 1 i 6 1 5 2 4 3 Pi1 22 46 410 212 113 316 Pi2 57 411 415 520 727 633 Pi3 512 517 522 830 535 742 pi4 113 421 325 232 338 446 例如：有一個４ ６的排序問題，其加工時間如下表，當按順序Ｓ（６，１，５，２，４，３）加工時，其完工時間是多少 （ 1）、 2 n 流水型排序問題 n項任務在兩臺機床上加工，該問題使用約翰遜 貝爾曼規(guī)則，可求出最優(yōu)解（總工時最小的排序）。 約翰遜 貝爾曼規(guī)則為： 1）檢查 tAi, tBi的各數值，找出最小值。其中 tAi為零件在機床 A上加工的單件時間， tBi為零件在 B 機床上加工的單件時間， A為第一道工序， B為第二道工序。 2）若最小值為 tAi, 則該零件排在設備 A上最先加工，若tBi為最小值，則該零件在 B機床上最后加工。 3）將上述已排序的零件除去，重復上述兩個步驟，直至全部零件排完為止。 例： A， B兩臺機床，加工 6種零件，單件工時如下，求最優(yōu)排序。 J1 J2 J3 J4 J5 J6 A 21 4 7 13 16 6 B 4 7 20 5 10 14 零件 代 號 單件工時 時 .件 1 機床 J2 J1 J6 J3 J4 J5 J1 J2 J3 J4 J5 J6 A 加工開始 0 21 25 32 45 61 結束 21 25 32 45 61 66 B 加工開始 21 25 32 52 61 71 結束 25 32 52 57 71 85 J1 J2 J3 J4 J5 J6 A 21 4 7 13 16 6 B 4 7 20 5 10 14 J2 J6 J3 J5 J4 J1 A 加工開始 0 4 10 17 33 46 結束 4 10 17 33 46 67 B 加工開始 4 11 25 45 55 67 結束 11 25 45 55 60 71 （ 2）、 3 n 流水型排序問題 n項任務依次在 A， B， C三臺機床上加工，設 tAi, tBi ,tCi為第 i種任務（零件）在 A， B， C機床上的單件工時。排序方法有兩種： 1）。當符合下列兩個條件之一時，可將三臺機床的排序轉化 為兩臺機床排序問題。 (1) mintAi ≥ maxtBi (2) mintCi ≥ max tBi 設有機床 G與 H， 設 tGi, tHi分別為 G與 H的單件加工時間，則 tGi = tAi + tBi， tHi = tBi + tCi 上述問題變換為 G， H兩臺機床的排序問題。 例： A， B， C三臺機床，加工 6種零件，單件工時如下，求最優(yōu)排序。 J1 J2 J3 J4 J5 J6 A 8 6 5 8 7 6 B 4 5 6 2 3 1 C 6 8 7 6 9 10 J1 J2 J3 J4 J5 J6 G 12 11 11 10 10 7 H 10 13 13 8 12 11 J4 J6 J5 J2 J3 J1 或 J6 J5 J3 J1 J2 J4 J6 J5 J2 J3 J1 J4 A 加工開始 0 6 13 19 24 32 結束 6 13 19 24 32 40 B 加工開始 6 13 19 24 32 40 結束 7 16 24 30 36 42 C 加工開始 7 17 26 34 41 47 結束 17 26 34 41 47 53 按上列排序順序，安排三臺機床加工零件的順序： 2）、 3 n 問題在不符合上述條件下，按 m n問題求解。 （ 3）、 m n 流水型排序問題 m n 流水型排序問題常用的啟發(fā)式方法有Palmer法、 CDS法 、 關鍵 零件法 A. Palmer法 １９６５年Ｄ .Ｓ .Palmer法 提出按斜度指標排列工件的啟發(fā)式算法，稱之為 Palmer法 ．工件的斜度指標可按下式計算 ? ? ikmki pmk?????12/)1(?m為機器數目， pik為工件 i在 Mk上的加工時間 按照各工件 λi的降序排列工件，可得出令人滿意的順序 例：有 7種零件在 5臺機床上加工，工藝順序均相同，工時如下，求較優(yōu)工序。 J1 J2 J3 J4 J5 J6 J7 M1 3 4 6 5 7 2 4 M2 2 5 7 1 6 5 6 M3 5 3 3 2 2 8 5 M4 2 3 4 2 5 2 2 M5 2 6 8 5 4 4 3 λ 2 2 1 1 8 1 6 ? ? 54211222/)1( iiiiikmki pppppmk ???????? ???J2,J3,J4,J6,J1,J7,J5 J2,J4,J3,J6,J1,J7,J5 B. CDS法 ， Campbell, Ｄ udek, .Ｓ mith三人提出了一個啟發(fā)式算法，稱之為 Palmer法 ．他們把 約翰遜 貝爾曼規(guī)則用于一般的流水排序問題，得到（ m1）個加工順序，取其中優(yōu)者． 具體做法是，對加工時間 1,..... .,2,1,11????????mlppmlmkiklkik 和用約翰遜 貝爾曼規(guī)則求 (m1)次加工順序，取其中最好的結果 例：有 7種零件在 5臺機床上加工，工藝順序均相同，工時如下，求較優(yōu)工序。 J1 J2 J3 J4 J5 J6 J7 M1 3 4 6 5 7 2 4 M2 2 5 7 1 6 5 6 M3 5 3 3 2 2 8 5 M4 2 3 4 2 5 2 2 M5 2 6 8 5 4 4 3 J1 J2 J3 J4 J5 J6 J7 l=1 pi1 3 4 6 5 7 2 4 J6,J2,J4,J3,J5,J7,J1 pi5 2 6 8 5 4 4 3 L=2 Pi1+pi2 5 9 13 6 13 7 10 J4,J2,J3,J5,J6,J7,J1 Pi4+pi5 4 9 12 7 9 6 5 L=3 Pi1+pi2+pi3 10 12 16 8 15 15 15 J2,J6,J3,J5,J7J1J4 Pi3+pi4+pi5 9 12 15 9 11 14 10 J2,J6,J3,J5,J7,J4,J1 L=4 Pi1+pi2+p13+pi4 12 15 20 10 20 17 17 J4,J2,J6,J3,J5,J7,J1 Pi2+pi3+pi4+pi5 11 17 22 10 17 19 16 2 5 7 1 6 5 6 5 3 3 2 2 8 5 2 3 4 2 5 2 2 （ 3）、 m n 流水型排序問題 C. 關鍵零件法 ，步驟如下： （ 1）在 n種零件中，求出總工時最大的零件，作為關鍵零件 Jc。 （ 2） 除去關鍵零件 Jc， 將滿足 ti1tim的零件，按ti1值的大小，從小到大排列在 Jc之前。式中： i為零件號。 （ 3）除去關鍵零件 Jc， 將滿足 ti1tim的零件，按tim值的大小，從大到小排列在 Jc之后。 （ 4）若 ti1=tim ， 則相應的零件可排在 Jc之緊前，也可排在 Jc之緊后。 例：有 7種零件在 5臺機床上加工，工藝順序均相同，工時如下，求較優(yōu)工序。 J1 J2 J3 J4 J5 J6 J7 M1 3 4 6 5 7 2 4 M2 2 5 7 1 6 5 6 M3 5 3 3 2 2 8 5 M4 2 3 4 2 5 2 2 M5 2 6 8 5 4 4 3 ∑ 14 21 28 15 24 21 20 J6 J2 J4 J3 J5 J7 J1 或 J6 J2 J3 J4 J5 J7 J1 作業(yè)： 1。有 9種零件在一臺設備上加工，加工工時、交貨期如下，試分別用 SPT法， EDD法， More法安排投產順序。 任務編號 i 1 2 3 4 5 6 7 8 9 作業(yè)時間 P(i) 6 7 3 1 4 5 2 8 1 交貨期 D(i) 12 15 10 5 8 6 13 20 25 2 。 A， B兩臺機床，流水加工 7種零件，單件工時如 下，求最優(yōu)排序。 J1 J2 J3 J4 J5 J6 J7 A 10 6 8 3 4 2 6 B 2 7 6 3 5 8 4 作業(yè)： 作業(yè)： 3。 A， B， C三臺機床，流水加工 6種零件，單