SODA

A Scalable Sweep Algorithm for the "cumulative" Constraint

Letort, Arnaud and Beldiceanu, Nicolas and Carlsson, Mats (2012) A Scalable Sweep Algorithm for the "cumulative" Constraint. In: CP.

Full text not available from this repository.

Official URL: http://dx.doi.org/10.1007/978-3-642-33558-7_33

Abstract

This paper presents a sweep based algorithm for the cumulative constraint, which can operate in filtering mode as well as in greedy assignment mode. Given n tasks, this algorithm has a worst-case time complexity of O(n 2). In practice, we use a variant with better average-case complexity but worst-case complexity of O(n 2 log n), which goes down to O(n log n) when all tasks have unit duration, i.e. in the bin-packing case. Despite its worst-case time complexity, this algorithm scales well in practice, even when a significant number of tasks can be scheduled in parallel. It handles up to 1 million tasks in one single cumulative constraint in both Choco and SICStus.

Item Type:Conference or Workshop Item (Paper)
ID Code:5352
Deposited By:Mats Carlsson
Deposited On:17 Jan 2013 11:45
Last Modified:17 Jan 2013 11:45

Repository Staff Only: item control page