Reinforcement Learning Guided Neural Deconstruction Search for Flexible Job Scheduling

Davide Zago, André Hottung, Fynn Martin Gilbert, Rossella Cancelliere, Kevin Tierney

Abstract Learning-based approaches have made substantial progress on solving combinatorial optimization problems, increasingly rivaling classical operations research methods. In particular, improvement-based machine learning methods, which iteratively refine an existing solution, have achieved state-of-the-art results on routing problems such as the traveling salesperson problem and the vehicle routing problem. Despite this success, analogous learning-based improvement methods for scheduling remain largely unexplored. To close this gap, we introduce a learning-based improvement method for scheduling based on the neural deconstruction framework, which improves solutions by iteratively applying a learned deconstruction policy followed by a simple repair strategy. We apply our method to both the classical and flexible job-shop scheduling problems. Our experimental results demonstrate that our method is able to outperform existing end-to-end and learning-augmented approaches on various well-known benchmark instances from the operations research literature.