A branch and bound algorithm for the minimum storage-time sequencing problem

A branch and bound algorithm for the minimum storage-time sequencing problem

0.00 Avg rating0 Votes
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: ,
Keywords: programming: branch and bound
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.