Constraint Logic Programming for Real-World Test Laboratory Scheduling

Tobias Geibinger, Florian Mischek, Nysret MusliuAAAI 2021 · DOI

Introduction

In industrial test laboratories, scheduling represents a significant operational challenge. Managing hundreds of standardized tests (jobs) requires precise assignment to specific workbenches, qualified personnel, and specialized equipment, all while adhering to strict temporal windows. This challenge is formalized as the Test Laboratory Scheduling Problem (TLSP-S), an extension of the Resource-Constrained Project Scheduling Problem (RCPSP) that incorporates several real-world complexities.

The Complexity of TLSP-S

Unlike standard scheduling problems, TLSP-S involves "messy" constraints that complicate the search for optimal solutions:

  • Multi-mode execution: Jobs can be performed in various modes, each with distinct durations and resource requirements.
  • Linked jobs: Specific tasks must be executed by the same employee to ensure continuity and quality.
  • Heterogeneous resources: Resource allocation is restricted by specific qualifications and equipment compatibility.
  • Soft constraints: Objectives extend beyond simple completion, aiming to minimize tardiness, respect employee preferences, and limit the number of different employees assigned to a single project.

Previous methodologies, including Simulated Annealing and standard Constraint Programming (CP), often struggled to find optimal solutions for large-scale, complex instances of this problem.

Methodology: The CASP Approach

To address these challenges, researchers developed a high-performance scheduling system utilizing Constraint Answer-set Programming (CASP). This hybrid approach leverages the logical reasoning capabilities of Answer-set Programming (ASP) alongside the numerical efficiency of constraint solvers.

The CASP Advantage

Standard ASP excels at modeling discrete choices and "if-then" logic (e.g., assigning specific employees to tasks) but is less efficient with large numeric ranges like timestamps. Conversely, CP solvers handle timing well but can be cumbersome with complex logical dependencies. CASP bridges this gap by using ASP for logical structure and linear constraints for scheduling and timing.

Key Innovations

  1. The clingcon Solver: The system utilizes clingcon-5, which implements "lazy" constraint generation. This ensures that intensive mathematical calculations are only performed when the logical search requires them.
  2. Unary Resource Formulations: The study compared two methods for resource management. The Precedence formulation (determining the sequence of jobs) proved more robust for large instances than the Direct formulation (checking for overlapping time intervals).
  3. Hybrid VLNS: For the largest problem instances where solvers might time out, the CASP model was integrated into a Very Large Neighborhood Search (VLNS) framework. This "destroy and repair" method fixes a majority of the schedule and uses the CASP solver to optimally re-schedule a small subset of projects iteratively.

Experimental Results

The model was evaluated on 30 generated instances designed to mimic various laboratory scales and 3 real-world industrial instances.

Solver performance comparison: Penalty relative to best solution across different solvers. Multi-threaded clingcon (MT) demonstrates competitive performance against established solvers like Chuffed and CP Optimizer.

Key Findings

  • New Benchmarks: The CASP-based VLNS identified 12 new upper bounds, surpassing all previously recorded solutions for these instances.
  • Optimality Proofs: The system provided the first-ever optimality proofs for 5 instances in the literature, a feat unattainable by metaheuristic methods like Simulated Annealing.
  • Solver Performance: Multi-threaded clingcon outperformed established solvers like Chuffed and CP Optimizer in several scenarios, particularly in maintaining feasibility for large-scale problems.
VLNS performance comparison: Penalty relative to best solution for VLNS using clingcon vs Chuffed. The clingcon-based VLNS consistently achieves solutions closer to the best-known bounds.

Conclusion and Future Work

The research demonstrates that scheduling is as much a logic problem as it is a mathematical one. By using ASP to handle mode assignments and linked jobs, the search space for timing constraints becomes significantly more manageable.

Future work aims to expand the model to the broader TLSP, which includes the initial phase of grouping tasks into jobs. Additionally, the authors plan to explore "multi-shot" solving to preserve learned information between VLNS iterations, further enhancing solver efficiency.

Summary updated

BibTeX
@inproceedings{geibinger2021constraint,
  author = {Tobias Geibinger and Florian Mischek and Nysret Musliu},
  title = {{Constraint Logic Programming for Real-World Test Laboratory Scheduling}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i7.16789},
}
Figure