面向印制电路板钻孔任务动态调度的短视策略

doi:10.3969/j.issn.1007-7375.2021.06.003

工业工程 ›› 2021, Vol. 24 ›› Issue (6): 18-24,56.doi: 10.3969/j.issn.1007-7375.2021.06.003

面向印制电路板钻孔任务动态调度的短视策略

鄢敏杰, 王小明, 朱松平, 陈庆新, 毛宁

广东工业大学广东省计算机集成制造重点实验室，广东广州 510006

收稿日期:2020-03-10 发布日期:2022-01-24
通讯作者: 王小明(1986-),男,江西省人,副教授,博士,主要研究方向为随机项目调度与监控、制造与服务系统随机建模优化等。E-mail:simonwang@gdut.edu.cn E-mail:simonwang@gdut.edu.cn
作者简介:鄢敏杰(1995—)，男，湖北省人，硕士研究生，主要研究方向为项目调度与机器调度
基金资助:
国家自然科学基金资助项目(71972053, 61973089, 51505090, 51775120)

Myopic Strategy for Dynamic Scheduling of Printed Circuit Board Drilling Tasks

YAN Minjie, WANG Xiaoming, ZHU Songping, CHEN Qingxin, MAO Ning

Provincial Key Laboratory of Computer Integrated Manufacturing, Guangdong University of Technology, Guangzhou 510006, China

Received:2020-03-10 Published:2022-01-24

摘要/Abstract

摘要： 印制电路板钻孔任务因随机到达和工艺要求而难以调度。考虑该问题的NP难性质，提出基于优先规则和智能算法的短视策略。该策略采用事件驱动的再调度机制，在任务到达和任务完工时触发优化算法对当前未开工任务进行决策。为了高效求解每个决策时刻的优化问题，构建了嵌入局部优势定理的模拟退火和变邻域搜索算法，其初始解由优先规则获得。通过计算实验，在不同调度环境下对比两种智能算法与经典优先规则的表现。实验结果表明，智能算法在多数目标下的优化效果较优先规则可提升20%以上，变邻域搜索的优化效果略好于模拟退火，但是模拟退火的计算效率高一倍。

关键词: 印制电路板, 钻孔任务, 动态调度, 短视策略, 模拟退火, 变邻域搜索

Abstract: The scheduling of printed circuit board drilling tasks is difficult due to stochastic arrivals and process requirements. Considering the NP-hard property of the problem, myopic strategies based on priority rule and intelligent algorithm are proposed. In these strategies, an event-driven rescheduling mechanism is used to trigger the optimization algorithm on task arrival and task completion, which makes decisions on current unstarted tasks. In order to solve the optimization problem at each decision time point efficiently, a simulated annealing algorithm and a variable neighborhood search algorithm embedded with local dominance rules are constructed. The initial solutions of these algorithms are obtained by priority rules. Computational experiments are conducted to compare the proposed intelligent algorithms with classic priority rules under different scheduling environments. Experimental results show that the optimization effect of intelligent algorithms under most objectives is improved by more than 20% compared with the priority rules. The optimization effect of variable neighborhood search is slightly better than that of simulated annealing, but the latter is twice as efficient.

Key words: printed circuit board, drilling tasks, dynamic scheduling, myopic strategy, simulated annealing, variable neighborhood search

中图分类号:

TP391

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

YAN Minjie, WANG Xiaoming, ZHU Songping, CHEN Qingxin, MAO Ning. Myopic Strategy for Dynamic Scheduling of Printed Circuit Board Drilling Tasks[J]. Industrial Engineering Journal, 2021, 24(6): 18-24,56.

参考文献

[1] XING W, ZHANG J. Parallel machine scheduling with splitting jobs[J]. Discrete Applied Mathematics, 2000, 103(1): 259-269
[2] KIM Y D, SHIM S O, KIM S B, et al. Parallel machine scheduling considering a job-splitting property[J]. International Journal of Production Research, 2004, 42(21): 4531-4546
[3] SHIM S O, KIM Y D. A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property[J]. Computers & Operations Research, 2008, 35(3): 863-875
[4] SARIÇIÇEK İ, ÇELIK C. Two meta-heuristics for parallel machine scheduling with job splitting to minimize total tardiness[J]. Applied Mathematical Modelling, 2011, 35(8): 4117-4126
[5] KIM J G, SONG S, JEONG B. Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times[J]. International Journal of Production Research, 2020, 58(6): 1628-1643
[6] YALAOUI F, CHU C. An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times[J]. IIE Transactions, 2003, 35(2): 183-190
[7] NAIT TAHAR D, YALAOUI F, CHU C, et al. A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times[J]. International Journal of Production Economics, 2006, 99(1): 63-73
[8] WANG W L, WANG H Y, ZHAO Y W, et al. Parallel machine scheduling with splitting jobs by a hybrid differential evolution algorithm[J]. Computers & Operations Research, 2013, 40(5): 1196-1206
[9] WANG C, LIU C, ZHANG Z H, et al. Minimizing the total completion time for parallel machine scheduling with job splitting and learning[J]. Computers & Industrial Engineering, 2016, 97: 170-182
[10] LIU C, WANG C, ZHANG Z H, et al. Scheduling with job-splitting considering learning and the vital-few law[J]. Computers & Operations Research, 2018, 90: 264-274
[11] LIANG Y C, HSIAO Y M, TIEN C Y. Metaheuristics for drilling operation scheduling in Taiwan PCB industries[J]. International Journal of Production Economics, 2013, 141(1): 189-198
[12] OUELHADJ D, PETROVIC S. A survey of dynamic scheduling in manufacturing systems[J]. J Sched, 2009, 12(4): 417-431
[13] AYTUG H, LAWLEY M A, MCKAY K, et al. Executing production schedules in the face of uncertainties: a review and some future directions[J]. European Journal of Operational Research, 2005, 161(1): 86-110
[14] ÐURASEVIĆ M, JAKOBOVIĆ D. A survey of dispatching rules for the dynamic unrelated machines environment[J]. Expert Systems with Applications, 2018, 113: 555-569
[15] NIE L, GAO L, LI P, et al. A GEP-based reactive scheduling policies constructing approach for dynamic flexible job shop scheduling problem with job release dates[J]. Journal of Intelligent Manufacturing, 2013, 24(4): 763-774
[16] BECK J C, WILSON N. Proactive algorithms for job shop scheduling with probabilistic durations[J]. Journal of Artificial Intelligence Research, 2007, 28: 183-232
[17] RAHMANI D, HEYDARI M. Robust and stable flow shop scheduling with unexpected arrivals of new jobs and uncertain processing times[J]. Journal of Manufacturing Systems, 2014, 33(1): 84-92
[18] CHURCH L K, UZSOY R. Analysis of periodic and event-driven rescheduling policies in dynamic shops[J]. International Journal of Computer Integrated Manufacturing, 1992, 5(3): 153-163
[19] 刘爱军, 杨育, 邢青松, 等. 柔性作业车间多目标动态调度[J]. 计算机集成制造系统, 2011, 17(12): 2629-2637
LIU Aijun, YANG Yu, XING Qingsong, et al. Dynamic scheduling on multi-objective flexible job shop[J]. Computer Integrated Manufacturing Systems, 2011, 17(12): 2629-2637
[20] 来凯, 王小明, 陈庆新, 等. 面向模具项目动态调度问题的优先规则对比研究[J]. 工业工程, 2017, 20(5): 28-37
LAI Kai, WANG Xiaoming, CHEN Qingxin, et al. A comparative study of priority rules on mold project dynamic scheduling problem[J]. Industrial Engineering Journal, 2017, 20(5): 28-37
[21] 王小岗, 王小明, 陈庆新, 等. 具有随机返工且可中断的设计任务调度[J]. 工业工程, 2019, 22(5): 59-67
WANG Xiaogang, WANG Xiaoming, CHEN Qingxin, et al. Preemptive scheduling of design tasks with random rework[J]. Industrial Engineering Journal, 2019, 22(5): 59-67
[22] LAWRENCE S R, MORTON T E. Resource-constrained multi-project scheduling with tardy costs: comparing myopic, bottleneck, and resource pricing heuristics[J]. European Journal of Operational Research, 1993, 64(2): 168-187
[23] HANSEN P, MLADENOVIĆ N. Variable neighborhood search: principles and applications[J]. European Journal of Operational Research, 2001, 130(3): 449-467

面向印制电路板钻孔任务动态调度的短视策略

Myopic Strategy for Dynamic Scheduling of Printed Circuit Board Drilling Tasks

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

本文评价

[1]	周游, 朱文斌. 大规模基站运维优化与车队规划研究[J]. 工业工程, 2021, 24(3): 115-120,160.
[2]	刘广宇, 陈志坚, 於慧琳, 陈明瑶, 谢维. 动态的可选择可重复取送货基站运维路径优化研究[J]. 工业工程, 2020, 23(6): 89-94,123.
[3]	杨武成, 程文明. 求解考虑顺序相关调整时间的双边装配线平衡问题的变邻域搜索算法[J]. 工业工程, 2019, 22(5): 68-74.
[4]	王玖河, 韩希卓, 时国强. 考虑铁路分割线的物流园区功能区布局规划研究[J]. 工业工程, 2019, 22(5): 102-108.
[5]	吴正佳, 涂晶鑫, 华露, 白炜铖, 刘秀凤. 基于本体案例匹配的扰动作业车间智能调度辅助决策[J]. 工业工程, 2018, 21(6): 7-15,22.
[6]	郑硕, 蔺宇. 基于模拟退火的n-n入厂物流运输方案规划[J]. 工业工程, 2017, 20(2): 86-90.
[7]	刘思婧，张锦，李国旗. 基于退货策略的快速时尚品物流网络规划模型研究[J]. 工业工程, 2013, 16(6): 128-133.
[8]	林汉华1，陈新度1，吴立华1，李黎明2. 工期不确定的模具车间柔性Flowshop调度问题[J]. 工业工程, 2012, 15(1): 120-124.
[9]	彭碧涛1,2，周永务1. 三维装载约束的车辆路径问题的模拟退火算法[J]. 工业工程, 2011, 14(5): 71-74.