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

黨世杰，張國輝，鈔宇飛

?

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

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

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

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

一、前言

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

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

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

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

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

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

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

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

(3)一臺(tái)機(jī)器在同一時(shí)間只能加工某個(gè)工件的某一工序。

(4)為了保證加工過程的安全性，機(jī)器加工完一個(gè)工序，若下一工序仍為同一工件則繼續(xù)加工，否則進(jìn)行停機(jī)操作，當(dāng)加工下一工件時(shí)重啟機(jī)器進(jìn)行加工。

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

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

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

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

1.編碼和解碼

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

圖1　染色體編碼

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

2.種群初始化

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

3.遺傳操作

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

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

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

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

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

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

五、結(jié)語

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

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

參考文獻(xiàn)：

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

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

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

[4]項(xiàng)喧,陶守強(qiáng),熊偉.結(jié)合仿真和遺傳算法的生產(chǎn)調(diào)度多目標(biā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]張國輝,高亮,李培根,等.改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問題[J].機(jī)械工程學(xué)報(bào),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]張超勇,饒運(yùn)清,劉向軍,等.基于POX交叉的遺傳算法求解Job-Shop 調(diào)度問題[J].中國機(jī)械工程,2004,15(23):83-87.

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

(Y20150105))

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

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

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

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