Research on Multi-Agent Task Scheduling Optimization Based on Deep Reinforcement Learning
DOI:
https://doi.org/10.62051/2drfd889Keywords:
Multi-agent scheduling; Graph neural network; Reinforcement learning.Abstract
For the task scheduling problem in multi-agent systems, this paper proposes a collaborative optimization method based on Graph Neural Network and Reinforcement Learning. Firstly, a heterogeneous graph structure is constructed to uniformly model the temporal dependencies, resource competition, and agent capability differences among tasks, and multi-dimensional node features are designed to fully describe the scheduling state. Secondly, the Proximal Policy Optimization algorithm is adopted to achieve efficient training and stable convergence of the policy network based on graph embedding, supporting rapid decision-making for large-scale instances. To verify its effectiveness, 30 test cases are generated for each of the three scales, totaling 90 cases. It is compared with Genetic Algorithm and Gurobi's exact solver. Through a large number of simulation experiments, the effectiveness and advantages of this method in solving the studied problem have been verified.
Downloads
References
[1] Weiss G. Multiagent systems: a modern approach to distributed artificial intelligence [M]. Cambridge: MIT press; 1999.
[2] Gronauer S, Diepold K. Multi-agent deep reinforcement learning: a survey [J]. Artificial Intelligence Review. 2022, 55 (2): 895-943. DOI: https://doi.org/10.1007/s10462-021-09996-w
[3] Graham RL, Lawler EL, Lenstra JK, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey [J]. Annals of Discrete Mathematics. 1979 (5): 287–326. DOI: https://doi.org/10.1016/S0167-5060(08)70356-X
[4] Pinedo ML. Scheduling: Theory, Algorithms, and Systems [M]. 4th ed. Cambridge: Springer, 2008.
[5] Hoogeveen H. Multicriteria scheduling [J]. European Journal of operational research, 2005, 167 (3): 592- 623. DOI: https://doi.org/10.1016/j.ejor.2004.07.011
[6] Minella G, Ruiz R, Ciavotta M. A review and evaluation of multiobjective algorithms for the flowshop scheduling problem [J]. INFORMS Journal on Computing. 2008, 20 (3): 451-471. DOI: https://doi.org/10.1287/ijoc.1070.0258
[7] Peha JM. Heterogeneous-criteria scheduling: minimizing weighted number of tardy jobs and weighted completion time [J]. Computers & operations research. 1995; 22 (10): 1089-100. DOI: https://doi.org/10.1016/0305-0548(94)00090-U
[8] Balasubramanian H, Fowler J, Keha A, et al. Scheduling interfering job sets on parallel machines [J]. European Journal of Operational Research. 2009, 199 (1): 55-67. DOI: https://doi.org/10.1016/j.ejor.2008.10.038
[9] Elvikis D, Hamacher H, t'Kindt V. Scheduling two interfering job sets on uniform parallel machines with makespan and cost functions [C]. //4th Multidisciplinary International Conference on Scheduling: Theory and Applications. 2009: 645–654
[10] Perez-Gonzalez P, Framinan JM. A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems[J]. European Journal of Operational Research. 2014, 235 (1): 1-6. DOI: https://doi.org/10.1016/j.ejor.2013.09.017
[11] Prorok A, Hsieh MA, Kumar V. Fast redistribution of a swarm of heterogeneous robots [J]. EAI Endorsed Transactions on Scalable Information Systems. 2016, 3 (10): 249-55. DOI: https://doi.org/10.4108/eai.3-12-2015.2262349
[12] Caridi M, Cavalieri S. Multi-agent systems in production planning and control: an overview [J]. Production Planning & Control. 2004, 15 (2): 106-18. DOI: https://doi.org/10.1080/09537280410001662556
[13] Amador S, Okamoto S, Zivan R. Dynamic multi-agent task allocation with spatial and temporal constraints [C]. //Proceedings of the AAAI Conference on Artificial Intelligence. 2014, 28 (1). DOI: https://doi.org/10.1609/aaai.v28i1.8889
[14] Le Pape C. A combination of centralized and distributed methods for multi-agent planning and scheduling [C]. // Proceedings., IEEE International Conference on Robotics and Automation. 1990: 488- 493. DOI: https://doi.org/10.1109/ROBOT.1990.126026
[15] Nunes E, Gini M. Multi-robot auctions for allocation of tasks with temporal constraints [C]. //Proceedings of the AAAI conference on artificial intelligence. 2015, 29 (1). DOI: https://doi.org/10.1609/aaai.v29i1.9440
[16] Das GP, McGinnity TM, Coleman SA, Behera L. A distributed task allocation algorithm for a multi-robot system in healthcare facilities [J]. Journal of Intelligent & Robotic Systems. 2015, 80 (1): 33-58. DOI: https://doi.org/10.1007/s10846-014-0154-2
[17] Cheng CY, Chen TL, Wang LC, et al. A genetic algorithm for the multi-stage and parallel-machine scheduling problem with job splitting–A case study for the solar cell industry [J]. International Journal of Production Research. 2013, 51 (16): 4755-77. DOI: https://doi.org/10.1080/00207543.2013.774468
[18] Chen L, Dai SL, Dong C. Adaptive optimal tracking control of an underactuated surface vessel using actor–critic reinforcement learning [J]. IEEE Transactions on Neural Networks and Learning Systems. 2022.
[19] Vu VT, Tran QH, Pham TL, et al. Online actor-critic reinforcement learning control for uncertain surface vessel systems with external disturbances [J]. International Journal of Control, Automation and Systems. 2022, 20 (3): 1029-40. DOI: https://doi.org/10.1007/s12555-020-0809-7
[20] Dao PN, Liu YC. Adaptive reinforcement learning in control design for cooperating manipulator systems [J]. Asian Journal of Control. 2022, 24 (3): 1088-103. [53] Lillicrap T P, Hunt J J, Pritzel A. et al. Continuous control with deep reinforcement learning [J]. arXiv preprint arXiv: 1509. 02971. 2015. DOI: https://doi.org/10.1002/asjc.2830
[21] Wang Z, Liu C, Gombolay M. Heterogeneous graph attention networks for scalable multi-robot scheduling with temporospatial constraints [J]. Autonomous Robots. 2022, 46 (1): 249-68. DOI: https://doi.org/10.1007/s10514-021-09997-2
[22] Tampuu A, Matiisen T, Kodelja D, et al. Multiagent cooperation and competition with deep reinforcement learning [J]. PloS one. 2017, 12 (4): e0172395. [56] Hu K, Li M, Song Z, et al. A review of research on reinforcement learning algorithms for multi-agents [J]. Neurocomputing. 2024: 128068. DOI: https://doi.org/10.1371/journal.pone.0172395
[23] Ning Z. A survey on multi-agent reinforcement learning and its application [J]. Journal of Automation and Intelligence. 2024. DOI: https://doi.org/10.1016/j.jai.2024.02.003
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Transactions on Computer Science and Intelligent Systems Research
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
