黨世杰，張國輝，鈔宇飛

?

低碳目標下的柔性作業(yè)車間調(diào)度問題研究

黨世杰1，張國輝1，鈔宇飛2

摘要：針對柔性作業(yè)車間調(diào)度問題的特點，結(jié)合實際生產(chǎn)情況，建立低碳下的柔性作業(yè)車間調(diào)度問題模型，擴展了經(jīng)典的柔性作業(yè)車間調(diào)度問題，使該問題更具現(xiàn)實意義。使用實際碳排放量為染色體編碼，減少了以往遺傳算法編碼的轉(zhuǎn)換，提高了編碼和解碼的效率，并使用了改進的遺傳操作來提高遺傳算法的效率。然后通過使用改進的遺傳算法分析具體案例，得到了最優(yōu)解，最后給出了機器最大碳排放量最低的調(diào)度方案，從而驗證了所建模型的可行性及所提算法的有效性。

關(guān)鍵詞：低碳遺傳算法；柔性作業(yè)；車間調(diào)度

一、前言

柔性作業(yè)車間調(diào)度問題是經(jīng)典作業(yè)車間調(diào)度問題的擴展，允許一道工序在可選機器集中任選一臺機器進行加工，是典型的NP-Hard問題，是車間生產(chǎn)研究的重點問題之一。以往的柔性作業(yè)車間調(diào)度問題大多考慮最大完工時間[1-2]、機器負荷[3]、拖期[4]等，很少有文獻從生產(chǎn)過程中碳排放量最小的角度去安排生產(chǎn)調(diào)度方案。

制造業(yè)消耗了大量能源，產(chǎn)生大量的溫室氣體，是碳排放的主要來源，對調(diào)度方案的中的碳排放量加以考慮有利于節(jié)能減排，降低生產(chǎn)成本，加大制造企業(yè)的成本優(yōu)勢。Tang等[5]考慮了柔性車間調(diào)度問題的能源消耗，并使用遺傳模擬退火算法就行求解，但在大規(guī)模問題上的效果不理想。Liu等[6]使用遺傳算法求解雙目標柔性作業(yè)車間調(diào)度并取得了滿意解。

本文建立了以低碳排放為目標的柔性作業(yè)車間調(diào)度模型，擴展了柔性作業(yè)車間調(diào)度問題，在遺傳算法中對生產(chǎn)過程中的碳排放量直接進行編碼，提高了編碼和解碼的效率。最后使用了遺傳算法對問題進行求解，驗證了所用算法在求解低碳目標下的柔性作業(yè)車間調(diào)度問題時的可行性和有效性。

二、低碳目標下的柔性作業(yè)車間調(diào)度問題的描述

低碳目標下的柔性作業(yè)車間調(diào)度問題需考慮三個子問題，即工序的加工機器、工序的加工順序以及生產(chǎn)過程中的碳排放，是經(jīng)典的作業(yè)車間調(diào)度問題的延伸。低碳目標下的柔性作業(yè)車間調(diào)度問題一般描述為：n個工件在m臺機器上加工，每個工件由一道或多道工序構(gòu)成，每道工序可在其可選機器集上選擇一臺機器加工，不同的工序在不同的機器上進行加工時的碳排放量可能相同也可能不同。調(diào)度目標是確定為工序選擇最佳的加工機器，確定工序加工順序，使生產(chǎn)過程中的碳排放量最小。表1所示的是4個工件在4臺機器上加工的低碳目標下的柔性作業(yè)車間調(diào)度問題，如O11和M1對應(yīng)的數(shù)字13表示工序O11在機器M1上加工時的碳排放量為13，“-”表示該工序不能在相應(yīng)機器上加工。

低碳目標下的柔性作業(yè)車間調(diào)度問題的假設(shè)如下。

(1)某一工序在加工過程中不允許中斷。

(2)不同工件之間沒有加工順序約束，同一工件的不同工序間有加工順序約束。

(3)一臺機器在同一時間只能加工某個工件的某一工序。

(4)為了保證加工過程的安全性，機器加工完一個工序，若下一工序仍為同一工件則繼續(xù)加工，否則進行停機操作，當加工下一工件時重啟機器進行加工。

本文的優(yōu)化目標為：每個機器的最大碳排放量最小，即minCE=min(max(CEk)), 1≤k≤m，其中CE為碳排放量。

表1　低碳排放的柔性作業(yè)車間調(diào)度問題

三、遺傳算法設(shè)計

遺傳算法由美國Holland教授于1975年首先提出并被廣泛用于函數(shù)優(yōu)化、組合優(yōu)化問題及生產(chǎn)調(diào)度問題等。本文使用了遺傳算法求解低碳目標下的柔性作業(yè)車間調(diào)度問題，將生產(chǎn)過程中的碳排放量直接進行編碼并優(yōu)化求解。

1.編碼和解碼

編碼和解碼是運用遺傳算法求解問題的關(guān)鍵步驟。柔性作業(yè)車間調(diào)度問題需要為每道工序選擇合適的加工機器，然后確定加工順序，因此本文設(shè)計的染色體由機器染色體和工序染色體構(gòu)成。染色體編碼如圖1所示。

圖1　染色體編碼

在圖1中顯示了工件1的編碼，工件2、3、4則依照此編碼方式完成。圖1中工件1加工部分可解碼為工序O11在機器M4上加工，對應(yīng)碳排放量為12；工序O12在機器M3上加工，對應(yīng)碳排放量為11；工序O13在機器M2上加工，對應(yīng)碳排放量為8；工序O14在機器M2上加工，對應(yīng)碳排放量為12。該部分轉(zhuǎn)化為機器順序矩陣和碳排放量矩陣后為：

2.種群初始化

種群初始化即按照一定的方式生成初始可行解，初始解對整個算法的運行過程都有極大的影響。本文采用張國輝等[7]所使用的種群初始化方法來加快遺傳算法的收斂速度。

3.遺傳操作

(1)選擇操作。通過使用選擇操作可以使優(yōu)良的個體得以保存下來，淘汰不適應(yīng)環(huán)境的低劣個體來加快遺傳算法的收斂性，提高算法效率。本文采用GOLDBERG等[8]提出的錦標賽法，目標值即是適應(yīng)值，減少了目標值和適應(yīng)值之間的轉(zhuǎn)換，使操作更容易進行。

(2)交叉操作。針對染色體兩段式特點，本文分別對機器染色體和工序染色體進行交叉操作，得到新染色體。當進行機器染色體交叉操作時采用兩點交叉方式；工序染色體使用張超勇等[9]所提的POX交叉方式。通過使用交叉操作可以保留父代優(yōu)良染色體，避免遺傳算法陷入局部最優(yōu)解。

(3)變異操作。該操作主要為了提高遺傳算法的局部搜索能力，維持群體多樣性，防止陷入局部最優(yōu)解。機器染色體變異時，在基因串中隨機選擇一個位置，在此工序的加工機器集中任意選擇一個與它不相等的整數(shù)，替換當前的基因，這樣可以保證得到的解是可行的。工序染色體變異時，隨機選擇兩個位置的基因后調(diào)換其位置，這種方法產(chǎn)生的解是合法解。

四、計算結(jié)果分析

遺傳算法的程序采用Visual Studio 2012。程序在環(huán)境為P4 CPU、主頻3.0GHz、內(nèi)存4GB的個人電腦上運行，程序運行參數(shù)為：種群規(guī)模Ps=200，迭代次數(shù)G=100，交叉概率Pc=0.9，變異概率Pm=0.1。為了驗證算法有效性，本文以表1為例進行計算，求得生產(chǎn)過程中每個機器最大碳排放量最低的調(diào)度方案，如圖2所示，此時總碳排放量為153，然后可以按照該調(diào)度方案安排生產(chǎn)。

圖2　每個機器最大碳排放量最低的調(diào)度方案

五、結(jié)語

本文通過對生產(chǎn)過程中每臺機器的碳排放量最小為目標的柔性作業(yè)車間調(diào)度問題的描述，構(gòu)建低碳目標下的柔性作業(yè)車間調(diào)度模型?；诨镜倪z傳算法，使用實際碳排放量為染色體編碼，減少了以往編碼方式的轉(zhuǎn)換，提高了編碼和解碼的效率，并使用了改進的遺傳操作來提高遺傳算法的效率。然后使用了基于Visual Studio 2012的遺傳算法程序?qū)Π咐M行優(yōu)化，得到了每臺機器最大碳排放量最低的調(diào)度方案。最后給出了相應(yīng)的調(diào)度甘特圖。實驗結(jié)果表明筆者提出的改進遺

傳算法在求解低碳目標下的柔性作業(yè)車間調(diào)度問題時是可行的和有效的。

參考文獻：

[1]張國輝,吳立輝.求解柔性作業(yè)車間調(diào)度的GATOC混合方法[J].計算機工程與應(yīng)用，2015,51(23)：266-270.

[2]廖珊,翟所霞,魯玉軍.基于改進遺傳算法的柔性作業(yè)車間調(diào)度方法研究[J].機電工程,2014,31(6):729-733.

[3]蘇子林,車忠志,馮寶富.求解多目標柔性作業(yè)車間調(diào)度的改進遺傳算法[J].魯東大學(xué)學(xué)報(自然科學(xué)版),2015,31(4):380-384.

[4]項喧,陶守強,熊偉.結(jié)合仿真和遺傳算法的生產(chǎn)調(diào)度多目標優(yōu)化[J].系統(tǒng)仿真技術(shù),2014,10(2):90-95.

[5]Tang D B, Dai M. Energy-efficient Approach to Minimizing the Energy Consumption in An Extended Job-shop Scheduling Problem[J]. Chinese Journal of MechanicalEngineering,2015,28(05):1-8.

[6]Liu Y, Tiwari A. An Investigation into Minimising Total Energy Consumption and Total Completion Time in a Flexible Job Shop for Recycling Carbon Fiber Reinforced Polymer[C]. The 22nd CIRP conference on Life Cycle Engineering,2015,29:722-727.

[7]張國輝,高亮,李培根,等.改進遺傳算法求解柔性作業(yè)車間調(diào)度問題[J].機械工程學(xué)報,2009,45(7):145-151.

[8]GOLDBERG D E, DEB K. Acomparativeanalysisof selection schemes used in genetic algorithms[C].RAWLINSG,ed.FoundationsofGeneticAlgorithms,MorganKaufmann,1991:69-93.

[9]張超勇,饒運清,劉向軍,等.基于POX交叉的遺傳算法求解Job-Shop 調(diào)度問題[J].中國機械工程,2004,15(23):83-87.

(2015CX009)；鄭州航院大學(xué)生科技創(chuàng)新基金項目

(Y20150105))

(作者單位：1.鄭州航空工業(yè)管理學(xué)院 管理工程學(xué)院；

2.中北大學(xué) 經(jīng)濟與管理學(xué)院)

(責(zé)任編校：裴媛慧，孫詠梅)

(基金項目：鄭州航院研究生教育創(chuàng)新計劃基金項目