A new relaxation of the Resource-Constrained Project Scheduling Problem

International audienceIn this paper we propose to partially relax the resource constraints in order to get lower bounds of the RCPSP. To this aim, by analogy with tactical project planning, we consider the resource constraints on aggregated periods while the precedence constraints still hold. Hence, according to period duration, the resource constraints will be more or less strong. An iterative bounding scheme is presented and some results are given. 1 A time/resource relaxation of the Resource-Constrained Project Scheduling Problem Given a set of activities V = {0,. .. , n + 1} linked by precedence constraints E, and such that each activity i ∈ V requires an amount b i,k ≥ 0 on each resource k of a set of resources R, the Resource-Constrained Project Scheduling Problem (RCPSP) can be defined as the problem of finding a start time S i for each activity i ∈ V while satisfying the precedence constraints E and not exceeding the resource availabilities B k , k ∈ R, such that the makespan, given by the difference between the start time of the dummy end activity n + 1 and the dummy start activity 0, is minimized. We consider a relaxation of the RPCP (P ∆) for any ∆ ∈ R * +. (P ∆) min S n+1 − S 0 (1) S j ≥ S i + p i (i, j) ∈ E (2) i∈V p i,t b i,k ≤ ∆.B k t ∈ T, k ∈ R (3) p i,t = |[t∆, (t + 1)∆] ∩ [S i , S i + p i ]| i, ∈ A, t ∈ T (4) S i ≥ 0 i ∈ A (5) where T = {0,. .. , |T | − 1} is a set of periods t of length ∆ and p i,t denote the length of the time interval under which activity i is executed in period t. We assume that (|T | − 1)∆ is an upper bound on the makespan. To obtain a correct formulation for the RCPSP, one should take ∆ = 1 and enforce integrity on the start times, i.e. replace constraints (5) by S i ≥ 0 and integer , ∀i ∈ A. Obviously (P ∆) is a relaxation of the RCPSP (even for ∆ = 1) as it can be seen that any schedule S feasible for the RCPSP, is also feasible for (P ∆), for any ∆ ∈ R * +. Furthermore, in the figure below with three activities having requirements (3,4,3) on a single resource of availability 4 a makespan of 6 is obtained thanks to non integer start times in the optimal solution of (P 2). Note that besides being a valid relaxation of the RCPSP, the problem (P ∆) can be used in a project planning context, when resource consumption have to be aggregated over several periods in an upper decision level while precedence constraints between activities hav