A new novel local search integer-programming-based heuristic for PCB assembly on collect-and-place machines
Tóm tắt
This paper presents the development of a novel vehicle-routing-based algorithm for optimizing component pick-up and placement on a collect-and-place type machine in printed circuit board manufacturing. We present a two-phase heuristic that produces solutions of remarkable quality with respect to other known approaches in a reasonable amount of computational time. In the first phase, a construction procedure is used combining greedy aspects and solutions to subproblems modeled as a generalized traveling salesman problem and quadratic assignment problem. In the second phase, this initial solution is refined through an iterative framework requiring an integer programming step. A detailed description of the heuristic is provided and extensive computational results are presented.
Từ khóa
Tài liệu tham khảo
Ahmadi, J., Ahmadi, R., Matuso, H., Tirupati, D.: Component fixture positioning/sequencing for printed circuit board assembly with concurrent operations. Oper. Res. 43(3), 444–457 (1995)
Altinkemer, K., Kazaz, B., Köksalan, M., Moskowitz, H.: Optimization of printed circuit board manufacturing: integrated modeling and algorithms. Eur. J. Oper. Res. 124(2), 409–421 (2000)
Applegate, D., Bixby, R., Chvatal, V., Cook, W.: CONCORDE TSP solver. Website http://www.tsp.gatech.edu/concorde.html (2009)
Ayob, M., Kendall, G.: A triple objective function with a Chebychev dynamic pick-and-place point specification approach to optimise the surface mount placement machine. Eur. J. Oper. Res. 164(3), 609–626 (2005)
Ayob, M., Kendall, G.: A survey of surface mount device placement machine optimisation: machine classification. Eur. J. Oper. Res. 186(3), 893–914 (2008)
Ball, M.O., Magazine, M.J.: Sequencing of insertions in printed circuit board assembly. Oper. Res. 36(2), 192–201 (1988)
Barnhart, C., Johnson, E., Nemhauser, G., Savelsbergh, M., Vance, P.: Branch-and-price: column generation for solving huge integer programs. Oper. Res. 46(3), 316–329 (1998)
Burke, E.K., Cowling, P.I., Keuthen, R.: Effective heuristic and metaheuristic approaches to optimize component placement in printed circuit board assembly. In: Proceedings of the 2000 Congress on Evolutionary Computation, vol. 1 (2000)
Clarke, G., Wright, J.: Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12(4), 568–581 (1964)
Crama, Y., van de Klundert, J., Spieksma, F.C.R.: Production planning problems in printed circuit board assembly. Discrete Appl. Math. 123(1–3), 339–361 (2002)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)
Ellis, K.P., Kobza, J.E., Vittes, F.J.: Development of a placement time estimator function for a turret style surface mount placement machine. Robot. Comput. Integr. Manuf. 18(3–4), 241–254 (2002)
Ellis, K.P., Vittes, F.J., Kobza, J.E.: Optimizing the performance of a surface mount placement machine. IEEE Trans. Electron. Packag. Manuf. [see also IEEE Transactions on Components, Packaging and Manufacturing Technology, Part C: Manufacturing] 24(3), 160–170 (2001)
Feremans, C., Grigoriev, A.: Approximation schemes for the generalized geometric problems with geographic clustering. METEOR, Maastricht research school of Economics of TEchnology and ORganizations; University Library, Universiteit Maastricht (2004)
Fischetti, M., Salazar Gonzalez, J.J., Toth, P.: The symmetric generalized traveling salesman polytope. Networks 26(2), 113–123 (1995)
Fischetti, M., Toth, P.: The generalized traveling salesman and orienteering problems. Comb. Optim. 12, 609–662 (2002)
Franceschi, R.D., Fischetti, M., Toth, P.: A new ILP-based refinement heuristic for vehicle routing problems. Math. Program. 105(2), 471–499 (2006)
Golden, B.L., Raghavan, S., Wasil, E.A.: The vehicle routing problem: latest advances and new challenges, vol. 43 of Operations Research/Computer Science Interfaces Series. Springer (2008)
Grunow, M., Günther, H.O., Schleusener, M., Yilmaz, I.O.: Operations planning for collect-and-place machines in PCB assembly. Comput. Ind. Eng. 47(4), 409–429 (2004)
Gyorfi, J.S., Wu, C.H.: An efficient algorithm for placement sequence and feeder assignment problems with multiple placement-nozzles and independent link evaluation. IEEE Trans. Syst. Man Cybern.: Part A: Syst. Hum. 38(2), 437 (2008)
Haberle, K.R., Graves, R.J.: Cycle time estimation for printed circuit board assemblies. IEEE Trans. Electron. Packag. Manuf. [see also IEEE Transactions on Components, Packaging and Manufacturing Technology, Part C: Manufacturing], 24(3), 188–194 (2001)
Haimovich, M., Kan, A.H.G.R., Stougie, L.: Vehicle Routing: Methods and Studies. North-Holland, 1988, ch. Analysis of heuristics for vehicle routing problems, pp. 47–61
Hirvikorpi, M., Knuutila, T., Johnsson, M., Nevalainen, O.: A general approach to grouping of PCB assembly jobs. Int. J. Comput. Integr. Manuf. 18(8), 710–720 (2005)
Ho, W., Ji, P.: Component scheduling for chip shooter machines: a hybrid genetic algorithm approach. Comput. Oper. Res. 30(14), 2175–2189 (2003)
Ho, W., Ji, P., Dey, P.K.: Optimization of PCB component placements for the collect-and-place machines. Int. J. Adv. Manuf. Technol. 37(7), 828–836 (2008)
ILOG Inc.: CPLEX linear optimizer and mixed integer optimizer v. 11.0. Website http://www.ilog.com (2009)
Ji, P., Wan, Y.F.: Planning for printed circuit board assembly: the state-of-the-art review. Int. J. Comput. Appl. Technol. 14(4), 136–144 (2001)
Kazaz, B., Altınkemer, K.: Optimization of multi-feeder (depot) printed circuit board manufacturing with error guarantees. Eur. J. Oper. Res. 150(2), 370–394 (2003)
Knuutila, T., Pyottiala, S., Nevalainen, O.S.: Minimizing the number of pickups on a multi-head placement machine. J. Oper. Res. Soc. 58(1), 115 (2007)
Kulak, O., Yilmaz, I.O., Günther, H.O.: PCB assembly scheduling for collect-and-place machines using genetic algorithms. Int. J. Prod. Res. 45(17), 3949–3969 (2007)
Kumar, R., Luo, Z.: Optimizing the operation sequence of a chip placement machine using TSP model. IEEE Trans. Electron. Packag. Manuf. 26(1), 14–21 (2003)
Lapierre, S.D., Debargis, L., Soumis, F.: Balancing printed circuit board assembly line systems. Int. J. Prod. Res. 38(16), 3899–3911 (2000)
Leu, M.C., Wong, H., Ji, Z.: Planning of component placement/insertion sequence and feeder setup in PCB assembly using genetic algorithm. J. Electron. Packag. 115(4), 424 (1993)
Li, S., Hu, C., Tian, F.: Enhancing optimal feeder assignment of the multi-head surface mounting machine using genetic algorithms. Appl. Soft Comput. J. 8(1), 522–529 (2008)
Parkhi, K.: Printed circuit board: world outlook. Tech. Rep. 844-F2, Visant Strategies, Inc. (2007)
Salonen, K., Smed, J., Johnsson, M., Nevalainen, O.: Grouping and sequencing PCB assembly jobs with minimum feeder setups. Robot. Comput. Integr. Manuf. 22(4), 297–305 (2006)
Sarvanov, V.I., Doroshoko, N.N.: The approximate solution of the travelling salesman problem by a local search algorithm with scanning neighborhoods of factorial cardinality in cubic time. Softw.: Algorithms Programs 31, 11–13 (1981)
Seth, A., Klabjan, D., Ferreira, P.M.: Analyses of advanced iterated tour partitioning heuristics for generalized vehicle routing problems. Tech. rep., Northwestern University. http://www.klabjan.dynresmanagement.com (2009)
SIPLACE-Americas. Siemens automation electronic assembly systems. Siemens’ official website http://ea.automation.siemens.com (2009)
Smed, J., Johnsson, M., Johtela, T., Nevalainen, O.: Techniques and applications of production planning in electronics manufacturing systems. Tech. Rep. 320, Turku Centre for Computer Science (1999)
Su, C., Ho, L., Fu, H.: A novel tabu search approach to find the best placement sequence and magazine assignment in dynamic robotics assembly. Integr. Manuf. Syst. 9(6), 366–376 (1998)
Tirpak, T.M., Nelson, P.C., Asmani, A.J.: Optimization of revolver head SMT machines using adaptive simulated annealing (ASA). In: Proceedings of the Twenty-Sixth IEEE/CPMT International Electronics Manufacturing Technology Symposium, pp. 214–220 (2000)
Toth, P., Vigo, D.: The Vehicle Routing Problem. Monographs on discrete mathematics and applications. Society for Industrial and Applied Mathematics (2002)
Wilhelm, W.E., Arambula, I., Choudhry, N.N.D.: Optimizing picking operations on dual-head placement machines. IEEE Trans. Autom. Sci. Eng. [see also IEEE Transactions on Robotics and Automation] 3(1), 1–15 (2006)
Wilhelm, W.E., Choudhry, N.D., Damodaran, P.: A model to optimize placement operations on dual-head placement machines. Discrete Optim. 4(2), 232–256 (2007)
Wilhelm, W.E., Tarmy, P.K.: Circuit card assembly on tandem turret-type placement machines. IIE Trans. 35(7), 627–645 (2003)
Yilmaz, I., Günther, H.-O.: A group setup strategy for PCB assembly on a single automated placement machine. In: Haasis, H.-D., Kopfer, H., Schönberger, J. (eds.) Operations Research. Springer, Berlin, Heidelberg pp. 143–148 (2005)