混合流水车间调度问题的IPSO算法

Improved Particle Swam Optimization Algorithm for Hybrid Flow Shop Scheduling

混合流水车间调度问题又称柔性流水车间调度问题,广泛存在于现代工业之中。它是对传统流水车间的扩展。其中,每道工序可能有多台机器负责处理。针对混合流水车间调度问题,论文以最小化最大完成时间为目标建立整数规划模型,将经典粒子群优化算法进行改进,并同教与学算法(Teaching-Learning Based Optimation,TLBO)相结合,提出了一种用于解决该问题的改进的粒子群算法(Improved Particle Swam Optical Algorithm,IPSO)。算法在产生初始种群的过程中,首先将原问题转化为一系列置换流水车间调度问题,并求得其解。之后,将得到的解作为初始种群的一部分。由于现有的粒子群算法具有易收敛于局部最优解的缺点。因此为防止算法收敛于局部最优解,引入变异操作。此外,在粒子群优化算法的基础上引入适用于求解混合流水车间的TLBO算法的老师阶段和学生阶段。设计正交试验对算法参数设置进行分析,并确定了较优的参数组合。通过基于算例的仿真实验,并与现有的解决混合流水车间调度问题的算法进行比较,验证所提出IPSO算法是有效的。

For the hybrid flow shop scheduling problem which aims to minimize makespan,an integer program model is established.The improved particle swarm optimization algorithm with a new method of generating initial population,which is based on the study of classic particle swarm optimization algorithm,is presented.The new method transforms the hybrid flow shop scheduling problem into m-machine permutation flow shop scheduling problem.Parts of initial solutions consist of the transformed scheduling problem solution.The teacher phase and student phase of TLBO for solving hybrid flow shop scheduling problem is introduced into the proposed algorithm.The phenomenon that the particle converging on local optimum is avoided by mutation operation.Suitable parameters are suggested by perpendicular experiments on influence of parameter setting.Simulation experiments and comparisons with existing algorithms show the presented algorithm is effective.