王建華，潘宇杰，孫 瑞

(江蘇大學 管理學院，江蘇 鎮(zhèn)江 212013)

0 引言

環(huán)境污染是近年來我國重點關(guān)注的熱點問題。據(jù)有效數(shù)據(jù)不完全統(tǒng)計，中國工業(yè)能源消耗占社會總能源消耗的70%，而二氧化碳排放量占總二氧化碳排放量的83.1%，可以看出，大部分的能源消耗以及二氧化碳排放都來自于工業(yè)行業(yè)[1]，因此能源的使用效率成為了工業(yè)企業(yè)關(guān)注的重點。

綠色制造正是在這一背景下逐漸成為企業(yè)界與學術(shù)界的常議話題之一[2]。綠色制造作為現(xiàn)代先進制造模式，其主旨為在不降低產(chǎn)品功能與質(zhì)量的前提下，盡可能地降低生產(chǎn)成本，同時兼顧環(huán)境污染與能源浪費問題，進而實現(xiàn)經(jīng)濟指標和綠色指標多目標的協(xié)同優(yōu)化[3]，而綠色車間調(diào)度作為綠色制造的重要一環(huán)，近年來也成為了學術(shù)界研究的熱點。雖然綠色車間調(diào)度已經(jīng)引起了學者們的關(guān)注，但是相關(guān)的研究文獻還較少。李玉霞等[4]基于設(shè)備選擇和作業(yè)順序規(guī)劃提出了一種二階低碳調(diào)度模型用于解決車間調(diào)度問題；Adekola等[5]和Capón-García等[6]分別研究了丙烯酸纖維生產(chǎn)的批處理問題,用于解決以經(jīng)濟指標和綠色指標為目標的多目標車間調(diào)度問題；Ding等[7]針對作業(yè)車間調(diào)度問題以產(chǎn)品總完工時間不超過截止時間為約束,優(yōu)化生產(chǎn)過程的總電耗。

上述文獻的研究對象大都是傳統(tǒng)車間調(diào)度問題(Job-shop Scheduling Problem, JSP)，所研究的內(nèi)容較為簡單，而關(guān)于柔性作業(yè)車間調(diào)度問題(Flexible Job-shop Scheduling Problem, FJSP)的綠色車間調(diào)度研究還相對較少。柔性作業(yè)車間區(qū)別于傳統(tǒng)作業(yè)車間，具有工序順序、工藝路線和機器的不確定性。朱偉[8]提出一種改進非支配排序遺傳算法解決柔性作業(yè)車間多目標調(diào)度問題；Gong等[9]設(shè)計了一種模因算法用于解決具有工人柔性的多目標柔性車間調(diào)度；Zheng等[10]提出一種基于知識導向的果蠅優(yōu)化算法求解具有雙資源約束的柔性作業(yè)車間調(diào)度問題。上述研究中，多是只從經(jīng)濟目標角度出發(fā)解決柔性作業(yè)車間問題，少有考慮綠色目標，本文將從機床折舊的角度進行考慮，機床在使用過程中不可避免地產(chǎn)生折舊，從而導致單位時間內(nèi)產(chǎn)生的能耗增加，使用時間越久的機床，單位時間內(nèi)產(chǎn)生的能耗越多。因而在作業(yè)調(diào)度過程中，若有若干個調(diào)度方案完工時間相同，但因使用的機器不同導致產(chǎn)生的能耗不同，進而可以選擇能耗低的方案，此類方案大多使用折舊低的機床。

在求解方法方面，現(xiàn)有的研究提出了許多改進遺傳算法用于解決流水車間問題以及作業(yè)車間問題[11-13]，但是并未考慮引入均衡分散原則用于生成初始種群，因此本文建立了以最大完工時間和總能耗加權(quán)和最小為調(diào)度目標的柔性作業(yè)車間綠色調(diào)度模型，同時設(shè)計了一種改進的遺傳算法(Improved Genetic Algorithm, IGA)對其進行求解。在IGA中，不僅采用了一種三維實數(shù)的編碼方式、便于動態(tài)變化的工序機器號選擇與加工時間的數(shù)據(jù)存儲；同時提出了結(jié)合均衡分散原則的初始種群產(chǎn)生方法，使遺傳算法的收斂速度和全局搜索性能顯著提升，降低陷入局部最優(yōu)解的概率，使初始種群的解均勻遍布整個解空間。最后結(jié)合Brandimarte算例驗證所提出的算法的可行性和有效性，同時也分析了不同權(quán)重比例對最大完工時間和總能耗的影響。

1 柔性作業(yè)車間綠色調(diào)度問題

1.1 問題描述

對于柔性作業(yè)車間綠色調(diào)度問題可以有如下描述：車間中有n個工件在m臺機器上加工，工件i(i=1,2,…,n)具有Ni道工序，其中不同工件的工序數(shù)量可以不等，在本文中不考慮工件的工序順序柔性，因此每個工件只有一條指定的工藝路線；工件i的第j道工序Oij具有一定可選擇的機器數(shù)mij(mij

表1 簡單FJSP模型 Tab. 1 Simple FJSP model

在對本文提出的問題建立模型之前，首先對問題作一些合理的假設(shè)，以保證研究結(jié)果的嚴謹性和準確性：1)工序不能在加工過程中被打斷；2)本文不考慮工件在加工前的準備時間以及加工過程中的搬運時間；3)機器不會在加工過程中出現(xiàn)故障；4)每道工序僅能被一臺機器上加工一次；5)每臺機器在每個時刻只能加工一個工件；6)同一工件的不同工序必須在不同的時刻被加工；7)在初始時間，機器處于停止運轉(zhuǎn)狀態(tài)，且機器上沒有代加工工件；8)在初始時間，所有工件的原材料準備完畢；9)機器一旦開啟，只有加工完該機器所需加工的最后一道工序才停止運行，其余時間保持空載狀態(tài)。

1.2 柔性作業(yè)車間綠色調(diào)度問題模型建立

1.2.1 符號定義

為方便討論及讀者對本文的理解，現(xiàn)對本文中出現(xiàn)的所有符號作定義，如表2所示。

表2 符號定義 Tab. 2 Symbol definition

1.2.2 模型建立

基于以上問題描述以及條件假設(shè)，結(jié)合本文的調(diào)度目標為最大完成時間和總碳排放量的加權(quán)和，其中總能耗的計算公式參照文獻[14]所提出的普通機械加工設(shè)備工步間空載運行時停機節(jié)能的理論決策模型。其能耗分布如圖1所示，其中：t0～t1為機器的啟動時間，t2～t3，t4～t5都是機器的加工時間，t1～t2及t3～t4為機器的空載時間，t5～t6為機器的停機時間。

圖1 機床加工功率變化Fig. 1 Machine tool power change

結(jié)合本文研究問題以及上述表2的參數(shù)設(shè)定，可以得到機器在啟動、負載、空轉(zhuǎn)、停止時各產(chǎn)生的能耗。

(1)

(2)

(3)

(4)

進而可以得到在整個生產(chǎn)過程中總的能量消耗：

E=Eb+Ec+El+Ef

(5)

其中：式(1)表示機器啟動的總能耗；式(2)表示機器負載時的總能耗；式(3)表示機器空轉(zhuǎn)時的總能耗；式(4)表示機器停止運轉(zhuǎn)的總能耗；式(5)表示所有機器的總能耗。

時間是企業(yè)生產(chǎn)時考慮的最重要的因素，同樣能耗也是一項重要指標，本文的目標函數(shù)是使最大完工時間(Makespan)CT和總能耗E的加權(quán)和最小，以此建立如下FJSP模型。

(6)

s.t.Cij-Sij=Pij;i=1,2,…,n,j=1,2,…,Ni

(7)

Mij∈mij

(8)

(i,k)=1,2,…,n,(j,v)=1,2,…,Ni

(9)

Sij≥Ci(j-1);i=1,2,…n,j=1,2,…,Ni

(10)

m=1,2,…,k

(11)

Xkvij∈{0,1},(i,k)=1,2,…,n,

(j,v)=1,2,…,Ni

(12)

Kijm∈{0,1};i=1,2,…,n,

j=1,2,…,Ni,m=1,2,…,k

(13)

其中：式(6)表示目標函數(shù)，OS為所求的目標值，代表最小的最大完工時間C和總能耗E的加權(quán)和；式(7)表示工序不能在加工過程中被打斷；式(8)表示每道工序有且僅能在一臺機器上進行加工，并且只能加工一次；式(9)表示每臺機器一次在每個時刻只能加工一個工件；式(10)表示同一個工件的不同工序需要在不同時間被加工，且時間不能有重疊；式(11)表示機器一旦開啟，需要在加工完該機器上的最后一道工序才停止；式(12)表示0- 1變量，若工序Oij在工序Okv之后加工，則Xkvij=1，否則Xkvij=0；式(13)表示0- 1變量，若工序Oij在機器m上加工，則Kijm=1，否則Kijm=0。

2 改進遺傳算法設(shè)計

本文所求解的綠色FJSP問題主要有兩個子問題，即每道工序機器的選擇以及工序在機器上的加工順序，F(xiàn)JSP已被證實屬于NP-hard問題，而對于大規(guī)模的FJSP更是屬于求解困難的問題。針對這些問題設(shè)計了一種改進遺傳算法用于求解綠色FJSP。遺傳算法是一種具有隨機、自適應(yīng)和高度并行特點的優(yōu)化算法，由Holland教授于1975年首次提出，但也存在著明顯的缺點，遺傳算法的本質(zhì)是隨機性的搜索，不能保證最終所得解為全局最優(yōu)解[15-16]。針對這一問題，本文引入正交實驗的均衡分散原則生成初始種群，保證初始種群分布于用于整個解空間，提高初始種群的質(zhì)量；同時采用三維實數(shù)的編碼方式，避免了交叉操作后重復(fù)基因片段的產(chǎn)生，具體操作步驟如下：

步驟1 設(shè)置參數(shù)：種群規(guī)模N、迭代次數(shù)count、交叉概率Pc以及變異概率Pm。

步驟2 產(chǎn)生初始種群。令i=0，結(jié)合均衡分散原則隨機產(chǎn)生初始種群P。

步驟3 計算種群的適應(yīng)度值。采用權(quán)重分配法為兩個目標分配權(quán)重，然后求和得到個體適應(yīng)度值。

步驟4 判斷終止條件，如果滿足條件(i>count)，則輸出最優(yōu)解；否則進行下一步。

步驟5 進行選擇操作，采用輪盤賭的方法選擇適應(yīng)度值較優(yōu)的個體進入新的種群，種群規(guī)模仍為N。

步驟6 進行交叉操作，從種群中選取兩個個體，若random>Pc，則用雙個體算術(shù)交叉的方式對其進行交叉操作，然后放入新的種群；否則將兩個個體直接放入新的種群，直到所有的個體都執(zhí)行了交叉操作為止。

步驟7 進行變異操作，根據(jù)變異概率Pm判斷是否對個體進行變異操作，若random>Pm，則用動態(tài)步長的方式對其基因片段進行變異；否則進行下一步操作。

步驟8 求出當前種群的最優(yōu)解，令i=i+1，返回步驟4。

2.1 編碼機制

本文采用三維實數(shù)的編碼方式[17]，用元胞結(jié)構(gòu)進行存儲，存儲結(jié)構(gòu)為N×n×Ni，這種編碼方式的好處是方便對其中的基因進行修改以及交叉時不會產(chǎn)生沖突基因。每道工序的機器號為一條染色體的基因，每個染色體擁有n×Ni個基因，而一個種群擁有N條這樣的染色體。例如圖2所示為4×4的一條染色體，行代表同一個工件的不同工序的機器號，列代表不同工件的同一道工序的機器號，0表示該工件的該工序不存在。

圖2 染色體示例圖Fig. 2 Example diagram of chromosome

染色體中基因的位置決定了工件的加工順序，先自上而下加工所有工件的第一道工序，再同樣加工所有工件的第二道工序，直至所有工序都加工完成，例如圖2染色體對應(yīng)的加工順序轉(zhuǎn)化為表3,首先加工O11，再加工O21，然后繼續(xù)加工其余工序。

表3 基因加工順序 Tab. 3 Gene processing sequence

2.2 初始種群的產(chǎn)生

初始種群解質(zhì)量與最優(yōu)解之間的差距很大程度上決定了GA的搜索性能，而一般采用隨機方式產(chǎn)生的初始種群很難保證解的質(zhì)量，在搜索過程中難免會造成陷入局部最優(yōu)解以及增加搜索時長的情況。為了加強GA的全局搜索性能，本文結(jié)合均衡分散原則來生成初始種群，均衡分散原則是實驗設(shè)計(Design of Experiment, DOE)中的常用方法[18]，在實驗安排中,所挑選出來的水平組合是均勻分布在所有水平空間的，均衡分散原則如表4所示。以此原則為基準的初始種群生成方法主要遵守三個原則：1)所有機器被選擇的次數(shù)相等；2)同一工件的不同工序選用不同機器；3)不同工件的同一工序選用不同機器。以此方法生成的每一個解都具備三個維度上的分散性，提升了解的質(zhì)量，具體步驟如下：

步驟1 建立調(diào)用機器次數(shù)初始集a1×k=[0,0,…,0]。

步驟2 隨機生成工序Oij的機器號Mij，令am=Mij，其中Mij∈mij，m代表機器號。

表4 均勻分布點數(shù) Tab. 4 Evenly distributed points

假設(shè)存在一個每個面都有9個點的立方體中，根據(jù)均勻分散原則，在所有的面上都需要均勻分布點數(shù)，如表4所示坐標，在立方體中均勻分布著9個點。具體示例如圖2所示，該表為4×4的一條染色體，共有4個工件，每個工件4道工序，最終所選的機器集體現(xiàn)了上述三個原則，但考慮到實際情況中機器平均調(diào)用次數(shù)不一定為整數(shù)，本實例中共有6臺機器，每臺機器的理想調(diào)用次數(shù)為2.6，而機器1～4都調(diào)用三次，機器5、6調(diào)用兩次，因此原則1)可以具有一定柔性。

2.3 選擇算子

選擇操作的目的是為了讓具有高適應(yīng)度值的染色體存活下來，而高適應(yīng)度值意味著該個體的解質(zhì)量更高，在一次次迭代過程中，種群的規(guī)模N是固定不變的，但是其中的染色體是在不斷變化的，并且是朝著好的一面發(fā)展。本文采用輪盤賭的方法選擇染色體個體，具體步驟如下：

步驟2 隨機產(chǎn)生α,α∈(0,1)，若α∈(∑fi′,∑fi+1′)，則選取第i個個體，將此步驟循環(huán)N次，即得到新的種群。

2.4 交叉算子

在IGA中，交叉操作選擇雙個體算術(shù)交叉的方式，在基于機器的編碼或基于工件的編碼方式中，通常在兩個被選中染色體的相同位置選取兩個或者多個交叉位進行交叉，隨后再進行沖突檢測，檢查重復(fù)的基因片段，而在本文所采用的三維實數(shù)的編碼方式中，需要將該交叉方式進行改進，同時避免了產(chǎn)生相同的基因片段，無需進行沖突檢測，減少了交叉操作的步驟，示例如圖3所示，具體步驟如下：

步驟1 隨機從種群N中選取兩條染色體，染色體結(jié)構(gòu)為n×Ni，隨機確定兩個數(shù)βi,βj，β=(β1,β2,…,βn)，其中βi∈{1,2,…,Ni},N=N-2。

步驟2 在兩條染色體的每一行都確定一個交叉位，每個交叉位置的選擇用β，然后將兩條染色體進行交叉。繼續(xù)步驟1的操作，直至N=0。

圖3 染色體交叉Fig. 3 Chromosome crossover

2.5 變異算子

變異操作的目的是為了保證種群的多樣性，同樣也是為了增加算法的搜索方向，防止遺漏某些區(qū)域的解。本文因采用的是實數(shù)編碼，所以選擇動態(tài)步長[16]的方式來進行變異操作，從而達到搜索該方向局部空間的效果，實例如圖4所示，具體步驟如下：

步驟1 隨機生成X=(ε1,ε2)用于確定需要執(zhí)行變異操作的基因，其中ε1∈{1,2,…,n},ε2∈{1,2,…,Ni}，X為選中的機器號。

步驟2 確定基因的搜索方向，若X≤k/2，則搜索方向為正方向{X+1,X+2,…,k}；否則搜索方向為負方向{1,2,…,X-1}，其中X∈{1,2,…,k}。

步驟3 確定搜索的步長。為了保證局部搜索的有效性，若搜索方向為正方向，則將步長確定為L1，若L1不存在，將步長變?yōu)長3，直至步長存在L2i+1；否則步長為L2，L2不存在變?yōu)長4，直至步長存在L2i，其中L=(X+1,X-1,X+2,X-2,…,k,1)。

圖4 染色體變異實例Fig. 4 Example of chromosomal variation

3 算例研究和結(jié)果分析

為了驗證IGA的有效性，本文采用Matlab 2014a的M語言進行編程，并在Windows 7，Intel Core i5- 3337U，CPU 1.8 GHz，內(nèi)存4 GB，64位操作系統(tǒng)的計算機上運行。在整個實驗過程中，IGA的參數(shù)設(shè)置如下：迭代次數(shù)count=1 000，種群規(guī)模N=200，交叉概率Pc=0.8，變異概率Pm=0.1。

3.1 IGA性能分析

3.1.1 實驗1(8×8問題)

實驗1的8×8工件測試數(shù)據(jù)來自于文獻[19]，由8個工件、8臺機器組成，為了測試IGA的性能，將其目標函數(shù)設(shè)定為最小化最大完成時間，將所得結(jié)果與SPT規(guī)則、傳統(tǒng)GA以及Zhang等[20]提出的GA測試結(jié)果進行對比，其中SPT所能求得的最優(yōu)解為19，傳統(tǒng)GA求解的最優(yōu)解為16，Zhang等[20]的方法求得的最優(yōu)解為14，而本文所提算法求得的最優(yōu)解為14，由對比數(shù)據(jù)可知，IGA的求解結(jié)果已達到文獻記錄中的最優(yōu)解，圖5顯示了8×8算例中Makespan為14的調(diào)度方案。

3.1.2 實驗2(基準Brandimarte算例)

為了更好地驗證IGA的有效性，在基準Brandimarte算例MK01～MK08的基礎(chǔ)上分別運行10次，并取其中的最優(yōu)解分別與田旻等[21]提出的分層混合遺傳算法(Hierarchical Hybrid Genetic Algorithm, HHGA)，Ziaee[22]提出的基于構(gòu)造過程的啟發(fā)式算法(Heuristic Algorithm Construction Process, HACP)，夏俊紅等[23]提出的改進螢火蟲(Improved Glowworm Swarm Optimization, IGSO)算法進行對比。

從表5的統(tǒng)計結(jié)果來看，MK02、MK03以及MK06已經(jīng)達到了相關(guān)文獻算法的最優(yōu)值，其余問題的結(jié)果也接近于相關(guān)文獻算法的最優(yōu)值。與單個算法相比，本文算法得到的結(jié)果有7個優(yōu)于HACP得到的結(jié)果，有3個優(yōu)于HHGA得到的結(jié)果，有7個接近或等于IGSO得到的結(jié)果，由此可見本文算法與其余三種算法相比具有一定的優(yōu)越性，圖6顯示了20×10算例中最大完成時間為530的調(diào)度方案。

圖5 8×8實例(Makespan=14)調(diào)度方案Fig. 5 Scheduling scheme of 8×8 instance (Makespan=14)

圖6 20×10實例(Makespan=530)調(diào)度方案Fig. 6 Scheduling scheme of 20×10 instance (Makespan=530)

表5 Brandimarte算例結(jié)果分析 Tab. 5 Analysis of Brandimarte example results

3.1.3 算法分析

圖7為實驗1中傳統(tǒng)GA的收斂曲線，圖8為IGA的收斂曲線，從圖7～8中可以看出，傳統(tǒng)GA在第1 000代的時候才得到了最優(yōu)解，而IGA在420代的時候已經(jīng)得到了傳統(tǒng)GA最優(yōu)解相等的值，并在大約500代的時候得到了IGA所能得到的最優(yōu)解。此外，IGA在開始階段就快速收斂，并在之后收斂速度減緩，說明了IGA初始解集的質(zhì)量較高，具有一定的全局搜索性能。

圖7 8×8實例傳統(tǒng)GA收斂曲線Fig. 7 Traditional GA convergence curve of 8×8 instance

圖8 8×8實例IGA收斂曲線Fig. 8 IGA convergence curve of 8×8 instance

3.2 綠色FJSP結(jié)果分析

對于以最大完工時間(Makespan)CT和總能耗E的加權(quán)和最小為目標函數(shù)的綠色FJSP，為了保證實驗結(jié)果的可信度，數(shù)據(jù)采用基準Brandimarte算例的MK08，因其最終的Makespan較大，能夠較為明顯比較出不同α值得到結(jié)果的差異。機器的四階段(開機、空載、加工、關(guān)機)單位能耗取[42,14,25,43][24]，同時考慮新舊機器單位能耗不同的因素[25]，因不同使用年限的機器能耗不同，在這里本文假設(shè)舊機器的單位能耗為新機器的1.2倍，MK08算例中的10臺機器M1～M5為新機器，M6～M10為舊機器，因此舊機器的四階段(開機、空載、加工、關(guān)機)單位能耗為[50,17,30,52]對于α分別取[0.0,0.2,0.4,0.6,0.8,1.0]六個維度，測試結(jié)果如表6所示。

表6 不同α取值的綠色FJSP結(jié)果 Tab. 6 Green FJSP results with different α values

為了更好地分析不同α取值對OS、C、E的影響，將OS與E分別取除以100得到對比結(jié)果，如圖9所示。

圖9 FJSP結(jié)果分析Fig. 9 Analysis chart of FJSP results

從圖9可以發(fā)現(xiàn)：在α不斷增大的過程中，最大完成時間逐漸縮小，而總能耗也呈逐漸下降的趨勢，因此可以得出結(jié)論，最大完成時間與能耗呈正相關(guān)關(guān)系，企業(yè)在追求完工時間最小化的同時，也在潛在地追求能耗的最小。

4 結(jié)語

針對綠色FJSP進行研究，本文設(shè)計了IGA用于解決該類問題。依據(jù)GA的缺陷，采用三維實數(shù)的編碼方式，并在初始解集生成階段引入均衡分散原則，確保初始解集均勻分散在整個解空間，保證了初始解集的質(zhì)量；在交叉階段選用雙個體算術(shù)交叉的方式，結(jié)合實數(shù)編碼方式能夠避免單個解內(nèi)部的沖突；在變異階段采用了動態(tài)步長的方式進行變異，保證了對局部空間的有效搜索。最后將IGA運用于兩個實驗，實驗結(jié)果表明了IGA求解FJSP的有效性，同時分析了不同權(quán)重比例對最大完工時間CT和總能耗E的加權(quán)和的影響，實驗結(jié)果表明最大完工時間與總能耗呈正相關(guān)關(guān)系。

本文的不足之處在于僅考慮了機器柔性，下一步的研究方向是考慮其他的柔性約束，此外對于大規(guī)模調(diào)度，庫存對于工件的加工順序影響也值得研究。