Drill-Path Optimization with Time Limit and Thermal Protection


Article Preview

The drilling of the printed circuit board (PCB) is a critical process due to occupying a third of the total PCB production time. This study integrates the K-nearest neighbor (K-NN) algorithm and the bi-objective multi-population genetic algorithm (BMGA) for deriving a near-optimal drilling path to reduce the drilling time, to protect product from overheating, and to balance the loading of the drill axes. Firstly, the holing coordinates are parsed from a CNC drilling program, clustered with the K-NN algorithm, which divides the global holes into several areas with local holes. Next, the local holes are classified and reconnected using 1-NN algorithm and BMGA, respectively. The BMGA fitness function is adjusted to eliminate overheating and unbalancing through drill jumping to ensure product quality. Finally, the near-optimal drilling paths can be derived within the time limit by checking a stable factor. The practical values of BMGA have already been demonstrated in 20 PCB samples. By including the thermal protection and the load balancing constraints and resolving the optimal path within an acceptable time limit, i.e. 30 min, this method can reduce the drilling length by an average of 15.5% compared to the original drilling length if the number of holes to be drilled is less than 5k. For cases with the number of holes between 5k and 20k, the average length of the drilling paths can be reduced to 25.6% of the original length. Moreover, the thermal protection maintains the samples with mean yield 99.8%.



Edited by:

Zone-Ching Lin, You-Min Huang, Chao-Chang Arthur Chen and Liang-Kuang Chen




H. C. Yang et al., "Drill-Path Optimization with Time Limit and Thermal Protection", Advanced Materials Research, Vol. 579, pp. 153-159, 2012

Online since:

October 2012




[1] C. Oysu and Z. Bingul, Application of heuristic and hybrid-GASA algorithms to tool-path optimization problem for minimizing airtime during machining, Engineering Applications of Artificial Intelligence, 22(3) (2008) 389-396.

DOI: https://doi.org/10.1016/j.engappai.2008.10.005

[2] H. D. Nguyen, I. Yoshihara, K. Yamamori, and M. Yasunaga, Implementation of an Effective Hybrid GA for Large-Scale Traveling Salesman Problems, IEEE Instrumentation and Measurement Magazine, 37 (2007) 92-99.

DOI: https://doi.org/10.1109/tsmcb.2006.880136

[3] S. Chatterjee, C. Carrera, and L. A. Lynch, Genetic algorithms and traveling salesman problems, European Journal of Operational Research, 93 (1996) 490-510.

DOI: https://doi.org/10.1016/0377-2217(95)00077-1

[4] Y. Z. Guang, Drill Path Optimization Based on Swarm Intelligent Algorithm, IEEE Trans. on Instrumentation and Measurement, (2006) 193-196.

[5] A. Adam, A. F. Z. Abidin, Z. Ibrahim, A. R. Husain, Z. M. Yusof, and I. Ibrahim, A Particle Swarm Optimization Approach to Robotic Drill Route Optimization, in Fourth Asia International Conference on Mathematical/Analytical Modeling and Computer Simulation, Kota Kinabalu, Borneo, Malaysia (2010).

DOI: https://doi.org/10.1109/ams.2010.25

[6] M. Dorigo and L. M. Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1(1) (1997) 53-66.

DOI: https://doi.org/10.1109/4235.585892

[7] M. Chandrasekaran, M. Muralidhar, C. M. Krishna, and U. S. Dixit, Application of soft computing techniques in machining performance prediction and optimization: a literature review, The International Journal of Advanced Manufacturing Technology, 46(3) (2010).

DOI: https://doi.org/10.1007/s00170-009-2104-x

[8] Y. C. Liu and Y. B. Liu, Application of Genetic Algorithms in the Optimization of the Drilling Path on the Printed Circuit Board, Advanced Materials Research on Sport Materials, Modeling and Simulation, 187 (2011) 133-138.

DOI: https://doi.org/10.4028/www.scientific.net/amr.187.133

[9] P. -C. Changa, J. -C. Hsiehb, and C. -Y. Wang, Adaptive multi-objective genetic algorithms for scheduling of drilling operation in printed circuit board industry, Applied Soft Computing, 7(3) (2007) 800-806.

DOI: https://doi.org/10.1016/j.asoc.2006.02.002

[10] Z. -W. Zhou and T. -M. Ding, Research on Holes Machining Path Planning Optimization with TSP and GA, Modular Machine Tool & Automatic Manufacturing Technique, 7 (2007).

[11] S. Sigl and H. A. Mayer, Hybrid Evolutionary Approaches to CNC Drill Route Optimization, in International Conference on Computational Intelligence for Modelling, Control and Automation, (2005) 905-010.

DOI: https://doi.org/10.1109/cimca.2005.1631379