机械工程学报

作者：赵诗奎

单位：济南大学机械工程学院 济南 250022

关键词：作业车间调度问题,邻域结构,多工序联动,邻域搜索,最大完工时间；

基金：国家自然科学基金（51775240）和济南大学科技计划（XKY1721）资助项目。

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

来源：2020年第13期

《机械工程学报》期刊编辑部

查看机械工程学报杂志2020年第13期