工件插入算法求解动态柔性作业车间调度问题

A Job Insertion Algorithm for Dynamic Flexible Job Shop Scheduling Problems

摘要

具有随机工件到达的柔性作业车间调度问题广泛存在于实际制造环境中，而传统调度算法在处理新工件到达时需要频繁重调度，响应效率低，难以满足高节奏生产环境的需求。针对这一问题，本文提出一种高效的工件插入算法，用于应对调度过程中突发的工件插入需求。该算法通过构建基于最小调度延迟与剩余调度灵活性的二维评估指标向量，对工序插入位置进行联合评估，并采用非支配排序机制提取具有潜力的插入点集合。接着，设计评估函数对插入点集合进行评估。在插入方案的构建过程中，借鉴 A*算法搜索思想进行贪婪式搜索，并在搜索完成后采用回溯机制恢复全局最优的插入方案。最后，将所提出算法应用于柔性作业车间的预排产阶段和随机工件到达阶段。实验结果表明，所提方法在预排产以及应对动态事件方面具备较高的调度效率和稳定性，在完工时间与响应速度方面均优于对比算法。

Abstract

The flexible job shop scheduling problem with random job arrivals is widely encountered in real-world manufacturing environments. Traditional scheduling algorithms often require frequent rescheduling when new jobs arrive, resulting in poor responsiveness and difficulty in satisfying the demands of fast-paced production environments. To address this issue, this paper proposes an efficient job insertion algorithm for handling unexpected job arrivals during the scheduling process. The algorithm constructs a two-dimensional evaluation vector based on minimum scheduling delay and residual scheduling flexibility to jointly assess potential insertion positions for each operation. A non-dominated sorting mechanism is employed to identify a set of promising insertion candidates, which are further evaluated using a tailored evaluation function. During the construction of the insertion plan, an A*-inspired greedy search strategy is adopted, and a backtracking mechanism is subsequently applied to obtain the globally optimal insertion plan. Finally, the proposed algorithm is applied to both the initial scheduling stage and the dynamic rescheduling stage involving randomly arriving jobs. Experimental results demonstrate that the proposed method achieves high scheduling efficiency and stability in both stages, and outperforms benchmark algorithms in terms of makespan and response time.

关键词

柔性作业车间 / 随机工件到达 / 工件插入算法 / 启发式路径搜索 / 动态调度

Key words

flexible job shop / random job arrival / job insertion algorithm / heuristic path search / dynamic scheduling

参考文献

[1] 胡东波, 王国庆, 左小德. 实时动态排产系统研究[J]. 中国机械工程, 2004, 15(8): 698-703.

[2] Hu Dongbo, Wang Guoqing, Zuo Xiaode. Study on real-time dynamic production schedule system[J]. China Mechanical Engineering, 2004, 15(8): 698-703.

[3] 唐国兰, 唐成华, 吴云忠. 车间生产计划动态调整应用研究[J]. 机电工程技术, 2004, 33(8): 92-94.

[4] Tang Guolan, Tang Chenghua, Wu Yunzhong. Application and study of dynamic adjustment of workshop production plan[J]. Mechanical & Electrical Engineering Technology, 2004, 33(8): 92-94.

[5] 严浩云, 李宏余. 基于面向负荷的生产控制的紧急订单插单问题[J]. 计算机集成制造系统, 2009(9): 1809-1815.

[6] Yan Haoyun, Li Hongyu. Rush order inserting problem based on load-oriented manufacturing control technique[J]. Computer Integrated Manufacturing Systems, 2009(9): 1809-1815.

[7] 刘思宇, 李铁克, 王柏琳, 等 . 混合流水车间插单重调度的超启发式遗传算法[J]. 计算机应用研究, 2023, 40(9): 2609-2615.

[8] Liu Siyu, Li Tieke, Wang Bailin, et al. Hyper-heuristic genetic algorithm for hybrid flow shop with rush orders insertion rescheduling problem[J]. Application Research of Computers, 2023, 40(9): 2609-2615.

[9] 杨贵林. 不确定条件下航空零部件柔性制造调度技术研究[D]. 贵阳: 贵州大学, 2024.

[10] 秦红斌, 孔仁杰, 常永顺, 等 . 基于混合平衡优化器算法的多目标柔性作业车间多重动态调度研究[J]. 工业工程, 2023, 26(5): 78-88.

[11] Qin Hongbin, Kong Renjie, Chang Yongshun, et al. Multiple dynamic scheduling of multi-objective flexible job shops based on a hybrid equilibrium optimizer algorithm[J]. Industrial Engineering Journal, 2023, 26(5): 78-88.

[12] 郭具涛, 戴铮, 张洁, 等 . 面向生产扰动的航天制造车间鲁棒性调度方法研究[J]. 工业工程, 2025, 28(2): 69-77.

[13] Guo Jutao, Dai Zheng, Zhang Jie, et al. A robust scheduling method for aerospace manufacturing workshops with production disturbance[J]. Industrial Engineering Journal, 2025, 28(2): 69-77.

[14] 鄢敏杰, 王小明, 朱松平, 等 . 面向印制电路板钻孔任务动态调度的短视策略[J]. 工业工程, 2021, 24(6): 18-24,56.

[15] Yan Minjie, Wang Xiaoming, Zhu Songping, et al. Myopic strategy for dynamic scheduling of printed circuit board drilling tasks[J]. Industrial Engineering Journal, 2021, 24(6): 18-24,56.

[16] Gao K Z, Suganthan P N, Tasgetiren M F, et al. Effective ensembles of heuristics for scheduling flexible job shop problem with new job insertion[J]. Computers & Industrial Engineering, 2015, 90: 107-117.

[17] 裴小兵, 杨景霞. 一种解决带有紧急插单问题的果蝇优化算法[J]. 系统工程, 2020, 38(6): 139-146.

[18] Pei Xiaobing, Yang Jingxia. AFOA method for rush order insertion problem[J]. Systems Engineering, 2020, 38(6): 139-146.

[19] Tang H T, Xiao Y, Zhang W, et al. A DQL-NSGA-III algorithm for solving the flexible job shop dynamic scheduling problem[J]. Expert Systems with Applications, 2024, 237: 121723.

[20] Guo H X, Liu J H, Wang Y, et al. An improved genetic programming hyper-heuristic for the dynamic flexible job shop scheduling problem with reconfigurable manufacturing cells[J]. Journal of Manufacturing Systems, 2024, 74: 252-263.

[21] 朱旭东. 考虑订单加急生产的柔性车间作业动态调度[J]. 机电工程, 2022, 39(12): 1755-1761.

[22] Zhu Xudong. Dynamic scheduling of flexible job shop considering order expedited production[J]. Journal of Mechanical & Electrical Engineering, 2022, 39(12): 1755-1761.

[23] Sun H, Hao Z W, Hu Z Y, et al. A rescheduling strategy based on deep reinforcement learning for new order insertion[J]. Engineering Applications of Artificial Intelligence, 2025, 159: 111676.

[24] Lu S J, Wang Y Q, Kong M, et al. A double deep Q-Network framework for a flexible job shop scheduling problem with dynamic job arrivals and urgent job insertions[J]. Engineering Applications of Artificial Intelligence, 2024, 133: 108487.

[25] 周荣升, 王艳红. 基于 DQN 算法的动态调度问题研究[J]. 微处理机, 2025, 46(1): 55-59.

[26] Zhou Rongsheng, Wang Yanhong. Research on dynamic scheduling problem based on DQN algorithm[J]. Microprocessors, 2025, 46(1): 55-59.

[27] 王立群. 基于 Agent 和深度强化学习的柔性作业车间动态调度方法研究[D]. 南京: 南京航空航天大学, 2022.

[28] 李晓婉. MSO 生产方式下响应订单变更的柔性作业车间调度研究[D]. 重庆: 重庆大学, 2016.

[29] Huang L, Tang D B, Zhang Z Q, et al. An iterated greedy algorithm integrating job insertion strategy for distributed job shop scheduling problems[J]. Journal of Manufacturing Systems, 2024, 77: 746-763.

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

[31] 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.

[32] Xie J, Li X Y, Gao L, et al. A hybrid genetic tabu search algorithm for distributed flexible job shop scheduling problems[J]. Journal of Manufacturing Systems, 2023, 71: 82-94.

[33] 赵诗奎. 柔性作业车间调度的改进邻域结构混合算法[J]. 计算机集成制造系统, 2018, 24(12): 3060-3072.

[34] Zhao Shikui. Hybrid algorithm based on improved neighborhood structure for flexible job shop scheduling[J]. Computer Integrated Manufacturing Systems, 2018, 24(12): 3060-3072.

[35] 陈祉烨, 胡毅, 刘俊, 等 . 利用强化学习的改进遗传算法求解柔性作业车间调度问题[J]. 科学技术与工程, 2024, 24(25): 10848-10856.

[36] Chen Zhiye, Hu Yi, Liu Jun, et al. Improved genetic algorithm using reinforcement learning to solve flexible job shop scheduling problem[J]. Science Technology and Engineering, 2024, 24(25): 10848-10856.

[37] 李志军, 陈秋莲. 改进离散蝙蝠算法求解柔性作业车间调度问题[J]. 计算机工程与应用, 2025, 61(23): 351-359.

[38] Li Zhijun, Chen Qiulian. Improved discrete bat algorithm for solving flexible job shop scheduling problem[J]. Computer Engineering and Applications, 2025, 61(23): 351-359.

[39] Gao J, Sun L Y, Gen M. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems[J]. Computers & Operations Research, 2008, 35(9): 2892-2907.

[40] Bożejko W, Uchroński M, Wodecki M. Parallel hybrid metaheuristics for the flexible job shop problem[J]. Computers & Industrial Engineering, 2010, 59(2): 323-333.

基金资助

国家自然科学基金青年基金项目(52305539)

国家自然科学基金重大研究计划培育项目(92267109)