2002 | OriginalPaper | Buchkapitel
A New Multi-resource cumulatives Constraint with Negative Heights
verfasst von : Nicolas Beldiceanu, Mats Carlsson
Erschienen in: Principles and Practice of Constraint Programming - CP 2002
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper presents a new cumulatives constraint, which generalizes the original cumulative constraint in different ways. The two most important aspects consist in permitting multiple cumulative resources as well as negative heights for the resource consumption of the tasks. This allows modeling in an easy way workload covering, producer-consumer, and scheduling problems. The introduction of negative heights has forced us to come up with new filtering algorithms and to revisit existing ones. The first filtering algorithm is derived from an idea called sweep, which is extensively used in computational geometry; the second algorithm is based on a combination of sweep and constructive disjunction; while the last is a generalization of task intervals to this new context. A real-life crew scheduling problem originally motivated this constraint which was implemented within the SICStus finite domain solver and evaluated against different problem patterns.