In this paper, we propose exact and heuristic solution approaches based on dynamic programming for an open lot streaming problem. We also present the first application of Lagrangian relaxation to compute strong lower bounds to such a problem. The application concerns the minimization of the total flow time for the discrete version of a single-job lot streaming problem from the literature in a two-machine flow shop with attached setup times. Computational results on benchmark instances illustrate the effectiveness of the proposed approaches and give evidence of the strength of the Lagrangian relaxation lower bounds.

Dynamic programming algorithms and Lagrangian lower bounds for a discrete lot streaming problem in a two-machine flow shop / Alfieri, Arianna; Zhou, Shuyu; Scatamacchia, Rosario; van de Velde, Steef L. - In: 4OR. - ISSN 1619-4500. - STAMPA. - 19:(2021), pp. 265-288. [10.1007/s10288-020-00449-8]

Dynamic programming algorithms and Lagrangian lower bounds for a discrete lot streaming problem in a two-machine flow shop

Alfieri, Arianna;Scatamacchia, Rosario;
2021

Abstract

In this paper, we propose exact and heuristic solution approaches based on dynamic programming for an open lot streaming problem. We also present the first application of Lagrangian relaxation to compute strong lower bounds to such a problem. The application concerns the minimization of the total flow time for the discrete version of a single-job lot streaming problem from the literature in a two-machine flow shop with attached setup times. Computational results on benchmark instances illustrate the effectiveness of the proposed approaches and give evidence of the strength of the Lagrangian relaxation lower bounds.
2021
4OR
File in questo prodotto:
File Dimensione Formato  
Alfieri2020_Article_DynamicProgrammingAlgorithmsAn(1).pdf

accesso riservato

Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 386.48 kB
Formato Adobe PDF
386.48 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

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: https://hdl.handle.net/11583/2839505