计算机科学 ›› 2024, Vol. 51 ›› Issue (9): 283-289.doi: 10.11896/jsjkx.230900086
陈雅莉, 潘友林, 刘耿耿
CHEN Yali, PAN Youlin, LIU Genggeng
摘要： 由于受到疫情影响,企业迫切地需要通过升级改造自动化柔性生产线来实现降本增效。在这一背景下,装配作业车间调度问题(Assembly Job Shop Scheduling Problem,AJSSP)再一次成为学术界和企业界的研究热点。AJSSP比普通作业车间调度问题多了一道装配阶段,故其存在前后工序相互制约和多机并行现象,问题求解也更加复杂。针对该问题,提出了一种基于离散变邻域蜉蝣优化算法(Discrete Variable Neighborhood Mayfly Algorithm,D-VNMA)的调度方法,主要工作如下:1)采用符合Lamarkian特性的编码解码机制,实现个体有效信息的迭代继承;2)使用Circle映射融合常见启发式算法初始化蜉蝣种群,保证种群的多样性;3)加入新的邻域探索策略,采用多种不同的邻域结构和搜索策略的差异组合,增加搜索方案的多样性,提高寻找局部最优解的搜索效率;4)提出改进的雌雄蜉蝣交配策略,提高算法全局探索能力,加快算法整体收敛速度。在实验过程中,通过试验设计(Design of Experiment,DOE)方法获得D-VNMA的最佳参数设置,并在不同规格AJSSP算例数据上将D-VNMA和其他算法进行比较。实验结果表明,D-VNMA得到最优解的概率提升了30%,且收敛效率最高可提升62.15%。
中图分类号:
| [1]HUANG X,YANG H,WEI J.Shifting Bottleneck AlgorithmBased on Filtered Beam Search for JSSP[J].Computer Science,2009,36(4):254-256,284. [2]GUO P,ZHAO W C,LEI K.Dual-resource Constrained Flexible Job Shop Optimal Scheduling Based on An Improved Jaya Algorithm[J].Journal of Jilin University(Engineering and Technology Edition),2023,53(2):480-487. [3]KOMAKI G M,SHEIKH S,MALAKOOTI B.Flow ShopScheduling Problems with Assembly Operations:A Review and NewTrends[J].International Journal of Production Research,2019,57(10):2926-2955. [4]YANG Y,LI X.A Knowledge-Driven Constructive HeuristicAlgorithm for the Distributed Assembly Blocking Flow Shop SchedulingProblem[J].Expert Systems with Applications,2022,202:117269. [5]JIANG T,LIU L,ZHU H,et al.An Improved Elephant Herding Optimization for Energy-Saving Assembly Job Shop Scheduling Problem with TransportationTimes[J].Axioms,2022,11(10):561. [6]REN W,WEN J,YAN Y,et al.Multi-ObjectiveOptimisation for Energy-aware Flexible Job-shop Scheduling Problem with Assembly Operations[J].International Journal of Production Research,2021,59(23):7216-7231. [7]WANG Z Y,LU C.An Integrated Job Shop Scheduling and Assembly Sequence Planning Approach for Discrete Manufacturing[J].Journal of Manufacturing Systems,2021,61:27-44. [8]HAJIBABAEI M,BEHNAMIAN J.Fuzzy Cleaner Productionin Assembly Flexible Job-Shop Scheduling with Machine Breakdown and Batch Transportation:Lagrangian Relaxation[J].Journal of Combinatorial Optimization,2023,45(5):112. [9]JOHNSON D,CHEN G,LU Y.Multi-Agent ReinforcementLearning for Real-Time Dynamic Production Scheduling in A Robot Assembly Cell[J].IEEE Robotics and Automation Letters,2022,7(3):7684-7691. [10]MIAO K,LI C.Optimization Algorithms for Job Shop Scheduling Problems Based on Correction Mechanisms and ReinforcementLearning[J].Computer Science,2023,50(6):274-282. [11]SUKKERD W,WUTTIPORNPUN T,LATTHAWANICH-PHAN J,et al.A New Improvement of the NEH Heuristic to EitherMinimise Total Tardiness or Makespan for a Hybrid Flow Shop with Assembly Operations[C]//Proceedings of the International Conference on Industrial Engineering and Applications.Chengdu:IEEE,2021:315-320. [12]HALIM A H,YUSRISKI R.Batch Scheduling for the Two-stage Assembly Model to Minimize Total Actual Flow Time[C]//Proceedings of the Asia Pacific Industrial Engineering and Management Systems.Kitakyushu:APIEM,2022:1742-1748. [13]LI X,LU J,YANG C,et al.Research of Flexible Assembly Job-Shop Batch-Scheduling Problem Based on Improved Artificial BeeColony[J].Frontiers in Bioengineering and Biotechnology,2022,10:909548. [14]ZERVOUDAKIS K,TSAFARAKIS S.A Mayfly OptimizationAlgorithm[J].Computers & Industrial Engineering,2020,145:106559. [15]EBERHART R,KENNEDY J.A New Optimizer Using Particle Swarm Theory[C]//Proceedings of the International Sympo-sium on Micro Machine and Human Science.Nagoya:IEEE,1995:39-43. [16]GREFENSTETTE J J.Genetic Algorithms and Machine Lear-ning[J].Machine Learning,1988,3(2):95-99. [17]YANG X S.Firefly Algorithms for Multimodal Optimization[C]//Proceedings of the International Symposium on Stochastic Algorithms.Berlin:Springer Berlin Heidelberg,2009:169-178. [18]WHITLEY D,GORDON V S,MATHIAS K.Lamarckian Evolution,the Baldwin Effect and Function Optimization[C]//Proceedings of the International Conference on Parallel Problem Solving from Nature.Israel:Springer Berlin Heidelberg:1994:5-15. [19]OW P S,MORTON T E.The Single Machine Early/Tardy Pro-blem[J].Management Science,1989,35(2):177-191. [20]DIANA R,SOUZA S.Analysis of Variable Neighborhood De-scent as a Local Search Operator for Total Weighted Tardiness Problem on Unrelated Parallel Machines[J].Computers & Ope-rations Research,2020,117:104886. [21]WANG L,WANG S,ZHENG X.A Hybrid Estimation of Distribution Algorithm for Unrelated Parallel Machine Scheduling with Sequence-dependent Setup Times[J].IEEE/CAA Journal of Automatica Sinica,2016,3(3):235-246. [22]YI Z,GONG M,ZENG J,et al.Hybrid Multi-objective Algo-rithm for Solving Flexible Job Shop Scheduling Problem[J].Computer Science,2015,42(9):220-225. [23]JANKOVIC A,CHAUDHARY G,GOIA F.Designing the Design of Experiments(DOE)－An Investigation on the Influence of Different Factorial Designs on the Characterization of Complex Systems[J].Energy and Buildings,2021,250:111298. [24]NOUIRI M,BEKRAR A,JEMAI A,et al.An Effective and Dis-tributed Particle Swarm Optimization Algorithm for Flexible Job-shop Scheduling Problem[J].Journal of Intelligent Manufacturing,2018,29:603-615. [25]KHRAIBET T J,GHAFIL W K.Using Hybrid GA-PSO Algorithm to Solve Problem in Machine Scheduling[J].Journal of Discrete Mathematical Sciences and Cryptography,2021,24(7):2027-2035. [26]RASHID M,OSMAN M.Optimisation of Energy Efficient Hybrid Flowshop Scheduling Problem Using Firefly Algorithm[C]//Proceedings of the Symposium on Computer Applications &Industrial Electronics.Malaysia:IEEE,2020:36-41. |
|
||
首页