Tip-II montaj hattı dengeleme problemi için büyük komşuluk arama algoritması

Öz

Bu makale tip-II basit montaj hattı dengeleme problemi (BMHDP-II) için bir büyük komşuluk arama (BKA) algoritması önermektedir. BKA algoritması ilk olarak araç rotalama problemlerinin çözümü için önerilmiş ve sonraki uygulamaları çizelgeleme problemlerinin çözümü üzerine olmuştur. Bu iki problem için raporlanan sonuçlar BKA algoritmasının güçlü bir yöntem olduğunu ortaya koymuştur. Araç rotalama problemi belirli sayıdaki rota ile belirli sayıdaki müşteriler arasındaki optimum eşleşmeyi bulmak temel amacına sahipken, BMHDP-II belirli sayıdaki istasyon ile belirli sayıdaki montaj işlemleri arasındaki optimum eşleşmeyi bulmaya çalışmaktadır. Bizim açımızdan, bu iki problem arasındaki bu yapısal benzerlik BKA algoritmasının BMHDP-II için de güçlü bir yöntem olabileceği fikrini doğurmuştur. Bu kapsamda, BMHDP-II için bir BKA algoritması geliştirilmiş ve geliştirilen algoritmanın performansı bir problem seti üzerinde test edilmiştir. Hesaplamalı sonuçlar BMHDP-II çözümünde BKA algoritmasının tatmin edici performansını ortaya koymaktadır.

Anahtar Kelimeler

• Büyük komşuluk arama algoritması,Montaj hattı dengeleme,Üretim oranı maksimizasyonu,Meta-sezgisel

Large neighbourhood search algorithm for type-II assembly line balancing problem

Abstract

This paper proposes a large neighbourhood search (LNS) algorithm for type-II simple assembly line balancing problem (SALBP-II). The LNS algorithm was initially developed for solving vehicle routing problem and its later implementations were used to solve scheduling problems. The reported results about these two problems indicate that LNS algorithm is a powerful method. Vehicle routing problem has the main objective to find the optimal match between a certain number of routes and a certain number of customers, while SALBP-II is trying to find the optimal match between a certain number of workstations and a certain number of assembly operations. To our point of view, LNS algorithm would also be a powerful method for solving SALBP-II due to the structural similarity between these two problems. Within this context, a LNS algorithm is developed to tackle SALBP-II and the performance of the proposed algorithm is tested on a set of benchmark instances. Computational results indicate the satisfactory performance of LNS algorithm in solving SALBP-II.

Keywords

• Large neighbourhood search algorithm,Assembly line balancing,Maximizing production rate,Meta-heuristic

References

1. Thomopoulos NT. Assembly Line Planning and Control. Switzerland, Springer, 2014.
2. Salveson ME. “The assembly line balancing problem”. Journal of Industrial Engineering, 6, 18-25, 1955.
3. Ghosh S, Gagnon RJ. “A comprehensive literature review and analysis of the design, balancing and scheduling of assembly systems”. The International Journal of Production Research, 27(4), 637-670, 1989.
4. Erel E, Sarin SC. “A survey of the assembly line balancing procedures”. Production Planning & Control, 9(5), 414-434, 1998.
5. Becker C, Scholl A. “A survey on problems and methods in generalized assembly line balancing”. European Journal of Operational Research, 168(3), 694-715, 2006.
6. Battaïa O, Dolgui A. “A taxonomy of line balancing problems and their solution approaches”. International Journal of Production Economics, 142(2), 259-277, 2013.
7. Sivasankaran P, Shahabudeen P. “Literature review of assembly line balancing problems”. The International Journal of Advanced Manufacturing Technology, 73(9-12), 1665–1694, 2014.
8. Scholl A, Becker C. “State-of-the-art exact and heuristic solution procedures for simple assembly line balancing”. European Journal of Operational Research, 168(3), 666–693, 2006.

9. Scholl A. Balancing and Sequencing of Assembly Lines. Heidelberg, Physica-Verlag, 1999.
10. Hackman ST, Magazine MJ, Wee TS. “Fast, effective algorithms for simple assembly line balancing problems”. Operations Research, 37(6), 916-924, 1989.
11. Klein R, Scholl A. “Maximizing the production rate in simple assembly line balancing-a branch and bound procedure”. European Journal of Operational Research, 91(2), 367-385, 1996.
12. Pastor R, Ferrer L. “An improved mathematical program to solve the simple assembly line balancing problem”. International Journal of Production Research, 47(11), 2943–2959, 2009.
13. Pastor R, Ferrer L, García A. Evaluating optimization models to solve SALBP. Editors: Gervasi O, Gavrilova ML. Computational Science and Its Applications–ICCSA 2007, 791-803, Berlin Heidelberg, Springer, 2007.
14. Uğurdağ HF, Rachamadugu R, Papachristou CA. “Designing paced assembly lines with fixed number of stations”. European Journal of Operational Research, 102(3), 488-501, 1997.
15. Kilincci O. “A Petri net-based heuristic for simple assembly line balancing problem of type 2”. The International Journal of Advanced Manufacturing Technology, 46(1), 329-338, 2010.
16. Liu SB, Ong HL, Huang HC. “Two bi-directional heuristics for the assembly line type II problem”. The International Journal of Advanced Manufacturing Technology, 22(9-10), 656–661, 2003.
17. Anderson EJ, Ferris MC. “Genetic algorithms for combinatorial optimization: the assemble line balancing problem”. ORSA Journal on Computing, 6(2), 161-173, 1994.
18. Watanabe T, Hashimoto Y, Nishikawa I, Tokumaru H. “Line balancing using a genetic evolution model”. Control Engineering Practice, 3(1), 69-76, 1995.
19. Kim YJ, Kim YK, Cho Y. “A heuristic-based genetic algorithm for workload smoothing in assembly lines”. Computers & Operations Research, 25(2), 99-111, 1998.
20. Scholl A, Voß S. “Simple assembly line balancingheuristic approaches”. Journal of Heuristics, 2(3), 217-244, 1997.
21. Chiang WC. “The application of a tabu search metaheuristic to the assembly line balancing problem”. Annals of Operations Research, 77, 209-227, 1998.
22. Henrici AA. Comparison between simulated annealing and tabu search with an example from the production planning. Editors: Dyckhoff H. et al. Operations Research Proceedings, 498–503, Springer Verlag, Berlin, Germany, 1994.
23. Seyed-Alagheband SA, Fatemi Ghomi SMT, Zandieh M. “A simulated annealing algorithm for balancing the assembly line type II problem with sequence-dependent setup times between tasks”. International Journal of Production Research, 49(3), 805-825, 2011.
24. Boysen N, Fliedner M. “A versatile algorithm for assembly line balancing”. European Journal of Operational Research, 184(1), 39-56, 2008.
25. Zheng Q, Li M, Li Y, Tang Q. “Station ant colony optimization for the type 2 assembly line balancing problem”. The International Journal of Advanced Manufacturing Technology, 66(9-12), 1859-1870, 2013.
26. Nearchou AC. “Maximizing production rate and workload smoothing in assembly lines using particle swarm optimization”. International Journal of Production Economics, 129(2), 242-250, 2011.
27. Nearchou AC. “Balancing large assembly lines by a new heuristic based on differential evolution method”. The International Journal of Advanced Manufacturing Technology, 34(9-10), 1016–1029, 2007.
28. 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), 1-27, 2016.
29. Blum C, Miralles C. “On solving the assembly line worker assignment and balancing problem via beam search”. Computers & Operations Research, 38(1), 328-339, 2011.
30. Blum C. “Iterative beam search for simple assembly line balancing with a fixed number of work stations”. SORT, 35(2), 145-164, 2011.
31. Lei D, Guo, X. “Variable neighborhood search for the second type of two-sided assembly line balancing problem”. Computers & Operations Research, 72, 183- 188.
32. Polat O, Kalayci CB, Mutlu Ö, Gupta, SM. “A two-phase variable neighbourhood search algorithm for assembly line worker assignment and balancing problem type-II: an industrial case study”. International Journal of Production Research, 54(3), 722-741, 2016.
33. Dang QV, Pham K. “Design of a Footwear Assembly Line Using Simulation-based ALNS”. Procedia CIRP, 40, 597-602, 2016.
34. Shaw P. Using constraint programming and local search methods to solve vehicle routing problems. Editors: Maher M, Puget JF. Principles and Practice of Constraint Programming-CP98, 417–431, Berlin Heidelberg, Springer, 1998.
35. Ropke S, Pisinger D. “An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows”. Transportation Science, 40(4), 455-472, 2006.
36. Pisinger D, Ropke S. Large neighborhood search. Editors: Gendreau M, Potvin JY. Handbook of Metaheuristics 2nd ed. New York, USA, Springer, 2010.
37. Laporte G, Musmanno R, Vocaturo F. “An adaptive large neighbourhood search heuristic for the capacitated arcrouting problem with stochastic demands”. Transportation Science, 44(1), 125-135, 2010.
38. Muller LF, Spoorendonk S, Pisinger D. “A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times”. European Journal of Operational Research, 218(3), 614-623, 2012.
39. Demir E, Bektaş T, Laporte G. “An adaptive large neighborhood search heuristic for the pollution-routing problem”. European Journal of Operational Research, 223(2), 346-359, 2012.
40. Masson R, Lehuédé F, Péton O. “An adaptive large neighborhood search for the pickup and delivery problem with transfers”. Transportation Science, 47(3), 344-355, 2013.
41. Adulyasak Y, Cordeau JF, Jans R. “Optimization-based adaptive large neighborhood search for the production routing problem”. Transportation Science, 48(1), 20-45, 2012.
42. Belo-Filho MAF, Amorim P, Almada-Lobo B. “An adaptive large neighbourhood search for the operational integrated production and distribution problem of perishable products”. International Journal of Production Research, 53(20), 6040-6058, 2015.
43. Luo Z, Qin H, Zhang D, Lim A. “Adaptive large neighborhood search heuristics for the vehicle routing problem with stochastic demands and weight–related cost”. Transportation Research Part E: Logistics and Transportation Review, 85, 69-89, 2016.
44. Rifai AP, Nguyen HT, Dawal SZM. “Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling”. Applied Soft Computing, 40, 42-57, 2016.
45. Leu YY, Matheson LA, Rees LP. “Assembly line balancing using genetic algorithms with heuristic generated initial populations and multiple criteria”. Decision Sciences, 15, 581-606, 1994.
46. Akpınar S, Bayhan GM. “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-57, 2011.
47. Helgeson NB, Birnie DP. “Assembly line balancing using the ranked positional weight technique”. Journal of Industrial Engineering, 12(6), 394-398, 1961.
48. Kim YK, Kim YJ, Kim Y. “Genetic algorithms for assembly line balancing with various objectives”. Computers & Industrial Engineering, 30(3), 397–409, 1996.
49. Goncalves JF, De Almeida JR. “A hybrid genetic algorithm for assembly line balancing”. Journal of Heuristics, 8(6), 629-642, 2002.
50. Akpınar, S. “Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem”. Expert Systems with Applications, 61, 28-38, 2016.