second newest literal (in this case se ≤ 5) thus undoing the decisions sd ≤ 2 and sb ≤ 2 and their consequences. The newly added nogood unit propagates to force se ≥ 6 with explanation Jsb ≥ 2K ∧ Jsb ≤ 5K ∧ Jse ≥ 5K ∧ Jsc ≥ 3K ∧ Jsc ≤ 6K → Jse ≥ 6K, and the precedence constraint se − 3 ≤ sd forces sd ≥ 3 with explanation Jse ≥ 6K → Jsd ≥ 3K.

Search proceeds looking for a solution. ✷

## 3. Models For Rcpsp/Max

In this section a basic model for Rcpsp/max instance is presented at first, and then different possible model improvements which are mainly based on activities in disjunction.

An Rcpsp/max problem can be represented as follows: A set of activities V =
{1*, . . . , n*} is subjected to generalized precedences in *E ⊂ V*2 × Z between two activities, and scarce resources in R. The goal is to find a schedule S = (Si)i∈V that respects the precedence and resource constraints, and minimizes the project duration (makespan)
where Siis the *start time* of the activity i.

Each activity i has a finite processing time or *duration* pi and requires (non-negative)
rik units of resource k, k ∈ R for its execution where rik is the *resource requirement* or usage of activity i for resource k. A resource k ∈ R has a constant3*resource capacity* Rk over the planning period which cannot be exceeded at any point in time. The planning period is given by [0, tmax) where tmax is the maximal planning horizon.

Generalized precedences (i, j, dij ) ∈ E between the activities i and j are subjected to the constraint Si + dij ≤ Sj , i.e. it represents a *minimal time lag* (j must start at least dij time units after i starts) if dij ≥ 0 and a *maximal time lag* (i must start at most
−dij time units after the start of j) if dij < 0. Generalized precedences encode not only start-to-start relations between activities, but also start-to-end, end-to-start, and end-to-end by addition/ subtraction of i's or j's duration to dij . If a minimal time lag d
+
ij and a maximal time lag d
−
ji exist for an activity j concerning to i then the start time Sj is restricted to [Si + d
+
ij ..Si − d
−
ji]. In the case of d
+
ij = −d
−
ji the activity j must start exactly d
+
ij time units after i.

For the remainder of this section let an Rcpsp/max instance be given with activities V = {1, 2*, . . . , n*}, generalized precedences E, resources R, and a planning period [0, tmax). Then the basic model can be stated as the following Zinc [20] model.

| %---------------------------------------------------------------------% % Parameters int: t max; % The planning horizon set of int: R; % The set of resources set of int: V; % The set of activities set of int: Idx; % The index set of precedences array [R] of int: rcap; % The resource capacities array [V] of int: p; % The activities durations   |
|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
