Efficient non-population-based algorithms for the permutation flowshop scheduling problem with makespan minimisation subject to a maximum tardiness

• We address the permutation flowshop problem to minimise makespan subject to a maximum tardiness.
• We propose two new non-population-based algorithms for the problem.
• We define several properties of the problem to be able to partly apply Taillard׳s acceleration.
• We compare the proposals with each efficient algorithm in the literature.

This paper focuses on the problem of scheduling jobs in a permutation flowshop with the objective of makespan minimisation subject to a maximum allowed tardiness for the jobs, a problem that combines two desirable manufacturing objectives related to machine utilisation and to customer satisfaction. Although several approximate algorithms have been proposed for this NP-hard problem, none of them can use the excellent speed-up method by Taillard (1990) [22] for makespan minimisation due to the special structure of the problem under consideration. In this paper, several properties of the problem are defined in order to be able to partly apply Taillard׳s acceleration. This mechanism, together with a novel feasible tabu local search method, allows us to further exploit the structure of solutions of the problem, and are incorporated in two proposed algorithms: a bounded-insertion-based constructive heuristic and an advanced non-population-based algorithm. These algorithms are compared with state-of-the-art algorithms under the same computer conditions. The results show that both algorithms improve existing ones and therefore, constitute the new state-of-art approximate solution procedures for the problem.