Slack-Based Heuristics for Constraint Satisfaction Scheduling

Abstract

In this paper, we define and empirically evaluate new heuristics for solving the job shop scheduling problem with non-relaxable time windows. The hypothesis underlying our approach is that by approaching the problem as one of establishing sequencing constraints between pairs of operations requiring the same resource (as opposed to a problem of assigning start times to each operation) and by exploiting previously developed analysis techniques for limiting search through the space of possible sequencing decisions, simple, localized look-ahead techniques can yield problem solving performance comparable to currently dominating techniques that rely on more sophisticated analysis of resource contention. We define a series of attention focusing heuristics based on simple analysis of the temporal flexibility associated with different sequencing decisions, and a similarly motivated heuristic for determining how to sequence a given operation pair. Performance results are reported on a suite of benchmark problems previously investigated by two advanced approaches, and our simplified look-ahead analysis techniques are shown to provide comparable problem solving leverage at reduced computational cost.