On linear lower bounds for the resource constrained project scheduling problem

The aim of this paper is to propose efficient methods for solving the resource constrained project scheduling problem (RCPSP). These methods are based on makespan lower bounds, which linearly depend on the processing times of the activities. Linear lower bounds (LLB) can be obtained in different ways. The first application that we present is a general linear programming scheme for computing a makespan lower bound. The second application consists in associating redundant resources with LLB. Consequently we get new adjustments of release dates and tails of the project activities. These adjustments are tight for certain RCPSP instances, as shown by our computational results. (C) 2003 Published by Elsevier Science B.V.