On linear lower bounds for the resource constrained project scheduling problem. (Q1399576): Difference between revisions

In the paper lower bounds for the resource-constrained project scheduling problem minimizing the makespan are proposed. These bounds depend linearly on the processing times of the activities. After showing that several bounds from the literature belong to this class of bounds, two new approaches are presented. The first is based on a general linear programming scheme, the second uses the concept of redundant resources. Computational results are presented for the PSPLIB benchmark instances of \textit{R. Kolisch, A. Sprecher} and \textit{A. Drexl} [Manage. Sci. 41, 1693--1703 (1995; Zbl 0870.90070)] showing the effectiveness of the proposed procedures.