【正文】 243214321分鐘）（代入例中數(shù)字：短的單件時(shí)間。前后工序兩兩對(duì)比，較一般式：周期順序移動(dòng)方式下的加工平行較短較短較短????????????????????????????????????????TttntnTtntntnnttnnttnntntttnnttntTimiimiiiiii 第二節(jié) 生產(chǎn)過程任務(wù)排序 一、流水型排序問題 n項(xiàng)任務(wù)，等待多臺(tái)串聯(lián)設(shè)備組成的生產(chǎn)線加工，各項(xiàng)任務(wù)的工藝順序相同。 n項(xiàng)任務(wù)，單臺(tái)設(shè)備 (一個(gè)單位 )的排序。例： 8項(xiàng)任務(wù)、單臺(tái)設(shè)備，資料如下： 任 務(wù) j1 j2 j3 j4 j5 j6 j7 j8 加工時(shí)間 tj 8 3 6 12 7 5 3 2 交貨期 dj 19 12 9 33 48 40 37 23 任 務(wù) j8 j2 j7 j6 j3 j5 j1 j4 加工時(shí)間 tj 2 3 3 5 6 7 8 12 交貨期 dj 23 12 37 40 9 48 19 34 流程時(shí)間 Fi 2 5 8 13 19 26 34 46 延期量 Dj 0 0 0 0 10 0 15 13 1)、最小加工時(shí)間規(guī)則 (SPT) 按各任務(wù)加工時(shí)間的大小，從小大到排序。 本規(guī)則可得到最小平均流程時(shí)間，最小平均在制品占用量。但可能出現(xiàn)延期交貨。 平均流程時(shí)間： 2) EDD規(guī)則 最早交貨期規(guī)則 任 務(wù) j3 j2 j1 j8 j4 j7 j6 j5 加工時(shí)間 tj 6 3 8 2 12 3 5 7 交貨期 dj 9 12 19 23 34 37 40 48 流程時(shí)間 Fi 6 9 17 19 31 34 39 46 延期量 Dj 0 0 0 0 0 0 0 0 ? 按任務(wù)規(guī)定的交貨期先后，從小到大排序。 ? 可使交貨延期量最小化，但平均流程時(shí)間相對(duì)較大，平均在制品數(shù)較大。 ? 平均流程時(shí)間 ? 最大交貨延期量為零 任 務(wù) j3 j2 j1 j8 j4 j7 j6 j5 加工時(shí)間 tj 6 3 8 2 12 3 5 7 交貨期 dj 9 12 19 23 34 37 40 48 流程時(shí)間 Fi 6 9 17 19 31 34 39 46 延期量 Dj 0 0 0 0 0 0 0 0 ? 3）、 EDDSPT綜合規(guī)則： ? 按 EDD規(guī)則排序所的方案的基礎(chǔ)上，按 SPT規(guī)則對(duì)其調(diào)整。 任 務(wù) j2 j3 j8 j1 j7 j4 j6 j5 加工時(shí)間 tj 3 6 2 8 3 12 5 7 交貨期 dj 12 9 23 19 37 33 40 48 流程時(shí)間 Fi 3 9 11 19 22 34 39 46 延期量 Dj 0 0 0 0 0 0 0 0 ? 找出最大流程時(shí)間 max Fi ? 找出滿足條件： dj≥max Fi 的任務(wù)，當(dāng)滿足條件的任務(wù)只有一項(xiàng)時(shí)，該任務(wù)不調(diào)整，當(dāng)滿足條件的任務(wù)有多項(xiàng)時(shí)，對(duì)這些任務(wù)按 SPT規(guī)則調(diào)整。 ? 去掉已調(diào)整的任務(wù)，對(duì)剩余任務(wù)反復(fù)用第二步直至所有任務(wù)調(diào)整完 ? 平均流程時(shí)間 ? 最大交貨延期量為零 N項(xiàng)任務(wù)、兩臺(tái)設(shè)備的排序 任 務(wù) j1 j2 j3 j4 j5 j6 j7 j8 Ma taj 8 3 6 12 7 5 3 2 Mb tbj 9 2 5 3 4 10 7 11 N項(xiàng)任務(wù)，均按 MaMb 的工藝順序加工，要求最大流程時(shí)間最小化的最優(yōu)排序方案。 用約翰孫 貝爾曼規(guī)則求解 找出最小加工時(shí)間，如果該時(shí)間在第一臺(tái)設(shè)備行，則對(duì)應(yīng)的任務(wù)最先加工，若在第二臺(tái)設(shè)備行，則對(duì)應(yīng)的任務(wù)排在最后加工； 去掉已排序任務(wù)，對(duì)剩下的任務(wù)反復(fù)應(yīng)用第 1步，直至所有任務(wù)排完。 按約 貝規(guī)則對(duì)上例進(jìn)行排序，得到排序結(jié)果如下： 任務(wù) j8 j7 j6 j1 j3 j5 j4 j2 Ma taj 2 2 3 5 5 10 8 18 6 24 7 31 12 43 3 46 Mb tbj 11 13 7 20 10 30 9 39 5 44 4 48 3 51 2 53 J8J7J6J1J3J5J4J2 用哈姆表算法，求得各任務(wù)在各設(shè)備上的完工時(shí)間如下表： 排序前的流程時(shí)間計(jì)算 任 務(wù) j1 j2 j3 j4 j5 j6 j7 j8 Ma taj 8 8 3 11 6 17 12 29 7 36 5 41 3 44 2 46 Mb tbj 9 17 2 19 5 24 3 32 4 40 10 51 7 58 11 69 任務(wù) j1 j2 j3 j4 j5 j6 j7 j8 Ma taj 2 3 5 8 6 7 12 3 Mb tbj 11 7 10 9 5 4 3 2 Mc tcj 11 13 12 15 16 11 12 14 N項(xiàng)任務(wù)、三臺(tái)設(shè)備的排序 例：三臺(tái)設(shè)備、 8項(xiàng)任務(wù)，各任務(wù)的工藝順序相同，資料如下： ? 求最優(yōu)解條件，滿足如下條件之一： ? 求解步驟 ： ? 把三臺(tái)設(shè)備轉(zhuǎn)換為兩臺(tái)假象設(shè)備，假想設(shè)備加工時(shí)間按如下公式轉(zhuǎn)換： ???????jbjcjhjbjajgtttttt,, 任 務(wù) j1 j2 j3 j4 j5 j6 j7 j8 Mg tgj 13 10 15 17 11 11 15 5 Mh thj 22 20 22 24 21 15 15 16 用約 貝規(guī)則求得排序結(jié)果如下： J8J2J5J6J1J3J7J4； (或： J4J7） 上例中，滿足條件 jbjc tt , maxmin ?轉(zhuǎn)換兩臺(tái)假想設(shè)備，結(jié)果如下表： 任務(wù) j8 j2 j5 j6 j1 j3 j7 j4 Ma taj 3 3 3 6 6 12 7 19 2 21 5 26 12 38 8 46 Mb tbj 2 5 7 13 5 18 4 23 11 34 10 44 3 47 9 56 Mc tcj 14 19 13 32 16 48 11 59 11 70 12 82 12 94 15 109 用哈姆表算法分別計(jì)算兩方案的流程時(shí)間： J8J2J5J6J1J3J7J4； 任務(wù) j8 j2 j5 j6 j1 j3 j4 j7 Ma taj 3 3 3 6 6 12 7 19 2 21 5 26 8 34 12 48 Mb tbj 2 5 7 13 5 18 4 23 11 34 10 44 9 53 3 56 Mc tcj 14 19 13 32 16 48 11 59 11 70 12 82 15 97 12 109 J8J2J5J6J1J3J4J7 任務(wù) j1 j2 j3 j4 j5 j6 j7 j8 Ma taj 2 2 3 5 5 10 8 18 6 24 7 31 12 43 3 46 Mb tbj 11 13 7 20 10 30 9 39 5 44 4 48 3 51 2 53 Mc tcj 11 24 13 33 12 45 15 60 16 76 11 87 12 99 14 113 按自然順序加工的流程時(shí)間計(jì)算 N項(xiàng)任務(wù)， m臺(tái)設(shè)備的排序方法 ： 例： 8項(xiàng)任務(wù)，須經(jīng) 6臺(tái)設(shè)備加工，求最優(yōu)加工順序： 任務(wù) 設(shè)備 j1 j2 j3 j4 j5 j6 j7 j8 M1 t1j 5 7 5 2 5 6 4 2 M2 t2j 7 5 8 6 6 2 2 3 M3 t1j 3 6 4 4 7 6 3 2 M4 t1j 4 3 6 1 9 3 11 9 M5 t1j 8 2 9 6 1 8 3 7 M6 t1j 2 9 1 3 8 9 7 6 合 計(jì) 29 32 33 22 36 35 30 29 ? 1）、關(guān)鍵任務(wù)法： ? 求出各項(xiàng)任務(wù)的總加工時(shí)間； ? 以總加工時(shí)間最大者為關(guān)鍵任務(wù) JC； ? 找出： t1,j tm,j 的任務(wù)，按 t1,j 從小到大排在 JC 前面； ? 找出： t1,j tm,j的任務(wù)，按 tm,j 從大到小排在 JC 后面； ? t1,j = tm,j的任務(wù)，排在 JC 緊前或緊后 。 ? 求上例加工順序： ? 關(guān)鍵零件： Jc=J5 ? 滿足 t1,j tm,j的零件有： J2 、 J4 、 J6 、 J7 、J8, 按 t1j大小從小到大排在： J5 之前： ? J8 J4 J7 J6 J2 J5 ? 滿足 t1,jtm,j的零件有： J J3， 按 tm,j從大到小排在 J5之后。 ? 得到加工順序： ? J8 J4 J7 J6 J2 J5 J1 J3 ? 用哈姆表算法計(jì)算流程時(shí)間： 任務(wù) 設(shè)備 j8 J4 j7 j6 j2 j5 j1 j3 M1 t1j 2 2 2 4 4 8 6 14 7 21 5 26 5 31 5 36 M2 t2j 3 5 6 11 2 13 2 16 5 26 6 32 7 39 8 47 M3 t1j 2 7 4 15 3 18 6 24 6 32 7 39 3 42 4 51 M4 t1j 9 15 1 16 11 29 3 32 3 35 9 48 4 52 6 58 M5 t1j 7 22 6 28 3 31 8 40 2 42 1 49 8 60 9 69 M6 t1j 6 28 3 31 7 38 9 49 9 58 8 66 2 68 1 70 任務(wù) 設(shè)備 j1 j2 j3 j4 j5 j6 j7 j8 M1 t1j 5 5 7 12 5 17 2 19 5 24 6 30 4 34 2 36 M2 t2j 7 12 5 17 8 25 6 31 6 37