A hybrid method for the parallel flow-shop scheduling problem.

In this study, we have dealt with a scheduling problem that has not been studied enough, the parallel flow-shop scheduling problem. Its difficulty lies in the fact that it consists of two sub-problems: the assignment of jobs to workshops and the scheduling of these jobs once assigned. Due to the complexity of the research problem, we propose a hybridization of two well-known optimization algorithms, a bio-inspired meta-heuristic (Particle Swarm Optimization, PSO) and a local search algorithm (Tabu Search, TS); with the aim of minimizing the maximum execution time of all jobs within constraints. The purpose of this hybridization is to combine the strengths of the two methods in order to obtain more efficient results than those achieved by classic methods. The concept of the proposed method is to start by generating a set of near-optimal solutions by the PSO meta-heuristic. Then the TS algorithm refines and improves these solutions in order to attain the optimal solution.