基于优势种群的离散果蝇优化算法求解无等待流水车间调度问题

Discrete fruit fly optimization algorithm based on dominant population for solving no-wait flow shop scheduling problem

针对以最小化最大完工时间为目标的无等待流水车间调度问题,提出一种基于优势种群的离散果蝇算法进行求解。算法基于排列形式进行编码,以PF_NEH(Profile Fitting&Nawaz-Enscore-Ham)算法为基础构造优势种群;在果蝇优化算法的嗅觉搜索阶段,提出分段破坏迭代贪婪算法和成组插入法进行邻域搜索;在视觉搜索阶段,设计部分交叉策略对较差个体与优势个体进行信息交换,从而引导较差个体向种群中心位置移动,同时提出多种变异机制对优势个体进行变异,以提高种群的多样性。通过标准实例测试,验证了所提算法的有效性。

An effective Discrete Fruit fly Optimization Algorithm（DFOA）based on dominant population was proposed for no-wait flow shop scheduling problem with makespan minimization.The permutation based encoding schemes was designed in the algorithm,and Profile Fitting Nawaz-Enscore-Ham（PF_NEH）algorithm was used to construct the initial population.In the smell-based search stage of DFOA,the improved Iterated Greedy algorithm（IG）and group-based insertion method were put forward to carry out the neighborhood search;in the visionbased search stage,the partly crossing policy was designed to make the worst individuals change the information with the better individuals and guide the worst individuals to fly to the best position of the population.To improve the diversities of the population,several mutate methods were used for the better individuals.Effectiveness of the proposed algorithm was validated through a group of benchmark instances.