The minimum storage-time sequencing problem generalizes many well-known prob- lems 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 op- timization 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 Chvatal closure equals the convex hull of all the integer solutions of the problem.

Detti, P., & Pacciarelli, D. (2001). A branch and bound algorithm for the Minimum Storage-Time Sequencing problem. NAVAL RESEARCH LOGISTICS, 48(4), 313-331 [10.1002/nav.11].

A branch and bound algorithm for the Minimum Storage-Time Sequencing problem

DETTI, PAOLO;
2001

Abstract

The minimum storage-time sequencing problem generalizes many well-known prob- lems 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 op- timization 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 Chvatal closure equals the convex hull of all the integer solutions of the problem.
File in questo prodotto:
File Dimensione Formato  
MSTS.pdf

non disponibili

Tipologia: Abstract
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 201.3 kB
Formato Adobe PDF
201.3 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11365/21954
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo