Abstract
In this paper we present a parallel tabu search algorithm for the permutation flow shop sequencing problem with the objective of minimizing the flowtime. We propose a neighbourhood using so-called blocks of jobs on a critical path and a backtrace jump method. By computer simulations it is shown that the performance of the proposed algorithm is comparable with the random heuristic technique discussed in literature. Another interesting property is the fact that the speedup of parallel implementation is equal or even greater than p, where p is the number of processors.