zbMATH — the first resource for mathematics

Unary resource constraint with optional activities. (English) Zbl 1152.68590
Wallace, Mark (ed.), Principles and practice of constraint programming – CP 2004. 10th international conference, CP 2004, Toronto, Canada, September 27–October 1, 2004. Proceedings. Berlin: Springer (ISBN 978-3-540-23241-4/pbk). Lecture Notes in Computer Science 3258, 62-76 (2004).
Summary: Scheduling is one of the most successful application areas of constraint programming mainly thanks to special global constraints designed to model resource restrictions. Among these global constraints, edge-finding filtering algorithm for unary resources is one of the most popular techniques. In this paper we propose a new \(O(n \log n)\) version of the edge-finding algorithm that uses a special data structure called \(\Theta\)-\(\Lambda \)-tree. This data structure is especially designed for “what-if” reasoning about a set of activities so we also propose to use it for handling so called optional activities, i.e., activities which may or may not appear on the resource. In particular, we propose new \(O(n \log n)\) variants of filtering algorithms which are able to handle optional activities: overload checking, detectable precedences and not-first/not-last.
For the entire collection see [Zbl 1139.68008].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68P05 Data structures
90B35 Deterministic scheduling theory in operations research
Full Text: DOI