基于遺傳算法的企業能源優化調度方法研究

吳辰超，凌衛青，戴毅茹

（同濟大學CIMS研究中心，上海 201804）

0 引言

隨著能源問題的日益加劇，企業迫切需要提高生產效率和資源利用率，達到交貨期短、生產能耗小的生產要求，因此車間作業調度問題的研究顯得尤為重要。本文以某重型裝備企業生產流程作為模型，結合中心開發的企業生產與能耗耦合建模仿真軟件對優化調度結果進行仿真。應用遺傳算法，在機器準備時間、加工時間、單位時間能源消耗等初始參數不變的情況下，通過改變生產的投料順序，達到總生產時間、總能源消耗最少的目標。

1 遺傳算法與重型裝備企業優化排程研究

1.1 重型裝備企業特點

重型裝備制造企業是典型的能耗大戶，其消耗的能源介質包括電、煤、天然氣、煤氣、蒸汽、氧氣、水等。重型裝備制造企業能源管理普遍屬于粗放型、分散化的模式，其熱加工處理環節消耗能量巨大，熱加工排程往往采用人工經驗方式制定，沒有考慮到能源約束，熱加工環節往往不考慮到余熱的回收利用，熱能損失大，所以對重型的裝備企業的能耗實行精細化管理、對企業的生產排程進行優化是企業節能減排與緩解企業能源約束矛盾的根本措施。

1.2 遺傳算法優化調度應用

在國內企業對生產排程的調度由于技術上的制約，基本上是依靠技術人員的經驗。隨著智能算法尤其是遺傳算法的研究越來越成熟，遺傳算法在企業生產排程上的應用也越來越多。

基本遺傳算法[6]（簡稱SGA）是一種種群型操作，該操作以種群中的所有個體為對象，只使用基本遺傳算子、選擇算子、交叉算子和變異算子，其遺傳進化操作過程簡單，容易理解，是其他一些遺傳算法的基礎，不僅給各種遺傳算法提供了一個基本框架，同時也具有一定的應用價值。選擇、交叉和變異是遺傳算法的三個主要操作算子，它們構成了所謂的遺傳操作，使遺傳算法有了其他傳統方法沒有的特點。

圖1 遺傳算法流程圖Fig.1 Genetic algorithm flow chart

1.3 建模仿真工具介紹

優化結果的驗證通過重型裝備能耗耦合建模仿真軟件來實現，該軟件是用C#在.NET平臺上開發的用來模擬企業生產過程中能源消耗過程。通過對重型裝備企業生產流程的建模，能夠清晰地反映出生產過程中的能源流、物料流、信息流和排放流。在設置完設備加工時間、設備能耗、加工訂單數量、物料加工時間等參數后，通過對相應模型的仿真，能夠得到一次加工過程所消耗的折標能源總量、單臺設備所消耗的折標能源總量等數值，為驗證優化結果是否正確提供了一條有效的途徑。

2 遺傳算法在生產調度中的應用

2.1 企業背景

某重型裝備廠是一家典型的高能耗企業，該企業對于節能減排的需求相當迫切。近些年，企業結合自身情況逐步對一些耗能設備進行了節能改造。如鍋爐加裝分層燃燒裝置，增設蒸汽蓄熱器和引進天然氣替代自制發生爐煤氣及重油，但是隨著公司熱加工產品的比重上升，能耗呈加速上升趨勢。

目前，比較常用的應用于企業節能減排的方法主要有以下幾種方式。通過改變設備的工藝參數，在保證生產產品質量的情況下，減少工件加工時間、降低加工爐膛溫度等。在生產過程中通過余熱回收，提高燃油、煤炭等能源介質的熱效率。改變生產排程，使工件間加工過程更加緊湊，從而提高了設備的利用率，減少了設備的開機總時間、啟停次數、保溫時間。本案例通過遺傳算法對企業的生產排程及設備調度策略可行解進行快速搜索，找到最佳的生產排程及設備調度方案，實現企業節能減排的目標。

2.2 軟件總體設計思想

遺傳算法后臺操作主要包含兩個類：染色體類與遺傳操作類。染色體類中包含了用來存儲基本遺傳信息的一些屬性如染色體碼、染色體適應值、染色體輪盤選擇概率等。遺傳操作類屬性主要包含兩部分數據，一部分是用來記錄遺傳操作控制信息如遺傳代數、種群大小、交叉概率、變異概率等。另一部分用來記錄每一代進化過程中的中間信息如染色體種群適應值的平均值、染色體種群中最優染色體、染色體種群中最差染色體等。

（1）編碼設計。遺傳算法編碼采用整數編碼，將一條染色體分成兩部分，前半部分為企業生產計劃信息，例如 [3142]編碼方式表示企業先加工3號訂單，其次是1號與4號訂單，最后是2號訂單。后半部分為設備調度策略信息，例如 [1132]編碼方式表示1號設備使用第一種工件進入策略，第2臺設備使用第一種工件進入策略，第三臺設備使用第三種工件進入策略。設備的每種進入策略包含在建模信息中，只要在仿真過程中讀取即可，如第一種工件進入策略為先到先加工（FIFO），第二種工件進入策略為最短加工時間優先（SPT），只需根據建模信息映射即可。在軟件中，染色體編碼信息以動態數組（List＜＞）的方式保存。

（2）適應度函數設計。針對優化目標為生產能耗最小的情況，選取電消耗、天然氣消耗、煤氣消耗折標求和后的值直接作為優化的適應度函數。由于本案例屬于最小化優化問題，所以在做選擇操作時必須以適應值最小作為最優條件。

（3）遺傳操作設計思想：①初始化種群操作：主要根據優化操作的基本信息生成符合要求的初始種群；②選擇操作：采用輪盤賭選擇方法。進行輪盤賭選擇操作時，首先按照適應值大小進行排序，適應值小的染色體排在前，適應值大的染色體排在后，然后進行選擇概率統計，計算出每條染色體的適應值與所有染色體適應值的和之間的比值。由于該問題是最小化問題，所以在計算完概率值后，將對應染色體的概率值進行逆序操作，保證適應值小的染色體被選擇到的概率大。完成這些操作后再分別將這些數值從第一條染色體開始進行累加，并將累加值存入對應的染色體中。進行選擇時，只需用調用Random類的NextDouble方法，生成一個0～1之間的隨機小數，并將其與遺傳池中的每個染色體累計值進行比較，當隨機小數值大于染色體累積值時，選擇當前染色體進入選擇池。重復此操作，直到選擇的染色體數量滿足種群大小要求；③交叉操作：按照交叉概率選擇一定數量的染色體進入交叉池，例如當交叉概率為0.4，種群大小為10時，則選擇4條染色體進入交叉池執行交叉操作，交叉的方法采用單點交叉法，交叉點的位置由隨機數生成，由于訂單排程編碼必須保證唯一性原則，所以交叉點選擇范圍為第一個設備策略碼至最后一個策略碼；④變異操作：按照變異概率選擇一定數量的染色位并改變其值，當變異概率為0.05時，表示每一百個染色體位中，有五個位要發生變異。變異操作的實現是通過對染色體池中的每條染色體的每一位進行遍歷，每次遍歷通過Random類的NextDouble方法，生成一個0～1之間的隨機小數，當該小數小于變異概率時，則進行當前位的變異操作。

2.3 仿真結果及分析

為驗證算法解決調度問題的有效性，結合某重型裝備企業的生產流程與生產仿真軟件進行仿真，工件加工路徑在建模時確定，工件加工時間、準備時間等設備參數在仿真前設定。加工初始訂單根據企業生產情況確定，如圖2所示。

圖2 生產計劃輸入界面Fig.2 Production plan input interface

遺傳算法使用的參數如下：種群大小M=20；遺傳運算終止進化代數T=30；交叉概率=0.5；變異=0.05。由仿真優化報告可知，當按照優化算法得出訂單投料順序為1324、機器使用調度策略如圖3所示時，生產能耗（折標能耗）比使用隨機投料與機器隨機調度方式的情況下的能耗少了7.09%。

圖3 優化結果展示界面Fig.3 Optimization results show interface

3 結束語

遺傳算法提供了一種求解復雜系統優化問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，遺傳算法是解決生產調度問題的一種有效途徑。生產調度問題在很多情況下建立起來的數學模型難以精確求解，即使經過一些簡化之后可以進行求解.也會因簡化得太多而使得求解結果與實際相差甚遠。目前在單件生產車間調度、流水線生產間調度、生產規劃、任務分配等方面遺傳算法都得到了有效的應用。

[1]王錫祿.Job-Shop調度問題的優化模型及算法[J].系統工程理論與實踐，2000，1.

[2]謝勝利，策金祥，黃強.基于遺傳算法的車間作業調度問題求解[J].計算機工程與應用，2002，10.

[3]王凌.車間調度及其遺傳算法[M].清華大學出版社，2003.

[4]陸薄.作業車間調度的建模及優化方法研究[D].上海.上海交通大學，2007.

[5]馮紅娟.基于遺傳算法的車間作業調度問題研究[D].長春理工大學，2008.

[6]周明，孫樹棟.遺傳算法原理及應用[M].國防工業出版社，1999.