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

ALKAYA A. F., DUMAN E.

DISCRETE APPLIED MATHEMATICS, cilt.192, ss.2-16, 2015 (SCI-Expanded) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 192
  • Basım Tarihi: 2015
  • Doi Numarası: 10.1016/j.dam.2015.03.009
  • Dergi Adı: DISCRETE APPLIED MATHEMATICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.2-16
  • Anahtar Kelimeler: PCB assembly, Sequence dependent TSP, Metaheuristics, Artificial bee colony, Simulated annealing, COMPONENT PLACEMENT MACHINE, PRINTED-CIRCUIT BOARDS, GENETIC ALGORITHM, SCHEDULING PROBLEM, OPTIMIZATION, PERFORMANCE, OPERATIONS, MODELS, SYSTEM
  • Marmara Üniversitesi Adresli: Evet

Özet

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. (C) 2015 Elsevier B.V. All rights reserved.