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