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
Article number106320
<mark>Journal publication date</mark>30/11/2023
<mark>Journal</mark>Computers and Operations Research
Volume159
Number of pages9
Publication StatusPublished
Early online date27/06/23
<mark>Original language</mark>English

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 dominates
the 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.

Related datasets