Home > Research > Publications & Outputs > On some lower bounds for the permutation flowsh...

Research

Associated organisational unit

Electronic data

  • flowshop-bounds

    Accepted author manuscript, 387 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Text available via DOI:

Keywords

View graph of relations

On some lower bounds for the permutation flowshop problem

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

On some lower bounds for the permutation flowshop problem. / Letchford, Adam; Dang, Thu; Caceres Gelvez, Sebastian.
In: Computers and Operations Research, Vol. 159, 106320, 30.11.2023.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Letchford, A, Dang, T & Caceres Gelvez, S 2023, 'On some lower bounds for the permutation flowshop problem', Computers and Operations Research, vol. 159, 106320. https://doi.org/10.1016/j.cor.2023.106320

APA

Letchford, A., Dang, T., & Caceres Gelvez, S. (2023). On some lower bounds for the permutation flowshop problem. Computers and Operations Research, 159, Article 106320. https://doi.org/10.1016/j.cor.2023.106320

Vancouver

Letchford A, Dang T, Caceres Gelvez S. On some lower bounds for the permutation flowshop problem. Computers and Operations Research. 2023 Nov 30;159:106320. Epub 2023 Jun 27. doi: 10.1016/j.cor.2023.106320

Author

Letchford, Adam ; Dang, Thu ; Caceres Gelvez, Sebastian. / On some lower bounds for the permutation flowshop problem. In: Computers and Operations Research. 2023 ; Vol. 159.

Bibtex

@article{ac55376d990945fe817e9d21b022a360,
title = "On some lower bounds for the permutation flowshop problem",
abstract = "The permutation flowshop problem with makespan objective is a classic machine scheduling problem, known to be NP-hard in the strong sense. We analyse some of the existing lower bounds for the problem, including the “job-based” and “machine-based” bounds, a bound from linear programming (LP), and a recent bound of Kumar and co-authors. We show that the Kumar et al. bound dominatesthe machine-based bound, but the LP bound is stronger still. On the other hand, the LP bound does not, in general, dominate the jobbased bound. Based on this, we devise simple iterative procedures for strengthening the Kumar et al. and LP bounds. Computational results are encouraging. In particular, we are able to obtain improved lower bounds for the “hard, small” instances of Vallada, Ruiz and Framinan.",
keywords = "machine scheduling, flowshop scheduling, combinatorial optimisation",
author = "Adam Letchford and Thu Dang and {Caceres Gelvez}, Sebastian",
year = "2023",
month = nov,
day = "30",
doi = "10.1016/j.cor.2023.106320",
language = "English",
volume = "159",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier Ltd",

}

RIS

TY - JOUR

T1 - On some lower bounds for the permutation flowshop problem

AU - Letchford, Adam

AU - Dang, Thu

AU - Caceres Gelvez, Sebastian

PY - 2023/11/30

Y1 - 2023/11/30

N2 - The permutation flowshop problem with makespan objective is a classic machine scheduling problem, known to be NP-hard in the strong sense. We analyse some of the existing lower bounds for the problem, including the “job-based” and “machine-based” bounds, a bound from linear programming (LP), and a recent bound of Kumar and co-authors. We show that the Kumar et al. bound dominatesthe machine-based bound, but the LP bound is stronger still. On the other hand, the LP bound does not, in general, dominate the jobbased bound. Based on this, we devise simple iterative procedures for strengthening the Kumar et al. and LP bounds. Computational results are encouraging. In particular, we are able to obtain improved lower bounds for the “hard, small” instances of Vallada, Ruiz and Framinan.

AB - The permutation flowshop problem with makespan objective is a classic machine scheduling problem, known to be NP-hard in the strong sense. We analyse some of the existing lower bounds for the problem, including the “job-based” and “machine-based” bounds, a bound from linear programming (LP), and a recent bound of Kumar and co-authors. We show that the Kumar et al. bound dominatesthe machine-based bound, but the LP bound is stronger still. On the other hand, the LP bound does not, in general, dominate the jobbased bound. Based on this, we devise simple iterative procedures for strengthening the Kumar et al. and LP bounds. Computational results are encouraging. In particular, we are able to obtain improved lower bounds for the “hard, small” instances of Vallada, Ruiz and Framinan.

KW - machine scheduling

KW - flowshop scheduling

KW - combinatorial optimisation

U2 - 10.1016/j.cor.2023.106320

DO - 10.1016/j.cor.2023.106320

M3 - Journal article

VL - 159

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

M1 - 106320

ER -