徐 明，張劍銘，陳松航，陳 豪

(1.福州大學電氣工程與自動化學院，福建 福州 350108；2.中國科學院泉州裝備制造研究所福建省復雜動態(tài)系統(tǒng)智能辨識與控制重點實驗室，福建 泉州 362200)

0 引 言

在過去，人們遇到多目標問題時往往通過簡單加權的方式把多目標問題轉成單目標問題進行求解。多目標問題的加權求解方式雖然簡單易行，但卻面臨求解結果過于單一且加權系數(shù)事先難以確定的問題。Pareto方法綜合多個優(yōu)化目標，摒棄加權系數(shù)給出一組Pareto最優(yōu)解結果供選擇，使解集變得更為靈活多樣[1]。

柔性作業(yè)車間調度問題(Flexible Job Shop Problem, FJSP)是典型的多目標優(yōu)化問題，它對傳統(tǒng)作業(yè)車間調度問題(Job Shop Problem)作了進一步的拓展，使每個工件都可以在其對應的機器集中進行加工，消除了機器資源的唯一限制，具有更強的適用性[2]。相較而言，F(xiàn)JSP更貼近實際車間的生產，有著重要的現(xiàn)實意義。

近年對于求解FJSP這類多目標問題的研究主要集中在智能優(yōu)化算法領域。姜天華[3]把遺傳算子插入灰狼算法中以增強算法的全局收斂能力，同時加入了變鄰域搜索算法提高了局部尋優(yōu)能力，使算法得到更好的全局最優(yōu)解。Tang等人在文獻[4]中建立包含生產時間間隔的多目標車間調度模型，并將粒子群算法與模擬退火算法進行混合以求解FJSP。程子安等人[5]為解決FJSP問題提出了多種群遺傳算法，通過優(yōu)化種群初始化方法與種群精英個體互換的方式，增強了算法的收斂性能。文獻[6]提出了改進的遺傳算法，該算法在每次迭代中通過設置解的閾值來選擇進入精英庫中的個體，使得解集更為多樣化。文獻[7-9]通過優(yōu)化遺傳算法初始解與使用改進的個體交叉、變異策略的方式大幅提高了解的質量與收斂速度。丁舒陽等人在文獻[10]中使用粒子群算法求解FJSP問題時，把包含工序與機器信息的操作算子加入粒子的迭代中，使種群快速收斂。文獻[11]針對NSGA-II過早收斂且容易陷入局部最優(yōu)的問題，加入泊松、平均以及高斯算子以平衡算法全局收斂于局部尋優(yōu)能力。

傳統(tǒng)多目標優(yōu)化算法求解FJSP問題時往往難以獲得滿意的解集個數(shù)且收斂速度與收斂精度較低。因此改進傳統(tǒng)多目標優(yōu)化算法以獲得更優(yōu)的收斂性能與更多樣的解集顯得尤為重要。

1 FJSP調度模型

1.1 問題描述

有n個工件需要在m臺機器上進行加工，各個工件都有固定數(shù)量的工序。工序間有生產次序約束，各個工件在需要加工時應選擇合適的加工機器，以便完成生產。其中，各個工序對應的可用加工機器集以及在機器集上的加工時間為已知條件。該問題旨在通過確定適當?shù)臋C器分配和工序排列來尋找滿足完工時間與能耗等優(yōu)化指標的最佳調度方案。

1.2 FJSP多目標優(yōu)化模型

本文求解的多目標FJSP同時優(yōu)化最大完工時間與最大能耗，且滿足以下約束條件[12]：所有機器在0時刻開啟等待加工，機器上的最后工件加工結束后關機以節(jié)約能耗；工件只能在機器集中選擇被某臺機器加工，加工過程不能中途停止；工件的各個工序必須按次序進行，工件前一道工序若未結束則不可啟動下一道工序；同一時刻每臺機器上最多操作一道工序，每個時刻一個工件最多也只能被某臺機器操作。

1)最小化最大完工時間。

柔性作業(yè)車間生產中往往是多個工件同時在不同機器上加工，直到所有工件被加工完成。最后一個工件被加工完成的時間就是最大完工時間，完工時間越小說明調度方案越好。數(shù)學表達可用如下公式表示：

f(1)=minCmax=min{Ci|i=1,2，…，n}

(1)

其中，Cmax代表最大的完工時間，Ci代表工件i的完工時間，n是工件總數(shù)量。

2)最小化最大能耗。

在現(xiàn)實的車間生產中，不僅機器加工工件時會產生能耗，機器等待加工時的空轉也會產生能耗。因此，能耗可分為2個部分，數(shù)學表達式如下：

(2)

(3)

其中，Qj表示機器j在這次加工過程中產生的總能耗；Q為m臺機器消耗能量的總和。因此，最小化最大能耗的數(shù)學描述可表示為：

f(2)=minQ

(4)

車間所有可使用的加工機器的功率信息如表1所示。

表1 機器功率表

3)最小化機器總負荷。

在生產加工時，不僅要盡可能地使加工能耗與最大完工時間最小，還要考慮機器的總負荷。因此，工序在選擇加工機器時需要權衡機器的加工能耗與機器的加工時間，在能耗相同的情況下選擇加工時間短的機器，以使機器總負荷最小化。機器總負荷最小化數(shù)學表達式如下：

(5)

其中，Tj表示機器j的總加工時間，Tload表示機器總負荷。

2 基于改進的NSGA-II算法設計

NSGA-II是由遺傳算法改進而來，通過加入非支配排序思想使得算法具有運算速度與收斂性方面的優(yōu)勢。且該算法具有一次性獲得多個Pareto解的能力，常被用在FJSP問題的求解中[13-14]。本文提出的INSGA-II算法主要將初始化方法、交叉與變異策略、交叉與變異算子進行改進，使算法在解集與收斂性方面得到提升。

2.1 基于機器與工序的分段編碼策略

在NSGA-II算法中，針對問題選擇恰當?shù)木幋a方式能夠良好地反映問題特征，同時使算法快速收斂并提高求解精度[15-16]。本文采用工序與機器融合的分段編碼方式，工序編碼部分的實數(shù)代表工件號，而相同工件號重復的次數(shù)依次代表該工件的工序。機器編碼與工序編碼是相對應的，表示相應位置工序的機器選擇。該種分段編碼策略可以保證染色體解的可行性，避免后續(xù)繁雜的修正操作。圖1為機器與工序編碼。

圖1 機器與工序編碼

2.2 混合初始化方法

在NSGA-II算法中，初始化策略影響著解的好壞與收斂速度，因此種群初始化是一個重要的步驟?；旌铣跏蓟椒ㄏ茸尮ば蚓幋a部分全部使用隨機初始化方法，然后讓對應的機器編碼部分一半使用啟發(fā)式初始化另一半使用隨機式初始化。

啟發(fā)式初始化方法在一開始就為工序選擇可選機器集中加工時間最短的那臺；隨機初始化方法則是給工序隨機指定某臺可選設備。啟發(fā)式初始化方法能夠取得比隨機式初始化方法更快的收斂速度，然而卻在一定程度上影響種群多樣性進而削弱算法全局搜索能力；隨機式初始化方法可以提升種群多樣性但是會降低收斂速度與算法穩(wěn)定性。因此將2種初始化方法結合能夠在保證一定收斂速度的同時增強算法全局搜索能力。

2.3 適應度函數(shù)與選擇操作

根據(jù)FJSP模型中的優(yōu)化目標，算法的適應度函數(shù)為：

(6)

其中，f(1)、f(2)、f(3)分別為式(1)、式(4)與式(5)中的最小化最大完工時間、最小化最大能耗以及最小化機器總負荷優(yōu)化目標函數(shù)。因此算法需要衡量3個適應度函數(shù)，并根據(jù)計算后的適應度對個體進行非支配排序，同時計算處于同一支配層級的個體擁擠度[17]。

算法的選擇操作選定二元錦標賽選擇策略[18]，其思想為：先將種群進行非支配排序并對處于同一支配層級的個體進行擁擠度計算；然后從種群中有放回地抽取2個個體，選擇支配層級高的個體進入子代種群，若支配層級相同則選擇擁擠度小的個體；最后不斷重復抽取選擇操作，直至形成的新種群大小達到原種群的規(guī)模。

2.4 基于工序與機器的分段交叉策略

1)工序部分的交叉。

合適的交叉算子使子代繼承父代的優(yōu)良部分，同時提高后續(xù)種群的多樣性，提升算法的全局收斂性。基于工序優(yōu)先順序的交叉(Precedence Preserving Order-based Crossover, POX)的優(yōu)良特性決定了它更適合應用于FJSP問題[19]。POX交叉如圖2所示，首先從所有工件中選擇子工件集J1，然后子代1先繼承父代1中與J1相同的基因，最后子代1的其余位置則由父代2與J1相異的基因填充。

圖2 工序部分的POX交叉

2)機器部分的交叉。

為避免出現(xiàn)不可解，同時提高種群多樣性，機器部分采用均勻交叉方式。均勻交叉如圖3所示，首先在Parent1上隨機選取r個點位(r

圖3 機器部分的均勻交叉

2.5 基于工序與機器的分段變異策略

在本文編碼方式下，工序部分可采用常見的兩點交換突變，而機器部分由于各個工序對應的可選機器數(shù)量不同，為避免染色體修正操作，因此只在非遺傳關系的父代子代之間進行個別基因的等位交換，以此達到突變效果(見圖4)。具體步驟如下：

圖4 工序與機器部分的變異

Step1選取2對復制了Parent1與Parent2基因的染色體作為Children1與Children2。

Step2在染色體基因上隨機指定2個不重復的突變位置點。

Step3工序部分：Children1與Children2各自把2個突變位置上的基因進行互換。

Step4機器部分：Children1與Children2按照突變位置從Parent2與Parent1上復制基因。

2.6 自適應交叉、變異算子的設計

交叉算子ρc與變異算子ρm對算法的收斂性能起著重要影響[20]。ρc越大越容易產生新個體并增強種群全局搜索能力，但容易使種群不穩(wěn)定且使局部尋優(yōu)能力變弱；ρc過小容易使種群陷入局部最優(yōu)并降低算法收斂速度。而ρm過大會影響種群穩(wěn)定與收斂精度[21-22]，過小則容易使算法“早熟”。傳統(tǒng)的NSGA-II算法使用數(shù)值固定的交叉、變異算子，顯然無法滿足對FJSP問題的求解。因此設計一種隨迭代次數(shù)動態(tài)改變的自適應交叉、變異算子，數(shù)學描述如下：

(7)

(8)

2.7 算法基本流程

INSGA-II算法流程如圖5所示。

圖5 INSGA-II算法流程圖

3 實驗結果與分析

實驗環(huán)境：CPU采用Inter Core i5 2.3 GHz，運行內存為8 GB，軟件采用MATLAB R2016a。將INSGA-II算法與其他普通多目標優(yōu)化算法在同等運行條件下運行，通過比較所獲解集驗證INSGA-II算法收斂性能與解集的豐富性。

mk01～mk07是由Brandimarte[23]設計的典型FJSP數(shù)據(jù)集，這7組數(shù)據(jù)包含不同的工件數(shù)、工序數(shù)、機器數(shù)以及加工時間。為更好地驗證算法性能，測試分為雙目標與三目標進行實驗，其中，雙目標采用最大完工時間與最大能耗為優(yōu)化目標。

1)雙目標實驗。

表2為INSGA-II算法在mk01～mk07數(shù)據(jù)集上的實驗結果。其中每個方括號代表一個解集，方括號中第一個數(shù)字代表最大完工時間，第二個數(shù)字代表最大能耗。

表2 mk01～mk07解集

表3為INSGA-II與NSGA-II在mk01～mk07進行實驗的結果，選取各自解集中完工時間最小的解來進行對比。從表中可以看出，INSGA-II不但在解集數(shù)量上多于NSGA-II,且最大完工時間與最大能耗有明顯減少。因此INSGA-II在解集多樣化與收斂精度方面要優(yōu)于未改進的普通NSGA-II算法。

表3 NSGA-II與INSGA-II對比

表4為GA、PSO、INSGA-II在mk01～mk07數(shù)據(jù)集上各自運行10次的平均運行時間，從表中可見，相較于傳統(tǒng)的多目標優(yōu)化算法，INSGA-II有著更快的收斂速度。

表4 算法運行時間對比

此外，圖6為NSGA-II與INSGA-II在mk01數(shù)據(jù)集上運行得到的Pareto最優(yōu)前沿解的對比，可以看出，INSGA-II不僅解集更為豐富，且獲得的最大能耗與最大完工時間這2個優(yōu)化目標的解也要更小，可見INSGA-II的全局收斂性能要更優(yōu)。

注：圖中時間和能耗為單位時間和單位能耗，無單位

使用mk01數(shù)據(jù)集進行實驗測試，從INSGA-II算法求得的解集中獲取一個調度結果，如圖7所示。其中，縱軸為加工機器，橫軸為最大完工時間，O2,3表示第2個工件的第3道工序，以此類推。此外，同一機器上的不同工件用不同灰度區(qū)分。從圖中可看出，使用INSGA-II能夠獲得較優(yōu)的調度方案。

注：圖中時間為單位時間，無單位

2)三目標實驗。

在mk01數(shù)據(jù)集上進行實驗，同等條件下將NSGA-II與INSGA-II進行算法性能對比。三維的Pareto前沿對比結果如圖8所示。從圖中可以看出，INSGA-II所獲解的范圍更大，全局性能更好；INSGA-II解的個數(shù)也要更多，解集多樣性得到了保持；INSGA-II算法尋找到的解集質量也要更優(yōu)，可見其全局收斂性與局部搜索性要更好。

注：圖中時間和能耗為單位時間和單位能耗，無單位

4 結束語

本文在考慮FJSP問題和多目標優(yōu)化的特點后，構建了以最大完工時間、最大能耗、機器總負荷為優(yōu)化目標的柔性作業(yè)車間調度模型。在模型優(yōu)化目標下，提出一種改進的多目標優(yōu)化算法用于該模型的求解。通過該算法可有效解決FJSP問題，得到滿意的調度方案，為生產管理者提供多種選擇方案。最后在Matlab平臺上進行對比實驗，驗證了所提算法的有效性。