基于障碍图模型和禁忌搜索混合算法求解作业车间调度问题

作     者：黄林 赵诗奎 黄森 HUANG Lin;ZHAO Shikui;HUANG Sen

作者机构：济南大学机械工程学院济南250022 浙江师范大学计算机系金华321000 

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

出 版 物：《机械工程学报》 (Journal of Mechanical Engineering)

年 卷 期：2023年第59卷第16期

页      码：435-444,426页

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

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

学科分类：08[工学] 0701[理学-数学类] 0812[工学-测绘类] 081202[081202] 

核心收录：

D　O　I：10.3901/JME.2023.16.435

馆 藏 号：203124345...