加熱爐板坯入爐時間調度模型與算法

蔣正鍇 張珊珊 范瑜愷 許 晗

?

加熱爐板坯入爐時間調度模型與算法

蔣正鍇 張珊珊 范瑜愷 許 晗

本文以鋼鐵企業熱軋生產階段中的加熱爐生產過程為背景，提煉出加熱爐板坯入爐時間調度問題，即在滿足實際生產工藝約束，保證熱軋生產連續性的前提下，以節能降耗為目標，決策板坯在加熱爐中的分配情況和入爐時間。針對該問題，建立了數學模型。基于實際排產規則，構造初始啟發式，并提出鄰域搜索算法對初始解改進。最后，通過計算實驗對所提模型和算法進行驗證。

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

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

鋼鐵企業加熱爐板坯入爐時間調度模型

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

引入以下符號

M 候選加熱爐的數量；

N 候選板坯的數目；

n 加熱爐i 的爐容；

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

Cj 板坯j的出爐時間；

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

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

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

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

決策變量

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

針對加熱爐入爐時間調度問題建立以下模型

圖1　熱軋生產工序布局

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

鄰域搜索算法

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

初始啟發式

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

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

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

Step 3.如果j3N，停止計算，否則，轉到Step4；

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

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

鄰域

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

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

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

2-opt鄰域：基于當前解，通過2-opt移動獲得的所有解所構成的當前解鄰域。

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

停止準則

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

圖2　移動操作示意圖

仿真實驗

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

板坯數　爐子數　目標函數　計算時間（秒）啟發式　鄰域搜索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

結語

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

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

蔣正鍇 張珊珊 范瑜愷 許 晗

東北大學信息科學與工程學院

10.3969/j.issn.1001-8972.2016.11.036