Skip to main content
Springer Nature Link
Log in

Multi-neighborhood based path relinking for two-sided assembly line balancing problem

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

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

    Article  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • Deng Y, Bard J (2013) A reactive GRASP with path relinking for capacitated clustering. J Heuristics 17(2):119–152 2011

    Article  MATH  Google Scholar 

  • Glover F (1997) A template for scatter search and path relinking. Lect Notes Comput Sci 1363:1–51

    Article  Google Scholar 

  • Glover F, Laguna M, Martí R (2000) Fundamentals of scatter search and path relinking. Control Cybern 39:653–684

    MathSciNet  MATH  Google Scholar 

  • Huang W, Yin A (2004) An improved shifting bottleneck procedure for the job shop scheduling problem. Comput Oper Res 31(12):2093–2110

    Article  MathSciNet  MATH  Google Scholar 

  • Huang W, Wang L (2006) A local search method for permutation flow shop scheduling. J Oper Res Soc 57(10):1248–1251

    Article  MATH  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • Khorasanian D, Hejazi S, Moslehi G (2013) Two-sided assembly line balancing considering the relationships between tasks. Comput Ind Eng 66(4):1096–1105

    Article  Google Scholar 

  • Kim Y, Kim Y, Kim Y (2000) Two-sided assembly line balancing: a genetic algorithm approach. Prod Plan Control 11(1):44–53

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Lü Z, Huang W (2009) Iterated tabu search for identifying community structure in complex networks. Phys Rev E 80(2):026130

    Article  Google Scholar 

  • Özbakir L, Tapkan P (2011) Bee colony intelligence in zone constrained two-sided assembly line balancing problem. Expert Syst Appl 38:11947–11957

    Article  Google Scholar 

  • Ö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

    Article  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • 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

    Article  Google Scholar 

  • Wang Y, Lü Z, Glover F, Hao J (2012) Path relinking for unconstrained binary quadratic programming. Eur J Oper Res 223(3):595–604

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

Download references

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

  1. State Key Laboratory of Digital Manufacturing Equipment & Technology, Huazhong University of Science and Technology, Wuhan, 430074, People’s Republic of China

    Zhaoyang Yang, Guojun Zhang & Haiping Zhu

  2. School of Automotive Engineering, Hubei University of Automotive Technology, Shiyan, 442002, People’s Republic of China

    Zhaoyang Yang

Authors
  1. Zhaoyang Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guojun Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Haiping Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhaoyang Yang.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-015-9959-6

Keywords

Search

Navigation