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 language | English |
---|---|
Pages (from-to) | 265-288 |
Number of pages | 24 |
Journal | 4OR |
Volume | 19 |
Issue number | 2 |
DOIs | |
Publication status | Published - 10 Jul 2020 |
Bibliographical note
Funding Information:We wish to thank the two anonymous referees and the associate editor for their suggestions and comments that allowed us to improve the manuscript. This work has been partially supported by “Ministero dell’Istruzione, dell’Università e della Ricerca” Award “TESUN-83486178370409 finanziamento dipartimenti di eccellenza CAP. 1694 TIT. 232 ART. 6”.
Publisher Copyright:
© 2020, Springer-Verlag GmbH Germany, part of Springer Nature.