混合PSO算法求解混裝工藝下的加熱爐調度問題

[摘 要] 針對鋼鐵生產中為減輕混裝的影響在冷熱板坯混裝處空爐的情況，以提高成品質量、降低能耗為目標，建立了混裝工藝下并行加熱爐調度的數學模型，并提出了基于粒子群算法和鄰域搜索技術的混合算法，仿真實驗驗證了算法的可行性和有效性。

[關鍵詞] 加熱爐調度;并行機;粒子群優化算法;鄰域搜索

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2009 . 21 . 015

[中圖分類號]TP393;C931.6 [文獻標識碼]A[文章編號]1673 - 0194(2009)21 - 0050- 03

1引 言

作為鋼鐵生產中重要的熱工設備和高能耗環節，加熱爐在軋鋼生產和熱送熱裝工藝中所處的重要地位使之成為研究熱點之一。在已有的研究成果中，文獻[1]、[2]設計了加熱爐爐群生產物流仿真系統，得出了在熱送熱裝條件下生產計劃和加熱爐生產的若干特點和規律。文獻[3]、[4]根據加熱爐的生產特征，抽象出極小化最大完工時間的單機連續型批調度問題，并證明了極小化最大拖期問題是強NP-難的。文獻[5]把加熱爐調度問題看作背包容量為無限的多約束背包問題，并設計了基于遺傳局部搜索的求解算法。

本文在上述研究的基礎上，針對混裝工藝下加熱爐生產的特點，以降低能耗、提高成品質量為目標，建立混裝工藝下的并行加熱爐調度數學模型，提出基于粒子群算法和鄰域搜索技術的混合算法，并對算法的性質進行分析和驗證。

2問題建模

2.1問題描述

在現代鋼鐵生產中，加熱爐位于連鑄和熱軋工序之間，通常有多臺加熱爐并行工作，對應于熱軋工序的一臺熱軋機。由于熱軋機要求所加工的板坯溫度在1100℃以上，因此絕大多數板坯都需要經加熱爐加熱后才能進入熱軋工序生產。軋制工序與連鑄工序間能力的不匹配，使得生產中通常需要板坯庫的冷坯作為補充，于是加熱爐內會經常出現混坯現象，導致過渡坯中的冷坯燒不透，熱坯溫度又偏高，使得部分板坯出現氧化燒損，影響成品質量，也降低了加熱爐效率。在非專用爐制下，一般采取在冷熱板坯混裝處空爐的方法減輕混裝的影響。

混裝工藝下并行加熱爐生產的約束條件可概述為:

(1)加熱爐群必須嚴格按照軋制計劃中的板坯順序向熱軋機提供板坯。

(2)一臺加熱爐可以同時加熱多塊板坯，板坯在加熱爐中按先進先出的原則加工。

(3)每塊板坯都有一個已知的最小加工時間，由板坯的入爐溫度、鋼種、重量等因素決定。板坯在爐內的停留時間達到最小加工時間即可認為達到工藝要求的軋制溫度。

(4)已入爐板坯在軋制之前不允許在加熱爐外停留，必須在加熱爐中保溫等待。

(5)由于熱軋機停機造成的損失很大，因此不允許熱軋機停機等待。

(6)當爐內出現冷熱混坯現象時，需要根據過渡板坯的溫度在混裝處空爐以減輕混裝的影響。

目前在生產實際中常用的調度方法是按照板坯的軋制順序依爐號順序依次向各加熱爐分配板坯，這種調度方法能夠保證向熱軋機持續供應板坯，但不能保證板坯在加熱爐內的加工時間最短，也不能保證成品的質量。

2.2 數學模型

為便于描述，假設:

(1) 連鑄和熱軋間設有多臺性能相同的加熱爐，板坯的設備指派不受限制;

(2) 加熱爐足夠長，不存在爐容限制。

定義符號和變量如下:

i為加熱爐序號，I為加熱爐集合，i∈I = {1，2，…，m｝，m為加熱爐的臺數;

j為板坯序號，J為板坯集合，j∈J = {1，2，…，n｝，不失一般性，對各板坯按軋制先后順序編號;

Mi為在第i臺加熱爐上加工的板坯序號集合， Mi(k)表示第k塊進入加熱爐i中的板坯的序號，1≤k ≤ |Mi|，i∈I;

dik為加熱爐i中相鄰板坯Mi(k)和Mi(k + 1)的入爐時間間隔，取決于相鄰板坯的入爐溫度;

pj，pj*分別為板坯j的實際加工時間和最小加工時間;

sj，cj分別為板坯j的入爐時間和出爐時間;

hj為板坯j的軋制時間;

xij = 1，若指派板坯j到加熱爐i，i∈I，j∈J0，否則

混裝工藝下并行加熱爐群調度的數學模型描述如下:

min Z2 =(pj - pj*)(1)

s.t.pj ≥ pj*，?坌j∈J，(2)

cj - sj = pj，?坌j∈J (3)

s ≥s+ dik，1 ≤ k < |Mi|(4)

c ≥c+ dik，1 ≤ k < |Mi|(5)

xij = 1，?坌j∈J(6)

ck+1 - ck = hk，?坌k，k + 1∈J(7)

xij ={0，1｝，?坌i∈I，j∈J(8)

目標函數(1)表示最小化板坯達到工藝要求后的加工時間;式(2)表示每塊板坯的實際加工時間不得少于其最小加工時間;式(3)表示板坯在加工過程中不允許中斷;式(4)、式(5)表示在同一加熱爐里加工的板坯必須先熱軋的先進入加熱爐，且在冷熱坯混裝處空爐;式(6)表示每塊板坯都被分配且只被分配到一個加熱爐里加工;式(7)表示板坯在熱軋機空閑之前一直在加熱爐里保溫停留，且熱軋機不允許停機等待;約束(8)為變量取值約束。

3求解算法

由加熱爐調度的問題特征可知，確定了板坯的分配策略亦即確定了各臺加熱爐中板坯加工的先后順序。因此其關鍵問題在于板坯的分配。由于加熱爐調度具有任務指派問題NP-完全的性質，因此難以在多項式時間內找到一個最優調度方案。為了滿足生產需要，在短時間內找到滿意解，本文采用粒子群算法求解，并結合鄰域搜索技術提高收斂速度。

3.1 粒子群算法

粒子群算法源于對鳥群或魚群群體行為的研究，通過初始化一群隨機粒子，迭代找到最優解。在每一次迭代中，粒子通過跟蹤粒子本身的最優解和整個種群的歷史最優解并根據以下公式更新自己的速度和位置:

vid(t + 1) = wvid(t) + c1r1(pid - xid(t)) + c2r2(pgd - xid(t))(9)

xid(t + 1) = xid(t) + vid(t + 1)(10)

式中，pid為粒子i所經過的最優位置，pgd為當前全局粒子所經過的最優位置;w為慣性權重;c1和c2為學習因子;r1和r2是[0，1]之間的隨機數。

3.1.1 編碼和解碼

對于任務指派問題，常用的方法是構造成2n維(n為任務數)的解空間，并對這2n維采用統一的編碼方法。考慮到加熱爐調度問題的特殊性，本文將此編碼方式簡化，僅需構造n維的解空間。在求解加熱爐調度問題時采用的是面向機器(加熱爐)的取整解碼方法。假設軋制計劃中的板坯序列為:(q1，q2，…，qj，…，qn)，第i個粒子的位置為: (xi1，xi2，…，xij，…，xin )，在粒子的初始化階段，xij在(1，m + 1)隨機取值，通過取整操作得到的整數即為加工該板坯的加熱爐號，由此即可得到各板坯的分配策略以及各加熱爐中板坯的加工順序。

3.1.2適應值函數

由于軋制計劃內第一塊板坯的出爐時間c1和各板坯的軋制時間hj已知，因此根據公式(7)可以得到所有板坯的出爐時間cj。記sj* = cj - pj*為板坯j的最遲入爐時間，由于各板坯的最小加工時間pj*已知，則所有板坯的最遲入爐時間可以確定。不難看出 (pj - pj*) =(sj* - sj)，因此，目標函數等價于Z = (sj* - sj)。為便于計算，本文將Z′作為適應值函數，計算方法如下:若在當前分配策略下，板坯j是分配到加熱爐i的第k塊板坯，那么從軋制計劃的最后一塊板坯開始，依公式sj = min{sj*，s- dik｝確定板坯 j的入爐時間;當所有板坯的入爐時間確定后，計算適應值Z′。

3.1.3停止條件

預先設定一個迭代次數，當算法運行到此迭代次數時停止，取停止時當前種群中的最優解作為結果輸出。

3.2 鄰域搜索

為了加快收斂速度，減少運算時間，本文將鄰域搜索算法與之結合，利用2-opt鄰域搜索的思想，對每代更新后的粒子進行2-opt操作。具體步驟如下:

Step 1: 隨機選取粒子中的兩塊板坯，判斷這兩塊板坯是否被分配到相同的加熱爐中加工，若是，則重復此操作，否則轉Step 2;

Step 2: 將兩塊板坯所在的加熱爐號互換，并對新粒子進行評價，若有改進則用交換后的新粒子代替舊粒子，否則保持原粒子。

Step 3: 達到預先設置的最大交換次數后，算法終止，否則轉Step 1。

3.3 算法步驟

Step 1: 初始化粒子群。

a) 設置群體規模P，慣性權重w，學習因子c1、c2，最大允許迭代次數和交換次數等參數;

b) 初始化粒子位置，隨機產生P個n維且分量值均在(1，m + 1)的向量，得到板坯在加熱爐的分配策略;

c) 初始化粒子速度，隨機產生P個初始速度。

Step 2: 計算適應值。

根據3.1.2節的方法計算每種分配策略下所有板坯的入爐時間和加工時間，并計算粒子的適應值。

Step 3:鄰域搜索。

按照3.2節的步驟，隨機選取各粒子中的某兩個分量互換，并評價新解，若有改進則用新解代替舊解，直到達到預先設定的交換次數。

Step 4: 更新粒子群。

a) 更新最優值，對于每個粒子，將其適應值與經歷過的最好位置的適應值比較，若更好，則更新該位置作為pid;并將每個粒子的歷史最優適應值與群體內所經歷的最好位置的適應值比較，若更好，則更新該位置作為pgd;

b) 根據公式(9)、(10)更新粒子的速度和位置。

Step 5:停止準則。

判斷是否滿足最大迭代次數，若滿足，則算法終止，輸出當前種群中的最優解;如不滿足，則轉Step 2。

4數據實驗

本文采用MATLAB編程實現加熱爐調度算法。算法的參數設置為:種群規模為150，迭代次數為50次，慣性權重采用時變權重，變化范圍為0.1~0.9，交換次數為5。軋制計劃根據某大型鋼廠的生產實際數據得到。其中，軋制單元的板坯數為60~100，每塊板坯的最小加工時間已知，熱坯為110~120min，冷坯為150~160min。混裝處空爐數據采用文獻[1]、[2]中仿真得到的數據。假設加熱爐的臺數分別為2，3，4。對于每組數據，用本文算法各運行10次，記錄最好結果、最差結果和平均值。仿真結果與實際生產調度方法的結果見表1。

表1中9組數據的仿真結果均表明，應用基于粒子群和鄰域搜索的混合算法求解混裝工藝下的加熱爐調度問題，結果均優于人工調度方法。且9組數據的運行時間都不超過1分鐘，完全可以滿足實際應用的需要。

另外，對于相同的軋制計劃，若加熱爐的臺數不同，目標函數值可能相差很大，這表明適當增加加熱爐的臺數可以避免過渡熱坯的長時間加熱，提高成品質量。

5結束語

本文在綜合考慮混裝工藝的基礎上建立了并行加熱爐調度問題的數學模型，利用粒子群算法制定加熱爐的裝坯策略，并利用2-opt的方法進行鄰域搜索，以加快收斂速度，提高粒子群的質量。仿真實驗表明，與傳統的裝坯策略相比，本算法得到的調度方案減輕了混裝的影響，縮短了板坯的在爐時間，優化了加熱爐的生產調度。

主要參考文獻

[1] 李婧， 李蘇劍， 顧云舟. 基于加熱爐爐群生產物流仿真系統的熱送熱裝[J]. 北京科技大學學報， 2001， 23(3): 368-372.

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

[3] Lixin Tang，Yufang Zhao. Scheduling a Single Semi-continuous Batching Machine[J]. Omega，2008，36(6):992-1004.

[4] 趙玉芳， 唐立新. 一種帶有鏈約束的連續型批處理機調度問題[J]. 控制與決策， 2008， 23(6): 677-680.

[5] 寧樹實， 王偉，等. 鋼鐵生產中的加熱爐優化調度算法研究[J]. 控制與決策， 2006， 21(10): 1138-1142.

Hybrid PSO Algorithm for Reheating Furnaces Scheduling Problems in Mixing Charge

ZHAO Yan-yan， WANG Bai-lin

(School of Economics and Management， University of Science and Technology Beijing， Beijing 100083， China)

Abstract: Considering the way of uncharged between the cold and hot slabs to ease the impact of mixing charge， a model of parallel reheating furnaces scheduling in mixing charge is established and it takes improving the quality of final products and reducing the energy consumption of reheating furnaces as the goal. Besides， a hybrid algorithm based on PSO and local search is developed and simulation results verify the feasibility and the validity.

Key words: Reheating Furnaces Scheduling; Parallel Machines; Particle Swarm Optimization; Local Search

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文