Tight LP bounds for resource constrained project scheduling (Q1880319)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2101663
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Tight LP bounds for resource constrained project scheduling |
scientific article; zbMATH DE number 2101663 |
Statements
Tight LP bounds for resource constrained project scheduling (English)
0 references
22 September 2004
0 references
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)].
0 references
resource-constrained project scheduling
0 references
lower bounds
0 references
constraint propagation
0 references
linear programming
0 references
0.929631769657135
0 references
0.929631769657135
0 references
0.9132696390151978
0 references
0.8992071747779846
0 references
