考慮能耗優(yōu)化和學(xué)習(xí)效應(yīng)的隨機(jī)多目標(biāo)并行機(jī)調(diào)度問題研究

齊玉欣 付亞平 孫翠華

摘要：針對具有學(xué)習(xí)效應(yīng)且處理時間不確定的并行機(jī)調(diào)度問題，以最小化最大完工時間和能源消耗為優(yōu)化目標(biāo)，建立了該問題的隨機(jī)多目標(biāo)調(diào)度模型;設(shè)計和改進(jìn)了非支配排序遺傳算法和基于分解的多目標(biāo)進(jìn)化算法進(jìn)行求解。通過采用覆蓋率指標(biāo)和逆世代距離指標(biāo)對實驗結(jié)果進(jìn)行評價，分析了兩種算法在求解該問題上的性能。研究結(jié)果表明，MOEA/D在C指標(biāo)方面優(yōu)于NSGA-II，而NSGA-II在IGD指標(biāo)方面優(yōu)于MOEA/D。

關(guān)鍵詞：并行機(jī)調(diào)度;學(xué)習(xí)效應(yīng);能源優(yōu)化;隨機(jī)優(yōu)化;多目標(biāo)優(yōu)化算法

中圖分類號：F552.3

文獻(xiàn)標(biāo)志碼：A

文章編號：1006-1037（2021）01-0082-05

基金項目：

國家自然科學(xué)基金青年科學(xué)基金（批準(zhǔn)號：61703220）資助;中國博士后科學(xué)基金特別資助項目（批準(zhǔn)號：2019T120569）資助;山東省高等學(xué)校優(yōu)秀青年創(chuàng)新團(tuán)隊項目（批準(zhǔn)號：2020RWG011）資助。

通信作者：付亞平，男，博士，教授，主要研究方向為復(fù)雜系統(tǒng)計劃與調(diào)度和進(jìn)化多目標(biāo)優(yōu)化。

調(diào)度問題是制造和服務(wù)運營管理中需要解決的重要問題[1]。并行機(jī)問題作為一類復(fù)雜的調(diào)度問題，近年來得到了廣泛的研究。傳統(tǒng)的并行機(jī)調(diào)度問題研究多集中于優(yōu)化單一目標(biāo)，如Chen[2]研究了以最小化最大完成時間為優(yōu)化目標(biāo)的并行機(jī)調(diào)度問題，Junior[3]研究了以最小化總延遲時間為優(yōu)化目標(biāo)的并行機(jī)調(diào)度問題。近年來，資源消耗和環(huán)境污染引起了學(xué)界和業(yè)界的普遍重視。現(xiàn)階段制造企業(yè)的生產(chǎn)過程不僅需要考慮時間因素，還需要關(guān)注能源消耗指標(biāo)，如李國臣等[4-5]研究了以最小化能源消耗為優(yōu)化目標(biāo)的并行機(jī)調(diào)度問題。上述研究均考慮加工時間確定的情況，實際生產(chǎn)過程中往往難以事先得到設(shè)備和工件的詳細(xì)信息，使得制造過程易出現(xiàn)諸多不確定情形，如Jia等[6-7]研究了具有模糊加工時間的并行機(jī)調(diào)度問題。現(xiàn)階段制造系統(tǒng)采用了一系列具有自學(xué)習(xí)、自組織和自優(yōu)化能力的智能設(shè)備，這些設(shè)備通過收集和利用實際生產(chǎn)中過程的實時信息提高自身處理效率，進(jìn)而使得工件的處理時間變短，即出現(xiàn)學(xué)習(xí)效應(yīng)。Yeh等[8]研究了具有學(xué)習(xí)效應(yīng)的并行機(jī)調(diào)度問題，并提出兩種啟發(fā)式算法進(jìn)行求解。Lin[9]研究了機(jī)器學(xué)習(xí)率確定情況下的具有學(xué)習(xí)效應(yīng)的多目標(biāo)并行機(jī)調(diào)度問題，并通過線性規(guī)劃模型進(jìn)行求解。現(xiàn)有對于具有學(xué)習(xí)效應(yīng)的并行機(jī)調(diào)度問題的研究，多集中于確定環(huán)境下的單目標(biāo)優(yōu)化，未考慮能耗優(yōu)化和加工過程的隨機(jī)特點。本文圍繞制造系統(tǒng)提高能源利用率的實際需求，考慮加工過程的隨機(jī)特點和學(xué)習(xí)效應(yīng)，研究一種考慮能耗優(yōu)化和學(xué)習(xí)效應(yīng)的隨機(jī)多目標(biāo)并行機(jī)調(diào)度問題。以最小化最大完工時間和能源消耗為優(yōu)化目標(biāo)，建立該問題的調(diào)度模型，同時設(shè)計非支配排序遺傳算法和基于分解的多目標(biāo)進(jìn)化算法進(jìn)行求解。

1 問題描述與建模

本文提出了一種具有學(xué)習(xí)效應(yīng)的隨機(jī)多目標(biāo)并行機(jī)調(diào)度模型，旨在提高服務(wù)水平的同時降低生產(chǎn)成本。該問題的優(yōu)化目標(biāo)為最小化最大完工時間和能源消耗。由于很難提前準(zhǔn)確地知道工件的加工時間和準(zhǔn)備時間，因此，加工過程中的加工時間和準(zhǔn)備時間都是隨機(jī)變量。為建立并行機(jī)調(diào)度模型，在表1中定義了相關(guān)符號。

一個可行的調(diào)度必須滿足如下條件：1）每個工件只能在一臺機(jī)器上處理;2）每臺機(jī)器只能處理一個工件;3）設(shè)備的運行過程不允許中斷。為刻畫學(xué)習(xí)效應(yīng)，工件的實際加工時間是其正常加工時間的函數(shù)。實際加工時間函數(shù)為

其中，式（1）定義工件的實際加工時間;式（2）和（3）表示最小化期望最大完工時間和能源消耗;式（4）保證每臺機(jī)器上每個位置最多只能處理一個工件;式（5）保證每個工件只能在一臺機(jī)器的一個位置上處理;式（6）保證每個工件只能以一種速度處理;式（7）定義工件在相應(yīng)加工速度下加工時的單位時間能耗;式（8）保證每臺機(jī)器上后續(xù)工件的開始加工時間晚于前置工件的結(jié)束時間;式（9）保證每臺機(jī)器的結(jié)束時間不得大于最大完工時間;式（10）表示決策變量的取值范圍。

2 算法

進(jìn)化算法已被廣泛應(yīng)用于求解多目標(biāo)優(yōu)化問題[10]，被認(rèn)為是求解多目標(biāo)優(yōu)化問題最有效的算法之一。近年來，學(xué)者提出了許多進(jìn)化算法框架，非支配排序遺傳算法（Non-dominated Sorting Genetic Algorithm II， NSGA-II）[11]和基于分解的多目標(biāo)進(jìn)化算法（Multi-Objective Evolutionary Algorithm based on Decomposition， MOEA/D）[12]被認(rèn)為是兩種經(jīng)典的多目標(biāo)優(yōu)化算法，且已成功地解決了旅行商[13]和流水車間調(diào)度[14]等問題。因此，本文采用NSGA-II和MOEA/D解決所提出的考慮能耗優(yōu)化和具有學(xué)習(xí)效應(yīng)的隨機(jī)多目標(biāo)并行機(jī)調(diào)度問題。

2.1 編碼與解碼

在并行機(jī)調(diào)度問題中，需要同時考慮分配和排序兩種不同的決策。本文采用雙鏈表結(jié)構(gòu)進(jìn)行編碼[15]，個體用S=O，V來表示，其中O=o1，o2，…，oN表示工件的加工順序，V=v1，v2，…，vN表示工件加工速度的索引，vn，vn∈D，表示O中相應(yīng)工件的加工速度。

2.2 交叉與變異

隨機(jī)選擇當(dāng)前種群中的兩個個體進(jìn)行交叉。對于兩個父代S1=O1，V1和S2=O2，V2的O1和O2部分采用兩點交叉的方法進(jìn)行交叉，而對于V1和V2部分采用二進(jìn)制編碼中均勻交叉的方法進(jìn)行交叉，從而得到新的子代。每一個經(jīng)過交叉產(chǎn)生的子代個體根據(jù)變異率進(jìn)行變異操作，對父代個體S1和S2中的O1、O2與V1、V2兩部分采用不同的變異方法，對于兩個個體的O1和O2部分采用兩點交叉的方法進(jìn)行變異，而對于V1和V2部分采用單點變異的方法進(jìn)行變異。

3 實驗結(jié)果分析

NSGA-II的參數(shù)如下：種群規(guī)模為100，變異概率為0.3。MOEA/D的參數(shù)設(shè)置如下：種群規(guī)模為100，變異概率為1.0。為了對兩種算法進(jìn)行公平比較，將適應(yīng)度評估的次數(shù)設(shè)置為停止準(zhǔn)則，并將100mn作為兩種算法的最大適應(yīng)度評估次數(shù)，其中m和n分別表示機(jī)器和工件的數(shù)量。本文選用逆世代距離指標(biāo)[16]（Inverted Generational Distance metric， IGD-metric）和覆蓋率指標(biāo)[17]（Set Coverage metric， C-metric）對NSGA-II和MOEA/D的結(jié)果進(jìn)行比較。IGD指標(biāo)主要通過計算實際Pareto前沿上每個點（個體）之間的最小距離與算法得到的個體集的平均值來評價算法的綜合性能。IGD值越小，算法的收斂性和分布性越好。C指標(biāo)是兩個相互支配的解集的百分比，可以判斷解集的質(zhì)量。C值越大，算法性能越好。

為了驗證兩種算法的有效性和可行性，該實驗隨機(jī)產(chǎn)生了20個測試算例，其中m∈2， 4， 6，8和n∈20， 40， 60， 80， 100組合的測試問題。測試時，工件的正常加工時間作為其平均加工時間，工件加工時間的標(biāo)準(zhǔn)差設(shè)置為平均加工時間和系數(shù)θ的乘積，其中，θ=0.001。對于每個測試問題，機(jī)器的可選速度的集合為vil=1.00， 1.30， 1.55， 1.80， 2.00。在vil中隨機(jī)選擇生成工件在機(jī)器上的加工速度，在區(qū)間1，10和1，100上隨機(jī)生成每臺機(jī)器上工件的準(zhǔn)備時間和處理時間，在區(qū)間0， 0.1上隨機(jī)生成設(shè)備的學(xué)習(xí)系數(shù)，設(shè)置設(shè)備在準(zhǔn)備階段的單位時間能耗為1.0。采用NSGA-II和MOEA/D對測試問題分別求解20次，并分別采用C指標(biāo)與IGD指標(biāo)對實驗結(jié)果進(jìn)行分析，見表1和表2。其中，表1中的符號“X”和“Y”分別表示NSGA-II和MOEA/D所獲得的解集。

從表2可知，MOEA/D在11個實例中獲得的非支配解集均能支配NSGA-II，通過比較方差看出，MOEA/D在10個實例中優(yōu)于NSGA-II，可知MOEA/D具有較好的穩(wěn)定性，由此可以看出MOEA/D在C指標(biāo)方面的最終結(jié)果優(yōu)于NSGA-II。

NSGA-II得到的12個實例的求解結(jié)果優(yōu)于NSGA-II，通過比較方差看出，NSGA-II在15個實例中優(yōu)于MOEA/D，可知NSGA-II具有較好的穩(wěn)定性，由此可以看出NSGA-II在IGD指標(biāo)方面的結(jié)果優(yōu)于MOEA/D。

從以上實驗結(jié)果的對比分析中可以看出，MOEA/D在C指標(biāo)方面優(yōu)于NSGA-II，而NSGA-II在IGD指標(biāo)方面優(yōu)于MOEA/D。

4 結(jié)論

本文提出了考慮能耗優(yōu)化和學(xué)習(xí)效應(yīng)的隨機(jī)多目標(biāo)并行機(jī)調(diào)度問題，以最小化最大完工時間和能源消耗為優(yōu)化目標(biāo)，建立了該問題的調(diào)度模型。結(jié)合問題特點，采用了非支配排序遺傳算法和基于分解的多目標(biāo)進(jìn)化算法進(jìn)行求解。通過采用C指標(biāo)和IGD指標(biāo)對結(jié)果進(jìn)行分析，MOEA/D在C指標(biāo)方面優(yōu)于NSGA-II，而NSGA-II在IGD指標(biāo)方面優(yōu)于MOEA/D。本文研究工作在實際調(diào)度問題中可以協(xié)助決策者對具有多目標(biāo)優(yōu)化、學(xué)習(xí)效應(yīng)、隨機(jī)特點的并行機(jī)調(diào)度問題做出有效的決策。根據(jù)以上所研究的問題，在未來的工作中對隨機(jī)環(huán)境下的并行機(jī)調(diào)度問題進(jìn)行探索。

參考文獻(xiàn)

[1]徐軍芹，姚居良.一類單階段混合制造系統(tǒng)的調(diào)度[J].青島大學(xué)學(xué)報（自然科學(xué)版），2003， 14（4）：80-84.

[2]CHEN J F. Unrelated parallel-machine scheduling to minimize total weighted completion time[J]. Journal of Intelligent Manufacturing， 2015， 26（6）：1099-1112.

[3]JUNIOR P L D O， ARROYO J E C， SANTOS A G D， et al. An evolutionary algorithm with path-relinking for the parallel machine with job splitting[C]// IEEE International Conference on Systems， Man and Cybernetics. Seoul， 2012：3153-3158.

[4]李國臣，喬非，王俊凱，等.考慮能耗約束的并行機(jī)組批調(diào)度[J].中南大學(xué)學(xué)報（自然科學(xué)版），2017， 48（8）：2063-2072.

[5]ZHANG L K， DENG Q W， GONG G L， et al. A new unrelated parallel machine scheduling problem with tool changes to minimise the total energy consumption[J]. International Journal of Production Research， 2019，58（1）：1-20.

[6]JIA Z H， YAN J H， LEUNG J Y T， et al. Ant colony optimization algorithm for scheduling jobs with fuzzy processing time on parallel batch machines with different capacities[J]. Applied Soft Computing， 2019，75：548-561.

[7]LI K， CHEN J F， FU H， et al. Uniform parallel machine scheduling with fuzzy processing times under resource consumption constraint[J]. Applied Soft Computing， 2019， 82：105585.

[8]YEH W C， LAI P J， LEE W C， et al. Parallel-machine scheduling to minimize makespan with fuzzy processing times and learning effect[J]. Information Sciences， 2014，269（4）：142-158.

[9]LIN Y K. Scheduling identical jobs on uniform parallel machines under position-based learning effects[J]. Arabian Journal for Science and Engineering， 2014， 39（8）：6567-6574.

[10] DING J L， YANG C E， JIN Y C， et al. Generalized multitasking for evolutionary optimization of expensive problems[J]. IEEE Transactions on Evolutionary Computation， 2019， 23（1）：44-58.

[11] DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-II[J]. IEEE Transactions on Evolutionary Computation， 2002， 6（2）：182-197.

[12] ZHANG Q F， Li H. MOEA/D： A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation， 2007， 11（6）：712-731.

[13] 陳彧，韓超.一種求解旅行商問題的進(jìn)化多目標(biāo)優(yōu)化方法[J].控制與決策，2019， 34（4）：106-111.

[14] HAN Z H， WANG S Y， DONG X T， et al. Improved NSGA-II algorithm for multi-objective scheduling problem in hybrid flow shop[C]// International conference on modelling， identification and control.Kunming， 2017， 273-289.

[15] GUO X W， LIU S X， ZHOU M C， et al. Dual-Objective program and scatter search for the optimization of disassembly sequences subject to multi resource constraints[J]. IEEE Transactions on Automation Science and Engineering， 2018， 15（3）：1091-1103.

[16] PARDALOS P M， STEPONAVICE I， ZILINSKAS A. Pareto set approximation by the method of adjustable weights and successive lexicographic goal programming[J]. Optimization Letters， 2012， 6（4）：665-678.

[17] WANG H F， FU Y P， HUANG M， et al. A NSGA-II based memetic algorithm for multiobjective parallel flowshop scheduling problem[J]. Computers & Industrial Engineering， 2017， 113：185-194.