Parallel tabu search algorithm for the hybrid flow shop problem

• We propose new fast methods of parallel calculation of the criterion function and the local neighborhood.
• These methods are embedded and tested in the tabu search approach for the hybrid flow shop problem.
• We present theoretical analysis and the original implementation with the use of vector processing instructions.
• Numerical properties of the proposed approaches are empirically verified on the multi-core computing environment.

The paper deals with the parallel variant of the scheduling algorithm dedicated to the hybrid flow shop problem. The problem derives from practice of automated manufacturing lines, e.g. for printed packages. The overall goal is to design a new algorithm which merges the performance of the best known sequential approach with the efficient exploitation of parallel calculation environments. In order to fulfill the above aim, there are two methods proposed in this paper: the original fast method of parallel calculation of the criterion function and the local neighborhood parallel search method embedded in the tabu search approach. The theoretical analysis, as well as the original implementation, with the use of vector processing instructions SSE2 supported by suitable data organization, are presented below. Numerical properties of the proposed algorithm are empirically verified on the multi-core processor.