Combining and solving sequence dependent traveling salesman and quadratic assignment problems in PCB assembly

Abstract

In this study we undertake the optimization of chip shooter component placement machines which became popular in assembling printed circuit boards (PCB) in recent years. A PCB is usually a rectangular plastic board on which the electrical circuit to be used in a particular electronic equipment is printed. The overall optimization of the chip shooter placement machines leads to a very complicated optimization problem which we formulate here for the first time (without any simplifying assumptions). However, it is possible to decompose the problem into placement sequencing problem and feeder configuration problem which turn out to be sequence dependent traveling salesman problem (SDTSP) and Quadratic Assignment Problem (QAP), respectively. We use simulated annealing metaheuristic approach and the heuristics developed for the SDTSP in an earlier study to solve these two problems in an iterative manner. We also attempt to solve the combined overall optimization problem by simulated annealing and artificial bee colony metaheuristics and compare their performances with the iterative approach. The results are in favor of iterative approach.