顧九春，姜天華,2+，朱惠琦

(1.魯東大學 交通學院，山東 煙臺 264025；2.吉林大學 符號計算與知識工程教育部重點實驗室,吉林 長春 130012)

0 引言

作業(yè)車間調(diào)度問題(Job shop Scheduling Problem, JSP)通過合理安排各機器上工件的加工順序獲得期望的生產(chǎn)性能，由于該問題具有很強的理論和應(yīng)用背景，自提出以來，一直受到國內(nèi)外研究學者的廣泛關(guān)注，而且絕大多數(shù)JSP已被證明具有NP難特性。然而，傳統(tǒng)JSP只考慮與時間、質(zhì)量或成本等相關(guān)的經(jīng)濟指標，未關(guān)注與環(huán)境等相關(guān)的能耗指標，難以指導企業(yè)獲得真正意義上的最大利潤。

在當今能源危機日益嚴峻的形勢下，綠色制造受到世界絕大多數(shù)國家的重視，而節(jié)能調(diào)度作為實現(xiàn)綠色制造的重要手段之一，已逐漸引起學者們的興趣[1-2]。節(jié)能調(diào)度能夠通過制定有效的調(diào)度方案，在提高生產(chǎn)效率的同時實現(xiàn)節(jié)能、降耗、降成本的目標，相比于傳統(tǒng)JSP，節(jié)能調(diào)度問題的出現(xiàn)時間較晚，相關(guān)文獻仍較少。LIU等[3]建立了一種以最小化總能耗量和工件總權(quán)重拖期時間為目標的數(shù)學模型，并提出一種非支配排序遺傳算法進行求解；HE等[4]提出一種以最小化能耗和工件最大完工時間為目標的數(shù)學模型，并提出一種基于禁忌搜索的啟發(fā)式算法；GONZLEZ等[5]針對JSP，以總權(quán)重拖期時間和總能耗為優(yōu)化目標，提出基于Pareto的多目標進化算法、基于分解的多目標優(yōu)化算法和約束優(yōu)化方法進行求解；KEMMOE等[6]考慮具有能量閾值的JSP，提出一種基于局部搜索的貪婪隨機自適應(yīng)搜索算法進行求解；MAY等[7]以優(yōu)化車間總能耗量和工件最大完工時間為目標，提出一種遺傳算法求解多目標優(yōu)化問題。由上述文獻可知，在調(diào)度模型中引入與環(huán)境相關(guān)的能耗指標來同時優(yōu)化經(jīng)濟指標和能耗指標，既能改善車間生產(chǎn)性能，又能達到節(jié)能降耗的目的。然而，目前作業(yè)車間節(jié)能調(diào)度的成熟程度遠不及傳統(tǒng)JSP，還需對該類問題進行進一步研究，以使研究成果更加貼近實際生產(chǎn)。例如，上述文獻均假設(shè)車間內(nèi)機器的加工速度是固定的，而在現(xiàn)實生產(chǎn)中各機器可根據(jù)實際情況以不同的工作速度運行，并對應(yīng)不同的加工能耗和工件處理時間。一般情況下，機器加工速度越大，工件處理時間越短，加工能耗量越大；反之，機器加工速度越小，加工能耗量越小，工件處理時間越長，從而使降低車間能耗成為可能。JIANG等[8]針對具有多速度機器的作業(yè)車間，以最小化能耗成本和完工時間成本為目標，提出一種改進鯨魚優(yōu)化算法；SALIDO等[9]提出一種遺傳算法用于求解具有多速度機器的作業(yè)車間節(jié)能調(diào)度問題(Energy-saving Job shop Scheduling Problem, EJSP)；JIANG等[10]針對含多速度機器的JSP，以優(yōu)化車間能耗成本和完工時間成本為目標，提出一種離散鯨魚優(yōu)化算法。對于這類EJSP，需要考慮速度選擇和工件排序兩個子問題，通過合理選擇機器的工作速度，并安排各機器上工件的加工順序，達到節(jié)能降耗的目的。選擇速度雖然增加了問題的復雜程度，但是使其更加貼近實際生產(chǎn)，具有一定實際應(yīng)用價值。因此，本文以作業(yè)車間為對象，研究車間內(nèi)機器包含多種工作速度的節(jié)能調(diào)度問題，提出一種同時優(yōu)化工件最大完工時間和車間總能耗量的節(jié)能調(diào)度優(yōu)化算法。

高效的優(yōu)化算法有助于企業(yè)提高生產(chǎn)效率、降低能源消耗量，近年來智能優(yōu)化算法已經(jīng)成為節(jié)能調(diào)度問題主要的求解途徑?；依莾?yōu)化算法(Grey Wolf Optimization algorithm, GWO)是根據(jù)狼群等級制度和捕食行為而提出的一種新型群智能優(yōu)化算法[11]，該算法搜索原理簡單、易于實現(xiàn)，而且具有較高的收斂精度和較快的求解速度，已成功用于求解多種優(yōu)化問題[12-17]。然而，由于GWO最初用于解決連續(xù)優(yōu)化問題，灰狼個體在連續(xù)域內(nèi)進行位置更新，無法直接應(yīng)用于車間調(diào)度問題，姜天華[18]提出一種連續(xù)個體位置與離散調(diào)度解間的轉(zhuǎn)換方法，然而該方法需要在算法搜索過程中頻繁轉(zhuǎn)換，影響了算法的求解效率。為了克服這一缺點，JIANG等[19]提出一種離散GWO，通過個體與決策層個體的離散交叉操作體現(xiàn)GWO中決策層個體對其他個體更新的引導作用，使算法能夠直接在離散調(diào)度域內(nèi)運行，然而算法中的個體仍只根據(jù)決策層個體的信息進行更新，導致算法易出現(xiàn)早熟收斂。因此，本文采用一種雙模式并行搜索機制，即算法每次迭代時先將整個狼群劃分為兩個子群，然后分別對子群內(nèi)的個體執(zhí)行搜尋操作和跟蹤操作。在跟蹤模式下，個體根據(jù)決策層個體進行更新，算法執(zhí)行局部搜索；在搜尋模式下，個體根據(jù)記憶池機制進行更新，算法執(zhí)行全局搜索。為了協(xié)調(diào)算法的全局搜索和局部搜索能力，在搜索過程中動態(tài)調(diào)整各子種群中的個體數(shù)量，使算法前期側(cè)重于全局搜索，后期側(cè)重于局部搜索。另外，針對本文多目標優(yōu)化的特點，對GWO進行一系列設(shè)計和改進，提出一種多目標離散灰狼優(yōu)化算法(Multi-Objective Discrete Grey Wolf Optimization algorithm, MODGWO)，并通過大量仿真對其有效性進行驗證。

1 問題描述

(1)所有機器和工件在初始零時刻均為可用。

(2)每臺機器同時只可加工一個工件。

(3)每個工件同時只能被一臺機器加工。

(4)工件的加工過程不允許被中斷。

(5)各工件間相互獨立，同一工件不同工序間遵循一定的先后加工約束。

(6)不考慮機器故障和機器調(diào)整時間。

(7)在任一工件的加工過程中，機器的加工速度不允許被調(diào)整。

2 模型建立

2.1 車間能耗模型

本文車間總能耗可劃分為加工能耗和空載能耗兩部分，下面分別對各個能耗組成部分進行分析，建立車間能耗模型。

(1)加工能耗 指機器加工工件所消耗的能量[20]，總加工能耗

(1)

式中xikl為0-1變量，若工件i在機器k以速度檔l進行加工則xikl=1，否則xikl=0。

(2)空載能耗 指機器在相鄰工件的時間間隔內(nèi)空載運行所消耗的能量，即前一個工件已加工完，而后一個工件還未到達時，機器空載運行所消耗的能量[20]?？偪蛰d能耗

(2)

式中：SEk為機器k單位時間內(nèi)的平均空載能耗；MCk為機器k的完工時間；Wk為機器k的總負載，即機器k上所有工件加工時間之和。

根據(jù)上述分析，車間總能耗

(3)

2.2 作業(yè)車間節(jié)能調(diào)度模型

由前述可知，節(jié)能調(diào)度的目的是在提高生產(chǎn)效率的同時實現(xiàn)節(jié)能降耗。因此，本文以優(yōu)化車間總能耗和工件最大完工時間為目標，建立如下數(shù)學模型：

minF1=EC1+EC2；

(4)

minF2=CTmax。

(5)

s.t.

(6)

i=1,2,…,n,k=1,2,…,m；

(7)

i,j=1,2,…,n,k=1,2,…,m；

(8)

(9)

MCk=max{Cik},i=1,2,…,n；

(10)

Cik≥0,i=1,2,…,n,k=1,2,…,m；

(11)

xikl∈{0,1},i=1,2,…,n,

k=1,2,…,m,l=1,2,…,dk；

(12)

yijk∈{0,1},i,j=1,2,…,n,k=1,2,…,m。

(13)

式(4)表示最小化車間總能耗；式(5)表示最小化工件最大完工時間；式(6)表示工件在機器上的加工速度一旦確定后不允許更改；式(7)表示同一工件內(nèi)后道工序必須在前道工序完工后才能開工；式(8)表示任何機器在同一時刻只允許處理一個工件；式(9)表示機器的總工作負載；式(10)表示機器的完工時間；式(11)表示工序完工時間為非負；式(12)和式(13)表示0-1變量。

3 離散灰狼優(yōu)化算法

3.1 基本灰狼優(yōu)化算法

GWO是一種模仿狼群社會等級制度和捕食行為的群智能優(yōu)化算法[11]。在算法每次迭代過程中，種群內(nèi)的個體被劃分為頭狼α、下屬狼β、普通狼δ和底層狼ω，前三者屬于決策層個體，分別表示歷史最優(yōu)解、歷史次優(yōu)解和歷史第三優(yōu)解，ω對應(yīng)其余個體。在算法迭代過程中，α，β，δ負責定位獵物的位置，并引導ω更新位置，通過完成靠近、包圍和攻擊等一系列行為來捕食獵物。限于篇幅，GWO的具體原理和步驟請參考文獻[11]。

3.2 編碼方法

本文采用基于速度—工序的編碼方法，即每個調(diào)度解均包含長度相等的前后兩段，分別對應(yīng)速度選擇方案和工序排序方案，如圖1所示。其中O12表示工件1的第2道工序，其他工序依此類推。另外，前半段元素值表示各工序所在機器選擇的加工速度，后半段元素值表示各工序所屬工件的編號，相同元素值表示同一工件的不同工序，其出現(xiàn)的順序表示工序加工的先后順序。

對于JSP，每個工件的加工路徑已知，解碼時從左到右掃描每個調(diào)度解后半段內(nèi)的元素，并根據(jù)前半段元素的值確定每道工序所在機器的加工速度。處于后半段最左端的工序最先被調(diào)度，以盡可能早地在相應(yīng)的機器上加工，并獲得所有工序的開始時間和完工時間。其他工序以此類推，直到所有工序調(diào)度完為止。

3.3 種群初始化

對于一個群智能優(yōu)化算法，初始解的優(yōu)劣在很大程度上影響算法的計算性能。由于本文問題分為速度選擇和工序排序兩個子問題，種群初始化也分兩階段進行，對于每個個體，首先在前半段采用隨機方式獲得工序在相應(yīng)機器上的速度選擇方案，然后確定各工序的加工時間；后半段采用基于調(diào)度規(guī)則的方法，即以相同的概率選擇剩余負荷最多(Most Work Remaining, MWR)優(yōu)先[21]、剩余工序最多(Most Operation Remaining, MOR)優(yōu)先[21]和隨機規(guī)則(Random Rule, RR)獲得工序排序方案。

3.4 Pareto排序

多目標優(yōu)化問題無法直接根據(jù)適應(yīng)度值比較個體優(yōu)劣，需要通過Pareto排序?qū)⒎N群中的個體分為若干個非支配等級。首先找出當前種群中的非支配最優(yōu)解，構(gòu)成第一個非支配最優(yōu)解層，并為其中個體的等級賦值為1級，然后將這些解從種群中去除，在余下個體中找出新的非支配解，給其中個體的等級賦值為2級，依此類推，直到所有個體均被分級。顯然，等級數(shù)小的個體表現(xiàn)更優(yōu)。

3.5 確定決策層個體

在基本GWO中，新個體由當前個體根據(jù)決策層個體α，β，δ的信息產(chǎn)生。然而，由于多目標優(yōu)化問題無法直接通過比較適應(yīng)度值的大小來確定決策層個體，本文采用基于非支配等級和擁擠距離的方法獲得決策層個體，即根據(jù)種群中個體的非支配等級和擁擠距離對個體進行排序，排在最前面的3個個體有機會成為決策層個體。排序遵循的原則為：對于任意兩個個體，等級低的個體排在前面；若兩個個體等級相同，則比較二者的擁擠距離，擁擠距離大的個體排在前面。

首先根據(jù)上述排序原則從初始種群中選擇排在前3位的個體，分別將其作為α，β，δ；其次，每代個體更新完成后，根據(jù)排序原則從當前種群中選出3個個體與當前決策層個體合并，從而獲得一個子集；然后，對合并后子集內(nèi)的個體進行排序，確定新的α，β，δ。

3.6 外部檔案更新

為了存放搜索過程中的非支配解,建立一個外部檔案，并基于Pareto支配關(guān)系對其進行更新，更新方法如下：對于一個新產(chǎn)生的解，若其被外部檔案中的任一解支配，則拒絕其加入；若其支配外部檔案中的部分解，則將其加入外部檔案，并剔除受支配的解；若其與外部檔案中的所有解均為非支配關(guān)系，則新解直接進入外部檔案。

3.7 個體更新策略

在基本GWO中，個體只根據(jù)決策層個體的信息進行更新，可能導致在運行后期算法的種群多樣性下降，出現(xiàn)早熟收斂。本文采用跟蹤模式和搜尋模式的雙模式并行搜索機制，分別對應(yīng)局部搜索和全局搜索。每次迭代時，算法先將整個狼群劃分為兩個子群，再分別對子群內(nèi)的個體執(zhí)行搜尋操作和跟蹤操作。為了協(xié)調(diào)算法的全局搜索和局部搜索能力，通過在搜索過程中動態(tài)調(diào)整各子種群中個體的數(shù)量，使算法前期側(cè)重于全局搜索，后期側(cè)重于局部搜索。

3.7.1 跟蹤模式

與基本GWO相同，跟蹤模式下的個體主要根據(jù)決策層個體的信息進行更新。然而，由于基本GWO不能直接用于離散調(diào)度問題，本文根據(jù)問題特點設(shè)計了一種基于交叉操作的個體更新方法，即個體按照一定概率與α，β，δ進行交叉操作，從而獲得新的個體，如式(14)所示。

Xk(t+1)=

(14)

式中：Xk為灰狼k對應(yīng)的調(diào)度解，Xα,Xβ,Xδ為α，β，δ對應(yīng)的調(diào)度解；rand為一個0和1之間服從均勻分布的隨機數(shù)；CR表示交叉操作，前半段采用兩點交叉法，即在前半段任選兩個位置，互換父代個體中被選位置間的元素，后半段采用文獻[22]中的優(yōu)先交叉操作(Precedence Operation Crossover，POX)。

需要注意的是，交叉操作后將獲得兩個子代個體，根據(jù)支配關(guān)系選擇其中較優(yōu)的個體作為新個體。若兩個個體互不支配，則任選其中一個作為新個體。

3.7.2 搜尋模式

由跟蹤模式可以看出，個體只根據(jù)決策層的個體信息進行更新。因此，本節(jié)引入搜尋模式，其主要思想是通過記憶池機制進行全局搜索，即預(yù)先設(shè)定記憶池的大小為MS，然后對當前個體進行擾動操作，生成MS個候選解并填滿記憶池。通過評價記憶池中的所有個體，選擇其中最優(yōu)個體替代原來的個體，從而完成一個個體更新。不斷重復該過程，直到搜尋模式下的所有個體均完成個體更新。在評價記憶池個體時，首先找出記憶池中的非支配解，然后將原個體與其進行比較，若原個體被記憶池中某些非支配個體所支配，則從這些個體中任選一個替代原來個體，否則保持原來個體不變。

根據(jù)本文問題的特點，隨機執(zhí)行以下一種或兩種鄰域結(jié)構(gòu)進行個體擾動，鄰域結(jié)構(gòu)如下：

(1)速度選擇 隨機選擇一道工序，該工序?qū)?yīng)機器的可選速度應(yīng)多于一個，然后任選一個不同速度替代原來的值。

(2)工序排序 隨機選擇兩個屬于不同工件的工序，然后互換被選工序的位置。

3.7.3 全局和局部搜索的平衡

為了平衡算法局部搜索和全局搜索的能力，動態(tài)調(diào)整兩個子群中個體的數(shù)量，在算法運行前期側(cè)重于全局搜索，隨著迭代次數(shù)的增加，在算法后期側(cè)重于局部搜索。

用MR表示搜尋模式下子種群內(nèi)個體數(shù)量占整個種群的比率，其大小反映算法對全局和局部搜索的側(cè)重程度。MR較大時，算法側(cè)重于全局搜索；反之，算法側(cè)重于局部搜索。MR的值可通過式(15)進行調(diào)節(jié)，其中MRmax和MRmin分別為1和0；t和tmax分別表示算法的當前迭代次數(shù)和最大迭代次數(shù)。

MR=MRmax-(MRmax-MRmin)×t/tmax。

(15)

3.8 算法步驟

基于前述，MODGWO的具體步驟如下：

步驟1設(shè)置算法參數(shù)，包括種群大小、記憶池大小和最大迭代次數(shù)。

步驟2采用第3.3節(jié)的種群初始化方法，獲得初始調(diào)度解。

步驟3評價初始種群中的個體，確定決策層個體α，β，δ，并將非支配解加入外部檔案。

步驟4判斷是否達到算法終止條件，是則轉(zhuǎn)步驟8，否則執(zhí)行步驟5。

步驟5根據(jù)式(12)計算MR的值，并對狼群個體進行劃分。

步驟6對于每個灰狼個體，若處于搜尋模式，則對其執(zhí)行搜尋操作；否則，對其執(zhí)行跟蹤操作。

步驟7評價更新后的灰狼個體，更新決策層個體和外部檔案，然后轉(zhuǎn)步驟4。

步驟8算法結(jié)束，輸出外部檔案。

4 實驗結(jié)果與分析

為了測試MODGWO的性能，采用FORTRAN語言進行編程，并在WinXP系統(tǒng)下內(nèi)存為2 G的VMware Workstation上運行。

4.1 測試問題

基于所構(gòu)造的算例，采用文獻[24]中的比例指標和文獻[25]中的距離指標評價算法性能：

(1)比例指標ζr指算法r所獲非支配解集Sr提供的非支配解在整個參考集S*中所占的比例，

(16)

式中參考集S*是將所有算法的非支配解集合并而獲得的非支配解的集合?？梢姡苧值越大，算法得到的非支配解越多。

(2)距離指標IGDr指Sr中元素相對于參考集S*的距離，

(17)

4.2 參數(shù)分析

MODGWO主要包括種群大小PS、記憶池大小MS和最大迭代次數(shù)itermax3個參數(shù)。本節(jié)采用試驗設(shè)計方法(Design of Experiment, DOE)對這3個參數(shù)進行設(shè)置。為此，建立一個三因素四水平L16(43)正交表，如表1和表2所示。

表1 參數(shù)水平

表2 正交表和IGDr值

針對算例LA25，將每種參數(shù)組合下的算法均獨立運行10次，并以IGDr作為性能評價指標。根據(jù)表2中的數(shù)據(jù)計算各參數(shù)響應(yīng)值，如表3所示，所繪制的算法參數(shù)對計算性能的影響曲線如圖2所示。由表3可見，參數(shù)itermax的極差最大，表明該參數(shù)對算法性能影響最大，PS次之，MS影響最小。結(jié)合分析結(jié)果，將MODWWO參數(shù)設(shè)置為：種群大小PS=200，記憶池大小MS=15，最大迭代次數(shù)itermax=1 500。

表3 各參數(shù)的響應(yīng)值

4.3 改進策略的有效性分析

本節(jié)主要分析種群初始化方法和雙模式并行搜索方式兩種改進策略的有效性，對比算法如下：

(1)A1算法表示MODGWO采用隨機初始化方法獲得初始解。

(2)A2算法表示MODGWO每次迭代時不劃分種群，只采用單一的跟蹤模式進行搜索。

(3)A3算法表示MODGWO。

針對算例LA01～LA40，各算法獨立運行10次，采用IGDr，ζr，Time3個指標比較算法的性能，如表4所示。其中：Time為算法的平均運行時間(單位：s)；粗體表示算法獲得的最佳值。由表4可見，對于IGDr和ζr指標，A3算法表現(xiàn)最好，其在37個算例中獲得的IGDr值小于其他算法，在21個算例中獲得的ζr值大于其他算法；對于Time指標，A1和A3算法的運行時間相差不大，均大于A2算法，主要原因是搜尋模式中的記憶池機制增加了算法的運行時間。

表4 改進策略有效性分析

續(xù)表4

4.4 與其他算法的對比分析

對于具有多速度機器的EJSP，文獻[8-9]分別提出了鯨魚優(yōu)化算法和遺傳算法，并通過仿真算例驗證了算法的有效性。然而文獻[8-9]研究的均為單目標優(yōu)化問題，本文將這兩種算法稍作修改，得到多目標改進鯨魚優(yōu)化算法(Multi-Objective Improved Whale Optimization Algorithm, MOIWOA)和多目標遺傳算法(Multi-Objective Genetic Algorithm, MOGA)，并與本文所提算法進行了對比。

對于MOGA，首先基于本文的種群初始化方法獲得初始調(diào)度解，并利用Pareto排序法確定個體等級；其次，選擇算子采用二元錦標賽機制，從種群中隨機選擇兩個個體，個體等級不同則優(yōu)先選擇等級較低的個體，個體等級相同則選擇擁擠距離較小的個體；然后，采用文獻[9]的方法進行個體交叉和變異操作。為了便于比較，對比算法的參數(shù)設(shè)置如下：對于MOIWOA，種群大小均為200，最大迭代次數(shù)為1 500；對于MOGA，種群大小均為200，最大迭代次數(shù)為1 500，交叉率為0.8，變異率為0.2。算法對比結(jié)果如表5所示。

表5 算法對比結(jié)果

由表5可見，對于IGDr指標，MODGWO在39個算例中獲得的IGDr值小于其他算法，而且22個算例中的IGDr值均為零；對于ζr指標，MODGWO在所有40個算例中獲得的ζr值均大于其他算法，即能夠產(chǎn)生參考集S*中的大多數(shù)元素，其中22個算例中整個參考集S*元素均由MODGWO產(chǎn)生；對于Time指標，MOGA運行時間最短，MODGWO的運行時間雖然大于其他算法，但是計算結(jié)果明顯更優(yōu)。為了進一步比較算法性能，圖3給出3種算法在算例LA04和LA21下的收斂曲線，可見MODGWO的收斂情況明顯優(yōu)于其他兩種算法。圖4所示為算法在算例LA02和LA40下所獲解的分布情況，可見總能耗量和工件最大完工時間之間存在沖突關(guān)系。根據(jù)圖4中解的分布情況可以發(fā)現(xiàn)，MODGWO所獲解優(yōu)于其他兩種算法。綜上所述，MODGWO在求解本文多目標EJSP方面具有有效性。

圖5和圖6所示分別為算例LA07和LA27下MODGWO所獲得的甘特圖，圖中每個方框代表一道工序，方框下字符表示“工件—工序”，例如9-6表示工件9的第6道工序。

5 結(jié)束語

本文針對EJSP進行研究，建立以車間能耗總量和工件最大完工時間為優(yōu)化指標的數(shù)學模型，并提出一種MODGWO。該算法采用速度—工序兩段式編碼方法表示調(diào)度解，基于調(diào)度規(guī)則實現(xiàn)種群初始化，然后引入雙模式并行搜索方式，在搜索過程中動態(tài)調(diào)整全局和局部搜索的能力。為了使算法適用于多目標離散調(diào)度問題，提出一種基于個體非支配等級和擁擠距離的決策層個體選擇策略，并設(shè)計了基于交叉操作的離散個體更新方法。最后，對傳統(tǒng)JSP的40個基準算例進行改造，用于算法仿真測試，通過大量實驗表明MODGWO在求解本文EJSP方面的有效性。

下一步的研究方向如下：①進一步提煉與節(jié)能調(diào)度相關(guān)的啟發(fā)式規(guī)則，將其嵌入智能優(yōu)化算法中改善解的質(zhì)量；②將節(jié)能調(diào)度問題擴展到更復雜的制造系統(tǒng)，并考慮更多的現(xiàn)實約束，如動態(tài)生產(chǎn)環(huán)境、分時電價政策和可再生能源利用等；③將GWO與其他智能優(yōu)化算法結(jié)合，取長補短，以獲得更高效的求解算法。