

![0_image_0.png](0_image_0.png)

time that does not violate any constraint regarding the current partial schedule. In the case of backtracking they apply dominance rules to fathom search space. As far as we can determine this exact approach outperforms other exact methods for Rcpsp/max on the CD benchmark set.

Franck et al. [15] compare different solution methods on a benchmark set UBO with instances ranging from 10 to 1000 activities. Their methods are a truncated branch-andbound algorithms, filter-beam search, heuristics with priority rules, genetic algorithms and tabu search. All methods share a preprocessing step to determining feasibility or infeasibility. The preprocessing step decomposes the precedence network into strongly connected components (SCCs) (which are denoted "cyclic structures" in [15]). The preprocessing then determines a solution or infeasibility for each SCC individually using constraint propagation and a destructive lower bound computation. Once a solution for all SCCs is determined a first solution can be deterministically generated for the original instance; otherwise infeasibility is proven.

Ballest´ın et al. [4] employ an evolutionary algorithm based on a serial generation scheme with unscheduling step. Their crossover operator is based on so called *conglomerates*, i.e. set of cycle structures and other activities which cannot move freely inside a schedule, it tries to keep the "good" conglomerates of the parents to their children. This is the best published local search method so far on the testsets UBO (up to instances with 100 activties) and CD.

Cesta at al. [9] propose a two layered heuristic that is based on a temporal precedence network and extension of this network by new temporal precedence in order to resolve minimal conflict sets. For guidance, constraint propagation algorithms are applied on the network. Their method is competitive on the benchmark set SM.

Oddi and Rasconi [23] apply a generic iterative search consisting of of a relaxation and flatting step based on temporal precedences which are used for resolving resource conflicts. In the first step some of the temporal precedences are removed from the problem and then in the second others added if a resource conflict exists. Their methods is evaluate on instances with 200 activities from the benchmark set UBO.

A special case of Rcpsp/max is the well-studied Resource-constrained Project Scheduling Problem (Rcpsp) where the precedence constraints Si + dij ≤ Sj express that the