双目标流水线调度的动态双子群离散果蝇算法

Dynamic double subgroup fruit fly algorithm for bi-criteria flow shop scheduling problem

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

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