作业车间调度问题的多工序联动邻域结构研究

摘要

针对作业车间调度问题(Job shop scheduling problem,JSP),以优化最大完工时间为目标,提出一种有效的多工序联动邻域结构。邻域结构真正将JSP求解算法的盲目搜索变得更加科学有效,同时移动多个工序是进一步提升邻域结构性能的关键。针对交换两个工序邻域结构,从理论上剖析了如何进行多工序联动能够优化最大完工时间。对已有多工序联动邻域结构存在的不足进行了分析,提出了科学有效的最多同时交换3对工序的多工序联动邻域结构。在交换关键工序块边缘工序的同时,根据最早开完工时间查找前移工序的工件前序工序,对其进行前移交换操作,根据最晚开完工时间查找后移工序的工件后序工序,对其进行后移交换操作。提出了更为宽泛的针对2个工序交换操作的可行解保障条件,在此基础上,扩展了同时交换2对工序和3对工序的可行解保障条件。对JSP基准算例进行测试,验证了所提邻域结构具有良好的性能,对于设计更为高效的JSP求解算法具有重要意义。