On The Effectiveness Of Bottleneck Information For Solving Job Shop Scheduling Problems Using Deep Reinforcement Learning

Abstract

Job shop scheduling problems (JSSPs) have been the subject of intense studies for decades because they are often at the core of significant industrial planning challenges and have a high optimization potential. As a result, the scientific community has developed clever heuristics to approximate optimal solutions. A prominent example is the shifting bottleneck heuristic, which iteratively identifies bottlenecks in the current schedule and uses this information to apply targeted optimization steps. In recent years, deep reinforcement learning (DRL) has gained increasing attention for solving scheduling problems in job shops and beyond. One design decision when applying DRL to JSSPs is the observation, i.e., the descriptive representation of the current problem and solution state. Interestingly, DRL solutions do not make use of explicit notions of bottlenecks that have been developed in the past when designing the observation. In this paper, we investigate ways to leverage a definition of bottlenecks inspired by the shifting bottleneck heuristic for JSSPs with DRL to increase the effectiveness and efficiency of model training. To this end, we train two different DRL base models with and without bottleneck features. However, our results indicate that previously developed bottleneck definitions neither increase training efficiency nor final model performance.