Solving large scale industrial production scheduling problems with complex constraints: an overview of the state-of-the-art

Production scheduling is challenging and the body of literature addressing various variants of the problem is large. It can roughly be divided into two streams: The first stream addresses and generalizes established scheduling problems, being general in the sense that they are not only applicable in a particular industry. The second stream works on less generic scheduling approaches for real industry cases by enriching standard models with all the required realistic aspects, such as process overlapping or sequence dependent setup times. Furthermore, different approaches have different limitations in terms of the problem size that they can tackle. The rise of Industry 4.0 has lead to a significant increase in data collection activities and the gathered information is used to build larger and more complex models. Industrial use cases may consist of several thousand operations on a large variety of machines, while classical benchmark instances tend to range up to only a few hundred of operations. It is therefore necessary to identify and highlight approaches, that can meet the challenges of scheduling in the era of Industry 4.0 and are suitable to tackle large scale problems. In this work, we conduct a structured literature review on scheduling problems incorporating several real world aspects among a broad range of use cases. Based on the identified publications we find that advanced solution approaches for large scale scheduling problems usually belong to one out of three categories, namely metaheuristic methods, constraint programming and machine learning. Our review shows that comparably few contributions tackling (very) large scale problems exist, emphasizing the need for additional research in this field. We identify promising approaches for further research, such as powerful metaheuristics combining concepts of tabu search and genetic algorithms. We further discuss the possibility to enhance solution methods by integrating constraint programming concepts and investigating problem decomposition.