Abstract
A widespread supposition on mixed-model assembly line-balancing problems assigns a task, which is shared between two or more models to a single station. Bukchin and Rabinowitch (European Journal of Operational Research, 174:492–508, 2006) relaxed the restriction for mixed-model straight-line assembly line problems and allowed tasks common to multiple models to be assigned to different stations, called task duplication. In this paper, considering the same relaxation but for mixed-model U-shaped assembly lines, a novel genetic algorithm (GA) approach for solving large-scale problems is developed. Although superiorities of U-shaped assembly lines over straight lines have been discussed in several articles, this paper makes the advantage more tangible by providing a quantitative example. This paper also presents a novel two-stage genetic algorithm which is fittingly devised for solving the new proposed model. In order to evaluate the effectiveness of the GA, one small-scale and one medium-scale problem are solved using both the proposed GA and Lingo 8.0 software, and the obtained outcomes are compared. The computational results indicate that the GA is capable of providing high-quality solutions for small- and medium-scale problems in negligible central processing unit (CPU) times. It is worth mentioning that, for large-scale problems, such as Kim and Arcus test problems, no analogous results for those obtained by our proposed GA exist. To conclude, it can be said that the proposed GA performs well and is able to solve large-scale problems within acceptable CPU times.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ajenblit DA, Wainwright RL (1998) Applying genetic algorithms to the U-shaped assembly line balancing problem. In: Proceedings of the 1998 IEEE International Conference on Evolutionary Computation (ICEC’98), part of WCCI, Anchorage, Alaska, May 4–9, pp. 96–101
Baykasoglu A, Özbakir L (2007) Stochastic U-line balancing using genetic algorithms. Int J Adv Manuf Technol 32(1–2):139–147
Betts J, Mahmoud KI (1989) A method for assembly line balancing. Eng Costs Prod Econ 18:55–64
Bowman EH (1960) Assembly-line balancing by linear programming. Oper Res 8(3):385–389
Boysen N, Fliedner M, Scholl A (2008) Assembly line balancing: which model to use when? Int J Prod Econ 111:509–528
Bukchin J, Dar-El EM, Rubinovitz J (2002) Mixed-model assembly line design in a make-to-order environment. Comput Ind Eng 41:405–421
Bukchin Y, Rabinowitch I (2006) A branch-and-bound based solution approach for the mixed-model assembly line balancing problem for minimizing stations and task duplication costs. Eur J Oper Res 174:492–508
Chen Cheng-Wu (2009) Modeling and control for nonlinear structural systems via a NN-based approach. Expert Syst Appl 36:4765–4772. doi:10.1016/j.eswa.2008.06.0622009
Chen C, Lin J, Lee W, Chen C (2010) Fuzzy control for an oceanic structure: a case study in time-delay TLP system. J Vib Control 16:147–160. doi:10.1177/1077546309339424
Chiang WC, Urban TL (2006) The stochastic U-line balancing problem: a heuristic procedure. Eur J Oper Res 175:1767–1781
Erel E, Gokcen H (1999) Shortest route formulation of mixed-model assembly line balancing problem. Eur J Oper Res 116:194–204
Gokcen H, Erel E (1998) Binary integer formulation for mixed-model assembly line balancing problem. Comput Ind Eng 34:451–461
Gokcen H, Agpak K, Gencer C, Kizilkaya E (2005) A shortest route formulation of simple U-type assembly line balancing problem. Appl Math Model 29:373–380
Gokcen H, Agpak K (2006) A goal programming approach to simple U-line balancing problem. Eur J Oper Res 171:577–585
Gutjahr AL, Nemhauser GL (1964) An algorithm for the line balancing problem. Manage Sci 11:308–315
Hwang R, Katayama H (2009) A multi-decision genetic approach for workload balancing of mixed-model U-shaped assembly line systems. Int J Prod Res 47:3797–3822
Hwang R, Katayama H, Gen M (2008) U-shaped assembly line balancing problem with genetic algorithm. Int J Prod Res 46:4637–4649
Kara Y, Tekin M (2009) A mixed integer linear programming formulation for optimal balancing of mixed-model U-lines. Int J Prod Res 47:4201–4233
Kim YK, Kim YJ, Kim YH (1996) Genetic algorithms for assembly line balancing with various objectives. Comput Ind Eng 30(3):397–409
Lapierre SD, Ruiz A, Soriano P (2006) Balancing assembly lines with Tabu search. Eur J Oper Res 168:826–837
Liang S, Lu S, Chang J (2008) A novel two-stage impulse noise removal technique based on neural networks and fuzzy decision. IEEE Trans Fuzzy Syst 16(4):863–873
Miltenburg J, Wijngaard J (1994) The U-line line balancing problem. Manage Sci 40:1378–1388
Noorul Haq A, Jayaprakash J, Rengarajan K (2006) A hybrid genetic algorithm approach to mixed-model assembly line balancing. Int J Adv Manuf Technol 28(3–4):337–341
Patterson JH, Albracht JJ (1975) Assembly line balancing: zero-one programming with Fibonacci search. Oper Res 23:166–172
Rekiek B, Dolgui A, Delchambre A, Bratcu A (2002) State of art of optimization methods for assembly line design. Annu Rev Control 26:163–174
Sabuncuoglu I et al (2009) Ant colony optimization for the single model U-type assembly line balancing problem. Int J Prod Econ 120(2):287–300
Scholl A, Klein R (1999) ULINO: optimally balancing U-shaped JIT assembly lines. Int J Prod Res 37:721–736
Sparling D, Miltenburg J (1998) The mixed-model U-line balancing problem. Int J Prod Res 36:485–501
Tasan SO, Tunali S (2008) A review of the current applications of genetic algorithms in assembly line balancing. J Intell Manuf 19(1):49–69
Thomopoulos NT (1970) Mixed model line balancing with smoothed station assignments. Manage Sci 16(9):593–603
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kazemi, S.M., Ghodsi, R., Rabbani, M. et al. A novel two-stage genetic algorithm for a mixed-model U-line balancing problem with duplicated tasks. Int J Adv Manuf Technol 55, 1111–1122 (2011). https://doi.org/10.1007/s00170-010-3120-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-010-3120-6