Complex real-world scheduling problems often include multiple conflicting objectives. Decision makers (DMs) can express their preferences over those objectives in different ways, including as sets of weights which are used in a linear combination of objective values. However, finding good sets of weights that result in solutions with desirable qualities is challenging and currently involves a lot of trial and error. We propose a general method to explain objectives' values under a given set of weights using Shapley regression values. We demonstrate this approach on the Test Laboratory Scheduling Problem (TLSP), for which we propose a multi-objective solution algorithm and show that suggestions for weight adjustments based on the introduced explanations are successful in guiding decision makers towards solutions that match their expectations. This method is included in the TLSP MO-Explorer, a new decision support system that enables the exploration and analysis of high-dimensional Pareto fronts.

The area of project scheduling problems has seen a tremendous amount of different problem variations. Traditionally, each problem variant requires custom solution approaches in order to produce high-quality solutions. Developing and tuning these methods is an expensive process that may have to be repeated as soon as the requirements or problem structures change. On the other hand, research into hyper-heuristics has produced general heuristic problem-solving techniques that were developed to achieve good results on multiple diverse problem domains. They work with a set of comparatively simple low-level heuristics and dynamically adapt themselves to each new problem variant. In this paper, we investigate hyper-heuristic approaches for a real-world industrial test laboratory scheduling problem and develop a new problem domain for the HyFlex hyper-heuristic framework. We propose a diverse portfolio of low-level heuristics that can be dynamically selected during the search process by hyper-heuristics to solve the problem. We evaluate and compare the performance of several problem-independent hyper-heuristics on this domain and show that they are able to match, and sometimes even exceed, the performance of state-of-the-art solution techniques that were developed and tuned specifically for this problem.

Automated scheduling solutions are tremendously important for the efficient operation of industrial laboratories. The Test Laboratory Scheduling Problem (TLSP) is an extension of the well-known Resource Constrained Project Scheduling Problem (RCPSP) and captures the specific requirements of such laboratories. In addition to several new scheduling constraints, it features a grouping phase, where the jobs to be scheduled are assembled from smaller units. In this work, we introduce an innovative scheduling system that allows the efficient and flexible generation of schedules for TLSP. It features a new Constraint Programming model that covers both the grouping and the scheduling aspect, as well as a hybrid Very Large Neighborhood Search that internally uses the CP model. Our experimental results on generated and real-world benchmark instances show that good results can be obtained even compared to settings which have a good grouping already provided, including several new best known solutions for these instances. Our algorithms for TLSP have been successfully implemented in a real-world industrial test laboratory. We provide a detailed description of the deployed system as well as additional useful soft constraints supported by the solvers and general lessons learned. This includes a discussion of the choice of soft constraint weights, with an analysis on the impact and relation of different objectives to each other. Our experiments show that some soft constraints complement each other well, while others require explicit trade-offs via their relative weights.

In this paper, we propose a new hyper-heuristic approach that uses reinforcement learning to automatically learn the selection of low-level heuristics across a wide range of problem domains. We provide a detailed analysis and evaluation of the algorithm components, including different ways to represent the hyper-heuristic state space and reset strategies to avoid unpromising areas of the solution space. Our methods have been evaluated using HyFlex, a well-known benchmarking framework for cross-domain hyper-heuristics, and compared with state-of-the-art approaches. The experimental evaluation shows that our reinforcement-learning based approach produces results that are competitive with the state-of-the-art, including the top participants of the Cross Domain Hyper-heuristic Search Competition 2011.

The Test Laboratory Scheduling Problem (TLSP) and its subproblem TLSP-S are real-world industrial scheduling problems that are extensions of the Resource-Constrained Project Scheduling Problem (RCPSP). Besides several additional constraints, TLSP includes a grouping phase where the jobs to be scheduled have to be assembled from smaller tasks and derive their properties from this grouping. For TLSP-S such a grouping is already part of the input. In this work, we show how TLSP-S can be solved by Answer-set Programming extended with ideas from other constraint solving paradigms. We propose a novel and efficient encoding and apply an answer-set solver for constraint logic programs called clingcon. Additionally, we utilize our encoding in a Very Large Neighborhood Search framework and compare our methods with the state of the art approaches. Our approach provides new upper bounds and optimality proofs for several existing benchmark instances in the literature.