自適應多種群Jaya算法求解綠色并行機調度問題

王建華，楊 琦，朱 凱

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

0 引言

在并行機調度問題中，設置操作長期以來被認為是可以忽略或被認為是處理時間的一部分，雖然這對于一些調度來說是合理的，但對于有些情況下是需要明確的[1]。例如，化工廠在加工一種混合物轉換到另一種混合物時，反應器必須經過清洗，清洗時間取決于之前的工作和后續(xù)的工作。如果前一種化學物質影響后一種化學物質，可能需要很長的清洗時間，以相反順序只需更短時間[2]。另一方面，當今社會環(huán)境問題日益嚴重，綠色制造研究備受關注。作為現(xiàn)代制造模式，綠色制造旨在保證產品功能與質量的同時減少能源浪費，實現(xiàn)經濟指標和綠色指標的協(xié)同優(yōu)化[3-4]。因此，形成了本文所研究的具有設置時間的綠色并行機調度問題(Green Parallel Machine Scheduling Problem with Set-up Time, GPMSP-ST)。

目前，解決并行機調度問題常用到精確算法、近似算法以及智能優(yōu)化算法。精確算法包括分支界定，最速下降法等運籌學算法[5-6]，該類算法在小規(guī)模問題中能在短時間內獲得最佳解，但面對較大規(guī)模問題時，求解時間較長，若問題具有非凸性，則不存在通用的最優(yōu)解求解算法?；趧討B(tài)規(guī)劃的近似算法可以提出能夠保證最優(yōu)解不丟失的遞推方程，在較長時間內能夠保證算法獲得最優(yōu)解，但其本質上仍屬于窮舉法，時間復雜度基本為指數(shù)型，且只能應用于能提出相應規(guī)則的簡單并行機調度問題[7-9]。相較于前兩種算法，智能優(yōu)化算法具有求解速度快、普適性強、求解質量高等優(yōu)點，近年來得到了廣泛研究。軒華等[10]基于遺傳算法和禁忌搜索算法提出一種混合啟發(fā)式算法求解了每階段含不相關并行機的多階段混合流水車間問題。宋強[11]以異構并行機為研究對象，提出混合多目標教與學算法解決了最小化makespan和提前、延誤懲罰總成本的多目標問題。時維國等[12]以最小化最大完工時間為單目標，提出一種改進灰狼算法，有效解決了帶相同并行機的混合流水車間調度問題。付亞平等[13]針對生產中存在的串并聯(lián)共存的布局環(huán)境，研究了特殊的混合并行機調度問題，并提出一種改進的非支配遺傳算法進行求解。張潔等[14]構建了一種兩階段蟻群并行搜索算法，對于非等效并行機車間調度問題，明顯提高了獲得較優(yōu)解的概率。以上文獻并未涉及工序間的設置時間，當加工不同工件由于設置操作產生序列相關準備時間時，設置時間就必須明確。胡大勇等[15]以最小化最大完工時間為目標，研究了設置時間與順序相關的等同并行機調度，對建立的數(shù)學規(guī)劃模型所求問題下界評價了遺傳算法所得近似最優(yōu)解的質量。何雨潔等[16]驗證了所提出的混合離散教與學算法可以有效解決廣泛存在的復雜并行機調度問題，即帶到達時間、加工約束、多工序和工序間設置時間的并行機調度問題。李作成等[17]針對帶工件加工約束和序相關設置時間的異構并行機調度問題，提出一種分布估算方法并驗證了其有效性和魯棒性。FANJUL-PEYRO等[18]提出了新的混合整數(shù)線性規(guī)劃和基于數(shù)學規(guī)劃的算法，經過測試比較現(xiàn)有模型和算法，證實了該算法在具有作業(yè)序列設置時間的不相關并行機調度問題上的求解效果更好。VALLADA等[19]針對帶工序設置時間的異構并行機問題，提出一種性能優(yōu)異的增強局部搜索的遺傳算法。YEPES-BORRERO等[20]考慮了異構并行機中具有設置時間和設置中附帶額外資源的情況，設計了3種元啟發(fā)式算法，并證實了考慮資源約束的算法能產生更好結果。在關于并行機調度的研究中，基本以最小化完工時間這類經濟指標為優(yōu)化目標，近年來，逐漸有學者考慮能耗等綠色因素。李凱等[21]考慮了具有能耗成本約束的并行機調度問題，提出了改進的最早交貨期優(yōu)先(Earliest Due Date firstly, EDD)算法并驗證了其有效性。

根據(jù)已有文獻來看，在考慮設置時間的并行機調度問題上，考慮能耗、碳排放等綠色指標的文獻尚不多見，且大多研究采用傳統(tǒng)智能優(yōu)化算法。VENKATA RAO教授[22]在2016年提出的Jaya算法相較于其他智能優(yōu)化算法具有無參數(shù)控制、求解速度快、全局搜索能力強等優(yōu)點。近年來，Jaya算法也逐步應用到車間調度領域，但大部分研究集中在流水車間調度問題領域，少有應用于并行機調度領域內。因此，本文建立了最小化最大完工時間與最小化機器總能耗的雙目標優(yōu)化模型，在Jaya算法的基礎上，設計子種群數(shù)量可隨搜索情況自適應改變的多種群策略，形成可以求解多目標的自適應多種群Jaya算法(Self-Adaptive Multi-Population Jaya algorithm, SAMP-Jaya)，經過測試分析，驗證了該算法求解GPMSP-ST問題的有效性與魯棒性。

1 具有設置時間的綠色并行機調度問題

1.1 問題描述

考慮序列相關準備時間的異速并行機調度問題由m臺并行機器和n個工件組成，每個工件可以在任意機器上加工且每個工件只需加工一次。工件加工時間取決于機器的性能，在不同的機器上加工時間往往不同。同一機器上加工不同工件時，需要一定加工準備時間，不同工件間加工準備時間基本不同，處于加工準備時間時，機器為空載狀態(tài)，能耗為空載能耗。綠色并行機調度問題在優(yōu)化最大完工時間的同時，也需考慮機器能耗，保證經濟指標與綠色指標的優(yōu)化同步進行。

1.2 問題模型

為了構建當前調度的數(shù)學模型，現(xiàn)定義相關符號如表1所示。

表1 符號定義

根據(jù)上述定義，建立如下數(shù)學模型，優(yōu)化目標為最小化最大完工時間和最小化機器總能耗。

(2)

s.t.

(3)

k=1,2,…,m;h=1,2,…,qk。

(4)

k=1,2,…,m;h=1,2,…,qk。

(5)

k=1,2,…,m;h=1,2,…,qk。

(6)

(7)

(8)

Xikh={0,1};i=1,2,…,n;k=1,2,…,m;h=1,2,…,qk。

(9)

其中：式(1)和式(2)為數(shù)學模型中的雙目標函數(shù)；約束(3)表示每個作業(yè)都能調度到一臺機器上；約束(4)確保每臺機器同一加工位置只能加工一個工件；約束(5)保證工件一旦開始加工，則不能中斷；約束(6)表示同一機器上相鄰加工位置存在前后緊前關系；約束(7)表示每臺機器加工時間起始時間為0時刻；約束(8)表示每臺機器的第一個加工工件不需要設置時間；約束(9)表示Xikh只能為0或1。

2 自適應多種群Jaya算法

GPMSP-ST為離散型問題，對于求解連續(xù)性問題的Jaya算法而言，本文設計了一種排序機制將離散與連續(xù)結合起來。此外，為了提升初始種群的質量，隨機選擇兩種機器分配規(guī)則中的一種。相較于固定種群，多種群方法可以將整個種群分為多個子種群并將其分配至整個搜索空間，每個子種群具有在不同區(qū)域搜索的能力，從而可以提高搜索多樣性，有效檢驗問題的變化。GPMSP-ST為多目標問題，解的優(yōu)劣性需要衡量多個目標值，本文采用非支配排序的方法給解劃分等級，通過計算各等級擁擠度得到最優(yōu)解與最劣解。SAMP-Jaya算法不需要調整特定于算法的參數(shù)，求解效果具有良好的魯棒性。多種群的搜索有助于提升算法全局搜索能力，不易陷入局部最優(yōu)。

2.1 編碼與解碼

GPMSP-ST可以分為工件排序與機器分配兩個子問題。本文采用二維實數(shù)編碼方式，可以有效映射問題的解空間。設每一個解矩陣X包含兩個向量，分別為基于工件排序的向量X1和基于機器分配X2，現(xiàn)有一個9×3 GPMSP-ST的例子，X1=[1,5,4,9,8,2,6,3,7]，X2=[2,3,2,1,3,2,2,1,3]，表示工件1在2號機器加工，工件5在3號機器加工，以此類推。3臺機器的加工工件順序矩陣分別為Y1=[9,3]，Y2=[1,4,2,6]，Y3=[5,8,7]。編碼示例如圖1所示。

工件在各機器加工時間和工件間設置時間如表2和表3所示。

表2 工件加工時間

表3 各工件間設置時間

此例中，經解碼后，其調度甘特圖如圖2所示。

2.2 多規(guī)則種群初始化

高質量種群有助于算法的尋優(yōu)，但是為避免算法陷入局部最優(yōu)，同時也要考慮種群多樣性，因此本文采用多規(guī)則初始化種群，依然以2.1節(jié)中9×3的問題為例。

工件加工向量初始化：首先為加工工件序列創(chuàng)建數(shù)值為0～1隨機值的位置向量Z1=[A1,A2,A3,…,A9]，然后將所有數(shù)值按降序進行排序，最后將位置向量數(shù)值所對應的原工件序列更換位置，具體步驟如圖3所示。

機器分配向量初始化：每個種群個體初始化時會隨機產生一個0～1的隨機數(shù)，然后根據(jù)CALDEIRA等[23]提出的規(guī)則結合本文問題形成如下規(guī)則進行機器分配：

(1)隨機規(guī)則 若隨機數(shù)小于0.8，為每個工件隨機分配相應的機器。

(2)工作量均衡規(guī)則 若隨機數(shù)大于等于0.8，根據(jù)工件加工順序逐一為每個工件分配機器，每當為一個新工件分配機器時，將統(tǒng)計所有機器被使用次數(shù)，優(yōu)先分配尚未達到使用平均數(shù)的機器給待分配機器的加工工件，倘若有若干機器可供選擇，隨機選擇一臺機器。

2.3 種群的劃分與合并

多種群相比于固定數(shù)量的種群，子種群的數(shù)目與選擇將是算法性能的關鍵問題。為了滿足種群的多樣性，SAMP-Jaya算法將對VENKATA RAO等[24]提出的多目標Jaya算法(Multi-Objective Jaya algorithm, MO-Jaya)作出如下修改：

(1)根據(jù)解的質量劃分多個子種群，使用子種群的數(shù)量將解分布在搜索空間上，而不是集中在某個特定的區(qū)域內，因此，算法有望產生最優(yōu)解。

(2)根據(jù)解的變化情況自適應改變子種群數(shù)量，以跟蹤最佳解決方案并改進搜索過程多樣化，此外，重復解被新生解所代替，以保持算法多樣性和勘探性。若第n代種群被劃分為m個子種群，經過更新后形成新子種群并且合并成第n+1代新種群。當新種群的最優(yōu)解優(yōu)于舊種群時，則m=m+1，目的是為了增加搜索過程的探索特性，否則m=m-1，因為算法更需要開發(fā)性而不是探索性。

種群的劃分與合并過程如圖4所示。

2.4 Pareto尋優(yōu)及個體擁擠度計算

在單目標優(yōu)化的情況下，很容易根據(jù)解的適應度來判斷解的優(yōu)劣性。但是在存在多個沖突目標的情況下，很難從一組解中決定最優(yōu)解與最劣解。為了有效處理多個目標，本文利用非支配等級以及個體擁擠度兩種指標來評價個體解?；趦?yōu)勢概念可以將群體劃分幾個等級。其規(guī)則如下：設有兩個解方案Xi和Xj，只有當Xi在所有目標方面不比Xj差，并且至少在一個目標上嚴格優(yōu)于Xj時，解Xi支配解Xj，即解Xi具有更高的等級。等級高的解被認為優(yōu)于其他的解。若兩個解擁有相同的等級，具有較高擁擠距離的解被視為優(yōu)于其他解[25]。這保證了從搜索空間的稀疏區(qū)域中選擇解決方案，有助于提升解的多樣性。擁擠度(Crowding Distance, CD)計算步驟如下：

步驟1對于每一個目標函數(shù)，將等級相同的解按相應目標函數(shù)值遞增順序排序。

步驟2設排序集合中有n個解，將邊界解(第一個解和第n個解)分配最大擁擠距離CD=∞，對于排序集合j=2到n-1中所有其他解，擁擠距離為：

(10)

具有最高等級且擁擠度最高的為最優(yōu)解，反之為最劣解。當二者確定后，新種群中每個個體將根據(jù)2.5節(jié)中更新公式進行更新。

2.5 種群個體變量更新策略

Jaya算法在每一輪迭代時會更新每個變量值，變量的值更新后，其新目標值將與舊值比較，只有更好的解才被考慮用于下一代。其更新公式如下所示：

H(i+1,k)=H(i,k)+r1(H(i,b)-

|H(i,k)|)-r2(H(i,w)-|H(i,k)|)。

(11)

式中：i，k分別表示迭代和候選解的索引；H(i,k)表示第k個候選解在第i次迭代后的變量值；r1和r2是[0,1]范圍內產生的隨機數(shù)，二者充當比例因子，確保解良好的多樣化。與此同時，每次更新，候選解都嘗試接近最佳解并遠離最差解，因此，實現(xiàn)了搜索過程良好強化與多樣化的同步性。

SAMP-Jaya算法繼承了Jaya算法的更新思想，即試圖接近成功(達到最佳解)，并試圖避免失敗(遠離最差解)。并在此基礎上設計了一種位置向量更新機制來解決離散型變量更新問題。工件加工順序碼更新過程如圖5所示。

機器分配經過初始化規(guī)則后，其更新過程與圖5類似。

2.6 SAMP-Jaya算法流程

SAMP-Jaya算法具體步驟如下：

步驟1根據(jù)2.1節(jié)描述設計變量，2.2節(jié)中的規(guī)則初始化種群，并設置迭代次數(shù)為終止條件。

步驟2計算種群中每個候選解的所有目標值。

步驟3基于解的質量，將整個種群劃分為m個組(m的初始值為2)。

步驟4每個子種群使用2.5節(jié)描述的更新規(guī)則獨立更新每個種群的解，每一個修改后的解只有比舊方案更好的情況下才被接受(修改后的解被支配)。

步驟5將所有子種群合并為一個整體，并根據(jù)2.3節(jié)描述修改m值。

步驟6檢查終止條件。若搜索過程已經達到終止條件，則終止循環(huán)并輸出最佳解決方案，否則返回步驟2。

3 算例測試與分析

3.1 測試準備

在頻率為2.10GHz，內存4GB，AMDA8-5550MAPU的計算機上進行仿真，選用NetBeansIDE8.2進行編程，為體現(xiàn)實驗結果的公平性，各算法相同參數(shù)設置為：種群大小為50，終止條件為迭代次數(shù)為200代。

3.2 SAMP-Jaya與兩種智能算法比較分析

為了驗證本文所提出的SAMP-Jaya算法的優(yōu)越性，將SAMP-Jaya算法與ABREU等[26]提出的混合遺傳算法(HybridGeneticAlgorithm,HGA)、何雨潔等[16]提出的混合離散教與學算法(Hybridmulti-objectiveTeaching-Learning-basedOptimization,HDTLBO)進行比較。根據(jù)上述兩篇文獻已有測試結果表明，取兩種算法較優(yōu)表現(xiàn)參數(shù)如表4所示。

表4 兩種算法參數(shù)取值

以最大完工時間為單目標，測試算例是隨機生成的，其中處理和設置時間是從U(50,100)和U(125,175)中兩個均勻分布中隨機提取。共有如下3種情況：①當處理和設置時間平衡(ProcessingSetupBalanced,PSB)時，它們都是從U(50,100)中提取的；②當處理時間占據(jù)主導(ProcessingDominant,PD)時，處理時間和設置時間分別從U(125,175)和U(50,100)中提?。虎郛斣O置時間占據(jù)主導(SetupDominant,SD)時，處理時間和設置時間分別從U(50,100)和U(125,175)中提取。測試問題的規(guī)模n和m的集合分別為{20,40,60,80,100,120}和{2,4,6}。將SAMP-Jaya算法運行15次，比較各算法的最優(yōu)解與標準偏差(StandardDeviation,STD)如表5所示。表中粗體表示相同算例中優(yōu)于其他算法的最優(yōu)解。

表5 各算法最優(yōu)解與標準差對比

由表4中所有算例可以發(fā)現(xiàn)，相較于其他兩種算法，SAMP-Jaya算法所得最優(yōu)解次數(shù)總計為15次，只在3種規(guī)模的算例中未取得最優(yōu)；在所有規(guī)模問題中均表現(xiàn)良好，在未取得最優(yōu)解的3種算例中也接近其他算法的最優(yōu)解，綜合效果相較其他兩種算法更加優(yōu)越。所得標準差中，SAMP-Jaya算法所得結果在10次中獲得較小值，HGA算法與HDTLBO算法分別在4種不同算例下取得最小值，所得結果表明SAMP-Jaya算法離散程度整體更加穩(wěn)定，算法具有良好的魯棒性。

以PD情況下40×6規(guī)模問題為例，如圖6所示為其最大完工時間為1 380的最優(yōu)調度甘特圖,其中：括號內數(shù)字為工件號，其余數(shù)字均為加工或設置時間。

3.3 SAMP-Jaya求解GPMSP-ST性能分析

為了驗證SAMP-Jaya求解GPMSP-ST問題的性能，本節(jié)以最大完工時間與能耗為雙目標，在PSB情況下，采用20×8，40×8，60×8，80×8，100×8，120×8規(guī)模問題，單位加工能耗在(10 J,30 J)中均勻分布，單位空載能耗在(1 J,5 J)中均勻分布。比較SAMP-Jaya算法與MO-Jaya算法，以及MENG等[27]提出的變鄰域結構遺傳算法Ⅲ(Variable Neighborhood Structure Genetic Algorithm Ⅲ, VNSGAⅢ)在求解質量和收斂性能兩個方面的效果。采用非支配解集數(shù)量(N)、非支配解集占參考解集比率(NR)、世代距離(GD)和反世代距離(IGD)4個指標來評價3種算法所求非支配解集質量的優(yōu)劣，后3項指標定義如下：

(1)NR。該比率表示所衡量算法所獲得的非支配解占參考解集的比率。較大的NR值表示算法可以獲得更多最優(yōu)解，其計算公式為：

(12)

(2)GD。表示所測算法中非支配解集各點與參考解集的平均距離，其計算公式為：

(13)

式中：di表示Dj中第i個解到到D*中最近點的歐式距離，n表示Dj中解的個數(shù)。GD越小，算法性能越好。考慮到兩個目標量綱不同對指標產生的影響，對目標采用歸一化處理如式(14)所示：

(14)

(3)IGD。為綜合性測量指標，表示參考解集中各點到所測算法中非支配解集之間的平均距離，其計算公式為：

(15)

式中：xi表示D*中第i個解到到Dj中最近點的歐式距離，n*表示D*中解的個數(shù)。對所有目標值均采用歸一化處理。

對于各測試算例，將3種算法均獨立運行15次，所得各指標平均值如表6所示，3種算法所得最優(yōu)指標加粗顯示。

表6 3種算法4項指標對比

續(xù)表6

由表中測試結果可知，就N指標而言，SAMP-Jaya算法在5種算例中取得最優(yōu)值，說明該算法全局搜索能力更強，意味著更多種方案可供選擇；在NR、GD、IGD三種指標中，SAMP-Jaya算法均表現(xiàn)良好。就NR指標而言，SAMP-Jaya算法所有測試結果均等于或接近1，說明該算法在各算例中所得非支配解大多數(shù)優(yōu)于其他算法的非劣解；以GD、IGD指標而言，SAMP-Jaya算法在5種算例測試結果中均為最小值，說明該算法所得非支配解集更加接近問題真實Pareto前沿，相較于其他兩種算法收斂性能更佳。

以100×8的問題為例，如圖7所示為3種算法所得非支配解集，由圖可知，相較其他兩種算法，SAMP-Jaya算法所求非劣解集在分布面上更加廣泛，分布均勻性更優(yōu)；MO-Jaya算法獲得13個非支配解，SAMP-Jaya算法獲得15個非支配，且其極端解均優(yōu)于MO-Jaya算法，說明所設計自適應多種群策略有助于提升算法的全局搜索能力。

如圖8所示為某次運行時3種算法各目標值的收斂曲線。SAMP-Jaya算法、VNSGAⅢ算法、MO-Jaya算法分別在140代左右、145代左右、160代左右時達到最優(yōu)值；SAMP-Jaya算法的初始解為(2 098,180.25)優(yōu)于VNSGAⅢ算法、MO-Jaya算法的初始解(2 120,180.88)、(2 150,180.96)，說明所設計多規(guī)則初始化種群可以提升初始種群的質量。綜上所述，SAMP-Jaya算法兩個目標值收斂速度更快，收斂性更為優(yōu)異。根據(jù)圖7和圖8可知SAMP-Jaya算法的求解質量和收斂性能更好。

4 結束語

在如今提倡綠色制造的生產背景下，本文建立了以最大完工時間和能耗為雙目標的帶有設置時間的并行機調度模型。針對問題模型，運用一種二維實數(shù)編碼方案。為有效求解問題，在Jaya算法的基礎上設計以下3種策略形成SAMP-Jaya算法：①采用多規(guī)則初始化種群來提升初始種群質量；②提出多種群的策略提升算法的全局搜索性與局部開發(fā)性，自適應調整子種群數(shù)目提升算法收斂速度；③提出位置向量排序機制解決離散型變量更新問題。經過測試分析，從單目標而言，將SAMP-Jaya算法與HGA算法和HDTLBO算法比較，證明了SAMP-Jaya算法的優(yōu)越性；進而運用SAMP-Jaya算法求解GPMSP-ST，并與MO-Jaya、VNSGAⅢ對比，驗證了所設計策略有效地提升了算法求解質量和收斂速度。

未來將從以下幾個方面展開進一步研究：①針對如機器故障，訂單緊急插入等不確定性因素下對初始調度方案作出調整，形成動態(tài)調度；②本文所提種群初始化規(guī)則雖然改善了初始種群質量，但效果并不突出，未來可利用啟發(fā)式規(guī)則作進一步改善；③本文問題模型中的工件僅需加工一道工序，針對多工序并行機問題還需深入研究。