SODA

A New multi-resource cumulatives constraint with negative heights

Beldiceanu, Nicolas and Carlsson, Mats (2002) A New multi-resource cumulatives constraint with negative heights. In: CP'2002, 8th International Conference, Principles and Practice of Constraint Programming, 9-13 Sept 2002, Ithaca, New York, USA.

Full text not available from this repository.

Official URL: http://www.springerlink.com/content/yblp5037rxkqn2...

Abstract

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 new scheduling and planning problems. The introduction of negative heights has forced us to come up with new propagation algorithms and to revisit existing ones. The first propagation 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 timetabling problem originally motivated this constraint which was implemented within the SICStus finite domain solver and evaluated against different problem patterns.

Item Type:Conference or Workshop Item (Paper)
Additional Information:DOI: 10.1007/3-540-46135-3_5. Preprint available as SICS Technical Report T2001-11.
ID Code:3403
Deposited By:Vicki Carleson
Deposited On:07 Aug 2008
Last Modified:18 Nov 2009 16:22

Repository Staff Only: item control page