巴智勇,袁逸萍,裴国庆,王 波

(1.新疆大学 机械工程学院,新疆 乌鲁木齐 830017;2.卓郎新疆智能机械有限公司,新疆 乌鲁木齐 830057)

0 引言

作业车间调度问题(Job Shop Scheduling Problem, JSP)不仅是典型的NP-hard问题,还是管理领域中许多优化问题的通用模型,如项目计划调度、岸桥调度优化[3]、轨道列车时刻表调度优化[4]等。另外,JSP模型能以一种明确的方式对问题添加各种侧约束和目标,使其应用范围不限于调度优化问题[5]。

学者们针对JSP提出了大量高效的求解方法,如数学规划[6]、调度规则[7]、启发式和元启发式算法。由于JSP的NP-hard特性,精确求解方法只适合求解小规模问题,难以应用于实际生产,当前主流研究方向是采用近似方法求解JSP。近似求解方法包括大量经典和新型的元启发式方法,如粒子群优化[8]、遗传算法[9]、差分进化[10]、蚁群算法[11]、细菌觅食算法[12]、教与学优化算法[13]和灰狼优化算法[14]等。然而,受限于基本理论和算法框架,单一的元启发式算法在JSP上的求解效果并不理想,越来越多学者利用两个或多个算法的互补特征开发更为先进的混合算法。REN等[15]提出一种混合局部搜索策略的遗传算法求解JSP,通过引入多样化的种群更新机制防止算法过早收敛;REHAB等[16]设计了基于邻域多样化强化策略的粒子群优化算法,实现了对JSP解空间的广泛搜索;PENG等[17]提出基于路径重连的禁忌算法,采用路径重连方法产生更多样的候选解,同时在禁忌搜索中应用更复杂的N7邻域,改进了多个JSP基准算例的上界;CHENG等[5]提出一种基于机……