Hierarchical Multi-Agent Deep Reinforcement Learning with Guided Search for U-Shaped Seru Production Scheduling

Abstract

This paper investigates an integrated scheduling problem in U-shaped seru production systems under a static and deterministic order environment. The problem jointly determines order-to-seru assignment, intra-seru order sequencing, and multi-skilled worker allocation, with the objective of minimizing the makespan. Compared with conventional parallel-machine scheduling, U-shaped seru scheduling involves stronger decision coupling because workload distribution, learning effects, sequence-dependent setup times, and worker configuration jointly determine seru completion times. To characterize these features, a mixed-integer nonlinear programming model is formulated by incorporating the DeJong learning effect, sequence-dependent setup times, worker allocation constraints, and sequencing feasibility requirements. The scheduling problem is then reformulated as a single-step combinatorial Markov decision process. Based on this formulation, a hierarchical Multi-Agent Deep Deterministic Policy Gradient algorithm with Guided Search, termed MADDPG-GuidedSearch, is proposed. The framework consists of a global coordination agent for order assignment and multiple seru execution agents for intra-seru sequencing and worker allocation. Graph attention-based state encoding, centralized training with decentralized execution, Gumbel-Softmax relaxation, decoding repair, local search, and multi-candidate Guided Search are integrated to improve feasibility, search robustness, and solution quality. Computational experiments show that MADDPG-GuidedSearch-50 achieves a slightly lower average makespan than a strong genetic algorithm baseline while requiring less online solution time after offline training. Sensitivity and ablation analyses further indicate that Guided Search and Repair/Local Search are the main contributors to performance improvement.