## S sTx n Srx n c

Get Instant Access

A feasible solution to problem (MP) consists in a schedule-assignment pair (S,x), where i is a feasible full assignment (i.e., a solution to the mode-assignment problem) and S is a feasible schedule with respect to x (i.e., a feasible solution to the respective single-mode project scheduling problem). An optimal solution is a feasible solution (S, x) with minimum objective function value f(S).

From Theorem 1.12 it immediately follows that finding a feasible solution (S,x) is NP-hard. In addition, Kolisch (1995), Sect. 2.3, and Schwindt (19986) have shown by transformations from Knapsack and Precedence-Constrained Knapsack, respectively, that the problems of testing whether there is a resource-feasible or a time-feasible full mode assignment x are already NP-complete. Consequently, the resource relaxation of a multi-mode resource allocation problem is NP-hard. Hence, to obtain a problem that can be solved efficiently, the mode assignment constraints (5.7) have to be relaxed as well. The mode relaxation for an assignment x then reads

Obviously, the single-mode resource-constrained project scheduling problem (P(x)) is a relaxation of all mode relaxations (P(x')) belonging to extensions x' of x, i.e.,

This observation is the starting point for a relaxation-based enumeration scheme for solving multi-mode problem (MP). Let p be some relation in node set V, and let St(p,x) '■= {S £ St(x) \ Sj > Si + Pi{x) for all (i,j) £ p) be the relation polytope belonging to p and assignment x. The algorithm starts with the empty assignment x = 0. For the corresponding single-mode problem (P(x)), schedules are enumerated as minimal points of appropriate (unions of) relation polytopes St(p,x), see Algorithms 3.1 and 3.3. Each time a schedule S feasible with respect to x has been obtained, the execution mode of some activity i with em ■—imi = 0 is fixed such that the resulting assignment x' is still feasible (if there is no mode m-j £ Mi such that x' is feasible, we perform backtracking). Then, the time-feasibility of S with respect to the new assignment x' is restored. Due to <S(x') C S(x), S may be not resource-feasible with respect to x'. In that case, the enumeration of schedules is resumed by extending the current relation p until a schedule S' which is feasible with respect to x' has been found. These steps are reiterated until a feasible full assignment x has been reached or there is no feasible extension of the current assignment x'.