An effective metaheuristic with a differential flight strategy for the distributed permutation flowshop scheduling problem with sequence-dependent setup times

A discrete fruit fly optimisation algorithm based on a differential flight strategy (DFFO_DF) is proposed for solving the distributed permutation flowshop scheduling problem with sequence-dependent setup times. In the olfactory exploration stage, four types of neighbourhood perturbation operators are designed. An olfactory exploration mechanism is proposed to guide fruit flies during the exploration. In the visual flight stage, to avoid the algorithm from falling into a local optimum, we abandon the mode of all fruit flies flying towards the best individual and propose a differential flight strategy for the fruit flies to make better use of the information of different individuals. A local search method based on critical factories and job blocks helps fruit flies to improve their search capabilities. In addition, the lower bound property is applied to some operators contained in the DFFO_DF to reduce the search space. The proposed algorithm is evaluated using a detailed experimental design to determine the appropriate values of the key parameters. Finally, the proposed DFFO_DF is compared with several state-of-the-art algorithms based on different test instances. The experimental results prove that the DFFO_DF is an effective metaheuristic algorithm. (C)& nbsp;2022 Elsevier B.V. All rights reserved.

Automated summary

This paper proposes a discrete fruit fly optimisation algorithm (DFFO_DF) based on a differential flight strategy to solve the distributed permutation flowshop scheduling problem. In the olfactory exploration stage, four types of neighbourhood perturbation operators and an olfactory exploration mechanism are introduced to improve the exploration capability of fruit flies. In the visual flight stage, a differential flight strategy and a local search method based on critical factories and job blocks are employed to prevent falling into local optima.