zbMATH — the first resource for mathematics

Max energy filtering algorithm for discrete cumulative resources. (English) Zbl 1241.90125
van Hoeve, Willem-Jan (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 6th international conference, CPAIOR 2009, Pittsburgh, PA, USA, May 27–31, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-01928-9/pbk). Lecture Notes in Computer Science 5547, 294-308 (2009).
Summary: In scheduling using constraint programming we usually reason only about possible start times and end times of activities and remove those which are recognized as unfeasible. However often in practice there are more variables in play: variable durations of activities and variable resource capacity requirements. This paper presents a new algorithm for filtering maximum durations and maximum capacity requirements for discrete cumulative resources. It is also able to handle optional interval variables introduced in IBM ILOG CP Optimizer 2.0. Time complexity of the algorithm is \({\mathcal O}(n \log n)\). The algorithm is based on never published algorithm by Wim Nuijten and a on slightly modified e-feasibility checking algorithm by Armin Wolf and Gunnar Schrader. The later algorithm is also described in the paper.
For the entire collection see [Zbl 1163.68006].

90C27 Combinatorial optimization
90B35 Deterministic scheduling theory in operations research
PDF BibTeX Cite
Full Text: DOI