Parallel shifting bottleneck algorithms for non-permutation flow shop scheduling

The flow shop scheduling problem is one of the most complex and widely applicable scheduling problem. In this paper, we design efficient parallel algorithms for solving large-size non-permutation flow shop scheduling problems by leveraging the huge amount of computing power of the current multi-core computing systems. We design two parallel algorithms based on the Shifting Bottleneck heuristic. The first one is a coarse-grained parallel algorithm that is suitable for execution on multi-core systems with a small number of cores, while the second one is a fine-grained parallel algorithm suitable for multi-core systems with a large number of cores. We perform an extensive experimental analysis to evaluate the performance of the proposed algorithms for instances of various sizes. The results show that the proposed algorithms can solve large-size instances of the problem in a reasonable amount of time and obtain solutions that are within acceptable distance from the lower bounds. The proposed parallel algorithms achieve good speedup with respect to the serial variants of the algorithms.