【文章內(nèi)容簡介】 (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)法則） 這種方法使拖期項目達(dá)到最少，如期完成作業(yè)項目最多。它是在 EDD原則的基礎(chǔ)上排序，依次計算每項作業(yè)是否拖期。如果拖期，則將該作業(yè)移到最后加工，然后再檢查任務(wù)是否拖期，直到第一次向后移的任務(wù)仍然拖期為止。 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) 總天數(shù) 項目數(shù) 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法，可使任務(wù)拖期時間減少 （ 3） More法則可使拖期的作業(yè)項目達(dá)到最少 多臺設(shè)備的排序問題 2 n 排序問題 3 n 排序問題 m n 排序問題 序：多臺設(shè)備完工時間的計算 設(shè) n個工件的加工順序為Ｓ (Ｓ 1,Ｓ 2,Ｓ 3,…., Ｓ n)其中Ｓ i為排在第 i位加工的工件代號．以 表示工件 Si在機器 Mk上的完工時間， 表示工件 Si在上 Mk的加工時間，則可按以下公式計算 iSkC kisp 在熟悉以上計算公式以后，可以直接在加工時間矩陣上從左向右計算完工時間并標(biāo)注在加工時間的右上角 nimkpCCCpCCkikiSiSiSkiiSiSskkkS,... ...2,1。,... ,3,2},max{11)1(11????????? 由遞推公式可知，對于第一行第一列，只需將加工時間的數(shù)值作為完工時間標(biāo)在加工時間的右上角，對于第一行的其它元素，只需從左到右依次將前一列右上角的數(shù)字加上計算列的加工時間，并將結(jié)果填在計算列加工時間的右上角．對于從第二行到第 m行第一列，只要把上一行右上角的數(shù)字和本行的加工時間相加，將結(jié)果填在本行加工時間的右上角，從第二列到第 n列，則要從本行前一列右上角和本列上一行的右上角數(shù)字中取大者，再加上本列的加工時間，將結(jié)果填在本列加工時間的右上角．最后一行的最后一列右上角數(shù)字即為整個完工時間 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 例如：有一個４ ６的排序問題，其加工時間如下表，當(dāng)按順序Ｓ（６，１，５，２，４，３）加工時，其完工時間是多少 （ 1）、 2 n 流水型排序問題 n項任務(wù)在兩臺機床上加工，該問題使用約翰遜 貝爾曼規(guī)則，可求出最優(yōu)解（總工時最小的排序）。 約翰遜 貝爾曼規(guī)則為： 1）檢查 tAi, tBi的各數(shù)值，找出最小值。其中 tAi為零件在機床 A上加工的單件時間， tBi為零件在 B 機床上加工的單件時間， A為第一道工序， B為第二道工序。 2）若最小值為 tAi, 則該零件排在設(shè)備 A上最先加工，若tBi為最小值，則該零件在 B機床上最后加工。 3）將上述已排序的零件除去，重復(fù)上述兩個步驟，直至全部零件排完為止。 例： 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 結(jié)束 21 25 32 45 61 66 B 加工開始 21 25 32 52 61 71 結(jié)束 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 結(jié)束 4 10 17 33 46 67 B 加工開始 4 11 25 45 55 67 結(jié)束 11 25 45 55 60 71 （ 2）、 3 n 流水型排序問題 n項任務(wù)依次在 A， B， C三臺機床上加工，設(shè) tAi, tBi ,tCi為第 i種任務(wù)（零件）在 A， B， C機床上的單件工時。排序方法有兩種： 1）。當(dāng)符合下列兩個條件之一時，可將三臺機床的排序轉(zhuǎn)化 為兩臺機床排序問題。 (1) mintAi ≥ maxtBi (2) mintCi ≥ max tBi 設(shè)有機床 G與 H， 設(shè) 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 結(jié)束 6 13 19 24 32 40 B 加工開始 6 13 19 24 32 40 結(jié)束 7 16 24 30 36 42 C 加工開始 7 17 26 34 41 47 結(jié)束 17 26 34 41 47 53 按上列排序順序，安排三臺機床加工零件的順序： 2）、 3 n 問題在不符合上述條件下，按 m n問題求解。 （ 3）、 m n 流水型排序問題 m n 流水型排序問題常用的啟發(fā)式方法有Palmer法、 CDS法 、 關(guān)鍵 零件法 A. Palmer法 １９６５年Ｄ .Ｓ .Palmer法 提出按斜度指標(biāo)排列工件的啟發(fā)式算法，稱之為 Palmer法 ．工件的斜度指標(biāo)可按下式計算 ? ? ikmki pmk?????12/)1(?m為機器數(shù)目， 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)次加工順序，取其中最好的結(jié)果 例：有 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. 關(guān)鍵零件法 ，步驟如下： （ 1）在 n種零件中，求出總工時最大的零件，作為關(guān)鍵零件 Jc。 （ 2） 除去關(guān)鍵零件 Jc， 將滿足 ti1tim的零件，按ti1值的大小，從小到大排列在 Jc之前。式中： i為零件號。 （ 3）除去關(guān)鍵零件 Jc， 將滿足 ti1tim的零件，按tim值的大小，從大到小排列在 Jc之后。 （ 4）若 ti1=tim ， 則相應(yīng)的零件可排在 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種零件在一臺設(shè)備上加工，加工工時、交貨期如下，試分別用 SPT法， EDD法， More法安排投產(chǎn)順序。 任務(wù)編號 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種零件，單