融合NSGA-II和CSA的多目标车间调度

doi:10.3778/j.issn.1002-8331.2210-0486

摘要/Abstract

摘要： 针对在灵活车间系统中调度作业和自动引导车（automated guide vehicle，AGV）的同时调度问题，考虑在有限多个AGV和加工机台的情况下，以最小化最大完工时间、单个AGV搬运消耗时间及所有AGV搬运总消耗时间为目标函数，设计融合NSGA-II（non-dominated sorting genetic algorithms）和克隆选择（clonal selection algorithm，CSA）的改进算法INGCSA来解决此类问题。采用工件、加工机台和AGV三部分编码；引入非支配排序和目标函数值大小排序后总得分进行种群分层，从而有效地保留优秀个体；针对克隆后的种群，对不同等级的种群采取不同的变异概率，并对染色体进行内部交换与均匀交叉混合交换的基因重组，有效地提高了种群的多样性与防止陷入局部最优。通过三组对比实验，验证了该算法在探索最优解时，具有运行时间短、稳定性高和收敛性好等优点。

关键词: NSGA-II, 克隆选择算法, 任务调度, 运输调度, 自动引导车（AGV）

Abstract: Aiming at the simultaneous scheduling problem of scheduling jobs and automated guide vehicles (AGVs) in the flexible workshop system, consider building the objective function to minimize maximum processing machine duration, single AGV handling time, and total AGV handling time in the case of a finite number of AGVs and processing machines. Design an improved algorithm that combines NSGA-II (non-dominated sorting genetic algorithms) and clonal selection algorithm (CSA) to solve such problems. Firstly, the workpiece, the processing machine and the AGV are used for three-part coding. Secondly, the total score of non-dominated ranking and objective function value size sorting is introduced to stratify the population, so as to effectively retain excellent individuals. Thirdly, for the cloned population, different probabilities of variation are adopted for different levels of populations, and the genetic recombination of internal exchange and uniform cross-mixing exchange of chromosomes is carried out to effectively improve the diversity of the population and prevent it from falling into local optimum. Finally, three sets of comparative experiments verify that the algorithm has the advantages of short running time, high stability and good convergence when exploring the optimal solution.

Key words: NSGA-II, clonal selection algorithm, task scheduling, transportation scheduling, automated guide vehicle (AGV)

杨青, 席珍珍, 葛亮, 林星宇, 邢志超. 融合NSGA-II和CSA的多目标车间调度[J]. 计算机工程与应用, 2024, 60(4): 315-323.

YANG Qing, XI Zhenzhen, GE Liang, LIN Xingyu, XING Zhichao. Multi-Objective Shop Floor Scheduling Combining NSGA-II and CSA[J]. Computer Engineering and Applications, 2024, 60(4): 315-323.

参考文献

[1] FONTES D B M M, HOMAYOUNI S M. Joint production and transportation scheduling in flexible manufacturing systems[J]. Journal of Global Optimization, 2019, 74(4): 879-908.
[2] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[3] 张伟, 曾思通. 基于NSGA-II的多目标流水车间调度问题研究[J]. 机电技术, 2017(6): 46-50.
ZHANG W, ZENG S T. Research on multi-objective flow shop scheduling problem based on NSGA-II[J]. Electro-Mechanical Technology, 2017(6): 46-50.
[4] TAN W H, YUAN X, WANG J, et al. A fatigue-conscious dual resource constrained flexible job shop scheduling problem by enhanced NSGA-II: an application from casting work-shop[J]. Computers & Industrial Engineering, 2021, 160: 107557.
[5] 王莹莹, 张贞凯. 基于改进 NSGA-II 的雷达通信一体化信号功率优化设计[J]. 火力与指挥控制, 2022,47(1): 150-155.
WANG Y Y, ZHANG Z K. Optimal design of signal power for integrated radar and communication based on improved NSGA-II[J]. Fire Control & Command Control, 2022, 47(1): 150-155.
[6] 陆科苗, 何利力. 基于改进NSGA-Ⅱ混合算法求解多目标柔性作业车间调度问题[J]. 智能计算机与应用, 2022, 12(7): 46-51.
LU K M, HE L L. Solving multi-objective flexible job shop scheduling problem based on improved NSGA-Ⅱ hybrid algorithm[J]. Intelligent Computer and Application, 2022, 12(7): 46-51.
[7] CHEN J, NING T, XU G, et al. A memetic algorithm for energy-efficient scheduling of integrated production and shipping[J]. International Journal of Computer Integrated Manufacturing, 2022, 35(10/11): 1246-1268.
[8] LI G, LI X, GAO L, et al. Tasks assigning and sequencing of multiple AGVs based on an improved harmony search algorithm[J]. Journal of Ambient Intelligence and Humanized Computing, 2019, 10(11): 4533-4546.
[9] 陈魁, 毕利. 考虑运输时间的多目标柔性作业车间调度研究[J]. 小型微型计算机系统, 2021, 42(5): 946-952.
CHEN K, BI L. Research on multi-objective flexible job shop scheduling considering transport time[J]. Journal of Chinese Computer Systems, 2021, 42(5): 946-952.
[10] HIDRI L, ELKOSANTINI S, MABKHOT M. Exact and heuristic procedures for the two-center hybrid flow shop scheduling problem with transportation times[J]. IEEE Access, 2018, 6: 21788-21801.
[11] NISHI T, HIRANAKA Y, GROSSMANN I E. A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles[J]. Computers & Operations Research, 2011, 38(5): 876-888.
[12] 赵宁, 李开典, 田青, 等. 考虑运输时间柔性作业车间调度问题的快速寻优方法[J]. 计算机集成制造系统, 2015, 21(3): 724-732.
ZHAO N, LI K D, TIAN Q, et al. Fast optimization approach of flexible job shop scheduling with transport time consideration[J]. Computer Integrated Manufacturing Systems, 2015, 21(3): 724-732.
[13] ZABIHZADEH S S, REZAEIAN J. Two meta-heuristic algorithms for flexible flow shop scheduling problem with robotic transportation and release time[J]. Applied Soft Computing, 2016, 40: 319-330.
[14] MA P C, TAO F, LIU Y L, et al. A hybrid particle swarm optimization and simulated annealing algorithm for job-shop scheduling[C]//Proceedings of the 2014 IEEE International Conference on Automation Science and Engineering, 2014: 125-130.
[15] SEENU N, KUPPAN C R M, RAMYA M M, et al. Review on state-of-the-art dynamic task allocation strategies for multiple-robot systems[J]. Industrial Robot, 2020, 47(6): 929-942.
[16] 黄平, 孟永钢. 最优化理论与方法[M]. 北京：清华大学出版社, 2009: 189-201.
HUANG P, MENG Y G. Optimization theory and method[M]. Beijing: Tsinghua University Press, 2009: 189-201.
[17] 高亮, 张国辉, 王晓娟. 柔性作业车间调度智能算法及其应用[M]. 武汉: 华中科技大学出版社, 2012:102-107.
GAO L, ZHANG G H, WANG X J. Flexible job shop scheduling intelligent algorithm and its application[M]. Wuhan: Huazhong University of Science and Technology Press, 2012: 102-107.
[18] 全燕鸣, 何一明. 多机器人任务分配调度的克隆选择算法[J]. 华南理工大学学报 (自然科学版), 2021, 49(5): 102-110.
QUAN Y M, HE Y M. Research on clonal selection algorithm for multi-robot task allocation and scheduling[J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(5): 102-110.
[19] BAGHISHANI H, MOHAMMADZADEH M. A data cloning algorithm for computing maximum likelihood estimates in spatial generalized linear mixed models[J]. Computational Statistics & Data Analysis, 2011, 55(4): 1748-1759.
[20] 王丽萍, 任宇, 邱启仓, 等. 多目标进化算法性能评价指标研究综述[J]. 计算机学报, 2021, 44(8): 1590-1619.
WANG L P, REN Y, QIU Q C, et al. Survey on performance indicators for multi-objective evolutionary algorithms[J]. Chinese Journal of Computers, 2021, 44(8): 1590-1619.
[21] COELLO C A C, CORTéS N C. Solving multi-objective optimization problems using an artificial immune system[J]. Genetic Programming and Evolvable Machines, 2005, 6(2): 163-190.
[22] LI Z P, LI X T. Research on model and algorithm of task allocation and path planning for multi-robot[J]. Open Journal of Applied Sciences, 2017, 7(10): 511-519.