Tip-II Basit Montaj Hattı Dengeleme Probleminin Bölge Kısıtlamaları ile Çözümüne Yönelik Benders Ayrıştırma Algoritması

Year 2022, , 400 - 415, 30.08.2022

Alper Hamzadayı

https://doi.org/10.53433/yyufbed.1080238

Abstract

Bu makale, işler ve istasyonlar arasındaki uyumluluğu (veya başka türlü) dikkate alarak ve istasyonlar arasındaki öncelik ilişkilerini gözlemleyerek belirli bir iş istasyonu kümesine bir dizi iş atamaktan oluşan, bölgeleme kısıtlamaları ile tip II montaj hattı dengeleme problemi ile ilgilidir. Amaç, herhangi bir istasyondaki en son tamamlanma süresini en aza indirmektir. Bu makale, Benders ayrıştırmasının yapısına uygun olarak bir dizi kısıtlamayı yinelemeli olarak ortaya koyan bir problem formasyonuna dayanan kesin bir algoritmayı açıklamaktadır. Algoritma, üst sınırlar oluşturmak için karar değişkenleri, kombinatoryel kesimler ve referanslı bir yerel arama üzerinde bir dizi sınırlayıcı kısıtlama içerir. Algoritmanın problem için en gelişmiş yaklaşımlardan daha üstün olduğu kıyaslamalı örnekler üzerinde kapsamlı hesaplama deneyleri ile gösterilmiştir.

Keywords

Benders ayrıştırması, Bölge kısıtlamaları, Montaj hattı dengeleme, Referanslı yerel arama, Tip-II

Benders Decomposition Algorithm for Solving the Type-II Simple Assembly Line Balancing Problem with Zoning Restrictions

Abstract

This paper considers the type-II assembly line balancing problem under zoning constraints, where a number of tasks must be assigned to a number of workstations while respecting compatibility (or otherwise) between tasks and stations, and by observing the precedence relationships between tasks. The objective is to minimize the latest completion time at any station. The paper proposes an exact algorithm that takes into account an exact formulation of the problem as well as iteratively introduces a set of constraints in the spirit of Benders decomposition. In addition to boundary constraints on the decision variables, the algorithm makes use of combinatorial cuts and a referenced local search in order to generate upper bounds. The algorithm is extensively evaluated on benchmark instances, which indicates that it outperforms the state-of-the-art approaches to the problem.

Keywords

Assembly line balancing, Benders decomposition, Referenced local search, Type-II, Zoning restrictions

References

• Akpınar, S., & Bayhan, G. M. (2011). A hybrid genetic algorithm for mixed model assembly line balancing problem with parallel workstations and zoning constraints. Engineering Applications of Artificial Intelligence, 24(3), 449-457. doi: 10.1016/j.engappai.2010.08.006
• Akpinar, S., Elmi, A., & Bektaş, T. (2017). Combinatorial Benders cuts for assembly line balancing problems with setups. European Journal of Operational Research, 259(2), 527-537. doi: 10.1016/j.ejor.2016.11.001
• Amen, M. (2006). Cost-oriented assembly line balancing: Model formulations, solution difficulty, upper and lower bounds. European Journal of Operational Research, 168(3), 747-770. doi: 10.1016/j.ejor.2004.07.026
• Balas, E. (1965). An additive algorithm for solving linear programs with zero-one variables. Operations Research, 13(4), 517-546. doi: 10.1287/opre.13.4.517
• Baybars, İ. (1986). A survey of exact algorithms for the simple assembly line balancing problem. Management Science, 32(8), 909-932. doi: 10.1287/mnsc.32.8.909
• Baykasoglu, A., & Dereli, T. (2008). Two-sided assembly line balancing using an ant-colony based heuristic. The International Journal of Advanced Manufacturing Technology, 36(5-6), 582-588. doi: 10.1007/s00170-006-0861-3
• Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238-252.
• Bowman, E. H. (1960). Assembly-line balancing by linear programming. Operations Research, 8(3), 385-389. doi: 10.1287/opre.8.3.385
• Boysen, N., Fliedner, M., & Scholl, A. (2008). Assembly line balancing: Which model to use when? International Journal of Production Economics, 111(2), 509-528. doi: 10.1016/j.ijpe.2007.02.026
• Codato, G., & Fischetti, M. (2006). Combinatorial Benders’ cuts for mixed-integer linear programming. Operations Research, 54(4), 756-766. doi: 10.1287/opre.1060.0286
• Côté, J.-F., Dell’Amico, M., & Iori, M. (2014). Combinatorial Benders’ cuts for the strip packing problem. Operations Research, 62(3), 643-661. doi: 10.1287/opre.2013.1248
• Deng, G., & Gu, X. (2012). A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion. Computers & Operations Research, 39(9), 2152-2160. doi: 10.1016/j.cor.2011.10.024
• Furugi, A. (2022). Sequence-dependent time- and cost-oriented assembly line balancing problems: a combinatorial Benders’ decomposition approach. Engineering Optimization, 54(1), 170-184. doi: 10.1080/0305215X.2021.1953003
• Gokcen, H., & Erel, E. (1997). A goal programming approach to mixed-model assembly line balancing problem. International Journal of Production Economics, 48(2), 177-185. doi: 10.1016/S0925-5273(96)00069-2
• Hamzadayı, A. (2018). Balancing of mixed-model two-sided assembly lines using teaching-learning based optimization algorithm. Pamukkale University Journal of Engineering Sciences, 24(4), 682-691. doi: 10.5505/pajes.2017.14227
• Hazır, Ö., & Dolgui, A. (2013). Assembly line balancing under uncertainty: Robust optimization models and exact solution method. Computers & Industrial Engineering, 65(2), 261-267. doi: 10.1016/j.cie.2013.03.004
• Hazır, Ö., & Dolgui, A. (2015). A decomposition based solution algorithm for u-type assembly line balancing with interval data. Computers & Operations Research, 59, 126-131. doi: 10.1016/j.cor.2015.01.010
• Held, M., Karp, R. M., & Shareshian, R. (1963). Assembly-line balancing - dynamic programming with precedence constraints. Operations Research, 11(3), 442-459. doi: 10.1287/opre.11.3.442
• Hoffmann, T. R. (1992). Eureka: A hybrid system for assembly line balancing. Management Science, 38(1), 39-47. doi: 10.1287/mnsc.38.1.39
• Holland, J. H. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. University of Michigan Press, Ann Arbor, MI.
• Huang, D., Mao, Z., Fang, K. & Yuan, B. (2021). Combinatorial Benders decomposition for mixed-model two-sided assembly line balancing problem. International Journal of Production Research, 60(8), 2598-2624. doi: 10.1080/00207543.2021.1901152
• Jackson, J. R. (1956). A computing procedure for a line balancing problem. Management Science, 2(3), 261-271. doi: 10.1287/mnsc.2.3.261
• Johnson, R. V. (1988). Optimally balancing large assembly lines with FABLE. Management Science, 34(2), 240-253. doi: 10.1287/mnsc.34.2.240
• Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of Computer Computations, 85-103. Springer.
• Klein, M. (1963). On assembly line balancing. Operations Research, 11(2), 274-281. doi: 10.1287/opre.11.2.274
• Klein, R., & Scholl, A. (1996). Maximizing the production rate in simple assembly line balancing–a branch and bound procedure. European Journal of Operational Research, 91(2), 367-385. doi: 10.1016/0377-2217(95)00047-X
• Özbakır, L., & Tapkan, P. (2011). Bee colony intelligence in zone constrained two-sided assembly line balancing problem. Expert Systems with Applications, 38(9), 11947-11957. doi: 10.1016/j.eswa.2011.03.089
• Özcan, U., & Toklu, B. (2009). Multiple-criteria decision-making in two-sided assembly line balancing: A goal programming and a fuzzy goal programming models. Computers & Operations Research, 36(6), 1955-1965. doi: 10.1016/j.cor.2008.06.009
• Pan, Q.-K., & Ruiz, R. (2014). An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem. Omega, 44, 41-50. doi: 10.1016/j.omega.2013.10.002
• Pastor, R., & Ferrer, L. (2009). An improved mathematical program to solve the simple assembly line balancing problem. International Journal of Production Research, 47(11), 2943-2959. doi: 10.1080/00207540701713832
• Patterson, J. H., & Albracht, J. J. (1975). Assembly-line balancing: zero-one programming with fibonacci search. Operations Research, 23(1), 166-172. doi: 10.1287/opre.23.1.166
• Ritt, M., & Costa, A. M. (2018). Improved integer programming models for simple assembly line balancing and related problems. International Transactions in Operational Research, 25(4), 1345-1359. doi: 10.1111/itor.12206
• Scholl, A., & Becker, C. (2006). State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. European Journal of Operational Research, 168(3), 666-693. doi: 10.1016/j.ejor.2004.07.022
• Scholl, A., & Klein, R. (1997). SALOME: A bidirectional branch-and-bound procedure for assembly line balancing. INFORMS Journal on Computing, 9(4), 319-334. doi: 10.1287/ijoc.9.4.319
• Schrage, L., & Baker, K. R. (1978). Dynamic programming solution of sequencing problems with precedence constraints. Operations Research, 26(3), 444-449. doi: 10.1287/opre.26.3.444
• Talbot, F. B., & Patterson, J. H. (1984). An integer programming algorithm with network cuts for solving the assembly line balancing problem. Management Science, 30(1), 85-99. doi: 10.1287/mnsc.30.1.85
• Vilarinho, P. M., & Simaria, A. S. (2002). A two-stage heuristic method for balancing mixed model assembly lines with parallel workstations. International Journal of Production Research, 40(6), 1405-1420. doi: 10.1080/00207540110116273
• White, W. W. (1961). Letter to the editor – comments on a paper by Bowman. Operations Research, 9(2), 274–276. doi: 10.1287/opre.9.2.274