基于遺傳算法的鋼板罩退工序生產(chǎn)調(diào)度優(yōu)化

付豫金，袁林艷

（1.中國空空導(dǎo)彈研究院，河南 洛陽471000；2.濱海新區(qū)塘沽浙江路小學(xué)，天津 濱海300450）

0 引言

近年，企業(yè)生產(chǎn)調(diào)度問題越來越得到研究者的注意，從最早的組合優(yōu)化、數(shù)學(xué)規(guī)劃等方法被引入，到排隊論、控制理論被用來解決生產(chǎn)調(diào)度問題，生產(chǎn)調(diào)度研究得到了快速發(fā)展，但隨著研究問題的復(fù)雜度不斷提升，精確求解法已經(jīng)很難取得理想結(jié)果，啟發(fā)式算法和智能算法被引入到調(diào)度問題研究中。研究范圍也從傳統(tǒng)的離散型企業(yè)擴(kuò)展到流程型企業(yè)。其中，針對鋼鐵行業(yè)的研究逐漸得到重視。

鋼鐵產(chǎn)業(yè)中，薄板生產(chǎn)因技術(shù)含量高、附加值高、用途廣泛的原因，成為鋼鐵制造中的一項核心產(chǎn)業(yè)。薄板生產(chǎn)調(diào)度問題成為鋼鐵產(chǎn)業(yè)此類問題研究中的重點(diǎn)，但鋼板生產(chǎn)調(diào)度問題屬于一種混合車間調(diào)度問題，即涉及具有流程型特征的連續(xù)加工，又包含批次生產(chǎn)等多種生產(chǎn)因素。薄板生產(chǎn)工藝過程一般包括轉(zhuǎn)爐煉鋼、精煉、連鑄連軋、熱軋、酸軋、罩退、平整和鍍鋅工序[1]，其中轉(zhuǎn)爐煉鋼、精練、連鑄連扎屬于連續(xù)加工過程，熱軋、酸軋、罩退、平整和鍍鋅工序?qū)儆谂渭庸ぁ５滞斯ば蛴稚婕爱a(chǎn)品分類加工問題，包含產(chǎn)品約束、設(shè)備約束和批次約束，是薄板生產(chǎn)調(diào)度問題中最復(fù)雜，最核心的部分。

針對鋼鐵企業(yè)的調(diào)度問題研究多集中在精煉、連鑄等液體加工工序階段，針對酸軋、罩退等固體加工工序的研究相對較少。如唐立新對薄板生產(chǎn)彩涂工序調(diào)度問題進(jìn)行了研究，將動態(tài)規(guī)劃算法與禁忌搜索算法結(jié)合起來，對問題進(jìn)行了求解[2]。Wang和Tang運(yùn)用禁忌搜索算法解決了熱軋工序的組批和調(diào)度問題[3]。而針對罩退工序調(diào)度問題，以往研究只針對工藝約束進(jìn)行了考慮[4]，沒有充分考慮罩退工序生產(chǎn)過程中的其他因素。還有一些學(xué)者針對罩退工序的調(diào)度問題，采用了仿真、聚類分析和緊急搜索算法等方法進(jìn)行了求解[5-8]。

針對以往研究未能充分考慮罩退工序?qū)嶋H生產(chǎn)中面臨的多種約束問題，本文以鋼板生產(chǎn)罩退工序為切入點(diǎn)，將罩退工序?qū)嶋H生產(chǎn)中具有的設(shè)備約束、產(chǎn)品約束、時間約束和批次約束納入研究范疇，構(gòu)建了基于多種約束的數(shù)學(xué)模型，并通過遺傳算法進(jìn)行求解，驗證模型及算法有效性，為企業(yè)生產(chǎn)調(diào)度提供新的思路和方法。

1 問題描述

罩退工序是罩式退火工序的簡稱，是指將鋼卷放在爐臺上，扣入加工內(nèi)罩，在進(jìn)行密封檢查和預(yù)吹掃后，扣入加熱外罩，進(jìn)行相應(yīng)的退火路線操作。鋼鐵薄板生產(chǎn)中，罩退工序是典型的混型生產(chǎn)工序，不同規(guī)格的產(chǎn)品組成一個生產(chǎn)批次加工，因此同一批次不同規(guī)格的產(chǎn)品具有相同的開始時間和結(jié)束時間。同一批次產(chǎn)品具有同樣的工藝要求，主要包括設(shè)備要求、產(chǎn)品厚度要求、時間要求。設(shè)備要求是指同一批次鋼卷寬度疊加后不會高于罩退爐的高度，厚度要求指同一個批次的產(chǎn)品應(yīng)具有相同的厚度屬性。厚度一般分為三種規(guī)格，即小于0.6 cm、大于3 cm和處于兩者之間的厚度。時間約束是指，由于同一批次鋼卷特征不同，因此加工時間不同，罩退工序的時間必須滿足同一批次中所有鋼卷的時間要求。罩退工序調(diào)度問題示意圖如圖1所示。

圖1 罩退工序調(diào)度問題流程圖

罩退工序的調(diào)度問題是典型的混型生產(chǎn)調(diào)度問題，首先需要確定分批，將產(chǎn)品劃分為不同的批次，而后需要確定某一批次產(chǎn)品的加工設(shè)備，并確定同一設(shè)備不同批次間的加工順序，是典型的NP難題[4]。本文針對罩退工序，綜合考慮工藝、產(chǎn)品和時間約束，構(gòu)建數(shù)學(xué)模型，并通過遺傳算法進(jìn)行求解。

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

通過罩退工序流程及約束研究，構(gòu)建以最小訂單加權(quán)時間為目標(biāo)函數(shù)的罩退工序數(shù)學(xué)模型，具體參數(shù)設(shè)置及模型如下：

參數(shù)：

M——隨機(jī)的很大的一個常數(shù)（M→+∞）

N——罩式退火爐的集合

J——鋼卷的集合

Pj——鋼卷j的加工時間

TR——從酸軋工序到罩退工序的運(yùn)輸時間

F——類的集合

Jf——類中f的鋼卷的集合

Dj——鋼卷j的厚度所屬的屬性

WIj——鋼卷j的寬度

HE——罩式退火爐的高度

O——訂單的集合

Fo——訂單o中的類的集合

Wo——訂單o的權(quán)重

Jj——鋼卷j在酸軋工序的完成時間

1變量：

Jj——鋼卷j的完成時間

2

Rin——0-1變量，等于1時表示鋼卷i在設(shè)備n上進(jìn)行加工，等于0時則不是

Qij——0-1變量，等于1時表示鋼卷i在鋼卷j之前進(jìn)行加工，等于0時則不是

Sij——0-1變量，等于1時表示鋼卷i和鋼卷j一起進(jìn)行加工，即屬于同一個并行批次，等于0時則不是

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

模型中，（1）為本模型的目標(biāo)函數(shù)；約束（2）-（6）表示是否為同一批次以及相應(yīng)的鋼卷加工順序的邏輯約束；（7）表示每一個鋼卷只能選擇一個罩式退火爐進(jìn)行加工；約束（5-8）是關(guān)于選擇在同一時間同一罩式退火爐加工的鋼卷的加工時間的約束，其加工時間為所含鋼卷的固有加工時間的最大值；約束（9）是關(guān)于每一個鋼卷在罩式退火工序的完成時間的約束；約束（10）-（11）是關(guān)于同一批次的鋼卷之間的厚度約束和寬度約束，即厚度要一致，寬度之和不能大于罩式退火爐的高度；約束（12）-（13）表示類和訂單的完成時間，皆為所含鋼卷的完成時間的最大值；約束（14）是關(guān)于0-1變量的約束。

3 算法實(shí)現(xiàn)

鋼板罩退工序的生產(chǎn)調(diào)度問題屬于NP難題，智能算法是求解NP難題的重要方法。由于本文研究問題涉及約束及因素較多，因此需要選擇即具有較好的靈活性又能充分表達(dá)生產(chǎn)因素的算法。本文采用遺傳算法進(jìn)行模型的求解，一方面，遺傳算法能夠很好地表達(dá)各種生產(chǎn)因素和約束，同時具有良好的穩(wěn)定性及時效性。

3.1 染色體的編碼與解碼

遺傳算法中，用編碼來表示研究問題的變量，編碼構(gòu)成染色體，按照遺傳規(guī)律進(jìn)行選擇、交叉、變異。基于罩退工序調(diào)度問題特征，染色體編碼由三部分組成，第一部分代表類的加工順序，基因值為類的索引號，第二部分表示加工順序，基因值表示鋼卷索引號，第三部分表示不同的鋼卷加工時所選的設(shè)備，基因值代表第二部分鋼卷選擇的退火爐編號。具體示例如下：

類：1，2，3，4

類與鋼卷：（1，2，3，4，5，6，7，8，9），（15，16，17，18，19，20，21，22，23，24），（25，26，27，28，29，30，31），（10，11，12，13，14）

設(shè)備的編號：1，2，3

則某個體的染色體的構(gòu)成可以表示為：

第二部分：

第三部分：

3.2 種群初始化

采用隨機(jī)生成法進(jìn)行種群的初始化操作，第一部分隨機(jī)生成類的加工順序，第二部分根據(jù)索引號的大小排列。第三部分首先進(jìn)行了并行批次數(shù)最大批量和最小批量求解，取得各退火爐出現(xiàn)數(shù)量后，進(jìn)行隨機(jī)化處理，生成第三部分編碼。示例如下：

例如：a=4，b=2，N=31，d=3

第二部分：

則 a'=7.5，b'=15

隨機(jī)生成 c=8，則 c'=3，r=7，r/c'得 m=2，n=1，則（c+m+1）=11，從而由（c+m+1）/d 得e=3，f=2

即1號、2號、3號罩式退火爐出現(xiàn)的次數(shù)分別為12次、10次和9次。按照出現(xiàn)次數(shù)，隨機(jī)生成一個順序列，即得到染色體第三部分的初始編碼，結(jié)果如下：

第三部分：

3.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用來評價個體在目標(biāo)函數(shù)方向上的優(yōu)劣程度，適應(yīng)度值的大小代表個體的結(jié)果優(yōu)劣，適應(yīng)度函數(shù)值越大說明個體越接近最優(yōu)值，反之則越遠(yuǎn)離。本文研究以時間最少為目標(biāo)函數(shù)的衡量指標(biāo)，因此取目標(biāo)函數(shù)的倒數(shù)為適應(yīng)度函數(shù)，以保證適應(yīng)度函數(shù)與目標(biāo)函數(shù)的一致性和匹配性。由于工藝條件限制，產(chǎn)品的批次組合必須滿足寬度和厚度的要求，因此計算適應(yīng)度函數(shù)時，需首先確定同一設(shè)備下加工的鋼卷，并將鋼卷按照所分批次進(jìn)行組合，通過鋼卷加工順序和時間，計算出不同批次的完成時間，進(jìn)而確定不同設(shè)備加工完成時間，最終確定訂單的完成時間，將時間取倒數(shù)，即得到適應(yīng)度函數(shù)的值。

3.4 選擇、交叉和變異

遺傳算法中的選擇是為了將具有較優(yōu)適應(yīng)度值的個體選擇出來，并作為下一輪計算的基礎(chǔ)樣本，交叉和變異用于產(chǎn)生新的個體，以更新基礎(chǔ)樣本。染色體的選擇方式很多，本研究分兩步實(shí)現(xiàn)，首先確定優(yōu)秀個體占種群個體的比例，而后按照輪盤賭的方式將這些個體選擇出來。

交叉是通過不同染色體之間的交叉，以保持種群的多樣化，并將優(yōu)秀的基因遺傳到下一代。本文采用江志彬所介紹的方法[9]和PMX方法相結(jié)合的方式，并根據(jù)實(shí)際情況作了相應(yīng)調(diào)整。交叉的實(shí)現(xiàn)過程如下：選取個體P1和P2，根據(jù)交叉概率選擇是否對其進(jìn)行交叉操作，如果進(jìn)行交叉則在P1和P2的第一部分編碼中隨機(jī)選取兩個位置記為，而后將P1中與C2位置包含的相同的基因碼刪除，并將C2所包含的基因碼置于P1末端，同理對P2進(jìn)行類似操作。而后，染色體中第二部分，按照新產(chǎn)生的第一部分?jǐn)?shù)據(jù)進(jìn)行相應(yīng)調(diào)整，只調(diào)整類的順序，類中包含的鋼卷順序不做改變。染色體中的第三部分不變。交叉操作過程示例如下：

P1第一部分和第二部分染色體基因碼分別如下：

P2的第一部分和第二部分染色體基因碼分別如下：

P1與P2交叉操作示意圖如下：

得到結(jié)果：

染色體第二部分對應(yīng)第一部分進(jìn)行相應(yīng)調(diào)整，得到結(jié)果為：

染色體變異是按照一定的變異率，為個體進(jìn)行變異操作，以增加種群的多樣性，避免算法過快收斂而趨近局域最優(yōu)解。本研究通過初始化染色體第三部分進(jìn)行變異操作。

4 算例及結(jié)果

為驗證所構(gòu)建算法的有效性，本文對算法進(jìn)行了實(shí)例運(yùn)算。算法數(shù)據(jù)取自于國內(nèi)某薄板廠真實(shí)數(shù)據(jù)，提取算法中的變量及參數(shù)，主要包括：罩退工序訂單交貨期、罩退工序類的劃分、設(shè)備臺數(shù)、設(shè)備高度、鋼卷的寬度厚度、鋼卷所需的加工時間。具體見下表1、表2所示。

表1 算例訂單數(shù)據(jù)（節(jié)選）

表2 不同型號鋼卷罩退工序加工時間（小時）

在代入算法計算之前，對訂單按照交貨期的緊迫程度確定了訂單權(quán)重，距離交貨期越近，則訂單權(quán)重越大。選取訂單中前147個類代入算法進(jìn)行運(yùn)算，結(jié)果顯示，遺傳代數(shù)接近150代時，結(jié)果趨于收斂。將遺傳算法最大代數(shù)設(shè)為500，結(jié)果基本收斂于2.76×104，如圖2所示。調(diào)度方案運(yùn)算結(jié)果共計2424列，文中不再展示。

圖2 示例運(yùn)算結(jié)果

為了驗證訂單規(guī)模對運(yùn)算結(jié)果的影響，使用遺傳算法進(jìn)行了不同訂單規(guī)模罩退工序時間的計算，統(tǒng)計結(jié)果如表3所示。

表3 不同訂單規(guī)模算法計算結(jié)果與實(shí)際生產(chǎn)數(shù)據(jù)比較

運(yùn)算結(jié)果顯示，不同訂單規(guī)模下，遺傳算法運(yùn)算結(jié)果均優(yōu)于實(shí)際生產(chǎn)過程中的訂單完成時間。其中，訂單規(guī)模為1時，生產(chǎn)調(diào)度問題較為簡單，由人工即可計算得出較優(yōu)結(jié)果，算法計算結(jié)果與實(shí)際組織生產(chǎn)時差異不大，事實(shí)上，這是一種臨界情況，在生產(chǎn)過程中極少出現(xiàn)。當(dāng)訂單規(guī)模大于等于2時，由于同一訂單本身包含不同的產(chǎn)品，因此具備一定的計算難度，在多種因素制約下，已經(jīng)很難由人工計算取得最有解。計算結(jié)果同時顯示，隨著訂單規(guī)模的增加，優(yōu)化效果越來越明顯，但當(dāng)達(dá)到一定規(guī)模后，優(yōu)化效果趨于穩(wěn)定。

5 結(jié)論

本文針對鋼鐵薄板生產(chǎn)中罩退工序制約因素多，資源調(diào)配困難的問題，基于企業(yè)生產(chǎn)實(shí)際，綜合考慮多種制約因素，構(gòu)建了以最小化訂單完成時間為目標(biāo)的數(shù)學(xué)模型，并通過遺傳算法進(jìn)行求解。結(jié)果顯示，遺傳算法求解算例驗證了算法的有效性，罩退工序訂單完成總時間明顯優(yōu)于現(xiàn)行實(shí)際加工時間，且隨著訂單規(guī)模的增加，算法取得的優(yōu)化效應(yīng)逐漸增加，但訂單規(guī)模達(dá)到一定程度后，優(yōu)化效果趨于穩(wěn)定。一方面，當(dāng)前產(chǎn)品生產(chǎn)調(diào)度問題存在改進(jìn)空間，另一方面，時間效率的上限為100%，因此算法的優(yōu)化效益存在上限。本研究為薄板生產(chǎn)中罩退這一瓶頸工序調(diào)度問題提供了可參考的思路，由于薄板生產(chǎn)罩退工序具有相似性，因此模型和算法適當(dāng)調(diào)整后可用于其他企業(yè)或者行業(yè)的調(diào)度問題優(yōu)化。按照研究思路，所用模型和方法可推廣延伸至其他工序，累計效益將更加顯著。研究方法和結(jié)論可為企業(yè)生產(chǎn)計劃和調(diào)度提供借鑒和幫助。