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

Autor:	Ondřej Čepek, Roman Barták, Petr Vilím
Rok vydání:	2005
Předmět:	Computational Theory and Mathematics Unary operation Application areas Artificial Intelligence Resource constraints Constraint programming Discrete Mathematics and Combinatorics Data structure Time complexity Algorithm Software Mathematics Scheduling (computing)
Zdroj:	Constraints. 10:403-425
ISSN:	1572-9354 1383-7133
DOI:	10.1007/s10601-005-2814-0
Popis:	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-first/not-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 ?-?-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-first/not-last.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::c4826ccf61df2610dcb36e4b55ccb243 https://doi.org/10.1007/s10601-005-2814-0 Zobrazit plný text záznamu Full text from SpringerLink