【文章內(nèi)容簡(jiǎn)介】 3 Pi1 10 22 14 12 Pi4 15 15 12 15 i 1 2 3 4 Pi1 1 9 5 4 Pi2 5 7 6 3 Pi3 4 6 3 5 Pi4 6 2 3 7 L=3時(shí)： 2/1/2023 46 排序?yàn)椋?S1=（ 1， 4， 2 ， 3 ） i 1 4 2 3 Pi1 1 4 9 5 Pi2 5 3 7 6 Pi3 4 5 6 3 Pi4 6 7 2 3 1 5 14 19 6 9 21 27 10 15 27 30 16 23 29 33 Fmax=33 所以最終排序?yàn)椋?S1=（ 1， 4， 2 ， 3 ）滿意解。 2/1/2023 47 三、采用 Johnson法則解決多個(gè)工件在三臺(tái)設(shè)備上的作業(yè)排序 若存在一個(gè) n/3/P/Fmax問(wèn)題，且 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è)排序 試采用 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問(wèn)題，其加工時(shí)間如表 1117所示 2/1/2023 48 解： ① ∵ mint1i =6 maxt2i =6 存在 mint1i ≥maxt2i mint3i =4 mint2i =1 存在 mint3i ≥ mint2i ∴ 可采用 Johnson法求解該作業(yè)排序問(wèn)題 (具備其一即可 )。 ② 計(jì)算 tAi 和 tBi，列于表 1118中 表 1118 tAi 、 tBi 與排序結(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/1/2023 49 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/1/2023 50 單件作業(yè)排序是最一般的排序問(wèn)題，也是最復(fù)雜的一種排序問(wèn)題。該問(wèn)題本身容易表達(dá)，也能看出該問(wèn)題所需要求解的是什么，但是朝著求解方向作任何推進(jìn)都是極為困難的。許多人在此問(wèn)題上都進(jìn)行了探索，但一無(wú)所獲者大有人在。 第三節(jié) 單件作業(yè)排序問(wèn)題 2/1/2023 51 第三節(jié) 單件作業(yè)排序問(wèn)題 一、問(wèn)題的描述 對(duì)一般的單件作業(yè)排序問(wèn)題，每個(gè)工件都有其獨(dú)特的加工路線，工件沒(méi)有一定的流向。但是，對(duì)于流水作業(yè)的排序問(wèn)題，第 k道工序永遠(yuǎn)在 MK上 進(jìn)行，沒(méi)有必要將工序號(hào)與機(jī)器號(hào)分開(kāi)。而對(duì)于一般的單件作業(yè)排序問(wèn)題，要描述一道工序需要 i、 j、 k三個(gè)參數(shù)，即 i、j、 k表示第 i 個(gè)工件的第 j道工序在 Mk(第 k臺(tái)機(jī)器上 )上進(jìn)行的。所以，可以用加工描述矩陣的形式來(lái)描述所有工件的加工。加工描述矩陣的形式如加工描述矩陣 D所示。 ?????????2,3,21,2,23,1,22,3,13,2,11,1,1D 加工描述矩陣的每一行描述一個(gè)工件的加工過(guò)程 (第 1行描述第一個(gè)工件的加工過(guò)程，第二行描述第 2個(gè)工件的加工過(guò)程 )。 D的每一組數(shù)中的第 1列數(shù)表示工件序號(hào)； D的每組數(shù)中的第 2列數(shù)碼相同，說(shuō)明第 2列表示工序號(hào)； D的每一組數(shù)中的第3列數(shù)表示設(shè)備序號(hào)。 ?????????598845T2/1/2023 52 第三節(jié) 單件作業(yè)排序問(wèn)題 二、一般 n/m/G/Fmax問(wèn)題的啟發(fā)式算法 n/m/G/Fmax 為 n個(gè)工件， m臺(tái)機(jī)器，一般單件作業(yè)排序問(wèn)題，使最大流程時(shí)間最短。對(duì)這類作業(yè)排序問(wèn)題，可以用分支定界法或整數(shù)規(guī)劃法求最優(yōu)解。但是，都是無(wú)效的方法。為此，在實(shí)際工作中，多采用啟發(fā)式算法。為了對(duì)研究啟發(fā)式算法有所幫助，先介紹兩種十分重要的作業(yè)計(jì)劃及其構(gòu)成方法。 2/1/2023 53 (一 ) 兩種作業(yè)計(jì)劃的構(gòu)成 一般說(shuō)來(lái)，在可行的加工順序下，可以擬定出無(wú)數(shù)種作業(yè)計(jì)劃。其中，各工序都按最早可能開(kāi)始工作的時(shí)間安排作業(yè)計(jì)劃，稱為半能動(dòng)作業(yè)計(jì)劃。任何一臺(tái)機(jī)器的每段空閑時(shí)間都不足以加工一道可加工工序的半能動(dòng)作業(yè)計(jì)劃，又稱為能動(dòng)作業(yè)計(jì)劃。 無(wú)延遲作業(yè)計(jì)劃是指沒(méi)有任何延遲出現(xiàn)的能動(dòng)作業(yè)計(jì)劃。 所謂“延遲”是指工件等待加工時(shí)，機(jī)器出現(xiàn)空閑 ( 即使這段空閑時(shí)間不足以完成一道工序的加工 )。 能動(dòng)作業(yè)計(jì)劃和無(wú)延遲作業(yè)計(jì)劃在研究一般單件作業(yè)排序問(wèn)題時(shí)有重要作用。 二、一般 n/m/G/Fmax問(wèn)題的啟發(fā)式算法 2/1/2023 54 △ 能動(dòng)作業(yè)計(jì)劃與無(wú)延遲作業(yè)計(jì)劃構(gòu)成過(guò)程中涉及到的 4個(gè)符號(hào)： 若將每安排一道工序稱為“一步”。 設(shè) ： ? St } — 為第 t 步之前已排序工序構(gòu)成的部分作業(yè)計(jì)劃； ? Ot } — 為第 t 步可以排序的工序集合； Tk — 為 ? Ot }中工序 Ok 的最早可能開(kāi)工時(shí)間； T?k — 為 ? Ot } 中工序 Ok的最早可能完工時(shí)間。 顯然： Ok工序的作業(yè)時(shí)間 = T?k Tk 2/1/2023 55 1. 設(shè) t=1,? S1 }為空集， ? O1 }為各工件第一道工序的集合。 2. 求 T*=min|T’k|,并求出 T*出現(xiàn)的機(jī)器 M*。如果 M*有多臺(tái)，則任選一臺(tái)。 3. 從 ? Ot }中挑出滿足以下兩個(gè)條件的工序 Oj ，需要機(jī)器 M*加工，且 TjT*。 4. 將確定的工序 Oj放入 ? St } ，從 ? Ot }中消去 Oj ，并將 Oj的緊后工序放入 ? Ot } ，使 t=t+1。 5. 若還有未安排的工序，轉(zhuǎn)步驟（ 2）；否則，停止。 6. 二、一般 n/m/G/Fmax問(wèn)題的啟發(fā)式算法 (一 ) 兩種作業(yè)計(jì)劃的構(gòu)成 P310 能動(dòng)作業(yè)計(jì)劃的構(gòu)成步驟 2/1/2023 56 例 ：有一個(gè) 2/3/G/Fmax問(wèn)題，其加工描述矩陣 D和加工時(shí)間矩陣 T分別為：試構(gòu)成一個(gè)能動(dòng)作業(yè)計(jì)劃。 P310 ? 按表 11~9 所示的能動(dòng)作業(yè)計(jì)劃構(gòu)成過(guò)程，可繪出圖 11~4能動(dòng)作業(yè)計(jì)劃時(shí)間安排 (排序 )圖 — 能動(dòng)作業(yè)計(jì)劃。 ??????????????????5144322,3,22,3,11,2,23,2,13,1,21,1,1 TD2/1/2023 57 表 11— 9 能動(dòng)作業(yè)計(jì)劃的構(gòu)成 T *＝ min {T?k} t ? Ot } Tk T T?k T* M* Oj 1 2 3 4 5 6 },max{ 39。 11 ??? kkk TTT 39。 1?? kk TT下期工序最早可能開(kāi)工時(shí)間： 1, 1, 1 2, 1, 3 1, 2, 3 2, 2， 1 1, 3， 2 2, 3， 2 1, 1, 1 2, 1, 3 1, 2, 3 2, 1, 3 1, 2, 3 2, 2， 1 1, 3， 2 2, 2， 1 1, 3， 2 2, 3， 2 2, 3， 2 0 0 2 0 3 3 7 3 7 7 8 2 3 4 3 4 4 1 4 1 5 5 2 3 6 3 7 7 8 7 8 12 13 2 3 7 7 8 13 M1 M3 M3 M1 M1 M2 M2 2,4,1 3,4,5 T= D= 1,1,1 1,2,3 1,3 2 2,1,3 2,2,1 2,3,2 或： 一個(gè) 2/3/G/Fmax問(wèn)題 2/1/2023 58 能動(dòng)作業(yè)計(jì)劃的甘特圖；最大流程： Fmax=13 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 M1— M2— M3— 1,1,1 2,2,1 2 3 7 2,1,3 1,2,3 7 3 1,3,2 2,3,2 7 8 13 ??????????????????5144322,3,22,3,11,2,23,2,13,1,21,1,1 TD2/1/2023 59 對(duì)表 11~9所示的能動(dòng)作業(yè)計(jì)劃（作業(yè)時(shí)間排序）構(gòu)成過(guò)程可描述為下列過(guò)程： （ 1）當(dāng) t =1時(shí) ? O1 } 為： 2個(gè) 工件、可以在第 1道工序上、進(jìn)行第 1步排序的集合，即 ? O1 } = ? （ 1, 1, 1）；（ 2, 1, 3） } 。它們的最早可能開(kāi)工時(shí)間 Tk = T1 =0。工序（ 1, 1, 1）的最早可能完工時(shí)間 T180。k = T180。1 =2；工序（ 2, 1, 3）的 T180。k = T180。1 =3， ? T*= min ? T?k }=2。 可見(jiàn)， T*= 2出現(xiàn)的機(jī)器 M*= M1。 在這一步中 M1上僅有一道工序（ 1, 1, 1）可以排序。所以，首先安排（ 1, 1, 1）在 M1上加工。 （ 2）、（ 3） …… （略） （ 4）當(dāng) t=4 時(shí)， ? O4 } = ? （ 1, 3, 2）；（ 2, 2, 1） }， T4 =7或 3， T180。4 =8或 7。 T*=7，出現(xiàn)在 M1上， ? 將 （ 2, 2, 1）安排在 M1上加工。 （ 5） …… （略） （ 6）當(dāng) t=6 時(shí)， ? O6 } = ? （ 2, 3, 2） }， T6=8， T180。6 =13。 此時(shí)只剩下 （ 2, 3, 2）， ? 將 （ 2, 3, 2）安排在 M2上加工。 ?該排序問(wèn)題最后完工時(shí)間為 13。 能動(dòng)作業(yè)計(jì)劃的構(gòu)成步驟 (一 ) 兩種作業(yè)計(jì)劃的構(gòu)成 2/1/2023 60 在作業(yè)計(jì)劃中，“延遲”是指工件等待加工，而機(jī)器出現(xiàn)空閑（空閑時(shí)間不能完成一道工序的加工作業(yè)）。所以，無(wú)