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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Modeling and Solving the Generalized Test Laboratory Scheduling Problem

  • Philipp Danzinger,
  • Tobias Geibinger,
  • Florian Mischek,
  • Nysret Musliu

摘要

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.