Result: Extension of O(n log n) filtering algorithms for the unary resource constraint to optional activities

Title:
Extension of O(n log n) filtering algorithms for the unary resource constraint to optional activities
Authors:
VILIM, Petr, BARTAK, Roman, CEPEK, Ondrej
Source:
Principles and practice of constraint programming (CP 2004)Constraints (Dordrecht). 10(4):403-425
Publisher Information:
Heidelberg: Springer, 2005.
Publication Year:
2005
Physical Description:
print, 16 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Arbre graphe, Tree(graph), Arbol grafo, Ordonnancement, Scheduling, Reglamento, Programmation logique avec contrainte, Constraint logic programming, Programación lógica con restricción, Structure arborescente, Tree structure, Estructura arborescente, Structure donnée, Data structure, Estructura datos, Alternative, Contrainte globale, Contrainte ressource unaire, Contrainte ressource, Resource constraint, Constreñimiento recurso, alternatives, global constraints, scheduling, unary resource
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Faculty of Mathematics and Physics, Charles University, Malostranskè namesti 2/25, Praha, Czech Republic
ISSN:
1383-7133
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=17266049
Rights:
Copyright 2006 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.17266049
Database:
PASCAL Archive

Further Information

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 θ-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-first/not-last.