Improved Fruit Fly Algorithm to Solve No-Idle Permutation Flow Shop Scheduling Problem

The no-idle permutation flow shop scheduling problem (NIPFSP), as a current hot topic, is widely present in practical production scenarios in industries such as aviation and electronics. However, existing methods may face challenges such as excessive computational time or insufficient solution quality when solving large-scale NIFSSP instances. In this paper, a discrete fruit fly optimization algorithm (DFFO) is proposed for solving the NIPFSP. DFFO consists of three phases, i.e., the smell search phase based on the variable neighborhood, the visual search phase based on the probabilistic model, and the local search phase. In the smell search phase, multiple perturbation operators are constructed to further expand the search range of the solution; in the visual search phase, a probabilistic model is constructed to generate a series of positional sequences using some elite groups, and the concept of shared sequences is adopted to generate new individuals based on the positional sequences and shared sequences. In the local search stage, the optimal individuals are refined with the help of an iterative greedy algorithm, so that the fruit flies are directed to more promising regions. Finally, the test results show that DFFO’s performance is at least 28.1% better than other algorithms, which verifies that DFFO is an efficient method to solve NIPFSP.