Article ID: | iaor20021717 |
Country: | United States |
Volume: | 48 |
Issue: | 4 |
Start Page Number: | 313 |
End Page Number: | 331 |
Publication Date: | Jun 2001 |
Journal: | Naval Research Logistics |
Authors: | Pacciarelli D., Detti P. |
Keywords: | programming: branch and bound |
The minimum storage-time sequencing problem generalizes many well-known problems in combinatorial optimization, such as the directed linear arrangement and the problem of minimizing the weighted sum of completion times, subject to precedence constraints on a single processor. In this paper we propose a new lower bound, based on a Lagrangian relaxation, which can be computed very efficiently. To improve upon this lower bound, we employ a bundle optimization algorithm. We also show that the best bound obtainable by this approach equals the one obtainable from the linear relaxation computed on a formulation whose first Chvátal closure equals the convex hull of all the integer solutions of the problem.