基于MOMA 算法的分時電價下煉鋼生產調度研究

薛明遠，葉春明

（上海理工大學 管理學院，上海 200093）

0 引言

氣候變暖、能源價格上漲等話題已成為社會熱點，節能減排目標任務也隨即擺在眾多高耗能企業的面前。鋼鐵企業的鋼鐵生產具有高耗能、高排放的特點，一直是節能減排課題的重要研究對象。近年來，隨著分時電價政策的推廣適用，各企業紛紛應用分時電價政策來合理安排企業自身的生產計劃，尋求降低能耗成本的有效途徑。

Wang 等人針對傳統的車間調度問題進行了分時電價下的混合流水車間的研究。并且分時電價政策的推出，促使鋼鐵企業也在考慮分時電價下的生產調度，如Li 等人針對基于混合流水車間的煉鋼連鑄生產調度問題，提出了一種高效的果蠅算法對問題進行求解。馬文強等人也針對同一問題，提出了一種基于變鄰域搜索的混合教與學優化算法。沈鵬針對分時電價下煉鋼生產的澆次計劃調度問題，提出了一種遺傳算法來獲得求解。Hadera 等人以優化電力成本為目標，構建了一個具有能量感知的連續時間模型，并提出了一種雙層啟發算法來求解問題。

在傳統的混合流水車間調度及鋼鐵企業煉鋼生產調度方面的研究較多，而對于分時電價下鋼鐵行業雙目標煉鋼生產研究較少。本文以分時電價下鋼鐵企業雙目標煉鋼生產調度為研究對象，在傳統的煉鋼生產基礎上引入分時電價政策，在滿足煉鋼生產約束的前提下，以最小化最大完工時間和最小化電力成本為優化目標，建立分時電價下鋼鐵企業煉鋼生產的調度模型。

1 鋼鐵生產調度問題描述及數學模型

1.1 問題描述

相比于“長流程”煉鋼模式，以電弧爐為主要冶煉設備的“短流程”煉鋼是較為節能環保的一種生產方式，但是也會加大用電負荷，增加電力成本。對于短流程煉鋼模式可以描述為有個爐次，各爐次生產某種或者某些不同的鋼鐵產品，并將按照生產加工順序依次經過：煉鋼、精煉／多重精煉、連鑄等多個加工階段。具體而言，分別要經過電弧爐煉鋼（Electric Arc Furnace Steelmaking，EAF）、氬氧脫碳精煉（Argon Oxygen Decarburization，AOD）、鋼包精煉（Ladle Furnace，LF）、連鑄（Continuous Casting，CC）四個生產階段。各生產階段有多臺并行加工設備，各階段每臺設備的功率不同，對同一爐次的加工時長也不同。為保證鋼鐵產品的質量，要滿足以下工藝約束：

（1）各個生產階段有多臺并行的加工設備，同一時刻、同一爐次最多在一臺機器上被加工，同一時刻每臺設備上最多只能加工一個爐次。

（2）每一爐次一旦開始加工便不可中斷。

（3）所有爐次之間互不影響，各爐次之間的加工順序沒有先后，但是每個爐次在加工工序上有前后順序約束，前一生產階段結束后才能開始下一生產階段的加工。

（4）同一澆次的爐次澆鑄時不允許斷澆。

1.2 數學模型

在分時電價政策的應用下，涉及到大量時間索引，本文提出了雙目標的鋼鐵生產調度時間離散模型，為確保計算速度，本文將時間單位設置為1 h。

研究給出目標函數的數學公式可寫為：

其中，表示最大完工時間；C表示爐次的完工時間；表示爐次序號，1，2，…，；表示加工過程中設備加工消耗的電力成本；PW表示加工設備的功率，表示設備序號；T表示設備所處的時間段區間的加工時間，1，2，…，；PR表示時間段區間的電價。

研究中要用到的約束條件可做闡釋分述如下：

（1）保證同一爐次的前一加工階段結束后才可以開始下一階段，對此可表示為：

其中，b為爐次到達1 生產階段并開始加工的時間； c為爐次在第生產階段的完工時間；表示某一工序，表示所有工序的集合，｛1，2，…，｝，表示工序的總數，∈。

（2）保證每個爐次在各生產階段上僅可以選擇該階段的某一臺設備在某一時刻開始加工，對此可表示為：

其中，x為0-1 變量，若爐次在第時刻，選擇第生產階段的第臺設備開始加工，則x＝1，否則，x＝0；為某一設備序號，M為工序中所有設備的集合，M＝｛1，2，…，｜M ｜｝；｜M ｜為工序中設備的總數，∈M，M∈。

（3）保證各階段的任何一臺設備在某一時刻最多只能加工一個爐次，對此可依次表示為：

其中，y為0-1 變量，若爐次在第時刻，生產階段的第臺設備上正在加工，則y＝1，否則y＝0。

（4）爐次在生產階段上的加工開始時間、加工時間、加工結束時間，對此可分別表示為：

其中，p指爐次在第生產階段的第臺設備上加工所用的時間。

（5）保證爐次在生產階段上的第臺設備上的加工是連續的，對此可表示為：

其中，是一個足夠大的正數。

（6）爐次的完工時間和所有爐次完工的最大完工時間定義，對此可表示為：

其中，C為爐次的完工時間，為所有爐次的最大完工時間。

2 改進的MOMA 算法

鋼鐵企業煉鋼生產調度問題與混合流水車間的調度問題相似，均屬于NP 問題。多目標文化基因算法（MOMA）是一種基于種群的全局搜索和基于個體的局部搜索的結合體，常應用于解決具有多約束條件的0-1 問題，其優點是可以采用不同的搜索策略生成多種改進的MOMA 算法，NSGA-Ⅱ算法的編碼規則是可以有效求解此類調度問題的處理策略，所以本文在MOMA 算法的基礎上采用NSGA-Ⅱ的編碼規則進行改進，在MOMA 算法框架下采用NSGA-Ⅱ的編碼規則設計了交叉算子、變異算子以及局部搜索算子，提高了MOMA 算法的種群多樣性以及局部搜索性能。改進后的MOMA 算法求解流程如圖1 所示。

圖1 改進的MOMA 算法求解流程圖Fig.1 Improved MOMA algorithm solution flow chart

算法改進的相關操作可做重點表述如下：

（1）編碼和解碼。本文采用隨機鍵升序的編碼方式，構造出從個體位置到爐次排序的對應關系，通過解碼過程將為各工件的每一生產階段選擇一臺加工設備，同時確定各設備上需加工的各工件的加工順序以及起始時間，根據求得的目標函數值及本文的各種約束條件生成最優調度方案。

（2）交叉、變異操作。考慮到交叉算子、變異算子影響著局部和全部的搜索能力，本文采用優先工序交叉的交叉策略和局部最優的變異策略。以一條5 個工件的工列排序染色體為例，進行優先工序交叉操作如圖2 所示，具體操作為：

圖2 優先工序交叉操作示意圖Fig.2 Schematic diagram of priority process crossover operation

①隨機選擇2 個父代染色體和，并將所有工件的序號分配到2 個非空子集和中；

②將父代染色體中包含在中的工件復制到，將父代染色體中包含在中的工件復制到，并維持原有位置；

③將父代染色體中包含在中的工件復制到，將父代染色體中包含在中的工件復制到，原有順序保持不變；

④得到經過交叉操作后的子代染色體和。

以一條5 個工件的工序排列染色體為例，進行局部最優變異操作，具體操作為：隨機選擇一個父代染色體，在中隨機選擇3 個工件｛1，3，5｝作為一個局部的算子，將局部算子中工件排序的所有可能列出｛1，3，5｝、｛1，5，3｝、｛3，1，5｝、｛3，5，1｝、｛5，1，3｝、｛5，3，1｝，然后對每種組合進行計算評估，根據支配關系選擇最優的組合得到經過局部最優變異后的子代染色體。假設｛3，5，1｝是最優的組合，局部最優變異操作示意，如圖3 所示。

圖3 局部最優變異操作示意圖Fig.3 Schematic diagram of local optimal mutation operation

（3）局部搜索算子?？紤]到局部搜索性能和種群的多樣性，本文采用了變鄰域的方式，具體操作為：在個體中隨機選擇一個工件將工件的位置和其他工件的位置進行交換，分別計算每次交換后的目標函數值，記錄每次的目標函數值，并根據支配關系選擇最優的目標函數值，此時所對應的染色體序列就是最優的變鄰域操作后的序列。

3 實驗結果與分析

在鋼鐵企業中，假設爐次的冶煉路線分為4 個階段，即：EAF 爐熔化廢鋼→AOD 爐氬氧脫碳精煉→LF 爐鋼包精煉→CC 澆鑄。

本文中選用一個具有15 個爐次規模的實例進行實驗分析，僅考慮各生產階段之間最大等待時間為0 的情況。每個生產階段有2 臺不同功率的加工設備，每臺設備對同一爐次的加工時間不同。各階段加工設備的功率及編號，見表1。各加工設備對每個爐次的加工時間，見表2。

表1 各階段加工設備的功率及編號Tab.1 Power and number of processing equipments at each stage

表2 各加工設備對各爐次的加工時間Tab.2 Processing time of each processing equipment for each furnace h

以上海市非夏季時段一天內針對大工業用電的分時電價（單位：元／kWh）政策為例，如圖4 所示。分時電價將一天24 h 分為峰時段（8～11 時、18～21時），平時段（6～8 時、11～18 時、21～22 時），谷時段（22 時～次日6 時）。根據具體的電價，一天24 h內的分時電價函數（單位：元／kWh）可表示為式（16）：

圖4 上海市大工業用電24 h 分時電價圖Fig.4 24 h time-of-use electricity prices for large-scale industries in Shanghai

運用改進的雙目標文化基因算法可以得到求解結果，獲得最優調度方案，最優解甘特圖如圖5 所示，計算排產計劃的完工時間為169 h。在實際操作過程中，鋼鐵企業煉鋼生產的各個階段的排產計劃大多由調度員用某種簡單的啟發式規則人工制定，考慮最多的就是完工時間，但是卻很少會將電力成本因素考慮其中。在本文中引入分時電價政策前、最小化最大完工時間最優調度方案的電力成本為15 203.334元，在引入分時電價政策后、得到的電力成本結果為14 043.506 元。因此，在分時電價條件下使用改進的MOMA 算法，既保證了最小化最大完工時間，又使電力成本降低了7.63%，對于高耗能的鋼鐵企業來說，通過充分利用分時電價政策，能夠有效地減少生產過程中的電力成本，證明了本文模型有著良好可行性。

圖5 模型最優解甘特圖Fig.5 Gantt chart of the optimal solution of the model

4 結束語

本文在分時電價政策背景下，以“短流程”煉鋼生產為研究對象，分析了分時電價政策下鋼鐵企業煉鋼生產的調度特點，建立了以最小化最大完工時間和最小化電力成本為目標的調度模型，并以一個15 爐次的實例進行實驗。實驗結果表明，在保證最小化最大完工時間的前提下，引入分時電價政策能夠有效地降低自身約7.63%的電力成本，對鋼鐵企業實現成本節約以及維持整個電網負荷的平衡都具有重要意義。