求解高维多目标调度的新型人工蜂群算法

doi:10.11896/jsjkx.190600089

摘要/Abstract

摘要： 高维多目标连续优化问题已得到广泛研究,而高维多目标组合优化问题的进展相对较小,虽然人工蜂群(Artificial Bee Colony,ABC)算法已成功应用于多种生产调度问题,但很少被用来求解高维多目标调度问题,而且高维多目标调度自身的研究进展也非常小。针对高维多目标柔性作业车间调度问题,文中提出了一种新型ABC算法以同时优化最大完成时间、总延迟时间、总能耗和机器总负荷。与常规柔性作业车间调度问题不同,上述问题考虑了总能耗,使其成为绿色调度问题。新型ABC具有明显不同于现有ABC算法的新特点,其跟随蜂(onlooker bee)的数量小于引领蜂(employed bee),引领蜂侧重于全局搜索,而跟随蜂只进行局部搜索,通过两类蜜蜂彼此各异的搜索方式来避免算法陷入局部最优。同时,该算法将跟随对象限定为质量较好的部分引领蜂和外部档案成员,其他引领蜂无法成为跟随对象,以避免计算资源浪费在较差解的搜索上,并给出了侦查蜂(scout)新的处理策略。测试实例的仿真实验表明,高维多目标调度问题中非劣解数量占种群规模的比例明显低于高维连续优化问题。将新型ABC与多目标遗传算法和变邻域搜索进行比较,实验结果表明,新型ABC在求解高维多目标调度方面比对比算法更有优势,计算结果更好。

关键词: 调度问题, 多目标优化, 局部最优, 人工蜂群算法, 外部档案

Abstract: Many-objective continuous optimization problem has been considered extensively while there are few studies on many-objective combination optimization problem.Artificial bee colony(ABC) algorithm has been successfully applied to solve various production scheduling problem,but ABC is seldom used to solve many-objective scheduling problem and many-objective scheduling problem itself is also seldom handled.Aiming at multi-objective flexible job shop scheduling problem,a new ABC algorithm is proposed to optimize simultaneously maximum completion time,total tardiness,total energy consumption and total workload.Unlike the general flexible job shop scheduling problem,the above problem is green scheduling one because of the inclusion of total energy consumption.The new ABC has new characteristics which are obviously different from the existing ABC algorithm.Its number of onlooker bees is less that of employed bees,employed bee focuses on global search while onlooker bee only carries out local search,which avoids the algorithm from falling into local optimization through the different search methods of two kinds of bees.At the same time,onlooker bee just selects some best employed bees or members of external file,and some employed bees cannot become follower objects to avoid wasting computing resources on search for poor solutions.A new strategy is adopted to handle scout.The simulation results show that the ratio of the number of non-dominated solutions to population scale for many-objective scheduling problem is notably less than the same ratio for many-objective continuous optimization problem.Compared with multi-objective genetic algorithm and variable neighborhood search,the computational results show that ABC has better results than two comparative algorithms on solving the considered many-objective scheduling.

Key words: Artificial bee colony, External archive, Local optima, Multi-objective optimization, Scheduling problem

中图分类号:

TP301.6

郑友莲, 雷德明, 郑巧仙. 求解高维多目标调度的新型人工蜂群算法[J]. 计算机科学, 2020, 47(7): 186-191. https://doi.org/10.11896/jsjkx.190600089

ZHENG You-lian, LEI De-ming, ZHENG Qiao-xian. Novel Artificial Bee Colony Algorithm for Solving Many-objective Scheduling[J]. Computer Science, 2020, 47(7): 186-191. https://doi.org/10.11896/jsjkx.190600089

参考文献

[1]KARABOGA D,AKAY B.A comparative study of artificial bee colony algorithms[J].Applied Mathematics and Computation,2009,214(1):108-132.
[2]ZHAO X Q,DUAN S Y,MA X M.A multi-objective artificial bee colony based on limit search strategy[J].Control and Decision,2020,35(8):1793-1802.
[3]XIANG Y,ZHOU Y R,LIU H L.An elitism based multi-objective artificial bee colony algorithm[J].European Journal of Ope-rational Research,2015,245(1):168-193.
[4]SAAD A,KHAN S A,MAHMOOD A.A multi-objective evolutionary artificial bee colony algorithm for optimizing network topology design[J].Swarm and Evolutionary Computation,2018,38:187-201.
[5]LIANG R H,WU C Y,CHEN Y T,et al.Multi-objective dynamic optimal power flow using improved artificial bee colony algorithm based on Pareto optimization[J].International Tran-sactions on Electrical Energy Systems,2016,26(4):692-712.
[6]LI J Q,PAN Q K,GAO K Z.Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problem[J].International Journal of Advanced Manufacturing Technology,2011,55(9-12):1159-1169.
[7]PAN Q K,FAITH T M,SUGANTHAN P N,et al.A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem[J].Information Science,2011,181:2455-2468.
[8]ZHANG R,SONG S J,WU C.A hybrid artificial bee colony algorithm for the job shop scheduling problem[J].International Journal of Production Economics,2013,141(1):167-178.
[9]LEI D M,GUO X P.Scheduling job shop with lot streaming and transportation through a modified artificial bee colony[J].International Journal of Production Research,2013,51(16):4930-4941.
[10]HAN Y Y,GONG D W,SUN X Y.A discrete artificial bee colony algorithm incorporating differential evolution for the flow-shop scheduling problem with blocking[J].Engineering Optimization,2015,47(7):927-946.
[11]ASADZADEH L.A parallel artificial bee colony algorithm forthe job shop scheduling problem with a dynamic migration stra-tegy[J].Computers and Industrial Engineering,2016,102,359-367.
[12]SUNDAR S,SUGANTHAN P N,JIN C T,et al.A hybrid artificial bee colony algorithm for the job-shop scheduling problem with no-wait constraint[J].Soft Computing,2017,21(5):1193-1202.
[13]GONG D W,HAN Y Y,SUN J Y.A novel hybrid multi-objective artificial bee colony algorithm for blocking lot-straming flow shop scheduling problems[J].Knowledge-based Systems,2018,148:115-130.
[14]WU R,GUO S S,LI Y B,et al.An improved artificial bee colony algorithm for distributed and flexible job-shop scheduling problem [J].Control and Decision,2019.
[15]LI X Y,XIAO S Q,WANG C Y,et al.Mathematical modelling and a discrete artificial bee colony algorithm for the welding shop scheduling problem[J].Memeting Computing,2019,11:371-389.
[16]GAO K Z,SUGANTHAN P N,PAN Q K,et al.An improved artificial bee colony algorithm for flexible job-shop scheduling problem with fuzzy processing time[J].Expert Systems with Applications,2016,65:52-67.
[17]BEHNAMIAN J.Decomposition based hybrid VNS-TS algo-rithm for distributed parallel factories scheduling with virtual corporation[J].Computers and Operations Research,2014,52:181-191.
[18]CHANG H C,LIU T K.Optimisation of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms[J].Journal of Intelligent Manufacturing,2017,28:1973-1986.
[19]DE G L,PEZZELLA F.An improved genetic algorithm for the distributed and flexible job shop scheduling problem[J].European Journal of Operational Research,2010,200(2):395-408.
[20]LEI D M,YUAN Y,CAI J C,et al.An imperialist competitive algorithm with memory for distributed unrelated parallel machines scheduling[J].International Journal of Production Research,2020,58(2):597-614.
[21]LIN J,WANG Z J,LI X D.A backtracking search hyper-heuristic for the distributed assembly flow shop scheduling problem[J].Swarm and Evolutionary Computation,2017,36,124-135.
[22]PIROOZFARD H,WONG K Y,WONG W P.Minimizing total carbon footprint and total late work criterion in flexible job shop scheduling by using an improved multi-objective genetic algorithm[J].Resources Conservation and Recycling,2018,128:267-283.
[23]BAGHERI A,ZANDIEH M.Bi-criteria flexible job-shop sche-duling with sequence-dependent setup times-variable neighbor-
hood search approach[J].Journal Manufacturing Systems,2011,30(1):8-15.
[24]LEI D M,ZHENG Y L,GUO X P.A shuffled frog leaping algorithm for flexible job shop scheduling with the consideration of energy consumption [J].International Journal of Production Research,2017,55(11):3126-3140.
[25]LI M,LEI D M.Novel imperialist competitive algorithm formany-objective flexible job shop scheduling [J].Control theory and Applications,2018,35(1):1-9.
[26]KONG W J,DING J L,CHAI T Y.Survey on large-dimensional multi-objective evolutionary algorithms[J].Control and Decision,2010,25(3):321-326.
[27]DEB K,PRATAP A,AGARWAL S,et al.A fast and elitistmultiobjective genetic algorithm:NSGA-II [J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[28]BRANDIMARTE P.Routing and scheduling in a flexible jobshop by tabu search [J].Annals of Operations Research,1993,41(1):157-183.
[29]KNOWLES J D,CORNE D W.On metrics for comparing non- dominated sets[C]//Proc. of 2002 Congress on Evolutionary Computation.Honolulu,2002:711-716.
[30]LEI D M.Pareto archive particle swarm optimization multi-objective fuzzy job shop scheduling problems[J].International Journal of Advanced Manufacturing Technology,2008,37(1/2):157-165.

相关文章 15

[1]	孙刚, 伍江江, 陈浩, 李军, 徐仕远. 一种基于切比雪夫距离的隐式偏好多目标进化算法 Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance 计算机科学, 2022, 49(6): 297-304. https://doi.org/10.11896/jsjkx.210500095
[2]	李浩东, 胡洁, 范勤勤. 基于并行分区搜索的多模态多目标优化及其应用 Multimodal Multi-objective Optimization Based on Parallel Zoning Search and Its Application 计算机科学, 2022, 49(5): 212-220. https://doi.org/10.11896/jsjkx.210300019
[3]	彭冬阳, 王睿, 胡谷雨, 祖家琛, 王田丰. 视频缓存策略中QoE和能量效率的公平联合优化 Fair Joint Optimization of QoE and Energy Efficiency in Caching Strategy for Videos 计算机科学, 2022, 49(4): 312-320. https://doi.org/10.11896/jsjkx.210800027
[4]	石克翔, 保利勇, 丁洪伟, 官铮, 赵雷. 基于生成时间序列均匀优化的混沌人工蜂群算法 Chaos Artificial Bee Colony Algorithm Based on Homogenizing Optimization of Generated Time Series 计算机科学, 2021, 48(7): 270-280. https://doi.org/10.11896/jsjkx.200800087
[5]	章菊, 李学鋆. 基于莱维萤火虫算法的智能生产线调度问题研究 Research on Intelligent Production Line Scheduling Problem Based on LGSO Algorithm 计算机科学, 2021, 48(6A): 668-672. https://doi.org/10.11896/jsjkx.210300118
[6]	王珂, 曲桦, 赵季红. 多域SFC部署中基于强化学习的多目标优化方法 Multi-objective Optimization Method Based on Reinforcement Learning in Multi-domain SFC Deployment 计算机科学, 2021, 48(12): 324-330. https://doi.org/10.11896/jsjkx.201100159
[7]	朱汉卿, 马武彬, 周浩浩, 吴亚辉, 黄宏斌. 基于改进多目标进化算法的微服务用户请求分配策略 Microservices User Requests Allocation Strategy Based on Improved Multi-objective Evolutionary Algorithms 计算机科学, 2021, 48(10): 343-350. https://doi.org/10.11896/jsjkx.201100009
[8]	崔国楠, 王立松, 康介祥, 高忠杰, 王辉, 尹伟. 结合多目标优化算法的模糊聚类有效性指标及应用 Fuzzy Clustering Validity Index Combined with Multi-objective Optimization Algorithm and Its Application 计算机科学, 2021, 48(10): 197-203. https://doi.org/10.11896/jsjkx.200900061
[9]	张清琪, 刘漫丹. 复杂网络社区发现的多目标五行环优化算法 Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery 计算机科学, 2020, 47(8): 284-290. https://doi.org/10.11896/jsjkx.190700082
[10]	陈孟辉, 曹黔峰, 兰彦琦. 基于区块挖掘与重组的启发式算法求解置换流水车间调度问题 Heuristic Algorithm Based on Block Mining and Recombination for Permutation Flow-shop Scheduling Problem 计算机科学, 2020, 47(6A): 108-113. https://doi.org/10.11896/JsJkx.190300151
[11]	孙敏, 陈中雄, 叶侨楠. 云环境下基于HEDSM的工作流调度策略 Workflow Scheduling Strategy Based on HEDSM Under Cloud Environment 计算机科学, 2020, 47(6): 252-259. https://doi.org/10.11896/jsjkx.190400047
[12]	赵松辉, 任志磊, 江贺. 软件升级问题的多目标优化方法 Multi-objective Optimization Methods for Software Upgradeability Problem 计算机科学, 2020, 47(6): 16-23. https://doi.org/10.11896/jsjkx.200400027
[13]	夏春艳, 王兴亚, 张岩. 基于多目标优化的测试用例优先级排序方法 Test Case Prioritization Based on Multi-objective Optimization 计算机科学, 2020, 47(6): 38-43. https://doi.org/10.11896/jsjkx.191100113
[14]	董海, 徐晓鹏, 谢谢. 多目标优化算法求解多柔性作业车间调度问题 Solving Multi-flexible Job-shop Scheduling by Multi-objective Algorithm 计算机科学, 2020, 47(12): 239-244. https://doi.org/10.11896/jsjkx.191100042
[15]	王绪亮, 聂铁铮, 唐欣然, 黄菊, 李迪, 闫铭森, 刘畅. 流式数据处理的动态自适应缓存策略研究 Study on Dynamic Adaptive Caching Strategy for Streaming Data Processing 计算机科学, 2020, 47(11): 122-127. https://doi.org/10.11896/jsjkx.190800093

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed