Extension of O(n log n) Filtering Algorithms for the Unary Resource Constraint to Optional Activities

摘要

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 and not-firstot-last are the most popular filtering algorithms for unary resources. In this paper we introduce new O(n log n) versions of these two filtering algorithms and one more O(n log n) filtering algorithm called detectable precedences. These algorithms use a special data structures Θ-tree and Θ-A-tree. These data structures are especially designed for "what-if" reasoning about a set of activities so we also propose to use them 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-firstot-last.