×

A memetic algorithm for the cost-oriented robotic assembly line balancing problem. (English) Zbl 1458.90237

Summary: In order to minimize costs, manufacturing companies have been relying on assembly lines for the mass production of commodity goods. Among other issues, the successful operation of an assembly line requires balancing work among the stations of the line in order to maximize its efficiency, a problem known in the literature as the assembly line balancing problem, ALBP. In this work, we consider an ALBP in which task assignment and equipment decisions are jointly considered, a problem that has been denoted as the robotic ALBP. Moreover, we focus on the case in which equipment has different costs, leading to a cost-oriented formulation. In order to solve the problem, which we denote as the cost-oriented robotic assembly line balancing problem, cRALBP, a hybrid metaheuristic is proposed. The metaheuristic embeds results obtained for two special cases of the problem within a genetic algorithm in order to obtain a memetic algorithm, applicable to the general problem. An extensive computational experiment shows the advantages of the hybrid approach and how each of the components of the algorithm contributes to the overall ability of the method to obtain good solutions.

MSC:

90B30 Production models
90C59 Approximation methods and heuristics in mathematical programming

Software:

SALBPGen; irace
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Amen, M., An exact method for cost-oriented assembly line balancing, Int. J. Prod. Econ., 64, 1-3, 187-195, (2000)
[2] Amen, M., Cost-oriented assembly line balancing: model formulations, solution difficulty, upper and lower bounds, Eur. J. Oper. Res., 168, 3, 747-770, (2006) · Zbl 1083.90012
[3] Araújo, F.; Costa, A.; Miralles, C., Two extensions for the alwabp: parallel stations and collaborative approach, Int. J. Prod. Econ., 140, 1, 483-495, (2012)
[4] Bautista, J.; Pereira, J., A dynamic programming based heuristic for the assembly line balancing problem, Eur. J. Oper. Res., 194, 3, 787-794, (2009) · Zbl 1168.90404
[5] Bautista, J.; Pereira, J., Procedures for the time and space constrained assembly line balancing problem, Eur. J. Oper. Res., 212, 3, 473-481, (2011) · Zbl 1237.90082
[6] Baybards, I., A survey of exact algorithms for the simple assembly line balancing problem, Manage. Sci., 32, 8, 909-932, (1986) · Zbl 0601.90081
[7] Becker, C.; Scholl, A., A survey on problems and methods in generalized assembly line balancing, Eur. J. Oper. Res., 168, 3, 694-715, (2006) · Zbl 1083.90013
[8] Blum, C.; Miralles, C., On solving the assembly line worker assignment and balancing problem via beam search, Comput. Oper. Res., 38, 1, 328-339, (2011) · Zbl 1231.90256
[9] Borba, L.; Ritt, M., Exact and heuristic methods for the assembly line worker assignment and balancing problem, Comput. Oper. Res., 45, 87-96, (2014) · Zbl 1348.90220
[10] Borba, L.; Ritt, M.; Miralles, C., Exact and heuristic methods for solving the robotic assembly line balancing problem, Eur. J. Oper. Res., forthcoming, (2018) · Zbl 1403.90652
[11] Boysen, N.; Fliedner, M.; Scholl, A., A classification of assembly line balancing problems, Eur. J. Oper .Res., 183, 2, 674-693, (2007) · Zbl 1179.90103
[12] Bukchin, J.; Tzur, M., Design of flexible assembly line to minimize equipment cost, IIE Trans., 32, 7, 585-598, (2000)
[13] Çil, Z.; Mete, S.; Ağpak, K., Analysis of the type ii robotic mixed-model assembly line balancing problem, Eng. Optim., 49, 6, 990-1009, (2017)
[14] Corominas, A.; Ferrer, L.; Pastor, R., Assembly line balancing: general resource-constrained case, Int. J. Prod. Res., 49, 12, 3527-3542, (2011)
[15] Daoud, S.; Chehade, H.; Yalaoui, F.; Amodeo, L., Solving a robotic assembly line balancing problem using efficient hybrid methods, J. Heuristics, 20, 3, 235-259, (2014)
[16] Dolgui, A.; Battaïa, O., A taxonomy of line balancing problems and their solution approaches, Int. J. Prod. Econ., 142, 2, 259-277, (2013)
[17] Fleszar, K.; Hindi, K., An enumerative heuristic and reduction methods for the assembly line balancing problem, Eur. J. Oper. Res., 145, 3, 606-620, (2003) · Zbl 1011.90039
[18] Gadidov, R.; Wilhelm, W., A cutting plane approach for the single-product assembly system design problem, Int. J. Prod. Res., 38, 8, 1731-1754, (2000) · Zbl 0945.90540
[19] Gao, J.; Sun, L.; Wang, L.; Gen, M., An efficient approach for type II robotic assembly line balancing problems, Comput. Ind. Eng., 56, 3, 1065-1080, (2009)
[20] Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W. H. Freeman & Co. New York, NY, USA · Zbl 0411.68039
[21] Hazir, Ö.; Delorme, X.; Dolgui, A., A review of cost and profit oriented line design and balancing problems and solution approaches, Annu. Rev. Control, 40, 14-24, (2015)
[22] Hoffmann, T., Assembly line balancing with a precedence matrix, Manage. Sci., 9, 4, 551-562, (1963)
[23] Holland, J. H., Adaptation in natural and artificial systems, (1975), University of Michigan Press
[24] Johnson, D. S.; Niemi, K. A., On knapsacks, partitions, and a new dynamic programming technique for trees, Math. Oper. Res., 8, 1, 1-14, (1983) · Zbl 0506.90035
[25] Levitin, G.; Rubinovitz, J.; Shnits, B., A genetic algorithm for robotic assembly line balancing, Eur. J. Oper. Res., 168, 3, 811-825, (2006) · Zbl 1083.90018
[26] López-Ibáñez, M.; Dubois-Lacoste, J.; Cáceres, L. P.; Stützle, T.; Birattari, M., The irace package: iterated racing for automatic algorithm configuration, Oper. Res. Perspect., 3, 43-58, (2016)
[27] Miller, B. L.; Goldberg, D. E., Genetic algorithms, tournament selection, and the effects of noise, Complex Syst., 9, 193-212, (1995)
[28] Miralles, C.; García-Sabater, J. P.; Andrés, C.; Cardos, M., Advantages of assembly lines in sheltered work centres for disabled. a case study, Int. J. Prod. Econ., 110, 1, 187-197, (2007)
[29] Moreira, M.; Cordeau, J.-F.; Costa, A.; Laporte, G., Robust assembly line balancing with heterogeneous workers, Comput. Ind. Eng., 88, 254-263, (2015)
[30] Moreira, M.; Miralles, C.; Costa, A., Model and heuristics for the assembly line worker integration and balancing problem, Comput. Ind. Eng., 54, 64-73, (2015) · Zbl 1348.90228
[31] Moreira, M.; Pastor, R.; Costa, A.; Miralles, C., The multi-objective assembly line worker integration and balancing problem of type-2, Comput. Ind. Eng., 82, 114-125, (2017) · Zbl 1391.90225
[32] Moreira, M.; Ritt, M.; Costa, A.; Chaves, A., Simple heuristics for the assembly line worker assignment and balancing problem, J. Heuristics, 18, 3, 505-524, (2012)
[33] Morrison, D. R.; Sewell, E. C.; Jacobson, S. H., An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset, Eur. J. Oper. Res., 236, 2, 403-409, (2014) · Zbl 1317.90258
[34] Mutlu, O.; Polat, O.; Supciller, A., An iterative genetic algorithm for the assembly line worker assignment and balancing problem of type-ii, Comput. Oper. Res., 40, 1, 418-426, (2013) · Zbl 1349.90864
[35] Nilakantan, J.; Nielsen, I.; Ponnambalam, S.; Venkataramanaiah, S., Differential evolution algorithm for solving ralb problem using cost- and time-based models, Int. J. Adv. Manuf. Technol., 89, 1-4, 311-332, (2017)
[36] Nilakantan, J.; Ponnambalam, S., Robotic u-shaped assembly line balancing using particle swarm optimization, Eng. Optim., 48, 2, 231-252, (2016)
[37] Otto, A.; Otto, C.; Scholl, A., Systematic data generation and test design for solution algorithms on the example of salbpgen for assembly line balancing, Eur. J. Oper. Res., 228, 1, 33-45, (2013) · Zbl 1332.90176
[38] Pape, T., Heuristics and lower bounds for the simple assembly line balancing problem type 1: overview, computational tests and improvements, Eur. J. Oper. Res., 240, 1, 32-42, (2015) · Zbl 1339.90339
[39] Peeters, M.; Degraeve, Z., An linear programming based lower bound for the simple assembly line balancing problem, Eur. J. Oper. Res., 168, 3, 716-731, (2006) · Zbl 1083.90028
[40] Pekin, N.; Azizoglu, M., Bi criteria flexible assembly line design problem with equipment decisions, Int. J. Prod. Res., 46, 22, 6323-6343, (2008) · Zbl 1154.90373
[41] Pereira, J., Empirical evaluation of lower bounding methods for the simple assembly line balancing problem, Int. J. Prod. Res., 53, 11, 3327-3340, (2015)
[42] Polat, O.; Kalayci, C.; Mutlu, O.; Gupta, S., A two-phase variable neighbourhood search algorithm for assembly line worker assignment and balancing problem type-ii: an industrial case study, Int. J. Prod. Res., 54, 3, 722-741, (2016)
[43] Rekiek, B.; Dolgui, A.; Delchambre, A.; Bratcu, A., State of art of optimization methods for assembly line design, Annu Rev Control, 26 II, 163-174, (2002)
[44] Ritt, M.; Costa, A.; Miralles, C., The assembly line worker assignment and balancing problem with stochastic worker availability, Int. J. Prod. Res., 54, 3, 907-922, (2016)
[45] Ritt, M.; Costa, A. M., Improved integer programming models for simple assembly line balancing and related problems, International Transactions of Operations Research, (2015)
[46] Rubinovitz, J.; Bukchin, J.; Lenz, E., Ralb - a heuristic algorithm for design and balancing of robotic assembly lines, CIRP Annals - Manufacturing Technology, 42, 1, 497-500, (1993)
[47] Sastry, K.; Goldberg, D. E.; Kendall, G., Genetic algorithms, (Burke, E. K.; Kendall, G., Search Methodologies, (2014), Springer), 97-125
[48] 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) · Zbl 1083.90019
[49] Sewell, E.; Jacobson, S., A branch, bound, and remember algorithm for the simple assembly line balancing problem, INFORMS J. Comput., 24, 3, 433-442, (2012) · Zbl 1462.90112
[50] Sternatz, J., Enhanced multi-hoffmann heuristic for efficiently solving real-world assembly line balancing problems in automotive industry, Eur. J. Oper. Res., 235, 3, 740-754, (2014) · Zbl 1305.90168
[51] Tasan, S.; Tunali, S., A review of the current applications of genetic algorithms in assembly line balancing, J. Intell. Manuf., 19, 1, 49-69, (2008)
[52] Triki, H.; Mellouli, A.; Masmoudi, F., A multi-objective genetic algorithm for assembly line resource assignment and balancing problem of type 2 (alrabp-2), J. Intell. Manuf., 28, 2, 371-385, (2017)
[53] Valério De Carvalho, J., Lp models for bin packing and cutting stock problems, Eur. J. Oper. Res., 141, 2, 253-273, (2002) · Zbl 1059.90095
[54] Fernandez de la Vega, W.; Lueker, G. S., Bin packing can be solved within 1 + ϵ in linear time, Combinatorica, 1, 4, 349-355, (1981) · Zbl 0485.68057
[55] Vilà, M.; Pereira, J., A branch-and-bound algorithm for assembly line worker assignment and balancing problems, Comput. Ind. Eng., 44, 105-114, (2014) · Zbl 1307.90090
[56] Yoosefelahi, A.; Aminnayeri, M.; Mosadegh, H.; Ardakani, H., Type ii robotic assembly line balancing problem: an evolution strategies algorithm for a multi-objective model, J. Manuf. Syst., 31, 2, 139-151, (2012)
[57] Zacharia, P.; Nearchou, A., A population-based algorithm for the bi-objective assembly line worker assignment and balancing problem, Eng. Appl. Artif. Intell., 49, 1-9, (2016)
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.