nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.08.2016

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

verfasst von: Zhaoyang Yang, Guojun Zhang, Haiping Zhu

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Online tradeoff scheduling on a single machine to minimize makespan and maximum lateness

Nächster Artikel A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Bartholdi J (1993) Balancing two-sided assembly lines: a case study. Int J Prod Res 31(10):2447–2461CrossRef

Bautista J, Pereira J (2007) Ant algorithms for a time and space constrained assembly line balancing problem. Eur J Oper Res 177(3):2016–2032CrossRefMATH

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

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

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

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

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

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–14CrossRef

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–440CrossRefMATH

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

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

Lee T, Kim Y, Kim Y (2001) Two-sided assembly line balancing to maximize work relatedness and slackness. Comput Ind Eng 40(3):273–292CrossRef

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

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

Ö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–524CrossRef

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–693MathSciNetCrossRefMATH

Simaria A, Vilarinho P (2009) 2-ANTBAL: an ant colony optimization algorithm for balancing two-sided assembly lines. Comput Ind Eng 56(2):489–506CrossRefMATH

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–240CrossRef

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

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–425MathSciNetCrossRefMATH

Titel: Multi-neighborhood based path relinking for two-sided assembly line balancing problem
verfasst von: Zhaoyang Yang
Guojun Zhang
Haiping Zhu
Publikationsdatum: 01.08.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2016
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9959-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2016

Solving the maximum vertex weight clique problem via binary quadratic programming

A hybrid algorithm based on variable neighbourhood for the strip packing problem

An improved bound on 2-distance coloring plane graphs with girth 5

Multi-neighborhood based iterated tabu search for routing and wavelength assignment problem

Introduction: Special issue dedicated to the memory of professor Wenqi Huang

A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang