爐容受限的加熱爐-熱軋集成調(diào)度模型與算法

周登舉 ZHOU Deng-ju；王韋棋 WANG Wei-qi

（安徽工業(yè)大學(xué)管理科學(xué)與工程學(xué)院，馬鞍山 243032）

0 引言

熱軋是鋼鐵生產(chǎn)過程中最重要的工序之一，直接影響產(chǎn)品的質(zhì)量。加熱爐是熱軋工序的輔助設(shè)備，也是熱軋階段的瓶頸環(huán)節(jié)，對鋼坯實現(xiàn)連續(xù)熱軋起到重要的調(diào)節(jié)作用。因此，加熱爐和熱軋的調(diào)度優(yōu)化問題一直是學(xué)者和專家們研究的重點內(nèi)容。目前，相關(guān)研究主要集中于加熱爐調(diào)度、熱軋調(diào)度和加熱爐-熱軋集成調(diào)度三個方面。

關(guān)于加熱爐調(diào)度研究，楊[1]等認(rèn)為加熱爐調(diào)度是在軋制計劃和連鑄出坯計劃已確定的前提下，決定鋼坯在加熱爐區(qū)的加工路徑。其目標(biāo)通常為燃料消耗最小[2，3]、住爐時間最小[3]等。

關(guān)于熱軋調(diào)度問題的研究，Liu[4]等將其歸納為多旅行商問題，Chen[5]等則將其描述為車輛路徑問題。熱軋調(diào)度的目標(biāo)大多為最小化跳躍懲罰成本[6]和最小化軋制單元數(shù)量[7]。文獻[4]在前人研究的基礎(chǔ)上，將噸鋼能耗考慮進去，建立了以最小化噸鋼能耗和最小化軋制單元數(shù)為目標(biāo)的數(shù)學(xué)模型。

近年來，加熱爐-熱軋集成調(diào)度逐漸成為研究熱點，學(xué)者們紛紛提出集成調(diào)度模型的建模方法，如文獻[8]分析了加熱爐對熱軋生產(chǎn)的影響，抽取板坯標(biāo)準(zhǔn)住爐時間和出爐溫度這兩個關(guān)鍵因素，建立了熱軋板坯軋制計劃的整數(shù)規(guī)劃模型、文獻[9]將問題建模為兩個耦合的子問題，分別用于求解軋制計劃和加熱爐調(diào)度方案。目標(biāo)函數(shù)有最大化熱裝比[9]、最小化住爐時間[9]等。

從現(xiàn)有的研究中可以看出，單獨的加熱爐和熱軋調(diào)度缺乏整體性考量，求出的調(diào)度方案無法兼顧多工序工藝約束和設(shè)備資源約束。而現(xiàn)有加熱爐-熱軋集成調(diào)度研究中，假設(shè)條件通常過于理想化，如軋機不允許空轉(zhuǎn)等待、不考慮加熱爐容量限制等。本文充分考慮軋制階段工藝約束和設(shè)備資源約束，以鋼坯的總完工時間最小、總住爐時間最小和軋機總待機時間最小為目標(biāo)建立數(shù)學(xué)規(guī)劃模型，并提出改進的NSGA-II算法對模型進行求解。本文的主要貢獻如下：

①模型方面：考慮加熱爐容量約束；考慮實際生產(chǎn)中的工藝約束，允許軋機短暫待機；通過添加最小化軋機待機時間為目標(biāo)，盡可能減少軋機待機的時間。

②算法方面：根據(jù)問題特點，設(shè)計多層編碼的染色體用以表征問題的解；根據(jù)染色體中存在實數(shù)編碼的特點設(shè)計多點復(fù)合交叉的交叉策略；通過引入沖突檢測-修復(fù)模塊確保解的可行性。

1 問題描述

本文針對一類典型的熱軋生產(chǎn)線展開研究，每條生產(chǎn)線包含一臺加熱爐和一臺軋機。熱軋前，待軋制的鋼坯先進入加熱爐加熱，達到額定加熱時間才允許出爐，鋼坯出爐后立即通過輥道運送至軋機進行軋制。其中，額定加熱時間是指鋼坯達到額定軋制溫度所需的最短加熱時間。軋制過程中，將鋼種、規(guī)格等屬性相同或相近的鋼坯組成批次集中軋制，使用同一套軋輥軋制的鋼坯稱為一個軋制單元。加熱爐-熱軋階段的工藝流程如圖1所示。

圖1 加熱爐-熱軋階段工藝流程圖

加熱爐-熱軋區(qū)間生產(chǎn)調(diào)度需要同時考慮加熱爐和軋機的工藝約束，兩者相互影響、相互制約。因此，為進一步提高設(shè)備利用率和生產(chǎn)效率、降低加熱爐能耗，在編制加熱爐-熱軋集成調(diào)度方案時，需考慮如下工藝約束和設(shè)備資源約束。

①加熱爐和軋機一一對應(yīng)，可將有對應(yīng)關(guān)系的加熱爐和軋機視為一體，稱為生產(chǎn)線；

②同一軋制單元的鋼坯僅可由一條生產(chǎn)線加工；

③軋不同軋制單元時，軋機需停機換輥；

④鋼坯有額定加熱時間和最大住爐時間，鋼坯實際住爐時間不得少于額定加熱時間，也不得大于最大住爐時間；

⑤鋼坯的入爐順序、出爐順序和軋制順序須保持一致，且與軋制單元計劃中鋼坯的加工順序相同；

⑥一臺加熱爐可同時加工多塊鋼坯，但不可超出容量限制，當(dāng)加熱爐裝滿時須等待鋼坯出爐，爐中有空位的情況下才能裝入新的鋼坯；

⑦由于軋機待機造成的損失較大，生產(chǎn)中要求軋機待機的時間不超過一個上限值。

2 問題建模

2.1 符號定義

為了方便描述模型，定義如下符號：

2.1.1 參數(shù)

i，j：軋制單元索引，i，j∈{0，1，…，n，n+1}，其中，0和n+1表示虛擬軋制單元，n表示軋制單元總數(shù)；

k：生產(chǎn)線索引，k∈{1，2，…，m}，其中m表示生產(chǎn)線總數(shù)；

Ωi：軋制單元i中的鋼坯集合；

Ω：所有軋制單元中的鋼坯集合；Ω=Ω1∪Ω2∪…∪Ωn

l：鋼坯索引，l∈Ω；

ail：鋼坯l在軋制單元i中的加工序號；

pil：軋制單元i中鋼坯l在加熱爐中的額定加熱時間；

wil：軋制單元i中鋼坯l在加熱爐中的最大住爐時間；

qil：軋制單元i中鋼坯l的軋制時間；

Si：軋制單元i的開軋時間；

Qi：軋制單元i的軋制時間；

rilk：若軋制單元i中鋼坯l在生產(chǎn)線k上的加熱爐中加熱，則rilk=1，否則rilk=0；

β：鋼坯從加熱爐到軋機的運輸時間；

δ：同爐相鄰鋼坯的最小入爐時間間隔；

ε：軋機允許的最大待機時長；

φ：相鄰兩個軋制單元之間的軋機換輥時間；

Ck： 生產(chǎn)線k上加熱爐的容量上限；

γ（ilt）：若，則為1，否則為0；

ρ（k，t）：表示t時刻加熱爐k中鋼坯的數(shù)量；

T：全部鋼坯加熱完成的最大時間；

U：一個足夠大的正數(shù)。

2.1.2 決策變量

xik：若軋制單元i在生產(chǎn)線k上加工，則xik=1，否則xik=0；

yijk：若軋制單元i和j均在生產(chǎn)線k上加工，且j緊隨i之后進行加工，則yijk=1，否則yijk=0；

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

爐容受限的加熱爐-熱軋集成調(diào)度的數(shù)學(xué)模型如下：

目標(biāo)函數(shù)（1）最小化總完工時間；目標(biāo)函數(shù)（2）最小化鋼坯總住爐時間；目標(biāo)函數(shù)（3）最小化軋機總待機時間；約束（4）每個軋制單元只能分配到一條生產(chǎn)線上加工；約束（5）所有軋制單元有且僅有一個前序軋制單元和一個后繼軋制單元；約束（6）虛擬軋制單元0被安排在每條線的第一位；約束（7）虛擬軋制單元n+1被安排在每條生產(chǎn)線的最后一位；約束（8）在相同軋機上連續(xù)加工的兩個軋制單元，后者開工時間要大于前者完工時間加軋機換輥時間；約束（9）鋼坯軋制開始時間等于出爐時間加上加熱爐到軋機的運輸時間；約束（10）軋制單元的開軋時間即為單元中第一塊鋼坯的開軋時間；約束（11）軋制單元的軋制時間等于單元中最后一塊鋼坯軋制完工時間減去軋制單元的開軋時間；約束（12）同一軋制單元內(nèi)的相鄰兩塊鋼坯，入爐的時間間隔必須大于等于最小入爐時間間隔；約束（13）鋼坯實際住爐時間應(yīng)在額定加熱時間至最大住爐時間范圍內(nèi)；約束（14）同一軋制單元內(nèi)的相鄰兩塊鋼坯，后者開工時間要大于前者完工時間和軋機待機時間不能過長；約束（15）加熱爐中同時加熱的鋼坯數(shù)不可超出容量限制；約束（16）決策變量取值約束。

3 求解算法

加熱爐-熱軋集成調(diào)度問題作為NP-hard問題，短時間無法獲得最優(yōu)解，一般使用智能優(yōu)化算法獲取滿意解。NSGA-II是常見的多目標(biāo)優(yōu)化算法，但考慮到模型中加熱爐容量限制，傳統(tǒng)的NSGA-II算法獲得的解不完全可行。因此，本文通過引入沖突檢測-修復(fù)模塊對不可行的解進行修復(fù)。

3.1 個體編碼和初始解

染色體采用三段實數(shù)編碼形式，由軋制單元所在生產(chǎn)線編號、鋼坯的開始加熱時間和開始軋制時間組成，其數(shù)據(jù)結(jié)構(gòu)可表示如下：

其中，N為軋制單元個數(shù)，Mi為軋制單元i中鋼坯的個數(shù)，第一段數(shù)組中FurnaceNo(1×N)是通過隨機數(shù)為各軋制單元指派加工的生產(chǎn)線編號；第二段數(shù)組中BilletStartHeat(1×N×Mi)是鋼坯開始加熱時間，第三段數(shù)組中BilletStartRoll(1×N×Mi)是鋼坯開始軋制時間。如個體[1，2；[0，2，4]，[4，6，8]；[120，122，124]，[124，126，128]]。該個體表達了兩個軋制單元被分派到兩條生產(chǎn)線加工，每個軋制單元中包含三塊鋼坯。

3.2 選擇、交叉和變異算子

采用輪盤賭方式進行選擇操作，采用多點復(fù)合交叉方式進行交叉操作，采用均勻變異方式進行變異操作。

3.3 適應(yīng)度函數(shù)和停止準(zhǔn)則

適應(yīng)度函數(shù)采用本文所求目標(biāo)函數(shù)。停止準(zhǔn)則采用給定種群的最大迭代次數(shù)。

3.4 沖突檢測-修復(fù)模塊

3.4.1 沖突檢測

首先定義加熱爐剩余資源能力函數(shù)R（k，t）：

R（k，t）表示t時刻加熱爐k的剩余資源能力，若R（k，t）＜0，則表示t時刻加熱爐k的資源負(fù)荷量超過爐容，違背爐容約束式（15），存在資源沖突。

若初始調(diào)度方案中，軋制單元i中的鋼坯l被指派到加熱爐k上加工，且入爐時間為說明鋼坯l的加工時間違背加熱爐的容量約束，則鋼坯l為沖突鋼坯。

3.4.2 修復(fù)方法

為消解沖突，需為沖突鋼坯重新指定開始加熱時間。定義lk∈{1，2，…，Nk}，lk和Nk分別表示在生產(chǎn)線k上加熱爐加工的鋼坯索引及鋼坯總數(shù)，鋼坯lk在初始調(diào)度方案中給定的入爐時間和出爐時間分別為鋼坯lk經(jīng)調(diào)整后入爐時間和出爐時間分別為為生產(chǎn)線k上加熱爐的最早可用時間。

Step2：約束檢查。

3.5 算法步驟

下面介紹改進NSGA-II算法求解步驟。其中：iter表示算法的迭代次數(shù)，maxIter是算法最大迭代次數(shù)，Pop表示種群，sonPop表示子代種群，popSize表示種群規(guī)模，Pc表示交叉概率，Pm表示變異概率。

Step1：隨機生成初始不完全解，執(zhí)行沖突檢測-修復(fù)模塊獲得初始種群Pop。

Step2：初始化參數(shù)，包括種群規(guī)模popSize、最大進化代數(shù)maxIter、交叉概率Pc、變異概率Pm、當(dāng)前進化代數(shù)iter=1。

Step3：判斷是否已經(jīng)生成第一代子群，如果iter=1，轉(zhuǎn)Step4，否則轉(zhuǎn)Step5。

Step4：對父代種群進行非支配排序，再執(zhí)行選擇、交叉、變異操作，最后執(zhí)行沖突檢測-修復(fù)模塊，獲得子代種群sonPop，更新進化代數(shù)iter=iter+1。返回Step3。

Step5：將父代種群Pop和子代種群sonPop合并，對合并后的種群進行快速非支配排序，再計算擁擠度距離，最后選出popSize個個體組成新的父代種群Pop。

Step6：對新的父代種群進行選擇、交叉、變異操作，再執(zhí)行沖突檢測-修復(fù)模塊，獲得新的子代種群。

Step7：判斷迭代終止條件，如果iter>maxIter，則算法終止，否則更新進化代數(shù)iter=iter+1，返回Step3。

4 應(yīng)用案例

采用某鋼廠生產(chǎn)數(shù)據(jù)進行仿真實驗，其生產(chǎn)配置為2臺軋機對應(yīng)2臺加熱爐。根據(jù)歷史數(shù)據(jù)和專家經(jīng)驗設(shè)置加熱爐到軋機運輸時間為20s、軋機換輥時間為60min，加熱爐最小入爐時間間隔為10s，軋機最大待機時長為10min、加熱爐容量為（12，14）。根據(jù)問題規(guī)模設(shè)置算法種群規(guī)模為100，最大迭代次數(shù)為100，交叉概率0.7，變異概率為0.1。

選取一組樣本數(shù)據(jù)進行實驗。如表1所示是樣本數(shù)據(jù)的基礎(chǔ)信息，包括軋制單元編號、鋼坯的額定加熱時間、鋼坯的軋制時間、軋制單元中鋼坯數(shù)量等信息。經(jīng)過算法求解得到調(diào)度方案的甘特圖，如圖2所示。從圖中可以發(fā)現(xiàn)兩條產(chǎn)線的產(chǎn)能負(fù)荷分配均勻，軋機出現(xiàn)待機的情況較少。

圖2 加熱爐-熱軋集成調(diào)度甘特圖

表1 相關(guān)的實際生產(chǎn)數(shù)據(jù)

5 結(jié)論

加熱爐-熱軋集成調(diào)度是一類復(fù)雜的組合優(yōu)化問題。本文考慮實際生產(chǎn)中存在的加熱爐容量限制約束，分析了國內(nèi)某鋼廠熱軋生產(chǎn)線的特點，以鋼坯為調(diào)度對象，以提高生產(chǎn)效率和設(shè)備利用率、降低能耗為目的，建立了加熱爐-熱軋集成調(diào)度的多目標(biāo)模型。針對問題特點設(shè)計改進NSGA-II算法，通過引入沖突檢測-修復(fù)模塊保證解可行。結(jié)果表明，本文所提出的調(diào)度方法符合生產(chǎn)實際，能夠有效降低加熱爐能耗，提高軋機利用率。對降低鋼鐵企業(yè)的生產(chǎn)成本、提高生產(chǎn)效率、均衡生產(chǎn)負(fù)荷具有顯著意義。