Application of Sequence-Dependent Traveling Salesman Problem in Printed Circuit Board Assembly

作者：Alkaya Ali Fuat^*; Duman Ekrem

来源：IEEE Transactions on Components, Packaging and Manufacturing Technology, 2013, 3(6): 1063-1076.

DOI：10.1109/TCPMT.2013.2252429

• Heuristic algorithms
• optimization
• quadratic programming
• simulated annealing

Optimization issues regarding the automated assembly of printed circuit boards attracted the interest of researchers for several decades. This is because even small gains in assembly time result in very important benefits in mass production. In this paper, the focus is on a particular placement machine type that has a rotational turret and a stationary component magazine. So far, this type of machine received little attention among the researchers. In this paper, the feeder configuration, placement sequencing, and assembly time minimization problems are formulated explicitly and completely (without simplifying assumptions) using nonlinear integer programming. In addition, the placement sequencing problem is shown to be a recently introduced new generalization of the traveling salesman problem (the sequence-dependent traveling salesman). These formulations show the complexity of the problems and the need for effective heuristic designs for solving them. We propose three heuristics that improve previously suggested solution methods and give comparable results when compared to simulated annealing that is a widely accepted good performing metaheuristic on combinatorial optimization problems. The heuristics are experimentally shown to improve previous methods significantly in assembly time that implies a huge economic benefit. The heuristics proposed could also be applied to other placement machines with similar operation principles.

• 出版日期2013-6