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

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.

Anahtar Kelimeler:

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

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,

PDF

___

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