A tabu search for the permutation flow shop problem with sequence dependent setup times

In this work we present a tabu search metaheuristic method for solving the permutation flow shop scheduling problem with sequence dependent setup times and the objective of minimising total weighted tardiness. The problem is well known for its practical applications and for the difficulty in obtaining good solutions. The tabu search method proposed is based on the insertion neighbourhood, and is characterised by the selection and evaluation of a small subset of this neighbourhood at each iteration; this has consequences both on diversification and intensification of the search. We also propose a speed-up technique based on book keeping information of the current solution, used for the evaluation of its neighbours.