An improved fruit fly optimization algorithm with Q-learning for solving distributed permutation flow shop scheduling problems

Abstract

Abstract The distributed permutation flow shop scheduling problem (DPFSP) is one of the hottest issues in the context of economic globalization. In this paper, a Q-learning enhanced fruit fly optimization algorithm (QFOA) is proposed to solve the DPFSP with the goal of minimizing the makespan. First, a hybrid strategy is used to cooperatively initialize the position of the fruit fly in the solution space and the boundary properties are used to improve the operation efficiency of QFOA. Second, the neighborhood structure based on problem knowledge is designed in the smell stage to generate neighborhood solutions, and the Q-learning method is conducive to the selection of high-quality neighborhood structures. Moreover, a local search algorithm based on key factories is designed to improve the solution accuracy by processing sequences of subjobs from key factories. Finally, the proposed QFOA is compared with the state-of-the-art algorithms for solving 720 well-known large-scale benchmark instances. The experimental results demonstrate the most outstanding performance of QFOA.

Keywords

• Fruit fly optimization algorithm
• Makespan
• Distributed permutation flow-shop scheduling
• Q-learning