陈园园, 夏筱筠, 柏 松, 宋 佳



粒子群遗传算法在离散制造业排产中的研究①

陈园园1,2, 夏筱筠2, 柏 松3, 宋 佳2

1(中国科学院大学, 北京 100049)2(中国科学院沈阳计算技术研究所, 沈阳 110168)3(中航工业沈阳黎明航空发动机(集团)有限责任公司, 沈阳 110043)

在离散制造业中, 排产方法的优劣直接影响生产的效率. 为了使算法更好的应用到排产当中, 首先分析离散制造业的生产特点. 同时, 为了提高算法的搜索性能, 分析遗传算法与粒子群优化算法的优缺点, 提出了一种粒子群遗传混合算法(PSO_GA). 该算法中, 在遗传算法的基础上引入参数, 从而动态控制每次迭代交叉变异比, 进而提高群体多样性. 同时为了克服遗传算法自身收敛速度慢的缺点, 在适当的迭代周期内引入粒子群优化算法, 从而提高算法的搜索速度和精度. 最后, 针对排产模型进行仿真实验, 结果表明该算法具有很好的搜索性能.

离散制造业; 排产; 遗传算法; 粒子群优化; PSO_GA混合算法

Job-shop调度问题是一类经典的NP-Hard组合优化问题, 它是求解每道工序具有特定加工机器的一类调度问题. 而离散制造业具有小批量、多品种、并行、异步生产、设备功能多、冗余度高等特点[1]. 这些特点使得离散制造业中可以加工某道工序的设备往往不止一个, 且每种工件所包含的工序数也不相同. 因此,与经典的Job-shop问题相比, 离散制造业排产问题的可行解空间更大, 问题的复杂性更高, 对其展开研究具有重要意义.

近年来, 随着并行计算的……