【正文】 /A / B。這個(gè)方法主要涉及到 4個(gè)參數(shù)，只用 4個(gè)參數(shù)就可以表示大多數(shù)不同的排序問題。 ? Fi —— Ji 的流程時(shí)間 ,即工件在車間的實(shí)際停留時(shí)間 , Fmax —— 最長流程時(shí)間 , Fmax = max{Fi}, 即一批工件中的最長流程時(shí)間 。 2. 采取平行移動(dòng)方式移送被加工的工件。 當(dāng)某臺機(jī)器已加工完一個(gè)工件，而下一個(gè)工件尚未到達(dá)。第 十 章 作業(yè)排序與生產(chǎn)作業(yè)計(jì)劃 第一節(jié) 作業(yè)排序的基本概念 第二節(jié) 流水作業(yè)排序問題 第三節(jié) 單件作業(yè)排序問題 第四節(jié) 多臺設(shè)備作業(yè)排序 2/1/2023 1 引 言 在確定了各車間的零部件投入、出產(chǎn)計(jì)劃、將全廠的生產(chǎn)計(jì)劃變成了各車間的生產(chǎn)任務(wù)后 ,各車間還應(yīng)將零部件的投入、出產(chǎn)計(jì)劃變成車間的作業(yè)計(jì)劃，即將車間的生產(chǎn)任務(wù)變成各工段、班組、各工作地的生產(chǎn)任務(wù)。這種情況稱為“工件等待”。 2/1/2023 5 1. 一個(gè)工件不能同時(shí)在幾臺不同的機(jī)器上被加工。 第一節(jié) 作業(yè)排序的基本概念 Ci —— Ji 的完工時(shí)間 ? Cmax —— 最長完工時(shí)間 ,Cmax = max{Ci}, 即一批工件中的最長完工時(shí)間 。 第一節(jié) 作業(yè)排序的基本概念 2/1/2023 12 通常采用 Conway等人提出的排序方法。 第一節(jié) 作業(yè)排序的基本概念 2/1/2023 14 第 十 章 作業(yè)排序與生產(chǎn)作業(yè)計(jì)劃回顧 ? 排序問題常見的分類方法有按 機(jī)器 、 工件 、 目標(biāo)函數(shù) 的特征分類。 當(dāng) Li 0 時(shí)為負(fù)延遲 , 即 Ji 提前完工 。但本節(jié)要討論的是一種特殊情況 ,即所有工件在各臺機(jī)器上的加工順序都相同的情況。 本節(jié)所討論的是 n/m/ρ/Fmax問題 ,目標(biāo)函數(shù)是使最長流程時(shí)間最短。然后 , 從加工時(shí)間矩陣中劃去已排序工件的加工時(shí)間。對例 (2,5,6,4,1,3)不符合 Johnson法則 , 但它也是一個(gè)最優(yōu)順序。啟發(fā)式算法以小的計(jì)算量得到足夠好的結(jié)果 ,因而十分適用。 (2)對于余下的工件 , 若 Pi1≦ Pim, 則按 Pi1不減的順序排成一個(gè)序列Sa；若 Pi1＞ Pim， 則按 Pim不增的順序排列成一個(gè)序列 Sb。 2/1/2023 47 三、采用 Johnson法則解決多個(gè)工件在三臺設(shè)備上的作業(yè)排序 若存在一個(gè) n/3/P/Fmax問題，且 mint1i ≥maxt2i 或 mint3i ≥ mint2i ( i =1， 2， …… ， n)，則可采用 Johnson法排序。但是，對于流水作業(yè)的排序問題，第 k道工序永遠(yuǎn)在 MK上 進(jìn)行，沒有必要將工序號與機(jī)器號分開。但是，都是無效的方法。 能動(dòng)作業(yè)計(jì)劃和無延遲作業(yè)計(jì)劃在研究一般單件作業(yè)排序問題時(shí)有重要作用。 5. 若還有未安排的工序，轉(zhuǎn)步驟（ 2）；否則，停止。k = T180。4 =8或 7。 無延遲作業(yè)計(jì)劃的構(gòu)成步驟 1. 設(shè) t=1,? S1 }為空集， ? O1 }為各工件第一道工序的集合。即排序時(shí)將各個(gè)工件的加工時(shí)間由短到長進(jìn)行排隊(duì)，排在前面的加工時(shí)間最短的工序優(yōu)先按排加工。其缺點(diǎn)是使平均流程時(shí)間 F增加，增大了在制品占用量。 (三 ) 優(yōu)先調(diào)度法則例題 (此為單臺設(shè)備排序問題例題 ) 表 1110 加工時(shí)間與交貨期表 工序號 J1 J2 J3 J4 J5 J6 加工時(shí)間 4 8 2 5 9 3 交貨期 24 23 8 6 32 13 2/1/2023 69 (三 ) 優(yōu)先調(diào)度法則例題 (此為單臺設(shè)備排序問題例題 ) SPT與 EDD混合 (結(jié)合 )法則例題 按 SPT與 EDD結(jié)合的規(guī)則排序步驟如下： （ 1）首先根據(jù) EDD規(guī)則排序，即安排一個(gè)使 Lmax?min(使最長延遲時(shí)間最短 )的初步方案。 (三 ) 優(yōu)先調(diào)度法則例題 (此為單臺設(shè)備排序問題例題 ) SPT與 EDD混合 (結(jié)合 )法則例題 工件排序 J4 J3 J6 J2 J1 加 工時(shí)間與 F 5 2 3 8 4 預(yù)定交貨 期 6 8 13 23 24 由表 1113可知，余下 5個(gè)工件中 J1 的 F最大， Fmax = 22。 (自己練習(xí) ) 表 1115 加 工 時(shí) 間 例：有一個(gè) 7/2/F/Fmax 問題，其加工時(shí)間如表 1115所示，試進(jìn)行作業(yè)排序。 例： 2個(gè)工件在 4臺機(jī)器上加工，每個(gè)工件的加工順序不同。連線若為 45176。角方向引線，并使等待時(shí)間最小。 2/1/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/1/2023 84 （二） 用啟發(fā)式算法求解 按能動(dòng)作業(yè)計(jì)劃構(gòu)成步驟求解 ? 根據(jù) 1120可繪出如圖 117所示的該問題作業(yè)排序甘特圖。該圖解法求解 2/4/G/ Cmax 問題的過程如圖 115所示。到了 C點(diǎn) (12,11)， M4剛好加工完 J1， M2 剛好加工完 J2。找出表示 J J2 總加工時(shí)間的坐標(biāo)點(diǎn) D(12， 16)。 ② 計(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è)排序。 SPT與 EDD混合 (結(jié)合 )法則例題 工件排序 J4 J3 J6 J1 J2 J5 加工時(shí)間與 F 5 2 3 4 8 9 預(yù)定交貨期 6 8 13 24 23 32 計(jì)劃完成時(shí)刻 5 7 10 14 22 31 交貨延期 0 0 0 0 0 0 平均流程時(shí)間 F= 2/1/2023 72 現(xiàn)有一個(gè) n/2/F/Fmax (n個(gè)工件， 2臺設(shè)備，流水作業(yè)排序問題，使最長流程時(shí)間最短 )問題。 ］ （ 2）計(jì)算全部生產(chǎn)任務(wù)的總流程時(shí)間 F總 = Fmax = max{Fi}= F5 =?Pi =P4 + P3 + P6 +P2+P1 + P5 =31 （ 3）找出初步方案中預(yù)定交貨期大于 Fmax 的工件 (可能有多件 )，并按SPT規(guī)則，把其中加工時(shí)間最長的工件排在最后加工。平均流程時(shí)間 F= (三 ) 優(yōu)先調(diào)度法則例題 (此為單臺設(shè)備排序問題例題 ) EDD規(guī)則 (最早預(yù)定交貨規(guī)則 )例題 解：根據(jù) EDD法則是將完工期限最緊的工序優(yōu)先按排，為此 采用 表 1112把 交貨期短的工件先按排，再求出流程時(shí)間與交貨期相比較，檢查是否存在有延遲時(shí)間的工件，延遲時(shí)間是多少，是否可以在排序上再進(jìn)行調(diào)整。解： 2 5 9 14 22 31 2 3 4 5 8 9 1 6 F = ?(2+5+9+14+22+31)= 工 件 號 J3 J6 J1 J4 J2 J5 交貨期 di 8 13 24 6 23 32 流程時(shí)間 Fi=Ci 2 5 9 14 22 31 延期交貨 Li 6 8 15 8 1 1 由求解過程可知，按 SPT法則排序順序?yàn)椋?J3， J6， J1， J4， J2， J5； 流程時(shí)間分別為： 2， 5 ， 9 ， 14 ， 22， 31； F=；工件 J4 延期交貨 8個(gè)時(shí)間單位。 4. 將確定的工序 Oj放入 ? St } ，從 ? Ot }中消去 Oj ，并將 Oj的緊后工序放入 ? Ot } ，使 t=t+1。 此時(shí)只剩下 （ 2, 3, 2）， ? 將 （ 2, 3, 2）安排在 M2上加工。 可見， T*= 2出現(xiàn)的機(jī)器 M*= M1。 11 ??? kkk TTT 39。 2. 求 T*=min|T’k|,并求出 T*出現(xiàn)的機(jī)器 M*。其中，各工序都按最早可能開始工作的時(shí)間安排作業(yè)計(jì)劃，稱為半能動(dòng)作業(yè)計(jì)劃。 ?????????2,3,21,2,23,1,22,3,13,2,11,1,1D 加工描述矩陣的每一行描述一個(gè)工件的加工過程 (第 1行描述第一個(gè)工件的加工過程，第二行描述第 2個(gè)工件的加工過程 )。 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è)排序是最一般的排序問題，也是最復(fù)雜的一種排序問題。 i = 1,2,3,4； m=1,2,3 工件 i 1 2 3 4 Pi1 1 2 6 3 Pi2 8 4 2 9 Pi3 4 5 8 2 Pi 13 11 16 14 3 1 2 4 2/1/2023 34 解： （ 1）計(jì)算每個(gè)工件的總加工時(shí)間，填寫在表 116上，分別為（ 13,11,16,14），可見總加工時(shí)間最長的工件為 3號工件，總加工時(shí)間 P3=16。 2/1/2023 27 1 3 9 12 9 15 13 24 13 26 18 28 工件 i 設(shè)備工時(shí) 1 2 3 4 Pi1 1 2 6 3 Pi2 8 4 2 9 Pi3 4 5 8 2 表 115 加工時(shí)間矩陣 例 有一個(gè) 4/3/F/Fmax排序問題（即 4個(gè)工件 3臺設(shè)備，流水作業(yè)排序問題，目標(biāo)是使最長流程時(shí)間最短），各個(gè)工件在每臺設(shè)備上的加工時(shí)間如下面的加工時(shí)間矩陣表所示，試采用 Palmer法求解。但對于實(shí)際生產(chǎn)中規(guī)模較大的問題 ,計(jì)算量相當(dāng)大 ,以至連電子計(jì)算機(jī)也無法求解。如對例 (2,5,6,1,4,3) , 若去掉一些工件 , 得到的順序 (5,6,1,4,3)、 (2,6,4,3)、 (2,6,1,4)等仍為余下工件的最優(yōu)順序。以 Ck(si)表示工件 Si 在機(jī)器Mk上的完工時(shí)間 , Psik表示工件 Si 在 Mk上的加工時(shí) 間 , k = 1,2,…, m ； i = 1,2,…, n則 Ck(si)可按以下公式計(jì)算 : C1(si) = C1(si1) + Psi1 Ck(si)