【正文】 80 = 84 = 62 = E 85 30 37 F 104 50 32 合計(jì) 427 381 325 設(shè)備負(fù)荷率 ABCDEF EFACDB FECDAB 工作時(shí)間 占用時(shí)間 負(fù)荷率 占用時(shí)間 負(fù)荷 率 占用時(shí)間 負(fù)荷率 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)和計(jì)算量問(wèn)題 ★ 6 種零件可以有 6!=720個(gè)排序方案 10種零件 10!=3628800個(gè)方案 20種零件 20!= 如果用窮舉法，把所有方案都排出來(lái)從中選最優(yōu)方案。用計(jì)算機(jī)來(lái)排序并計(jì)算，如果計(jì)算機(jī)每秒能計(jì)算一萬(wàn)個(gè)方案， 20個(gè)零件需要 年 468 1360 024365 418??? ???求解排序問(wèn)題的啟發(fā)式方法 ★ 當(dāng)零件數(shù)增加時(shí)，排序方案呈指數(shù)型增長(zhǎng)，所以當(dāng)零件較多時(shí)，由于計(jì)算工作量太大，目前沒(méi)有可行的求最優(yōu)解的方法。數(shù)學(xué)界做了很多研究，已得出結(jié)論，大部分排序問(wèn)題均屬 NP難題，沒(méi)有有效的算法可以求解，只有一小部份特殊問(wèn)題可以找到專門的算法。因此當(dāng)前排序問(wèn)題的一個(gè)重要發(fā)展方向是尋找實(shí)用的啟發(fā)式方法，目標(biāo)是求近優(yōu)解。 啟發(fā)式方法舉例 —關(guān)鍵工序法 關(guān)鍵工序法編制步驟： ,并把全部零件分成三組 首 尾 分在第一組 首 = 尾 分在第二組 首 尾 分在第三組 第一組 每一零件分別將關(guān)鍵工序前的各工序相加 根據(jù)相加后的數(shù)值按遞增序列排隊(duì) 關(guān)鍵工序法 (續(xù) ) 第三組 每一零件分別將關(guān)鍵工序之后的工序相加 根據(jù)相加后的數(shù)值按遞減序列排隊(duì) 第二組 組內(nèi)零件按第一組的規(guī)則排列 (當(dāng)?shù)谝唤M的 零件 數(shù)少于第三組時(shí) ) 組內(nèi)零件按第三組的規(guī)則排列 (當(dāng)?shù)谌M的零件 數(shù)少于第一組時(shí) ) 三組排第二組后面 關(guān)鍵工序法例題計(jì)算 M4的工作量最大 ,故 M4為關(guān)鍵工序 A B C D E F 合計(jì)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 第二組 首工序 = 尾工序 無(wú)零件 第三組 首工序 尾工序 B 關(guān)鍵工序法 (續(xù) ) 關(guān)鍵工序法 (續(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 第一組內(nèi)零件的投產(chǎn)順序?yàn)? F E C D A 關(guān)鍵工序法 (續(xù) ) 第三組組內(nèi)排序 只有一個(gè)零件 B 第二組組內(nèi)排序 組內(nèi)無(wú)零件 第一組 第二組 第三組 F E C D A B 所以總的投產(chǎn)順序?yàn)? : F E C D A B 零件甘特圖 M1M2M3M4M5F E C D A B 優(yōu)先規(guī)則法排序原理 M1 M2 M3 A11 B12 C43 等待隊(duì) E23 F43 等待隊(duì) C51 D31 E23 等待隊(duì) E32 A22 C51 優(yōu)先規(guī)則排序法 優(yōu)先規(guī)則舉例 : 規(guī)則名稱 優(yōu)先原則 優(yōu)先級(jí)計(jì)算值 FCFS 先到的先安排 SPT 加工時(shí)間最短的作業(yè) Pij TWORK 加工工作量最大的工件 SLACK 余裕時(shí)間最少的工件 Dit SLACK/ FOPNR 余裕時(shí)間與剩余工序數(shù) (Dit ) 之比最小的工件 mi+1 ??mijPi1,mijPi,?mijPi,工件號(hào) 第一工序 第二工序 第三工序 第四工序 總 工時(shí) 交貨期 設(shè)備工時(shí) 設(shè)備 工時(shí) 設(shè)備工時(shí) 設(shè)備 工時(shí) 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 時(shí)間 M1 24 19 11 14 5 11 15 21 按 SPT規(guī)則排出的零件進(jìn)度計(jì)劃 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ī)則排出的零件進(jìn)度計(jì)劃 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ī)則排出的零件進(jìn)度計(jì)劃 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ī)則排出的零件進(jìn)度計(jì)劃 SPT FCFS MWKR SLACK 工件 編號(hào) 交貨 期限 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ī)則所得的不同結(jié)果 演講完畢，謝謝觀看！