Multi-thread parallel metaheuristics for the flow shop problem

Abstract. The matter of using scheduling algorithms in parallel com-puting environments is discussed. As the completion of our theoretical studies on parallel small-granularity single-thread approach [2], in this paper we propose and examine some parallel large-grain multi-thread ap-proaches, namely: parallel variants of tabu search, simulated annealing, population-based search and scatter search. Computational experiments are done for the flow shop scheduling problem, the classical NP-hard case in combinatorial optimization, which plays here the role of exem-plary test problem. Obtained results exhibit superlinear speedup in par-allel environment and allow us to recommend parallel metaheuristics as the most suitable to solve scheduling instances derived from practice.