Genetic Algorithm Application in a Dynamic PCB Assembly with Carryover Sequence- Dependent Setups

We consider a typical problem in the assembly of printed circuit boards (PCBs) in a two-machine flow shop system to simultaneously minimize the weighted sum of weighted tardiness and weighted flow time. The investigated problem is a group scheduling problem in which PCBs are assembled in groups and the interest is to find the best sequence of groups as well as the boards within each group to minimize the objective function value. The type of setup operation between any two board groups is characterized as carryover sequence-dependent setup time, which exactly matches with the real application of this problem. As a technical constraint, all of the boards must be kitted before the assembly operation starts (kitting operation) and by kitting staff. The main idea developed in this paper is to completely eliminate the role of kitting staff by assigning the task of kitting to the machine operator during the time he is idle which is referred to as integration of internal (machine) and external (kitting) setup times. Performing the kitting operation, which is a preparation process of the next set of boards while the other boards are currently being assembled, results in the boards to continuously enter the system or have dynamic arrival times. Consequently, a dynamic PCB assembly system is introduced for the first time in the assembly of PCBs, which also has characteristics similar to that of just-in-time manufacturing. The problem investigated is computationally very complex, meaning that finding the optimal solutions especially when the problem size gets larger is impossible. Thus, a heuristic based on Genetic Algorithm (GA) is employed. An example problem on the application of the GA developed is demonstrated and also numerical results of applying the GA on solving several instances are provided.

Authors:

• M. T. Yazdani Sabouni
• Rasaratnam Logendran

Keywords:

• Genetic algorithm
• Dynamic PCB assembly
• Carryover sequence-dependent setup times
• Multi-objective.

References:

[1] J.E. Schaller, "A new lower bound for the flow shop group scheduling
problem," Computers and Industrial Engineering, vol. 41, pp. 151-161,
2001.
[2] S.W. Choi, and Y.D. Kim, "Minimizing total tardiness on a twomachine
re-entrant flowshop," European Journal of Operational
Research, vol. 199, pp. 375-384, 2009.
[3] V.A. Strusevic, "Group technology approach to the open shop
scheduling problem with batch setup times," Operations Research
Letters, vol. 26, pp. 181-192, 2000.
[4] D.H. Eom, H.J. Shin, I.H. Kwun, J.K. Shim, and S.S. Kim, "Scheduling
jobs on parallel machines with sequence-dependent family setup times,"
International Journal of Advanced Manufacturing Technology, vol. 19,
pp. 926-932, 2002.
[5] J.E. Schaller, J.N.D. Gupta, and A.J. Vakharia, "Scheduling a flowline
manufacturing cell with sequence dependent family setup times,"
European Journal of Operational Research, vol. 125, pp. 324-339,
2000.
[6] Y.D. Kim, H.G. Lim, and M.W. Park, "Search heuristics for a flowshop
scheduling problem in a printed circuit board assembly process,"
European Journal of Operational Research, vol. 91, pp. 124-143, 1996.
[7] L.F. McGinnis, J.C. Ammons, M. Carlyle, L. Cranmer, G.W. Depuy,
K.P. Ellis, C.A. Tovey, and H. Xu, "Automated process planning for
printed circuit card assembly," IIE Transactions, vol. 24, pp. 18-30,
1992.
[8] C.S. Tang, and E.V. Denardo, "Models arising from a flexible
manufacturing machine, part 1: Minimization of the number of tool
switches," Operations Research, vol. 36, pp. 767-777, 1988.
[9] I.O. Yilmaz, and H.O. G├╝nther, "A group setup strategy for PCB
assembly on a single automated placement machine," Operations
Research Proceedings, Bremen, 2005, pp.143-148.
[10] V.J. Leon, and I.J. Jeong, "An improved group setup strategy for PCB
assembly," International Conference on Computational Science and its
Applications, Singapore, 2005, pp. 312-321.
[11] N. Van Hop, and N.N. Nagarur, "The scheduling problem of PCBs for
multiple non-identical parallel machines," European Journal of
Operational Research, vol. 158, pp. 577-594, 2004.
[12] J. Ashayeri, and W. Selen, " A planning and scheduling model for
onsertion in printed circuit board assembly," European Journal of
Operational Research, vol. 183, pp. 909-925, 2007.
[13] C.A. Gelogullari, and R. Logendran, "Group-scheduling problems in
electronics manufacturing," Journal of Scheduling, vol. 13, pp. 177-202,
2010.
[14] J.A. Holland, Adaptation in natural and artificial systems, University of
Michigan, Ann Arbor, 1975.
[15] K.A. De Jong, Analysis of the behavior of a class of genetic adaptive
systems, Doctoral Dissertation, University of Michigan, USA, 1975.
[16] D.E. Goldberg, Genetic algorithms in search, optimization and machine
learning, Massachusetts: Wesley, 1989.
[17] V.A. Cicirello, "Non-wrapping order crossover: An order preserving
crossover operator that respects absolute position," Proceedings of
Genetic and Evolutionary Computation Conference, GECCO, USA,
2006, pp. 1125-1131.
[18] O. Abdoun, and J. Abouchabaka, "A comparative study of adaptive
crossover operators for genetic algorithms to resolve the traveling
salesman problem," International Journal of Computer Applications,
vol. 31, pp. 49-57, 2011.
[19] S.S. Joshi, Phadnis, K. Srihari, and R. Seeniraj, "Use of simulation to
improve the kitting process at an EMS provider's facility," Computers
and Industrial Engineering Conference, Singapore, 2002.
[20] V. Pandya, and R. Logendran, "Weighted tardniess minimization in
flexible flow shops," Proceedings (CD-ROM), 19th Annual Industrial
Engineering Research Conference, Cancun, Mexico, 2010.
[21] M.T. Yazdani Sabouni, and R. Logendran, "Bicriteria carryover
sequence-dependent group scheduling in PCB manufacturing,"
Proceedings (CD-ROM), 20th Annual Industrial Engineering Research
Conference (IERC), Reno, NV, USA, 2011.
[22] ILOG CPLEX. IBM, Version 12.2, 2010.