A (not so) brief overview of propagation (and explanations) for the cumulative constraint

Not-first/not-last detection is the pendant of edge-finding in constraint-based disjunctive and cumulative scheduling. Both methods provide strong pruning algorithms in constraint programming. This paper shows that the not-first/not-last detection algorithm presented by Nuijten that runs in time }{\backslashcal O}(n^3k)}is incorrect and incomplete, where n is the number of tasks and k is the number of different capacity requirements of these tasks. A new correct and complete detection algorithm for cumulative scheduling is then presented which runs in }{\backslashcal O}(n^3\backslashlog n)}.

Energetic reasoning is a strong filtering technique for the Cumulative constraint. However, the best algorithms process }}O(n^2)}}time intervals to perform the satisfiability check which makes it too costly to use in practice. We present how to apply the energetic reasoning by processing only }}O(n \backslashlog n)}}intervals. We show how to compute the energy in an interval in }}O(\backslashlog n)}}time. This allows us to propose a }}O(n \backslashlog ^2 n)}}checker and a filtering algorithm for the energetic reasoning with }}O(n^2 \backslashlog n)}}average time complexity. Experiments show that these two algorithms outperform their state of the art counterparts.

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.

The introduction of edge-finding techniques was a significant development in constraint-based scheduling. Today, edge finders are still the state of the art in the disjunctive case and a technique of interest in cumulative scheduling. This paper reconsiders edge-finding algorithms for cumulative scheduling and shows that Nuijten’s edge finder, and its derivatives, are incomplete because they use an invalid dominance rule. We then present a correct cumulative edge finder running in time O(n2k), where n is the number of tasks and k the number of different capacity requirements of the tasks. The new algorithm is organized in two phases and first uses dynamic programming to precompute the innermost maximization in the edge-finder specification. The paper also proposes the first extended edge-finding algorithms that run in time O(n2k), improving the running time of available algorithms. Finally, the paper discusses how to speed up the algorithm in practice and how the first phase can be used to improve algorithms based on energetic reasoning.