Scheduling; Combinatorial Optimization; Instance Space Analysis; Hyper-heuristics; Reinforcement Learning
en
Abstract:
Optimization problems in real-life scenarios are often difficult to model and solve, as they have various different constraints and objectives coming from different sources, and these might require frequent changes and adaptations. This often leads to the requirement for highly customized solutions that are specifically made for a particular version of a problem. While such tailored solutions are important, e.g., to obtain proven optimal or bounded solutions, they can often not be applied to other problems or require extensive adaptation effort, which raises the need for general solution methods that can be applied to different problem variants or entirely different problems with minimum adaptation effort. This thesis contributes to the state of the art both regarding problem-specific methods and general methods for complex real-life problems from the application area of employee scheduling, a very challenging domain where the solutions have a huge impact on the lives and well-being of employees as well as the profits of companies. The contributions on three different real-life example problem domains include new formal problem definitions, analysis of problem characteristics and more realistic problem extensions, and exact solution approaches including novel modelling options as well as approaches using metaheuristics. They further include detailed analysis of available instances as well as the generation of new realistic benchmark instances, and the analysis of strengths and weaknesses of different solution approaches. On the side of general methods, the thesis provides the architecture of an interval-based framework that allows to model the three example problem domains, but also further problems, in a common modular framework. It uses this framework to introduce several new low-level heuristics, which are algorithmic building blocks, to be able to apply the general methodology of hyper-heuristics, which use these building blocks to create a solution method for an instance of a problem on the fly. With the new low-level heuristics in place, a range of state-of-the-art hyper-heuristics are evaluated on these domains, providing very good results while being generally applicable.Finally, the thesis introduces the new hyper-heuristic LAST-RL, which uses reinforcement learning based on a rich representation of the search state in combination with an exploration strategy based on Iterated Local Search, which performs very well both on an academic benchmark, outperforming previous approaches based on reinforcement learning, and on the three real-life domains, providing new best results for two of those domains, which shows the great potential of applying such general methods for complex real-life domains.
