Modeling and Solving the Generalized Test Laboratory Scheduling Problem

Abstract

The Test Laboratory Scheduling Problem (TLSP) is an NP-hard scheduling problem based on the real-world scheduling requirements of an industrial test laboratory. TLSP requires the solver to find a grouping of tasks into jobs, and to schedule those jobs, assigning resources of different types (employees, workbenches, and equipment) and optimizing different soft constraints. Over time, new real-world scheduling requirements have emerged that necessitate a more flexible description of resources. To deal with such situations, in this paper, we propose Generalized TLSP (G-TLSP), a new problem extension of TLSP which unifies different resource types. To solve G-TLSP, we propose a new Constraint Programming (CP) model and solve instances with exact CP solvers as well as with a Very Large Neighborhood Search (VLNS) algorithm. Our approaches are evaluated on existing instances as well as two new real-world instances. We achieve competitive performance with existing specialized solvers on converted TLSP instances and find high-quality solutions for the new real-world instances.