Scheduling Policies for the Stochastic Resource Leveling Problem

Abstract

When uncertainties come into play, the leveled baseline schedule obtained by solving the deterministic resource leveling problem can hardly be executed as planned and this schedule may even become infeasible. In addition, traditional stochastic methods may also suffer from not being able to produce satisfactorily leveled schedules. Therefore, there is a pressing need for new procedures that are capable of dealing with resource leveling subject to uncertainties. The writers study the resource leveling problem subject to activity durations uncertainty where the usage of renewable resources needs to be leveled over time. Two heuristics for producing scheduling policies are presented with the objective of minimizing the expected sum of the weighted coefficient of variation of the resource usage. The two heuristics represent two different ways of tackling the stochastic resource leveling problem. The first heuristic, a modified version of the Burgess and Killebrew leveling procedure, obtains a scheduling policy by solving the deterministic equivalent of the stochastic resource leveling problem. The second heuristic, a simulation-based tabu search procedure, directly works with the stochastic resource leveling problem. Computational experiments are conducted on the well-known project scheduling problem library (PSPLIB) J90 instances.