Multiobjective permutation flow shop scheduling using a memetic algorithm with an NEH-based local search

Tsung Che Chiang, Hsueh Chien Cheng, Li Chen Fu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

In this paper we address scheduling of the permutation flow shop with minimization of makespan and total flow time as the objectives. We propose a memetic algorithm (MA) to search for the set of non-dominated solutions (the Pareto optimal solutions). The proposed MA adopts the permutation-based encoding and the fitness assignment mechanism of NSGA-II. The main feature is the introduction of an NEH-based neighborhood function into the local search procedure. We also adjust the size of the neighborhood dynamically during the execution of the MA to strike a balance between exploration and exploitation. Forty public benchmark problem instances are used to compare the performance of our MA with that of twenty-seven existing algorithms. Our MA provides close performance for small-scale instances and much better performance for large-scale instances. It also updates more than 90% of the net set of non-dominated solutions for the large-scale instances.

Original languageEnglish
Title of host publicationEmerging Intelligent Computing Technology and Applications - 5th International Conference on Intelligent Computing, ICIC 2009, Proceedings
Pages813-825
Number of pages13
DOIs
Publication statusPublished - 2009 Nov 11
Event5th International Conference on Intelligent Computing, ICIC 2009 - Ulsan, Korea, Republic of
Duration: 2009 Sep 162009 Sep 19

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5754 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th International Conference on Intelligent Computing, ICIC 2009
CountryKorea, Republic of
CityUlsan
Period09/9/1609/9/19

Keywords

  • Evolutionary algorithm
  • Flow shop
  • Makespan
  • Memetic algorithm
  • Multiobjective
  • Total flow time

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Multiobjective permutation flow shop scheduling using a memetic algorithm with an NEH-based local search'. Together they form a unique fingerprint.

  • Cite this

    Chiang, T. C., Cheng, H. C., & Fu, L. C. (2009). Multiobjective permutation flow shop scheduling using a memetic algorithm with an NEH-based local search. In Emerging Intelligent Computing Technology and Applications - 5th International Conference on Intelligent Computing, ICIC 2009, Proceedings (pp. 813-825). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5754 LNCS). https://doi.org/10.1007/978-3-642-04070-2_87