Optimizing constraint programming for real world scheduling of test Laboratories

Abstract

The Test Laboratory Scheduling Problem (TLSP) is a recently proposed complex scheduling problem based on the real-world scheduling requirements of an industrial test laboratory. TLSP is related to the well-known Resource Constrained Project Scheduling Problem (RCPSP). One extension in TLSP compared to the RCPSP is the division of resources into three categories: employees, workbenches, and equipment, each with different properties and constraints. Over time, new real-world scheduling requirements put this taxonomy into question. The first part of this Thesis addresses this by proposing a new problem variant, TLSP with Generalized Resources (TLSP-GR), which unifies these resource types into a single concept. This immediately solves some of the new scheduling requirements and provides an elegant basis for implementing others. To solve TLSP-GR, a new Constraint Programming (CP) model is proposed. Through careful generalization and optimization of the new model, its performance on TLSP instances is still competitive with the existing state-of-the-art model for TLSP. The second part of this Thesis concerns extending the CP-SAT solver from Google's OR-Tools suite to improve its performance on complex scheduling problems like TLSP. While CP-SAT is known for its excellent performance, routinely winning gold medals at the MiniZinc Challenge, its performance lagged behind the academic Chuffed solver on TLSP instances. In an attempt to close this gap, CP-SAT is extended to support priority search and random variable selection, and hot-start support is added to its MiniZinc backend. While the improvements from priority search can surprisingly be replicated through a search strategy not using this feature, the overall extensions to the solver make it a viable option for TLSP, matching state-of-the-art results when included in an existing VLNS algorithm for TLSP. Using the methods from this Thesis, 4 new optimality results are achieved for TLSP. In addition, new state-of-the-art penalties are achieved for 17 out of 33 test instances.