Slack-based heuristics for constraint satisfaction scheduling

Abstract

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