Decentralized multi-agent collaborating for job shop scheduling with spatial constraints

Abstract

Existing job shop scheduling methods often neglect job mobility and machine spatial distribution. This paper addresses the flexible job shop scheduling problem under the spatial constraints. Specifically, it incorporates both job movement time and potential collision risks caused by local job density. The paper defines a spatially constrained scheduling environment with non-sequential machine distribution. The spatial constraints are then refined into moving distance constraints and local density constraints. Additionally, a reward function is designed, including penalties for both movement and density. This paper employs a multi-agent reinforcement learning method that combines dual attention and counterfactual baselines to solve the scheduling problem. Experimental results show that our approach effectively balances temporal and spatial factors. It reduces job movement costs and collision risks while achieving the shortest completion time.

Graphical abstract

Keywords

flexible job-shop scheduling problem / spatial constraints / multi-agent reinforcement learning

References

[1] Stephane D P, Ding J, Shen L, Tamssaouet K . The flexible job shop scheduling problem: a review. European Journal of Operational Research, 2024, 314( 2): 409–432

[2] Li Q, Ba W . A group priority earliest deadline first scheduling algorithm. Frontiers of Computer Science, 2012, 6( 5): 560–567

[3] Xue S, Zhao S, Chen Q, Song Z, Chen S, Ma T, Yang Y, Zheng W, Guo M . Kronos: towards bus contention-aware job scheduling in warehouse scale computers. Frontiers of Computer Science, 2023, 17( 1): 171101

[4] Qin Y, Wang H, Yi S, Li X, Zhai L . A multi-objective reinforcement learning algorithm for deadline constrained scientific workflow scheduling in clouds. Frontiers of Computer Science, 2021, 15( 5): 155105

[5] Li K . UAV mission scheduling with completion time, flight distance, and resource consumption constraints. Connection Science, 2023, 35( 1): 2281250

[6] Li Z, Barenji A V, Jiang J, Zhong R Y, Xu G . A mechanism for scheduling multi robot intelligent warehouse system face with dynamic demand. Journal of Intelligent Manufacturing, 2020, 31( 2): 469–480

[7] Çaliş B, Bulkan S . A research survey: review of AI solution strategies of job shop scheduling problem. Journal of Intelligent Manufacturing, 2015, 26( 5): 961–973

[8] Zhang J D, He Z, Chan W H, Chow C Y . DeepMAG: deep reinforcement learning with multi-agent graphs for flexible job shop scheduling. Knowledge-Based Systems, 2023, 259: 110083

[9] Ho N B, Tay J C. Evolving dispatching rules for solving the flexible job-shop problem. In: Proceedings of 2005 IEEE Congress on Evolutionary Computation. 2005, 2848−2855

[10] Kanet J J, Li X . A weighted modified due date rule for sequencing to minimize weighted tardiness. Journal of Scheduling, 2004, 7( 4): 261–276

[11] Jayamohan M S, Rajendran C . Development and analysis of cost-based dispatching rules for job shop scheduling. European Journal of Operational Research, 2004, 157( 2): 307–321

[12] Doh H H, Yu J M, Kim J S, Lee D H, Nam S H . A priority scheduling approach for flexible job shops with multiple process plans. International Journal of Production Research, 2013, 51( 12): 3748–3764

[13] Zhang H, Roy U . A semantics-based dispatching rule selection approach for job shop scheduling. Journal of Intelligent Manufacturing, 2019, 30( 7): 2759–2779

[14] Nguyen S, Zhang M, Johnston M, Tan K C. Evolving reusable operation-based due-date assignment models for job shop scheduling with genetic programming. In: Proceedings of the 15th European Conference on Genetic Programming. 2012, 121−133

[15] Nguyen S, Zhang M, Johnston M, Tan K C. A coevolution genetic programming method to evolve scheduling policies for dynamic multi-objective job shop scheduling problems. In: Proceedings of 2012 IEEE Congress on Evolutionary Computation. 2012, 1−8

[16] Li X, Olafsson S . Discovering dispatching rules using data mining. Journal of Scheduling, 2005, 8( 6): 515–527

[17] Yuan Y, Xu H . Flexible job shop scheduling using hybrid differential evolution algorithms. Computers & Industrial Engineering, 2013, 65( 2): 246–260

[18] Wang L, Luo C, Cai J . A variable interval rescheduling strategy for dynamic flexible job shop scheduling problem by improved genetic algorithm. Journal of Advanced Transportation, 2017, 2017: 1527858

[19] Gu X L, Huang M, Liang X . A discrete particle swarm optimization algorithm with adaptive inertia weight for solving multiobjective flexible job-shop scheduling problem. IEEE Access, 2020, 8: 33125–33136

[20] Huang R H, Yang C L, Cheng W C . Flexible job shop scheduling with due window—a two-pheromone ant colony approach. International Journal of Production Economics, 2013, 141( 2): 685–697

[21] Rossi A . Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships. International Journal of Production Economics, 2014, 153: 253–267

[22] Shiue Y R, Lee K C, Su C T . Real-time scheduling for a smart factory using a reinforcement learning approach. Computers & Industrial Engineering, 2018, 125: 604–614

[23] Waschneck B, Reichstaller A, Belzner L, Altenmüller T, Bauernhansl T, Knapp A, Kyek A . Optimization of global production scheduling with deep reinforcement learning. Procedia CIRP, 2018, 72: 1264–1269

[24] Luo S . Dynamic scheduling for flexible job shop with new job insertions by deep reinforcement learning. Applied Soft Computing, 2020, 91: 106208

[25] Lang S, Behrendt F, Lanzerath N, Reggelin T, Müller M. Integration of deep reinforcement learning and discrete-event simulation for real-time scheduling of a flexible job shop production. In: Proceedings of 2020 Winter Simulation Conference (WSC). 2020, 3057−3068

[26] He J, Li J. Deep reinforcement learning based on graph neural network for flexible job shop scheduling problem with lot streaming. In: Proceedings of the 20th International Conference on Advanced Intelligent Computing Technology and Applications. 2024, 85−95

[27] Park J, Chun J, Kim S H, Kim Y, Park J . Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. International Journal of Production Research, 2021, 59( 11): 3360–3377

[28] Wang R, Wang G, Sun J, Deng F, Chen J . Flexible job shop scheduling via dual attention network-based reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 2024, 35( 3): 3091–3102

[29] Wang X, Zhang L, Lin T, Zhao C, Wang K, Chen Z . Solving job scheduling problems in a resource preemption environment with multi-agent reinforcement learning. Robotics and Computer-Integrated Manufacturing, 2022, 77: 102324

[30] Liu R, Piplani R, Toro C . A deep multi-agent reinforcement learning approach to solve dynamic job shop scheduling problem. Computers & Operations Research, 2023, 159: 106294

[31] Si J, Li X, Gao L, Li P . An efficient and adaptive design of reinforcement learning environment to solve job shop scheduling problem with soft actor-critic algorithm. International Journal of Production Research, 2024, 62( 23): 8260–8275

[32] Jing X, Yao X, Liu M, Zhou J . Multi-agent reinforcement learning based on graph convolutional network for flexible job shop scheduling. Journal of Intelligent Manufacturing, 2024, 35( 1): 75–93

[33] Zhang W, Zhao F, Li Y, Du C, Feng X, Mei X . A novel collaborative agent reinforcement learning framework based on an attention mechanism and disjunctive graph embedding for flexible job shop scheduling problem. Journal of Manufacturing Systems, 2024, 74: 329–345

[34] Peng S, Xiong G, Yang J, Shen Z, Tamir T S, Tao Z, Han Y, Wang F Y . Multi-agent reinforcement learning for extended flexible job shop scheduling. Machines, 2024, 12( 1): 8

[35] Gu W, Liu S, Guo Z, Yuan M, Pei F . Dynamic scheduling mechanism for intelligent workshop with deep reinforcement learning method based on multi-agent system architecture. Computers & Industrial Engineering, 2024, 191: 110155

[36] Thomas P S, Brunskill E. Policy gradient methods for reinforcement learning with function approximation and action-dependent baselines. 2017, arXiv preprint arXiv: 1706.06643

[37] Haarnoja T, Zhou A, Hartikainen K, Tucker G, Ha S, Tan J, Kumar V, Zhu H, Gupta A, Abbeel P, Levine S. Soft actor-critic algorithms and applications. 2018, arXiv preprint arXiv: 1812.05905

[38] Weaver L, Tao N. The optimal reward baseline for gradient-based reinforcement learning. In: Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence. 2001, 538−545

[39] Foerster J N, Farquhar G, Afouras T, Nardelli N, Whiteson S. Counterfactual multi-agent policy gradients. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 2018, 363

[40] Hu S, Shen L, Zhang Y, Tao D. Learning multi-agent communication from graph modeling perspective. In: Proceedings of the 12th International Conference on Learning Representations. 2024

[41] Song S, Lin Y, Han S, Yao C, Wu H, Wang S, Lv K. CoDe: communication delay-tolerant multi-agent collaboration via dual alignment of intent and timeliness. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2025, 23304−23312

[42] Han S, Dastani M, Wang S . Sparse communication in multi-agent deep reinforcement learning. Neurocomputing, 2025, 625: 129344

[43] Na H, Seo Y, Moon I C. Efficient episodic memory utilization of cooperative multi-agent reinforcement learning. 2024, arXiv preprint arXiv: 2403.01112

[44] Ba Y, Liu X, Chen X, Wang H, Xu Y, Li K, Zhang S. Cautiously-optimistic knowledge sharing for cooperative multi-agent reinforcement learning. In: Proceedings of the 38th AAAI Conference on Artificial Intelligence. 2024, 1929

[45] Liu Y, Wang W, Hu Y, Hao J, Chen X, Gao Y. Multi-agent game abstraction via graph attention neural network. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2020, 7211−7218

[46] Sunehag P, Lever G, Gruslys A, Czarnecki W M, Zambaldi V, Jaderberg M, Lanctot M, Sonnerat N, Leibo J Z, Tuyls K, Graepel T. Value-decomposition networks for cooperative multi-agent learning. 2017, arXiv preprint arXiv: 1706.05296

RIGHTS & PERMISSIONS

Higher Education Press