Tuesday, 15:45 - 16:10 h, Room: H 3003A


Alexander Schnell
The impact of the predefined search space on recent exact algorithms for the RCPSP

Coauthor: Richard F. Hartl


The problem of assigning starting times to a number of jobs subject to resource and precedence constraints is called the resource-constrained project scheduling problem (RCPSP). This presentation deals with exact algorithms for the standard version of the RCPSP assuming a single mode, non-preemption and renewable resources. Recent exact algorithms for this problem combine a branch and bound-based optimization search with principles from constraint programming, boolean satisfiability solving and mixed-integer programming for the branching and the fathoming of the search space. In our presentation, we analyze and enhance two recent exact algorithms by a parallel solving procedure. The latter consists of running the exact algorithm in parallel on an instance with different variable domains which are determined through a preprocessing step based on activity lists. Our results on instances with 60, 90 and 120 jobs show that the efficiency of the exact algorithms strongly varies depending on the predefined search space. Moreover, when employing the best found search space (which is not the smallest), we can improve two recent exact algorithms from the literature.


Talk 2 of the contributed session Tue.3.H 3003A
"Constraint programming methodology" [...]
Cluster 5
"Constraint programming" [...]


  payday loans online. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.