Mixed-Model U-Shaped Assembly Line Balancing Problems with Coincidence Memetic Algorithm

Parames Chutima, Panuwat Olanviwatchai

Department of Industrial Engineering, Faculty of Engineering, Chulalongkorn University, Bangkok, Thailand.

DOI: 10.4236/jsea.2010.34040                

Abstract

Mixed-model U-shaped assembly line balancing problems (MMUALBP) is known to be NP-hard resulting in it being nearly impossible to obtain an optimal solution for practical problems with deterministic algorithms. This paper pre-sents a new evolutionary method called combinatorial optimisation with coincidence algorithm (COIN) being applied to Type I problems of MMUALBP in a just-in-time production system. Three objectives are simultaneously considered; minimum number workstations, minimum work relatedness, and minimum workload smoothness. The variances of COIN are also proposed, i.e. CNSGA II, and COIN-MA. COIN and its variances are tested against a well-known algo-rithm namely non-dominated sorting genetic algorithm II (NSGA II) and MNSGA II (a memetic version of NSGA II). Experimental results showed that COIN outperformed NSGA II. In addition, although COIN-MA uses a marginal CPU time than CNSGA II, its other performances are dominated.

Keywords

Assembly Line Balancing, Mixed-Model U-Line, JIT, COIN

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	N. Boysen, M. Fliedner and A. Scholl, “Assembly Line Balancing: Which Model to Use When?” International Journal of Production Economics, Vol. 111, No. 2, 2008, pp. 509-528.
[2]	R. J. Schonberger, “Japanese Manufacturing Techniques: Nine Hidden Lessons in Simplicity,” Free Press, New York, 1982, pp. 140-141.
[3]	J. Miltenburg, “U-Shaped Production Lines: A Review of Theory and Practice,” International Journal of Production Economics, Vol. 70, No. 3, 2001, pp. 201-214.
[4]	Y. Monden, “Toyota Production System,” 2nd Edition, Industrial Engineering Press, Institute of Industrial Engi-neering, Norcross, 1993.
[5]	G. J. Miltenburg and J. Wijngaard, “The U-Line Balancing Problem,” Management Science, Vol. 40, No. 10, 1994, pp. 1378-1388.
[6]	C. H. Cheng, G. J. Miltenburg and J. Motwani, “The Effect of Straight- and U-Shaped Lines on Quality,” IEEE Transactions on Engineering Management, Vol. 47, No. 3, 2000, pp. 321-334.
[7]	G. J. Miltenburg, “The Effect of Breakdowns on U-Shaped Production Lines,” International Journal of Production Research, Vol. 38, No. 2, 2000, pp. 353-364.
[8]	J. Miltenburg, “One-Piece Flow Manufacturing on U- Shaped Production Lines: A Tutorial,” IIE Transactions, Vol. 33, No. 4, 2001, pp. 303-321.
[9]	Y. Kara, U. Ozcan and A. Peker, “Balancing and Se-quencing Mixed-Model just-in-Time U-Lines with Multiple Objectives,” Applied Mathematics and Computation, Vol. 184, No. 2, 2007, pp. 566-588.
[10]	M. E. Salveson, “The Assembly Line Balancing Problem,” The Journal of Industrial Engineering, Vol. 6, No. 3, 1955, pp. 18-25.
[11]	I. Baybars, “A Survey of Exact Algorithms for the Simple Assembly Line Balancing Problem,” Management Science, Vol. 32, No. 8, 1986, pp. 909-932.
[12]	S. Ghosh and R. J. Gagnon, “A Comprehensive Literature Review and Analysis of the Design, Balancing and Sched-uling of Assembly Systems,” International Journal of Production Research, Vol. 27, No. 4, 1989, pp. 637-670.
[13]	E. Erel and S. C. Sarin, “A Survey of the Assembly Line Balancing Procedures,” Production Planning and Control, Vol. 9, No. 5, 1998, pp. 414-434.
[14]	C. Becker and A. Scholl, “A Survey on Problems and Methods in Generalized Assembly Line Balancing,” European Journal of Operational Research, Vol. 168, No. 3, 2006, pp. 694-715.
[15]	N. Boysen and M. Fliedner, “A Versatile Algorithm for Assembly Line Balancing,” European Journal of Opera-tional Research, Vol. 184, No. 1, 2008, pp. 39-56.
[16]	D. Sparling and J. Miltenburg, “The Mixed-Model U-Line Balancing Problem,” International Journal of Production Research, Vol. 36, No. 2, 1998, pp. 485-501.
[17]	G. J. Miltenburg, “Balancing U-Lines in a Multiple U- Line Facility,” European Journal of Operational Research, Vol. 109, No. 1, 1998, pp. 1-23.
[18]	T. L. Urban, “Optimal Balancing of U-Shaped Assembly Lines,” Management Science, Vol. 44, No. 5, 1998, pp. 738-741.
[19]	D. A. Ajenblit and R. L. Wainwright, “Applying Genetic Algorithms to the U-Shaped Assembly Line Balancing Problem,” Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, Alaska, 1998, pp. 96-101.
[20]	A. School and R. Klein, “ULINO: Optimally Balancing U-Shaped JIT Assembly Lines,” International Journal of Production Research, Vol. 37, No. 4, 1999, pp. 721-736.
[21]	E. Erel, I. Sabuncuoglu and B. A. Aksu, “Balancing of U-Type Assembly Systems Using Simulated Annealing,” International Journal of Production Research, Vol. 39, No. 13, 2001, pp. 3003-3015.
[22]	G. R. Aase, M. J. Schniederjans and J. R. Olson, “U-OPT: An Analysis of Exact U-Shaped Line Balancing Proce-dures,” International Journal of Production Research, Vol. 41, No. 17, 2003, pp. 4185-4210.
[23]	G. R. Aase, J. R. Olson and M. J. Schniederjans, “U- Shaped Assembly Line Layouts and their Impact on Labor Productivity: An Experimental Study,” European Journal of Operational Research, Vol. 156, No. 3, 2004, pp. 698- 711.
[24]	U. Martinez and W. S. Duff, “Heuristic Approaches to Solve the U-Shaped Line Balancing Problem Augmented by Genetic Algorithms,” Proceedings of the 2004 Systems and Information Engineering Design Symposium, Char-lottesville, 16 April 2004, pp. 287-293.
[25]	J. Balakrishnan, C.-H. Cheng, K.-C. Ho and K. K. Yang, “The Application of Single-Pass Heuristics for U-Lines,” Journal of Manufacturing Systems, Vol. 28, No. 1, 2009, pp. 28-40.
[26]	H. Gokcen and K. Agpak, “A Goal Programming Ap-proach to Simple U-Line Balancing Problem,” European Journal of Operational Research, Vol. 171, No. 2, 2006, pp. 577-585.
[27]	T. L. Urban and W.-C. Chiang, “An Optimal Piece-wise-Linear Program for the U-Line Balancing Problem with Stochastic Task Times,” European Journal of Opera-tional Research, Vol. 168, No. 3, 2006, pp. 771-782.
[28]	W.-C. Chiang and T. L. Urban, “The Stochastic U-Line Balancing Problem: A Heuristic Procedure,” European Journal of Operational Research, Vol. 175, No. 3, 2006, pp. 1767-1781.
[29]	Y. Kara, T. Paksoy and C. T. Chang, “Binary Fuzzy Goal Programming Approach to Single Model Straight and U-Shaped Assembly Line Balancing,” European Journal of Operational Research, Vol. 195, No. 2, 2009, pp. 335- 347. A. L. Arcus, “COMSOAL: A Computer Method of Sequencing Operations for Assembly Lines,” International Journal of Production Research, Vol. 4, No. 4, 1965, pp. 259-277.
[30]	A. Baykasoglu, “Multi-Rule Multi-Objective Simulated Annealing Algorithm for Straight and U Type Assembly Line Balancing Problems,” Journal of Intelligent Manu-facturing, Vol. 17, No. 2, 2006, pp. 217-232.
[31]	R. K. Hwang, H. Katayama and M. Gen, “U-Shaped As-sembly Line Balancing Problem with Genetic Algorithm,” International Journal of Production Research, Vol. 46, No. 16, 2008, pp. 4637-4649.
[32]	R. K. Hwang and H. Katayama, “A Multi-Decision Genetic Approach for Workload Balancing of Mixed-Model U-Shaped Assembly Line Systems,” International Journal of Production Research, Vol. 47, No. 14, 2009, pp. 3797- 3822.
[33]	A. Baykasoglu and T. Dereli, “Simple and U-Type As-sembly Line Balancing by Using an Ant Colony Based Algorithm,” Mathematical and Computational Applica-tions, Vol. 14, No. 1, 2009, pp. 1-12.
[34]	G. J. Miltenburg, “Balancing and Scheduling Mixed-Model U-Shaped Production Lines,” International Journal of Flexible Manufacturing Systems, Vol. 14, No. 2, 2002, pp. 119-151.
[35]	Y. K. Kim, S. J. Kim and J. Y. Kim, “Balancing and Se-quencing Mixed-Model U-Lines with a Co-Evolutionary Algorithm,” Production Planning and Control, Vol. 11, No. 8, 2000, pp. 754-764.
[36]	Y. K. Kim, J. Y. Kim and Y. Kim, “An Endosymbiotic Evolutionary Algorithm for the Integration of Balancing and Sequencing in Mixed-Model U-Lines,” European Journal of Operational Research, Vol. 168, No. 3, 2006, pp. 838-852.
[37]	S. Agrawal and M. K. Tiwari, “A Collaborative Ant Col-ony Algorithm to Stochastic Mixed-Model U-Shaped Dis-assembly Line Balancing and Sequencing Problem,” In-ternational Journal of Production Research, Vol. 46, No. 6, 2008, pp. 1405-1429.
[38]	I. Sabuncuoglu, E. Erel and A. Alp, “Ant Colony Optimi-zation for the Single Model U-Type Assembly Line Bal-ancing Problem,” International Journal of Production Economics, Vol. 120, No. 2, 2009, pp. 287-300.
[39]	Y. Kara, U. Ozcan and A. Peker, “An Approach for Bal-ancing and Sequencing Mixed-Model JIT U-Lines,” In-ternational Journal of Advanced Manufacturing Technol-ogy, Vol. 32, No. 11-12, 2007, pp. 1218-1231.
[40]	Y. Kara, “Line Balancing and Model Sequencing to Reduce Work Overload in Mixed-Model U-Line Production Environments,” Engineering Optimization, Vol. 40, No. 7, 2008, pp. 669-684.
[41]	A. Konak, D. W. Coit and A. E. Smith, “Multi-Objective Optimization Using Genetic Algorithms: A Tutorial,” Re-liability Engineering & System Safety, Vol. 91, No. 9, 2006, pp. 992-1007.
[42]	C. A. C. Coello, D. A. Veldhuizen and G. B. Lamont, “Evolutionary Algorithms for Solving Multi-Objective Problems,” Kluwer Academic Publishers, Dordrecht, 2002.
[43]	E. Zitzler and L. Thiele, “Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach,” IEEE Transactions on Evolutionary Computation, Vol. 3, No. 4, 1999, pp. 257-271.
[44]	C. M. Fonseca and P. J. Fleming, “Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization,” Proceedings of 5th International Conference on Genetic Algorithm, Urbana, June 1993, pp. 416- 423.
[45]	C. M. Fonseca and P. J. Fleming, “An overview of Evolu-tionary Algorithms in Multiobjective Optimization,” Evo-lutionary Computation, Vol. 3, No. 1, 1995, pp. 1-16.
[46]	K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA II,” IEEE Transactions on Evolutionary Computation, Vol. 6, No. 2, 2002, pp. 182-197.
[47]	D. Corne, M. Dorigo and F. Glover, “New Ideas in Opti-mization,” McGraw-Hill, London, 1999.
[48]	W. Wattanapornprom, P. Olanviwitchai, P. Chutima and P. Chongsatitvatana, “Multi-Objective Combinatorial Op-timisation with Coincidence Algorithm,” Proceedings of IEEE Congress on Evolutionary Computation, Norway, 11 February 2009, pp. 1675-1682.
[49]	J. R. Jackson, “A Computing Procedure for a Line Bal-ancing Problem,” Management Science, Vol. 2, No. 3, 1956, pp. 261-271.
[50]	D. E. Goldberg, “Genetic Algorithms in Search, Optimiza-tion, and Machine Learning,” Addison-Wesley, Boston, 1989.
[51]	J. Horn, N. Nafpliotis and D. E. Goldberg, “A Niched Pareto Genetic Algorithm for Multiobjective Optimization,” Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, Orlando, 27-29 June 1994.
[52]	P. Lacomme, C. Prins and M. Sevaux, “A Genetic Algo-rithm for a Bi-Objective Capacitated ARC Routing Prob-lem,” Computer & Operations Research, Vol. 33, No. 12, 2006, pp. 3473-3493.
[53]	P. Chutima and P. Pinkoompee, “An Investigation of Local Searches in Memetic Algorithms for Multi-Objective Sequencing Problems on Mixed-Model Assembly Lines,” Proceedings of Computers and Industrial Engineering, Beijing, 31 October-2 November 2008.
[54]	R. Kumar and P. K. Singh, “Pareto Evolutionary Algorithm Hybridized with Local Search for Bi-Objective TSP,” Studies in Computational Intelligence (Hybrid Evolutionary Algorithms), Springer, Berlin/Heidelberg, Vol. 75, 2007, pp. 361-398.
[55]	D. C. Montomery, “Design and Analysis of Experiments,” John Wiley & Sons, Inc., Hoboken, 2009.
[56]	N. T. Thomopoulos, “Mixed Model Line Balancing with Smoothed Station Assignment,” Management Science, Vol. 14, No. 2, 1970, pp. B59-B75.
[57]	A. L. Arcus, “COMSOAL: A Computer Method of Se-quencing Operations for Assembly Lines,” International Journal of Production Research, Vol. 4, No. 4, 1965, pp. 259-277.