Automated project scheduling in real-world test laboratories

Abstract

Complex project scheduling problems arise in many different settings and the quality of a schedule typically has a tremendous impact on the efficiency, timeliness, and cost of a project. However, creating good schedules manually is expensive and error-prone, which is why a lot of research has been done on automating this process. Due to the multitude of different problem settings, each with their own unique set of requirements and features which require specialized solution approaches, manual scheduling is still widespread in many areas. One such area is that of industrial test laboratories, where products need to be tested and certified according to a wide range of specifications and international norms.In this thesis, we introduce a new and complex project scheduling problem that is designed to model the requirements of industrial test laboratories. It features heterogeneous resources with different capabilities as well as a unique grouping aspect, which serves to improve the flexibility of the schedules and reduce unnecessary overheads. We provide a formal definition of this prob- lem, as well as a set of benchmark instances of varying sizes, both real-world instances taken directly from the laboratory of our industrial partner and randomly generated ones using a new and configurable instance generator. For this problem, as well as a subproblem that is relevant in practice, we develop new and innovative solution approaches. We propose a set of neigh- borhood structures that cover different aspects of the problems and together serve as the basis for several state-of-the-art search heuristics. Our exten- sive empirical evaluation shows that simulated annealing is very successful in finding good solutions for this problem and outperforms exact and hybrid methods on larger instances.In addition, we develop different problem-independent hyper-heuristic algorithms, which are capable of automatically adapting to new instances and even completely unseen problem domains. They achieved a good performance on several well-known NP-hard optimization problems, in particular our hyper-heuristics based on reinforcement learning. We also provide a comprehensive set of low-level heuristics for the test laboratory scheduling problem which allows it to be solved with our hyper-heuristics and we were able to show the effectiveness and generality of this approach. Finally, this thesis also describes the deployment of our algorithms at the laboratory of our industrial partner, where they are successfully used in practice for scheduling lab operations. For many other problems studied in the literature, adopting the theoretical methods and results into real-world practice has proved difficult and often unsuccessful. We describe the challenges we encountered in this process, as well as the lessons learned and recommendations for future deployments.