新型混合改进遗传算法求解零等待流水车间调度问题

来源：计算机集成制造系统杂志2021年第3期北京时间：

作者：裴小兵,李依臻

单位：天津理工大学管理学院

摘要：具有零等待约束条件的流水车间调度问题是一类典型的NP难问题,针对该问题提出一种新型混合改进遗传算法进行优化求解。首先,采用改进NEH算法强化初始种群质量,提高种群的多样性。结合关联规则理论挖掘种群中的优势块,借助优势块进行人工染色体组合,以降低问题复杂度。交叉操作采用单段交叉、双段交叉和三段交叉3种交叉机制,改善算法全局搜索能力;变异过程引入水平集和种群分割的思想,将种群分割成两部分,并赋予不同的变异概率,提高算法局部搜索能力。为进一步提高遗传算法的求解性能,提出了基于NEH的邻域搜索机制,增加种群多样性,进一步提高种群质量。最后,通过实验结果和算法比较,验证了所提算法的求解性能。

关键词：零等待约束条件,流水车间调度问题,遗传算法,NEH算法,关联规则,优势块

基金资助：国家创新方法工作专项资助项目(2017IM060200)。