【正文】 80 = 84 = 62 = E 85 30 37 F 104 50 32 合計 427 381 325 設備負荷率 ABCDEF EFACDB FECDAB 工作時間 占用時間 負荷率 占用時間 負荷 率 占用時間 負荷率 M1 29 29 100% 29 100% 29 100% M2 33 39 % 33 100% 35 % M3 48 48 100% 60 80% 48 100% M4 65 70 % 65 100% 65 100% M5 45 66 % 63 % 55 % 平均 % % % 排序方案的求優(yōu)和計算量問題 ★ 6 種零件可以有 6!=720個排序方案 10種零件 10!=3628800個方案 20種零件 20!= 如果用窮舉法，把所有方案都排出來從中選最優(yōu)方案。用計算機來排序并計算，如果計算機每秒能計算一萬個方案， 20個零件需要 年 468 1360 024365 418??? ???求解排序問題的啟發(fā)式方法 ★ 當零件數(shù)增加時，排序方案呈指數(shù)型增長，所以當零件較多時，由于計算工作量太大，目前沒有可行的求最優(yōu)解的方法。數(shù)學界做了很多研究，已得出結論，大部分排序問題均屬 NP難題，沒有有效的算法可以求解，只有一小部份特殊問題可以找到專門的算法。因此當前排序問題的一個重要發(fā)展方向是尋找實用的啟發(fā)式方法，目標是求近優(yōu)解。 啟發(fā)式方法舉例 —關鍵工序法 關鍵工序法編制步驟： ,并把全部零件分成三組 首 尾 分在第一組 首 = 尾 分在第二組 首 尾 分在第三組 第一組 每一零件分別將關鍵工序前的各工序相加 根據(jù)相加后的數(shù)值按遞增序列排隊 關鍵工序法 (續(xù) ) 第三組 每一零件分別將關鍵工序之后的工序相加 根據(jù)相加后的數(shù)值按遞減序列排隊 第二組 組內零件按第一組的規(guī)則排列 (當?shù)谝唤M的 零件 數(shù)少于第三組時 ) 組內零件按第三組的規(guī)則排列 (當?shù)谌M的零件 數(shù)少于第一組時 ) 三組排第二組后面 關鍵工序法例題計算 M4的工作量最大 ,故 M4為關鍵工序 A B C D E F 合計M1 3 8 6 9 1 2 29M2 13 2 2 4 7 5 33M3 7 16 10 9 6 0 48M4 15 7 8 10 11 14 65M5 6 4 7 12 5 11 4第二和第三組 第一組 首工序 尾工序 A 。C 。D 。E 。F 第二組 首工序 = 尾工序 無零件 第三組 首工序 尾工序 B 關鍵工序法 (續(xù) ) 關鍵工序法 (續(xù) ) 第一組 M1 + M2 + M3 A 3 13 7 = 23 C 6 2 10 = 18 D 9 4 9 = 22 E 1 7 6 = 14 F 2 5 0 = 7 第一組內零件的投產順序為 F E C D A 關鍵工序法 (續(xù) ) 第三組組內排序 只有一個零件 B 第二組組內排序 組內無零件 第一組 第二組 第三組 F E C D A B 所以總的投產順序為 : F E C D A B 零件甘特圖 M1M2M3M4M5F E C D A B 優(yōu)先規(guī)則法排序原理 M1 M2 M3 A11 B12 C43 等待隊 E23 F43 等待隊 C51 D31 E23 等待隊 E32 A22 C51 優(yōu)先規(guī)則排序法 優(yōu)先規(guī)則舉例 : 規(guī)則名稱 優(yōu)先原則 優(yōu)先級計算值 FCFS 先到的先安排 SPT 加工時間最短的作業(yè) Pij TWORK 加工工作量最大的工件 SLACK 余裕時間最少的工件 Dit SLACK/ FOPNR 余裕時間與剩余工序數(shù) (Dit ) 之比最小的工件 mi+1 ??mijPi1,mijPi,?mijPi,工件號 第一工序 第二工序 第三工序 第四工序 總 工時 交貨期 設備工時 設備 工時 設備工時 設備 工時 J1 M1 5 M2 5 M3 7 M4 3 20 28 J2 M2 7 M1 4 M3 1 M4 6 18 28 J3 M3 2 M1 6 M4 3 M2 7 18 25 J4 M3 4 M2 4 M1 6 M4 2 16 26 M2 M3 M4 t11 t12 t13 t14 t21 t22 t23 t24 t31 t41 t42 t43 t44 t32 t33 t34 7 11 16 23 23 22 27 2 6 15 16 時間 M1 24 19 11 14 5 11 15 21 按 SPT規(guī)則排出的零件進度計劃 M2 t11 M3 M4 M1 t32 t12 t13 t21 t22 t23 t31 t41 t42 t43 t14 t24 t44 t33 T34 5 11 15 16 22 7 12 16 23 2 6 12 19 20 11 14 19 22 28 30 按 FCFS規(guī)則排出的零件進度計劃 M4 t22 t13 t23 t31 t41 t43 t33 t14 t24 t44 t12 t21 t42 T34 t11 t32 M3 M2 M1 5 11 16 15 22 7 12 16 23 2 6 12 19 20 11 14 19 22 28 30 按 MWKR規(guī)則排出的零件進度計劃 t33 M4 t22 t13 t23 t31 t41 t43 t14 t24 t44 t12 t21 t42 T34 t11 t32 M3 M2 M1 5 11 17 21 7 11 16 23 11 14 17 19 23 26 32 2 6 16 23 24 按 SLACK規(guī)則排出的零件進度計劃 SPT FCFS MWKR SLACK 工件 編號 交貨 期限 F MAX L F max L F max L F max L J1 28 27 － 1 22 － 6 22 － 6 26 － 2 J2 28 24 － 4 28 0 28 0 32 4 J3 25 23 － 2 23 － 2 23 － 2 23 － 2 J4 26 24 － 2 30 4 30 4 19 － 7 F max 27 30 30 32 平均最大流程 延誤件數(shù) 0 1 1 1 平均延遲 － － 1 － 1 － 按不同排序規(guī)則所得的不同結果 演講完畢，謝謝觀看！