Genetic and Memetic Algorithms for Sequencing a New JIT Mixed-Model Assembly Line

Document Type : Research Article

Authors

1 Corresponding Author, R. Tavakkoli-Moghaddam is a professor in Department of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran (e-mail: tavakoli@ut.ac.ir)

2 Y. Gholipour-Kanani is a faculty member in Department of Management, Qaemshahr Branch, Islamic Azad University, Qaemshahr, Iran (e-mail: gholipourkanani@yahoo.com)

3 R. Cheraghalizadeh has received her M.Sc. degree from Mazandaran University of Science & Technology, Babol, Iran (e-mail: r_cheraghalizadeh@yahoo.com)

Abstract

This paper presents a new mathematical programming model for the bi-criteria mixed-model assembly line balancing problem in a just-in-time (JIT) production system. There is a set of criteria to judge sequences of the product mix in terms of the effective utilization of the system. The primary goal of this model is to minimize the setup cost and the stoppage assembly line cost, simultaneously. Because of its complexity to be optimally solved in a reasonable time, we propose and develop two evolutionary meta-heuristics based on a genetic algorithm (GA) and a memetic algorithm (MA). The proposed heuristics are evaluated by the use of random iterations, and the related results obtained confirm their efficiency and effectiveness in order to provide good solutions for medium and large-scale problems.

Keywords

References

[1]     P. M. Vilarinho and A.S. Simaria, “A two-stage heuristic method for balancing mixed-model assembly lines with parallel workstations”, International Journal of Production Research, Vol. 40, pp. 1405-1420, 2002.
[2]     Y. Zhang and P.B. Luh, K.Yoneda, T. Kano and Y. Kyoya, “Mixed-Model Assembly Line Scheduling Using the Lagrangian Relaxation Technique”, Institute of Industrial Engineering, Vol. 32, 125-134, 2000.
[3]     N. V. Hop, “A heuristic solution for fuzzy mixed-model line balancing problem”, European Journal of Operational Research , Vol. 168 (3), pp. 798–810, 2006.
[4]     Y. Monden, Toyota Production System, second Ed. The Institute of Industrial Engineers, Norcross, GA, 1993.
[5]     J. Miltenburg, “Level schedules for mixed-model assembly lines in just-in-time production systems”, Management Science, Vol. 35, pp. 192–207, 1989.
[6]     J. Miltenburg, G. Steiner and S. Yeomans, “A dynamic programming algorithm for scheduling mixed-model just-in-time production systems”, Mathematical Computation Modeling, Vol. 13, pp. 57–66, 1990.
[7]     P.R. Inman and R. L. Bulfin, “Note on sequencing JIT mixed-model assembly lines”, Management Science, Vol. 37, pp. 904–910, 1991.
[8]     C.A. Yano, and R. Rachamadugu,  “Sequencing to minimize work overload in assembly lines with product options”, Management Science, Vol. 37, pp. 572–586, 1991.
[9]     J.F. Bard, E.M. Dar-El, and A. Shtub, “An analytic framework for sequencing mixed model”, International Journal of Production Research, Vol. 30, pp. 35–48, 1992.
[10]  K. Okamura, and H. Yamshina, “A heuristic algorithm for the assembly line model-mix sequencing problem to minimize the risk of stopping the conveyor”, International Journal of Production Research, Vol. 17, 233–247, 1979.
[11]  I. Baybars, “A survey of exact algorithms for the simple assembly line balancing problem”, Management Science, Vol. 2, pp. 909–932, 1986.
[12]  S. Ghosh, and R. J. Gagnon, “A comprehensive literature review and analysis of the design, balancing and scheduling of assembly systems”. International Journal of Production Research, Vol. 27, pp. 637-670, 1989.
[13]  A. Scholl, Balancing and sequencing of assembly lines, Physica, Heidelberg, second Ed., 1999.
[14]  Fokkert, J.I.V.Z.D. and de Kok, T.G., “The mixed and multimodel line balancing problem: A comparison”, European Journal of Operational Research, Vol. 100, pp. 399–412, 1997.
[15]  W.B. Helgeson, and D.P. Birnie, “Assembly line balancing using the ranked positional weight technique”, Journal of Industrial Engineering, Vol. 12, pp. 394–398, 1961.
[16]  A.L. Gutjahr and G.L. Nemhauser, “An algorithm for the line balancing problem”, Management Science, Vol. 11, pp. 308–315, 1964.
[17]  E. M. Mansoor, “Assembly Line Balancing – An Improvement on the Ranked Positional Weight Technique”, Journal of Industrial Engineering, Vol. 15, pp. 73-78, 1964. 
[18]  A. Kabir, and M. Tabucanon, “Batch-Model Assembly Line Balancing: A Multi- Attribute Decision Making Approach”, Int. J. of Production Economics, Vol. 41, pp. 193-201, 1995.
[19]  H. Gokcen and E. Erel, “A Goal Programming Approach to Mixed-Model Assembly Line Balancing Problem”, Int. J. of Production Economics, Vol. 48, pp. 177-185, 1997.
[20]  H. Gokcen and E. Erel, “Binary integer formulation for mixed-model assembly line balancing problem”, Computers and Industrial Engineering, Vol. 34, pp. 451–461, 1998.
[21]  E. Erel and H. Gokcen, “Shortest-route formulation of mixed-model assembly line balancing problem”, European Journal of Operational Research, Vol. 116, pp. 194–204, 1999.
[22]  R.F. Deckro and S. Rangachari, “A goal approach to assembly line balancing”, Computers and Operations Research, Vol. 17, pp. 509–521, 1990.
[23]  A.L. Gutjahr and G.L. Nemhauser, “An algorithm for the line balancing problem”, Management Science, Vol. 11, 1964, pp. 308– 315, 1964.
[24]  S.D. Roberts and C.D. Villa, “On a multiproduct assembly line-balancing problem”, AIIE Transactions, Vol. 2, pp. 361–364, 1970.
[25]  R. Tavakkoli-Moghaddam, G. Moslehi, M. Vasei and A. Azaron, “Optimal scheduling for a single machine to minimize the sum of maximum earliness and tardiness considering idle insert”, Applied Mathematics and Computation, Vol. 167, pp. 1430–1450, 2005.
[26]  R. Tavakkoli-Moghaddam, G. Moslehi, M. Vasei and A. Azaron, “A branch-and-bound algorithm for a single machine sequencing to minimize the sum of maximum earliness and tardiness with idle insert”, Applied Mathematics and Computation, Vol. 17, pp.  388–408, 2006.
[27]  J.F. Bard, A. Shtub and S.B. Joshi, “Sequencing mixed-model assembly lines to level parts usage and minimize the length”, International Journal of Production Research, Vol. 32, pp. 2431–2454, 1994.
[28]  C.J. Hyun, Y. Kim and Y.K. Kim, “A genetic algorithm for multiple objective sequencing problems in mixed model assembly lines”, Computers and Operations Research, Vol. 25, pp. 675–690, 1998. 
[29]  T. Korkmazel and S. Meral, “Bi-criteria sequencing methods for the mixed-model assembly line in just-in-time production systems”, European Journal of Operational Research, Vol. 131, pp. 188–207, 2001.
[30]  Y. Monden, Toyota Production System, Institute of Industrial Engineers Press, Atlanta, 1983.
[31]  P.R. McMullen and G.V. Frazier, “A simulated annealing approach to mixed-model sequencing with multiple objectives on a JIT line”, IIE Transactions, Vol. 3, pp. 679–686, 2000.
[32]  P.R. McMullen, “JIT sequencing for mixed-model assembly lines with setups using tabu search”, Production Planning and Control, Vol. 9, pp. 504–510, 1998.
[33]  P.R. McMullen, “An efficient frontier approach to addressing JIT sequencing problems with setups via search heuristics”, Computers and Industrial Engineering, Vol. 41, pp.335–353, 2001.
[34]  P.R. McMullen, “A Kohonen self-organizing map approach to addressing a multiple objective, mixed-model JIT sequencing problem”, International Journal of Production Economics, Vol. 72, pp. 59–71, 2001.
[35]  P.R. McMullen, “An ant colony optimization approach to addressing a JIT sequencing problem with multiple objectives”, Artificial Intelligence in Engineering, Vol. 15, pp. 309–317, 2001.
[36]  S.A. Mansouri, “A multi-objective genetic algorithm for mixed-model sequencing on JIT assembly lines”, European Journal of Operational Research, Vol. 167, pp. 696–716, 2005.
[37]  R. Tavakkoli-Moghaddam, N. Safaei and M. Babakhani, “Solving a dynamic cell formation problem with machine cost and alternative process plan by memetic algorithms”, in: O.B. Lupanov, O.M. Kasim-Zade, A.V. Chaskin, K. Steinhofel (Eds.), Stochastic Algorithms: Foundation and Applications, Lecture Notes in Computer Science, Springer-Verlag, Berlin, vol. 3777,
pp. 213–227, 2005.
[38]  S. Emde and N. Boysen, “Optimally routing and scheduling tow trains for JIT-supply of mixed-model assembly lines”, European Journal of Operational Research, Vol. 217,  287–299, 2012.
[39]  S. Emde and N. Boysen, “Optimally locating in-house logistics areas to facilitate JIT-supply of mixed-model assembly lines”, International Journal of Production Economics, Vo. 135, 393–402, 2012.
[40]  Q.Y. Dong, J. Lu, and Y. Gui, “Integrated Optimization of Production Planning and Scheduling in Mixed Model Assembly Line”, Procedia Engineering, Vol. 29, 3340–3347, 2012.
[41]  A. Hamzadayi and G. Yildiz, “A genetic algorithm based approach for simultaneously balancing and sequencing of mixed-model U-lines with parallel workstations and zoning constraints”, Computers & Industrial Engineering Volume 62, 206– 215, 2012.
[42]  X. Zenga, W. K. Wonga and S. Y. Leung, “An operator allocation optimization model for balancing control of the hybrid assembly lines using Pareto utility discrete differential evolution algorithm”, Computers & Operations Research, Vol. 39, 1145–1159,  2012.
[43]  J. Bautista, A. Cano and R. Alfaro, “Modeling and solving a variant of the mixed-model sequencing problem with work overload minimization and regularity constraints. An application in Nissan’s Barcelona Plant”, Expert Systems with Applications, Available online 14 March 2012.
[44]  N. Boysena and S. Bock, “Scheduling just-in-time part supply for mixed-model assembly lines”, European Journal of Operational Research, Vol. 211, 15-25, 2011.
[45]  Q. Zhenga,Y. Lia and M. Li, “Assembly Line Balancing Model Based on Ant Colony Optimization Algorithm”, Energy Procedia, Vol. 13, 5366–5372, 2011.
[46]  S. Akpınar and G. M. Bayhan, “A hybrid genetic algorithm for mixed model assembly line balancing problem with parallel workstations and zoning constraints”, Engineering Applications of Artificial Intelligence, Vol. 24, 449–457, 2011.
[47]  S.J. Hua, J. Kob, L. Weyandc, H.A. ElMaraghyd, T.K. Liene, Y. Korena, H. Bleyc, G. Chryssolourisf, N. Nasrg and M. Shpitalnih, “Assembly system design and operations for product variety”, CIRP Annals - Manufacturing Technology, Vol. 60,  715–733, 2011.
[48]  U, Özcan, “Balancing stochastic two-sided assembly lines: A chance-constrained, piecewise-linear, mixed integer program and a simulated annealing algorithm”, European Journal of Operational Research, Vol. 205, 81–97, 2010.
[49]  V. Giard and J. Jeunet, “Optimal sequencing of mixed models with sequence-dependent setups and utility workers on an assembly line”, International Journal of Production Economics, Vol. 123, 290–300, 2010.
[50]  L. Yang and X. Zhang, “Design and Application of Kanban Control System in a Multi-Stage, Mixed-Model Assembly Line”, Systems Engineering - Theory & Practice, Vol. 29, 64-72, 2009.
[51]  N. Boysena, M. Fliednerb and A. Scholl, “The product rate variation problem and its relevance in real world mixed-model assembly lines”, European Journal of Operational Research, Vol. 197,  818–824, 2009.
[52]  J.F. Bard, E.M. Dar-El and A. Shtub, , “An analytic framework for sequencing mixed model”, International Journal of Production Research, Vol. 30, pp. 35–48, 1992.
[53]  C.J. Hyun, Y. Kim and Y.K. Kim, “A genetic algorithm for multiple objective sequencing problems in mixed model assembly lines”, Computers and Operations Research, Vol. 25, pp. 675–690, 1998.
[54]  T. Hoffmann, “Eureka: A hybrid system for assembly line balancing”, Int. J. of Management Science, Vol. 38, pp. 39-47, 1992.
[55]  B.B. Malakooti, “Assembly line balancing with buffers by multiple criteria optimization”, Int. J. of Production Research, Vol. 32,
pp. 2159-2178, 1994.
[56]  P.P Sonekar, S.M. Sindhi, J.V.L. Venkatesh, B.M.  Dabade and S.P. Kallurkar, “A multiple criterion heuristic software for the practical assembly line balancing problem”, Stochastic Models Optimization Techniques and Computer Applications, pp. 303-313, 1994.
[57]  F. Boctor, “A multiple-rule heuristic for assembly line balancing”, Int. J. of Operational Research Society, Vol. 46, pp. 62-69, 1995.
[58]  A. Enmer, J. Favrel and J. Gauthie, “Balancing an assembly line for industrial truck engines”, Proceedings for IFAC Intelligent Manufacturing System, Bucharest, Romania, pp. 163-165, 1995.
[59]  R. Roy and M.J. Allchurch, “Development of a knowledge-based system for balancing complex mixed model assembly lines”, International Journal of Computer Integrated Manufacturing, Vol. 9, pp. 205-216, 1996.
[60]  K. Oh, “Expert line balancing system (ELBS)”, Computer & Industry Engineering, Vol. 33, pp. 303-306, 1997.
[61]  A. Kumar and B. Malakooti, “A knowledge-based system for solving multi-objective assembly line balancing problems”, International Journal of Production Research, Vol. 34, pp. 2533-2552, 1996.
[62]  B. Azinze and F. Partovi, “A knowledge based method for designing precedence networks and performing job allocation in line balancing”, Compute Industry Engineering, Vol. 18, pp. 351-364, 1990.
[63]  K. Sudhir and K. Rajagopalan, “An artificial approach to precedence network generation for assembly line balancing”, Computers in Industry, Vol. 18, pp. 177-191, 1992.
[64]  R. Tavakkoli-Moghaddam, Y. Gholipour-Kanani, and R. Cheraghalizadeh, “A genetic algorithm and memetic algorithm to sequencing and scheduling of cellular manufacturing systems”, International Journal of Management Science and Engineering Management, Vol. 3, pp. 119-130, 2008.
[65]  P. Moscato, On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms, Technical Report C3P 826. Caltech Concurrent Computation Program, California Institute of Technology, Pasadena: CA, 1989.
[66]  P. Moscato, “Memetic algorithms: A short introduction, In: D. Corne, M. Dorigo, F. Glover (Eds.), “New ideas in optimization”, McGraw-Hill, London, pp. 219-213, 1999.
[67]  A. S. Mendes, F. M. Muller, a.P.M. Franc and P. Moscato, Comparing meta-heuristic approaches for parallel machine scheduling problems with sequence-dependent setup times, Proceedings of the 15th Int. Conf. on CAD/CAM Robotics and Factories of the Future, A ` guas de Lindo` ia, SP, Brazil, 1999.
[68]  D.E. Goldberg, Genetic algorithms in search, optimization and machines learning, Addison-Wesley, Reading, MA, 1989.
[69]  J. Holland, Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor, 1975.
[70]  J. Knowles  and D. Corne, “The pareto archived evolution strategy: A new baseline algorithm for pareto multi-objective optimization”, The Proc. of CEC’99, 98–105, 1999.
AUT Journal of Modeling and Simulation
Volume 44, Issue 2 - Serial Number 2
November 2012
Pages 17-28

Files

Share

How to cite

Statistics