Abstract
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.
Similar content being viewed by others
References
Bartholdi J (1993) Balancing two-sided assembly lines: a case study. Int J Prod Res 31(10):2447–2461
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
Deng Y, Bard J (2013) A reactive GRASP with path relinking for capacitated clustering. J Heuristics 17(2):119–152 2011
Glover F (1997) A template for scatter search and path relinking. Lect Notes Comput Sci 1363:1–51
Glover F, Laguna M, Martí R (2000) Fundamentals of scatter search and path relinking. Control Cybern 39:653–684
Huang W, Yin A (2004) An improved shifting bottleneck procedure for the job shop scheduling problem. Comput Oper Res 31(12):2093–2110
Huang W, Wang L (2006) A local search method for permutation flow shop scheduling. J Oper Res Soc 57(10):1248–1251
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
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
Khorasanian D, Hejazi S, Moslehi G (2013) Two-sided assembly line balancing considering the relationships between tasks. Comput Ind Eng 66(4):1096–1105
Kim Y, Kim Y, Kim Y (2000) Two-sided assembly line balancing: a genetic algorithm approach. Prod Plan Control 11(1):44–53
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
Lü Z, Huang W (2009) Iterated tabu search for identifying community structure in complex networks. Phys Rev E 80(2):026130
Özbakir L, Tapkan P (2011) Bee colony intelligence in zone constrained two-sided assembly line balancing problem. Expert Syst Appl 38:11947–11957
Özcan U, Toklu B (2009a) A tabu search algorithm for two-sided assembly line balancing. Int J Adv Manuf Technol 43:822–829
Özcan U, Toklu B (2009b) Balancing of mixed-model two sided assembly lines. Comput Ind Eng 57:217–227
Ö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
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
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
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
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
Wang Y, Lü Z, Glover F, Hao J (2012) Path relinking for unconstrained binary quadratic programming. Eur J Oper Res 223(3):595–604
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
Acknowledgments
This paper is dedicated to memorizing the first author’s supervisor, Prof. Wenqi Huang, for his lifelong insightful instruction. Special thanks are given to Prof. Zhipeng Lü for his helpful comments and suggestions to improve this paper significantly. The authors greatly acknowledge the financial supports from the National Natural Science Foundation of China (NSFC) with the Grant Number 51275191, and the Fundamental Research Funds for the Central Universities of HUST with the Grant Number 2014TS033.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Yang, Z., Zhang, G. & Zhu, H. Multi-neighborhood based path relinking for two-sided assembly line balancing problem. J Comb Optim 32, 396–415 (2016). https://doi.org/10.1007/s10878-015-9959-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-015-9959-6