A generalised makespan estimation for shop scheduling problems, using visual data and a convolutional neural network. Issue 6 (3rd June 2019) - De Jong, Arent W.; Rubrico, Jose I. U.; Adachi, Masaru; Nakamura, Takayuki; Ota, Jun
ABSTRACT: In Shop Scheduling problems, minimising total processing time (makespan) by means of heuristic methods is one of the main goals for throughput optimisation. Furthermore, reliably estimating makespan is critical for new order acceptance and for heuristic method selection. However, heuristic methods solutions either come without estimates or with very slow ones. Current estimation approaches are limited to either the number of heuristic methods accounted for, or to specific Shop Scheduling subproblems. They are especially limited in generalising over shop layout configurations and limited to non-visual data input. In order to overcome these two hurdles, a convolutional neural network algorithm for quick and accurate makespan regression is proposed, applicable to a wide variety of Shop Scheduling Problems. This algorithm allows for an information-rich, visual representation of the problem, that generalises over shop layout configuration. This has not been tried by prior studies, and the authors argue that this is a main contribution of this work. Results are compared to prior approaches in terms of the R 2 value. It is shown that, without compromising on estimation performance, the proposed algorithm improves upon prior research by allowing for visual input and for a wider variety of problems in terms of Shop Scheduling layout.