Scheduling Alternative Activities

AAAI 1999

TL;DR

This paper introduces a novel way to represent and schedule "alternative activities" in complex planning problems, where certain tasks might not need to be performed. By assigning a "probability of existence" (PEX) to activities and extending constraint propagation and heuristic search techniques, they significantly improve scheduling efficiency and solution quality, especially when dealing with a wide range of uncertainty.

What Problem Does This Paper Address?

Real-world scheduling problems often involve choices. For instance, a product might have multiple ways to be manufactured (alternative process plans), or a task could be performed by different machines (alternative resources). Traditional scheduling methods assume every defined activity must be executed. This paper tackles the challenge of modeling and efficiently solving scheduling problems where some activities are optional. This is crucial for making scheduling systems more flexible and realistic, allowing them to reason about uncertainty and make smarter decisions about which tasks are truly necessary to achieve a goal.

Methods

The core innovation is the introduction of a Probability of Existence (PEX) for each activity. This PEX value, ranging from 0 to 1, represents the estimated likelihood that an activity will be part of the final schedule.

Key techniques include:

  • PEX Representation: Activities are assigned a PEX variable. A PEX of 1 means the activity must exist, 0 means it won't, and values in between represent uncertainty.
  • XorNodes: These are new temporal network nodes that explicitly model exclusive-or relationships between alternative activities or paths.
  • PEX Propagation: Algorithms are developed to maintain consistency among PEX values. If one alternative path is chosen (PEX set to 1), others might have their PEX reduced to 0. This propagation is crucial for pruning the search space.
  • Modified Temporal Propagation: Standard temporal propagation is adapted to account for PEX values, ensuring that the timing constraints remain valid even when activities might not exist.
  • Extended Heuristics: Three existing heuristics (SumHeight, CBASlack, LJRand) are modified to incorporate PEX information.
  • SumHeightPEX: Modifies activity demand calculations by multiplying them with the activity's PEX, effectively scaling down the "criticality" of uncertain activities.
  • CBASlackPEX: Adapts slack calculations to consider PEX values, influencing sequencing decisions.
  • LJRandPEX: Modifies activity selection to prioritize those with a PEX greater than 0.
  • PEX-Edge-Finding: A novel propagation technique that extends existing edge-finding algorithms to work with activities that have a PEX less than 1. This allows for more powerful constraint deduction.

Datasets

The paper describes two experimental setups:

  • Experiment 1: Four problem sets were generated with varying maximum numbers of alternatives per process plan (1, 3, 5, and 7). These were based on a 10x10 job shop problem, transformed to include alternative paths.
  • Experiment 2: Transformations of the problems from Experiment 1 were created by adding alternative resources to each activity, with durations multiplied by a random factor between 1.0 and 1.5.

No new benchmarks were explicitly introduced, but the experimental setups were designed to specifically test the proposed PEX techniques under varying degrees of uncertainty.

Key Insights and Ideas

  • PEX is a powerful abstraction: Representing uncertainty via a "probability of existence" is a natural and effective way to model optional activities in scheduling.
  • Propagation is key: Maintaining PEX consistency through specialized propagation algorithms is essential for significantly reducing the search space and improving efficiency.
  • Texture-based heuristics shine: Heuristics that analyze the "texture" of the problem (like SumHeight) benefit most from PEX information because they can directly leverage the nuanced uncertainty represented by PEX values.
  • PEX-edge-finding is beneficial: Extending edge-finding propagation to handle PEX values leads to better performance, especially for heuristics that can utilize the richer information.
  • Trade-offs exist: While PEX representation and exploitation lead to higher quality solutions and better commitments, they can also lead to poorer scaling behavior on very large problems due to the increased complexity of representing multiple alternatives.

Key Results

  • Improved Performance: Algorithms incorporating PEX, particularly SumHeightPEX and CBASlackPEX, significantly outperform their non-PEX counterparts.
  • PEX-Edge-Finding Advantage: Using PEX-edge-finding consistently led to fewer timed-out problems and, in most cases, reduced mean CPU times. SumHeightPropPEX and LJRandPropPEX showed significant improvements in timing out fewer problems.
  • Heuristic Ranking: In Experiment 1, SumHeightPEX and CBASlackPEX significantly outperformed LJRandPEX. In Experiment 2, SumHeightPEX was significantly better than LJRandPEX.
  • Search Statistics: Algorithms with PEX and PEX-edge-finding made fewer backtracks and heuristic commitments.
  • Non-uniformity Matters: The performance differences between heuristics were more pronounced when PEX values were more non-uniform, highlighting SumHeightPEX's ability to exploit this.

Limitations and Future Work

  • Scaling Behavior: The authors acknowledge that representing multiple alternatives can lead to poor scaling behavior, a trade-off that needs further investigation and optimization.
  • CBASlackPEX Issues: The paper hypothesizes that CBASlackPEX might perform poorly due to its heuristic focusing on non-critical activity pairs when PEX values are low. Further research is needed to confirm and address this.
  • Future Research: The authors suggest characterizing the trade-off between representation complexity and scaling behavior, and optimizing for this. They also propose investigating applications of this PEX reasoning mechanism to other areas of artificial intelligence beyond scheduling.

Summary updated

BibTeX
@inproceedings{1999scheduling,
  title = {{Scheduling Alternative Activities}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure