Tight LP bounds for resource constrained project scheduling
type: Item
instance of: scholarly article
title: Tight LP bounds for resource constrained project scheduling
zbMATH Open document ID: 1072.90012
author: Philippe Baptiste
author: Sophie Demassey
published in: OR Spectrum
publication date: 2004-09-22T00:00:00Z
review text: In the paper destructive lower bound procedures for the resource-constrained project scheduling problem (RCPSP) are described, which are based on constrained propagation and linear programming. After generating redundant disjunctive resources by solving a mixed integer program, constraint propagation is applied in order to derive new constraints or to detect infeasibility. Afterwards, a linear programming lower bound is calculated, which strengthens the lower bound from \textit{P. Brucker} and \textit{S. Knust} [Eur. J. Oper. Res. 127, No. 2, 355--362 (2000; Zbl 0990.90055)] by additional cuts. Computational results are presented for the well-known RCPSP-instances from the library PSPLIB [cf. \textit{R. Kolisch} and \textit{A. Sprecher}, Eur. J. Oper. Res. 96, No. 1, 205--216 (1997; Zbl 0947.90587)].
reviewed by: Sigrid Knust
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 2101663
zbMATH Keywords: resource-constrained project scheduling
zbMATH Keywords: lower bounds
zbMATH Keywords: constraint propagation
zbMATH Keywords: linear programming
describes a project that uses: PSPLIB
describes a project that uses: BL data set
MaRDI profile type: Publication
full work available at URL: s00291-003-0155-1
OpenAlex ID: W2090923074
DOI: 10.1007/S00291-003-0155-1
description: scientific article; zbMATH DE number 2101663