蔣正鍇 張珊珊 范瑜愷 許 晗

?

加熱爐板坯入爐時間調(diào)度模型與算法

蔣正鍇 張珊珊 范瑜愷 許 晗

本文以鋼鐵企業(yè)熱軋生產(chǎn)階段中的加熱爐生產(chǎn)過程為背景，提煉出加熱爐板坯入爐時間調(diào)度問題，即在滿足實際生產(chǎn)工藝約束，保證熱軋生產(chǎn)連續(xù)性的前提下，以節(jié)能降耗為目標(biāo)，決策板坯在加熱爐中的分配情況和入爐時間。針對該問題，建立了數(shù)學(xué)模型?；趯嶋H排產(chǎn)規(guī)則，構(gòu)造初始啟發(fā)式，并提出鄰域搜索算法對初始解改進。最后，通過計算實驗對所提模型和算法進行驗證。

鋼鐵企業(yè)熱軋生產(chǎn)階段是將板坯軋制成鋼板或者帶鋼的加工過程，處于鋼鐵企業(yè)中間的核心部位，其原料來自于煉鋼生產(chǎn)階段， 產(chǎn)品送往下游冷軋生產(chǎn)階段。 熱軋生產(chǎn)階段包括加熱爐、熱軋生產(chǎn)線工序。 從連鑄到熱軋生產(chǎn)線主要包括四類銜接方式：連鑄-冷坯裝爐軋制（CCCCR）、連鑄-熱坯裝爐軋制（CC-HCR）、連鑄-直接熱坯裝爐軋制（CC-DHCR）、連鑄-直接熱軋（CC-HDR）： 連鑄-直接熱軋銜接方式對于各生產(chǎn)、物流環(huán)節(jié)的技術(shù)要求較好， 因此，在當(dāng)前的實際生產(chǎn)中較少使用， 而除了連鑄-直接熱軋之外，其余銜接方式均需通過加熱爐對板坯進行加熱，從而使板坯達(dá)到熱軋所需的軋制溫度， 因此，加熱爐是熱軋生產(chǎn)階段的核心工序。

熱軋生產(chǎn)階段包含一個熱軋生產(chǎn)線和多個加熱爐，其供料關(guān)系如圖1所示。由于通常在制定加熱爐板坯調(diào)度方案時，熱軋生產(chǎn)計劃已知，加熱爐和熱軋生產(chǎn)線通過輥道連接，板坯在加熱爐中的出爐時間可近似看作板坯在熱軋生產(chǎn)線的開始加工時間，因此，加熱爐板坯調(diào)度實質(zhì)為板坯入爐時間調(diào)度。實際加熱爐生產(chǎn)過程中，合理的板坯調(diào)度是保證加熱質(zhì)量，保證熱軋生產(chǎn)連續(xù)性的基礎(chǔ)。本文針對候選板坯，在保證生產(chǎn)連續(xù)性和工藝約束的前提下，以節(jié)能降耗為目標(biāo)，決策板坯在哪個加熱爐進行加熱，以及每塊板坯的入爐時間。文獻針對加熱爐優(yōu)化調(diào)度問題提出分散搜索算法進行求解；文獻針對考慮冷坯、熱坯互相轉(zhuǎn)化模式下的加熱爐調(diào)度問題進行研究，并提出兩階段算法對問題進行求解；文獻考慮加熱爐容量限制以及相鄰板坯在加熱過程之間的溫度傳遞關(guān)系，決策板坯在加熱爐中的調(diào)度方案，提出分散搜索算法對問題進行求解；文獻考慮加熱爐的容量限制決策板坯的調(diào)度方案，并設(shè)計啟發(fā)式算法對問題進行求解。

鋼鐵企業(yè)加熱爐板坯入爐時間調(diào)度模型

在加熱爐調(diào)度問題中，需要在給定軋制調(diào)度的前提下，決定在什么時間哪一個爐中加熱各個板坯。因為加熱爐和軋線之間是無等待的，并且它們之間的運輸時間是個相對較小的常數(shù)，所以每個板坯的出爐時間可以基于軋線的調(diào)度方案計算出來。因此，加熱爐調(diào)度問題即為決策板坯在哪個加熱爐中進行加工，各加熱爐中板坯的先后加工順序以及板坯的入爐時間，現(xiàn)場操作人員可操縱吊機按照決策出的入爐時間來運輸板坯，從而在保證軋線的穩(wěn)定供料，板坯達(dá)到理想的軋制溫度的前提下節(jié)能降耗。

引入以下符號

M 候選加熱爐的數(shù)量；

N 候選板坯的數(shù)目；

n 加熱爐i 的爐容；

tj 板坯j的理想加熱時間；

Cj 板坯j的出爐時間；

d 熱裝板坯和冷裝板坯相鄰加工所帶來的能量損失懲罰；

aj 板坯j的實際加熱時間與理想加熱時間偏差的單位懲罰系數(shù)；

Lj 板坯j的加熱時間下限；

Uj 板坯j的加熱時間上限。

決策變量

sj 第j個板坯的裝爐時間。

針對加熱爐入爐時間調(diào)度問題建立以下模型

圖1　熱軋生產(chǎn)工序布局

模型目標(biāo)函數(shù)包含兩部分，其中第一項為實際在爐時間與理想在爐時間偏差所導(dǎo)致的懲罰，第二項為相鄰加工板坯入爐溫度差異所導(dǎo)致的懲罰；約束（2）保證每個加熱爐里每個位置只有一個板坯；約束（3）保證每個板坯最多可被加工一次；約束（4）和（5）保證每個加熱爐里，先加工的板坯的出（入）爐時間一定大于后加工的板坯的出（入）爐時間；約束（6）保證板坯只有在加熱爐有空位的時候才能裝爐；約束（7）保證板坯的在爐時間需滿足上下限約束；約束（8）為變量取值范圍。

鄰域搜索算法

由于問題同時決策板坯的分配、排序和板坯的加工時刻表，該問題與經(jīng)典的并行機調(diào)度問題相似，而問題目標(biāo)函數(shù)考慮了實際在爐時間與理想在爐時間的偏差，以及依賴于相鄰板坯入爐溫度的懲罰，因此，本文考慮問題較經(jīng)典的并行機調(diào)度問題更為復(fù)雜，本問題屬于強NP-難，因此，在此處采用鄰域搜索算法求問題的近優(yōu)解。首先設(shè)計基于人工排產(chǎn)規(guī)則的啟發(fā)式構(gòu)造初始解。然后，通過鄰域搜索方法改進初始解。下面，首先給出獲得初始解的方法。

初始啟發(fā)式

獲得初始解的構(gòu)造啟發(fā)式可簡單描述如下。在調(diào)度過程中，首先將板坯按照出爐時間從小到大進行排序，預(yù)排序后的板坯序列表示為d， d，…， d［N］，然后再對板坯進行調(diào)度，具體方法如下：

Step 1.初始化待排板坯編號j=1，任意加熱爐k可安排位置為pk=1；

Step 2.令k=j mod M，將板坯j安排到第k個加熱爐的位置pk上；

Step 3.如果j3N，停止計算，否則，轉(zhuǎn)到Step4；

Step 4.另pk=pk+1，j=j+1，返回Step2；

Step 5.決策每個板坯的開始加工時間。

鄰域

在本文所設(shè)計的鄰域搜索算法中，主要采用三種領(lǐng)域，分別是交換鄰域、插入鄰域、2-opt鄰域，下面對著三種鄰域進行介紹。

交換鄰域：基于當(dāng)前解，通過將處于不同加工位置的板坯進行交換獲得的所有解構(gòu)成的當(dāng)前解鄰域；

插入鄰域：基于當(dāng)前解，通過將任意鋼卷從原位置移出，然后插入一個新的位置獲得的所有解構(gòu)成的當(dāng)前解鄰域；

2-opt鄰域：基于當(dāng)前解，通過2-opt移動獲得的所有解所構(gòu)成的當(dāng)前解鄰域。

如上三種鄰域所涉及的移動操作如圖2所示。

停止準(zhǔn)則

即使沒有找到問題最優(yōu)解，當(dāng)搜索過程滿足停止準(zhǔn)則時將停止迭代。在本算法中，設(shè)置了兩種停止準(zhǔn)則，當(dāng)滿足其中一條的時候，即停止改進過程。這兩個停止準(zhǔn)則分別為給定最大迭代次數(shù)和給定最大無改進迭代次數(shù)。

圖2　移動操作示意圖

仿真實驗

為了驗證如上算法的性能，如上算法用C語言來實現(xiàn)，并在Intel（R） Core（TM） i7-4790 CPU PC機上進行測試。基于隨機生成算例，對上述所提的算法進行測試，將鄰域搜索算法獲得結(jié)果與基于人工排產(chǎn)規(guī)則的啟發(fā)式進行對比，實驗結(jié)果如表1所示。

板坯數(shù)　爐子數(shù)　目標(biāo)函數(shù)　計算時間（秒）啟發(fā)式　鄰域搜索100　3　5400　4700　0.628 200　3　9500　8300　2.342 500　3　24600　23100　24.779 100　5　4600　3700　0.607 200　5　9000　7900　2.286 500　5　23400　21200　23.924 100　10　5000　4200　0.643 200　10　9800　8600　2.182 500　10　26800　25100　24.864

結(jié)語

加熱爐是連鑄到熱軋生產(chǎn)過程中的重要的環(huán)節(jié)，為實現(xiàn)均衡連續(xù)的軋制生產(chǎn)起著重要的緩沖調(diào)節(jié)作用。本文根據(jù)加熱爐的生產(chǎn)特點建立了鋼鐵企業(yè)加熱爐入爐時間的調(diào)度模型，并且設(shè)計了鄰域搜索算法進行了求解。實驗結(jié)果表明：1）隨著板坯數(shù)和爐子數(shù)量的增加，求解問題的規(guī)模越來越大。

2）鄰域搜索算法比人工排產(chǎn)規(guī)則的啟發(fā)式算法擁有更高的效率。所提鄰域搜索改進算法可明顯改進啟發(fā)式所獲得解。

蔣正鍇 張珊珊 范瑜愷 許 晗

東北大學(xué)信息科學(xué)與工程學(xué)院

10.3969/j.issn.1001-8972.2016.11.036