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

齊玉欣 付亞平 孫翠華

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

中圖分類號(hào)：F552.3

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

文章編號(hào)：1006-1037（2021）01-0082-05

基金項(xiàng)目：

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

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

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

1 問題描述與建模

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

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

其中，式（1）定義工件的實(shí)際加工時(shí)間;式（2）和（3）表示最小化期望最大完工時(shí)間和能源消耗;式（4）保證每臺(tái)機(jī)器上每個(gè)位置最多只能處理一個(gè)工件;式（5）保證每個(gè)工件只能在一臺(tái)機(jī)器的一個(gè)位置上處理;式（6）保證每個(gè)工件只能以一種速度處理;式（7）定義工件在相應(yīng)加工速度下加工時(shí)的單位時(shí)間能耗;式（8）保證每臺(tái)機(jī)器上后續(xù)工件的開始加工時(shí)間晚于前置工件的結(jié)束時(shí)間;式（9）保證每臺(tái)機(jī)器的結(jié)束時(shí)間不得大于最大完工時(shí)間;式（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)度問題中，需要同時(shí)考慮分配和排序兩種不同的決策。本文采用雙鏈表結(jié)構(gòu)進(jìn)行編碼[15]，個(gè)體用S=O，V來表示，其中O=o1，o2，…，oN表示工件的加工順序，V=v1，v2，…，vN表示工件加工速度的索引，vn，vn∈D，表示O中相應(yīng)工件的加工速度。

2.2 交叉與變異

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

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

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

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

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

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

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

參考文獻(xiàn)

[1]徐軍芹，姚居良.一類單階段混合制造系統(tǒng)的調(diào)度[J].青島大學(xué)學(xué)報(bào)（自然科學(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é)報(bào)（自然科學(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.