Using Genetic Algorithms in Assembly Line Balancing: a New Method

Abstract

Today, the use of industrial automation applications has increased. Along with this, different artificial intelligence solutions have been included in production These solutions can directly control production or they can plan the production. One of these application areas is assembly lines. Assembly lines are production lines in which parts of products are systematically assembled. Assembly lines need to be changed according to the quantity or type of request. In this process, assembly line balancing problem is encountered. In this study, a new crossover and mutation method is proposed in the use of genetic algorithms, one of the stochastic search methods, for the assembly line balancing problem. Furthermore, the proposed method is improved by a local search procedure used in station-oriented task distribution. The developed algorithms are written in Python programming language and tested on an assembly line. With Genetic Algorithms, an increase of 1-1.5% in line efficiency was observed. In experiments with the local exploration process, an increase of 0.1-0.2% was observed.

Keywords

• Assembly Line Balancing
• Genetic Algorithm
• Optimization
• Production Planning

Montaj Hattı Dengelemede Genetik Algoritmaların Kullanımı: Yeni Bir Yöntem

Abstract

Günümüzde endüstriyel otomasyon uygulamalarının yaygınlaşmasıyla birlikte, farklı yapay zeka çözümleri üretime dahil olmuştur. Bu çözümler, üretimi doğrudan kontrol edebilmekte ve üretimin planlamasını kendi kendine yapabilmektedir. Planlama aşamasının otomatik yapılabileceği alanlardan bir tanesi de montaj hatlarıdır. Montaj hatları, ürünlerin parçalarının sistematik bir şekilde birleştirildiği üretim hatlarıdır. Montaj hatlarının, gelen taleplerin miktarı veya çeşidine göre yeniden düzenlenmesi gerekmektedir. Düzenleme sürecinde, montaj hattı dengeleme problemiyle karşılaşırız. Bu çalışmada montaj hattı dengeleme problemi için stokastik arama yöntemlerinden genetik algoritmaların kullanımında yeni bir çaprazlama ve mutasyon yöntemi önerilmiştir. Bu yöntemin bulduğu sonuçlar, istasyon bazlı görev dağıtımında kullanılan bir yerel arama prosedürüyle güçlendirilmiştir. Geliştirilen algoritmalar Python programlama dili ile kodlanmış ve bir montaj hattı üzerinden test edilmiştir. Genetik Algoritmalaların kullanıldığı deneylerde hat etkinliğinde %1-1.5 artışa rastlanmıştır. Yerel arama prosödürüyle yapılan deneylerde %0.1-0.2 arası artış gözlenmiştir.

Keywords

• Montaj Hattı Dengeleme
• Genetik Algoritma
• Optimizasyon
• Üretim Planlama

References

1. Mahto, D. G., and Anjani Kumar. "An empirical investigation of assembly line balancing techniques and optimized implementation approach for efficiency improvements." Global Journal of Researches in Engineering Mechanical and Mechanics Engineering 12 (2012).
2. “ProPlanner | Line Balancing.” ProPlanner, y.y. t.y. Web. 4 Aralık 2020
3. Lazarev, A. A., E. R. Gafarov, and A. Dolgui. "Notes on Complexity of the Simple Assembly Line Balancing Problem." (2012)..
4. Amen, Matthias. "Heuristic methods for cost-oriented assembly line balancing: A survey." International Journal of Production Economics 68.1 (2000): 1-14.
5. Fang, Yilin, et al. "Multi-objective evolutionary simulated annealing optimisation for mixed-model multi-robotic disassembly line balancing with interval processing time." International Journal of Production Research 58.3 (2020): 846-862.
6. Kucukkoc, Ibrahim, and David Z. Zhang. "Mixed-model parallel two-sided assembly line balancing problem: A flexible agent-based ant colony optimization approach." Computers & Industrial Engineering 97 (2016): 58-72.
7. Chiang, Wen-Chyuan. "The application of a tabu search metaheuristic to the assembly line balancing problem." Annals of Operations Research 77 (1998): 209-227.
8. Tasan, Seren Ozmehmet, and Semra Tunali. "A review of the current applications of genetic algorithms in assembly line balancing." Journal of intelligent manufacturing 19.1 (2008): 49-69.

9. Bautista, Joaquín, Cristina Batalla-García, and Rocío Alfaro-Pozo. "Models for assembly line balancing by temporal, spatial and ergonomic risk attributes." European Journal of Operational Research 251.3 (2016): 814-829.
10. Anderson, Edward J., and Michael C. Ferris. "Genetic algorithms for combinatorial optimization: the assemble line balancing problem." ORSA Journal on Computing 6.2 (1994): 161-173.
11. Bautista, Joaquin, et al. "Local search heuristics for the assembly line balancing problem with incompatibilities between tasks." Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065). Vol. 3. IEEE, 2000.
12. Eryürük, Selin Hanife. Bir konfeksiyon işletmesinde montaj hattı dengeleme. Diss. Fen Bilimleri Enstitüsü, 2005.
13. Kara, Yakup. U-tipi montaj hattı dengeleme problemleri için yeni modeller ve otomotiv yan sanayiinde bir uygulama. Diss. Selçuk Üniversitesi Sosyal Bilimler Enstitüsü, 2004..
14. Akın, Nalan Gülten. "Kanepe Montaj Hattının Dengelenmesi ve Benzetim Yöntemi İle Sınanması." Çankırı Karatekin Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi 5.1 (2015): 95-120..
15. Yegul, Mustafa Fatih, Kursad Agpak, and Mustafa Yavuz. "A new algorithm for U-shaped two-sided assembly line balancing." Transactions of the Canadian Society for Mechanical Engineering 34.2 (2010): 225-241.
16. Zülcha, Gert, and Michael Zülchb. "Ergonomic evaluation of a hybrid U-shaped assembly system." Proceedings 19th Triennial Congress of the IEA. Vol. 9. 2015..
17. Akagi, Fumio, Hirokazu Osaki, and Susumu Kikuchi. "A method for assembly line balancing with more than one worker in each station." The International Journal of Production Research 21.5 (1983): 755-770..
18. Özcan, Uğur, and Bilal Toklu. "A tabu search algorithm for two-sided assembly line balancing." The International Journal of Advanced Manufacturing Technology 43.7-8 (2009): 822.
19. Chiang, Wen-Chyuan. "The application of a tabu search metaheuristic to the assembly line balancing problem." Annals of Operations Research 77 (1998): 209-227.
20. Lapierre SD, Ruiz A, Soriano P. “Balancing assembly lines with tabu search”. European Journal of Operational Research, 168, 826-837, 2006.
21. Storn R, Price K. “Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces”. Journal of Global Optimization, 11, 341-359, 1997
22. Bautista J, Pereira J. “Ant algorithms for a time and space constrained assembly line balancing problem”. European Journal of Operational Research, 177, 2016-2032, 2007.
23. McMullen, Patrick R., and Peter Tarasewich. "Using ant techniques to solve the assembly line balancing problem." IIE transactions 35.7 (2003): 605-617.
24. Suresh, G., and S. Sahu. "Stochastic assembly line balancing using simulated annealing." The International Journal of Production Research 32.8 (1994): 1801-1810.
25. Erel, E., I. Sabuncuoglu, and B. A. Aksu. "Balancing of U-type assembly systems using simulated annealing." International Journal of Production Research 39.13 (2001): 3003-3015.
26. Sabuncuoglu, Ihsan, Erdal Erel, and M. Tanyer. "Assembly line balancing using genetic algorithms." Journal of intelligent manufacturing 11.3 (2000): 295-310.
27. Ajenblit, Debora A., and Roger L. Wainwright. "Applying genetic algorithms to the U-shaped assembly line balancing problem." 1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence (Cat. No. 98TH8360). IEEE, 1998.
28. Helgeson, W. B., and Dunbar P. Birnie. "Assembly line balancing using the ranked positional weight technique." Journal of industrial engineering 12.6 (1961): 394-398.
29. Steven T. Hackman, Michael J. Magazine and T. S. Wee, "Fast, effective algorithms for simple assembly line balancing problems", Operations Research, 37(6), pp. 916-924, 1989.
30. Ponnambalam, S. G., P. Aravindan, and G. Mogileeswar Naidu. "A comparative evaluation of assembly line balancing heuristics." The International Journal of Advanced Manufacturing Technology 15.8 (1999): 577-586.
31. Arcus, Albert L. "A computer method of sequencing operations for assembly lines." International Journal of Production Research 4.4 (1965): 259-277.
32. udea Pearl, J. "The Logic of Representing Dependencies by Directed Graphs." (1937).
33. Gonçalves, José Fernando, and Jorge Raimundo De Almeida. "A hybrid genetic algorithm for assembly line balancing." Journal of heuristics 8.6 (2002): 629-642.
34. Özkan, Raşit. Tek Modelli Deterministik Montaj Hattı Dengeleme Problemlerine Genetik Algoritma İle Çözüm Yaklaşımı. Diss. Fen Bilimleri Enstitüsü, 2003.
35. Li, Zixiang, Ibrahim Kucukkoc, and J. Mukund Nilakantan. "Comprehensive review and evaluation of heuristics and meta-heuristics for two-sided assembly line balancing problem." Computers & Operations Research 84 (2017): 146-161.