Premium
A branch and bound algorithm for the minimum storage‐time sequencing problem
Author(s) -
Detti P.,
Pacciarelli D.
Publication year - 2001
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.11
Subject(s) - linear programming relaxation , branch and bound , branch and cut , relaxation (psychology) , upper and lower bounds , lagrangian relaxation , combinatorial optimization , mathematics , closure (psychology) , mathematical optimization , branch and price , integer programming , bundle , linear programming , integer (computer science) , combinatorics , algorithm , computer science , psychology , social psychology , mathematical analysis , materials science , economics , market economy , composite material , programming language
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. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 313–331, 2001