A Tabu Search Algorithm for the Parallel Assembly Line Balancing Problem

Year 2009, Volume: 22 Issue: 4, 313 - 323, 27.03.2010

Uğur Özcan Hakan Çerçioğlu Hadi Gökçen Bilal Toklu

Abstract

In a production facility there may be more than one straight assembly line located in parallel. Balancing of parallel assembly lines will provide the flexibility to minimize the total number of workstations due to common resource. This type of problem is called as parallel assembly line balancing (PALB) problem. In this paper, a tabu search based approach is proposed for PALB problem with aim of maximizing line efficiency (LE) (or minimizing number of stations) and minimizing variation of workloads (V). This study is based on the study of Gokcen et al. [1]. The proposed approach is illustrated on a numerical example and its performance is tested on a set of well-known problems in the literature. This study is the first multi objective parallel assembly line balancing study in the literature.

 

Key Words: Assembly line balancing; Parallel assembly lines; Tabu search.

Keywords

Assembly line balancing, Parallel assembly lines, Tabu search

Balancing Problem

Abstract

References

• Gökçen, H., Ağpak, K., Benzer, R., “Balancing of parallel assembly lines”, Int. J. Prod. Econ., 103: 600-609 (2006).
• Ghosh, S., Gagnon, J., “A comprehensive literature review and analysis of the design, balancing and scheduling of assembly systems”, Int. J. Prod. Res., 27: 637-670 (1989).
• Salveson, M.E., “The assembly line balancing problem”, J. Ind. Eng., 6: 18-25 (1955).
• Baybars, I., “A survey of exact algorithms for the simple assembly line balancing problem”, Manage. Sci., 32: 909-932 (1986).
• Erel, E., Sarin, S.C., “A survey of the assembly line balancing procedures”, Prod. Plan. Control., 9: 414-434 (1998).
• Scholl, A., Becker, C., “State-of-the-art exact and heuristic solution procedures for simple assembly line balancing”, Eur. J. Oper. Res., 168(3): 666- 693 (2006).
• Miltenburg, J., Wijngaard, J., “The U-line line balancing problem”, Manage. Sci., 40: 1378-1388 (1994).
• Urban, T.L., “Optimal balancing of U-shaped assembly lines”, Manage. Sci., 44: 738-741 (1998).
• Becker, C., Scholl, A., “A survey on problems and methods in generalized assembly line balancing”, Eur. J. Oper. Res., 168: 694-715 (2006).
• Süer, G.A., Dagli, C., “A knowledge-based system for selection of resource allocation rules and algorithms”, In: A. Mital and S. Anand, eds. Handbook of expert system applications in manufacturing; Structures and rules, Chapman and hall, 108-147 (1994).
• Süer, G.A., “Designing parallel assembly lines”, Comput. Ind. Eng., 35: 467-470 (1998).
• Simaria, A.S., Vilarinho, P.M., “The simple assembly line balancing problem with parallel workstations-a simulated annealing approach”, Int. J. Ind. Eng., 8: 230-240 (2001).
• Askin, R.G., Zhou, M., “A parallel station heuristic for the mixed-model production line balancing problem”, Int. J. Prod. Res., 35: 3095-3105 (1997).
• McMullen, P.R., Frazier, G.V., “A heuristic for solving mixed-model line balancing problems with stochastic task durations and parallel stations”, Int. J. Prod. Econ., 51: 177-190 (1997).
• Vilarinho, P.M., Simaria, A.S., “A two-stage heuristic method for balancing mixed-model assembly lines with parallel workstations”, Int. J. Prod. Res., 40: 1405-1420 (2002).
• Benzer, R., Gökçen, H., Çetinyokuş, T., Çerçioğlu, H., “A network model for parallel line balancing problem”, Math. Probl. Eng., Art. No: 10106 (2007).
• Gutjahr, A.L., Nemhauser, G.L., “An algorithm for
• the line balancing problem”, Manage. Sci., 11(2): 308-315 (1964).
• Glover, F., “Tabu search, part I”, ORSA Journal of Computing, 1: 190-206 (1989).
• Glover, F., “Tabu search, part II”, ORSA Journal of Computing, 2: 4-32 (1990).
• Scholl, A., Voß, S., “Simple assembly line balancing-Heuristic approaches”, J. Heuristics, 2: 217-244 (1996).
• Chiang, W.C., “The application of a tabu search metaheuristic to the assembly line balancing problem”, Ann. Oper. Res., 209-227 (1998).
• Lapierre, S.D., Ruiz, A., Soriano, P., “Balancing assembly lines with tabu search”, Eur. J. Oper. Res., 168 (3): 826-837 (2006).
• Hwang, R.K., Katayama, H., Gen, M., “U-shaped assembly line balancing problem with genetic algorithm”, Int. J. Prod. Res., 46 (16): 4637-4649 (2008).
• Tabucanon, M.T., “Multiple criteria decision making in industry (Studies in production and engineering economics; 8)”, Elsevier, Amsterdam- Oxford-New York-Tokyo (1988).