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