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

doi:10.3901/JME.2023.16.435

机械工程学报 ›› 2023, Vol. 59 ›› Issue (16): 435-444,426.doi: 10.3901/JME.2023.16.435

• 交叉与前沿 • 上一篇

扫码分享

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

黄林¹, 赵诗奎¹, 黄森²

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

收稿日期:2022-09-20 修回日期:2022-12-22 出版日期:2023-08-20 发布日期:2023-11-15
通讯作者: 赵诗奎(通信作者),男,1984年出生,博士,副教授。主要研究方向为车间生产调度和智能优化算法。E-mail:me_zhaosk@ujn.edu.cn
作者简介:黄林,男,1995年出生。主要研究方向为车间生产调度和智能优化算法。E-mail:670918850@qq.com;黄森,男,1995年出生。主要研究方向为群体智能和基于模型的故障诊断。E-mail:hs_huangs@163.com
基金资助:
国家自然科学基金资助项目(52275490,51775240)。

Hybrid Algorithm Based on Obstacle Graph Model and Tabu Search for Job Shop Scheduling Problem

HUANG Lin¹, ZHAO Shikui¹, HUANG Sen²

1. School of Mechanical Engineering, University of Jinan, Jinan 250022;
2. Department of Computer, Zhejiang Normal University, Jinhua 321000

Received:2022-09-20 Revised:2022-12-22 Online:2023-08-20 Published:2023-11-15

摘要/Abstract

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

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

Abstract: Aiming at the job shop scheduling problem（JSP）, a hybrid algorithm based on obstacle graph model and tabu search is proposed to optimize the maximum completion time. In the obstacle graph model, an effective path search algorithm is designed which scientifically inserts the removed jobs into schedule, and then the job-level search is achieved. In the tabu search algorithm, the neighborhood structure is utilized to realize the moving operations search. By mixing the two algorithms, the collaborative search on job-level and operation-level scales is realized. When an algorithm falls into local optimum, solution from the neighborhood solutions of the current algorithm is selected and inputted into the computing of another algorithm, and the two algorithms cooperate to get high quality solutions. The effectiveness of the proposed algorithm is verified by JSP benchmark instances test. By studying the characteristics of the path of obstacle graph, a new node expansion method is designed, which can not only find the shortest path of obstacle graph, but also provide a reference for other path search methods. At the same time, the proposed hybrid algorithm can also be regarded as an effective algorithm framework.

Key words: job shop scheduling, obstacle graph model, tabu search algorithm, path planning, maximum completion time

中图分类号:

TP301

黄林, 赵诗奎, 黄森. 基于障碍图模型和禁忌搜索混合算法求解作业车间调度问题[J]. 机械工程学报, 2023, 59(16): 435-444,426.

HUANG Lin, ZHAO Shikui, HUANG Sen. Hybrid Algorithm Based on Obstacle Graph Model and Tabu Search for Job Shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2023, 59(16): 435-444,426.

参考文献

[1] AKERS S. A graphical approach to production scheduling problems[J]. Operations Research, 1956, 4:244-245.
[2] YAMADA T, NAKANO R. A genetic algorithm applicable to large-scale job-shop problems[J]. Proceedings of the Second International Work Shop on Parallel Problem Solving from Nature, 1992, 2:281-290.
[3] VAN LAARHOVEN P J M, AARTS E H L, LENSTRA J K. Job shop scheduling by simulated annealing[J]. Operations Research, 1992, 40(1):113-125.
[4] NOWICKI E, SMUTNICKI C. A fast taboo search algorithm for the job shop problem[J]. Management Science, 1996, 42:797-813.
[5] NOWICKI E, SMUTNICKI C. Some new tools to solve the job shop problem[R]. Wroclaw:Institute of Engineering Cybernetics, Technical University of Wroclaw, 2002.
[6] ZHANG Chaoyong, LI Peigen, GUAN Zailin, et al. A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem[J]. Computers and Operations Research, 2007, 34(11):3229-3242.
[7] AIEX R M, BINATO S, RESENDE M G C. Parallel GRASP with path-relinking for job shop scheduling[J]. Parallel Computing, 2003, 29(4):393-430.
[8] 张超勇,管在林,刘琼,等. 一种新调度类型及其在作业车间调度中的应用[J]. 机械工程学报, 2008, 44(10):24-31. ZHANG Chaoyong, GUAN Zailin, LIU Qiong, et al. New scheduling type applied to solving job-shop scheduling problem[J]. Journal of Mechanical Engineering, 2008, 44(10):24-31.
[9] 潘全科,王凌,高亮,等. 基于差分进化与块结构邻域的作业车间调度优化[J]. 机械工程学报, 2010, 46(22):182-188. PAN Quanke, WANG Ling, GAO Liang, et al. Differential evolution algorithm based on blocks on critical path for job shop scheduling problems[J]. Journal of Mechanical Engineering, 2010, 46(22):182-188.
[10] ZUO Xingquan, WANG Chunlu, TAN Wei. Two heads are better than one:an AIS-and TS-based hybrid strategy for job shop scheduling problems[J]. International Journal of Advanced Manufacturing Technology, 2012, 63(1):155-158.
[11] 易军,李太福. 求解作业车间调度的变邻域细菌觅食优化算法[J]. 机械工程学报, 2012, 48(12):178-183. YI Jun, LI Taifu. Bacterial foraging optimization algorithm based on variable neighborhood for job-shop scheduling problem[J]. Journal of Mechanical Engineering, 2012, 48(12):178-183.
[12] GONÇALVES J F, RESENDE M G C. An extended Akers graphical method with a biased random-key genetic algorithm for job-shop scheduling[J]. International Transactions in Operational Research, 2014, 21(2):215-246.
[13] GONZÁLEZ M, VELA C, VARELA R. Scatter search with path relinking for the flexible job shop scheduling problem[J]. European Journal of Operational Research, 2015, 245(1):35-45.
[14] PENG Bo, LÜ Zhipeng, CHENG T C E. A tabu search/path relinking algorithm to solve the job shop scheduling problem[J]. Computers and Operations Research, 2015, 53(53):154-164.
[15] NAGATA Y, ONO I. A guided local search with iterative ejections of bottleneck operations for the job shop scheduling problem[J]. Computers and Operations Research, 2018, 90:60-71.
[16] PENG Chong, WU Guanglin, LIAO T W, et al. Research on multi-agent genetic algorithm based on tabu search for the job shop scheduling problem[J]. PLOS ONE, 2019, 14(9):e0223182.
[17] 赵诗奎. Job Shop基于无延迟调度路径重连与回溯禁忌搜索算法研究[J]. 机械工程学报, 2021, 57(14):291-303. ZHAO Shikui. Research on path relinking based on non-delay scheduling and backtracking tabu search algorithm of job shop scheduling problem[J]. Journal of Mechanical Engineering, 2021, 57(14):291-303.
[18] MAHMUD S, ABBASI A, RIPON K C, et al. Multi-operator communication based differential evolution with sequential tabu search approach for job shop scheduling problems[J]. Applied Soft Computing, 2021, 108:107470.
[19] XIE Jin, LI Xinyu, GAO Liang, et al. A new neighborhood structure for job shop scheduling problems[J]. International Journal of Production Research, 2023, 61(7):2147-2161.
[20] XIE Jin, LI Xinyu, GAO Liang, et al. A hybrid algorithm with a new neighborhood structure for job shop scheduling problems[J]. Computers and Industrial Engineering, 2022, 169:108205.
[21] STRASSL S, MUSLIU N. Instance space analysis and algorithm selection for the job shop scheduling problem[J]. Computers and Operations Research, 2022, 141:105661.
[22] BRUCKER P. An efficient algorithm for the job-shop problem with two jobs[J]. Computing, 1988, 40(4):353-359.
[23] AGNETIS A, ORIOLO G. The machine duplication problem in a job shop with two jobs[J]. International Transactions in Operational Research, 1995, 2(1):45-60.
[24] HART P E, NILSSON N J, RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE. Transactions on Systems and Cybernetics, 1968, 4(2):100-108.
[25] BALAS E, VAZACOPOULOS A. Guided local search with shifting bottleneck for job shop scheduling[J]. Management Science, 1998, 44(2):262-275.
[26] SHARMA N, SHARMA H, SHARMA A. Beer froth artificial bee colony algorithm for job-shop scheduling problem[J]. Applied Soft Computing, 2018, 68:507-524.
[27] QING-DAO-ER-JI R, WANG Yuping. A new hybrid genetic algorithm for job shop scheduling problem[J]. Computers and Operations Research, 2012, 39(10):2291-2299.

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

Hybrid Algorithm Based on Obstacle Graph Model and Tabu Search for Job Shop Scheduling Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	邓建新, 袁邦颐, 黄秋林, 丁度坤, 辛曼玉, 刘光明. 基于工业机器人的复杂曲面磨抛关键技术综述[J]. 机械工程学报, 2024, 60(7): 1-21.
[2]	张伟民, 徐森生, 张月. 基于改进A^*算法的室内巡检机器人路径规划研究[J]. 机械工程学报, 2024, 60(20): 315-326.
[3]	王晓飞, 许家忠, 丁亮, 黄成, 杨怀广, 刘美军. 趋向性锁链式路径规划算法[J]. 机械工程学报, 2024, 60(19): 53-61.
[4]	徐文琳, 彭羽, 何智成, 姜潮. 复杂路径规划的机构分区运动学拓扑构型设计[J]. 机械工程学报, 2024, 60(11): 62-73.
[5]	闫守鑫, 王伟, 苏鹏飞, 贠超. 大型复杂锻件打磨路径的智能化规划方法[J]. 机械工程学报, 2024, 60(11): 216-225.
[6]	胡林, 杨冬兆, 张新, 章杰, 廖家才. 基于DQP-LMPC的智能车超车换道动态路径规划[J]. 机械工程学报, 2024, 60(10): 171-181.
[7]	聂士达, 刘辉, 廖志昊, 谢雨佳, 项昌乐, 韩立金, 林思豪. 考虑复杂地形的越野环境无人车辆路径规划研究[J]. 机械工程学报, 2024, 60(10): 261-272.
[8]	林晨, 魏洪乾, 荆威, 张幽彤. 汽车功能安全：面向敏感指令攻击场景的自主驾驶车辆路径规划风险缓解控制[J]. 机械工程学报, 2024, 60(10): 302-316.
[9]	普雪洁, 张建辉, 李建勇, 张健楠. 复杂技术系统隐性冲突求解路径规划方法[J]. 机械工程学报, 2024, 60(1): 309-328.
[10]	向红标, 杨大虎, 杨璐, 王收军, 张冕, 黄显, 霍文星. 复杂环境下磁弹性微型游泳机器人的路径规划与识别跟踪[J]. 机械工程学报, 2023, 59(5): 89-99.
[11]	吴宏宇, 牛文栋, 张玉玲, 王树新, 阎绍泽. 水下滑翔机多点探测能耗最低路径的规划方法[J]. 机械工程学报, 2023, 59(5): 156-166.
[12]	赵诗奎, 黄林, 吕杰. Job shop强化多工序联动邻域结构与近似评价研究[J]. 机械工程学报, 2023, 59(4): 318-331.
[13]	刘鹏, 贾寒冰, 张雷, 王震坡. 结构化道路下智能汽车自主换道轨迹规划研究[J]. 机械工程学报, 2023, 59(24): 271-281.
[14]	崔钰萍, 郑国磊. 电缆布局设计技术研究进展综述[J]. 机械工程学报, 2023, 59(2): 268-280.
[15]	戴佳佳, 龚小溪, 汪俊. 面向飞机外表面检测任务的无人机覆盖路径规划方法[J]. 机械工程学报, 2023, 59(16): 243-253.