Search papers, labs, and topics across Lattice.
This paper introduces MIStar, a DRL-based improvement search framework for the flexible job-shop scheduling problem (FJSP) that addresses limitations of constructive methods. MIStar uses a heterogeneous disjunctive graph to represent scheduling solutions and a memory-enhanced heterogeneous graph neural network (MHGNN) to extract features, leveraging historical trajectories to improve policy learning. Experiments on synthetic and benchmark datasets demonstrate that MIStar outperforms both traditional improvement heuristics and state-of-the-art DRL-based constructive methods for FJSP.
By explicitly modeling operation sequences on machines with a novel heterogeneous disjunctive graph, MIStar significantly boosts the performance of improvement-based methods for flexible job-shop scheduling.
The rise of smart manufacturing under Industry 4.0 introduces mass customization and dynamic production, demanding more advanced and flexible scheduling techniques. The flexible job-shop scheduling problem (FJSP) has attracted significant attention due to its complex constraints and strong alignment with real-world production scenarios. Current deep reinforcement learning (DRL)-based approaches to FJSP predominantly employ constructive methods. While effective, they often fall short of reaching (near-)optimal solutions. In contrast, improvement-based methods iteratively explore the neighborhood of initial solutions and are more effective in approaching optimality. However, the flexible machine allocation in FJSP poses significant challenges to the application of this framework, including accurate state representation, effective policy learning, and efficient search strategies. To address these challenges, this paper proposes a Memory-enhanced Improvement Search framework with heterogeneous graph representation--MIStar. It employs a novel heterogeneous disjunctive graph that explicitly models the operation sequences on machines to accurately represent scheduling solutions. Moreover, a memoryenhanced heterogeneous graph neural network (MHGNN) is designed for feature extraction, leveraging historical trajectories to enhance the decision-making capability of the policy network. Finally, a parallel greedy search strategy is adopted to explore the solution space, enabling superior solutions with fewer iterations. Extensive experiments on synthetic data and public benchmarks demonstrate that MIStar significantly outperforms both traditional handcrafted improvement heuristics and state-of-the-art DRL-based constructive methods.
