Abstract
The job shop scheduling problem is an NP-hard combinatorial optimization problem relevant to manufacturing and timetabling. Traditional approaches use priority dispatching rules based on simple heuristics. Recent work has attempted to replace these with deep learning models, particularly graph neural networks (GNNs), that learn to assign priorities from data. However, training such models requires customizing numerous factors: graph representation, node features, action space, and reward functions. The lack of modular libraries for experimentation makes this research time-consuming. This work introduces JobShopLib, a modular library that allows customizing these factors and creating new components with its reinforcement learning environment. We trained several dispatchers through imitation learning to demonstrate the environment’s utility. One model outperformed various graph-based dispatchers using only individual operation features, highlighting the importance of feature customization. Our GNN model achieved near state-of-the-art results on large-scale problems. These results suggest significant room for improvement in developing such models. JobShopLib provides the necessary tools for future experimentation.
Type
With my bachelor’s thesis, I have explored the field of deep reinforcement learning and graph neural networks. Inspired by AlphaZero’s success in combinatorial games like Go and chess, I was interested in using RL to solve combinatorial optimisation problems. I found the job shop scheduling problem (JSSP) the perfect one. It had received significantly less attention than others, facilitating more impactful and original contributions. For instance, in tackling the JSSP, I realised a lack of tools for efficient experimentation. This led me to create JobShopLib, an open-source library that enables researchers to create, visualise, and solve the JSSP using customisable RL environments. Although this work extended beyond the typical scope of a bachelor’s thesis, I was committed to pursuing a challenging and original project, even if it meant a longer completion time.
High level overview of JobShopLib’s RL environment design.