有限等待置换流水车间调度问题的IGA算法

Improved Genetic Algorithm for Permutation Flow Shop Scheduling with Transfer Lags

在对经典遗传算法进行研究的基础上,针对具有等待时间置换流水车间调度问题,以最小化最大完成时间为优化目标建立整数规划模型,并提出一种解决该问题的IGA算法;算法中部分染色体的初始种群由原问题所转化而成的具有等待时间两台机器的置换流水车间调度问题的解所组成;交叉方法采用基于顺序和位置相结合的OPX方法;通过对Taillard算例中置换流水车间调度问题基准数据的测试,并对仿真实验的结果进行了分析,验证所提出IGA算法的有效性和可行性。

For the permutation flow shop scheduling problem with transfer lags which aims to minimize makespan, an integer program model was established. The improved genetic algorithm with a new method of generating initial population, which is based on the study of classic genetic algorithm, is presented. The new method transforms the permutation flow shop scheduling problem with transfer lags into a two--machine permutation flow shop scheduling problem with transfer lags. A part of initial solutions consist of the solution of the transformed scheduling problem. The simulation experiments using the Taillard ＇ s instances show the presented algorithm is feasible and effective.