鋼鐵企業(yè)坯料設(shè)計問題模型及算法

施燦濤 陳盈 曹小軍 李鐵克 杜景紅 席陽

[摘要]針對鋼鐵企業(yè)的坯料設(shè)計問題，建立了數(shù)學(xué)模型。針對模型特點，以標(biāo)準(zhǔn)粒子群算法為求解框架，通過線性加權(quán)法將多目標(biāo)化為單一目標(biāo)，引入基于三角函數(shù)的動態(tài)參數(shù)選擇方法和鄰域搜索以提升求解效率，設(shè)計了鄰域搜索機制以提升求解效果。通過對比實驗對算法的有效性進行了驗證。

[關(guān)鍵詞] 鋼鐵生產(chǎn)；坯料設(shè)計；粒子群算法；鄰域搜索；動態(tài)參數(shù)選擇

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 23. 034

[中圖分類號]TP27[文獻標(biāo)識碼]A[文章編號]1673 - 0194（2012）23- 0053- 04

1引言

在市場需求日益多樣化和鋼鐵生產(chǎn)工藝逐步柔性化的影響下，大規(guī)模定制生產(chǎn)已經(jīng)成為鋼鐵企業(yè)的主要發(fā)展方向[1-3]。在大規(guī)模定制生產(chǎn)中，坯料設(shè)計處于連接客戶需求和企業(yè)生產(chǎn)計劃的核心地位。在鋼鐵企業(yè)的生產(chǎn)流程中，鋼水通過精煉和連鑄等工藝形成各類鋼坯，鋼坯通過軋制形成各類鋼鐵產(chǎn)品。所謂坯料設(shè)計就是針對需求各異的客戶訂單，在滿足生產(chǎn)工藝要求的前提下，將基于量的產(chǎn)品需求轉(zhuǎn)化為基于件次的坯料需求，以便于生產(chǎn)計劃的編制，實現(xiàn)客戶需求與生產(chǎn)組織的統(tǒng)一。

客戶訂單中對鋼鐵產(chǎn)品的要求主要有交貨日期、鋼種、重量、規(guī)格等，針對不同的訂單要求，國內(nèi)外學(xué)者提出了各自的問題模型以及求解方法。針對重量要求為固定值，客戶訂單分配過程中有最小重量限制的問題，張文學(xué) 等[4]建立了以最小化板坯數(shù)量為目標(biāo)的約束滿足模型，給出了變量選擇策略和值選擇策略，提出了基于約束滿足技術(shù)的求解算法。針對重量要求為固定值，寬度和厚度要求為區(qū)間值的問題，Lee Kangbok等[5]將坯料設(shè)計問題歸結(jié)為基于區(qū)間圖的團劃分問題，并提出了相應(yīng)的算法進行求解。席陽 等[6]建立了最小化板坯數(shù)量和總盈余量的多目標(biāo)板坯設(shè)計模型，并提出了一種兩階段算法對問題進行求解，其中第一階段實現(xiàn)板坯數(shù)量最小的約束，第二階段在滿足第一階段的基礎(chǔ)上使板坯的盈余量最?。徊⒃谖墨I[7]中增加了最小加工重量的約束條件，并用粒子群算法對問題模型進行了求解。針對客戶訂單重量需求為固定值的問題，Antoine Gargani等[8]提出了基于全局和邏輯約束的，將具體的變量和值選擇策略植入到深度搜索的問題求解模型，并通過使用大規(guī)模鄰域搜索提升了求解速度。Hentenryck P. Van等[9]提出了一種打破對稱性的搜索方法，此方法在不使用大規(guī)模鄰域搜索的基礎(chǔ)上，保證了求解方法的完整性和高效性。Dawand Milind等[10]建立了以板坯數(shù)量和總盈余量最小為優(yōu)化目標(biāo)的數(shù)學(xué)模型，并提出了一種基于匹配和裝箱的啟發(fā)式算法對問題進行求解。針對訂單要求重量和寬度均為區(qū)間值的問題，張英杰 等[11]提出了基于合同—板坯矩陣的啟發(fā)式算法。

本文考慮訂單需求重量和規(guī)格為區(qū)間值，且具有最小加工重量限制的坯料設(shè)計問題，建立兼具一般性和特殊性的數(shù)學(xué)模型，采用改進的粒子群算法進行求解。

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

對鋼鐵企業(yè)而言，客戶訂單對產(chǎn)品提出的要求有鋼種、重量、最小加工重量、規(guī)格、交貨日期等。對于不同類型的鋼坯，其規(guī)格也有所不同，比如圓坯規(guī)格為直徑，矩形坯則為寬度和厚度。坯料設(shè)計通常考慮鋼坯與鋼材之間的規(guī)格對應(yīng)，鋼種和交貨日期等不在設(shè)計范圍內(nèi)，所以本文中客戶訂單對產(chǎn)品的約束主要包括訂單需求重量、最小加工重量、訂單規(guī)格3個方面，具體如下：

（1）客戶訂單的需求重量為區(qū)間值；

（2）最小加工重量為固定值，此值的設(shè)置是為了滿足工藝要求；

（3）客戶訂單的規(guī)格要求為區(qū)間值。

坯料設(shè)計問題應(yīng)追求以最少的坯料供應(yīng)滿足最多的訂單需求，體現(xiàn)精益制造和精益管理的理念。

為了便于描述，對符號定義如下：

集合和索引

i：訂單序號，i∈N+；j：坯料序號，j∈N+；O：訂單集合，O={1，2，…，i，…，m}；S：坯料集合，S={1，2，…，j，…，n}。

參數(shù)

Gi：訂單i的需求重量，為區(qū)間值，Gi=[ai，bi]，ai，bi∈Z+；Wi：訂單i的需求規(guī)格，為區(qū)間值，Wi=[li，ri]，li，ri∈Z+；mi：訂單i要求的最小加工重量，mi∈Z+；W：鑄造臨界值，即坯料的最大重量；Ωi：訂單i的可容多元坯集合；Ω：所有訂單的可容多元坯集合元素的集合。

變量

xij：坯料j中包含的訂單i的重量，xij∈Z+；rwij：訂單i在坯料j中的實際規(guī)格，rwij∈Z+。

2.3 模型建立

基于上述問題描述和符號說明，建立坯料設(shè)計問題的多目標(biāo)優(yōu)化模型[BD]如下：

maxF1=■■xij（1）

minF2=■（2）

s.t.

mi≤xij≤W，？坌i∈O，？坌j∈S（3）

0≤■xij≤W，？坌j∈S（4）

ai≤■xij≤bi，？坌i∈O（5）

li≤rwij≤ri，？坌i∈O，？坌i∈S（6）

rwuj=rwvj，？坌u，v∈O，Wu∩Wv≠？準(zhǔn)（7）

上述數(shù)學(xué)模型中，目標(biāo)函數(shù)（1）是最大化坯料中包含的所有訂單的重量和；目標(biāo)函數(shù)（2）是最小化坯料的數(shù)量；約束（3）是坯料j中包含的訂單i的重量在訂單i要求的最小加工重量和鑄造臨界值之間；約束（4）是每個坯料中包含的所有訂單的分配重量之和小于鑄造臨界值；約束（5）是訂單i分配到坯料j中的重量要在該訂單的要求重量區(qū)間中；約束（6）是訂單i中的設(shè)計規(guī)格必須在其要求的寬度區(qū)間內(nèi)；約束（7）是分配到同一塊坯料中的各個訂單的規(guī)格應(yīng)相同。

3模型分析

根據(jù)坯料中包含訂單的數(shù)目，將坯料劃分成兩類：單一坯和多元坯。單一坯是指此坯料中僅僅包含一個訂單并且訂單在此坯料中的重量恰恰為鑄造臨界值。多元坯是指此坯料中包含一個或是多個訂單并且所包含訂單要求的重量之和可以小于或是等于鑄造臨界值。通過定義可知，多元坯在滿足訂單的前提下，可能會產(chǎn)生盈余，此盈余可以作為庫存。

多元坯的最大數(shù)目等于訂單的數(shù)量，且每種多元坯的規(guī)格是固定的，即為將訂單按照需求規(guī)格區(qū)間的上限排列后，相應(yīng)序號訂單上限的數(shù)值。很顯然，一種坯料并不能包含全部的訂單，一個訂單也不能分配到任意的坯料中。本文定義訂單可以分配到的多元坯的集合為訂單的可容多元坯集合。令r0=l1，則訂單i的可容多元坯集合Ωi可定義如下：

Ωi={Sj|li≤rj，ri≥rj-1，？坌i∈O，？坌j∈S}

模型[BD]為多目標(biāo)優(yōu)化模型，因此需要按照一定的規(guī)則將兩個函數(shù)合二為一。通常，將多目標(biāo)劃一的方法有線性加權(quán)法、理想點法、功效系數(shù)法等，本文選擇簡單實用的線性加權(quán)法。其基本思想是根據(jù)各個分目標(biāo)的重要程度和數(shù)量級給出一組加權(quán)因子，取經(jīng)過無量綱化的分目標(biāo)函數(shù)和相對應(yīng)加權(quán)因子的線性組合，構(gòu)成一個新的統(tǒng)一的目標(biāo)函數(shù)。同時，由于一組訂單的單一坯的數(shù)量是固定的，故目標(biāo)函數(shù)F1化為最大化多元坯處理重量，F(xiàn)2轉(zhuǎn)化為最小化多元坯數(shù)目。

目標(biāo)函數(shù)F1=■■xij，進行無量綱化后轉(zhuǎn)化為：

F1*=■■

目標(biāo)函數(shù)F2=■ ，進行無量綱化為：

F2*=■

按照決策者的偏好和企業(yè)的實際情況給兩個目標(biāo)函數(shù)賦權(quán)重ω1和ω2，且ω1+ω2=1，因此原問題的目標(biāo)函數(shù)可以轉(zhuǎn)化為如下的單目標(biāo)函數(shù)：

maxF=F1*ω1-F2*ω2，i∈O，j∈Ω（8）

4求解算法

此問題是一個具有團劃分問題NP完全性質(zhì)的問題，因此本文選用粒子群算法（Particle Swarm Optimization， PSO）為求解方法的核心，以期在合理時間內(nèi)獲得滿意解。粒子群算法源于對鳥群捕食行為的研究，其基本思想是通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解。作為一類隨機性較強的群體智能算法，粒子群算法的應(yīng)用需要解決幾個主要問題，即編碼方案、初始化方案、種群更新機制和終止條件。此外，為了更有效地求解坯料設(shè)計問題，本文有針對性地設(shè)計了鄰域搜索機制以提升求解效果，采用了動態(tài)參數(shù)選擇機制以提升求解效率。

4.1 編碼方案

編碼方案是一種將問題空間映射到具有某種結(jié)構(gòu)的表示方法，根據(jù)前述定義，可以將所有訂單的多元坯集合中元素的順序排列作為粒子的編碼：（（x11…x1j）（x21…x2j）…（xm1…xmj））。

4.2 初始化粒子群

首先將訂單中包含的單一坯的數(shù)量求解出來，并更新訂單中的要求重量區(qū)間為Gi*=[ai*，bi*]，按照上述規(guī)則進行粒子編碼，最后對粒子賦初始值（iter=0）。其中：

ai*=ai-W ■，ifai-W ■ >00，else（9）

bi*=bi-W ■（10）

速度的初始值為：

vhij0=rand（vmax）（rand表示[0，1]之間的隨機數(shù)）（11）

4.3 種群更新

一般情況下適應(yīng)度應(yīng)為目標(biāo)函數(shù)的值，但在本文討論的問題中，粒子更新過程中產(chǎn)生的新的位置可能不滿足約束條件，所以增加懲罰值punish，對不滿足的粒子位置進行懲罰，懲罰值的計算公式如下：

punish=κ■xij-bi*（xhij-mi）+（12）

其中（x）+=max（x，0），κ為一個很大的實數(shù)。加上懲罰值的適應(yīng)度計算函數(shù)為：

Fitness（xhij）=F1ω1-F2ω2+punish （ω1+ω2=1）（13）

本文中用pbesthiter表示第h個粒子在第iter代的最優(yōu)位置；用gbestiter表示截止到第iter代，整個粒子群經(jīng)歷的最優(yōu)位置。h∈[1，H]，h∈N，H為種群粒子數(shù)量。iter≤maxiter，maxiter為算法的最大迭代次數(shù)。其中：

pbesthiter=pbesthiter-1，if（Fitness（xhiter）

gbestiter=pbesthiter-1，if（Fitness（gbestiter-1）

4.4 鄰域搜索

鄰域的確定根據(jù)下面兩個原則：

（1）當(dāng)前粒子附近可以使坯料處理總重量增加的粒子；

（2）當(dāng)前粒子附近不增加坯料數(shù)目的粒子。

上述兩個規(guī)則產(chǎn)生的粒子集合的交集即為當(dāng)前粒子的鄰域，鄰域若不為空集，則從鄰域中任取一個元素作為鄰域粒子，用nxhiter表示第h個粒子在第iter代的鄰域粒子，并將鄰域粒子nxhiter的取值賦給當(dāng)前粒子xhiter，然后進行全局和局部最優(yōu)位置的更新。

4.5 參數(shù)選擇

速度和位置的更新，按照如下公式：

vhij（t+1）=uvhij（t）+c1rand（pbesti-xhij（t））+c2rand（gbesti-xhij（t））（16）

xhij（t+1）=xhij（t）+vhij（t+1）（17）

其中，i∈O，j∈Ωi；u為慣性因子，是使粒子保持著運動慣性，具有搜索新的區(qū)域的能力；c1和c2是學(xué)習(xí)因子，分別代表將每個粒子推向自身最優(yōu)位置pbesti和全局最優(yōu)位置gbesti的加速權(quán)值；通過調(diào)整慣性因子和學(xué)習(xí)因子可以改變算法的全局和局部搜索能力。vmax為最大速度，當(dāng)更新后的速度絕對值超過最大速度時，正數(shù)取最大速度，負(fù)數(shù)取最大速度的相反數(shù)。參數(shù)u、c1和c2取值參照參考文獻[12]中提供的方法，即通過三角函數(shù)動態(tài)改變參數(shù)的值，使結(jié)果與實際搜索過程特點更加吻合。

4.6 終止條件

在進化類算法中，終止準(zhǔn)則一般為預(yù)先設(shè)定一個最大迭代次數(shù)或是規(guī)定適應(yīng)值穩(wěn)定的代數(shù)。本文中，設(shè)置最大迭代次數(shù)maxiter，每更新一代粒子，都檢查是否達到了終止條件，若iter=maxiter，則算法結(jié)束，輸出gbestiter和Fitness（gbestiter），否則繼續(xù)進行更新。

5數(shù)據(jù)實驗

算法參數(shù)設(shè)置為maxiter=200，H=150，vmax=20，ω1=0.7；訂單數(shù)據(jù)源自文獻[7]。算法程序由Eclipse Java EE IDE for Web Developers，Version： Helios Service Release 1實現(xiàn)，實驗環(huán)境：CPU為AMD Turion（tm） X2 Dual-Core Mobile RM-72 （2 CPUs），2.1GHz，3.00G RAM。

本文算法（BD-PSO）實驗結(jié)果與與文獻[7]算法（SD-PSO）結(jié)果對比如表1所示，其中，處理百分比等于多元坯處理的重量除以訂單要求重量上限減去單一坯重量。

從與文獻[7]中算法的對比結(jié)果可以看出，本文的優(yōu)化算法在處理單一坯和多元坯中都有明顯優(yōu)勢，但多元坯存在剩余，這將是下一步研究的優(yōu)化方向。

6結(jié)論

本文在考慮鋼鐵企業(yè)客戶訂單需求和工藝能力的基礎(chǔ)上，建立了坯料設(shè)計問題的數(shù)學(xué)模型。針對模型特點，以標(biāo)準(zhǔn)粒子群算法為求解框架，通過線性加權(quán)法將多目標(biāo)化為單一目標(biāo)，并引入基于三角函數(shù)的動態(tài)參數(shù)選擇方法和鄰域搜索，提高算法的求解效率。最后的數(shù)據(jù)實驗結(jié)果表明，本文提出的模型和求解方法可行、有效。

主要參考文獻

[1]劉相華，王國棟，杜林秀，等. 鋼材性能柔性化與柔性軋制技術(shù)[J]. 鋼鐵，2006，41（11）：32-36，62.

[2]A Balakrishnan，J Geunes. Production Planning with Flexible Product Specifications： An Application to Specialty Steel Manufacturing [J]. Operations Research， 2003， 51（1）： 94-112.

[3]周世春，丁建華，陳超，等.“大規(guī)模定制”生產(chǎn)模式在鋼鐵企業(yè)的應(yīng)用實踐[J]. 中國工程科學(xué)， 2006， 8（3）： 1-6.

[4]張文學(xué)，李鐵克. 基于約束滿足的板坯設(shè)計模型與求解方法[J]. 北京科技大學(xué)學(xué)報， 2011（5）：641-646.

[5]Lee Kangbok， Chang Soo Y， Hong Yushin. Continuous Slab Caster Scheduling and Interval Graphs[J]. Production Planning and Control， 2004， 15（5）：495-501.

[6]席陽， 李鐵克. 針對固定重量板坯的板坯設(shè)計優(yōu)化算法[J]. 北京科技大學(xué)學(xué)報，2008，30（10）：1179-1183.

[7]席陽， 李鐵克. 基于粒子群算法求解區(qū)間值板坯設(shè)計優(yōu)化問題[J]. 計算機工程與應(yīng)用，2008（3）：205-209.

[8]Antoine Gargani， Philippe Refalo. An Efficient Model and Strategy for the Steel Mill Slab Design Problem[C]//Proceeding of the 13th International Conference on Principles and Practice of Constraint Programming. Springer-Verlag，2007：77-89.

[9]P V Hentenryck，L Michel. The Steel Mill Slab Design Problem Revisited[C]//Proceedings of CPAIOR，2008： 377-381.

[10]Dawande Milind， Kalagnanam Jayant， Lee Ho Soo， et al. The Slab-Design Problem in the Steel Industry [J]. Interfaces， 2004， 34（3）： 215-225.

[11]張英杰， 席陽， 李鐵克. 考慮屬性區(qū)域值的板坯設(shè)計模型與算法[J]. 鑄造技術(shù)，2008，30（7）：945-948.

[12]Zhang Wenxue， Li Tieke， Shi Cantao. Dynamic Parameter Selection Based on Trigonometric[C]//Proceedings of the 2010 Third International Joint Conference on Computational Science and Optimization，2010.