Multi-Assignment Scheduler: A New Behavioral Cloning Method for the Job-Shop Scheduling Problem

Recent advances in applying deep learning methods to address complex scheduling problems have highlighted their potential in learning dispatching rules. However, most studies have predominantly focused on deep reinforcement learning (DRL). This paper introduces a novel methodology aimed at learning dispatching policies for the job-shop scheduling problem (JSSP) by employing behavioral cloning and graph neural networks. By leveraging optimal solutions for the training phase, our approach sidesteps the need for exhaustive exploration of the solution space, thereby enhancing performance compared to DRL methods proposed in the literature. Additionally, we introduce a novel modelling of the JSSP with the aim of improving efficiency in terms of solving an instance in real time. This involves two key aspects: firstly, the creation of an action space that allows our policy to assign multiple operations to machines within a single action, substantially reducing the frequency of model usage; and secondly, the definition of a state space that only includes significant operations. We evaluated our methodology using a widely recognized open JSSP benchmark, comparing it against four state-of-the-art DRL methods and an enhanced metaheuristic approach, demonstrating superior performance.