Particle swarm optimization with cocktail decoding method for hybrid flow shop scheduling problems with multiprocessor tasks

This paper addresses the problem of multiprocessor task-scheduling in a hybrid flow shop (HFS) problem to minimize the makespan. Due to the complex nature of an HFS problem, it is decomposed into the following two sequential decision problems: determining the job permutation in stage 1, followed by a decoding method to assign jobs into each machine in subsequent stages when designing a heuristic algorithm. The decoding method plays a pivotal role for improving the solution quality of any algorithm for the HFS problem. However, the majority of existing algorithms ignores the problem and is only concerned with the first decision problem. This study emphasizes the importance of the decoding method via a small test, and searches for a number of solid decoding methods that can be incorporated into the cocktail decoding method. Then, this study develops a particle swarm optimization (PSO) algorithm that can be combined with the cocktail decoding method. In the PSO, a variety of job sequences are generated using the PSO procedure in stage 1, and the cocktail decoding method is used to assign the jobs to machines in sequential stages. Moreover, a modified lower bound is introduced. Computational results show that the proposed lower bound is competitive, and with the help of the cocktail decoding method, the proposed PSO, and even the adoption of a standard PSO framework, significantly outperforms the majority of existing algorithms in terms of quality of solutions, especially for large problems.