Hybrid genetic algorithm for a type-II robust mixed-model assembly line balancing problem with interval task times

Abstract

The type-II mixed-model assembly line balancing problem with uncertain task times is a critical problem. This paper addresses this issue of practical significance to production efficiency. Herein, a robust optimization model for this problem is formulated to hedge against uncertainty. Moreover, the counterpart of the robust optimization model is developed by duality. A hybrid genetic algorithm (HGA) is proposed to solve this problem. In this algorithm, a heuristic method is utilized to seed the initial population. In addition, an adaptive local search procedure and a discrete Levy flight are hybridized with the genetic algorithm (GA) to enhance the performance of the algorithm. The effectiveness of the HGA is tested on a set of benchmark instances. Furthermore, the effect of uncertainty parameters on production efficiency is also investigated.

Keywords

Mixed-model assembly line / Assembly line balancing / Robust optimization / Genetic algorithm (GA) / Uncertainty

References

[1] Salveson ME. The assembly line balancing problem. J Ind Eng, 1955, 29(10): 55-101.

[2] Baybars I. A survey of exact algorithms for the simple assembly line balancing problem. Manag Sci, 1986, 32(8): 909-932.

[3] Boysen N, Fliedner M, Scholl A. A classification of assembly line balancing problems. Eur J Oper Res, 2007, 183(2): 674-693.

[4] Battaïa O, Dolgui A. A taxonomy of line balancing problems and their solution approaches. Int J Prod Econ, 2013, 142(2): 259-277.

[5] Simaria AS, Vilarinho PM. A genetic algorithm based approach to the mixed-model assembly line balancing problem of type II. Comput Ind Eng, 2004, 47(4): 391-407.

[6] Zhang WQ, Xu WT, Liu G, et al. An effective hybrid evolutionary algorithm for stochastic multiobjective assembly line balancing problem. J Intell Manuf, 2017, 28(3): 783-790.

[7] Dong JT, Zhang LX, Xiao TY. A hybrid PSO/SA algorithm for bi-criteria stochastic line balancing with flexible task times and zoning constraints. J Intell Manuf, 2018, 29(4): 737-751.

[8] Van Hop N. A heuristic solution for fuzzy mixed-model line balancing problem. Eur J Oper Res, 2006, 168(3): 798-810.

[9] Soyster AL. Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper Res, 1973, 21(5): 1154-1157.

[10] Bertsimas D, Sim M. The price of robustness. Oper Res, 2004, 52(1): 35-53.

[11] Al-e-hashem SMJM, Aryanezhad MB, Malekly H et al (2009) Mixed model assembly line balancing problem under uncertainty. In: Paper presented at the 2009 international conference on computers and industrial engineering, pp 233–238

[12] Hazır Ö, Dolgui A. Assembly line balancing under uncertainty: robust optimization models and exact solution method. Comput Ind Eng, 2013, 65(2): 261-267.

[13] Gurevsky E, Hazır Ö, Battaïa O, et al. Robust balancing of straight assembly lines with interval task times. J Oper Res Soc, 2013, 64(11): 1607-1613.

[14] Nazarian E, Ko J. Robust manufacturing line design with controlled moderate robustness in bottleneck buffer time to manage stochastic inter-task times. J Manuf Syst, 2013, 32(2): 382-391.

[15] Moreira MCO, Cordeau JF, Costa AM, et al. Robust assembly line balancing with heterogeneous workers. Comput Ind Eng, 2015, 88: 254-263.

[16] Hazır Ö, Dolgui A. A decomposition based solution algorithm for U-type assembly line balancing with interval data. Comput Oper Res, 2015, 59: 126-131.

[17] Pereira J, Álvarez-Miranda E. An exact approach for the robust assembly line balancing problem. Omega, 2018, 78: 85-98.

[18] Tasan SO, Tunali S. A review of the current applications of genetic algorithms in assembly line balancing. J Intell Manuf, 2008, 19(1): 49-69.

[19] Saavedra-Moreno B, Salcedo-Sanz S, Paniagua-Tineo A, et al. Seeding evolutionary algorithms with heuristics for optimal wind turbines positioning in wind farms. Renew Energ, 2011, 36(11): 2838-2844.

[20] Osaba E, Carballedo R, Diaz F et al (2014) On the influence of using initialization functions on genetic algorithms solving combinatorial optimization problems: a first study on the TSP. In: IEEE Conference on Evolving and Adaptive Intelligent Systems

[21] Oman S, Cunningham P. Using case retrieval to seed genetic algorithms. Int J Comput Intell Appl, 2001, 1(1): 71-82.

[22] Sewell EC, Jacobson SH. A branch, bound, and remember algorithm for the simple assembly line balancing problem. INFORMS J Comput, 2012, 24(3): 433-442.

[23] Hoffmann TR. Assembly line balancing with a precedence matrix. Manag Sci, 1963, 9(4): 551-562.

[24] Goldberg DE, Korb B, Deb K. Messy genetic algorithms: motivation, analysis, and first results. Complex Syst, 1989, 3(3): 493-530.

[25] Rubinovitz J, Levitin G. Genetic algorithm for assembly line balancing. Int J Prod Econ, 1995, 41(1–3): 343-354.

[26] Leu YY, Matheson LA, Rees LP. Assembly-line balancing using genetic algorithms with heuristic-generated initial populations and multiple evaluation criteria. Decis Sci, 1994, 25(4): 581-606.

[27] Cheng RW, Gen M, Tsujimura Y. A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies. Comput Ind Eng, 1999, 36(2): 343-364.

[28] Triki H, Mellouli A, Hachicha W, et al. A hybrid genetic algorithm approach for solving an extension of assembly line balancing problem. Int J Comput Integr Manuf, 2016, 29(5): 504-519.

[29] Yun Y, Chung H, Moon C. Hybrid genetic algorithm approach for precedence-constrained sequencing problem. Comput Ind Eng, 2013, 65(1): 137-147.

[30] Miltenburg J. Balancing and scheduling mixed-model U-shaped production lines. Int J Flex Manuf Syst, 2002, 14(2): 119-151.

[31] Li HP, Zhang SQ, Zhang C, et al. A novel unsupervised Levy flight particle swarm optimization (ULPSO) method for multispectral remote-sensing image classification. Int J Remote Sens, 2017, 38(23): 6970-6992.

[32] Li L, Zhang Z, Guan C, et al. Multi-objective optimization for partial disassembly line balancing with goal-driven discrete cuckoo search. J Comput Aid Des Comput Graph, 2018, 30(4): 681-694.

Funding

Ministry of Science and Technology http://dx.doi.org/10.13039/100007225(2013ZX04012-071)

Science and Technology Commission of Shanghai Municipality http://dx.doi.org/10.13039/501100003399(15111105500)