【正文】 20 46 55 73 78 80 （ 3）運(yùn)用 Johnson法則對(duì)此問(wèn)題求解如表 1116和圖 113所示。排序結(jié)果與 Fmax如表 1118及圖 114所示。 J1的加工順序是M1， M2， M3， M4； J2的加工順序是 M4， M2， M1， M3， 其加工時(shí)間如表 1119所示。 （ 2）劃去不可能同時(shí)加工兩個(gè)工件的時(shí)間。角，表示2個(gè)工件同時(shí)在 被 加工。 C點(diǎn)到 D點(diǎn)是豎直線，此段時(shí)間 J1已加工完畢， M1和 M3只加工 J2 。在實(shí)際操作上，這種排序方法常常通過(guò)目視、徒手畫(huà)的方法完成的，所以，不能保證求得最佳的排序結(jié)果，只能求得較令人滿意的結(jié)果。 2/1/2023 80 圖 115 圖解法求解 2/4/G/Cmax過(guò)程圖 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/1/2023 81 例，解： 上述作業(yè) 排序問(wèn)題 2/4/G/Fmax , 三、兩個(gè)工件在 m臺(tái)設(shè)備上的作業(yè)排序 的排序結(jié)果如圖 116所示。由圖 117可見(jiàn)，采用啟發(fā)式算法，按能動(dòng)作業(yè)計(jì)劃構(gòu)成步驟進(jìn)行求解，作業(yè)排序結(jié)果甘特圖與圖解法得出的圖 116所示的甘特圖相同，說(shuō)明兩種方法求解結(jié)果相同。 前述的 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解，其求解 (排序 )過(guò)程及結(jié)果如表 1120與圖 117所示。當(dāng)然此問(wèn)題也可寫(xiě)成 C1max =12； C2max =17。 ?????????342441132331222221412111，，，，D?????????31245652T2/1/2023 79 例，解： （ 3）由原點(diǎn)向 D點(diǎn)引連線時(shí)，盡量按 45176。從 B點(diǎn)開(kāi)始， M2加工 J2， M3加工 J1； 接著 M1加工 J2， M4加工 J1。 （ 3）從原點(diǎn)開(kāi)始，在未劃去的區(qū)域中，連線到終點(diǎn) D。 三、兩個(gè)工件在 m臺(tái)設(shè)備上的作業(yè)排序 該問(wèn)題亦可用加工描述矩陣 D與加工時(shí)間矩陣 T表示為： 表 1119 加工時(shí)間表 （一） 用圖解法求解 設(shè) 備 工 件 M1 M2 M3 M4 J1 2 5 4 1 J2 2 5 3 6 ?????????342441132331222221412111，，，，D?????????31245652T2/1/2023 78 第四節(jié) 多臺(tái)設(shè)備作業(yè)排序 （ 1）畫(huà)平面直角坐標(biāo)，橫、縱軸分別為 J J2 的加工時(shí)間，對(duì)應(yīng)橫軸下部的甘特圖與對(duì)應(yīng)縱軸左側(cè)的甘特圖分別表示 J J2 加工順序及其所對(duì)應(yīng)的加工時(shí)間，原點(diǎn) O為時(shí)間起點(diǎn)。但是，對(duì)于 2個(gè)工件在 m臺(tái)設(shè)備上排序問(wèn)題，運(yùn)用圖解法雖然不一定求到最佳解，卻可以求到比較令人滿意的解。 求解步驟為： （ 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問(wèn)題，其加工時(shí)間如表 1117所示 2/1/2023 75 解： ① ∵ mint1i =6 maxt2i =6 存在 mint1i ≥maxt2i mint3i =4 mint2i =1 存在 mint3i ≥ mint2i ∴ 可采用 Johnson法求解該作業(yè)排序問(wèn)題 (具備其一即可 )。 （ 2）劃去已排序工件，在余下來(lái)的未排序工件中仍然按上述方法進(jìn)行作業(yè)排序，直到全部工件安排完為止。 5 7 10 14 22 31 表 1114 排序方案及各參數(shù)結(jié)果表 (三 ) 優(yōu)先調(diào)度法則例題 (此為單臺(tái)設(shè)備排序問(wèn)題例題 ) 按 SPT與 EDD結(jié)合規(guī)則排序，可得出表 1110的排序問(wèn)題的排序?yàn)椋? J4 — J3 — J6 — J1— J2 — J5 表 1110排序問(wèn)題的結(jié)論如表 1114所示。此時(shí)出現(xiàn)情況如表 1113所示。所以，其排序?yàn)椋? J4 — J3 — J6 — J2 — J1 — J5 按此排序可以求得： Lmax = max{Li}= 1，滿足要求 。為了說(shuō)明問(wèn)題方便，仍以表 1110所示的排序問(wèn)題為例。 2/1/2023 67 由表 1112計(jì)算可知，該例采用 EDD法則排序?yàn)椋? J J3 、 J6 、J2 、 J J5，且各工件延遲時(shí)間均為 0。 EDD 法則的優(yōu)點(diǎn)是考慮了交貨期，有利于做到按期交貨，使工件中的最大延遲時(shí)間最小。 (三 ) 優(yōu)先調(diào)度法則例題 (此為單臺(tái)設(shè)備排序問(wèn)題例題 ) 表 1110 加工時(shí)間與交貨期表 工序號(hào) J1 J2 J3 J4 J5 J6 加工時(shí)間 4 8 2 5 9 3 交貨期 24 23 8 6 32 13 2/1/2023 65 SPT法則 (最短加工時(shí)間規(guī)則 )例題。 P312 解：表 11— 10無(wú)延遲作業(yè)計(jì)劃的構(gòu)成 ??????????????????5144322,3,22,3,11,2,23,2,13,1,21,1,1 TDt ? Ot } Tk T T?k T* M* Oj 1 1, 1, 1 2, 1, 3 0 0 2 3 2 3 0 0 M1 1, 1, 1 2 1, 2, 3 2, 1, 3 2 0 4 3 6 3 0 M3 2, 1, 3 3 1, 2, 3 2, 2， 1 3 3 4 4 7 7 3 3 M3 1, 2, 3 4 1, 3， 2 2, 2， 1 7 3 1 4 8 7 3 M1 2, 2， 1 5 1, 3， 2 2, 3， 2 7 7 1 5 8 12 7 7 M2 2, 3， 2 6 1, 3， 2 12 1 13 12 M2 1, 3， 2 最大流程： Fmax=13 2/1/2023 62 無(wú)延遲作業(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 12 13 2/1/2023 63 (二 ) 作業(yè)排序的三類啟發(fā)式算法 優(yōu)先調(diào)度法 ( 見(jiàn)教材 311~314頁(yè) ) 對(duì)應(yīng) 用 優(yōu)先調(diào)度法則的說(shuō)明 8個(gè)主要的優(yōu)先調(diào)度法則： P312 二、一般 n/m/G/Fmax問(wèn)題的啟發(fā)式算法 2/1/2023 64 SPT法則 (最短加工時(shí)間規(guī)則 )例題 SPT法則就是優(yōu)先選擇加工時(shí)間最短的工序。 3. 從 ? Ot }中挑出滿足以下兩個(gè)條件的工序 Oj ，需要機(jī)器 M*加工，且Tj=T*。所以，無(wú)延遲作業(yè)計(jì)劃是指沒(méi)有任何延遲出現(xiàn)的能動(dòng)作業(yè)計(jì)劃。6 =13。 （ 2）、（ 3） …… （略） （ 4）當(dāng) t=4 時(shí)， ? O4 } = ? （ 1, 3, 2）；（ 2, 2, 1） }， T4 =7或 3， T180。1 =3， ? T*= min ? T?k }=2。工序（ 1, 1, 1）的最早可能完工時(shí)間 T180。 ??????????????????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。 4. 將確定的工序 Oj放入 ? St } ，從 ? Ot }中消去 Oj ，并將 Oj的緊后工序放入 ? Ot } ，使 t=t+1。 顯然： Ok工序的作業(yè)時(shí)間 = T?k Tk 2/1/2023 55 1. 設(shè) t=1,? S1 }為空集， ? O1 }為各工件第一道工序的集合。 所謂“延遲”是指工件等待加工時(shí)，機(jī)器出現(xiàn)空閑 ( 即使這段空閑時(shí)間不足以完成一道工序的加工 )。 2/1/2023 53 (一 ) 兩種作業(yè)計(jì)劃的構(gòu)成 一般說(shuō)來(lái)，在可行的加工順序下，可以擬定出無(wú)數(shù)種作業(yè)計(jì)劃。對(duì)這類作業(yè)排序問(wèn)題，可以用分支定界法或整數(shù)規(guī)劃法求最優(yōu)解。加工描述矩陣的形式如加工描述矩陣 D所示。 第三節(jié) 單件作業(yè)排序問(wèn)題 2/1/2023 51 第三節(jié) 單件作業(yè)排序問(wèn)題 一、問(wèn)題的描述 對(duì)一般的單件作業(yè)排序問(wèn)題，每個(gè)工件都有其獨(dú)特的加工路線，工件沒(méi)有一定的流向。排序結(jié)果與Fmax如表 1118及圖 114所示。 工件 i 設(shè)備工時(shí) 2 3 1 4 Pi1 2 6 1 3 Pi2 4 2 8 9 Pi3 5 8 4 2 第二節(jié) 流水作業(yè)排序問(wèn)題 2 2/1/2023 40 P322習(xí)題 2：請(qǐng)用 CDS法排序并計(jì)算最長(zhǎng)流程時(shí)間 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 關(guān)鍵工件法求解過(guò)程如下： 2/1/2023 41 排序?yàn)椋?S1=（ 1， 4， 3 ， 2） i 1 2 3 4 L=1 Pi1 1 9 5 4 Pi4 6 2 3 7 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=1時(shí)： 2/1/2023 42 排序?yàn)椋?S1=（ 1， 4， 3 ， 2） i 1 4 3 2 Pi1 1 4 5 9 Pi2 5 3 6 7 Pi3 4 5 3 6 Pi4 6 7 3 2 1 5 10 19 6 9 16 26 10 15 19 32 16 23 26 34 Fmax=34 2/1/2023 43 排序?yàn)椋?S1=（ 1， 4， 2 ， 3 ） i 1 2 3 4 L=2 Pi1 6 16 11 7 Pi4 10 8 6 12 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=2時(shí)： 2/1/2023 44 排序?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