求解柔性流水车间调度问题的高效分布估算算法

Efficient Estimation of Distribution for Flexible Hybrid Flow Shop Scheduling

针对最小化最大完工时间的柔性流水车间调度,利用事件建模思想,线性化0-1混合整数规划模型,使得小规模调度问题通过Cplex可以准确求解,同时设计了高效分布估算算法来求解大规模调度问题.该算法采用的是一种新颖的随机规则解码方式,工件排序按选定的规则安排而机器按概率随机分配.针对分布估算算法中的概率模型不能随种群中个体各位置上工件的更新而自动调整的缺点,提出了自适应调整概率模型,该概率模型能提高分布估算算法的收敛质量和速度.同时为提高算法局部搜索能力和防止算法陷入局部最优,设计了局部搜索和重启机制.最后,采用实验设计方法校验了高效分布估算算法参数的最佳组合.算例和实例测试结果都表明本文提出的高效分布估算算法在求解质量和稳定性上均优于遗传算法、引力搜索算法和经典分布估算算法.

For flexible flow shop scheduling which minimizes the maximum completion time, a 0-1 mixed integer linear programming model is established by using event modeling method, and small-scale scheduling problems can be accurately solved through any linear solver. At the same time, an efficient estimation of distribution algorithm is designed to solve large-scale problems. A novel decoding way with random probability and rules is adopted by the new algorithm, and workpiece sequencing is based on rule while assignment of machines is based on random probability. Since the original probability model does not automatically adjust sampling probability, an improved probability model is put forward. And local search and restart mechanism are designed and adopted to improve the ability of local search and to avoid falling into local optimum. Finally, optimal combination of parameters is decided by using experimental design method, and experimental results show that the new algorithm outperforms genetic algorithm, gravitational search algorithm, and classical estimation of distribution algorithm in terms of quality and stability.