考慮機床折舊的柔性作業車間綠色調度算法

王建華，潘宇杰，孫 瑞

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

0 引言

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

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

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

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

1 柔性作業車間綠色調度問題

1.1 問題描述

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

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

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

1.2 柔性作業車間綠色調度問題模型建立

1.2.1 符號定義

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

表2 符號定義 Tab. 2 Symbol definition

1.2.2 模型建立

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

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

結合本文研究問題以及上述表2的參數設定，可以得到機器在啟動、負載、空轉、停止時各產生的能耗。

(1)

(2)

(3)

(4)

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

E=Eb+Ec+El+Ef

(5)

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

時間是企業生產時考慮的最重要的因素，同樣能耗也是一項重要指標，本文的目標函數是使最大完工時間(Makespan)CT和總能耗E的加權和最小，以此建立如下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)表示目標函數，OS為所求的目標值，代表最小的最大完工時間C和總能耗E的加權和；式(7)表示工序不能在加工過程中被打斷；式(8)表示每道工序有且僅能在一臺機器上進行加工，并且只能加工一次；式(9)表示每臺機器一次在每個時刻只能加工一個工件；式(10)表示同一個工件的不同工序需要在不同時間被加工，且時間不能有重疊；式(11)表示機器一旦開啟，需要在加工完該機器上的最后一道工序才停止；式(12)表示0- 1變量，若工序Oij在工序Okv之后加工，則Xkvij=1，否則Xkvij=0；式(13)表示0- 1變量，若工序Oij在機器m上加工，則Kijm=1，否則Kijm=0。

2 改進遺傳算法設計

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

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

步驟2 產生初始種群。令i=0，結合均衡分散原則隨機產生初始種群P。

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

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

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

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

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

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

2.1 編碼機制

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

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

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

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

2.2 初始種群的產生

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

步驟1 建立調用機器次數初始集a1×k=[0,0,…,0]。

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

表4 均勻分布點數 Tab. 4 Evenly distributed points

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

2.3 選擇算子

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

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

2.4 交叉算子

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

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

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

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

2.5 變異算子

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

步驟1 隨機生成X=(ε1,ε2)用于確定需要執行變異操作的基因，其中ε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不存在，將步長變為L3，直至步長存在L2i+1；否則步長為L2，L2不存在變為L4，直至步長存在L2i，其中L=(X+1,X-1,X+2,X-2,…,k,1)。

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

3 算例研究和結果分析

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

3.1 IGA性能分析

3.1.1 實驗1(8×8問題)

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

3.1.2 實驗2(基準Brandimarte算例)

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

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

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

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

表5 Brandimarte算例結果分析 Tab. 5 Analysis of Brandimarte example results

3.1.3 算法分析

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

圖7 8×8實例傳統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結果分析

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

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

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

圖9 FJSP結果分析Fig. 9 Analysis chart of FJSP results

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

4 結語

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

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