Resource Constrained Project Scheduling with Variable Intensity Activities

This page will contain material related to the above problem.

Problem Statement

An instance of the problem is given by a finite set N of activities, a finite set R of continuously divisible renewable resources and a directed acyclic graph D = (N,A) representing precedence constraints among the activities. The time horizon is divided into T periods, indexed as t = 1,..., T. For each activity i a release time e(i) and a deadline d(i) specify an interval of time periods {e(i),...,d(i)} in which the activity must entirely be executed. In each time period t in {e(i),...,d(i)} at most a(i) <= 1 fraction of activity i may be completed. Activity i requires a total of r(i,k) units of resource k. If the (chosen) intensity of activity i is x(i,t) in time period t, where 0 <= x(i,t) <= a(i) and sum( x(i,t) : t=1,...,T ) = 1 hold, then it requires r(i,k) x(i,t) units of resource k in period t. Each resource k has an internal capacity of b(k,t) units that can be used free of charge and it has an additional external capacity of b(k,t) units at the expense of c(k,t) for each external unit used.

The scheduling problem consists of determining for each activity i an intensity x(i,t) in each time period t in {e(i),...,d(i)} such that 0 <= x(i,t) <= a(i), sum( x(i,t) : t=1,...,T ) = 1, the precedence constraints among the activities are fulfilled, the resource demand does not exceed the resource availability b(k,t) + b(k,t) in any time period t and the total cost of using external capacity is minimized.

Computational Results

You can download my results on R. De Boer's instances here.

You can also access my results for the makespan minimization problem on 30 job and 60 job PSPLIB instances. Be aware that we have solved these instances by relaxing the assumption that the resource usage is constant during the execution of each activity.
 
Back to my home page.
Last modified: January 8, 2004.