Type-2 Assembly Line Balancing Using Reactive Tabu Search

Abstract

This study focusses on a two objective type-2 simple assembly line balancing problem. Its primary objective is minimizing the cycle time, or equivalently, maximizing the production rate of the line. Minimization of the workload imbalance among workstations is considered as the secondary objective. Since the problem is known to be intractable, a reactive tabu search algorithm is proposed for the solution. Although tabu search is a well-known meta-heuristic search procedure, based on the detailed literature survey, there is not a reactive tabu search algorithm to solve the investigated problem. Furthermore, the algorithm utilizes a sequence oriented solution representation which is usually applied by population heuristics such as genetic algorithms and differential evolution algorithms. The performance of the algorithm is tested on several benchmark problems taken from the open literature by comparing both objective values with those of previously developed four particle swarm optimization (PSO) algorithms and two multi-objective genetic algorithms (MOGA). The computational results show that the proposed approach presents a quite encouraging success over the existing meta-heuristics.  

Keywords

• Assembly line balancing
• SALBP-2
• Workload smoothing
• Reactive tabu search
• Meta-heuristics

References

1. [1] Boysen, N., Fliedner, M. and Scholl A., “A classification of assembly line balancing problems”, Eur. J. Oper. Res., 183: 674-93, (2007).
2. [2] Zheng, Q., Li, M., Li, Y. and Tang, Q., “Station ant colony optimization for the type 2 assembly line balancing problem”, Int. J. Adv. Manuf. Tech., 66: 1859-1870, (2013).
3. [3] Rachamadugu, R. and Talbot, B., “Improving the equality of workload assignments in assembly lines”, Int. J. Prod. Res., 29 (3): 619-633, (1991).
4. [4] La Scalia, G., Rosa, M., Giuseppe, A., Mario E., “Solving type-2 assembly line balancing problem with fuzzy binary linear programming”, J. Intell. Fuzzy Syst., 25: 517-524, (2013).
5. [5] Mastor, A.A.,” An experimental investigation and comparative evaluation of production line balancing techniques”, Manage. Sci. 16(11): 728-746, (1970).
6. [6] Gehrline, W.V. and Patterson, J.H., “Sequencing for assembly lines with integer task times”, Manage. Sci., 21(9): 1064-1070, (1975).
7. [7] Hackman, S.T., Magazine, M.J. and Wee, T.S., “Fast, effective algorithms for simple assembly line balancing problems”, Oper. Res., 37: 916-924, (1989).
8. [8] Klein, R. and Scholl, A., “Maximizing the production rate in simple assembly line balancing – A branch and bound procedure”, Eur. J. Oper. Res., 91: 367-385, (1996).

9. [9] Uğurdağ, H.F., Rachamadugu, R. and Papachristou, C.A., “Designing paced assembly lines with fixed number of stations”, Eur. J. Oper. Res., 102: 488-501, (1997).
10. [10] Liu, S.B., Ong, H.L. and Huang, H.C., “Two bi-directional heuristics for the assembly line type II problem”, Int. J. Adv. Manuf. Tech., 22: 656-661, (2003).
11. [11] Kılınçcı, Ö., “A petri-net based heuristic for simple assembly line balancing problem of type 2”, Int. J. Adv. Manuf. Tech., 46: 329-338, (2010).
12. [12] Blum, C., “Iterative beam search for simple assembly line balancing with a fixed number of work stations”, Stat. Oper. Res. T., 35(2): 145-164, (2011).
13. [13] Azizoğlu, M. and İmat, S., “Workload smoothing in simple assembly line balancing”, Comput. Oper. Res., 89: 51-57, (2018).
14. [14] Kılınçcı, Ö., “Petri-net based algorithm for maximizing production rate in assembly lines”, J. Fac. Eng. Archit. Gaz., 35(2): 753-763, (2020).
15. [15] Heinrici, A., “A comparison between simulated annealing and tabu search with an example from the production planning”, In: Dyckhoff H, Derigs U, Salomon M, Tijms HC, editors. Operations Research Proceedings 1993, Berlin: Springer-Verlag, 498-503, (1994).
16. [16] Scholl, A. and Voß, S., “Simple Assembly Line Balancing – Heuristic Approaches”, J. Heuristics, 2: 217-244, (1996).
17. [17] Kim, Y.K.., Kim, Y.J. and Kim, Y., “Genetic algorithms for assembly line balancing with various objectives”, Comput. Ind. Eng., 30(3): 397-409, (1996).
18. [18] Nearchou, A.C., “Balancing large assembly lines by a heuristic based on differential evolution method”, Int. J. Adv. Manuf. Tech., 34: 1016-1029, (2007).
19. [19] Nearchou, A.C., “Multi-objective balancing of assembly line by population heuristics”, Int. J. Prod. Res., 46(8): 2275-2297, (2008).
20. [20] Nearchou, A.C., “Maximizing production rate and workload smoothing in assembly lines using particle swarm optimization”, Int. J. Prod. Econ., 129: 242-250, (2011).
21. [21] Zacharia, P.T. and Nearchou, A.C., “Multi-objective fuzzy assembly line balancing using genetic algorithms”, J. Intell. Manuf., 23: 615-627, (2012).
22. [22] Mozdgir, A., Mahdavi, I., Badeleh, I.S. and Solimanpur, M., “Using the Taguchi method to optimize the differential evolution algorithm parameters for minimizing the workload smoothness index in simple assembly line balancing”, Math. Comput. Model., 57: 137-151, (2013).
23. [23] Zacharia, P.T., Tsirkas, S.A., Kabouridis, G. and Giannopoulos, G.I., “Planning the construction process of a robotic arm using a genetic algorithm”, Int. J. Adv. Manuf. Tech., 79: 1293-1302, (2015).
24. [24] Triki, H., Mellouli, A., Hachicha, W. and Masmoudi, F., “A hybrid genetic algorithm approach for solving an extension of assembly line balancing problem”, Int. J. Comput. Integ. M., 29(5): 504-519, (2016).
25. [25] Güden, H. and Meral, S., “An adaptive simulated annealing algorithm-based approach for assembly line balancing and a real-life case study”, Int. J. Adv. Manuf. Tech., 84: 1539-1559, (2016).
26. [26] Zhang, H., Yan, Q., Liu, Y. and Jiang, Z., “An integer-coded differential evolution algorithm for simple assembly line balancing problem of type 2”, Assembly Autom., 36(3): 246-261, (2016).
27. [27] Nearchou, A.C., and Omirou, S.L., “Assembly Line Balancing Using Differential Evolution Models”, Cybernet. Syst., 48(5): 436-458, (2017).
28. [28] Arıkan, M., “A tabu search algorithm for the simple assembly line balancing problem of type-2 with workload balancing objective”, J. Fac. Eng. Archit. Gaz., 32(4): 1169-1179, (2017).
29. [29] Akpınar, Ş., “Large neighbourhood search algorithm for type-II assembly line balancing problem”, Pamukkale University Journal of Engineering Sciences, 23(4): 444-450, (2017).
30. [30] Sivasankaran, P. and Shahabudeen, P., “Literature review of assembly line balancing problems”, Int. J. Adv. Manuf. Tech., 73: 1665-1694, (2014).
31. [31] Boysen, N., Fliedner, M. and Scholl, A., “Assembly line balancing: Which model to use when?”, Int. J. Prod. Econ., 111: 509-528, (2008).
32. [32] Chiang, W.C., “The application of a tabu search metaheuristic to the assembly line balancing problem”, Ann. Oper. Res., 77: 209-227, (1998).
33. [33] Lapierre, S.D., Ruiz, A. and Soriano, P., “Balancing assembly lines with tabu search”, Eur. J. Oper. Res., 168: 826-837, (2006).
34. [34] Driscoll, J. and Thilakawardana, D., “The definition of assembly line balancing difficulty and evaluation of balance solution quality”, Robot. Cim-Int. Manuf., 17: 81-86, (2001).
35. [35] Scholl, A., “Data of assembly line balancing problems”, Shriften zur Quantitativen Betriebwirtschaftslehre 16/93, TH Darmstadt, (1993).
36. [36] Pastor, R. and Ferrer, L., “An improved mathematical program to solve simple assembly line balancing problem”, Int. J. Prod. Res., 47(11): 2943-2959, (2009).
37. [37] Glover, F. and Laguna, M., “Tabu Search”, Boston, Kluwer Academic Publishers, (1997).
38. [38] Battiti, R. and Tecchiolli, G., “The reactive tabu search”, ORSA Journal on Computing, 6(2): 126-140, (1994).
39. [39] Voß, S. and Fink, A., “A hybridized tabu search approach for the minimum weight vertex cover problem”, J. Heuristics, 18(6): 869-876, (2012).
40. [40] Carlton, W.B. and Barnes, J.W., “Solving the traveling salesman problem with time windows using tabu search”, IIE Trans., 28: 617-629, (1996).
41. [41] Woodruff, D.L. and Zemel, E., “Hashing vectors for tabu search”, Ann. Oper. Res., 41: 123-137, (1993).
42. [42] Murata, T., Ishibuchi, H. and Tanaka, H., “Multi-objective genetic algorithm and its application to flowshop scheduling”, Comput. Ind. Eng., 30(4): 957-968, (1996).