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

摘要： 提出了一种基于动态双子群的离散果蝇优化算法，求解以最大完工时间和机床空闲时间的最小化为目标的无等待流水线调度问题。与传统的果蝇算法不同，该算法采用基于工序的编码方式，并用改进的NEH方法进行初始化，提高初始解的质量；根据算法在进化过程中个体的进化水平，动态地将整个群体划分为先进子群和后进子群，简单但有效地插入方法在先进个体邻域内进化精细搜索，贪婪迭代进化机制用于优化后进个体，以此平衡算法的全局开发能力和局部搜索能力；为了提高算法效率，快速算法用于计算函数目标值和判断更新非支配解。仿真试验表明了所提果蝇算法的有效性和高效性。

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