Propagation techniques of resource constraint for cumulative scheduling

Author: 

Roger Kameugne

School: 

University of Yaounde 1, Faculty of Sciences, Department of Mathematics.

Supervisors: 

Prof. Laure Pauline Fotso

Abstract: 

A scheduling problem consists in planning the execution of a set of tasks under resource and temporal constraints. It is an NP-hard combinatorial problem even if only one resource is considered. In this thesis, we use the constraint programming approach to solve the non-preemptive cumulative scheduling problem. We focus particularly on resource constraint propagation.

We describe and compare theoretically and experimentally new propagation algorithms for resource constraint in cumulative scheduling. We focus on edge-finding, extended edge-finding and not-first/not-last algorithms. Each of these algorithms has different filtering power. It is while they are combined in the global \textit{cumulative} constraint to increase their filtering power and for a maximum propagation. Each of this rules determines the position of the task $i$ relatively to a set of tasks $\Omega$ all sharing the same resource. We propose for each of these rules a new filtering algorithm. The complexity of some algorithms does not strictly dominate the best existing one, but the algorithm remains useful in practice.

For the edge-finding, we propose a sound $\mathcal{O}(n^2)$ algorithm based on the notions of maximum density and minimum slack. The algorithm doesn't necessary perform the maximum adjustment at the first run, but improves at subsequent iterations. In practice, it is three time faster than the best known standard algorithm of the literature.

We prove that the extended edge-finding of Mercier and Van Hentenryck of complexity $\mathcal{O}(n^2k)$ is incorrect. We then propose a sound $\mathcal{O}(n^2)$ extended edge-finding algorithm similar to our edge-finding and based on the notion of minimum slack. The conjunction of our new extended edge-finding algorithm with the edge-finding reduces the running time of a few instances and when the dynamic branching scheme is used, we have in addition, a reduction of the number of nodes on highly cumulative instances. We prove that the edge-finding and the extended edge-finding are not dominated by the timetable edge finding. This result contradicts the claim of Vil\'{i}m that the conjunction of edge-finding and extended edge-finding is dominated by the timetable edge finding.

We end with the proposition of two filtering algorithms for the not-first/not-last rule. The first one is complete and runs in $\mathcal{O}(n^2|H|\log n)$ where $|H|$ is the number of different earliest completion times of tasks. This algorithm thus improves the complexity of the best known complete not-first/not-last algorithm, $\mathcal{O}(n^3\log n)$, since $|H|\leq n$. The second filtering is sound and run in $\mathcal{O}(n^2\log n)$. This algorithm reaches the same fix point as complete filtering not-first/not-last algorithms and is faster than all of them in practice.

\textbf{Key Words:} Cumulative scheduling, constraint programming, constraint propagation, global constraint, edge-finding, extended edge-finding, not-first/not-last, timetable edge finding, RCPSP.

Graduated: 

Tuesday, September 30, 2014

PDF of thesis: