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