Dynamic programming algorithms and Lagrangian lower bounds for a discrete lot streaming problem in a two-machine flow shop
| Autor: | Shuyu Zhou, Steef van de Velde, Rosario Scatamacchia, Arianna Alfieri |
|---|---|
| Přispěvatelé: | Department of Technology and Operations Management |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
0209 industrial biotechnology
021103 operations research Total flow Computer science Heuristic (computer science) 0211 other engineering and technologies 02 engineering and technology Flow shop scheduling Management Science and Operations Research Theoretical Computer Science Management Information Systems Dynamic programming symbols.namesake 020901 industrial engineering & automation Computational Theory and Mathematics Lagrangian relaxation symbols Benchmark (computing) Minification Algorithm Lagrangian |
| Zdroj: | 4OR, 19(2), 265-288. Springer-Verlag |
| ISSN: | 1619-4500 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink