基于莱维萤火虫算法的智能生产线调度问题研究

doi:10.11896/jsjkx.210300118

摘要/Abstract

摘要： 针对智能生产线调度过程中易出现饥饿和堵塞等问题,通过分析调度过程,建立调度问题的目标函数和约束条件;然后提出一种基于莱维飞行的新型萤火虫算法,利用莱维分布提高种群的搜索范围和有效性,以最大和最小荧光素作为边界约束优化荧光素迭代公式,提高个体所携带荧光素的合理性;引入立方映射实现对种群的优化,提高种群的综合搜索能力。算法测试结果表明,莱维萤火虫算法(Levy Glowworm Swarm Optimization,LGSO)相比GSO(Glowworm Swarm Optimization)、SGSO(Glowworm Swarm Optimization of Scene Understanding )和CGSO(Chaos Glowworm Swarm Optimization)具有更好的求解精度、收敛性和稳定性。利用LGSO算法对典型的4种智能生产线的调度问题进行优化求解,并与GSO算法和SGSO算法进行对比,结果表明:LGSO算法计算结果的最差值、最优值、结果平均值以及标准偏差基本均优于其他两种算法,特别在复杂路径下,LGSO算法具有更好的求解精度、收敛速度及稳定性,验证了数学模型的准确性和LGSO算法解决调度问题的可行性。

关键词: 调度问题, 莱维飞行, 萤火虫优化算法, 智能生产线

Abstract: Aiming at the problems of starvation and congestion in the scheduling process of intelligent production line,the objective function and constraint conditions of scheduling problem are established by analyzing the scheduling process.Then a new glowworm swarm optimization algorithm based on Levy flight is proposed.Levy distribution is used to improve the search range and effectiveness of the population.The maximum and minimum fluorescein are taken as boundary constraints to optimize the ite-rative formula of fluorescein,and to improve the rationality of the fluorescein carried by individuals.And the cubic mapping is introduced to optimize the population,so as to improve the comprehensive search ability of the population.The algorithm test results show that LGSO is provided with better solution accuracy,convergence and stability than GSO,SGSO and CGSO.LGSO algorithm is used to solve the scheduling problems of four typical intelligent production lines,and compared with GSO and SGSO.The results show that LGSO is basically better than the other two algorithms in the worst value,the optimal value,the average value and the standard deviation.In the complex path,LGSO has better solution accuracy,convergence speed and stability.Further,the accuracy of the mathematical model and the feasibility of LGSO to solve the scheduling problem are verified by the test.

Key words: Glowworm swarm optimization algorithm, Intelligent production line, Levy flight, Scheduling problem

中图分类号:

O221

章菊, 李学鋆. 基于莱维萤火虫算法的智能生产线调度问题研究[J]. 计算机科学, 2021, 48(6A): 668-672. https://doi.org/10.11896/jsjkx.210300118

ZHANG Ju, LI Xue-yun. Research on Intelligent Production Line Scheduling Problem Based on LGSO Algorithm[J]. Computer Science, 2021, 48(6A): 668-672. https://doi.org/10.11896/jsjkx.210300118

参考文献

[1] LIU Y Z,LI M G,DU H.Robust H-∞ control of NCS with delay and packet dropout[J].Control and Decision,2014,29(3):517-522.
[2] AHMADI E,ZANDIEH M,FARROKH M,et al.A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithms[J].Computers & Operations Research,2016,73:56-66.
[3] FANG D J,HUANG Z Y.Method of parallel optimization of facility layout and production scheduling for reconfigurable hybrid flow production line[J].Logistics Technology,2019,38(7):117-122.
[4] EBRAHIMIPOUR V,NAJJARBASHI A,SHEIKHALISHAHI M.Multi-objective modeling for preventive maintenance scheduling in a multiple production line[J].Journal of Intelligent Manufacturing,2013,26(1):1-12.
[5] FLETCHER M,DEEN S M.Task rescheduling in multi-agent manufacturing[C]//Tenth International Workshop on Database and Expert Systems Applications.IEEE Computer Society,1999.
[6] LU Z Q,HU X M,ZHU H W.Dynamic scheduling method for aircraft moving assembly line under uncertain supply of material[J].Journal of Tongji University (Natural Science),2019,47(5):723-730,738.
[7] MAO Y N,TANG Q H,ZHANG L P,et al.Mathematic model for automated mixed production line scheduling problem with multi-capacity machines[J].Computer Integrated Manufacturing Systems,2019,25(7):1717-1728.
[8] LI H,ZHANG Y,YE Q H,et al,Research on flexible production line scheduling with lot streaming and setup times [J].Industrial Engineering and Management,2020,25(3):179-187.
[9] JIA Z H,CHEN H P,SUN Y H.Hybrid particle swarm optimization for flexible job-shop scheduling[J].Journal of System Simulation,2007(20):4743-4747.
[10] ŠUCHA B L,ZDENĚK P H.Solving the Resource Constrained Project Scheduling Problem using the parallel Tabu Search designed for the CUDA platform[M].Academic Press,Inc.2015.
[11] THOMAS P R,SALHI S.A Tabu Search Approach for the Resource Constrained Project Scheduling Problem[J].Journal of Heuristics,1998,4(2):123-139.
[12] ZDENĚK H,SUCHA P.Time symmetry of resource constrained project scheduling with general temporal constraints and take-give resources[J].Annals of Operations Research,2016,248:209-217.
[13] ZENG B,LI M F,ZHANG Y,et al.Research on assembly sequence planning based on firefly algorithm[J].Journal of Mechanical Engineering,2013,49(11):177-184.
[14] HUANG Q,ZHOU Q H,ZHANG Q,et al.Layout optimization of dip dyeing workshop based on system layout planning-genetic algorithm[J].Journal of Textile Research,2020,41(3):84-90.
[15] WU Q D,MA Y M,LI L,et al.Data-driven dynamic scheduling method for semiconductor production line[J].Control Theory & Applications,2015,32(9):1233- 1239.
[16] ZHU G Y,XU W J.Multi-objective flexible job shop scheduling method for machine tool component production line considering energy consumption and quality [J].Control and Decision,2019,34(2):252-260.
[17] LUO T H,LIANG S,HE Z Y,et al.Path planning of robot based on glowworm swarm optimization algorithm of scene understanding[J].Journal of Computer Applications,2017,37(12):3608-3613.
[18] HAO X Y,HE X S,XUE J J.A cuckoo initialization of fireflyalgorithm and its engineering application[J].Computer Technology and Development,2018,28(12):167-170,175.
[19] NIU H F,SONG W P,NING A P.Hybrid search algorithm on particle swarm optimization and levy flight[J].Journal of Taiyuan University of Science and Technology,2016,37(1):6-11.
[20] WANG X W,YAN Y X,GU X S.Welding robot path planning based on Levy-PSO[J].Control and Decision,2017,32(2):373-377.
[21] YU S H,SU S B.Research and application of chaotic glowworm swarm optimization algorithm[J].Journal of Frontiers of Computer Science & Technology,2014,8(3):352-358.

相关文章 15

[1]	陈俊, 何庆, 李守玉. 基于自适应反馈调节因子的阿基米德优化算法 Archimedes Optimization Algorithm Based on Adaptive Feedback Adjustment Factor 计算机科学, 2022, 49(8): 237-246. https://doi.org/10.11896/jsjkx.210700150
[2]	范星泽, 禹梅. 改进灰狼算法的无线传感器网络覆盖优化 Coverage Optimization of WSN Based on Improved Grey Wolf Optimizer 计算机科学, 2022, 49(6A): 628-631. https://doi.org/10.11896/jsjkx.210500037
[3]	郑洁锋, 占红武, 黄巍, 张恒, 吴周鑫. Lévy Flight的发展和智能优化算法中的应用综述 Development of Lévy Flight and Its Application in Intelligent Optimization Algorithm 计算机科学, 2021, 48(2): 190-206. https://doi.org/10.11896/jsjkx.200500142
[4]	郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划 Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021
[5]	李阳, 李维刚, 赵云涛, 刘翱. 基于莱维飞行和随机游动策略的灰狼算法 Grey Wolf Algorithm Based on Levy Flight and Random Walk Strategy 计算机科学, 2020, 47(8): 291-296. https://doi.org/10.11896/jsjkx.190600107
[6]	张严, 秦亮曦. 基于Levy飞行策略的改进樽海鞘群算法 Improved Salp Swarm Algorithm Based on Levy Flight Strategy 计算机科学, 2020, 47(7): 154-160. https://doi.org/10.11896/jsjkx.190600068
[7]	郑友莲, 雷德明, 郑巧仙. 求解高维多目标调度的新型人工蜂群算法 Novel Artificial Bee Colony Algorithm for Solving Many-objective Scheduling 计算机科学, 2020, 47(7): 186-191. https://doi.org/10.11896/jsjkx.190600089
[8]	陈孟辉, 曹黔峰, 兰彦琦. 基于区块挖掘与重组的启发式算法求解置换流水车间调度问题 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
[9]	董海, 徐晓鹏, 谢谢. 多目标优化算法求解多柔性作业车间调度问题 Solving Multi-flexible Job-shop Scheduling by Multi-objective Algorithm 计算机科学, 2020, 47(12): 239-244. https://doi.org/10.11896/jsjkx.191100042
[10]	毛肖,和丽芳,王庆平. 基于改进萤火虫优化算法的多阈值彩色图像分割 Multilevel Color Image Segmentation Based on Improved Glowworm Swarm Optimization Algorithm 计算机科学, 2017, 44(Z6): 206-211. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.047
[11]	李荣雨,戴睿闻. 自适应步长布谷鸟搜索算法 Adaptive Step-size Cuckoo Search Algorithm 计算机科学, 2017, 44(5): 235-240. https://doi.org/10.11896/j.issn.1002-137X.2017.05.042
[12]	张丽红,余世明. 求解置换流水线调度问题的改进萤火虫优化算法 Improved GSO Algorithm for Solving PFSP 计算机科学, 2016, 43(8): 240-243. https://doi.org/10.11896/j.issn.1002-137X.2016.08.048
[13]	左益,公茂果,曾久琳,焦李成. 混合多目标算法用于柔性作业车间调度问题 Hybrid Multi-objective Algorithm for Solving Flexible Job Shop Scheduling Problem 计算机科学, 2015, 42(9): 220-225. https://doi.org/10.11896/j.issn.1002-137X.2015.09.042
[14]	魏嘉银秦永彬许道云. 一种求解置换Flow Shop调度问题的DRPFSP算法 DRPFSP Algorithm for Solving Permutation Flow Shop Scheduling Problem 计算机科学, 2015, 42(7): 68-73. https://doi.org/10.11896/j.issn.1002-137X.2015.07.015
[15]	蔡延光,汤雅连,朱君. 混合禁忌搜索算法求解关联运输调度问题 Hybrid Tabu Search Algorithm for Solving Incident Vehicle Routing Problem 计算机科学, 2015, 42(4): 230-234. https://doi.org/10.11896/j.issn.1002-137X.2015.04.047

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed