【文章內(nèi)容簡(jiǎn)介】 ? SSI(i,j),j + ? + TSI(i, j),j dSI(i, j) + di i??k j??i?? SI(i,j)??p k， p =1， … ， M 且 k ? p (10) Xij ? 0 i?? j??i (5) Yij ? 0 i?? j??i?? (12) Zij ? 0 i?? j??i?? (13) 這是一個(gè)線性規(guī)劃模型，可用標(biāo)準(zhǔn)線性規(guī)劃程序求解。 模型的求解方法 Step 1. 形成爐次和澆次順序； Step 2. 建立子調(diào)度； Step 3. 形成粗調(diào)度； Step 4. 應(yīng)用以上模型，產(chǎn)生最優(yōu)參考方案； Step 5. 調(diào)整最優(yōu)參考方案，獲得最終方案，如需 要，可重復(fù)步驟 4， 5。 煉鋼－連鑄 生產(chǎn)調(diào)度方法步驟 ? 針對(duì)煉鋼車(chē)間的生產(chǎn)調(diào)度問(wèn)題 ，提煉出新的混合流水車(chē)間帶調(diào)整和清洗時(shí)間的多目標(biāo)批調(diào)度問(wèn)題 。 創(chuàng)建了基于離散時(shí)間區(qū)間的混合整數(shù)規(guī)劃模型 。 針對(duì)求解復(fù)雜性 ， 提出了拉格朗日松弛和動(dòng)態(tài)規(guī)劃混合求解策略 ，能夠獲得問(wèn)題近優(yōu)解 。 ? 相關(guān)工作發(fā)表在 EJOR 和 IJPR 上。 Kovalyov 和 Potts （國(guó)際著名調(diào)度專(zhuān)家）在 EJOR 的論文中將此作為背景進(jìn)行了批調(diào)度理論研究，評(píng)價(jià)為? Tang et al .將其歸結(jié)為一個(gè)在某些階段上具有 并行機(jī)和批處理器的混合調(diào)度模型 ?。 煉鋼階段 精煉階段 連鑄階段 轉(zhuǎn)爐 CF1 轉(zhuǎn)爐 CF2 ?轉(zhuǎn)爐 CFM1 精煉爐 RF1 精煉爐 RF2 精煉爐 RFM2 連鑄機(jī) CC1 連鑄機(jī) CC2 連鑄機(jī) CCM3 煉鋼 連鑄生產(chǎn)調(diào)度 基于離散時(shí)間建模策略的全自動(dòng)煉鋼 連鑄生產(chǎn)調(diào)度優(yōu)化 煉鋼過(guò)程 煉鋼過(guò)程（ SP）由三個(gè)階段組成：煉鋼、精煉、連鑄。每階段包括多臺(tái)并行機(jī)。 煉鋼階段 澆注階段 精煉階段 煉鋼階段 精煉階段 連鑄階段 轉(zhuǎn)爐 CF1 轉(zhuǎn)爐 CF2 轉(zhuǎn)爐 CFM1 精煉爐 RF1 精煉爐 RF2 精煉爐 RFM2 連鑄機(jī) CC1 連鑄機(jī) CC2 連鑄機(jī) CCM3 問(wèn)題特性 此問(wèn)題與一般的混合流水車(chē)間 (HFS)調(diào)度相比具有下列特性： ? 一個(gè)倒班內(nèi)需要調(diào)度的爐次數(shù)目不大。但是，每個(gè)爐次在高溫下包括了至少 100噸的鋼水，需要考慮階段之間運(yùn)輸時(shí)間。 ? 一組爐次（一個(gè)澆次）必須在相同的連鑄機(jī)上作為一組加工，而且在澆注期間，在同組中的爐次之間存在優(yōu)先級(jí)約束。 ? 整個(gè)澆次在連鑄機(jī)上加工前后分別需要調(diào)整時(shí)間和清理時(shí)間，這些時(shí)間不包括在加工時(shí)間之內(nèi)。 ? 在連鑄機(jī)上加工的每一澆次內(nèi)各爐次間的間隔時(shí)間會(huì)帶來(lái)附加成本。 ? 在不同加工階段間的爐次等待時(shí)間不僅造成了溫度的降低，更帶來(lái)了額外的加熱成本。 ? 因?yàn)楣ば蛑g時(shí)間銜接要求苛刻，無(wú)論提前或拖期都會(huì)受到懲罰。 成本函數(shù)和假設(shè) 成本函數(shù)由以下各項(xiàng)組成： ? 斷澆損失懲罰，因?yàn)殚g歇會(huì)降低同一澆次中的各爐次間的獨(dú)立性； ? 由各操作間的等待時(shí)間造成的鋼水溫度降低所帶來(lái)的損失； ? 提前 /拖期懲罰，用以確保爐次中板坯的準(zhǔn)時(shí)性。 HFS調(diào)度中的一般性假設(shè)： ? 所有的爐次遵循同樣的處理路線：煉鋼、精煉、然后連鑄。每個(gè)階段具有多臺(tái)并行同構(gòu)機(jī)，一爐次可以在此階段的任何一臺(tái)機(jī)器上加工； ? 一臺(tái)機(jī)器一次只能加工一個(gè)工件； ? 在任何時(shí)間一個(gè)工件至多只能在一臺(tái)機(jī)器上加工； ? 工件加工無(wú)優(yōu)先權(quán)。 實(shí)際建模過(guò)程中考慮到下述具體特點(diǎn)，以確保調(diào)度的可行性： ? 對(duì)于同一爐次來(lái)說(shuō)兩個(gè)連續(xù)進(jìn)行的操作，只有在前一個(gè)完成的情況下后一個(gè)才能開(kāi)始； ? 對(duì)于在同一臺(tái)機(jī)器上進(jìn)行連續(xù)加工的兩個(gè)爐次，只有當(dāng)前面的爐次加工結(jié)束后，后一個(gè)才能夠開(kāi)始。 參數(shù)： ? ? – 爐次集合， ? = {1, 2, ..., N}, 這里 N 表示生產(chǎn)爐次的總數(shù)； ? ?g – 澆次 g中的爐次集合， g ? {1, 2, ..., M}, 這里 M 表示澆次的總數(shù) 。 ?h ? ?g = ?, 任意 h, g ? {1, ..., M} 且 h ? g 。 ?1 ? ?2 ? ... ? ?M = ? 。 ? Sgp – g 澆次中的 第 p個(gè) 爐次，按批量計(jì)劃對(duì)爐次序列進(jìn)行定義， p = 1, 2, …, | ?g|，這一符號(hào)的使用簡(jiǎn)化了模型的表達(dá)方式； 成本函數(shù)和假設(shè) ? di – 爐次 i 的交貨期。它是一個(gè)時(shí)間點(diǎn)（時(shí)間單位的末端點(diǎn)）； ? C1g – 爐次 g的間歇損失懲罰系數(shù)； ? C2ij – 在第 j 階段完成加工的爐次 i 的等待時(shí)間的懲罰系數(shù)； ? C3i – 爐次 i 提前完工的懲罰系數(shù)； ? C4i – 爐次 i 拖期的懲罰系數(shù)； ? Tij – 爐次 i 在第 j 階段的加工時(shí)間； ? tj,j+1 – 從階段 j 到階段 j+1 的運(yùn)輸時(shí)間； ? Sij – 爐次 i 在第 j 階段的機(jī)器調(diào)整時(shí)間 。 當(dāng) i 是連鑄機(jī)上的第一個(gè)爐次且 j = 3 時(shí) ， 表示連鑄機(jī)上每進(jìn)行一個(gè)澆次所需的調(diào)整時(shí)間 ， 其值大于 0。 對(duì)于其它的 i, j, Sij = 0； 符號(hào) ? Rij – 在第 j 階段完成對(duì)爐次 i 的加工后所需的清理時(shí)間 。 當(dāng) i是連鑄機(jī)上的最后一個(gè)爐次且 j = 3 時(shí) ， 表示連鑄機(jī)上每進(jìn)行一個(gè)澆次所需的清理時(shí)間 ， 其值大于 0。 對(duì)于所有的 i, j, Rij = 0； ? Mjk – 在時(shí)間單位 k 內(nèi)在第 j 階段可使用的機(jī)器數(shù)； ? K – 計(jì)劃水平內(nèi)時(shí)間單位的總數(shù)。 決策變量： ? i ? ?。 j = 1, 2, 3。 k = 1, 2, …, K. ? Cij – 爐次 i 在階段 j 上的完成時(shí)間 , i ? ?。 j = 1, 2, 點(diǎn)（? Cij = k ”指的是操作的完成時(shí)間是時(shí)間單位 k 的末端）。 ????否則加工正在階段內(nèi)爐次如果在時(shí)間單位0 1 jikijk? 符號(hào) min Z ? ? ??????? ??Mg psssgggppgpg CTCC11||133,3, )(1 1,1,? ?? ???? ????Ni jjjijjijiij tCTCC1211,1,1, )(2???? Niiii CdC13 ),0m a x (3 ???? Niiii dCC13 ),0m a x (4Cij + tj,j+1 ? Ci,j+1 – Ti,j+1, i ? ?。 j = 1, 2. 3,3,3 1,1, ?? ?? pgpggp sss TCC , p = 1, 2, … , |?g|1。 g = 1, …, M. ijijijKkijk RST ????? 1? i ? ? 。 j = 1, 2, 3. k?ijk ? Cij + Rij, i ? ?。 j = 1, 2, 3。 k = 1, …, K. Cij – Tij – Sij +1? k + K(1?ijk), i ? ?。 j = 1, 2, 3。 k = 1, … , K. . (1) (2) (3) (4) (5) (6) 數(shù)學(xué)模型 ? Mjk , j = 1, 2, 3。 k = 1, …, K. ?ijk ? {0, 1}, i ? ? 。 j =1, 2, 3。 k = 1, …, K. Cij ?{1, 2, …, K}, i ? ? 。 j = 1, 2, 3. (8) (7) (9) ???i ijk? (1)中的每一項(xiàng)代表一種成本 。 約束 (2)定義了爐次在各個(gè)階段的操作優(yōu)先級(jí) ， 從而確保了一個(gè)爐次不可能在同一時(shí)間出現(xiàn)在不同的階段 。 約束 (3)定義了連鑄機(jī)上同一澆次內(nèi)的所有爐次的優(yōu)先級(jí)關(guān)系 。 約束 (4)對(duì)每個(gè)階段機(jī)器上的所有工件加上了總體時(shí)間要求 ， 包括調(diào)整和清理時(shí)間（ 如果需要 ） 。 約束 (5)和 (6)定義了每個(gè)爐次在各個(gè)階段的機(jī)器上所占用的時(shí)間區(qū)間 。 與約束 (4)聯(lián)合在一起 ， 它們描述對(duì)于所需的連續(xù)時(shí)間區(qū)間 ， 每個(gè)階段機(jī)器上的爐次的要求 。 約束 (7)是機(jī)器能力約束 ， (8)和 (9)定義了變量的取值范圍 。 數(shù)學(xué)模型 問(wèn)題的松弛和分解 約束 (3)和 (7)耦合不同的工件 ,因此將它們松弛 ,得到松弛問(wèn)題 ： ? ?? ?? ? ?? ??Mg p sssgg gppgpg CTCC1 1|| 1 33,3, )(1 1,1,? ?? ? ??????? Ni j jjijjijiijtCTCC121 1,1,1,)(2?? ?? Ni iii CdC1 3 ),0m a x (3 ?? ?? Ni iii dCC1 3 ),0m a x (4? ????? ????? Mg pssssgpgpggpgp TCCu11||13,3,3 )( 1,1,? ? ?? ? ?? ??Kk j i jkijkjkMv131)( ?gpsumin ZLR ? + 滿(mǎn)足約束 (), (), (), (), (), ()，且 ? 0, p = 1, 2, …, | ?g|1。 g = 1, …, M. vjk ? 0, j = 1, 2, 3。 k = 1, …, K. (10) (11) (12) (LR) 對(duì)于給定的 {ui}和 {vjk}值，松弛問(wèn)題可分解為針對(duì)每個(gè)工件的子問(wèn)題，工件 i（ i? ?）的子問(wèn)題是： (LRi) ????? ???211,1,1, )(2jjjijjijiij tCTCC? ?? ?? Kk jijkjkv131?min ZLR(i) ? + C3i max(0, di Ci3) + C4i max(0, Ci3 di) + ?(i) (13) 滿(mǎn)足約束 (2), (4), (5), (6), (8), (9)，這里 i對(duì)于第 i個(gè)子問(wèn)題是固定的， ?(i) 是根據(jù) i 的值定義的，如下： ?(i) ? 3)1( gpgp sgs CCu ?, for sgp = i and p = 1. (14) ?(i) ? ))(1()1( 3331 gpgpgpgpgp sssgsgs TCuCCCu ???? ? for sgp = i and p = 2, … , |?g|1. ?(i) ? ))(1(331, gpgppg sssg TCuC ?? ?, for sgp = i and p = |?g|. (15) (16) 問(wèn)題的松弛和分解 利用反向動(dòng)態(tài)規(guī)劃 (DP)求解子問(wèn)題 。 DP階段對(duì)應(yīng)著 SP生產(chǎn)階段 ，并且每一階段的狀態(tài)對(duì)應(yīng)著那個(gè)階段可能的工件 (爐次 )開(kāi)始時(shí)間 。 煉鋼 精煉 連鑄第 1 階段 第 2 階段 第 3 階段 子問(wèn)題的動(dòng)態(tài)規(guī)劃 (LRi) 各個(gè)階段節(jié)點(diǎn)費(fèi)用 ： 最后（第三個(gè)）階段上節(jié)點(diǎn) i 的費(fèi)用： Vi3(Ci3, ?i3k) = C2i2(Ci3 – Ti3) + C3i max(0, di Ci3) + C4i max(0, Ci3 di) + + ?(i)