【正文】 所謂“延遲”是指工件等待加工時，機(jī)器出現(xiàn)空閑 ( 即使這段空閑時間不足以完成一道工序的加工 )。對這類作業(yè)排序問題，可以用分支定界法或整數(shù)規(guī)劃法求最優(yōu)解。 第三節(jié) 單件作業(yè)排序問題 2/2/2023 51 第三節(jié) 單件作業(yè)排序問題 一、問題的描述 對一般的單件作業(yè)排序問題，每個工件都有其獨(dú)特的加工路線，工件沒有一定的流向。 工件 i 設(shè)備工時 2 3 1 4 Pi1 2 6 1 3 Pi2 4 2 8 9 Pi3 5 8 4 2 第二節(jié) 流水作業(yè)排序問題 2 2/2/2023 40 P322習(xí)題 2：請用 CDS法排序并計算最長流程時間 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)鍵工件法求解過程如下： 2/2/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時： 2/2/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/2/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時： 2/2/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 2 3 1 5 14 19 6 9 21 27 10 15 27 30 16 23 29 33 Fmax=33 2/2/2023 45 排序?yàn)椋?S1=（ 1， 4， 2 ， 3 ） i 1 2 3 4 L=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時： 2/2/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 ）滿意解。其步驟如下 : (1)計算每個工件的總加工時間 P i= ∑ Pij, 找出總加工時間最長的工件 C(j=1. 2. 3.…… m), 將其作為關(guān)鍵工件。 為了解決生產(chǎn)實(shí)際中的排序問題 ,人們提出了各種啟發(fā)式算法。不符合這個法則的加工順序 ,也可能是最優(yōu)順序。 (2) 若最短的加工時間出現(xiàn)在 M1上 ,則對應(yīng)的工件盡可能往前排；若最短加工時間出現(xiàn)在 M2上，則對應(yīng)工件盡可能往后排。 第二節(jié) 流水作業(yè)排序問題 2/2/2023 16 一、最長流程時間 Fmax的計算 最長流程時間就是工件在車間實(shí)際停留的最長時間。 一般說來 ,對于流水作業(yè)排序問題 , 工件在不同機(jī)器上的加工順序不盡一致。 當(dāng) Li 0 時為正延遲 , 即 Ji 的實(shí)際完工時間超過了完工期限 。例如， n / 3 / P / Cmax 表示 n 個工件經(jīng) 3臺機(jī)器加工的流水作業(yè)排列排序問題，目標(biāo)函數(shù)是使最長完工時間最短。 現(xiàn)只討論幾種有代表性的排序問題。 第一節(jié) 作業(yè)排序的基本概念 二、假設(shè)條件與符號說明 為了便于采用數(shù)學(xué)模型來分析研究排序問題，做下列假設(shè)： 2/2/2023 6 第一節(jié) 作業(yè)排序的基本概念 符號說明 Wi = ∑ m j=1 Wij ? Ji —— 第 i 工件， i = 1,2,…,n ； ? Mj —— 第 j 臺機(jī)器， j =1,2,…, m； (i , j, k) —— Ji 的第 j 道工序在 Mk上進(jìn)行； Pi = ∑ m j=1 Pij Pij —— Ji 在 Mj上的 加工時間， Ji加工完的總加工時間； ri—— Ji 到達(dá)工序時間 ，即可以開始加工的最早時間； di —— Ji 的 完工期限 ； ai—— Ji 在 車間允許停留的時間 （ Ji 進(jìn)入車間到完工時刻之間的時間間隔： ai = di － ri）； Wij —— Ji 在第 j 道 工序前的等待時間 ， Ji 總的等待時間： 2/2/2023 7 Ci = ri +∑( Pij + Wij ) = ri + Pi + Wi Li = Ci － di = ri + Pi + Wi － di = (Pi + Wi ) － (di － ri ) = Fi － ai Fi = Ci － ri = Pi + Wi 。 ? 機(jī)器 —— 服務(wù)者 ? 工件 —— 服務(wù)對象 ? 加工路線 —— 工件加工的工藝過程 ? 工序 —— 加工路線上的每一個具體工作地（機(jī)器）。 在編制生產(chǎn)作業(yè)計劃時常常出現(xiàn)一個工件在某道工序加工完之后，加工它的下一道工序的機(jī)器還在加工前一個工件，這時該工件不得不等待一段時間才能開始在下一道工序的機(jī)器上加工。編制車間生產(chǎn)作業(yè)計劃，應(yīng)該解決工件加工順序問題。這種情況稱為“機(jī)器空閑”。 3. 不允許中斷。 Li —— Ji 工件的延遲時間， 2/2/2023 8 第一節(jié) 作業(yè)排序的基本概念 當(dāng) Li 0 時為正延遲 , 即 Ji 的實(shí)際完工時間超過了完工期限 。這 4個參數(shù)通常表示為： n / m /A / B。 ? n 為工件數(shù)； m 為機(jī)器數(shù) ? B 為目標(biāo)函數(shù) ,通常是使其值最小 ? A 為車間類型，通常有以下幾種情況，在 A的位置： (1) 若標(biāo)以“ F” ,則代表流水作業(yè)排序問題。 例如： n / 3 / P / Cmax 表示 n 個工件經(jīng) 3臺機(jī)器加工的流水作業(yè)排列排序問題，目標(biāo)函數(shù)是使最長完工時間最短。流水作業(yè)排列排序問題常被稱作 同順序 排序問題。由于假設(shè)所有工件的到達(dá)時間都為零(r = 0， i = 1,2,…, n),所以 Fmax等于排在末位加工的工件在車間的停留時間 ,也等于一批工件的最長完工時間 Cmax。 (3) 若所有工件都已排序 , 停止 .否則 , 轉(zhuǎn)步驟 (1). 第二節(jié) 流水作業(yè)排序問題 二、 n/2/F/Fmax問題的最優(yōu)算法 2/2/2023 21 第二節(jié) 流水作業(yè)排序問題 二、 n/2/F/Fmax問題的最優(yōu)算法 例 1１ ３所示的 6/２ /Ｆ /Fmax問題的最優(yōu)解。對于一般的流水車間排列排序問題 ,可以用分支定界法。 2/2/2023 26 第二節(jié) 流水作業(yè)排序問題 (一 ) 帕爾姆 ( Palmer)法 1965年 ,。 第二節(jié) 流水作業(yè)排序問題 2/2/2023 33 表 11 6 工件在每臺設(shè)備上的單件工時與總工時 (見教材 305頁 ) 第二節(jié) 流水作業(yè)排序問題 例：有 4個工件，在 3臺設(shè)備上加工，每個工件在每臺設(shè)備上加工的單件工時消耗如表 116所示。 ② 計算 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è)排序。所以，可以用加工描述矩陣的形式來描述所有工件的加工。為了對研究啟發(fā)式算法有所幫助，先介紹兩種十分重要的作業(yè)計劃及其構(gòu)成方法。 設(shè) ： ? St } — 為第 t 步之前已排序工序構(gòu)成的部分作業(yè)計劃； ? Ot } — 為第 t 步可以排序的工序集合； Tk — 為 ? Ot }中工序 Ok 的最早可能開工時間； T?k — 為 ? Ot } 中工序 Ok的最早可能完工時間。 P310 ? 按表 11~9 所示的能動作業(yè)計劃構(gòu)成過程，可繪出圖 11~4能動作業(yè)計劃時間安排 (排序 )圖 — 能動作業(yè)計劃。k = T180。 （ 5） …… （略） （ 6）當(dāng) t=6 時， ? O6 } = ? （ 2, 3, 2） }， T6=8， T180。如果 M*有多臺，則任選一臺。 例：現(xiàn)有一個 6/1/F問題，其加工時間與交貨期如表1110所示，試采用 SPT法則進(jìn)行作業(yè)排序。 表 1110 加工時間與交貨期 例： (仍采用上例 )有一個 6/1/Lmax問題 (即 6個工件， 1臺機(jī)器，使最大延遲時間最小 )，其加工時間與交貨期如表 1110所示。例如表 1110的例子，可按交貨期最短的先安排加工 (即根據(jù)交貨期排序 )。 表 1113 余下工件的 F與預(yù)訂交貨期 5 7 10 18 22 2/2/2023 71 反復(fù)進(jìn)行（ 2）、（ 3）步，直到實(shí)現(xiàn)既使 Lmax ≦ 0，又使 F (平均流程時間 )為 Fmin的排序方案為止。 J4 J1 J5 J2 J6 J3 J7 3 6 7 8 11 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法排序。顯然，這是一個非流水作業(yè)排序問題，是一個一般的排序問題，故可用2/4/G/Fmax表示，也可用 2/4/G/Cmax表示。例如 A點(diǎn) (6,6)，表示 J1在 M1上加工早已完畢，正在 M2上加工； J2 在 M4上加工剛好完畢，正準(zhǔn)備進(jìn)入 M2上加工，但由于 M2正在加工 J1， 所以，又等了 1個單位時間到 B點(diǎn) (7,6) ，此時， M2剛好加工完 J1。從作圖求解過程可知： J1工件沒有等待時間，F(xiàn)1max =12； J2 加工等待時間為 1，所以，F(xiàn)2max =17。 1,1,1 2, 3,1 1, 2, 2 2, 2, 2 1, 3, 3