置换流水车间调度问题的两阶段分布估计算法

来源：计算机工程与应用杂志2017年第2期北京时间：

作者：孙良旭1，曲殿利2，刘国莉3

单位：1.辽宁科技大学 软件学院，辽宁 鞍山 114051；2.辽宁科技大学 高温材料与镁资源学院，辽宁 鞍山 114051 ；3.辽宁科技大学 理学院，辽宁 鞍山 114051

摘要：针对置换流水车间调度问题，以最小化总流水时间为目标，提出了一种新颖的两阶段分布估计算法。第一阶段先利用NEH（Nawaz-Enscore-Ham，NEH）启发式构造一个较优的初始个体，然后随机生成初始种群，为保留种群的多样性，提出一种择优机制来选择个体并建立概率模型，同时在当代种群中利用精英机制保留当代种群中的最优解，最后利用概率模型采样并生成下一代种群。第二阶段采用插入、互换操作算子对第一阶段得到的最优解进行邻域搜索，来提高分布估计算法的全局搜索能力，阻止其陷入局部最优解。通过对算例进行实验、对比和分析，证明该算法的可行性和有效性。

关键词：分布估计算法,置换流水车间调度问题,NEH启发式,择优机制,邻域搜索