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

Authors: Nicolau Santos; Rui Rebelo; João Pedro Pedroso

Addresses: INESC TEC and Faculdade de Ciências, Universidade do Porto, Rua do Campo Alegre, 4169-007 Porto, Portugal ' INESC TEC, Rua Dr. Roberto Frias, No. 378, 4200-465 Porto, Portugal ' INESC TEC and Faculdade de Ciências, Universidade do Porto, Rua do Campo Alegre, 4169-007 Porto, Portugal

Abstract: 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.

Keywords: flow shop scheduling; tabu search; metaheuristics; combinatorial optimisation; sequence dependent setup times; total weighted tardiness.

DOI: 10.1504/IJDATS.2014.063062

International Journal of Data Analysis Techniques and Strategies, 2014 Vol.6 No.3, pp.275 - 285

Published online: 26 Jul 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article