论文推荐 | 南京航空航天大学唐敦兵教授等论文:工件插入算法求解动态柔性作业车间调度问题

工业工程 2026年 第29卷 第3期

摘要及关键词

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

唐敦兵， 杨汝舟， 黄 林， 张泽群， 崔晓哲

(南京航空航天大学 机电学院，江苏 南京 210016)

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

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

中图分类号: F423; TP301

文献标志码: A               

文章编号: 1007-7375(2026)03-0104-14

A Job Insertion Algorithm for Dynamic Flexible JobShop Scheduling Problems 

Tang Dunbing, Yang Ruzhou, Huang Lin, Zhang Zequn, Cui Xiaozhe

(College of Mechanical and Electrical Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)

Abstract:The flexible job shop scheduling problem with random job arrivals is widely encountered in real-worldmanufacturing 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 addressthis issue, this paper proposes an efficient job insertion algorithm for handling unexpected job arrivals during the schedulingprocess. The algorithm constructs a two-dimensional evaluation vector based on minimum scheduling delay and residualscheduling flexibility to jointly assess potential insertion positions for each operation. A non-dominated sorting mechanismis employed to identify a set of promising insertion candidates, which are further evaluated using a tailored evaluationfunction. During the construction of the insertion plan, an A*-inspired greedy search strategy is adopted, and a backtrackingmechanism is subsequently applied to obtain the globally optimal insertion plan. Finally, the proposed algorithm is appliedto both the initial scheduling stage and the dynamic rescheduling stage involving randomly arriving jobs. Experimentalresults demonstrate that the proposed method achieves high scheduling efficiency and stability in both stages, andoutperforms 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

基金项目、作者及引文格式

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

作者简介：唐敦兵 (1972 — )，男，湖北省人，教授，博士，主要研究方向为制造系统与自动化、智能制造系统、数字化设计与制造。 Email: d.tang@nuaa.edu.cn

引文格式：唐敦兵, 杨汝舟, 黄林, 张泽群, 崔晓哲. 工件插入算法求解动态柔性作业车间调度问题[J]. 工业工程, 2026, 29(3): 104-117. DOI: 10.3969/j.issn.1007-7375.250070

Tang Dunbing, Yang Ruzhou, Huang Lin, Zhang Zequn, Cui Xiaozhe. A Job Insertion Algorithm for DynamicFlexible Job Shop Scheduling Problems[J]. Industrial Engineering Journal, 2026, 29(3): 104-117. DOI: 10.3969/j.issn.1007-7375.250070

电子版全文浏览

左右滑动，查看更多

联系我们