×

zbMATH — the first resource for mathematics

A branch-and-bound algorithm for assembly line worker assignment and balancing problems. (English) Zbl 1307.90090
Summary: In this paper, we studied the assembly line worker assignment and balancing problem, which is an extension of the classical assembly line balancing problem in which an optimal partition of the assembly work among the stations is sought along with the assignment of the operators to the stations. The relationship between this problem and several other well-studied problems is explored, and new lower bounds are derived. Additionally, an exact enumeration algorithm, which makes use of the lower bounds, is developed to solve the problem. The algorithm is tested by using a standard benchmark set of instances. The results show that the algorithm improves upon the best-performing methods from the literature in terms of solution quality, and verifies more optimal solutions than the other available exact methods.

MSC:
90B70 Theory of organizations, manpower planning in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Scholl, A.; Becker, C., State-of-the-art exact and heuristic solution procedures for simple assembly line balancing, Eur J Oper Res, 168, 666-693, (2006) · Zbl 1083.90019
[2] Garey, M.; Johnson, D. S., Computers and intractabilitya guide to the theory of NP-completeness, (1979), W.H. Freeman and Company
[3] Boysen, N.; Fliedner, M.; Scholl, A., A classification of assembly line balancing problems, Eur J Oper Res, 183, 674-693, (2007) · Zbl 1179.90103
[4] Battaïa, O.; Dolgui, A., A taxonomy of line balancing problems and their solution approaches, Int J Prod Econ, 142, 259-277, (2013)
[5] Heimlern, C.; Kolisch, R., Work assignment to and qualification of multi-skilled human resources under knowledge depreciation and company skill level targets, Int J Prod Res, 48, 3759-3781, (2010) · Zbl 1197.90269
[6] Rubinovitz, J.; Bukchin, J.; Lenz, E., RALB a heuristic algorithm for design and balancing of robotic assembly lines, CIRP Ann Manuf Technol, 42, 497-500, (1993)
[7] Miralles, C.; García-Sabater, J. P.; Andrés, C.; Cardos, M., Advantages of assembly lines in sheltered work centres for disableda case study, Int J Prod Econ, 110, 187-197, (2007)
[8] Sewell, E. C.; Jacobson, S. H., A branch, bound, and remember algorithm for the simple assembly line balancing problem, INFORMS J Comput, 24, 433-442, (2012) · Zbl 06599280
[9] Blum, C.; Miralles, C., On solving the assembly line worker assignment and balancing problem via beam search, Comput Oper Res, 38, 328-339, (2011) · Zbl 1231.90256
[10] Moreira, M. C.O.; Ritt, M.; Costa, A. M.; Chaves, A. A., Simple heuristics for the assembly line worker assignment and balancing problem, J Heuristics, 18, 505-524, (2012)
[11] Mutlu, Ö.; Polat, O.; Supciller, A. A., An iterative genetic algorithm for the assembly line worker assignment and balancing problem of type-II, Comput Oper Res, 40, 418-426, (2013) · Zbl 1349.90864
[12] Borba L, Ritt M. Exact and heuristic methods for the assembly line worker assignment and balancing problem. Comput Oper Res, arXiv:1007.4063v1, http://arxiv.org/abs/1308.0299, submitted for publication [retrieved on september 6th 2013]. · Zbl 1348.90220
[13] Levitin, G.; Rubinovitz, J.; Shnits, B., A genetic algorithm for robotic assembly line balancing, Eur J Oper Res, 168, 811-825, (2006) · Zbl 1083.90018
[14] Gao, J.; Sun, L.; Wang, L.; Gen, M., An efficient approach for type II robotic assembly line balancing problems, Comput Ind Eng, 56, 1065-1080, (2009)
[15] Mladenović, N.; Hansen, P., Variable neighborhood search, Comput Oper Res, 24, 1097-1100, (1997) · Zbl 0889.90119
[16] Miralles, C.; García-Sabater, J. P.; Andrés, C.; Cardos, M., Branch and bound procedures for solving the assembly line worker assignment and balancing problemapplication to sheltered work centres for disabled, Discrete Appl Math, 156, 352-367, (2008) · Zbl 1157.90396
[17] Chaves AA, Miralles C, Nogueira Lorena LA. Clustering search approach for the assembly line worker assignment and balancing problem. In: Proceedings of the 37th international conference on computers and industrial engineering, Alexandria, Egypt; 2007. p. 1469-78.
[18] Martello, S.; Soumis, F.; Toth, P., Exact and approximation algorithms for makespan minimization on unrelated parallel machines, Discrete Appl Math, 75, 169-188, (1997) · Zbl 0882.68016
[19] Scholl, A.; Klein, R., Salomea bidirectional branch and bound procedure for assembly line balancing, INFORMS J Comput, 9, 319-334, (1997) · Zbl 0895.90121
[20] Vilà, M.; Pereira, J., An enumeration procedure for the assembly line balancing problem based on branching by non-decreasing idle time, Eur J Oper Res, 229, 106-113, (2013) · Zbl 1317.90325
[21] Martello, S.; Toth, P., Knapsack problemsalgorithms and computer implementations, (1990), John Wiley & Sons
[22] Johnson, R. V., Optimally balancing large assembly lines with ‘fable’, Manage Sci, 34, 240-253, (1988)
[23] Wotzlaw, A., Scheduling unrelated parallel machinesalgorithms. complexity and performance, (2012), AV AkademikerVerlag
[24] Geoffrion, A. M., Lagrangian relaxation and its uses in integer programming, Math Prog, 2, 82-114, (1974)
[25] Burkard, R.; Dell’Amico, M.; Martello, S., Assignment problems, (2009), Society for Industrial and Applied Mathematics · Zbl 1196.90002
[26] Kao, G. K.; Sewell, E. C.; Jacobson, S. H., A branch, bound, and remember algorithm for the \(1 | r_i | \sum t_i\) scheduling problem, J Sched, 12, 163-175, (2009) · Zbl 1179.90139
[27] Fisher, M. L., The Lagrangian relaxation method for solving integer programming problems, Manage Sci, 27, 1-18, (1981) · Zbl 0466.90054
[28] Van de Velde, S. L., Duality-based algorithms for scheduling unrelated parallel machines, ORSA J Comput, 5, 192-205, (1993) · Zbl 0777.90019
[29] Jonker, R.; Volgenant, A., A shortest augmenting path algorithm for dense and sparse linear assignment problems, Computing, 38, 325-340, (1987) · Zbl 0607.90056
[30] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to algorithms, (2009), The MIT Press · Zbl 1187.68679
[31] Jackson, J. R., A computing procedure for a line balancing problem, Manage Sci, 2, 261-271, (1956)
[32] Bautista, J.; Pereira, J., Procedures for the time and space constrained assembly line balancing problem, Eur J Oper Res, 212, 473-481, (2011) · Zbl 1237.90082
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.