cannot be interrupted), and finding a schedule that minimizes the project duration (also called *makespan*). This problem is denoted as P S|temp|Cmax by Brucker et al. [8] and m, 1|gpr|Cmax by Herroelen et al. [16]. Bartusch et al. [5] show that the decision wether an instance is feasible or not is already NP-hard.

The Rcpsp/max problem is widely studied and some of its applications can be found in Bartusch et al. [5]. A problem instance consists of a set of resources, a set of activities, and a set of generalized precedences between activities. Each resource is characterized by its discrete capacity, and each activity by its discrete processing time (duration) and its resource requirements. Generalized precedences express relations of start-to-start, start-to-end, end- to-start, and end-to-end times between pairs of activities. All these relations can be formulated as start-to-start times precedence. Those precedences have the form Si + dij ≤ Sj where Si and Sj are the start times of the activities i and j resp., and dij is a discrete distance between them. If dij is non-negative this imposes a minimal time lag, while if dij is negative this imposes a maximal time lag between start times.

Example 1. A simple example of an Rcpsp/max problem consists of the five activities [*a, b, c, d, e*] with their start times [sa, sb, sc, sd, se], their durations [2, 5, 3, 1, 2] and resource requirements on a single resource [3, 2, 1, 2, 2] and a resource capacity of 4.

Suppose we also have the generalized precedences sa + 2 ≤ sb (activity a ends before activity b starts), sb + 1 ≤ sc (activity b starts at least 1 time unit before activity c starts), sc − 6 ≤ sa (activity c can not start later than 6 time units after activity a starts), sd + 3 ≤ se (activity d starts at least 3 time units before activity e starts), and se − 3 ≤ sd (activity e can not start later than 3 time units after activity d starts). Note that the last two precedences express the relation sd + 3 = se (activity d starts exactly 3 time units before activity e).

Let the planning horizon, in which all activities must be completed be 8. Figure 1 illustrates the precedence graph between the five tasks and source at the left (time 0) and sink at the right (time 8), as well as a potential solution to this problem, where a rectangle for activity i has width equal to its duration and height equal to its resource requirements. ✷
To our knowledge the first exact method to tackle Rcpsp/max was proposed by Bartusch et al. [5]. They use a branch-and-bound algorithm to tackle the problem. Their branching is based on resolving (minimal) conflict sets2 by the addition of precedence constraints breaking these sets. Later other branch-and-bound methods were developed which are based on the same idea (e.g. De Reyck and Herreolen [10], Schwindt [29],
and Fest et al. [12]). The results from Schwindt are the best published one for an exact method on the testset Sm so far.

Dorndorf et al. [11] use a time-oriented branch-and-bound combined with constraint propagation for precedence and resource constraints. In every branch one unscheduled and "eligible" activity is selected and its start time is assigned to the earliest point in