A heuristic for scheduling a permutation flowshop with makespan objective subject to maximum tardiness

In this paper, we tackle the problem of makespan minimisation in a permutation flowshop where the maximum tardiness is limited by a given upper bound. Since this problem is known to be NP-hard, we focus our attention on approximate approaches that allow obtaining good heuristic solutions to the problem. We first review the related literature and then propose a new algorithm. The algorithm is found to be competitive with the existing algorithms in terms of quality of the solution as well as in terms of the number of feasible solutions found. (c) 2005 Elsevier B.V. All rights reserved.