On some lower bounds for the permutation flowshop problem

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 job-based 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.