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