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

Myopic Strategy for Dynamic Scheduling of Printed Circuit Board Drilling Tasks

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

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.