黃旭

摘要：分析了熱軋生產(chǎn)作業(yè)計(jì)劃編制問題，基于車輛路徑問題，建立以軋制單元數(shù)量為目標(biāo)的熱軋批量計(jì)劃，模型考慮了實(shí)際生產(chǎn)中的生產(chǎn)約束和生產(chǎn)目標(biāo)，并針對建立的模型提出了一個基于改進(jìn)NSGA-II和禁忌搜索算法的混合算法，采用了支配強(qiáng)度和自適應(yīng)個體差異性度量的方法進(jìn)行優(yōu)勢種群選擇，提高了種群質(zhì)量，并加快算法收斂，并結(jié)合禁忌搜索算法來防止結(jié)果陷入局部最優(yōu)。實(shí)驗(yàn)結(jié)果表明模型和算法都是有效的。

關(guān)鍵詞：生產(chǎn)調(diào)度;熱軋批量計(jì)劃;車輛路徑問題;NSGA-II;禁忌搜索

中圖分類號：TP3? ? ? ? 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2020）35-0220-02

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

1 引言

隨著我國鋼鐵行業(yè)的發(fā)展，現(xiàn)在面臨著產(chǎn)能過剩、供需不平衡、產(chǎn)品創(chuàng)新力不夠、市場競爭激烈等問題，同時客戶的需求呈現(xiàn)多樣化、交貨周期短、要求高的特點(diǎn)。所以鋼鐵企業(yè)必須提高管理水平和信息自動化水平，降低能耗、提高生產(chǎn)效率和產(chǎn)品質(zhì)量。熱軋調(diào)度是其中的核心，已經(jīng)成為一個重要的研究課題。關(guān)于熱軋批量計(jì)劃國內(nèi)外已經(jīng)有很多的研究。文獻(xiàn)[1]建立多旅行商模型（MTSP），基于一種并行策略編制計(jì)劃，用改進(jìn)的遺傳算法（MGA）求解;文獻(xiàn)[2]將軋制單元數(shù)量作為目標(biāo)函數(shù)，考慮寬度相同的板坯進(jìn)行連續(xù)軋制的最大公里數(shù)的約束，采用遺傳算法求解，并用結(jié)合禁忌算法來防止陷入局部最優(yōu);文獻(xiàn)[3]在收集獎金車輛路徑問題基礎(chǔ)上得到熱軋生產(chǎn)作業(yè)計(jì)劃模型，在蟻群優(yōu)化算法的基礎(chǔ)上，加入單向插入、2-opt算法來增加局部搜索過程。文獻(xiàn)[4]建立了以提高平均單元計(jì)劃軋制長度和熱裝比為目標(biāo)的數(shù)學(xué)模型，提出了一種兩階段變鄰域搜索算法解決軋制批量計(jì)劃問題。

2 問題描述

2.1 工藝約束

熱軋過程中板坯會對軋輥有磨損，所以需要對軋輥進(jìn)行更換。使用相同工作輥軋制的板坯稱為一個軋制單元計(jì)劃，多個單元計(jì)劃可以組成一個軋制批量計(jì)劃。熱軋批量計(jì)劃是在已經(jīng)形成的連鑄預(yù)計(jì)劃基礎(chǔ)上，以連鑄過來的還未生產(chǎn)的虛擬板坯與板坯庫的實(shí)物板坯為單位，在滿足實(shí)際生產(chǎn)工藝約束的前提下，追求批量綜合評價函數(shù)最優(yōu)結(jié)果情況下的一類組合優(yōu)化問題。熱軋是通過軋輥的擠壓作用使高溫板坯成為符合要求的鋼卷或鋼板。軋輥的性能對于決定產(chǎn)品的質(zhì)量、運(yùn)行成本和生產(chǎn)能力起著重要的作用。編制計(jì)劃的時候，根據(jù)軋制規(guī)程，最小化對軋輥的磨損，來排列順序。高效的熱軋編制計(jì)劃可以極大提高生產(chǎn)效率和降低成本。

一個完整的軋制單元由燙輥材和主體材組成，板坯在編制寬度上呈現(xiàn)“烏龜殼”形狀。燙輥材主要是用來預(yù)熱軋輥，數(shù)量一般不多，寬度呈遞增變化，部分編制規(guī)程為：板坯的硬度下限為1，上限為2;相鄰兩塊寬度差在規(guī)定范圍內(nèi)，且不反跳;不能安排表面質(zhì)量、板形要求高的合同。主體材是軋制的主要組成部分，寬度呈遞減變化。部分編制規(guī)程為：計(jì)劃最大公里數(shù)和同寬軋制公里數(shù)限制在一定范圍內(nèi)，規(guī)定主體材之間寬度正跳和反跳最大跳躍量;相鄰帶鋼硬度組差最大值為2。

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

本文針對熱軋帶鋼軋制批量計(jì)劃問題建立了多目標(biāo)VRP模型。假設(shè)N塊板坯被安排到K個軋制單元中，每個軋制單元里面都有虛擬板坯0作為起始和結(jié)束，來分隔各個單元計(jì)劃，可以把N塊板坯看作N個顧客，將K個軋制單元看成K輛車輛。運(yùn)輸費(fèi)用為各個軋制單元內(nèi)板坯之間的總的跳躍懲罰值。

[f1=mink=1Ki∈Ij∈I，j≠ipijsisjrijk+k=1Ki∈Ij∈I，j≠ip'ijs'is'jrijk]? ? ? ? （1）

[f2=minK]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）

[j∈Nk＼irijk=cik，?i∈Nk，k=1，...，K]? ? ? ? ? ? ? ? ? ? ? （3）

[i∈Nk＼jrijk=cjk，?j∈Nk，k=1，...，K]? ? ? ? ? ? ? ? ? ? ? ?（4）

[c0k=1，k=1，...，K]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （5）

[k=1Kcik≤1，i∈I]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（6）

[Lmin≤i∈Ilisicik≤Lmax，?k∈1，2，...，K]? ? ? ? ? ? ? ?（7）

[j∈diklj≤R，i∈Nk，k=1，...，K]? ? ? ? ? ? ? ? ? ? ? ? ? ?（8）

[-Δw-max≤wj-wisisjrijk≤Δw+max，?i，j∈I，?k∈1，2，...，K]

[（hj-hi）sisjrijk≤Δhmax，?i，j∈I，?k∈1，2，...，K]

[（gj-gi）sisjrijk≤Δgmax，?i，j∈I，?k∈1，2，...，K]? ? ? ? ? ? ?（9）

模型中的符表示如下：

（1）記N為全部板坯集合，[i]表示板坯序號，[i=0] 為公共虛擬板坯，[k]表示第[k]個軋制單元，[Nk∈N]為被編入軋制單元計(jì)劃[k]的板坯集合;

（2）[wi]，[gi]和[hi]分別為板坯[i]的寬度、厚度和硬度，[Δw-max]，[Δw+max]，[Δgmax]和[Δhmax]分別為熱軋軋制規(guī)范所允許的相鄰板坯的最大寬度反跳、寬度正跳、厚度跳躍和硬度跳躍，[pij=pwij+pgij+phij+ptaij+pthij] 為總的懲罰值，[p0j=pj0=0] ，[pii=∞]，[i∈N];

（3）[rijk=1]，表示在第[k]個軋制單元里板坯[i]之后軋制板坯[j]，否則，[rijk=0]。[cik=1]表示板坯[i]被編入第[k]個軋制單元，否則，[cik=0]。軋制單元[k]內(nèi)[i]是主體材，則[dikz=1]，否則，[dikz=0];

（4）[li]為第[i]塊板坯的長度，[Lk]為軋制單元[k]的最大軋制里程;

（5）[Nm={i1，...，iNm}]為編入計(jì)劃，同寬系列[m]連續(xù)軋制的最長板坯序列，[Rm]為其最大連續(xù)軋制長度。

公式（1）和（2）表示目標(biāo)函數(shù)，為最小化跳躍懲罰值、最小化軋制單元數(shù)量;公式（3）表示在已經(jīng)安排的軋制計(jì)劃中板坯[i]后有且只有一塊板坯;公式（4）表示在已經(jīng)安排的軋制計(jì)劃中板坯[j]前有且只有一塊板坯;公式（5）表示虛擬板坯0一定被安排到每個軋制單元;公式（6）表示板坯最多只能被安排進(jìn)一個軋制單元;公式（7）表示每個軋制單元計(jì)劃主體材的最小軋制長度限制和最大軋制長度限制;公式（8）表示每個軋制單元計(jì)劃內(nèi)同寬主體材板坯軋制長度限制;公式（9）表示主體材板坯間的板寬、軋厚、硬度、出爐溫度、終軋溫度的跳躍量約束。

3 求解算法

采用改進(jìn)的NSGA-II算法結(jié)合啟發(fā)式算法對熱軋批量計(jì)劃優(yōu)化問題進(jìn)行求解。

3.1 主體材計(jì)劃編制

在一個軋制單元里，主體材占絕大多數(shù)，用改進(jìn)的NSGA-II算法求解。

編碼：

假設(shè)有[N]塊主體材板坯，安排[K]個軋制單元，根據(jù)熱軋調(diào)度問題的特點(diǎn)，采用自然數(shù)編碼方式，安排[K+1]個虛擬板坯0添加進(jìn)軋制計(jì)劃，這[K+1]個板坯是為了分開不同的軋制單元，第[i]塊板坯的板坯號用自然數(shù)編號，隨機(jī)排[N+K+1]個不同的自然數(shù)，得到了一個解。

解碼：

利用分割符0，還原各條子路徑。

算法步驟：

1）設(shè)置種群規(guī)模NP，截止進(jìn)化代數(shù)[Gmax]，根據(jù)設(shè)置的種群規(guī)模的大小，產(chǎn)生NP個個體作為初始種群;

2）然后對初始種群進(jìn)行非支配型排序。用常規(guī)遺傳算法的選擇，交叉，變異操作產(chǎn)生第一代子代種群（常見的選擇算子包括輪盤賭選擇法）;

3）從第二代開始，將父代和子代種群混合，組成新一代種群;

4）采用快速非支配排序法對種群中的個體進(jìn)行分級排序，分級之后的每個非支配層個體，對它們進(jìn)行擁擠度計(jì)算，通過選取非支配程度高和擁擠度低的個體來組成新的父代種群;

5）采用引入自適應(yīng)的交叉概率[pc]和變異概率[pm]的模擬二進(jìn)制交叉及多項(xiàng)式變異方法，再對變異的個體采用禁忌搜索算法，選擇種群中的優(yōu)質(zhì)個體進(jìn)入新一代種群;

6）若達(dá)到進(jìn)化終止條件，則停止循環(huán)，輸出結(jié)果，否則轉(zhuǎn)至步驟2。

3.2 燙輥材編碼

采用啟發(fā)式規(guī)則進(jìn)行燙輥材計(jì)劃編制，步驟如下：

Step1：讀取當(dāng)前軋制批次所有軋制單元;

Step2：對于當(dāng)前軋制單元的第一塊板坯，按回溯法選取一塊燙輥材與該板坯連接，得到所有軋制單元的最后一塊燙輥材;

Step3：將剩余燙輥材按寬度由大到小排序，對于每個軋制單元，將剩余燙輥材按順序嘗試與已加入軋制單元的燙輥材連接;

Step4：判斷板坯寬度跳躍是否可與下一塊燙輥材連接，如果可以將板坯編入軋制單元，否則執(zhí)行Step5;

Step5：判斷軋制單元中燙輥材是否達(dá)到燙輥材數(shù)量需求，若是，結(jié)束編制;

否則進(jìn)行Step4。

4 仿真實(shí)驗(yàn)

利用某廠的生產(chǎn)數(shù)據(jù)實(shí)例進(jìn)行數(shù)值實(shí)驗(yàn)，算法的主要參數(shù)包括種群規(guī)模設(shè)置為20，迭代次數(shù)設(shè)為200。實(shí)驗(yàn)結(jié)果如表1所示。

綜上所述，可以得到以下結(jié)論：

1）從軋制單元板坯數(shù)來看，啟發(fā)式算法和改進(jìn)的差分進(jìn)化算法能得到相同數(shù)量的軋制單元，軋制計(jì)劃板坯總數(shù)、軋制公里數(shù)、重量相近，但前者得到的軋制單元板坯數(shù)波動較大，后者板坯分布更平均;

2）從懲罰值來看，兩種算法軋制計(jì)劃總懲罰值相近，改進(jìn)的差分進(jìn)化算法略小于啟發(fā)式算法，但啟發(fā)式算法單個軋制單元的懲罰值波動大;

3）從熱裝比來看，改進(jìn)的差分進(jìn)化算法熱裝比略高于啟發(fā)式算法;

4）從求解時間來看，基于數(shù)據(jù)解析的啟發(fā)式算法求解時間是改進(jìn)的差分進(jìn)化算法的1/2。

5 結(jié)論

熱軋生產(chǎn)調(diào)度問題是鋼鐵生產(chǎn)承上啟下的環(huán)節(jié)，本文以編制熱軋批量計(jì)劃為背景，對工業(yè)生產(chǎn)計(jì)劃與調(diào)度問題進(jìn)行深入研究。提出了一種基于實(shí)數(shù)編碼的支配強(qiáng)度和自適應(yīng)個體差異性度量NSGA-II算法，并結(jié)合禁忌搜索算法求解。經(jīng)過與經(jīng)典NSGA-II進(jìn)行對比數(shù)值實(shí)驗(yàn)，發(fā)現(xiàn)算法是有效的，基本解決了實(shí)際企業(yè)中熱軋生產(chǎn)計(jì)劃的自動編排問題。

參考文獻(xiàn)：

[1] Tang LX， Liu JY， Rong AY， Yang ZH. A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex[J].European Journal of Operational Research，2000，124： 267-282.

[2] 張濤，王夢光，楊建夏.不確定計(jì)劃數(shù)的軋制批量計(jì)劃的模型和算法[J].系統(tǒng)工程學(xué)報(bào)，2000，15（1）：54-60.

[3] 劉士新，宋健海，周山長.熱軋帶鋼軋制批量計(jì)劃優(yōu)化模型及算法[J].控制理論與應(yīng)用，2007，24（2）：243-248.

[4] 寧樹實(shí)，王偉.熱軋批量計(jì)劃編制模型及其算法[J].系統(tǒng)仿真學(xué)報(bào)，2007，19（3）：691-694.

[5] 李鐵克，郭冬芬.基于約束滿足的熱軋批量計(jì)劃模型與算法[J].控制與決策，2007，22（4）：389-393，398.

【通聯(lián)編輯：代影】