融合局部搜索與Pareto支配的多目標任務調度模型

摘 要：為了解決復雜任務群調度過程中資源利用不均、任務完成時間較長等問題，以最小化資源負載均方差和最小化任務群完成時間為目標構建復雜任務群資源調度模型，提出一種融合局部搜索和Pareto支配的多目標優化算法BRLSN（multi-objective optimization based on boundary range local search and NSGA-Ⅱ，BRLSN）。該算法采用有效的編碼方式與交叉變異算子進行迭代尋優，并利用基于邊界區域局部搜索的精英保留策略擴大算法搜索范圍，保存種群優良個體。實驗結果表明，BRLSN相較于其他多目標算法在收斂性和多樣性上有顯著的提升，同時算法收斂速度更快，種群質量更高，明顯優化了最終目標函數的結果值。

關鍵詞：多目標優化； 局部搜索； 智能算法； 任務調度； Pareto支配

中圖分類號：TP301 文獻標志碼：A

文章編號：1001-3695（2023）08-009-2298-06

doi：10.19734/j.issn.1001-3695.2022.12.0812

Multi-objective task scheduling model incorporating

local search and Pareto domination

Han Diya Zhang Fengli Yin Jiaqi Wang Ruijin Han Yingjun

（1.School of Information amp; Software Engineering， University of Electronic Science amp; Technology of China， Chengdu 610054， China; 2.Sichuan Environmental Information Center， Chengdu 610041， China）

Abstract：In order to solve the problems of uneven resource utilization and long task completion time in complex task group scheduling， this paper constructed a complex task group resource scheduling model to minimize the mean square error of resource load and the task group completion time， and proposed a multi-objective optimization algorithm based on boundary range local search and NSGA-Ⅱ， called BRLSN. The algorithm used an effective coding method and cross mutation operator for iterative optimization， and constructed an elite retention strategy based on local search in boundary region to expand the search scope of the algorithm and preserved good individuals in the population. Experimental results show that compared with other multi-objective algorithms， the convergence and diversity of BRLSN are significantly improved. At the same time， the algorithm convergence speed is faster， the population quality is higher， and the result value of the final objective function is obviously optimized.

Key words：multi-target optimization; local search; intelligent algorithms; task scheduling; Pareto dominance

0 引言

工業4.0時代的到來，加快了產業智能化的推進，生產過程中出現的各類任務與所需資源的調度問題也愈發復雜。工業生產場景下遇到的大型任務如車間生產、故障聯合處置等，需要調用多方資源協作完成，資源根據不同任務的需求可分為設備資源、運輸資源和人員資源等，本文將此類問題抽象為一個復雜任務群調度問題，將一段時間內產生的多個任務定義為一個任務群，每個任務根據復雜程度又可進一步細分為多個具有關聯關系的原子任務，原子任務是任務執行與持有資源的最小單元。針對工業場景下復雜任務群的調度就是要在考慮完成時間、資源利用率等因素的情況下為所有原子任務合理分配資源。

國內外針對復雜場景下多任務調度問題的研究已經取得了一定的成果，但多數都是針對單一目標進行的。文獻［1～6］利用混合進化算法以最小化任務完成時間為目標構建了生產資源配置模型；文獻［7，8］以最小化事件延期成本為目標提出了結合遺傳算法與自適應策略的調度模型；文獻［9，10］將粒子群算法進行離散化處理，并且驗證了在生成高質量資源—任務配置方案方面的有效性；文獻［11～13］考慮到了任務優先級差異，提出了混合精確算法與遺傳算法的任務調度框架；文獻［14，15］從安全性的角度出發，提出了任務調度隱私保護策略。

以上研究均從單一維度出發對問題進行建模，缺少了對實際應用的綜合考慮，應當從多目標出發，構建符合實際場景的多目標優化模型。在求解多目標問題上，主要有基于加權聚合和基于Pareto排序兩種方式。基于加權聚合的多目標優化策略通過降維的方式把問題簡單化，偏離了多目標優化研究的本質，同時權值的選擇有較強的主觀性。因此，多目標優化問題的研究更傾向于使用另一種基于Pareto前沿的多目標優化策略，該策略通過對個體的多個目標函數值進行非支配排序，從而選擇出一組最優的解集。基于Pareto的NSGA-Ⅱ［16］多目標算法利用快速非支配排序對種群進行分層，并結合擁擠度比較算子保留將優良個體保留下來，從而找到一組非支配解集。文獻［17］采用基于過程的隨機變異策略和交叉方法生成新一代種群，并改進了精英保留策略。針對工業車間調度問題，文獻［18］在原有多目標算法的基礎上提出了一種智能決策優化算法。文獻［19］引入了Pareto部分優勢的概念，使NSGA-Ⅱ在多維解空間中進行有效搜索，但是仍然存在算法易早熟、收斂速度較慢等問題。文獻［20］采用多區域采樣重組策略，有針對性地調整粒子在多個方向上的收斂能力。文獻［21，22］的研究表明，利用局部搜索可以有效提升多目標優化問題解的質量，但會產生大量局部解，導致計算量成倍增加。

從以上分析可知，目前針對工業場景下復雜任務群資源調度問題的研究多集中于將問題建模為一個單目標優化問題，然而實際應用場景中資源分配方案需要考慮多方面因素，如任務群完成時間、資源負載情況等。同時，傳統多目標算法尋優能力不足、易進入局部最優的缺陷，亦是需要解決的問題，局部搜索策略為問題的求解提供了思路，但需要解決計算量過大的問題。

本文首先以最小化任務群完成時間和最小化資源負載均方差為目標，構建了雙目標復雜任務群資源調度模型；其次針對問題模型的求解提出了一種融合邊界范圍局部搜索和Pareto支配的多目標優化算法（multi-objective optimization based on boundary range local search and NSGA-Ⅱ，BRLSN），算法利用混沌變量擴大解的搜索范圍，即有更大的概率發現更為優質的任務群調度方案，彌補了算法陷入局部最優的缺陷，同時加快了算法的收斂速度，能夠在更短的時間內找到更為優質的解；最后通過仿真實驗對算法性能進行測試，結果表明與現有算法相比，本文提出的BRLSN算法在收斂性和多樣性上相較于標準NSGA-Ⅱ算法分別平均提升了35%～70%和29%～56%，并且生成的資源調配方案在兩個目標值上的結果均優于其他具有代表性的多目標算法。

1 問題模型

1.1 問題描述

1.2 符號定義

1.3 問題假設

1.4 模型約束

1.5 優化目標

2 BRLSN多目標優化算法

2.1 算法概述

前一章已對本文需要解決的復雜任務群調度問題進行了建模，本章將介紹對該問題模型進行求解的算法。

此類任務群調度問題是NP-hard問題，以遺傳算法為代表的元啟發式算法是解決此類問題的重要方法，所以本文所提出的BRLSN沿用了進化算法的框架，如圖1所示，BRLSN算法具體由染色體編碼、交叉變異、精英選擇三大模塊組成。

首先通過染色體編碼將任務—資源的匹配方式以染色體的形式表示，每一條染色體代表一種任務群調度方案，染色體的編碼需要考慮1.3、1.4節中的假設和約束；其次通過交叉變異擴大種群的多樣性，即豐富調度方案的多樣性；最后以1.5節提出的優化目標為評價指標，利用精英選擇策略保留優良個體，對染色體優中選優，直到達到進化結束條件并生成最優解集，在最優解集中任一染色體均可作為最優個體，通過解碼獲得最優調度方案。各模塊具體描述將在后續章節進行詳細介紹。

2.2 染色體編碼

2.3 交叉變異

因為隨機性的交叉與變異方式會導致大量非可行解的產生，所以本文設計了兩種交叉變異算子來解決此問題。

2.3.1 交叉算子

2.3.2 變異算子

2.4 基于邊界區域局部搜索的精英保留策略

因為研究［19～22］表明局部搜索和多區域采樣能有效提高解的質量，但是盲目的擴張搜索范圍在增加發現優質解可能的同時會導致計算量過大從而使得收斂速度較慢，本文提出了一種基于邊界搜索的精英保留策略（elite retention strategy based on boundary search，BS-ERS），引導算法有目的地對種群周邊區域進行探索，發現優質解的同時提高尋優速度，同時結合精英保留策略最大程度保留優質解作為下一代進化的親本，促進種群整體向評價指標更優的方向迭代發展。BS-ERS主要包含快速非支配排序、邊界區域局部搜索和精英保留三個部分，下面將對其進行詳細說明。

2.4.1 快速非支配排序

2.4.2 邊界區域局部搜索

2.4.3 精英保留

規模為M的父種群Pt和子種群P1、P2經過合并與邊界區域局部搜索后，形成規模為2M+k的新種群R，其中k為通過搜索發現的新個體數。經過種群分層與個體擁擠度計算，每個染色體都具有兩個屬性，分別是非支配等級irank和擁擠度id，為了構成規模為M的新一代父種群Pt+1，優先選擇非支配等級數小的個體。直到添加到rank（x），此時種群規模超過M，對rank（x）中的所有染色體進行擁擠度排序，選擇擁擠度更大者，直到生成規模為M的新種群Pt+1。

2.5 BRLSN算法流程

3 實驗設計與結果分析

3.1 實驗環境

本章實驗均使用Python編程實現，運行環境為macOS Big Sur（1.4 GHz四核Intel Core i5，8 GB內存）。

為驗證本文所提出的多目標優化算法BRLSN的性能以及在解決復雜任務群調度問題上有效性設計了兩個對比實驗。用于對比的算法有標準NSGA-Ⅱ［16］、基于多鄰域局部搜索的MOEA-LS［23］和基于精英分布局部搜索的DEGA［24］。其中實驗1為算法性能測試，該實驗使用4個雙目標優化問題常用的測試函數，通過相應的評價指標量化對比算法計算得出的Pareto前沿與函數本身真實Pareto前沿的擬合程度，從而對算法的性能進行評估；實驗2為BRLSN在解決實際復雜任務群調度問題中的有效性測試，以資源負載均方差和任務群完成時間這兩個目標作為評價指標，對比各算法在相同進化代數下的表現。

3.2 實驗1設計與結果分析

因為無法確切地知道自定義的多目標優化問題真實Pareto前沿所在的位置，所以本實驗使用雙目標優化問題常用的ZDT系列測試函數［25］對算法的尋優性能進行測試，ZDT系列函數有真實的Pareto前沿，且均為多變量的無約束優化問題，能夠很好地測試優化算法的性能，函數具體內容如表2所示。

根據表3的實驗對比結果，BRLSN所求得Pareto解集的收斂性在ZDT1～ZDT4上均優于同組對比算法，說明BRLSN算法所求得的Pareto最優解集更接近于真實Pareto最優解集。以標準NSGA-Ⅱ算法收斂性均值和標準差為基準，BRLSN在ZDT1上的平均優化比例分別為70.6%和12.5%；在ZDT2上的平均優化比例分別為49.2%和42.8%；在ZDT3上的平均優化比例分別為35.25%和71.3%；在ZDT4上的平均優化比例分別為55.8%和72.6%。

根據表4的實驗對比結果，BRLSN所求得Pareto解集的多樣性在ZDT1～ZDT4上均優于同組對比算法，說明通過BRLSN算法得到的Pareto解在前沿上分布得更均勻，種類更豐富。以標準NSGA-Ⅱ算法多樣性的均值和標準差為基準，BRLSN在ZDT1上的平均優化比例分別為56.2%和48.5%；在ZDT2上的平均優化比例分別為31.9%和83.1%；在ZDT3上的平均優化比例分別為42.2%和89.2%；在ZDT4上的平均優化比例分別為29.6%和40%。

綜上，本文所提出的融合邊界范圍局部搜索的多目標優化算法BRLSN較標準NSGA-Ⅱ在綜合性能方面有明顯的提升，在保證收斂性的同時增強了種群多樣性，同時，結合基于多鄰域局部搜索的MOEA-LS和基于精英分布局部搜索的DEGA的實驗結果，驗證了引入局部搜索對算法尋優能力的積極影響。

3.3 實驗2設計與結果分析

為了驗證本文所提的BRLSN算法在實際場景中復雜任務群調度方面的有效性，本節結合真實案例數據，整理形成了符合實驗要求的三種規模的仿真算例，詳細信息如表5所示。

四種算法的初始種群規模均設置為100，交叉概率P_c為0.9，變異概率P_m為0.1，交叉部分均采用混合交叉方法，在變異部分，BRLSN采用本文提出的多點變異策略MMS，NSGA-Ⅱ、DEGA和MOEA-LS采用隨機變異策略，每組實驗都進行200次進化迭代，實驗目的在于對比進化代數相同時，不同算法所得出的平均任務群完成時間和平均資源負載均方差的差別。

BRLSN與三種對比算法的目標值隨進化代數的變化情況如圖6～8所示，結果表明：a）由于算例規模的不同，算法達到收斂時所需代數也有所差異，但BRLSN算法始終能夠在80代以內實現收斂，而標準NSGA-Ⅱ［16］、DEGA［24］、MOEA-LS［23］達到收斂時的代數始終大于BRLSN；b）從算法最終收斂到的目標值結果來看，BRLSN的求解較標準NSGA-Ⅱ有顯著的提升，同時明顯優于DEGA和MOEA-LS。

BRLSN最終生成的種群分布與標準NSGA-Ⅱ的對比情況如圖9所示，其中“×”點構成Pareto最優解集，BRLSN算法所找出的Pareto解集中的解在每個優化目標上均優于原始NSGA-Ⅱ最終解集中的解，即選擇BRLSN算法的Pareto解集中的任意解，都能夠得到資源負載均方差更小、任務群完成時間更短的調度方案。

因為本文的兩個優化目標都是向最小化的方向尋優，而相較于標準NSGA-Ⅱ，改進后的BRLSN算法的種群整體分布明顯更靠近于坐標系的左下方，所以結果顯示BRLSN算法最終生成的種群整體上更為優質。

4 結束語

本文首先以最小化任務群完成時間和最小化資源負載均方差為目標構建了復雜任務群資源調度模型；其次針對復雜任務群資源調度模型的求解，提出了一種融合邊界區域局部搜索策略的多目標優化算法BRLSN，利用混沌變量擴大了算法的搜索范圍；最后，通過仿真實驗與現有標準NSGA-Ⅱ、DEGA和MOEA-LS進行對比，結果表明BRLSN的解有更好的收斂性與多樣性，同時有效提高了收斂速度，所生成的方案在目標值上的表現更優質。目前的研究是針對雙目標優化問題展開的，后續工作將嘗試把本文的思想融入當目標維數大于3時的高維多目標優化問題，以解決更復雜場景下的應用問題。

參考文獻：

[1]Priyan M， Gokulnath C， Anandamurugan S， et al. Multi-criteria-based approach for job scheduling in industry 4.0 in smart cities using fuzzy logic［J］.Soft Computing，2021，25：12059-12074.

［2]Sooncharoen S， Pongcharoen P， Hicks C. Grey wolf production scheduling for the capital goods industry［J］.Applied Soft Computing，2020，94：106480.

［3]Ghaleb M， Zolfagharinia H， Taghipour S. Real-time production scheduling in the Industry-4.0 context： addressing uncertainties in job arrivals and machine breakdowns［J］.Computers amp; Operations Research，2020，123：105031.

［4]張懷強，盧遠超，王孟.混合遺傳算法的戰時艦艇伴隨保障人員優化配置［J］.火力與指揮控制，2019，44（4）：37-43.（Zhang Huai-qiang， Lu Yuanchao， Wang Meng. Optimal allocation of crew support in wartime ships based on hybrid genetic algorithm［J］.Fire Control amp; Command Control，2019，44（4）：37-43.）

［5]張莉莉，楊文文，羅冠聰.面向時間優化的“任務—人員”匹配逆最優值方法：以石化設備搶修為例［J/OL］.中國管理科學.http：//www.zgglkx.com/CN/abstract/abstract17506.shtml.（Zhang Lili， Yang Wenwen， Luo Guancong. Inverse optimal value method of “task-personnel” matching with time inferring： taking petrochemical equipment emergencyrepair as an example［J/OL］.Chinese Journal of Management Science.http：//www.zgglkx.com/CN/abstract/abstract17506.shtml.）

［6]Adamuthe A C，Mane S U， Thampi G T. Genetic algorithmic approach for security personnel scheduling［C］//Proc of International Confe-rence on Communication，Information Computing Technology.2012：1-6.

［7]Van Eeckhout D， Maenhout B， Vanhoucke M， et al. A heuristic procedure to solve the project staffing problem with discrete time/resource trade-offs and personnel scheduling constraints［J］.Compu-ters amp; Operations Research，2019，101：144-161.

［8]陳芮瑩，王承濤，劉振元.考慮服務水平的IT運維人員調度的智能遺傳算法［J］.系統仿真學報，2021，33（3）：732-744.（Chen Rui-ying， Wang Chengtao， Liu Zhenyuan. Intelligent genetic algorithm for workforce scheduling considering service level in IT maintenance ser-vice［J］.Journal of System Simulation，2021，33（3）：732-744.）

［9]Hu Xiaona， Ji Shan， Hua Hao. An improved genetic algorithm for berth scheduling at bulk terminal［J］.Computer Systems Science and Engineering，2022，43（3）：1285-1296.

［10]Zheng Anzhu， Yuan Dongfeng， Liang Daojun， et al. Personnel scheduling of machine tool assembly workshop based on hybrid discrete particle swarm optimization algorithm［C］//Proc of IEEE International Conference on Sensing， Diagnostics， Prognostics， and Control.Piscataway，NJ：IEEE Press，2021：137-142.

［11]Matthew S， Tao Xiaohui， Soman E， et al. A novel genetic algorithm based system for the scheduling of medical treatments［J］.Expert Systems with Applications，2022，195：116464.

［12]Asadujjaman M， Humyun F， Ripon K， et al. An immune genetic algorithm for solving NPV-based resource constrained project scheduling problem［J］.IEEE Access，2021，9：26177-26195.

［13]Reshma C， Pieter S， Tony W. An automatic constructive matheuristic for the shift minimization personnel task scheduling problem［J］.Journal of Heuristics，2021，27：205-227.

［14]Wang Ruijin， Pei Xikai， Zhu Juyi， et al. Multivariable time series forecasting using model fusion［J］.Information Sciences，2022，585：262-274.

［15]Wang Ruijin， Lai Jinshan， Zhang Zhiyang， et al. Privacy-preserving federated learning for Internet of medical things under edge computing［J］.IEEE Journal of Biomedical and Health Informatics，2023，27（2）：854-865.

［16]Kalyanmoy D， Samir A， Amrit P， Meyarivan T. A fast and elitist multiobjective genetic algorithm： NSGA-Ⅱ［J］.IEEE Trans on Evo-lutionary Computation，2002，6（2）：182-197.

［17]Yuan Minghai， Li Yadong， Zhang Lizhi， et al. Research on intel-ligent workshop resource scheduling method based on improved NSGA-Ⅱ algorithm［J］.Robotics and Computer-Integrated Manu-facturing，2021，71：102141.

［18]Sang Yangwei， Tan Jianpin， Liu Wen. Research on many-objective flexible Job-Shop intelligent scheduling problem based on improved NSGA-Ⅲ［J］.IEEE Access，2020，8：157676-157690.

［19]Makoto O. Effectiveness of NSGA-Ⅱ with linearly scheduled pareto-partial dominance for practical many-objecitve nurse scheduling［C］//Proc of the 7th International Conference on Control， Decision and Information Technologies.2020：581-586.

［20]張聞強，邢征，楊衛東.基于多區域采樣策略的混合粒子群優化求解多目標柔性作業車間調度問題［J］.計算機應用，2021，41（8）：2249-2257.（Zhang Wenqiang， Xing Zheng， Yang Weidong. Hybrid particle swarm optimization with multi-region sampling strategy to solve multi-objective flexible Job-Shop scheduling problem［J］.Journal of Computer Applications，2021，41（8）：2249-2257.）

［21]Xu Jianyou， Wu C C， Yin Yunqiang， et al. An iterated local search for the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times［J］.Applied Soft Computing，2017，52：39-4.

［22]Krzysztof M. A heuristic local search for the multiobjective firefighter problem［J］.Applied Soft Computing，2017，59：389-404.

［23]Shao Weishi， Shao Zhongshi， Pi Dechang. Multi-objective evolutio-nary algorithm based on multiple neighborhoods local search for multi-objective distributed hybrid flow shop scheduling problem［J］.Expert Systems with Applications，2021，183：115453.

［24]Bobby K， Wen Song， Wei Weng， et al. Distributed-elite local search based on a genetic algorithm for bi-objective Job-Shop scheduling under time-of-use tariffs［J］.Evolutionary Intelligence，2021，14（4）：1581-1595.

［25]Eckart Z， Kalyanmoy D， Lothar T. Comparison of multiobjective evolutionary algorithms：empirical results［J］.Evolutionary Computation，2000，8（2）：173-195.