×

Multi-neighborhood based path relinking for two-sided assembly line balancing problem. (English) Zbl 1350.90020

Summary: This paper presents a multi-neighborhood based path relinking algorithm (MN-PR) for solving the two-sided assembly line balancing problem. By incorporating an effective local search into a path relinking framework, the proposed MN-PR algorithm integrates a number of distinguishing features, such as a multi-neighborhood based local search procedure, a dedicated path relinking operator to generate new solutions and a strategy to fix an infeasible solution generated by the path relinking procedure to a feasible one. Our proposed MN-PR algorithm is tested on a set of totally 45 public instances widely used in the literature. Comparisons with other reference algorithms show the efficacy of the proposed algorithm in terms of the solution quality. Particularly, the proposed MN-PR algorithm is able to improve the best upper bounds for one instance with 65 tasks and 326 cycle time. This paper also presents an analysis to show the significance of the main components of the proposed algorithm.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

Scatter Search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bartholdi J (1993) Balancing two-sided assembly lines: a case study. Int J Prod Res 31(10):2447-2461 · doi:10.1080/00207549308956868
[2] Bautista J, Pereira J (2007) Ant algorithms for a time and space constrained assembly line balancing problem. Eur J Oper Res 177(3):2016-2032 · Zbl 1109.90032 · doi:10.1016/j.ejor.2005.12.017
[3] Deng Y, Bard J (2013) A reactive GRASP with path relinking for capacitated clustering. J Heuristics 17(2):119-152 2011 · Zbl 1211.90301 · doi:10.1007/s10732-010-9129-z
[4] Glover F (1997) A template for scatter search and path relinking. Lect Notes Comput Sci 1363:1-51 · doi:10.1007/BFb0026589
[5] Glover F, Laguna M, Martí R (2000) Fundamentals of scatter search and path relinking. Control Cybern 39:653-684 · Zbl 0983.90077
[6] Huang W, Yin A (2004) An improved shifting bottleneck procedure for the job shop scheduling problem. Comput Oper Res 31(12):2093-2110 · Zbl 1100.90509 · doi:10.1016/S0305-0548(03)00243-0
[7] Huang W, Wang L (2006) A local search method for permutation flow shop scheduling. J Oper Res Soc 57(10):1248-1251 · Zbl 1123.90080 · doi:10.1057/palgrave.jors.2602106
[8] Huang W, Fu Z, Xu R (2013) Tabu search algorithm combined with global perturbation for packing arbitrary sized circles into a circular container. Sci China Inform Sci 56(9):1-14 · doi:10.1007/s11432-011-4424-3
[9] Hu X, Wu E, Jin Y (2008) A station-oriented enumerative algorithm for two-sided assembly line balancing. Eur J Oper Res 186(1):435-440 · Zbl 1146.90387 · doi:10.1016/j.ejor.2007.01.022
[10] Khorasanian D, Hejazi S, Moslehi G (2013) Two-sided assembly line balancing considering the relationships between tasks. Comput Ind Eng 66(4):1096-1105 · doi:10.1016/j.cie.2013.08.006
[11] Kim Y, Kim Y, Kim Y (2000) Two-sided assembly line balancing: a genetic algorithm approach. Prod Plan Control 11(1):44-53 · doi:10.1080/095372800232478
[12] Lee T, Kim Y, Kim Y (2001) Two-sided assembly line balancing to maximize work relatedness and slackness. Comput Ind Eng 40(3):273-292 · doi:10.1016/S0360-8352(01)00029-8
[13] Lü Z, Huang W (2009) Iterated tabu search for identifying community structure in complex networks. Phys Rev E 80(2):026130 · doi:10.1103/PhysRevE.80.026130
[14] Özbakir L, Tapkan P (2011) Bee colony intelligence in zone constrained two-sided assembly line balancing problem. Expert Syst Appl 38:11947-11957 · doi:10.1016/j.eswa.2011.03.089
[15] Özcan U, Toklu B (2009a) A tabu search algorithm for two-sided assembly line balancing. Int J Adv Manuf Technol 43:822-829 · Zbl 1179.90191
[16] Özcan U, Toklu B (2009b) Balancing of mixed-model two sided assembly lines. Comput Ind Eng 57:217-227 · Zbl 1179.90191
[17] Özcan U, Toklu B (2009c) Multiple-criteria decision-making in two-sided assembly line balancing: a goal programming and a fuzzy goal programming models. Comput Oper Res 36:1955-1965 · Zbl 1179.90191
[18] Rahimi-Vahed A, Crainic T, Gendreau M, Rei W (2013) A path relinking algorithm for a multi-depot periodic vehicle routing problem. J Heuristics 19(3):497-524 · doi:10.1007/s10732-013-9221-2
[19] Scholl A, Becker C (2006) State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. Eur J Oper Res 168(3):666-693 · Zbl 1083.90019 · doi:10.1016/j.ejor.2004.07.022
[20] Simaria A, Vilarinho P (2009) 2-ANTBAL: an ant colony optimization algorithm for balancing two-sided assembly lines. Comput Ind Eng 56(2):489-506 · Zbl 1095.90100 · doi:10.1016/j.cie.2007.10.007
[21] Taha R, El-Kharbotly A, Sadek Y, Afia N (2011) A Genetic Algorithm for solving two-sided assembly line balancing problems. Ain Shams Eng J 2:227-240 · doi:10.1016/j.asej.2011.10.003
[22] Wang Y, Lü Z, Glover F, Hao J (2012) Path relinking for unconstrained binary quadratic programming. Eur J Oper Res 223(3):595-604 · Zbl 1292.90225 · doi:10.1016/j.ejor.2012.07.012
[23] Zhang G, Lai K (2006) Combining path relinking and genetic algorithms for the multiple-level warehouse layout problem. Eur J Oper Res 169(2):413-425 · Zbl 1079.90016 · doi:10.1016/j.ejor.2004.08.007
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.