Atama kısıtlı tip-1 montaj hattı dengeleme problemi: Bir kısıt programlama modeli yaklaşımı

Öz

Montaj hattı dengeleme problemi (MHDP) çevrim zamanı/istasyon sayısı ve görevler arasındaki öncelik ilişkileri gibi bazı kısıtlar içerir. Ancak, teknolojik ve organizasyonel kısıtlamalardan dolayı, uyumlu görevler, uyumsuz görevler, istasyon ve kaynak kısıtları gibi bazı diğer kısıtlar ile gerçek hayat üretim sistemlerinde karşılaşılabilmektedir. Bu çalışmada, bu kısıtların MHDP üzerindeki etkileri araştırılacaktır. Bu amaçla, bir kısıt programlama (KP) modeli önerilmiştir. Modelin amacı verilen bir çevrim zamanı değeri için istasyon sayısının en küçüklenmesidir (Tip-1 problemi). Önerilen KP modelinin karışık tamsayılı programlama (KTP) ve ABSALOM yaklaşımına göre kesinleştirilmiş optimal çözüm sayısı, optimal çözüm sayısı, iyi çözüm sayısı, optimal çözüm ile ulaşılan çözüm arasındaki görece fark ve ortalama toplam çözüm zamanı gibi performans ölçütleri açısından çözüm kalitesi araştırılmıştır. Ayrıca, önerilen yaklaşım literatürde yer alan problem örnekleri ile test edilmiştir ve modeller arasındaki karşılaştırmalı sonuçlar rapor edilmiştir. Sayısal deneyler, atama kısıtlarının problemin karmaşıklığını artırmasına rağmen, KP'nin MHDP'nin çözümünde etkin ve kaliteli bir çözüm yöntemi olduğunu göstermiştir.

Anahtar Kelimeler

• Montaj hattı dengeleme
• Tip-1 problemi
• Atama kısıtları
• Kısıt programlama
• Karışık tamsayılı programlama

Assembly line balancing type-1 problem with assignment restrictions: A constraint programming modeling approach

Abstract

The assembly line balancing problem (ALBP) contains some constraints which are cycle time/number of stations and precedence relations between tasks. However, due to the technological and organizational limitations, several other restrictions, such as linked tasks, incompatible tasks, station, and resource constraints, can be encountered in real production systems. In this study, we evaluate the effect of these restrictions on ALBP. For this purpose, a Constraint Programming (CP) model is proposed. The objective of the model is to minimize the number of stations for given cycle time (Type-1 problem). We investigate the solution quality of the proposed CP model according to the mixed-integer programming (MIP) and ABSALOM in terms of the several performance measurements such as the number of proofing optimal solution, number of the optimal solution, number of the best solution, relative gap between the solution with the optimal solution and average total solution time. Furthermore, the proposed approach is tested on the literature test instances, and the comparison results between models are reported. Although assignment restrictions increase the complexity of the problem, numerical experiments demonstrate that CP is an effective and high-quality solution method in solving ALBP.

Keywords

• Assembly line balancing
• Type-1 problem
• Assignment restrictions
• Constraint programming
• Mixed-integer programming

References

1. [1] Salveson ME. “The assembly line balancing problem”. Journal of Industrial Engineering, 6(1), 18-25, 1955.
2. [2] Bowman EH. “Assembly-line balancing by linear programming”. Operations Research, 8(3), 385-389, 1960.
3. [3] Küçükkoç İ. “A nondominated sorting ant colony optimization algorithm for complex assembly line balancing problem incorporating incompatible task sets”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 24(1), 141-152, 2018.
4. [4] Purnomo HD, Wee HM, Rau H. “Two-sided assembly lines balancing with assignment restrictions”. Mathematical and Computer Modelling, 57(1/2), 189-199, 2013.
5. [5] Tuncel G, Topaloğlu S. “Assembly line balancing with positional constraints task assignment restrictions and station paralleling: A case in an electronics company”. Computers &Industrial Engineering, 64(2), 602-609, 2013.
6. [6] Boysen N, Fliedner M. “A versatile algorithm for assembly line balancing”. European Journal of Operational Research, 184(1), 39-56, 2008.
7. [7] Liu CM, Chen CH. “Multi-section electronic assembly line balancing problems: A case study”. Production Planning & Control, 13(5), 451-461, 2002.
8. [8] Gadidov R, Wilhelm W. “A cutting plane approach for the single-product assembly system design problem”. International Journal of Production Research, 38(8), 1731-1754, 2000.

9. [9] Lapierre SD, Ruiz A, Soriano P. “Balancing assembly lines with tabu search”. European Journal of Operational Research, 168(3), 826-837, 2006.
10. [10] Pastor R, Corominas A. “Assembly line balancing with incompatibilities and bounded workstation loads”. Ricerca Operativa, 30(1), 23-45, 2000.
11. [11] Agpak K, Gökçen H. “Assembly line balancing: two resource constrained cases”. International Journal of Production Economics, 96(1), 129-140, 2005.
12. [12] Deckro RF. “Balancing cycle time and workstations”. IIE Transactions, 21(2), 106-111, 1989.
13. [13] Corominas A, Ferrer L, Pastor R. “Assembly line balancing: general resource-constrained case”. International Journal of Production Research, 49(12), 3527-3542, 2011.
14. [14] Sawik T. “Monolithic vs. hierarchical balancing and scheduling of a flexible assembly line”. European Journal of Operational Research, 143(1), 115-124, 2002. Wilhelm WE, Gadidov R. “A branch-and-cut approach for a generic multiple-product assembly-system design problem”. INFORMS Journal on Computing, 16(1), 39-55, 2004.
15. [15] Sikora CGS, Lopes TC, Magatã L. “Traveling worker assembly line (re)balancing problem: model reduction techniques and real case studies”. European Journal of Operational Research, 259(3), 949-971, 2017.
16. [16] Miralles C. “Solving procedures for the assembly line worker assignment and balancing problem: application to sheltered work centres for disabled”. XI Escuela Latinoamericana de Verano en Investigacionde Operaciones, Villa de Leyva, Colombia, 5-8 June 2005.
17. [17] Bautista J, Suárez R, Mateo M, Companys R. “Local search heuristics for the assembly line balancing problem with incompatibilities between tasks”. IEEE International Conference on Robotics and Automation, San Francisco, USA, 24-28 April 2000.
18. [18] Carnahan BJ, Norman BA, Redfern MS. “Incorporating physical demand criteria into assembly line balancing”. IIE Transactions, 33(10), 875-887, 2001.
19. [19] Kim YK, Kim Y, Kim YJ. “Two-sided assembly line balancing: a genetic algorithm approach”. Production Planning & Control, 11(1), 44-53, 2000.
20. [20] Quyen NTP, Chen JC, Yang CL. “Hybrid genetic algorithm to solve resource constrained assembly line balancing problem in footwear manufacturing”. Soft Computing, 21(21), 6279-6295, 2017.
21. [21] Rekiek B, De Lit P, Delchambre A. “Hybrid assembly line design and user’s preferences”. International Journal of Production Research, 40(5), 1095-1111, 2002.
22. [22] Rekiek B, De Lit P, Pellichero F, L’eglise T, Fouda P, Falkenauer E, Delchambre A. “A multiple objective grouping genetic algorithm for assembly line design”. Journal of Intelligent Manufacturing, 12(5/6), 467-485, 2001.
23. [23] Bautista J, Pereira J. “Ant algorithms for assembly line balancing”. International Workshop on ant Algorithms, Brussels, Belgium, 12-14 September, 2002.
24. [24] Bautista J, Pereira J. “Ant algorithms for a time and space constrained assembly line balancing problem”. European Journal of Operational Research, 177(3), 2016-2032, 2007.
25. [25] Vilarinho PM, Simaria AS. “Antbal: an ant colony optimization algorithm for balancing mixed model assembly lines with parallel workstations”. International Journal of Production Research, 44(2), 291-303, 2006.
26. [26] Pastor R, Andres C, Duran A, Perez M. “Tabu search algorithms for an industrial multi-product and multi-objective assembly line balancing problem with reduction of the task dispersion”. Journal of the Operational Research Society, 53(12), 1317-1323, 2002.
27. [27] Dong J, Zhang L, Xiao T. “A hybrid PSO/SA algorithm for bi-criteria stochastic line balancing with flexible task times and zoning constraints”. Journal of Intelligent Manufacturing, 29(4), 737-751, 2018.
28. [28] Vilarinho PM, Simaria AS. “A two-stage heuristic method for balancing mixed-model assembly lines with parallel workstations”. International Journal of Production Research, 40(6), 1405-1420, 2002.
29. [29] Lapierre S, Ruiz A. “Balancing assembly lines: An industrial case study”. Journal of the Operational Research Society, 55(6), 589-597, 2004.
30. [30] Lee TO, Kim Y, Kim YK. “Two-sided assembly line balancing to maximize work relatedness and slackness”. Computers & Industrial Engineering, 40(3), 273-292, 2001.
31. [31] Scholl A, Fliedner M, Boysen N. “Absalom: balancing assembly lines with assignment restrictions”. European Journal of Operational Research, 200(3), 688-701, 2010.
32. [32] Bockmayr A, Pisaruk N. “Solving assembly line balancing problems by combining IP and CP”. 6th Annual Workshop of ERCIM Working Group on Constraints, ERCIM, Prague, Czech Republic, 1-4 June 2001.
33. [33] Del Valle C, Marquez AA, Gasca RM, Toro M. “On selecting and scheduling assembly plans using constraint programming”. International Conference on Knowledge- Based and Intelligent Information and Engineering Systems, Oxford, UK, 3-5 September 2003.
34. [34] Pastor R, Ferrer L, García A. Evaluating Optimization Models to Solve SALBP. Editors: Gervasi O, Gavrilova ML. Proceeding of international Conference on Computational Science and its Applications ICCSA, 791-803, Berlin, Heidel-Berg, Germany, Springer, 2007.
35. [35] Topaloglu S, Salum L, Supciller AA. “Rule-based modelling and constraint programming based solution of the assembly line balancing problem”. Expert Systems with Applications, 39(3), 3484-3493, 2012.
36. [36] Alağaş HM, Yüzükırmızı M, Türker AK. “Balancing stochastic assembly lines using constraint programming and closed queueing networks”. Journal of the Faculty of Engineering and Architecture of Gazi University, 28(2), 231-240, 2013.
37. [37] Pınarbaşı M, Yüzükırmızı M, Toklu B. “Variability modelling and balancing of stochastic assembly lines”. International Journal of Production Research, 54(19), 5761-5782, 2016.
38. [38] Öztürk C, Tunalı S, Hnich B, Örnek MA. “Balancing and scheduling of flexible mixed model assembly lines”. Constraints, 18(3), 434-469, 2013.
39. [39] Özturk C, Tunali S, Hnich B, Ornek A. “Cyclic scheduling of flexible mixed model assembly lines with parallel stations”. Journal of Manufacturing Systems, 36(1), 147-158, 2015.
40. [40] Alağaş HM, Pınarbaşı M, Yüzükırmızı M, Toklu B. “Karma modelli tip-2 montaj hattı dengeleme problemi için bir kısıt programlama modeli”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 22(4), 340-348, 2016.
41. [41] Bukchin Y, Raviv T. “Constraint programming for solving various assembly line balancing problems”. Omega, 78(1), 57-68, 2018.
42. [42] Pınarbaşı M, Alakaş HM, Yüzükırmızı M. “A constraint programming approach to type-2 assembly line balancing problem with assignment restrictions”. Assembly Automation, 39(5), 813-826, 2019.
43. [43] Gamberini R, Grassi A, Rimini B. “A new multi-objective heuristic algorithm for solving the stochastic assembly line re-balancing problem”. International Journal of Production Economics, 100(2), 226-243, 2006.
44. [44] Apt KR. Principles of Constraint Programming. 1st ed. New York, USA, Cambridge University Press, 2003.