机械工程学报

作者：黄林, 赵诗奎, 黄森

单位：1. 济南大学机械工程学院 济南 250022;2. 浙江师范大学计算机系 金华 321000

关键词：作业车间调度,障碍图模型,禁忌搜索算法,路径规划,最大完工时间；

基金：国家自然科学基金资助项目(52275490,51775240)。

针对作业车间调度问题（Job shop scheduling problem,JSP），以优化最大完工时间为目标，提出一种基于障碍图模型和禁忌搜索混合算法。在障碍图模型中，设计有效的路径搜索算法，实现被移走工件的科学插入，进而实现工件级尺度的搜索。在禁忌搜索算法中，采用邻域结构实现移动工序搜索。通过两种算法混合，实现工件级与工序级尺度协同搜索，当某一算法陷入局部最优时，从当前算法的邻域解中选择一个解进入另一个算法运行，二者相互协同从而求解出高质量的解。通过对JSP基准算例测试，验证所提算法的有效性。通过研究障碍图路径的特征，设计新的节点扩展方式，不仅可以寻找障碍图最短路径，还可为其它路径搜索提供方法借鉴，同时所提的混合算法也可以看作是一个有效的算法框架。

来源：2023年第16期

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

查看机械工程学报杂志2023年第16期