考慮板坯設(shè)計(jì)的組爐優(yōu)化模型

杜 斌，朱 俊，賈樹晉，劉士新

（1.東北大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽110004；2.寶鋼研究院自動(dòng)化所，上海201900）

煉鋼組爐問題屬于煉鋼－連鑄段的生產(chǎn)批量計(jì)劃中的爐次計(jì)劃問題［1－2］.由于工藝原因，計(jì)劃人員必須將不同的合同組織到同一煉鋼爐進(jìn)行生產(chǎn)，爐中合同必須滿足如下幾個(gè)條件：①爐中各合同所采用的鋼級(jí)（steel grade）必須相同；②爐中各合同所采用板坯規(guī)格（厚度、寬度）必須相同，這是下游的連鑄工序約束；③設(shè)爐中某合同總質(zhì)量為X，則必存在某整數(shù)N，使X／N落在合同要求的板坯質(zhì)量上下限范圍內(nèi)；④爐內(nèi)合同總量不得超過煉鋼爐最大生產(chǎn)容量，在煉鋼生產(chǎn)中，若某爐的合同量不滿一爐時(shí)，仍然需要以一爐的量進(jìn)行組織生產(chǎn)，一爐中沒有合同對(duì)應(yīng)的多余產(chǎn)量稱為余材［3］.

組爐優(yōu)化的一般流程如下：首先按照合同要求進(jìn)行板坯規(guī)格設(shè)計(jì)，確定合同所需要的板坯的數(shù)量以及板坯規(guī)格，之后按煉鋼組爐的要求將不同的板坯歸并到一個(gè)煉鋼爐進(jìn)行生產(chǎn)，并確定板坯所選擇的鋼級(jí)（即對(duì)應(yīng)煉鋼爐的鋼級(jí)）.各合同均設(shè)計(jì)有一系列可選擇的鋼級(jí)，分別稱為主鋼級(jí)、副鋼級(jí)，使用主鋼級(jí)的生產(chǎn)成本最低，但有時(shí)候?yàn)闇p少余材的產(chǎn)生，也會(huì)選擇副鋼級(jí)進(jìn)行生產(chǎn)［4］.

對(duì)于組爐優(yōu)化問題，學(xué)者們做了很多研究，其中Tang等［2］研究了煉鋼組爐優(yōu)化與連鑄組澆優(yōu)化問題，該模型考慮了多個(gè)目標(biāo)（數(shù)量級(jí)不同）并通過加權(quán)方法轉(zhuǎn)化為單目標(biāo)，但其權(quán)重系數(shù)的確定是一大難題.黃可為等［3］以板坯為基礎(chǔ)分別建立了不考慮副鋼級(jí)取代成本與考慮副鋼級(jí)取代成本的數(shù)學(xué)模型，給出了基于動(dòng)態(tài)規(guī)劃算法的求解方案.朱俊等［4］則以合同為基礎(chǔ)建立了多目標(biāo)混合規(guī)劃數(shù)學(xué)模型，并給出了結(jié)合PBIL（population－based incremental learning）算法與網(wǎng)絡(luò)最大流算法的求解方案，該方法未考慮板坯質(zhì)量限制.唐立新等［5］同樣從板坯出發(fā)，給出了綜合考慮交貨期與鋼級(jí)取代成本的對(duì)應(yīng)模型，并給出了基于遺傳算法求解方案.本文從合同出發(fā)，同時(shí)考慮板坯設(shè)計(jì)［6－7］的合理性，建立統(tǒng)一的多目標(biāo)混合整數(shù)規(guī)劃模型，并結(jié)合匹配算法、網(wǎng)絡(luò)最大流算法以及裝箱算法設(shè)計(jì)出一套啟發(fā)式算法.試驗(yàn)分析表明，該算法能快速找到組爐優(yōu)化問題的較優(yōu)解，適合現(xiàn)場(chǎng)應(yīng)用.

1 優(yōu)化模型

煉鋼組爐問題可描述為：有M個(gè)規(guī)格要求相同且屬于同一鋼級(jí)序列的合同O＝｛o1，o2，…，oi，…，oM｝，鋼級(jí)序列為G＝｛g1，g2，…，gk｝，合同oi所允許的鋼級(jí)集合為Gi，Gi?G，其中一個(gè)鋼級(jí)為主鋼級(jí)，其余為副鋼級(jí)，訂貨量為mi，最少供貨量為mi，min，最大供貨量為mi，max，合同要求板坯最小質(zhì)量Ui，min，最大質(zhì)量為Ui，max，i＝1，2，…，I.煉鋼爐每爐最多煉鋼質(zhì)量為Mmax，最少煉鋼質(zhì)量為Mmin，若某爐煉鋼質(zhì)量在Mmin～Mmax范圍內(nèi)，則認(rèn)為余材量為零.要求合理組織爐次，使煉鋼余材量最少，并盡量減少副鋼級(jí)的使用.

為方便建模，現(xiàn)假設(shè)至多需要J個(gè)空爐，各爐具有唯一的冶煉鋼級(jí)屬性，即若某合同歸并到某爐進(jìn)行冶煉則必須按照該爐的冶煉鋼級(jí)進(jìn)行生產(chǎn).設(shè)各合同采用不同爐次進(jìn)行冶煉的單位代價(jià)成本為cij，i＝1，2，…，I，j＝1，2，…，J，若合同i不能采用爐j進(jìn)行生產(chǎn)，則cij＝＋∞.據(jù)此，建立以下混合整數(shù)規(guī)劃數(shù)學(xué)模型：

式中：xij為第i個(gè)合同匹配到第j個(gè)爐的鋼的質(zhì)量；Mj為中間決策變量，表示第j爐的煉鋼質(zhì)量，當(dāng)lj＝0時(shí)Mj＝0，當(dāng)lj＝1時(shí)Mmin）；T為某極大常數(shù)；lj為變量，標(biāo)志第j爐的使用情況，若有合同采用該爐進(jìn)行冶煉，則為1，否則為0；Nij為第i個(gè)合同在第j爐中的板坯數(shù).

該模型共有2個(gè)目標(biāo)，分別是：目標(biāo)1副鋼級(jí)成本最低，目標(biāo)2煉鋼總余材量最少.

各約束式含義如下：式（3）表示合同生產(chǎn)量在其供貨公差上下限內(nèi)；式（4）～（7）表示若某爐生產(chǎn)量大于零，則Mmin），否則lj＝0，Mj＝0；式（8）、式（9）表示板坯的單重約束；式（10）為lj的變量約束.

上述模型是一個(gè)多目標(biāo)優(yōu)化模型，在實(shí)際生產(chǎn)中這2個(gè)目標(biāo)的優(yōu)先級(jí)不同，一般來說成本的優(yōu)先級(jí)高于余材，主要是因?yàn)橛嗖目梢酝ㄟ^余材充當(dāng)?shù)确绞竭M(jìn)行消耗，而高的生產(chǎn)成本則難以通過其他方法挽回.

若不考慮鋼級(jí)約束，則該問題可轉(zhuǎn)化為使余材量最少的單目標(biāo)優(yōu)化問題，為Bin－packing問題的一種特殊形式.由于Bin－packing問題屬于NP－h(huán)ard問題［8－9］，故本問題也為NP－h(huán)ard問題.

2 一種基于匹配的啟發(fā)式算法

求解NP－h(huán)ard問題的常用算法主要包括遺傳算法、精確算法（小規(guī)模問題）以及啟發(fā)式算法等.由于啟發(fā)式算法具有計(jì)算速度快、靈活性強(qiáng)、可借鑒現(xiàn)場(chǎng)經(jīng)驗(yàn)等優(yōu)點(diǎn)，因此從工業(yè)應(yīng)用角度來講應(yīng)用最廣.基于此本文設(shè)計(jì)了一種基于最大匹配原理、裝箱算法及網(wǎng)絡(luò)最大流的啟發(fā)式算法.算法流程如圖1所示，其中非二分圖匹配算法用于確定爐次；二分圖算法與裝箱算法用于將剩余合同匹配到已有的爐次中；網(wǎng)絡(luò)最大流算法用于調(diào)整爐次中合同對(duì)應(yīng)的板坯質(zhì)量，以減少余材量；最后過濾篩選掉余材量過大的爐次.

步驟1：非二分圖匹配.對(duì)于給定的合同，可按照以下方法構(gòu)造一個(gè)合同兼容性圖G＝（V，E）：對(duì)于每個(gè)合同oi，存在一個(gè)節(jié)點(diǎn)vi∈V.如果2個(gè)合同oi，oj可以組成一爐（屬于同一鋼級(jí)序列），則增加邊e＝（vi，vj），合同oi，oj的匹配量可通過求解以下混合規(guī)劃問題得到.

其中：xi，xj為合同oi，oj的質(zhì)量；ni，nj為合同oi，oj的板坯數(shù).e＝（vi，vj）的權(quán)重wij代表2個(gè)合同oi，oj的匹配度，即oi，oj在一爐中冶煉的代價(jià)，代價(jià)越小越好.假設(shè)合同oi的鋼級(jí)優(yōu)于oj，那么oi，oj組成的爐次必須按照oi的鋼級(jí)生產(chǎn)，反之，則爐次須按照oj的鋼級(jí)生產(chǎn)，生產(chǎn)中稱之為“以優(yōu)充次”.設(shè)cij表示合同oi，oj組成一爐的單位代價(jià)，則令，若oi的鋼級(jí)優(yōu)于oj，那么wij＝c′ijxj，否則wij＝

圖1 基于匹配的啟發(fā)式算法Fig.1 A matching－based heuristic

如圖2所示，非二分圖G的最大權(quán)重匹配M意味著：①匹配的合同oi，oj是兼容的，即可以組成一爐；②每個(gè)合同最多只能出現(xiàn)在一爐中；③匹配的總權(quán)重最大.通過非二分圖匹配算法［7］可以獲得G的最大權(quán)重匹配M，得到｜M｜個(gè)初始爐次.如果總匹配等于零，結(jié)束程序，否則，轉(zhuǎn)步驟2.

圖2 由合同之間構(gòu)成的最大權(quán)重匹配非二分圖Fig.2 Maximum weight non－bipartite matching between orders

步驟2：二分圖匹配.該步驟循環(huán)地構(gòu)建一個(gè)以剩余合同與爐次為節(jié)點(diǎn)的二分圖并尋找其最大權(quán)重二分圖匹配［10］，算法步驟如下：①根據(jù)步驟1得到的結(jié)果，令Ri表示合同oi的剩余質(zhì)量，Rj表示爐次j的剩余質(zhì)量；②以剩余合同與已有爐次為節(jié)點(diǎn)，構(gòu)造一個(gè)如圖3所示的二分圖G，左側(cè)節(jié)點(diǎn)為剩余合同oi，右側(cè)節(jié)點(diǎn)為構(gòu)造的爐次fj.如果合同合同i與爐次j兼容，則增加一條邊e＝（i，j），匹配重量為wij.③令Rij＝min｛Ri，Rj｝，對(duì)于合同i與爐次j，令合同i匹配到爐次j中的板坯數(shù)為板坯尺寸為的權(quán)重為wij＝c′ij·Rij.④在G中尋找一個(gè)最大加權(quán)二分匹配，如果總的匹配為零，則轉(zhuǎn)步驟3；否則，將Rij質(zhì)量的合同i匹配到第j個(gè)爐次中，且令Ri＝Ri－Rij，Rj＝Rj－Rij，轉(zhuǎn)回步驟2繼續(xù)執(zhí)行.

圖3 由合同與爐次構(gòu)成的權(quán)重匹配二分圖Fig.3 Weighted bipartite matching between order and furnace

步驟3：裝箱算法.該步驟模擬一維裝箱過程，將之前所獲得的爐子視為箱子，以剩余合同物件進(jìn)行裝箱.步驟為，①根據(jù)步驟2得到的結(jié)果將剩余合同oi劃分成質(zhì)量為Ui，min的板坯.②采用Best－Fit算法進(jìn)行裝箱，具體步驟為令i＝l；對(duì)合同oi，依次從當(dāng)前可用爐次集合中尋找一個(gè)成本最低的爐次，即爐次鋼級(jí)屬于板坯主副鋼級(jí)之一，且爐次剩余質(zhì)量Rj大于合同剩余質(zhì)量；令i＝i＋1，如果i＜I，重復(fù)以上操作；否則算法終止.

步驟4：調(diào)整板坯質(zhì)量.本步驟通過增加板坯大

小來進(jìn)一步減少余材.由于步驟2、步驟3板坯并不是依據(jù)最大坯重進(jìn)行設(shè)計(jì)，故存在一定的調(diào)整空間.算法步驟為，①統(tǒng)計(jì)之前各合同所匹配的板坯數(shù)Pnumber，i以及匹配質(zhì)量Wappweight，i；②構(gòu) 建 最 大 流 網(wǎng)絡(luò)［11］如圖4所示.該網(wǎng)絡(luò)為4層有向網(wǎng)絡(luò)，輸入層僅含一個(gè)輸入節(jié)點(diǎn)，且與合同層所有節(jié)點(diǎn)相連，輸出層僅含一個(gè)輸出節(jié)點(diǎn)，爐次層所有節(jié)點(diǎn)均與輸出節(jié)點(diǎn)相連.合同層由所有在之前步驟中參與匹配且未完成的合同組成，每一個(gè)節(jié)點(diǎn)代表一個(gè)合同.爐次層由步驟1中產(chǎn)生的爐子組成，每一個(gè)節(jié)點(diǎn)代表一個(gè)爐次.若某合同oi有板坯匹配到某爐子fj，則該合同對(duì)應(yīng)節(jié)點(diǎn)與爐子對(duì)應(yīng)節(jié)點(diǎn)相連.③設(shè)定網(wǎng)絡(luò)中各爐容量.輸入節(jié)點(diǎn)到第i個(gè)合同節(jié)點(diǎn)的弧的容量為Pnumber，i·Uimax－Wappweight，i；所有爐子節(jié)點(diǎn)到輸出節(jié)點(diǎn)的弧容量為剩余爐容量Rj；設(shè)第i個(gè)合同匹配到第j個(gè)爐子的質(zhì)量為Wappweight，ij，板坯數(shù)Pnumber，i，則第i個(gè)合同節(jié)點(diǎn)匹配到第j個(gè)爐子節(jié)點(diǎn)的弧的容量為Pnumber，ij·Uimax－Wappweight，ij；④通過計(jì)算網(wǎng)絡(luò)最大流，若第i個(gè)合同節(jié)點(diǎn)匹配到第j個(gè)爐子節(jié)點(diǎn)的弧的容量大于Wappweight，ij，則可增加板坯質(zhì)量.然后轉(zhuǎn)步驟5.

圖4 最大流網(wǎng)絡(luò)Fig.4 Maximum flow network

步驟5：過濾篩選.依次檢查匹配好的各爐，若某爐的余材量超過設(shè)定閥值，則將該爐內(nèi)板坯重新放回合同，拋棄該爐，返回步驟1.考慮到算法的收斂，算法過程中對(duì)閥值進(jìn)行動(dòng)態(tài)調(diào)整，逐步增大閥值.

3 實(shí)例計(jì)算

現(xiàn)以某鋼廠實(shí)際生產(chǎn)數(shù)據(jù)為例，如表1 所示共有13個(gè)合同，以第1 個(gè)合同為例，若采用主鋼種1生產(chǎn)，則其額外單位質(zhì)量成本為零，若采用副鋼種3生產(chǎn)，則其額外單位質(zhì)量成本為4.煉鋼爐的容量上下限分別為290t與310t.

啟發(fā)式算法采用C＋＋編程實(shí)現(xiàn)，在CPU 2.20 GHz、內(nèi)存1GB 的配置下可在2s內(nèi)運(yùn)算得到表2所示結(jié)果.表中第5列表示該爐的合同構(gòu)成，如第1個(gè)爐次“1（28.5，2），2（261.5，17）”表示該爐中包含第1個(gè)合同28.5t共計(jì)2塊板坯、第2個(gè)合同261.5 t共計(jì)17塊板坯.從表2可知，第3，4，5，11，12爐中存在余材，共計(jì)400t，第9爐中合同8采用副鋼種生產(chǎn)，共13t，額外生產(chǎn)成本為26.

表1 合同信息Tab.1 Order information

表2 啟發(fā)式算法得到的組爐優(yōu)化結(jié)果Tab.2 Charge optimization results by using heuristic method

目前，現(xiàn)場(chǎng)較多采用的是基于規(guī)則的人工經(jīng)驗(yàn)方法，原理如下：

（1）對(duì)所有合同以主鋼級(jí)分類并以每類的主鋼級(jí)進(jìn)行組爐.如主鋼級(jí)Gi類總質(zhì)量為wi，則可組成［wi／W］爐，其中，W為一爐最大的生產(chǎn)量，剩余量為Ri.

（2）對(duì)剩余量Ri依可替代鋼級(jí)進(jìn)行合并，盡可能組成1爐，不夠1爐的，仍以1爐生產(chǎn)，多余的為余材.

表3為啟發(fā)式算法與人工經(jīng)驗(yàn)方法的優(yōu)化結(jié)果對(duì)比，從中可以得到以下結(jié)論：

（1）針對(duì)相同的合同，啟發(fā)式算法得到的板坯數(shù)量較少，說明單位板坯質(zhì)量較大，減少了板坯切割次數(shù)和切割損失，提高了生產(chǎn)效率，且有利于產(chǎn)品運(yùn)輸.

（2）啟發(fā)式算法可有效降低爐次數(shù)，減少了冶煉準(zhǔn)備時(shí)間，提高了生產(chǎn)效率.

（3）啟發(fā)式算法得到的組爐方案冶煉成本較低，說明大部分合同采用主鋼級(jí)生產(chǎn)、少數(shù)合同采用“以優(yōu)充次”的副鋼級(jí)生產(chǎn)有效降低了生產(chǎn)成本.

（4）啟發(fā)式算法可有效降低余材量，有利于減少庫存，增加流動(dòng)資金，從而提高經(jīng)濟(jì)效益.

（5）從計(jì)算效率來看，人工經(jīng)驗(yàn)方法可在很短的時(shí)間內(nèi)給出組爐方案，效率較高；啟發(fā)式方法的計(jì)算時(shí)間在秒級(jí)，在實(shí)際生產(chǎn)中完全可以接受.

表3 啟發(fā)式算法與人工經(jīng)驗(yàn)方法的組爐優(yōu)化結(jié)果對(duì)比Tab.3 Comparison of charge optimization results between our method and artificial experience method

從以上分析可知，啟發(fā)式算法在優(yōu)化效果上遠(yuǎn)遠(yuǎn)優(yōu)于人工經(jīng)驗(yàn)方法，在計(jì)算效率方面稍弱于人工經(jīng)驗(yàn)方法，因此本文的方法能在較短的時(shí)間內(nèi)得到好的組爐方案，對(duì)實(shí)際生產(chǎn)有指導(dǎo)意義.

4 結(jié)語

針對(duì)煉鋼組爐計(jì)劃編制問題，從合同出發(fā)，同時(shí)考慮板坯設(shè)計(jì)問題，建立了統(tǒng)一的多目標(biāo)混合整數(shù)規(guī)劃模型，并結(jié)合匹配算法、裝箱算法及網(wǎng)絡(luò)最大流算法設(shè)計(jì)出一套啟發(fā)式算法.通過實(shí)際生產(chǎn)數(shù)據(jù)的仿真研究表明，該算法能在較短的時(shí)間內(nèi)給出合理的組爐方案，在減少余材量的同時(shí)減少了煉鋼生產(chǎn)成本，有利于減少庫存，提高生產(chǎn)效率.

［1］ Smith A，Smith B.Constraint programming approaches to a scheduling problem in steelmaking［C］／／University of Leeds School of Computer studies Research Report Series.Leeds：Leeds School Press，1997：1－10.

［2］ Tang L X，Wang G S.Decision support system for the batching problems of steelmaking and continuous－casting production［J］.Omega，2008，36（6）：976.

［3］ 黃可為，盧克斌，汪定偉.煉鋼組爐問題優(yōu)化模型及其動(dòng)態(tài)規(guī)劃算法［J］.東北大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，27（2）：138.HUANG Kewei， LU Kebin， WANG Dingwei. Dynamic programming algorithm and optimization model of charge design for steel－making［J］.Journal of Northeastern University：Natural Science，2006，27（2）：138.

［4］ 朱俊，賈樹晉，杜斌.基于PBIL與網(wǎng)絡(luò)最大流的組爐算法［J］.東北大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，33（1）：52.ZHU Jun，JIA Shujin，DU Bin.PBIL and maximum－flow based algorithm of charge design problem［J］.Journal of Northeastern University：Natural Science，2012，33（1）：52.

［5］ 唐立新，楊自厚，王夢(mèng)光.煉鋼－連鑄最優(yōu)爐次計(jì)劃模型與算法［J］.東北大學(xué)學(xué)報(bào)：自然科學(xué)版，1996，17（4）：440.TANG Lixin，YANG Zihou，WANG Mengguang.Model and algorithm of furnace charge plan for steelmaking－continuous casting production scheduling［J］.Journal of Northeastern University：Natural Science，1996，17（4）：440.

［6］ Heinz S，Schlechte T，Stephan R，et al.Solving steel mill slab design problems［J］.Constraints，2012，17：39.

［7］ Dawande M，Kalagnanam J，Lee H S，et al.The slab－design problem in the steel industry［J］.Interface，2004，34（3）：215.

［8］ Stawowy A.Evolutionary based heuristic for bin packing problem［J］.Computer ＆Industrial Engineering，2008，55（2）：465.

［9］ Haouari M，Serairi M.Heuristics for the variable sized binpacking problem［J］.Computer ＆ Operations Research，2009，36（10）：2877.

［10］ Kalagnanam J，Dawande M，Trumbo M，et al.The surplus inventory matching problem in the process industry［J］.Operations Research，2000，48（4）：505.

［11］ Ford L R，F(xiàn)ulkerson D R.Maximal flow through a network［J］.Canadian Journal of Mathematics，1956，8（1）：399.