賈樹晉，李維剛，杜 斌

(寶鋼集團(tuán)中央研究院自動化研究所，上海，201900)

熱軋軋制計劃的多目標(biāo)優(yōu)化模型及算法

賈樹晉，李維剛，杜 斌

(寶鋼集團(tuán)中央研究院自動化研究所，上海，201900)

針對熱軋軋制計劃優(yōu)化問題，建立基于獎金收集車輛路徑問題(PCVRP)的多目標(biāo)優(yōu)化模型，其中包含兩個目標(biāo)：目標(biāo)1為最小化相鄰板坯的寬度、厚度與硬度的跳躍懲罰；目標(biāo)2為最大化收集的獎金，即使得盡可能多的板坯編入軋制計劃。在此基礎(chǔ)上，提出一種基于Pareto最優(yōu)的多目標(biāo)蟻群系統(tǒng)算法(MOACS)，避免了傳統(tǒng)加權(quán)法需要確定目標(biāo)權(quán)重系數(shù)的缺點，一次運行可產(chǎn)生多個Pareto最優(yōu)解，給決策者帶來了更大的決策自由度。現(xiàn)場數(shù)據(jù)測試表明該算法具有良好的優(yōu)化性能和實用性。

熱軋軋制計劃；多目標(biāo)優(yōu)化；Pareto最優(yōu)；蟻群算法

熱軋是現(xiàn)代鋼鐵生產(chǎn)中的一個重要工序。當(dāng)前，用戶對鋼鐵產(chǎn)品的需求日趨小批量、多品種，這對鋼鐵企業(yè)的生產(chǎn)組織提出了更高的要求。熱軋生產(chǎn)組織的關(guān)鍵和核心是熱軋軋制計劃的制訂，即根據(jù)生產(chǎn)條件、用戶需求及軋制規(guī)程，合理安排待生產(chǎn)板坯的加工順序。執(zhí)行一個合理有效的熱軋軋制計劃，能提高產(chǎn)品質(zhì)量與生產(chǎn)效率，降低能耗和生產(chǎn)成本，提升鋼鐵企業(yè)的競爭力。然而，由于生產(chǎn)中涉及大量復(fù)雜的約束，熱軋軋制計劃被認(rèn)為是鋼鐵生產(chǎn)計劃與調(diào)度中最復(fù)雜和難解的問題之一。

鑒于熱軋軋制計劃優(yōu)化問題的重要性，國內(nèi)外學(xué)者進(jìn)行了大量的研究。根據(jù)建立的模型類型，這些研究可分為旅行商問題(Travelling Salesman Problem, TSP)模型、車輛路徑問題(Vehicle Routing Problem,VRP)模型及其變種。Lopez等[1]提出了一種獎金收集旅行商模型(PCTSP)，并利用基于禁忌搜索和“Cannibalization”概念的啟發(fā)式算法來求解，得到了較好的結(jié)果。但這個模型是針對軋制單元計劃提出的，每次只考慮一個軋制單元的編制，本質(zhì)上說是一種串行策略。鑒于這種情況，隨后發(fā)表的文獻(xiàn)將研究重點放在并行策略的研究上。Tang等[2]提出了著名的多旅行商模型(MTSP)，采用并行策略同時生成多個軋制單元，并通過改進(jìn)的遺傳算法進(jìn)行了求解，然而這個模型未能包含軋制單元的能力約束。黃可為等[3]建立了MTSP模型，從實際應(yīng)用的角度描述了基于模型的熱軋計劃排程系統(tǒng)的建立和開發(fā)實現(xiàn)技術(shù)。李耀華等[4]建立了不確定軋制計劃數(shù)的VRP模型，該模型考慮了軋制單元中燙輥材和主體材的合理安排，并構(gòu)造出一種基于單親遺傳算子的免疫算法求解此模型。賈佳等[5]建立了單一、混合軋制計劃類型的主體材計劃VRP模型，提出了軋制計劃類型最小區(qū)間編制規(guī)則，并采用專家經(jīng)驗實現(xiàn)了計劃協(xié)調(diào)，經(jīng)測試表明該方法提高了批量計劃的組批數(shù)量、軋制效率和組批質(zhì)量。Liu[6]將熱軋批量計劃優(yōu)化問題歸結(jié)為多目標(biāo)獎金收集車輛路徑問題(Prize Collecting Vehicle Routing Problem, PCVRP)模型，并通過加權(quán)法將多目標(biāo)優(yōu)化模型轉(zhuǎn)化為單目標(biāo)優(yōu)化模型，使用基于分解-協(xié)調(diào)的蟻群算法進(jìn)行了優(yōu)化求解。筆者等考慮了板坯表面等級約束、熱裝熱送等約束,建立了一種帶雙時間窗的車輛路徑問題(VRPDTW)模型，并根據(jù)優(yōu)化目標(biāo)的優(yōu)先級，提出了一種基于分解的分層遞階優(yōu)化算法[7]。除TSP模型和VRP模型外，也有部分學(xué)者嘗試建立不同的模型。Pan等[8]建立了一種多目標(biāo)多路徑問題模型，并提出了一種改進(jìn)的列生成算法來編制大規(guī)模的熱軋批量計劃。郭冬芬等[9]建立了熱軋軋制計劃問題的約束滿足模型，并設(shè)計了基于約束滿足和啟發(fā)式的混合求解算法。

熱軋軋制計劃優(yōu)化問題屬于多目標(biāo)優(yōu)化問題，目前的主流求解方法是通過加權(quán)的方式將其轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，然后使用單目標(biāo)優(yōu)化算法進(jìn)行求解。此類方法存在的問題是目標(biāo)權(quán)重系數(shù)一般不易確定，尤其是在目標(biāo)數(shù)量級不一致的情形下。為此，文獻(xiàn)[10]中將熱軋軋制計劃問題歸結(jié)為一種帶能力約束的雙目標(biāo)TSP問題模型，并首次采用基于Pareto最優(yōu)的多目標(biāo)優(yōu)化算法進(jìn)行求解，該方法將所有候選板坯編入軋制計劃，適用于候選板坯數(shù)較少的情形，當(dāng)候選板坯數(shù)較多時，需要較長優(yōu)化時間。因此，本文考慮將部分候選板坯編入軋制計劃的情形，建立基于獎金收集車輛路徑問題(PCVRP)的多目標(biāo)優(yōu)化模型，并根據(jù)模型特點提出一種多目標(biāo)蟻群算法進(jìn)行優(yōu)化。

1 熱軋軋制計劃的數(shù)學(xué)模型

1.1 問題描述

如圖1所示，一個軋制計劃由若干個軋制單元構(gòu)成，一個軋制單元由燙輥材與主體材兩部分組成，在寬度上呈“烏龜殼”結(jié)構(gòu)。燙輥材按照由窄到寬的順序排列，主要用于預(yù)熱軋輥，其數(shù)量一般較少，容易確定，因此本文不對其討論。主體材是軋制單元的主要組成部分，按照由寬到窄的順序排列，以防止在帶鋼表面留下印跡，影響產(chǎn)品質(zhì)量，另外，在板坯排序時還要兼顧相鄰板坯間的厚度、硬度跳躍，使其盡量平滑。

在熱軋過程中，為避免由于軋輥磨損引起產(chǎn)品質(zhì)量問題，工作輥在軋完一個軋制單元后必須更換。由于更換軋輥會導(dǎo)致熱軋生產(chǎn)中斷，且耗時較長，會影響生產(chǎn)效率，因此從產(chǎn)品質(zhì)量與生產(chǎn)效率角度綜合考慮，軋制單元的軋制長度應(yīng)限定在一定范圍內(nèi)。另外，為了避免連續(xù)軋制同一寬度的板坯引起軋輥凹痕，必須對連續(xù)同寬軋制公里數(shù)作一限制。

綜上分析，編制軋制單元時主體材需要滿足以下軋制規(guī)程：①寬度須呈非增變化，且要求變化平滑，跳躍幅度有限制；②硬度變化要平穩(wěn)，遞增或遞減均可，但不能反復(fù)跳躍；③厚度變化要平穩(wěn)，不能反復(fù)跳躍，最好是朝非減方向變化；④連續(xù)同寬軋制公里數(shù)應(yīng)限定在一定范圍內(nèi)；⑤總軋制長度要有一定限制。

因此，熱軋軋制計劃編制可定義為：從候選板坯集中挑選部分板坯，對這些板坯進(jìn)行合理分組(每個分組對應(yīng)一個軋制單元)，然后根據(jù)軋制規(guī)程對軋制單元中的板坯進(jìn)行排序，使得相鄰板坯間的寬度、厚度與硬度的跳躍懲罰最小，同時使盡可能多的板坯被編入軋制計劃。

(a)軋制計劃的結(jié)構(gòu) (b)軋制單元寬度截面

圖1 軋制計劃結(jié)構(gòu)及其軋制單元形狀

Fig.1 Structure of rolling plan and shape of a rolling unit

1.2 數(shù)學(xué)模型

PCVRP可定義為：配送中心有m輛車，每輛車的最大載重量為U，需要為n個客戶配送貨物，客戶i的需求量為qi，與客戶j之間的距離為dij，每個客戶最多被一輛車服務(wù)，如果客戶i被服務(wù)，獲得pi的獎金，否則，得到pi的懲罰。每輛車的起點和終點均為配送中心，要求合理安排每輛車的行車路徑，使得總行駛距離盡可能短，收集到的獎金盡可能多。

在軋制計劃中，令每塊板坯對應(yīng)一個客戶，每個軋制單元對應(yīng)一輛車，客戶的需求對應(yīng)板坯的軋制長度，相鄰板坯間的寬度、厚度與硬度跳躍懲罰對應(yīng)客戶之間的距離，如板坯被編入軋制計劃，得到pi的獎金，否則，得到pi的懲罰。另外，引入編號為0的虛擬板坯，對應(yīng)配送中心，其軋制長度為0，與其他板坯間的跳躍懲罰為0，虛擬板坯必須被編入軋制計劃。這樣，就可將熱軋軋制計劃優(yōu)化問題與PCVRP對應(yīng)起來。

數(shù)學(xué)模型的決策變量定義如下：

wi：板坯i后連續(xù)同寬軋制的累積軋制長度

則熱軋軋制計劃優(yōu)化問題可描述為以下的多目標(biāo)PCVRP模型：

(1)

(2)

s.t.

(3)

(4)

(5)

y0k=1 (k∈M)

(6)

(7)

wj+T(1-sijxijk)≥wi+qj

(i,j∈N{0},k∈M)

(8)

qi≤wi≤R(i∈N{0})

(9)

(10)

(11)

xijk∈{0,1} (i,j∈N,k∈M)

(12)

yik∈{0,1} (i∈N,k∈M)

(13)

其中，目標(biāo)函數(shù)A代表板坯寬度、厚度、硬度與加熱時間跳躍懲罰最?。荒繕?biāo)函數(shù)B代表未被編入軋批的板坯總懲罰最小(即收集的獎金最多)；約束條件(3)表示在第k個軋制單元內(nèi)，板坯j前至多有一塊板坯；約束條件(4)表示在第k個軋制單元內(nèi)，板坯i后至多有一塊板坯；約束條件(5)避免軋制單元內(nèi)出現(xiàn)子回路；約束條件(6)表示虛擬板坯0必須被編入軋制計劃；約束條件(7)表示每塊實物板坯至多被安排到一個軋制單元內(nèi)；約束條件(8)和(9)限制了每個軋制單元內(nèi)最大連續(xù)同寬軋制長度，其中T為一個很大的數(shù)；約束條件(10)和(11)為每個軋制單元的能力約束，限制了最大最小軋制長度；約束條件(12)和(13)表示決策變量 為0-1變量。

2 熱軋軋制計劃的多目標(biāo)優(yōu)化算法

由于PCVRP屬于組合優(yōu)化問題，因此，軋制計劃的PCVRP模型中，當(dāng)板坯數(shù)量較大時，會帶來“組合爆炸”的問題，對其精確求解非常困難。一般對這類問題，可通過啟發(fā)式算法或智能優(yōu)化算法進(jìn)行優(yōu)化求解。另外，對于多目標(biāo)優(yōu)化問題，一般采用加權(quán)法進(jìn)行處理，但軋制計劃模型中的兩個目標(biāo)的量綱不一致，也不在同一數(shù)量級，因此，其目標(biāo)權(quán)重系數(shù)難以合理確定。本文利用基于Pareto最優(yōu)的多目標(biāo)優(yōu)化蟻群算法進(jìn)行求解，以避開確定目標(biāo)權(quán)重系數(shù)這一難題。

在眾多蟻群算法中，蟻群系統(tǒng)(Ant Colony System, ACS)[11]算法是一種最為成功的蟻群算法，但其原始算法只能解決單目標(biāo)優(yōu)化問題，因此，本文在ACS算法的基礎(chǔ)上，根據(jù)軋制計劃模型特點，通過重新設(shè)計狀態(tài)轉(zhuǎn)移策略、信息素更新策略，并引入局部搜索策略與精英保留策略，提出了一種多目標(biāo)蟻群系統(tǒng)(Multi-objective Ant Colony System, MOACS)算法對軋制計劃模型進(jìn)行優(yōu)化求解。

2.1 算法流程

MOACS中，設(shè)置有一個內(nèi)部種群PS和一個外部檔案ES。令L表示內(nèi)部種群PS中的螞蟻個數(shù)，m表示軋制計劃中的軋制單元數(shù)，maxGen表示算法的最大迭代次數(shù)，則MOACS算法的流程如下：

Step 1:令l=1，k=1，Gen=1，初始化信息素矩陣。

Step 2:螞蟻l從虛擬板坯0出發(fā)，從候選板坯集合中選擇最大寬度的板坯作為第k個軋制單元主體材的第1塊板坯。

Step 3:螞蟻l根據(jù)狀態(tài)轉(zhuǎn)移策略在可行板坯集合Fl中選擇下一塊板坯，其中可行板坯集合Fl是指滿足式(3)～式(11)約束條件的所有板坯。若Fl≠?，則返回Step 3繼續(xù)選擇下一塊板坯；若Fl=?，則返回虛擬板坯0，轉(zhuǎn)下一步。

Step 4:令k=k+1，若k≤m，轉(zhuǎn)到Step 2開始下一軋制單元的構(gòu)造；若k>m，按照局部搜索策略以概率PLS對螞蟻l構(gòu)造的路徑(軋制計劃)進(jìn)行局部搜索，以改善解的質(zhì)量。

Step 5:對螞蟻l構(gòu)造的路徑上的信息素濃度進(jìn)行局部更新(信息素更新策略)。

Step 6:令l=l+1，若l≤L，令k=1，轉(zhuǎn)到Step 2開始構(gòu)造下一只螞蟻的路徑；若l>L，說明所有螞蟻均已完成路徑構(gòu)造，轉(zhuǎn)下一步。

Step 7:根據(jù)精英保留策略將內(nèi)部種群PS產(chǎn)生的非支配解更新到外部檔案ES中，并刪除ES中的被支配解。

Step 8:對本次迭代成功進(jìn)入外部檔案ES中的Pareto最優(yōu)解進(jìn)行信息素全局更新(信息素更新策略)。

Step 9:令Gen=Gen+1，若Gen≤maxGen，則令l=1，k=1，返回Step 2繼續(xù)執(zhí)行；若Gen>maxGen，則輸出外部檔案ES中的Pareto最優(yōu)解，結(jié)束程序。

2.2 狀態(tài)轉(zhuǎn)移策略

在每次迭代中，蟻群需要根據(jù)狀態(tài)轉(zhuǎn)移策略來構(gòu)造路徑，其中有兩個重要的參數(shù)：信息素濃度和啟發(fā)式信息。對于處理單目標(biāo)優(yōu)化問題的ACS來說，其信息素矩陣與啟發(fā)式矩陣均只有一個，本文算法選擇兩個信息素矩陣，分別對應(yīng)軋制計劃模型中的兩個目標(biāo)，另外選擇一個啟發(fā)式矩陣，綜合考慮兩個目標(biāo)的啟發(fā)式信息。

在MOACS中，每塊板坯代表一個可能被螞蟻訪問的節(jié)點，位于節(jié)點i處的第l只螞蟻根據(jù)以下狀態(tài)轉(zhuǎn)移策略來選擇下一個節(jié)點s：

(14)

(15)

由式(15)可知，啟發(fā)式信息ηij隨著INj的改變而改變。對于每只螞蟻，λ衡量兩個目標(biāo)的相對重要性，為了使每只螞蟻搜索不同的目標(biāo)空間，第l只螞蟻對應(yīng)的λ可表示為：

(16)

S∈Fl(i)表示按照下述概率分布確定的板坯：

(17)

2.3 局部搜索策略

為改善蟻群算法所得解的質(zhì)量，MOACS中引入了局部搜索策略，包含3個算子：Insertion、2-opt和Swap。Insertion算子主要用于減少板坯未被編入軋坯所帶來的懲罰，2-opt算子用于減少相鄰板坯間的跳躍懲罰，Swap算子則兼顧兩者。圖2為局部搜索策略中3個算子的原理圖，其中，i、j、k、r均代表板坯。3個算子的執(zhí)行順序為Insertion→2-opt→Swap。

(1)Insertion。Insertion算子考慮所有未被編入軋批的板坯，首先將這些板坯按照獎金降序排列，然后為每個未編入計劃的板坯k尋找一個最好的位置插入到已有軋批中(判別標(biāo)準(zhǔn)為最小化dik+dkj-dij)，直到無可行插入為止。

(2)2-opt。2-opt算子是VRP與TSP中最常用的局部搜索算子，本文中用于減少每個軋制單元中相鄰板坯間的跳躍懲罰。如圖2中所示，2-opt算子首先刪掉完整路徑的兩條邊(r,i)與(j,k)，使其分成3個部分，然后通過引入新邊(r,j)與(i,k)并反轉(zhuǎn)節(jié)點i與j之間的路徑以達(dá)到更小的跳躍懲罰。

(3)Swap：Swap算子通過交換軋批中板坯與收池中板坯來同時達(dá)到上述兩種目的。具體來說，對每個收池中按照獎金降序排列的板坯r，如果滿足以下兩個條件：板坯j的獎金小于板坯r的獎金；dir+drk-dij-djk<0，則將板坯r與軋批中的板坯j交換。Swap算子亦可理解為插入板坯r與刪除板坯j。

2.4 精英保留策略

MOACS中，內(nèi)部種群PS用于構(gòu)造螞蟻路徑，外部檔案ES用于存儲算法迭代過程中產(chǎn)生的Pareto最優(yōu)解(或非支配解)，使得精英個體得以保留。具體來講，算法在每次迭代中，需要將內(nèi)部種群PS產(chǎn)生的非支配解更新到外部檔案ES中，并刪除外部檔案ES中的所有被支配解。如果外部檔案ES中的Pareto最優(yōu)解個數(shù)超過一定上限，為了保證算法效率，需要刪除一部分解。為了使外部檔案ES中的解分布均勻，選用自適應(yīng)網(wǎng)格策略[12]進(jìn)行多樣性保留。

2.5 信息素更新策略

在ACS中，信息素更新策略包含局部更新與全局更新兩種。局部更新是指螞蟻每選擇下一個節(jié)點后，按照一定規(guī)則減小該邊上的信息素濃度，其作用是降低下一只螞蟻選擇這條邊的概率，有利于擴(kuò)大搜索空間，避免算法過早收斂。而全局更新是指在一次迭代中，當(dāng)所有螞蟻完成路徑構(gòu)造后，對其中最好的一條路徑進(jìn)行信息素增強(qiáng)，誘導(dǎo)螞蟻以更大的概率選擇該條路徑上的邊，以此保證算法的收斂性。信息素的局部更新與全局更新體現(xiàn)了ACS算法對全局探索與局部開發(fā)的一種平衡。

在MOACS中，沿用這種思路，但需根據(jù)多目標(biāo)優(yōu)化特性，對信息素局部更新與全局更新公式進(jìn)行改進(jìn)。改進(jìn)后的信息素局部更新公式如下：

(18)

在ACS中，僅對一個最優(yōu)解進(jìn)行信息素全局更新。多目標(biāo)優(yōu)化不存在惟一的最優(yōu)解，可在每次迭代中，選擇對應(yīng)每個目標(biāo)的最優(yōu)解來更新相應(yīng)的信息素矩陣，信息素全局更新公式如下：

(19)

(20)

式中：ft(best)為本次迭代中第t個目標(biāo)的最優(yōu)值。

3 實驗驗證

為驗證軋制計劃模型與算法的有效性，采用某鋼鐵公司的實際生產(chǎn)數(shù)據(jù)進(jìn)行實驗驗證。測試數(shù)據(jù)中共包含331塊板坯，軋制計劃中包含3個軋制單元。使用3種方法進(jìn)行比較研究，方法一為本文提出的MOACS算法；方法二為改進(jìn)的ACS算法，即通過加權(quán)法將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，然后按照MOACS算法的思路對標(biāo)準(zhǔn)ACS算法進(jìn)行適當(dāng)改進(jìn)，使之能夠處理軋制計劃編制問題；方法三為人工排程方法，是生產(chǎn)現(xiàn)場采用的一種基于規(guī)則和人工經(jīng)驗的方法。MOACS和ACS算法使用C++編程實現(xiàn)，算法參數(shù)設(shè)置如下：α=1，β=2，ρ=0.1，q0=0.9，L=30，maxGen=200，PLS=0.1。

3種方法的優(yōu)化結(jié)果如表1和圖3所示。由表1和圖3中可知：

(1)表1中，為ACS算法選擇了5組不同的目標(biāo)權(quán)重系數(shù)進(jìn)行優(yōu)化，得到不同權(quán)重系數(shù)下的最優(yōu)解。從表1中可知，不同的目標(biāo)權(quán)重系數(shù)得到的最優(yōu)解不同，因此在使用單目標(biāo)優(yōu)化算法編制軋制計劃時，需要決策者具備一定的先驗知識來合理確定目標(biāo)權(quán)重系數(shù),而MOACS算法則避免了目標(biāo)權(quán)重系數(shù)的設(shè)置問題。

(2)從圖3中可知，ACS算法在取均勻分布的目標(biāo)權(quán)重系數(shù)時，最優(yōu)解并未在整個解空間均勻分布，存在一定的“偏置”，表明在目標(biāo)數(shù)量級不一致的情形下，目標(biāo)權(quán)重系數(shù)并不能準(zhǔn)確反映決策者對不同目標(biāo)的偏好。與之相反，MOACS算法可在整個解空間得到均勻分布的Pareto最優(yōu)解，為決策者提供了更全面的信息。

(3)在圖3中，解越靠近圖形的左下端，表明兩個目標(biāo)的值越小，優(yōu)化精度越高。從圖3中可知，MOACS算法的優(yōu)化精度最高，ACS算法次之，人工排程的精度最差。人工排程方法屬于典型的串行方法，類似于貪婪方法，容易陷入局部最優(yōu)，當(dāng)編制第一個軋制單元時，由于有足夠多的候選板坯可選，計劃員較容易就能編制出性能良好的軋制單元，而后隨著候選板坯數(shù)的減少，編制效果越來越差，表現(xiàn)為相鄰板坯間跳躍波動較大，排入軋制計劃的板坯數(shù)減少；而MOACS和ACS算法屬于并行算法，可有效地均衡各個軋制單元的排程質(zhì)量，實現(xiàn)全局優(yōu)化。另外，局部搜索策略的引入使得MOACS算法的性能得以顯著提高。眾所周知，ACS算法雖然有著良好的全局收斂性能，但其收斂速度較慢。本文針對軋制計劃特性引入的局部搜索策略，集成了Insertion、2-opt和Swap 3個算子，在蟻群算法的基礎(chǔ)上對兩個目標(biāo)進(jìn)行了精細(xì)搜索，在提高優(yōu)化精度的同時，加快了算法收斂的速度。

(4)從計算效率來看，雖然MOACS算法由于存在精英保留策略、局部搜索策略等額外運算，其單次運行的時間較ACS算法時間長，但MOACS算法一次運行可產(chǎn)生多個Pareto最優(yōu)解，而ACS算法每次運行僅得到一個最優(yōu)解，若想產(chǎn)生多個不同結(jié)果，需要在不同的目標(biāo)權(quán)重系數(shù)下，多次重復(fù)運行算法，花費的總時間更長。人工排程方法所花費的時間最長，一般需要2 h才能排好一個軋制計劃，給決策者帶來很大的負(fù)擔(dān)。

(5)決策者可在MOACS算法得到的Pareto最優(yōu)解中，挑選出最終的軋制計劃方案，屬于后驗決策。如圖3所示，最終方案很好地兼顧了兩個目標(biāo)，與人工排程方案相比，相鄰板坯間的跳躍懲罰更小，有利于減少軋輥磨損，同時該方案使得軋制計劃中編入更多板坯，可提高軋制單元軋制長度，減少換輥次數(shù)，提高生產(chǎn)效率。

4 結(jié)語

本文提出的基于Pareto最優(yōu)的多目標(biāo)蟻群系統(tǒng)算法(MOACS)為熱軋軋制計劃優(yōu)化問題的優(yōu)化求解提供了一種新的解決方案，不僅避免了選擇目標(biāo)權(quán)重系數(shù)的問題，且算法一次運行可產(chǎn)生多個Pareto最優(yōu)解，給決策者帶來更大的決策自由度?，F(xiàn)場數(shù)據(jù)測試表明，該算法無論是優(yōu)化精度還是優(yōu)化效率均明顯優(yōu)于ACS算法和人工排程方法，對實際生產(chǎn)具有很好的指導(dǎo)意義。

[1] Lopez L, Carter M W, Gendreau M. The hot strip mill production scheduling problem: a tabu search approach[J]. European Journal of Operational Research, 1998, 106(2-3): 317-335.

[2] Tang L X, Liu J Y, Rong A M, et al. A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex[J]. European Journal of Operational Research, 2000, 124: 267-282.

[3] 黃可為，杜斌，劉青，等. 基于模型的熱軋軋制計劃排程系統(tǒng)的設(shè)計與實現(xiàn)[J]. 上海金屬，2009，31(4)：41-45.

[4] 李耀華，王偉，徐樂江，等. 熱軋生產(chǎn)軋制計劃模型與算法研究[J]. 控制與決策，2005，20(3)：275-279.

[5] 賈佳，潘莉，屠乃威，等. 熱軋批量計劃多目標(biāo)智能優(yōu)化編制新方法[J]. 控制工程，2008，15(2)：220-224.

[6] Liu S X. Model and algorithm for hot rolling batch planning in steel plants[J]. International Journal of Information and Management Sciences, 2010, 21(3): 247-263.

[7] Jia S J, Zhu J, Yang G K. et al. A decomposition-based hierarchical optimization algorithm for hot rolling batch scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2012, 61(5-8): 487-501.

[8] Pan C C, Yang G K. A method of solving a large-scale rolling batch scheduling problem in steel production using a variant of column generation[J]. Computers & Industrial Engineering, 2009, 56: 165-178.

[9] 郭冬芬，李鐵克. 約束滿足技術(shù)在板坯排序中的應(yīng)用[J]. 計算機(jī)工程與應(yīng)用，2007，43(9)：1-3.

[10]賈樹晉，朱俊，杜斌，等. Pareto最大最小螞蟻算法及其在熱軋批量計劃優(yōu)化中的應(yīng)用[J].控制理論與應(yīng)用，2012，29(2)：137-144.

[11]Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the travelling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.

[12]Knowles J D, Corne D W. Approximating the nondominated front using the Pareto archived evolution strategy[J]. Evolutionary Computation, 2000, 8(2): 149-172.

[責(zé)任編輯 鄭淑芳]

Multi-objective optimization model and algorithm for the hot rolling batch scheduling problem

JiaShujin，LiWeigang，DuBin

(Automation Division of Central Research Institute, Baosteel Group Corporation, Shanghai 201900, China)

In view of the hot rolling batch scheduling problem,a multi-objective prize collecting vehicle routing problem (PCVRP) model is presented. This model has two objectives: the first objective is to minimize the penalties caused by jumps in width, gauge and hardness between adjacent slabs, and the second one is to maximize the collected prize,which means more slabs can be inserted into the rolling batch. Then, a multi-objective ant colony system algorithm based on Pareto optimal is proposed to solve the PCVRP model. This algorithm can not only avoid the selection of weight coefficients encountered in the single objective optimization but also obtain multiple Pareto-optimal solution, which provides more decision-making flexibility for the schedulers. Large numbers of site tests show that this algorithm has optimal performance and good practicability.

hot rolling batch scheduling; multi-objective optimization; Pareto optimal; ant colony algorithm

2014-08-05

賈樹晉(1982-)，男，寶鋼集團(tuán)中央研究院工程師，博士.E-mail：jiashujin@baosteel.com

李維剛(1977-)，男，寶鋼集團(tuán)中央研究院高級工程師，博士.E-mail：liweigang@baosteel.com

TP27

A

1674-3644(2015)01-0016-07