Basit düz ve U-tipi montaj hattı dengeleme problemleri için diferansiyel evrim algoritması

Abstract

Montaj hattı, seri olarak birbirine bağlı istasyonlardan oluşan bir akış tipi üretim sistemidir. Montaj hatlarının etkin olarak tasarımı, standart ürünlerin büyük miktarlarda üretiminde oldukça önemlidir.  Bu çalışmada, düz ve U-tipi basit montaj hattı dengeleme problemlerinin çözümü için bir diferansiyel evrim algoritması geliştirilmiştir. Popülasyon temelli evrimsel bir algoritma olan diferansiyel evrim algoritması, son yıllarda eniyileme problemlerinin çözümünde etkin olarak kullanılan bir yöntem olarak karşımıza çıkmaktadır. Önerilen algoritmanın çözüm başarısı, literatürde yaygın olarak kullanılan çok sayıda test problemi kullanılarak gerçekleştirilen deneyler ile değerlendirilmiştir. Sonuçlar algoritmanın etkinliğini göstermektedir.

Keywords

• Basit montaj hattı dengeleme,U-tipi hatlar,Diferansiyel evrim algoritması,Evrimsel algoritma

A differential evolution algorithm for simple straight and U-type assembly line balancing problems

Abstract

An assembly line is a flow-oriented production system in which the productive units performing the operations, referred to as stations, are aligned in a serial manner. Design of efficient assembly lines has considerable importance for the production of high-quantity standardized products. In this paper, a differential evolution algorithm is proposed to solve simple straight and U-type assembly line balancing problems. As a population-based evolutionary algorithm, differential evolution algorithm is seen as an effective method to solve optimization problems in recent years. A computational study is conducted by solving a large number of benchmark problems available in the literature to compare the performance of the proposed approach. The results show that the proposed approach performs quite effectively.

Keywords

• Simple assembly line balancing,U lines,Differential evolution algorithm,Evolutionary algorithm

References

1. Erkut H, Baskak M. Stratejiden Uygulamaya Tesis Tasarımı. İstanbul, Türkiye, İrfan Yayınevi, 2003.
2. Kara Y. U-Tipi Montaj Hattı Dengeleme Problemleri için Yeni Modeller ve Otomotiv Yan Sanayiinde Bir Uygulama. Doktora Tezi, Selçuk Üniversitesi, Konya, Türkiye, 2004.
3. Ajenblit DA, Wainwright RL. “Applying genetic algorithms to the u-shaped assembly line balancing problem”. Proceedings of the 1998 IEEE International Conference on Evolutionary Computation. Anchorage, Alaska, USA, 04-09 May 1998.
4. Salveson ME. “The assembly line balancing problem”. Journal of Industrial Engineering, 6(3), 18-25. 1955.
5. Bowman EH. “Assembly line balancing by linear programming”. Operations Research, 8(3), 385-389, 1960.
6. Klein M. “On assembly line balancing”. Operations Research, 11, 274-281, 1963.
7. Patterson JH, Albracht JJ. “Assembly-line balancing: Zero-one programming with fibonacci search”. Operations Research, 23(1), 166-172, 1975.
8. Talbot FB. Patterson JH. “An integer programming algorithm with network cuts for solving the assembly line balancing problem”. Management Science, 30(1), 85-99, 1984.

9. Jackson JR. “A computing procedure for a line balancing with a precedence matrix”. Management Science, 2, 261-272, 1956.
10. Held M, Karp RM, Shareshian R. “Assembly line balancing-dynamic programming with precedence constraints”. Operations Research, 11, 442-459, 1963.
11. Schrage L, Baker KR. “Dynamic programming solution of sequencing problems with precedence constraints”. Operations Research, 26, 444-449. 1978.
12. Johnson RV. “Assembly line balancing algorithms: Computational comparisons”. International Journal of Production Research, 19, 277-287, 1981.
13. Liu SB, Ng KM, Ong HL. “Branch-and-bound algorithms for simple assembly line balancing problem”. International Journal of Advanced Manufacturing Technology, 36, 169-177, 2008.
14. Dar-El EM. “MALB-a heuristic technique for balancing large scale single-model assembly lines”. AIIE Transactions, 5, 343-356, 1973.
15. Dar-El EM, Rubinovitch Y. “MUST-A multiple solutions technique for balancing single model assembly lines”. Management Science, 25, 1105-1114, 1979.
16. Baybars I. “An efficient heuristic method for the simple assembly line balancing problem”. International Journal of Production Research, 24, 149-166, 1986.
17. Tonge FM. “Assembly line balancing using probabilistic combinations of heuristics”. Management Science, 11, 727-735. 1965.
18. Moodie CL, Young HH. “A heuristic method of assembly line balancing for assumptions of constant or variable work element times”. Journal of Industrial Engineering, 16, 23-29, 1965.
19. Nevins AJ. “Assembly line balancing using best bud search”. Management Science, 18, 529-539, 1972.
20. Kim YJ, Kim YK, Cho Y. “A heuristic-based genetic algorithm for workload smoothing in assembly lines”. Computers and Operations Research, 25(2), 99-111. 1998.
21. Chan KCC, Hui PCL, Yeung KW, Ng FSF. “Handling the assembly line balancing problem in the clothing industry using a genetic algorithm”. International Journal of Clothing Science and Technology, 10(1), 21-37, 1998.
22. Sabuncuoğlu I, Erel E, Tanyer M. “Assembly line balancing using genetic algorithms”. Journal of Intelligent Manufacturing, 11, 295-310, 2000.
23. Ponnambalam SG, Aravindan P, Naidu GM. “A multiobjective genetic algorithm for solving assembly line balancing problem”. International Journal of Advanced Manufacturing Technology, 16, 341-352, 2000.
24. Goncalves JF, Almeida JR. “A hybrid genetic algorithm for assembly line balancing”. Journal of Heuristics, 8, 629-642. 2002.
25. Hwang RK, Katayama H, Gen M. “U-Shaped assembly line balancing problem with genetic algorithm”. International Journal of Production Research, 46(16), 4637-4649, 2008.
26. Scholl A, Voß S. “Simple assembly line balancing-heuristic approaches”. Journal of Heuristics, 2, 217-244, 1996.
27. Chiang WC. “The application of a tabu search metaheuristic to the assembly line balancing problem”. Annals of Operations Research, 77, 209-227, 1998.
28. Lapierre SD, Ruiz A, Soriano P. “Balancing assembly lines with tabu search”. European Journal of Operational Research, 168, 826-837, 2006.
29. 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.
30. McMullen PR, Tarasewich P. “Using ant techniques to solve the assembly line balancing problem”. IIE Transactions, 35, 605-617, 2003.
31. Baykasoğlu A, Özbakır L. “Discovering task assignment rules for assembly line balancing via genetic programming”. International Journal of Advanced Manufacturing Technology, 76, 417-434, 2015.
32. Heinrici A. A Comparison Between Simulated Annealing and Tabu Search With an Example From the Production Planning. Editor: Dyckhoff H. Operations research proceedings. 498-503, Berlin, Germany, Springer, 1994.
33. Suresh G, Sahu S. “Stochastic assembly line balancing using simulated annealing”. International Journal of Production Research, 32, 1801-1810, 1994.
34. McMullen PR, Frazier GV. “Using simulated annealing to solve a multi objective assembly line balancing problem with parallel workstations”. International Journal of Production Research, 36, 2717-2741, 1998.
35. Baykasoğlu A. “Multi-Rule multi-objective simulated annealing algorithm for straight and U type assembly line balancing problems”. Journal of Intelligent Manufacturing, 17, 217-232, 2006.
36. Özcan U, Toklu B. “A new hybrid improvement heuristic approach to simple straight and u-type assembly line balancing problems”. Journal of Intelligent Manufacturing, 20(1), 123-136, 2009.
37. Miltenburg GJ, Wijngaard J. “The u-line balancing problem”. Management Science, 40(10), 1378-1388, 1994.
38. Urban TL. “Note Optimal balancing of U-shaped assembly lines”. Management Science, 44(5), 738-741, 1998.
39. Scholl A, Klein R. “ULINO: Optimally balancing u-shaped JIT assembly lines”. International Journal of Production Research, 37(4), 721-736, 1999.
40. Erel E, Sabuncuoglu I, Aksu BA. “Balancing of U-type assembly systems using simulated annealing”. International Journal of Production Research, 39, 3003-3015, 2001.
41. Aase GR, Schniederjans MJ, Olson JR. “U-OPT: An analysis of exact U-Shaped line balancing procedures”. International Journal of Production Research, 41, 4185-4210, 2003.
42. Gökcen H, Ağpak K, Gencer C, Kizilkaya E. “A shortest route formulation of simple u-type assembly line balancing problem”. Applied Mathematical Modelling, 29, 373-380, 2005.
43. Gökcen H, Ağpak K. “A goal programming approach to simple u-line balancing problem”. European Journal of Operational Research, 171, 577-585, 2006.
44. Toklu B, Özcan U. “A fuzzy goal programming model for the simple u-line balancing problem with multiple objectives”. Engineering Optimization, 40(3), 191-204, 2008.
45. 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.
46. Nearchou AC. “Balancing large assembly lines by a new heuristic based on differential evolution method”. International Journal of Advanced Manufacturing Technology, 34, 1016-1029, 2007.
47. Mozdgir A, Mahdavi I, Badeleh IS, Solimanpur M. “Using the Taguchi method to optimize the differential evolution algorithm parameters for minimizing the workload smoothness index in simple assembly line balancing”. Mathematical and Computer Modelling, 57, 137-151, 2013.
48. Nearchou AC. “Multi-objective balancing of assembly lines by population heuristics”. International Journal of Production Research, 46(8), 2275-2297, 2008.
49. Nourmohammadi A, Zandieh M. “Assembly line balancing by a new multi-objective differential evolution algorithm based on TOPSIS”. International Journal of Production Research, 49(10), 2833-2855, 2011.
50. Zhang H, Yan Q, Liu Y, Jiang Z. “An integer-coded differential evolution algorithm for simple assembly line balancing problem of type 2”. Assembly Automation, 36(3), 246-261, 2016
51. Nearchou AC. “A differential evolution algorithm for simple assembly line balancing”. IFAC 16th Triennial World Congress, Prague, Czech republic, 4-8 July 2005.
52. Pitakaso R. “Differential evolution algorithm for simple assembly line balancing type 1 (SALBP-1)”. Journal of Industrial and Production Engineering, 32(2), 104-114, 2015.
53. Pitakaso R, Sethanan K. “Modified differential evolution algorithm for simple assembly line balancing with a limit on the number of machine types”. Engineering Optimization, 48(2), 253-271, 2016.
54. Rönkkönen JI, Kukkonen S, Price K. “Real-Parameter optimization with differential evolution”. IEEE Congress on Evolutionary Computation, Edinburgh, Scotland, 2-5 September 2005.