基于离散候鸟迁徙优化算法的置换流水车间调度问题

针对置换流水车间调度问题,以最小化最大完成时间为调度目标,提出了一种离散候鸟迁徙优化(Discrete Migrating Birds Optimization,DMBO)调度算法。采用NEH产生一个调度可行解,其余个体随机产生,保证了种群的质量和多样性,初始化鸟群按优化目标值升序排成倒V字形。领飞鸟通过优化插入加优化交换产生的邻域解进化,而通过混合策略获得跟飞鸟的邻域解。跟飞鸟通过其邻域解和前面个体未使用的、较好的邻域解进化,这种进化机制是独一无二的。最后,采用局部搜索算法进一步优化种群。仿真实验中使用正交设计方法调节算法参数,通过求解Car 和Rec标准算例,验证了算法的有效性。

A Discrete Migrating Birds Optimization Algorithm for Permutation Flow Shop Scheduling Problem

In this work,a discrete migrating birds optimization (DMBO) scheduling algorithm is proposed for permutation flow shop scheduling problem (PFSP) with the objective of minimizing maximum completion time (i.e. makespan).In order to guarantee the quality and diversity of the flock, NEH is employed to yield a feasible solution and the others are generated randomly in DMBO algorithm.The flock are arranged in the reversed hypothetical V formation according to the ascending order of optimization value.The leader is evolved from the neighbor solutions which are generated by optimizing insertion and swap operators.Meanwhile,the other birds in the flock are evolved by their neighbor solutions generated by hybrid-strategy and the unused better neighbor solutions of the previous generated by hybrid-strategy individuals.This evolution mechanism is unique for migrating birds optimization algorithm.Furthermore,a local search procedure is performed on every individual.Finally,an orthogonal design method is employed in experiment to regulate the parameters of DMBO.By testing the Car and Rec benchmarks,it is shown that the proposed DMBO algorithm is effective in the performance.