Beyond Contention: Extending Texture-Based Scheduling Heuristics

Abstract

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. Introduction Recently a number of researchers have examined extensions of constraint-directed scheduling techniques to realworld constraints (e.g., cumulative resources, alternative resources, sequence-dependent changeovers, inventory capacity) as found, for example, in the manufacturing and distribution industries (Saks, 1992; Nuijten, 1994; Le Pape, 1994; Brucker and Thiele, 1996; Caseau and Laburthe,...