兩階段法求解混裝模式下的加熱爐調度

［摘 要］針對目前加熱爐調度模型少有考慮混裝模式下加熱爐調度優化的不足，建立了連鑄-熱軋混裝一體化模式下的加熱爐生產調度優化模型，并提出了基于貪婪算法和模擬退火算法的兩階段求解方法。生產數據測試表明該模型和算法能有效解決加熱爐調度問題。

［關鍵詞］混裝模式；加熱爐；生產調度優化；多階段決策

doi:10.3969/j.issn.1673-0194.2009.15.013

［中圖分類號］TP399 ；F273.1；TB112［文獻標識碼］A［文章編號］1673-0194（2009）15-0042-03

1 引 言

加熱爐位于鋼鐵生產中連鑄工序和熱軋工序之間，是鋼鐵生產中的高能耗環節［1］。目前有關加熱爐的研究主要從熱能的角度側重于加熱爐加熱優化控制研究［2］，但對于加熱爐的生產調度優化的研究相對較少［3-4］。本文以一體化模式下的加熱爐優化調度為研究對象， 建立了連鑄-熱軋混裝一體化模式下的加熱爐生產調度優化的數學模型， 并應用基于貪婪算法和模擬退火算法的兩階段方法求解。加熱爐生產實際數據仿真結果表明，該算法能有效求解加熱爐調度優化問題。

2 混裝模式下的加熱爐物流分析

圖1 混裝模式下的加熱爐調度過程

連鑄-熱軋混裝一體化模式下加熱爐調度過程如圖1所示。混裝模式下原料既有從連鑄機產出的直裝坯，也有庫內板坯。其中，直裝坯通過輸送輥道直接進入加熱爐加熱；板坯庫冷坯、保溫坑溫裝坯先進入上料輥道， 然后通過裝料輥道裝爐。板坯入爐后， 隨著在爐時間及在爐位置的前移，板坯的溫度逐漸升高。最終，當板坯溫度（或者在爐時間）滿足要求且符合軋制計劃的出爐順序要求時，板坯出爐并由輸送輥道送往軋機進行軋制。

目前常用的加熱爐調度方法是根據板坯的軋制順序和加熱爐爐號順序，依次向各加熱爐分配板坯。在混裝模式下沿用上述順序裝爐方式，由于沒有考慮冷熱板坯加熱時間差異，冷熱板坯混裝對加熱的影響等因素，將導致板坯質量下降和加熱爐能耗的增加。因此，設計合理的加熱爐調度方案，在滿足混裝一體化生產約束下，盡量縮短生產時間和減少冷熱板坯混合裝爐，對提高板坯加熱質量和降低加熱爐能耗都具有重要意義。

3 加熱爐調度模型

本文研究的加熱爐的調度優化問題可描述為：在連鑄-熱軋一體化計劃已經確定的前提下決定如何將板坯分配給不同的加熱爐進行加熱，使得在滿足連鑄出坯間隔、板坯在爐時間等約束下，盡量縮短軋線生產時間和減少冷熱板坯混合裝爐，以節約能源、提高產品質量。根據以上描述，建立數學模型如下： 

min∑i，fn(i)∈Slabδ1×Pi，fn(i)×1S1-Sfn(i)+

∑i，hn(i)∈Slabδ2×(ei-ehn(i)-h)(1)

s.t. ei-si≥pmini， i∈Slab(2)

ei-si≤pmini， i∈Slab (3)

∑k∈FurFki=1， i∈Slab(4)

ei-efn(i)≥0， i、 fn(i)∈Slab(5)

ei-ehn(i)≥0， i、 hn(i)∈Slab(6)

ei-ehn(i)≤hmax， i、 hn(i)∈Slab(7)

si≥c i， i∈Slab， Typei=0(8)

Typei=0 直裝坯1 非直裝坯

Fi=0 板坯i分配給加熱爐k， i∈Slab， k∈Fur1否則

式中，Fur為加熱爐集合；Slab為板坯號集合；si為板坯i的開始加工時刻；ei為板坯i的實際加工完成時刻；pmini為板坯i在加熱爐加工時所需的最短的額定加工時間；pmaxi為板坯i在加熱爐內停留的最長時間；fn(i)為加熱爐內，與板坯i直接相連的后續板坯；hn(i)為緊鄰板坯i軋制的板坯；h為最短出坯間隔時間；hmax為熱軋機等待加熱爐出坯的時間上限值；ci為直裝坯i的產出時刻；Typei為板坯類型；Fki為板坯i的入爐標記；Pij為板坯j與板坯i連續裝爐的溫度差異懲罰系數。

目標函數式（1）表示加熱爐調度的優化目標為加熱懲罰與軋線等待懲罰總費用最小，其中第一項為連續裝爐板坯溫度差異的懲罰費用；第二項為由于板坯未能按時提供軋線所需的板坯從而導致軋線空閑的懲罰費用，δ1、δ2為上述兩懲罰項的權重。約束（2）表示板坯在加熱爐內的實際加工時間不少于最短額定加工時間；約束（3）表示板坯不能在加熱爐內停留時間過長；約束（4）表示每塊板坯都被分配而且只被分配到一個加熱爐加工；約束（5）表示在同一加熱爐中加工的板坯先進入爐的先進熱軋；約束（6）表示板坯在熱軋機軋制前一塊板坯時一直在加熱爐中停留；約束（7）表示熱軋機的空閑時間不超過一個預先設定的值；約束（8）表示直裝板坯的入爐時刻必須大于其連鑄出坯時刻。 

4 算法設計

加熱爐調度優化問題屬于NP-hard問題［3］，采用隨機搜索方法，容易產生非可行解，且求解速度較慢。為了避免上述缺陷，本文應用兩階段求解方法：在第一階段，應用基于貪婪算法和時間回溯的啟發式方法確定可行的設備指派方案；在第二階段，應用模擬退火算法，調整板坯與加熱爐爐號的匹配，最終尋找優化的調度方案。

4.1 初始解生成

本文采用了交貨期最早優先（Earliest Due Date，EDD）指派規則，根據軋制順序按從小到大排列，依次求解各板坯的入爐時間和爐號。

首先定義變量［i］為第i塊軋制的板坯。求解步驟如下：

Step 1：按軋制順序由小到大排列板坯。

Step 2：隨機安排第一塊軋制的板坯的入爐爐號，確定入爐時間s［1］=0，最佳出爐時間e［1］=pmin［1］，及出爐時間窗［pmin［1］， pmax［1］］。i=2。

Step 3：依次計算板坯［i］安排到k （k=1，…，M）加熱爐后的目標懲罰值。若爐群滿足約束，則選擇目標值最小的爐號為入爐爐號，確定相應的入爐、出爐時間窗，及最佳入爐、出爐時間，進入Step 5。否則，進入Step 4。

Step 4：采用時間順序回溯策略，選擇板坯［i-1］的次優加熱爐，重新指派板坯的入爐爐號及加工時間；當遍歷所有加熱爐，仍然找不到［i］板坯的合適解，回溯板坯［i-2］，依次類推；如果回溯到起始板坯仍然找不到合適解，則在該啟發式方法下無解，結束循環。

Step 5：i=i+1，執行Step 3，直到所有板坯安排完畢。

4.2 解的改進

本文應用模擬退火算法，以第一階段的可行解作為初始解，通過板坯交換和插入算子，調整板坯與加熱爐的組合，從而尋找優化調度方案。具體方法描述如下：

Step 1：初始化參數n=0，c=0，k=0，當前溫度tmax=tk；

Step 2：若n＞N1（N1為該溫度下總循環次數），或c＞N2（N2為該溫度下無改進解的累計次數），或板坯遍歷完畢，則轉Step 6；否則，隨機選擇要交換的板坯［i］（定義其入爐時間窗定義為［S［i］， S［i］］），并確定其鄰域U為：與［i］的入爐時間窗交集不為空的板坯集合。

Step 3：當U≠，則從領域中隨機選擇一鄰居［j］，轉Step 4；否則，令n=n+1，轉Step 2；

Step 4：若［S［j］， S［j］］［S［i］，則計算板坯［i］與［j］交換后的目標函數改進量Δf；若［S［j］， S［j］］［S［i］， S［i］］或［S［j］， S［j］］［S［i］， S［i］］，則判斷［i］插入到［j］前后或［j］插入到［i］前后的目標函數改進量Δf。若Δf≤0，則執行相應交換或插入操作，記錄當前最優解；否則當e-Δf/tk≥rand(1)，（rand(1)表示一個0 到1 之間的均勻隨機數），執行交換或插入。

Step 5：若板坯［i］與板坯［j］沒有執行交換或插入操作，令U=U-{［j］}，重復Step 3~Step 4；否則，n=n+1，若目標函數值非減，則令c=c+1，否則，c=0，進入Step 2。

Step 6：若連續N3次降溫均沒有出現改進解，輸出最優解，算法停止；否則，令n=0，c=0，k=k+1，tk=α×tk-1，轉Step 2。

5 數據驗證

本文采用了由120塊板坯組成的一體化計劃，分別應用以下算法進行測試：基于順序入爐規則的傳統調度方法，基于貪婪算法的求解方法，本文提出的二階段優化求解方法。實驗結果如表1所示。

從測試結果可以看出：采用傳統的順序入爐方式，由于其沒有考慮冷熱板坯同爐加熱對板坯質量和加熱節奏的影響，通過公式（1）計算的目標懲罰值很高，不適合作為混裝模式的生產組織形式；基于貪婪算法的求解方法一定程度上優化了裝爐效果；采用本文提出的兩階段求解方法，目標懲罰值最小，求解效果最好。此外，從運行時間上看，兩階段法的求解速度完全能夠滿足現場生產調度的要求。

表1仿真實驗結果

優化方式

運行結果

順序入爐貪婪算法二階段方法

總加工時間（min）550528473

溫度最大跳躍（℃）450280100

目標函數值5 6364 9893 530

運行時間（s）6.48.817.8

6 結 論

本文針對混裝一體化生產物流的特點，建立了混裝模式下的加熱爐生產調度模型。為便于求解，首先構造了基于貪婪算法和時間回溯算法的啟發式方法，從而提高了可行解的求解速度；在第二階段，基于模擬退火方法，設計了板坯交換和插入算子，快速實現了解的優化。實例計算證明該算法能及時有效求解混裝模式下的加熱爐調度優化問題。

主要參考文獻

［1］ Tang LX， Liu JY， Rong AY， Zhou YH. A Review of Planning and Scheduling Systems and Methods for Integrated Steel Production ［J］. European Journal of Operational Research， 2001，133(1):1-20.

［2］ 安月明，溫治. 步進梁式板坯加熱爐數學模型及其仿真系統［J］. 系統仿真學報， 2006，19(12):2827-2830.

［3］ 寧樹實，王偉，劉全利. 鋼鐵生產中的加熱爐優化調度算法研究 ［J］. 控制與決策， 2006，21(10):1138-1142.

［4］ 李婧，李蘇劍. 加熱爐爐群生產物流仿真系統的設計和實現［J］. 鋼鐵， 2001，36(8):52-55.

A Two Stage Method for Optimal Scheduling Problem of Reheating

Furnace in Hybrid Charge Mode Production

LIANG He-lan1， LI Su-jian1， DENG You-hao2

(1.Department of Logistics Engineering， School of Mechanical Engineering， University of Science and Technology

Beijing， Beijing， 100083， China; 2.Shougang Qian’an Iron Steel CO.， LTD.， Hebei， 064404， China)

Abstract： Focusing on the limitations of traditional optimal scheduling methods of reheating furnace that seldom consider the optimization for hybrid charge mode production， an optimization model for furnace scheduling problem of hybrid charge mode is formulated， and a two-stage combination method composed of both greedy and improved simulation anneal algorithm is put forward for solving the problem. Test with data from practical production process shows that the proposed method is suitable for practical production.

Key words: Hybrid Charge Mode; Reheating Furnace; Scheduling Optimization; Multi-stage Decision