Parallel metaheuristics for the cyclic flow shop scheduling problem

• We consider cyclic flow show problem with setups with minimization of cycle time.
• New parallel algorithms for elimination “block” properties are proposed.
• Parallel block algorithms are used for neighborhood search acceleration.
• New MIC (Intel Xeon Phi coprocessor) multiprocessor hardware is used for computational experiments.
• Implementation in tabu search and simulated annealing for comparison, verification on benchmarks instances.

In the paper there was proposed a new method of detection of block properties for cyclic flow shop problem with machine setups that uses patterns designated for each machine by solving the adequate traveling salesman problem. The proposed method is intended to be run in the environment of shared memory in concurrent computations, such as coprocessors, GPU, or machines with multi-core CPUs. The proposed method of accelerating the review of the neighborhood through the use of the blocks was tested on two parallel metaheuristics: tabu search and simulated annealing.