A novel fruit fly optimization algorithm for the semiconductor final testing scheduling problem

摘要

In this paper, a novel fruit fly optimization algorithm (nFOA) is proposed to solve the semiconductor final testing scheduling problem (SFTSP). First, a new encoding scheme is presented to represent solutions reasonably, and a new decoding scheme is presented to map solutions to feasible schedules. Second, it uses multiple fruit fly groups during the evolution process to enhance the parallel search ability of the FOA. According to the characteristics of the SFTSP, a smell-based search operator and a vision-based search operator are well designed for the groups to stress exploitation. Third, to simulate the information communication behavior among fruit flies, a cooperative search process is developed to stress exploration. The cooperative search process includes a modified improved precedence operation crossover (IPOX) and a modified multipoint preservative crossover (MPX) based on two popular structures of the flexible job shop scheduling. Moreover, the influence of the parameter setting is investigated by using Taguchi method of design-of-experiment (DOE), and suitable values are determined for key parameters. Finally, computational tests results with some benchmark instances and the comparisons to some existing algorithms are provided, which demonstrate the effectiveness and the efficiency of the nFOA in solving the SFTSP.