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

doi:10.1007/s40436-019-00256-3

Advances in Manufacturing ›› 2019, Vol. 7 ›› Issue (2): 117-132.doi: 10.1007/s40436-019-00256-3

• ARTICLES • 下一篇

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

Jia-Hua Zhang^1,2, Ai-Ping Li¹, Xue-Mei Liu¹

1 School of Mechanical Engineering, Tongji University, Shanghai 201804, People's Republic of China;
2 Department of Mechatronics Engineering, Wuxi Vocational Institute of Arts and Technology, Yixing 214206, Jiangsu, People's Republic of China

收稿日期:2018-08-11 修回日期:2019-02-14 出版日期:2019-06-25 发布日期:2019-06-19
通讯作者: Jia-Hua Zhang E-mail:1510278@tongji.edu.cn
基金资助:
This work is supported by the National Science and Technology Major Project of Ministry of Science and Technology of China (Grant No. 2013ZX04012-071) and the Shanghai Municipal Science and Technology Commission (Grant No. 15111105500).

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

Jia-Hua Zhang^1,2, Ai-Ping Li¹, Xue-Mei Liu¹

1 School of Mechanical Engineering, Tongji University, Shanghai 201804, People's Republic of China;
2 Department of Mechatronics Engineering, Wuxi Vocational Institute of Arts and Technology, Yixing 214206, Jiangsu, People's Republic of China

Received:2018-08-11 Revised:2019-02-14 Online:2019-06-25 Published:2019-06-19
Contact: Jia-Hua Zhang E-mail:1510278@tongji.edu.cn
Supported by:
This work is supported by the National Science and Technology Major Project of Ministry of Science and Technology of China (Grant No. 2013ZX04012-071) and the Shanghai Municipal Science and Technology Commission (Grant No. 15111105500).

摘要/Abstract

摘要： The type-Ⅱ 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.

The full text can be downloaded at https://link.springer.com/article/10.1007/s40436-019-00256-3

关键词: Mixed-model assembly line, Assembly line balancing, Robust optimization, Genetic algorithm (GA), Uncertainty

Abstract: The type-Ⅱ 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.

The full text can be downloaded at https://link.springer.com/article/10.1007/s40436-019-00256-3

Key words: Mixed-model assembly line, Assembly line balancing, Robust optimization, Genetic algorithm (GA), Uncertainty

Jia-Hua Zhang, Ai-Ping Li, Xue-Mei Liu. Hybrid genetic algorithm for a type-II robust mixed-model assembly line balancing problem with interval task times[J]. Advances in Manufacturing, 2019, 7(2): 117-132.

参考文献

1. Salveson ME (1955) The assembly line balancing problem. J Ind Eng 29(10):55-101
2. Baybars I (1986) A survey of exact algorithms for the simple assembly line balancing problem. Manag Sci 32(8):909-932
3. Boysen N, Fliedner M, Scholl A (2007) A classification of assembly line balancing problems. Eur J Oper Res 183(2):674-693
4. Battaïa O, Dolgui A (2013) A taxonomy of line balancing problems and their solution approaches. Int J Prod Econ 142(2):259-277
5. Simaria AS, Vilarinho PM (2004) A genetic algorithm based approach to the mixed-model assembly line balancing problem of type Ⅱ. Comput Ind Eng 47(4):391-407
6. Zhang WQ, Xu WT, Liu G et al (2017) An effective hybrid evolutionary algorithm for stochastic multiobjective assembly line balancing problem. J Intell Manuf 28(3):783-790
7. Dong JT, Zhang LX, Xiao TY (2018) A hybrid PSO/SA algorithm for bi-criteria stochastic line balancing with flexible task times and zoning constraints. J Intell Manuf 29(4):737-751
8. Van Hop N (2006) A heuristic solution for fuzzy mixed-model line balancing problem. Eur J Oper Res 168(3):798-810
9. Soyster AL (1973) Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper Res 21(5):1154-1157
10. Bertsimas D, Sim M (2004) The price of robustness. Oper Res 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 (2013) Assembly line balancing under uncertainty:robust optimization models and exact solution method. Comput Ind Eng 65(2):261-267
13. Gurevsky E, Hazır Ö, Battaïa O et al (2013) Robust balancing of straight assembly lines with interval task times. J Oper Res Soc 64(11):1607-1613
14. Nazarian E, Ko J (2013) Robust manufacturing line design with controlled moderate robustness in bottleneck buffer time to manage stochastic inter-task times. J Manuf Syst 32(2):382-391
15. Moreira MCO, Cordeau JF, Costa AM et al (2015) Robust assembly line balancing with heterogeneous workers. Comput Ind Eng 88:254-263
16. Hazır Ö, Dolgui A (2015) A decomposition based solution algorithm for U-type assembly line balancing with interval data. Comput Oper Res 59:126-131
17. Pereira J, Álvarez-Miranda E (2018) An exact approach for the robust assembly line balancing problem. Omega 78:85-98
18. 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
19. Saavedra-Moreno B, Salcedo-Sanz S, Paniagua-Tineo A et al (2011) Seeding evolutionary algorithms with heuristics for optimal wind turbines positioning in wind farms. Renew Energ 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 (2001) Using case retrieval to seed genetic algorithms. Int J Comput Intell Appl 1(1):71-82
22. Sewell EC, Jacobson SH (2012) A branch, bound, and remember algorithm for the simple assembly line balancing problem. INFORMS J Comput 24(3):433-442
23. Hoffmann TR (1963) Assembly line balancing with a precedence matrix. Manag Sci 9(4):551-562
24. Goldberg DE, Korb B, Deb K (1989) Messy genetic algorithms:motivation, analysis, and first results. Complex Syst 3(3):493-530
25. Rubinovitz J, Levitin G (1995) Genetic algorithm for assembly line balancing. Int J Prod Econ 41(1-3):343-354
26. Leu YY, Matheson LA, Rees LP (1994) Assembly-line balancing using genetic algorithms with heuristic-generated initial populations and multiple evaluation criteria. Decis Sci 25(4):581-606
27. Cheng RW, Gen M, Tsujimura Y (1999) A tutorial survey of jobshop scheduling problems using genetic algorithms, part Ⅱ:hybrid genetic search strategies. Comput Ind Eng 36(2):343-364
28. Triki H, Mellouli A, Hachicha W et al (2016) A hybrid genetic algorithm approach for solving an extension of assembly line balancing problem. Int J Comput Integr Manuf 29(5):504-519
29. Yun Y, Chung H, Moon C (2013) Hybrid genetic algorithm approach for precedence-constrained sequencing problem. Comput Ind Eng 65(1):137-147
30. Miltenburg J (2002) Balancing and scheduling mixed-model U-shaped production lines. Int J Flex Manuf Syst 14(2):119-151
31. Li HP, Zhang SQ, Zhang C et al (2017) A novel unsupervised Levy flight particle swarm optimization (ULPSO) method for multispectral remote-sensing image classification. Int J Remote Sens 38(23):6970-6992
32. Li L, Zhang Z, Guan C et al (2018) Multi-objective optimization for partial disassembly line balancing with goal-driven discrete cuckoo search. J Comput Aid Des Comput Graph 30(4):681-694

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价