Solving the flow shop problem by parallel tabu search

In this paper we present parallel tabu search algo-rithm for the permutation flow shop sequencing prob-lem 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 ran-dom heuristic technique discussed in literature. Other interesting property is the fact that the speedup of par-allel implementation is equal or even greater than p, where p is the number of processors. 1