付豫金，袁林艷

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

0 引言

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

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

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

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

1 問題描述

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

圖1 罩退工序調度問題流程圖

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

2 數學模型

通過罩退工序流程及約束研究，構建以最小訂單加權時間為目標函數的罩退工序數學模型，具體參數設置及模型如下：

參數：

M——隨機的很大的一個常數（M→+∞）

N——罩式退火爐的集合

J——鋼卷的集合

Pj——鋼卷j的加工時間

TR——從酸軋工序到罩退工序的運輸時間

F——類的集合

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

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

WIj——鋼卷j的寬度

HE——罩式退火爐的高度

O——訂單的集合

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

Wo——訂單o的權重

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

1變量：

Jj——鋼卷j的完成時間

2

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

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

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

數學模型：

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

3 算法實現

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

3.1 染色體的編碼與解碼

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

類：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）

設備的編號：1，2，3

則某個體的染色體的構成可以表示為：

第二部分：

第三部分：

3.2 種群初始化

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

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

第二部分：

則 a'=7.5，b'=15

隨機生成 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號罩式退火爐出現的次數分別為12次、10次和9次。按照出現次數，隨機生成一個順序列，即得到染色體第三部分的初始編碼，結果如下：

第三部分：

3.3 適應度函數

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

3.4 選擇、交叉和變異

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

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

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

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

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

得到結果：

染色體第二部分對應第一部分進行相應調整，得到結果為：

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

4 算例及結果

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

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

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

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

圖2 示例運算結果

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

表3 不同訂單規(guī)模算法計算結果與實際生產數據比較

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

5 結論

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