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

doi: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

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

^*Corresponding author for this work

Department of Technology and Operations Management

Research output: Contribution to journal › Article › Academic › peer-review

4 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 language	English
Pages (from-to)	265-288
Number of pages	24
Journal	4OR
Volume	19
Issue number	2
DOIs	https://doi.org/10.1007/s10288-020-00449-8
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.

Access to Document

10.1007/s10288-020-00449-8

Cite this

@article{a677afe8aee84ddd9da3b3079f8e49d4,

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

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.",

author = "Arianna Alfieri and Shuyu Zhou and Rosario Scatamacchia and van de Velde, {Steef L.}",

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{\textquoteright}Istruzione, dell{\textquoteright}Universit{\`a} e della Ricerca” Award “TESUN-83486178370409 finanziamento dipartimenti di eccellenza CAP. 1694 TIT. 232 ART. 6”. Publisher Copyright: {\textcopyright} 2020, Springer-Verlag GmbH Germany, part of Springer Nature.",

year = "2020",

month = jul,

day = "10",

doi = "10.1007/s10288-020-00449-8",

language = "English",

volume = "19",

pages = "265--288",

journal = "4OR",

issn = "1619-4500",

publisher = "Springer-Verlag",

number = "2",

}

TY - JOUR

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

AU - Alfieri, Arianna

AU - Zhou, Shuyu

AU - Scatamacchia, Rosario

AU - van de Velde, Steef L.

N1 - 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.

PY - 2020/7/10

Y1 - 2020/7/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85087672740&partnerID=8YFLogxK

U2 - 10.1007/s10288-020-00449-8

DO - 10.1007/s10288-020-00449-8

M3 - Article

AN - SCOPUS:85087672740

SN - 1619-4500

VL - 19

SP - 265

EP - 288

JO - 4OR

JF - 4OR

IS - 2

ER -

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

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this