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

付豫金，袁林艷

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

0 引言

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

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

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

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

1 問(wèn)題描述

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

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

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

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

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

參數(shù)：

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

N——罩式退火爐的集合

J——鋼卷的集合

Pj——鋼卷j的加工時(shí)間

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

F——類(lèi)的集合

Jf——類(lèi)中f的鋼卷的集合

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

WIj——鋼卷j的寬度

HE——罩式退火爐的高度

O——訂單的集合

Fo——訂單o中的類(lèi)的集合

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

Jj——鋼卷j在酸軋工序的完成時(shí)間

1變量：

Jj——鋼卷j的完成時(shí)間

2

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

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

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

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

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

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

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

3.1 染色體的編碼與解碼

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

類(lèi)：1，2，3，4

類(lèi)與鋼卷：（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è)備的編號(hào)：1，2，3

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

第二部分：

第三部分：

3.2 種群初始化

采用隨機(jī)生成法進(jìn)行種群的初始化操作，第一部分隨機(jī)生成類(lèi)的加工順序，第二部分根據(jù)索引號(hào)的大小排列。第三部分首先進(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號(hào)、2號(hào)、3號(hào)罩式退火爐出現(xiàn)的次數(shù)分別為12次、10次和9次。按照出現(xiàn)次數(shù)，隨機(jī)生成一個(gè)順序列，即得到染色體第三部分的初始編碼，結(jié)果如下：

第三部分：

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

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

3.4 選擇、交叉和變異

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

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

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

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

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

得到結(jié)果：

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

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

4 算例及結(jié)果

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

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

表2 不同型號(hào)鋼卷罩退工序加工時(shí)間（小時(shí)）

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

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

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

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

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

5 結(jié)論

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