基于能耗的柔性作業(yè)車間調(diào)度多目標優(yōu)化算法

張麗 王魯

摘 ?要： 針對柔性作業(yè)車間調(diào)度問題中的約束條件，考慮到低碳排放是制造業(yè)急需解決的問題，構(gòu)建了一種基于最大完成時間和最大能耗的數(shù)學模型，提出一種改進的多目標優(yōu)化算法。首先，在傳統(tǒng)的NSGA?Ⅱ算法中融入粒子群算法的思想，提高解集的搜索能力;其次，將機器和工序部分進行分層編碼，保證解集的合法性;然后，使用一種改進的密度估計方法計算平均距離，保證解集的分布性。為了驗證算法的有效性，使用mk01～mk07標準測試數(shù)據(jù)對NSGA?Ⅱ算法及改進的多目標優(yōu)化算法進行對比實驗。結(jié)果顯示，改進后算法得到的Pareto最優(yōu)解集在解的多樣性及收斂性方面優(yōu)于傳統(tǒng)多目標算法。

關鍵詞： 柔性作業(yè)車間調(diào)度; 多目標優(yōu)化; 能耗; 分層編碼; 調(diào)和平均數(shù); 融合非支配排序進化算法

中圖分類號： TN911.1?34 ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2020）07?0126?05

Multi?objective optimization algorithm for flexible job shop scheduling

based on energy consumption

ZHANG Li， WANG Lu

（College of Information Science & Engineering， Shandong Agricultural University， Taian 271018， China）

Abstract： In view of the constraints in the flexible job shop scheduling problem， an urgent issue of low carbon emission to be solved in the manufacturing industry is considered， a mathematical model based on maximum completion time and maximum energy consumption is constructed， and an improved multi?objective optimization algorithm is proposed. The particle swarm optimization is integrated into the traditional NSGA?Ⅱ algorithm in order to improve the search ability of solution set. The parts of machine and process are subjected to hierarchical coding to ensure the validity of the solution set. An improved density estimation method is used to calculate the average distance to ensure the distribution of the solution set. In order to validate the validity of the algorithm， mk01 ～ mk07 standard test data is used to perform contrast experiments to make comparison between the NSGA?Ⅱ algorithm and the improved multi?objective optimization algorithm. The results show that the Pareto optimal solution set obtained by the improved algorithm is superior to that by the traditional multi?objective algorithm in terms of diversity and convergence of solution.

Keywords： flexible job shop scheduling; multi?objective optimization; energy consumption; hierarchical coding; harmonic average; fusion non?dominated sorting genetic algorithm

0 ?引 ?言

近年來，車間調(diào)度問題也面臨著環(huán)境和經(jīng)濟的雙重解決問題[1]，因此，通過提高資源的利用率來降低能耗的產(chǎn)生對于節(jié)能減排這一目標具有極其重要的意義。在當前行業(yè)中設計一種降低能耗的模型對于提高生產(chǎn)效率必不可少[2]。

現(xiàn)實生活中，單目標已經(jīng)無法滿足人們對于優(yōu)化得到最優(yōu)解的需要，傳統(tǒng)的多目標處理方法是將多目標問題通過加權和的方式轉(zhuǎn)變?yōu)閱文繕藛栴}求解，這種方法的優(yōu)點是操作簡易，缺點是每次只能獲得一個解，多目標Pareto方法是在求解的過程中同時考慮多個目標，產(chǎn)生一組Pareto最優(yōu)解，減少了計算時間，增加了解的多樣性[3]。

文獻[4]對車間調(diào)度的標準進行評價，并設計了一種改進的遺傳算法來優(yōu)化工業(yè)機器在加工不同工件時產(chǎn)生不同能耗的問題。文獻[5]建立了車間調(diào)度的完工時間、加工成本、質(zhì)量以及能耗四個目標的最小化模型，然后提出一種基于廣泛數(shù)值分析的性能評估方法。文獻[6]建立了一種優(yōu)化能源消耗和使工作流程更靈活有效的調(diào)度模型，并對金屬加工工廠車間生產(chǎn)調(diào)度問題的案例進行了研究。文獻[7]以能耗和平均時間為目標，建立了基于遺傳算法的車間作業(yè)調(diào)度問題的多目標研究方法。文獻[8]設計了相應的矩陣編碼、交叉算子，改進了非劣前沿分級方法，并提出了基于Pareto等級的自適應變異算子以及精英保留策略。

傳統(tǒng)的多目標優(yōu)化算法在求解柔性作業(yè)車間調(diào)度問題時會出現(xiàn)解集個數(shù)和目標函數(shù)值并不如意的情況，因此，改進傳統(tǒng)的多目標優(yōu)化算法對于得到更多的解集個數(shù)，提高算法的快速收斂性具有重要意義。

1 ?問題描述及數(shù)學建模

1.1 ?多目標優(yōu)化理論

首先給出有關多目標優(yōu)化問題的一般描述[9]，給定決策向量[X=（x1，x2，…，xn）]，滿足下列約束：

[gi（X）≥0， ? ?i=1，2，…，k] （1）

[hi（X）≥0， ? ?i=1，2，…，k] （2）

設有[r]個相互沖突的優(yōu)化目標，則優(yōu)化目標可以表示為：

[f（X）=（f1（X），f2（X），…，fr（X））] （3）

尋求[X*=（x*1，x*2，…，x*n）]，使[f（X*）]在滿足約束條件（1）和（2）時達到最優(yōu)。

多目標優(yōu)化中，各個目標的解相互約束，最優(yōu)解未必只有一個，在進行多目標問題的研究過程中，不能簡易地比較各解，通?？汕蟮貌槐绕渌魏谓獠畹慕饧痆10]，相比于傳統(tǒng)的將多目標轉(zhuǎn)為單目標的方法，增加了解的多樣性，為決策者提供了一個較佳的選擇空間。

1.2 ?柔性作業(yè)車間調(diào)度問題理論

柔性作業(yè)車間調(diào)度問題（Flexible Job Shop Schedu?ling Problem，F(xiàn)JSP）是一類進行任務配置和順序約束的資源分配問題，關于FJSP的描述[11]如下：

[n]個工件，集合表示為：[J={J1，J2，…，Ji，…，Jn}]，

[i∈[1，n]];

[m]臺機器，集合表示為：[M={M1，M2，…，Mj，…，Mm}]，

[j∈[1，m]]。

每個工件需要經(jīng)過若干道工序加工才能完成，每個工件的工序的數(shù)目可以是不相同的，并且每道工序可以選擇在不同的機器上進行加工[12]。首先需要做出如下約束條件[13?14]：

1） 工件在不同機器的加工時間是已知的，且每類工件加工工序已經(jīng)預先確定;

2） 在零時刻所有的工件都可以被加工;

3） 加工過程中，任一道工序一旦加工開始則不允許中途中斷;

4） 同一臺機器只能在同一時刻加工一道工序;

5） 每道工序必須在其前一道工序完成才能進行后續(xù)工序。

1.3 ?數(shù)學建模

1） 最小化最大完成時間

最大完成時間是柔性作業(yè)車間調(diào)度過程中多個工件同時進行加工，所有工件加工結(jié)束需要的時間。時間越短，表明實際生產(chǎn)中的效率越高，其數(shù)學表達式為：

[f（1）=min Cmax=min{Cii∈n}] （4）

式中：[Cmax]是指最大完成時間;[n]表示工件的總數(shù)量;[Ci]表示工件[i]的完成時間，機器[i]總的時間等于加工時間[runtimei]和待機時間[idlei]的總和。

[Ci=runtimei+idlei] （5）

[f（1）=min Ci] （6）

式（6）表示最小化最大完成時間。

2） 最小化最大能耗

機器除了在加工過程中會產(chǎn)生能耗外，在待機時也會產(chǎn)生相應的能耗，隨著時間的增加，產(chǎn)生的能耗也會增加，因此，定義關于能耗的數(shù)學公式為：

[Qi=PWi×runtimei+PIi×idlei] （7）

式中：[PWi]為機器[i]的加工功率;runtime[i]為機器[i]的運行時間;[PIi]為機器[i]的待機功率;[idlei]為機器[i]的待機時間;[Qi]為機器[i]的能耗。

[Q=i=1mQi] （8）

式中：[Qi]為機器[i]的加工功率加上待機功率的總和;[Q]為[m]臺機器的總能耗。

[f（2）=min Q] （9）

式（9）將最大能耗的目標函數(shù)設置為最小值，能耗與完成時間有關，時間越長能耗也就越大。

各機器功率參數(shù)設置如表1所示。

2 ?改進的多目標優(yōu)化算法流程

NSGA?Ⅱ是目前應用比較廣泛的多目標進化算法之一，其在求解多目標問題時應用也比較多，該算法具有運行速度快、解集的收斂性好等優(yōu)點。改進的多目標優(yōu)化算法主要是基于融合非支配排序遺傳算法（Fusion Non?dominated Sorting Genetic Algorithms，F(xiàn)NSGA）對搜索空間中的個體進行快速非支配排序，算法具體操作流程如下。

2.1 ?編解碼方式

FJSP需要解決兩個子問題，即機器的選擇問題和工序的排序問題。為了處理這兩個子問題，這里采用分層編碼的方式，采用兩個[L]維（[L]為所有工件的總工序數(shù)）向量分別來表示工序和機器，其中，第一行代表工序的排序，向量中的每個分量為不大于工件總數(shù)的整數(shù)，第二行代表機器的選擇順序，向量中的每個分量為不大于機器總數(shù)的整數(shù)。

染色體的編碼方式如圖1所示，這是一個關于3個工件3臺機器柔性作業(yè)車間調(diào)度的問題。第一行是關于工序的排序問題，其中“1”表示工件1，“2”表示工件2;第一行第一次出現(xiàn)的“1”表示工件1的第一道工序，第二次出現(xiàn)的“1”表示工件1的第二道工序;第二行是關于機器的選擇問題，其中，第一個元素“2”表示工件1的第一道工序在機器2上加工，第二個元素“1”表示工件3的第一道工序在機器1上加工。

解碼就是將粒子轉(zhuǎn)換為對應的時間矩陣、能耗矩陣、機器矩陣和對應的機器加工向量，根據(jù)以上轉(zhuǎn)換產(chǎn)生相應的調(diào)度方案，從而根據(jù)調(diào)度方案生成對應的調(diào)度甘特圖。

2.2 ?初始化

對算法中涉及到的參數(shù)進行初始化設置。根據(jù)參數(shù)設置生成粒子群初始位置，求解初始粒子群的適應度，對初始粒子群進行非支配排序，初始化局部最優(yōu)粒子群解集和全局最優(yōu)粒子，保存全局最優(yōu)粒子。

2.3 ?選擇操作

適應度函數(shù)的選取對問題的求解非常重要，使用層次分析方法，其思想如圖2所示。

具體是重新按工序排好序，根據(jù)機器的開始加工時間和結(jié)束時間計算機器總的加工時間，這里用到的目標函數(shù)為1.3節(jié)中的最大完成時間和最大能耗兩個目標函數(shù)，將對應的粒子[xi]逐個解碼得到機器總的時間向量[C]，運行時間向量runtime，讀取出每個機器的加工功率[PWi]和待機功率[PIi]。

第一個目標函數(shù)最大完工時間為[f1（xi）=max（Ci）]，機器[i]的空閑時間向量[idlei=Ci-runtimei];

第二個目標函數(shù)最大能耗為：[f2（xi）=max（runtimei?PWi+idlei?PIi）]。

粒子[xi]所對應的適應度函數(shù)[f（xi）=[f1（xi） ? ? f2（xi）]]，分別計算各目標對應的適應度函數(shù)值。

2.4 ?交叉操作

選擇操作是將具有較高適應度的一半粒子遺傳給下一代，同時用適應度好的前一半粒子的位置替代適應度較低的后一半粒子的相應矢量。在交叉操作中，后一半粒子作為待交叉因子，兩兩進行結(jié)合配對，將產(chǎn)生的子代和父代作比較，選擇適應度高的一半再進入下一代，更新后代粒子的位置。

[y1=2?α*x1+（1-2?α）*x2] （10）

[y2=2?α*x2+（1-2?α）*x1] （11）

按照式（10）和式（11）進行交叉操作，其中，[y1]，[y2]是產(chǎn)生的父代粒子;[x1]，[x2]是子代粒子;[α]是與[x1]維數(shù)相同的隨機數(shù)向量，向量中的每個值[α∈（0，12）]。按照此種方式進行交叉的優(yōu)點是繼承了父代的優(yōu)良基因。

對新產(chǎn)生粒子的位置進行判斷，若超過編碼范圍，則將其重新隨機分配在編碼范圍內(nèi)，計算交叉后粒子的適應度值。

2.5 ?變異操作

對每個粒子產(chǎn)生一個隨機數(shù)[r]，[r～N（0，1）]，通過將該隨機數(shù)和預先設定的變異概率相比較來判斷是否進行變異操作。如果變異概率比這個隨機數(shù)大，則粒子重新進行搜索，其最優(yōu)位置保持不變，這主要是為了增加遺傳算法的全局搜索能力。

結(jié)合文獻[3]中的變異操作，使用一種停滯阻止策略，通過對全局最優(yōu)粒子進行變異操作來產(chǎn)生更好的全局最優(yōu)粒子，減少遺傳算法在迭代過程中陷入早熟的現(xiàn)象，防止出現(xiàn)局部最優(yōu)。

對新產(chǎn)生粒子的位置進行檢查，若超出編碼范圍，則將其重新隨機分配在編碼范圍內(nèi)，計算變異后粒子的適應度值。

2.6 ?多目標優(yōu)化中擁擠密度估計方法改進

多目標優(yōu)化算法大多采用密度估計維護進化群體的多樣性，為每個個體估計鄰域密度值，密度值越大說明個體周圍越擁擠，分布性能越差。通過在進化群體中保留鄰域密度較小的個體，刪除鄰域密度較大的個體，保證解集的分布性。

在進行密度估計時，個體密度估計僅考慮周圍鄰近個體的影響，鄰域個體數(shù)目為2或[k]（[k]<種群數(shù)量），使用的距離為歐氏距離，此計算公式的缺點是只考慮了同一Pareto非支配等級個體。

本文采用一種改進的密度估計方法，即Harmonic平均距離（調(diào)和平均數(shù)），主要用來解決在無法掌握總體單位數(shù)的情況下，只有變量值，需要得到平均數(shù)的情況下使用的一種數(shù)據(jù)方法。其思想為：針對種群的第[i]個個體，假設目標空間中與其距離最近的[k]個個體的歐氏距離為[di，1，di，2，…，di，k]，則個體[i]的Harmonic平均距離[di]如式（12）所示：

[di=kj=1k1di，j=k1di，1+1di，2+...+1di，k] （12）

為了避免鄰域個體數(shù)目和Pareto非支配等級的局限，式（12）中的參數(shù)[i]的取值范圍為種群數(shù)目為-1，即排除自身個體的影響。

3 ?實驗結(jié)果及分析

mk01～mk07是7組包含不同工件數(shù)、不同機器數(shù)、不同工序數(shù)的部分柔性作業(yè)車間調(diào)度問題測試數(shù)據(jù)[15]，通過實驗得到的Pareto解集個數(shù)也不盡相同。FNSGA在各個測試集上進行實驗得到的結(jié)果如表2所示。表2中，Pareto解集這一列中數(shù)據(jù)（50，383.5），前者表示最大完成時間為50，后者表示最大能耗為383.5，依次類推。

以下以mk06測試數(shù)據(jù)為例進行分析，mk06是一組包含10個工件，10臺機器，150道工序的柔性作業(yè)車間調(diào)度問題。

將FNSGA與NSGA?Ⅱ進行單獨實驗，得到的對比結(jié)果見表3。NSGA?Ⅱ得到的第一組數(shù)據(jù)（3，60，387），3表示Pareto解集個數(shù)，60表示最大完成時間最大值，387表示最大能耗最大值，依次類推。結(jié)果表明，改進后的算法最大完成時間和最大能耗比改進前少，得到的Pareto解集個數(shù)多于或等于未改進前的。算法獨立運行30次，最優(yōu)運行時間對比如表4所示，表中比較了傳統(tǒng)的NSGA?Ⅱ只使用GA，PSO以及改進算法的最優(yōu)運行時間。

FNSGA和NSGA?Ⅱ算法使用mk06測試數(shù)據(jù)進行實驗得到的Pareto解集的對比實驗圖如圖3所示。圖3中，F(xiàn)NSGA得到的Pareto解集共有6個，NSGA?Ⅱ得到的Pareto解集共4個。通過對比觀察可以看出，改進后的算法解集個數(shù)多于未改進的，同時最大能耗也比未改進的要低，收斂性也較好。

不同的非支配解對應不同的調(diào)度方案，因此，得到的最佳調(diào)度甘特圖也是不相同的。FNSGA算法使用mk06測試數(shù)據(jù)進行實驗，得到的其中一個最佳調(diào)度方案如圖4所示，圖中橫坐標表示完成時間，縱坐標表示10臺機器，從圖4中可以看出不同工序在不同機器上的加工情況，同一顏色代表同一工件，O1，1 表示工件1的第一道工序，依次類推。圖中[Cmax]為最大完成時間，最大完成時間為132。

4 ?結(jié) ?語

本文針對柔性作業(yè)車間調(diào)度和多目標優(yōu)化的特點，建立了基于考慮最大完成時間和最大能耗的數(shù)學模型，通過最小化最大完成時間和最小化最大能耗，在多種約束條件下，使用多目標優(yōu)化算法，將改進后的算法應用于柔性作業(yè)車間調(diào)度中，通過在Matlab平臺上進行仿真實驗，得到最優(yōu)調(diào)度方案和Pareto解集，為決策者的決策提供了多種選擇，通過對比實驗驗證了改進后算法的有效性。

注：本文通訊作者為王魯。

參考文獻

[1] 費凡.面向節(jié)能優(yōu)化的多目標柔性作業(yè)車間生產(chǎn)調(diào)度方法研究[D].合肥：合肥工業(yè)大學，2018.

[2] 黨世杰.低碳排放約束的柔性作業(yè)車間調(diào)度研究[D].鄭州：鄭州航空工業(yè)管理學院，2017.

[3] 吳定會，孔飛，田娜，等.教與同伴學習粒子群算法求解多目標柔性作業(yè)車間調(diào)度問題[J].計算機應用，2015，35（6）：1617?1622.

[4] ESCAMILLA J， SALIDO M A， GIRET A， et al. A metaheuristic technique for energy?efficiency in job?shop scheduling [J]. Knowledge engineering review， 2016， 31（5）： 475?485.

[5] JIANG Z， ZUO L， MINGCHENG E. Study on multi?objective flexible job?shop scheduling problem considering energy consumption [J]. Journal of industrial engineering and management， 2014， 7（3）， 589?604.

[6] DAI M， TANG D， GIRET A， et al. Energy?efficient scheduling for a flexible flow shop using an improved genetic?simulated annealing algorithm [J]. Robotics and computer?integrated manufacturing， 2013， 29（5）： 418?429.

[7] MAY G， STAHL B， TAISCH M， et al. Multi?objective genetic algorithm for energy?efficient job shop scheduling [J]. International journal of production research， 2015， 53（23）： 1?19.

[8] 鞠錄巖，楊建軍，張建兵，等.改進NSGA算法求解多目標柔性車間作業(yè)調(diào)度問題[J].計算機工程與應用，2019，55（13）：260?265.

[9] 王淑娟.柔性作業(yè)車間的多目標動態(tài)穩(wěn)健調(diào)度研究[D].濟南：山東大學，2014.

[10] 梁艷.基于混合型進化算法的柔性制造優(yōu)化研究[D].大連：大連理工大學，2013.

[11] 楊立熙，王秀萍.基于免疫遺傳算法求解多目標柔性作業(yè)調(diào)度問題[J].武漢理工大學學報（信息與管理工程版），2018，40（1）：69?74.

[12] 畢孝儒，張黎黎，賀拴，等.面向無等待多目標柔性車間調(diào)度問題的遺傳蜂群優(yōu)化算法[J].現(xiàn)代計算機（專業(yè)版），2015（23）：11?16.

[13] 王春，張明，紀志成，等.基于遺傳算法的多目標動態(tài)柔性作業(yè)車間調(diào)度[J].系統(tǒng)仿真學報，2017，29（8）：1647?1657.

[14] KONAK A， COIT D W， SMITH A E. Multi?objective optimization using genetic algorithms： a tutorial [J]. Reliability engineering & system safety， 2006， 91（9）： 992?1007.

[15] BRANDIMARTE P. Routing and scheduling in a flexible job shop by tabu search [J]. Annals of operations research， 1993， 41（3）： 157?183.