【正文】 12 24 3 9 16 24 35 47 71 3 6 9 20 46 55 73 78 80 M1 M2 時(shí)間 Fmax =80 圖 113 作業(yè)排序甘特圖 工件 Ji J1 J2 J3 J4 J5 J6 J7 加工時(shí)間 M1 6 8 12 3 7 11 24 M2 11 9 5 3 26 18 2 工件排序結(jié)果 J4 J1 J5 J2 J6 J3 J7 加工時(shí)間 M1 3 6 7 8 11 12 24 M2 3 11 26 9 18 5 2 J4 J1 J5 J2 J6 J3 J7 2/2/2023 74 若存在一個(gè) n/3/P/Fmax問題，且 mint1i ≥maxt2i 或 mint3i ≥ mint2i ( i =1， 2， …… ，n)，則可采用 Johnson法排序。 求解步驟為： （ 1）先找出 mint1i ≥maxt2i或 mint3i ≥ mint2i關(guān)系 （ 2）將 3臺(tái)設(shè)備變換成 2臺(tái)假想設(shè)備 MA和 MB，并令 tAi = t1i + t2i ； tBi = t2i + t3i （ 3）依據(jù) tAi 和 tBi， 采用 Johnson法則進(jìn)行作業(yè)排序 二、多個(gè)工件在三臺(tái)設(shè)備上的作業(yè)排序 (采用 Johnson法則 ) 試采用 Johnson法則進(jìn)行作業(yè)排序 工 件 設(shè) 備 J1 J2 J3 J4 M1 15 8 6 12 M2 3 1 5 6 M3 4 10 5 7 表 1117 加工時(shí)間表 例：有一個(gè) 4/3/P/ Fmax問題，其加工時(shí)間如表 1117所示 2/2/2023 75 解： ① ∵ mint1i =6 maxt2i =6 存在 mint1i ≥maxt2i mint3i =4 mint2i =1 存在 mint3i ≥ mint2i ∴ 可采用 Johnson法求解該作業(yè)排序問題 (具備其一即可 )。 ② 計(jì)算 tAi 和 tBi， 列于表 1118中 表 1118 tAi 、 tBi 與排序結(jié)果 學(xué)生自己練習(xí)繪制排序結(jié)果甘特圖 工 件 設(shè) 備 J1 J2 J3 J4 (MA) tAi 18 9 11 18 (MB) tBi， 7 11 10 13 排序結(jié)果 J2 J4 J3 J1 t1i 8 12 6 15 t2i 1 6 5 3 t3i 10 7 5 4 8 20 26 41 9 26 31 44 19 33 38 48 ③ 依據(jù) 1118中的 tAi 和 tBi， 采用 Johnson法進(jìn)行作業(yè)排序。排序結(jié)果與 Fmax如表 1118及圖 114所示。 Fmax = 48 2/2/2023 76 J2 J4 J3 J1 8 12 6 15 1 6 5 3 8 9 20 26 31 41 44 8 20 26 41 10 7 5 4 9 19 26 33 38 44 48 M1 M2 M3 時(shí) 間 圖 114 排序結(jié)果甘特圖 2/2/2023 77 n個(gè)工件在 m臺(tái)設(shè)備上排序是比較困難的。但是，對(duì)于 2個(gè)工件在 m臺(tái)設(shè)備上排序問題，運(yùn)用圖解法雖然不一定求到最佳解，卻可以求到比較令人滿意的解。 例： 2個(gè)工件在 4臺(tái)機(jī)器上加工，每個(gè)工件的加工順序不同。 J1的加工順序是M1， M2， M3， M4； J2的加工順序是 M4， M2， M1， M3， 其加工時(shí)間如表 1119所示。顯然，這是一個(gè)非流水作業(yè)排序問題，是一個(gè)一般的排序問題，故可用2/4/G/Fmax表示，也可用 2/4/G/Cmax表示。 三、兩個(gè)工件在 m臺(tái)設(shè)備上的作業(yè)排序 該問題亦可用加工描述矩陣 D與加工時(shí)間矩陣 T表示為： 表 1119 加工時(shí)間表 （一） 用圖解法求解 設(shè) 備 工 件 M1 M2 M3 M4 J1 2 5 4 1 J2 2 5 3 6 ?????????342441132331222221412111，，，，，，，，D?????????31245652T2/2/2023 78 第四節(jié) 多臺(tái)設(shè)備作業(yè)排序 （ 1）畫平面直角坐標(biāo)，橫、縱軸分別為 J J2 的加工時(shí)間，對(duì)應(yīng)橫軸下部的甘特圖與對(duì)應(yīng)縱軸左側(cè)的甘特圖分別表示 J J2 加工順序及其所對(duì)應(yīng)的加工時(shí)間，原點(diǎn) O為時(shí)間起點(diǎn)。找出表示 J J2 總加工時(shí)間的坐標(biāo)點(diǎn) D(12， 16)。 （ 2）劃去不可能同時(shí)加工兩個(gè)工件的時(shí)間。開始時(shí)， J1 在 M1上加工， M1 便不能加工 J2 ，故劃去方格 Ⅰ 的區(qū)域，同理劃去方格 Ⅱ 、 Ⅲ 、 Ⅳ 的區(qū)域。 （ 3）從原點(diǎn)開始，在未劃去的區(qū)域中，連線到終點(diǎn) D。連線若為 45176。角，表示2個(gè)工件同時(shí)在 被 加工。例如 A點(diǎn) (6,6)，表示 J1在 M1上加工早已完畢，正在 M2上加工； J2 在 M4上加工剛好完畢，正準(zhǔn)備進(jìn)入 M2上加工，但由于 M2正在加工 J1， 所以，又等了 1個(gè)單位時(shí)間到 B點(diǎn) (7,6) ，此時(shí)， M2剛好加工完 J1。從 B點(diǎn)開始， M2加工 J2， M3加工 J1； 接著 M1加工 J2， M4加工 J1。到了 C點(diǎn) (12,11)， M4剛好加工完 J1， M2 剛好加工完 J2。 C點(diǎn)到 D點(diǎn)是豎直線，此段時(shí)間 J1已加工完畢， M1和 M3只加工 J2 。 三、兩個(gè)工件在 m臺(tái)設(shè)備上的作業(yè)排序 例，解：該問題可采用圖解法求作業(yè)排序的解。 ?????????342441132331222221412111，，，，，，，，D?????????31245652T2/2/2023 79 例，解： （ 3）由原點(diǎn)向 D點(diǎn)引連線時(shí)，盡量按 45176。角方向引線，并使等待時(shí)間最小。在實(shí)際操作上，這種排序方法常常通過目視、徒手畫的方法完成的，所以，不能保證求得最佳的排序結(jié)果，只能求得較令人滿意的結(jié)果。從作圖求解過程可知： J1工件沒有等待時(shí)間，F(xiàn)1max =12； J2 加工等待時(shí)間為 1，所以，F(xiàn)2max =17。當(dāng)然此問題也可寫成 C1max =12； C2max =17。該圖解法求解 2/4/G/ Cmax 問題的過程如圖 115所示。 2/2/2023 80 圖 115 圖解法求解 2/4/G/Cmax過程圖 J1 J2 M1 M2 2 7 M3 11 M4 12 M4 M2 6 11 M1 13 M3 16 I II III IV ?? ?A(6,6) B(7,6) C(12,11) D(12,16) 0452/2/2023 81 例，解： 上述作業(yè) 排序問題 2/4/G/Fmax , 三、兩個(gè)工件在 m臺(tái)設(shè)備上的作業(yè)排序 的排序結(jié)果如圖 116所示。 ?????????3,4,24,4,11,3,23,3,12,2,22,2,14,1,21,1,1D?????????31245562T2, 2, 2 (1,4,4) （ 2） 2 12 （ 2） 14 2 （ 5） 7 （ 5） 12 7 （ 4） 11 14 （ 3） 17 （ 6） 6 11 12 （ 1） Fmax = Cmax =17 J1 J2 J2 J2 J2 J1 J1 J1 M1 M2 M3 M4 o 時(shí)間 圖 116 作業(yè)排序甘特圖 1,1,1 2,3,1 1,2,2 1,3,3 2,2,22,4,3 2,1,4 2/2/2023 82 三、兩個(gè)工件在 m臺(tái)設(shè)備上的作業(yè)排序 （二） 用啟發(fā)式算法求解 請(qǐng)同學(xué)們按能動(dòng)作業(yè)計(jì)劃構(gòu)成步驟求解。 前述的 2/4/G/Fmax , ?????????3,4,24,4,11,3,23,3,12,2,22,2,14,1,21,1,1D可采用按能動(dòng)作業(yè)計(jì)劃構(gòu)成步驟求 ?????????31245562T解，其求解 (排序 )過程及結(jié)果如表 1120與圖 117所示。 2/2/2023 83 表 11— 20 能動(dòng)作業(yè)計(jì)劃構(gòu)成表 t ? Ot } Tk T?k T* M* Oj 1 1, 1, 1 2, 1, 4 0 0 2 6 2 M1 1, 1, 1 2 1, 2, 2 2, 1, 4 2 0 7 6 6 M4 2, 1, 4 3 1, 2, 2 2, 2, 2 2 7 7 12 7 M2 1, 2, 2 4 1, 3, 3 2, 2, 2 7 7 11 12 11 M3 1, 3, 3 5 1, 4, 4 2, 2, 2 11 7 12 12 12 M2 2, 2, 2 6 1, 4, 4 2, 3, 1 11 12 12 14 12 M4 1, 4, 4 7 2, 3, 1 2, 4, 3 12 14 14 17 14 M1 2, 3, 1 8 2, 4, 3 14 17 17 M3 2, 4, 3 2/2/2023 84 （二） 用啟發(fā)式算法求解 按能動(dòng)作業(yè)計(jì)劃構(gòu)成步驟求解 ? 根據(jù) 1120可繪出如圖 117所示的該問題作業(yè)排序甘特圖。由圖 117可見，采用啟發(fā)式算法，按能動(dòng)作業(yè)計(jì)劃構(gòu)成步驟進(jìn)行求解，作業(yè)排序結(jié)果甘特圖與圖解法得出的圖 116所示的甘特圖相同，說明兩種方法求解結(jié)果相同。 1,1,1 2, 3,1 1, 2, 2 2, 2, 2 1, 3, 3