作业车间调度的块结构邻域搜索遗传算法

作者：薛玲玲

来源：计算机集成制造系统, 2021, 27(10): 2848-2857.

DOI：10.13196/j.cims.2021.10.009

• 作业车间调度
• 块结构邻域搜索
• 遗传算法
• 子代选择

针对以最小化最大完工时间为优化目标的作业车间调度问题,提出一种基于块结构邻域搜索的遗传算法。采用基于工序的编码方法进行个体编码,并在编码后的个体上进行邻域构建。首先,将关键工序块的块首或块尾工序与块内某个工序组合,然后对该组合进行交换、移动操作构建出邻域个体。其次,提出了个体的冗余性判断条件,对邻域中调度方案相同的个体只保留其中一个,达到减少冗余个体的目的。另外,为改善整个种群基因的有效性和延迟算法的早熟,采用具有子代选择特征的改进选择机制。最后,通过在典型算例上的仿真实验,验证了所提算法的有效性。

• 单位
  机器人学国家重点实验室; 中国科学院沈阳自动化研究所; 中国科学院大学