Effective NSGA-II Algorithm for a Limited AGV Scheduling Problem in Matrix Manufacturing Workshops with Undirected Material Flow
), Abstract
Automatic guided vehicles (AGVs) are extensively employed in manufacturing workshops for their high degree of automation and flexibility. This paper investigates a limited AGV scheduling problem (LAGVSP) in matrix manufacturing workshops with undirected material flow, aiming to minimize both total task delay time and total task completion time. To address this LAGVSP, a mixed-integer linear programming model is built, and a nondominated sorting genetic algorithm II based on dual population co-evolution (NSGA-IIDPC) is proposed. In NSGA-IIDPC, a single population is divided into a common population and an elite population, and they adopt different evolutionary strategies during the evolution process. The dual population co-evolution mechanism is designed to accelerate the convergence of the non-dominated solution set in the population to the Pareto front through information exchange and competition between the two populations. In addition, to enhance the quality of initial population, a minimum cost function strategy based on load balancing is adopted. Multiple local search operators based on ideal point are proposed to find a better local solution. To improve the global exploration ability of the algorithm, a dual population restart mechanism is adopted. Experimental tests and comparisons with other algorithms are conducted to demonstrate the effectiveness of NSGA-IIDPC in solving the LAGVSP.
Keywords
References
J. Mohr, N. Schmidtke, and F. Behrendt, Design of matrix production systems: New demands on factory planning methods, Procedia Comput. Sci., vol. 232, pp. 1972–1981, 2024.
T. van Erp, R. Goncalves, and N. G. M. Rytter, Design of matrix production systems: A skill-based systems engineering approach, Procedia CIRP, vol. 120, pp. 1173–1178, 2023.
W. Zou, J. Zou, H. Sang, L. Meng, and Q. Pan, An effective population-based iterated greedy algorithm for solving the multi-AGV scheduling problem with unloading safety detection, Inf. Sci., vol. 657, p. 119949, 2024.
Z. K. Li, H. Y. Sang, X. J. Zhang, W. Q. Zou, B. Zhang, and L. L. Meng, An effective discrete invasive weed optimization algorithm for multi-AGVs dispatching problem with specific cases in matrix manufacturing workshop, Comput. Ind. Eng., vol. 174, p. 108755, 2022.
D. B. M. M. Fontes, S. M. Homayouni, and J. F. Gonçalves, A hybrid particle swarm optimization and simulated annealing algorithm for the job shop scheduling problem with transport resources, Eur. J. Oper. Res., vol. 306, no. 3, pp. 1140–1157, 2023.
R. Chen, B. Wu, H. Wang, H. Tong, and F. Yan, A Q-learning based NSGA-II for dynamic flexible job shop scheduling with limited transportation resources, Swarm Evol. Comput., vol. 90, p. 101658, 2024.
Y. Yao, L. Gui, X. Li, and L. Gao, Tabu search based on novel neighborhood structures for solving job shop scheduling problem integrating finite transportation resources, Robot. Comput. Integr. Manuf., vol. 89, p. 102782, 2024.
Y. Yao, X. Li, and L. Gao, A DQN-based memetic algorithm for energy-efficient job shop scheduling problem with integrated limited AGVs, Swarm Evol. Comput., vol. 87, p. 101544, 2024.
Z. Zhu, J. Xiao, S. He, Z. Ji, and Y. Sun, A multi-objective memetic algorithm based on locality-sensitive hashing for one-to-many-to-one dynamic pickup-and-delivery problem, Inf. Sci., vol. 329, pp. 73–89, 2016.
Y. Lin, Y. Xu, J. Zhu, X. Wang, L. Wang, and G. Hu, MLATSO: A method for task scheduling optimization in multi-load AGVs-based systems, Robot. Comput. Integr. Manuf., vol. 79, p. 102397, 2023.
W. Q. Zou, Q. K. Pan, L. Wang, Z. H. Miao, and C. Peng, Efficient multiobjective optimization for an AGV energy-efficient scheduling problem with release time, Knowl. Based Syst., vol. 242, p. 108334, 2022.
X. J. Zhang, H. Y. Sang, J. Q. Li, Y. Y. Han, and P. Duan, An effective multi-AGVs dispatching method applied to matrix manufacturing workshop, Comput. Ind. Eng., vol. 163, p. 107791, 2022.
W. Q. Zou, Q. K. Pan, L. L. Meng, H. Y. Sang, Y. Y. Han, and J. Q. Li, An effective self-adaptive iterated greedy algorithm for a multi-AGVs scheduling problem with charging and maintenance, Expert Syst. Appl., vol. 216, p. 119512, 2023.
Q. Wei, Y. Yan, J. Zhang, J. Xiao, and C. Wang, A self-attention-based deep reinforcement learning approach for AGV dispatching systems, IEEE Trans. Neural Netw. Learn. Syst., vol. 35, no. 6, pp. 7911–7922, 2024.
H. Hu, X. Jia, Q. He, S. Fu, and K. Liu, Deep reinforcement learning based AGVs real-time scheduling with mixed rule for flexible shop floor in Industry 4.0, Comput. Ind. Eng., vol. 149, p. 106749, 2020.
X. Wang, J. Lu, F. Ke, X. Wang, and W. Wang, Research on AGV task path planning based on improved A* algorithm, Virtual Real. Intell. Hardw., vol. 5, no. 3, pp. 249–265, 2023.
W. Małopolski, A sustainable and conflict-free operation of AGVs in a square topology, Comput. Ind. Eng., vol. 126, pp. 472–481, 2018.
K. Wang, W. Liang, H. Shi, J. Zhang, and Q. Wang, Driving line-based two-stage path planning in the AGV sorting system, Robot. Auton. Syst., vol. 169, p. 104505, 2023.
M. Zhong, Y. Yang, Y. Dessouky, and O. Postolache, Multi-AGV scheduling for conflict-free path planning in automated container terminals, Comput. Ind. Eng., vol. 142, p. 106371, 2020.
L. Xu, N. Wang, and X. Ling, Study on conflict-free AGVs path planning strategy for workshop material distribution systems, Procedia CIRP, vol. 104, pp. 1071–1076, 2021.
S. Lin, A. Liu, J. Wang, and X. Kong, An improved fault-tolerant cultural-PSO with probability for multi-AGV path planning, Expert Syst. Appl., vol. 237, p. 121510, 2024.
K. Li, T. Liu, P. N. Ram Kumar, and X. Han, A reinforcement learning-based hyper-heuristic for AGV task assignment and route planning in parts-to-picker warehouses, Transp. Res. Part E Logist. Transp. Rev., vol. 185, p. 103518, 2024.
T. Miyamoto and K. Inoue, Local and random searches for dispatch and conflict-free routing problem of capacitated AGV systems, Comput. Ind. Eng., vol. 91, pp. 1–9, 2016.
H. Fazlollahtabar and S. Hassanli, Hybrid cost and time path planning for multiple autonomous guided vehicles, Appl. Intell., vol. 48, no. 2, pp. 482–498, 2018.
M. Saidi-Mehrabad, S. Dehnavi-Arani, F. Evazabadian, and V. Mahmoodian, An ant colony algorithm (ACA) for solving the new integrated model of job shop scheduling and conflict-free routing of AGVs, Comput. Ind. Eng., vol. 86, pp. 2–13, 2015.
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182–197, 2002.
W. Q. Zou, Q. K. Pan, and L. Wang, An effective multi-objective evolutionary algorithm for solving the AGV scheduling problem with pickup and delivery, Knowl. Based Syst., vol. 218, p. 106881, 2021.
E. Zitzler and L. Thiele, Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach, IEEE Trans. Evol. Comput., vol. 3, no. 4, pp. 257–271, 1999.
P. A. N. Bosman and D. Thierens, The balance between proximity and diversity in multiobjective evolutionary algorithms, IEEE Trans. Evol. Comput., vol. 7, no. 2, pp. 174–188, 2003.
K. Deb and H. Jain, An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints, IEEE Trans. Evol. Comput., vol. 18, no. 4, pp. 577–601, 2014.
Y. Tian, T. Zhang, J. Xiao, X. Zhang, and Y. Jin, A coevolutionary framework for constrained multiobjective optimization problems, IEEE Trans. Evol. Comput., vol. 25, no. 1, pp. 102–116, 2021.
京公网安备11010802044758号