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

Arianna Alfieri*, Shuyu Zhou, Rosario Scatamacchia, Steef L. van de Velde

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)265-288
Number of pages24
Journal4OR
Volume19
Issue number2
DOIs
Publication statusPublished - 10 Jul 2020

Fingerprint

Dive into the research topics of 'Dynamic programming algorithms and Lagrangian lower bounds for a discrete lot streaming problem in a two-machine flow shop'. Together they form a unique fingerprint.

Cite this