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