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

Authors: M. T. Yazdani Sabouni, Rasaratnam Logendran

Abstract:

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.

Keywords: Genetic algorithm, Dynamic PCB assembly, Carryover sequence-dependent setup times, Multi-objective.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1072353

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.