• CN:11-2187/TH
  • ISSN:0577-6686

机械工程学报 ›› 2021, Vol. 57 ›› Issue (14): 291-303.doi: 10.3901/JME.2021.14.291

• 交叉与前沿 • 上一篇    下一篇

扫码分享

Job Shop基于无延迟调度路径重连与回溯禁忌搜索算法研究

赵诗奎   

  1. 济南大学机械工程学院 济南 250022
  • 收稿日期:2020-06-05 修回日期:2021-02-18 出版日期:2021-09-15 发布日期:2021-09-15
  • 作者简介:赵诗奎,男,1984年出生,博士,副教授。主要研究方向为车间生产调度和智能优化算法。E-mail:me_zhaosk@ujn.edu.cn
  • 基金资助:
    国家自然科学基金资助项目(51775240)

Research on Path Relinking Based on Non-delay Scheduling and Backtracking Tabu Search Algorithm of Job Shop Scheduling Problem

ZHAO Shikui   

  1. School of Mechanical Engineering, University of Jinan, Jinan 250022
  • Received:2020-06-05 Revised:2021-02-18 Online:2021-09-15 Published:2021-09-15

摘要: 针对作业车间调度问题(Job shop scheduling problem,JSP),以优化最大完工时间为目标,提出一种路径重连和禁忌搜索混合算法。结合JSP领域知识设计路径重连,分别将正向无延迟调度解和反向无延迟调度解作为导向解。在正向无延迟和反向无延迟调度甘特图中,每一道工序的左边与右边分别无可用空闲时间。提出基于当前解工序头长度的正向无延迟调度转化算法,以及反转工件工艺路线,基于当前解工序尾长度的反向无延迟调度转化算法。设计新的基于精英解的回溯禁忌搜索算法,能够充分利用迭代过程中的历史解信息。不但提取更新的当前最优解加入到精英解集合,而且当最优解连续不更新代数达到设定值时,提取区间代数内较好的当前解加入到精英解集合。实现精英解池的不断补充和动态更新,使得算法可以持续进行回溯搜索。采用移动范围更广的邻域结构进行搜索,将路径重连与禁忌搜索算法混合,对JSP问题基准算例进行测试,验证了所提算法的有效性。

关键词: 作业车间调度, 禁忌搜索算法, 路径重连, 无延迟调度, 最大完工时间

Abstract: Aiming at the job shop scheduling problem(JSP), a hybrid algorithm of path relinking and tabu search is proposed to optimize the maximum completion time. Combining with JSP domain knowledge to design path relinking, the forward and reverse non-delay scheduling solutions are taken as the guiding solutions respectively. There is no available idle time on the left and right side of each operation respectively corresponding to the forward and reverse non-delay scheduling Gantt chart. A forward non-delay scheduling conversion algorithm based on operation head length of the current solution is proposed. A reverse non-delay scheduling conversion algorithm based on operation tail length of the current solution is presented after reversing the job process route. A new backtracking tabu search algorithm based on elite solutions is designed, which can make full use of the historical solutions information in the iterative evolution process. Not only the updated current optimal solution is extracted and added to the elite solution set, but when the number of consecutive non-update iterations of the optimal solution reaches the set value, the better current solution in the interval generations is extracted and added to the elite solution set. The continuous replenishment and dynamic update of the elite solution pool are realized, so that the algorithm can continuously carry out backtracking search. The neighborhood structure with a wider operation moving range is adopted. The path relinking and tabu search algorithm are mixed to test the JSP benchmarks to verify the effectiveness of the proposed algorithm.

Key words: job shop scheduling, tabu search algorithm, path relinking, non-delay scheduling, maximum completion time

中图分类号: