机械工程学报

作者：黄学文, 王强, 陈桢

单位：大连理工大学经济管理学院 大连 116024

关键词：非改进邻域解,邻域结构,局部搜索,作业车间调度；

基金：国家自然科学基金资助项目(72073018)

在局部搜索算法求解作业车间调度问题(Job-shop scheduling problem，JSP)时，准确识别邻域中的改进和非改进邻域解，可提高计算效率。为此，提出一种改进和非改进邻域解的判定定理，该判定定理在传统判定理论的基础上进行拓展，能够更为精准地对改进和非改进邻域解进行识别。考虑到所提出的判定定理需要高代价的精确算法，针对JSP常用的N1、N4、N5、N6和N7邻域结构，进一步提出一种低代价的非改进邻域解判定方法，在不需要实际执行移动的前提下，可实现非改进邻域解的快速识别。试验结果表明：尽管不能完全识别邻域中的所有非改进邻域解，但仍然能够筛查掉邻域中36.12%～94.92%的非改进邻域解；与此同时，在不降低求解质量的前提下，显著提升了局部搜索算法的计算效率。

来源：2025年第10期

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

查看机械工程学报杂志2025年第10期