A discrete particle swarm optimization algorithm with self-adaptive diversity control for the permutation flowshop problem with blocking

This paper proposes a discrete particle swarm optimization (DPSO) algorithm for the m-machine permutation flowshop scheduling problem with blocking to minimize the makespan, which has a strong industrial background, e.g., many production processes of chemicals and pharmaceuticals in chemical industry can be reduced to this problem. To prevent the DPSO from premature convergence, a self-adaptive diversity control strategy is adopted to diversify the population when necessary by adding a random perturbation to the velocity of each particle according to a probability controlled by the diversity of the current population. In addition, a stochastic variable neighborhood search is used as the local search to improve the search intensification. Computational results using benchmark problems show that the proposed DPSO algorithm outperforms previous algorithms proposed in the literature and that it can obtain 111 new best known upper bounds for the 120 benchmark problems.

Figure optionsDownload as PowerPoint slideHighlights
►
► Several operators are proposed to construct the update mechanism of particles in the proposed discrete particle swarm optimization algorithm.
► A self-adaptive diversity control strategy is adopted to prevent the DPSO from premature convergence.
► A stochastic variable neighborhood search is used as the local search to improve the search intensification.
► Computational results show that the proposed DPSO algorithm can obtain 111 new best known upper bounds for the 120 benchmark problems.