Experimental Results on the Application of Satisfiability Algorithms to Scheduling Problems

James M. Crawford, Andrew B. BakerAAAI 1994

Introduction

In the early 1990s, the artificial intelligence community focused heavily on "critically constrained" random 3SAT problems as the gold standard for benchmarking satisfiability solvers. While these problems are mathematically challenging, their relevance to real-world applications remained a subject of debate. Crawford and Baker (1994) addressed this gap by evaluating major SAT algorithms on job-shop scheduling problems, revealing that the structural properties of real-world tasks fundamentally change the performance landscape of search algorithms.

The Challenge of Scheduling as SAT

The core difficulty in applying SAT solvers to scheduling lies in the translation of temporal constraints into boolean logic. Traditional scheduling involves operations with start times, durations, and resource requirements. Crawford and Baker utilized a "SAT Encoding" that prioritizes "ordering" variables—determining whether operation $i$ precedes operation $j$. This approach significantly prunes the search space compared to mapping every possible start time to a variable, yet it still results in massive, structured theories that differ significantly from random 3SAT benchmarks.

Algorithmic Approaches

The study compared three distinct methodologies:

  1. TABLEAU: A systematic solver based on the Davis-Putnam (DPLL) procedure. It employs unit propagation to prune the search tree through forward checking.
  2. GSAT (specifically WSAT): A stochastic local search algorithm that performs "hill-climbing" by flipping variable assignments to maximize satisfied clauses.
  3. ISAMP (Iterative Sampling): A minimalist approach that assigns variables randomly and uses unit propagation. If a contradiction is reached, the algorithm immediately restarts from scratch.

Experimental Setup

The algorithms were tested on Sadeh’s job-shop scheduling benchmark, consisting of 60 problems. Each problem involves 50 operations across 10 jobs competing for 5 resources. The dataset varies by the "degree of constraint" (wide, narrow, or tight deadlines) and the number of "bottlenecks" (zero, one, or two), mimicking industrial environments.

Results and Discussion

The experimental results were surprising: the simplest algorithm, ISAMP, outperformed the more sophisticated systematic and local search methods.

The Dominance of Iterative Sampling

ISAMP achieved a 100% success rate across all problem classes, often finding solutions in under a minute. Its success stems from the "under-constrained" nature of these scheduling problems. While the search space is vast, solutions are relatively abundant; the primary obstacle is avoiding "dead zones" created by early mistakes in the search tree.

Performance of the ISAMP algorithm on scheduling benchmarks.

In contrast, TABLEAU struggled with consistency. While it was fast on many instances, it frequently became trapped in massive subtrees with no solutions due to a poor initial guess at the top of the search tree (which can be 70-80 levels deep). This led to significantly lower success rates in certain categories, such as the "n/1" (narrow deadline, one bottleneck) class.

Performance of the TABLEAU systematic solver, showing inconsistent success rates.

The Role of Forward Checking

GSAT initially performed poorly because it lacks the forward-checking capabilities of unit propagation. Without it, the local search often flips "control" variables (ordering) without realizing it has made thousands of "dependent" clauses (timing) impossible to satisfy. When the authors augmented the theory with pre-calculated unit propagation, GSAT's performance improved by an order of magnitude, highlighting the necessity of structural awareness in solvers.

Conclusion

The findings suggest that the "hardness" of random 3SAT is a poor proxy for the complexity of real-world scheduling. In structured, under-constrained domains, the ability to quickly recover from early search mistakes via restarts (as in ISAMP) is more valuable than exhaustive systematic exploration or pure local search. Future research should focus on developing solvers that operate within the "control space" of structured problems, potentially moving beyond pure propositional logic to more expressive constraint-satisfaction languages.

Summary updated

BibTeX
@inproceedings{crawford1994experimental,
  author = {James M. Crawford and Andrew B. Baker},
  title = {{Experimental Results on the Application of Satisfiability Algorithms to Scheduling Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure