zbMATH — the first resource for mathematics

Precedence constraint posting for cyclic scheduling problems. (English) Zbl 1302.90087
Achterberg, Tobias (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 8th international conference, CPAIOR 2011, Berlin, Germany, May 23–27, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-21310-6/pbk). Lecture Notes in Computer Science 6697, 137-153 (2011).
Summary: Resource constrained cyclic scheduling problems consist in planning the execution over limited resources of a set of activities, to be indefinitely repeated. In such a context, the iteration period (i.e. the difference between the completion time of consecutive iterations) naturally replaces the makespan as a quality measure; exploiting inter-iteration overlapping is the primary method to obtain high quality schedules. Classical approaches for cyclic scheduling rely on the fact that, by fixing the iteration period, the problem admits an integer linear model. The optimal solution is then usually obtained iteratively, via linear or binary search on the possible iteration period values. In this paper we follow an alternative approach and provide a port of the key Precedence Constraint Posting ideas in a cyclic scheduling context; the value of the iteration period is not a-priori fixed, but results from conflict resolution decisions. A heuristic search method based on Iterative Flattening is used as a practical demonstrator; this was tested over instances from an industrial problem obtaining encouraging results.
For the entire collection see [Zbl 1214.68003].

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
Full Text: DOI