Beyond Contention: Extending Texture-Based Scheduling Heuristics

In order to apply texture measurement based heuristic commitment techniques beyond the unary capacity resource constraints of job shop scheduling, we extend the contention texture measurement to a measure of the probability that a constraint will be broken. We define three methods for the estimation of this probability and show that they perform as well or better than existing heuristics on job shop scheduling problems. Empirical insight into the performance is provided and we sketch how we have extended probability-based heuristics to more complicated scheduling constraints. the “probability of breakage” of a constraint will allow us to directly compare the criticality of different types of constraints. We present three new techniques for estimating the probability of breakage of the resource constraint in job shop scheduling and compare the performance of heuristics based on these estimations against earlier texture-based and non-texture-based heuristics for scheduling. We also describe how our estimation techniques can be extended to more complicated scheduling domains.

Authors

• J. Christopher Beck University of Toronto
• Edward M. Sitarski Mark S. Fox

Keywords

No keywords are indexed for this paper.