柔性作業(yè)車間調(diào)度問題的多目標(biāo)優(yōu)化算法

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

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

0 引 言

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

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

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

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

1 FJSP調(diào)度模型

1.1 問題描述

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

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

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

1)最小化最大完工時(shí)間。

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

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

(1)

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

2)最小化最大能耗。

在現(xiàn)實(shí)的車間生產(chǎn)中，不僅機(jī)器加工工件時(shí)會(huì)產(chǎn)生能耗，機(jī)器等待加工時(shí)的空轉(zhuǎn)也會(huì)產(chǎn)生能耗。因此，能耗可分為2個(gè)部分，數(shù)學(xué)表達(dá)式如下：

(2)

(3)

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

f(2)=minQ

(4)

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

表1 機(jī)器功率表

3)最小化機(jī)器總負(fù)荷。

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

(5)

其中，Tj表示機(jī)器j的總加工時(shí)間，Tload表示機(jī)器總負(fù)荷。

2 基于改進(jìn)的NSGA-II算法設(shè)計(jì)

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

2.1 基于機(jī)器與工序的分段編碼策略

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

圖1 機(jī)器與工序編碼

2.2 混合初始化方法

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

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

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

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

(6)

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

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

2.4 基于工序與機(jī)器的分段交叉策略

1)工序部分的交叉。

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

圖2 工序部分的POX交叉

2)機(jī)器部分的交叉。

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

圖3 機(jī)器部分的均勻交叉

2.5 基于工序與機(jī)器的分段變異策略

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

圖4 工序與機(jī)器部分的變異

Step1選取2對(duì)復(fù)制了Parent1與Parent2基因的染色體作為Children1與Children2。

Step2在染色體基因上隨機(jī)指定2個(gè)不重復(fù)的突變位置點(diǎn)。

Step3工序部分：Children1與Children2各自把2個(gè)突變位置上的基因進(jìn)行互換。

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

2.6 自適應(yīng)交叉、變異算子的設(shè)計(jì)

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

(7)

(8)

2.7 算法基本流程

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

圖5 INSGA-II算法流程圖

3 實(shí)驗(yàn)結(jié)果與分析

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

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

1)雙目標(biāo)實(shí)驗(yàn)。

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

表2 mk01～mk07解集

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

表3 NSGA-II與INSGA-II對(duì)比

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

表4 算法運(yùn)行時(shí)間對(duì)比

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

注：圖中時(shí)間和能耗為單位時(shí)間和單位能耗，無單位

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

注：圖中時(shí)間為單位時(shí)間，無單位

2)三目標(biāo)實(shí)驗(yàn)。

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

注：圖中時(shí)間和能耗為單位時(shí)間和單位能耗，無單位

4 結(jié)束語

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