Constraint-Based Scheduling with Complex Setup Operations: An Iterative Two-Layer Approach

Adriana Pacheco, Cédric Pralet, Stéphanie Roussel

TL;DR

This paper introduces an iterative two-layer scheduling approach to tackle complex problems where tasks require intricate setup operations between them. By alternating between a high-level, simplified model and a detailed, fine-grained model, the method efficiently generates high-quality schedules for multi-robot missions, significantly outperforming traditional global models.

What Problem Does This Paper Address?

Many real-world scheduling problems involve resources that need to perform complex setup operations before executing subsequent tasks. Think of a robot needing to navigate a complex terrain to reach a new observation point, or data transfers between different computing cores that require intricate network coordination. These setup operations can be highly complex, involving interactions with other resources or tasks. Modeling these interactions directly in a single, large scheduling problem quickly becomes computationally intractable due to the combinatorial explosion of possibilities. The paper addresses this challenge by proposing a hierarchical approach that breaks down the problem into manageable layers, focusing on efficiency and practical applicability rather than absolute optimality.

Methods

The core of the paper's contribution is an iterative two-layer decision process.

  • Layer 1 (L1): Coarse-Grain Model. This layer works with a simplified model of setup operations, treating them as abstract, potentially parameterized, setup times. It generates a high-level schedule.
  • Layer 2 (L2): Fine-Grain Model. This layer takes the high-level schedule from L1 and refines it by detailing the complex setup operations. It uses a more accurate, fine-grained model, considering actual resource usage and potential interferences.

The key innovation is the iterative interaction between these layers. After L2 produces a detailed schedule, its findings (specifically, the actual durations of the detailed setup operations) are fed back to L1. L1 then updates its coarse-grain model of setup times based on this feedback, allowing it to generate a better high-level schedule in the next iteration. This process repeats until a time limit is reached. This iterative refinement allows L1 to learn a more accurate approximation of L2's behavior over time, leading to progressively better solutions. The approach is inspired by techniques like Benders decomposition but adapted for scenarios where L2 might be a black-box simulator.

Datasets

Not discussed in the paper. The authors generated instances for their multi-robot case study.

Key Insights and Ideas

  • Decomposition is Key: Directly modeling complex setup operations leads to intractable problem sizes. Hierarchical decomposition is a practical necessity.
  • Iterative Refinement for Learning: The iterative feedback loop between L1 and L2 allows the coarse-grained model (L1) to "learn" the implications of the fine-grained model (L2). This is crucial for improving schedule quality over time.
  • Flexibility in Setup Modeling: Unlike methods that rely on generating "cuts" (which must be valid), this approach allows L1 to use both lower and upper bounds on setup times, providing more flexibility for exploration.
  • Focus on Quality within Time Limits: The goal is not necessarily to find the absolute optimal solution but to achieve high-quality solutions within practical computation time constraints, which is often more valuable in real-world applications.

Key Results

The paper demonstrates the effectiveness of their approach on a multi-robot mission case study.

  • Significant Speedup: The two-layer approach achieved significantly better makespan results in much shorter computation times compared to a "Full Model" that attempted to solve the problem in a single, global step.
  • Scalability: For large instances where the Full Model failed to find any solution within 30 minutes, the two-layer approach provided good quality solutions in under 3 seconds.
  • Quality of Solutions: The makespan values obtained by the two-layer approach were often close to the lower bounds derived from Layer 1.
  • Convergence: Experiments showed that the makespans of both layers tended to converge quickly during the iterative process.

Limitations and Future Work

  • No Optimality Guarantee: The iterative process does not guarantee finding the globally optimal solution, as L1's approximation might not always be a lower bound.
  • Future Work:
    • Integrating task preconditions and effects (similar to HTN planning).
  • Developing strategies for step-by-step decomposition rather than a strict two-layer separation.
  • Exploring decomposition structures that can derive efficient cuts for Layer 1, potentially bridging towards Logic-Based Benders Decomposition.
  • Investigating more sophisticated update strategies for Layer 1 beyond simple reinforcement learning rates.

Summary updated

Abstract

In this paper, we consider scheduling problems involving resources that must perform complex setup operations between the tasks they realize. To deal with such problems, we introduce a simple yet efficient iterative two-layer decision process that alternates between the fast synthesis of high-level schedules based on a coarse-grain model of setup operations, and the production of detailed schedules based on a fine-grain model. Experiments realized on representative benchmarks of a multi-robot application show the efficiency of the approach.
BibTeX
@inproceedings{pacheco2019constraint,
  author = {Adriana Pacheco and Cédric Pralet and Stéphanie Roussel},
  title = {{Constraint-Based Scheduling with Complex Setup Operations: An Iterative Two-Layer Approach}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/161},
}
Figure