关键词: 果蝇优化算法, 无等待流水线调度问题, 双目标, 动态双子群

Abstract: This paper presents a fruit fly optimization algorithm （FOA） based on dynamic double subgroup for solving the Bi-criteria No-wait Flowshop Scheduling Problem（BNFSP） with makespan and idle time criteria. Unlike the traditional FOA, the proposed algorithm applies the job-permutation-based representation  and initialization method based on the improved NEH（Nawaz-Enscore-Ham）. Secondly, the whole group is dynamically divided into advanced subgroup and backward subgroup according to its own evolutionary level. A simple but effective insert search algorithm is made for advanced subgroup in the neighborhood, and iterative greedy is made for backward subgroup, so that the who group keeps in good balance between global exploration and local exploitation. Finally, to improve the efficiency of the scheduling algorithm, several speed-up methods are devised to evaluate a job permutation and its whole insert neighborhood as well as to decide the domination status of a solution with the archive set. Computational results show that the FOA presented in this paper is very effective and efficient for the BNFSP.

Key words: fruit fly optimization algorithm, no-wait flow shop scheduling problem, bi-criteria；dynamic double subgroup