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

Fingerprint

Permutation Flowshop
Memetic Algorithm
Flow Shop Scheduling
Local Search
Scheduling
Nondominated Solutions
NSGA-II
Pareto Optimal Solution
Flow Time
Exploitation
Fitness
Permutation
Encoding
Assignment
Update
Local search (optimization)
Benchmark

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Multiobjective permutation flow shop scheduling using a memetic algorithm with an NEH-based local search. / Chiang, Tsung-Che; Cheng, Hsueh Chien; Fu, Li Chen.

Emerging Intelligent Computing Technology and Applications - 5th International Conference on Intelligent Computing, ICIC 2009, Proceedings. 2009. p. 813-825 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5754 LNCS).

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

Chiang, T-C, Cheng, HC & Fu, LC 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5754 LNCS, pp. 813-825, 5th International Conference on Intelligent Computing, ICIC 2009, Ulsan, Korea, Republic of, 09/9/16. https://doi.org/10.1007/978-3-642-04070-2_87
Chiang T-C, Cheng HC, Fu LC. 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. 2009. p. 813-825. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-04070-2_87
Chiang, Tsung-Che ; Cheng, Hsueh Chien ; Fu, Li Chen. / Multiobjective permutation flow shop scheduling using a memetic algorithm with an NEH-based local search. Emerging Intelligent Computing Technology and Applications - 5th International Conference on Intelligent Computing, ICIC 2009, Proceedings. 2009. pp. 813-825 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{19c4801e24c5441899da80a97dd0c211,
title = "Multiobjective permutation flow shop scheduling using a memetic algorithm with an NEH-based local search",
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.",
keywords = "Evolutionary algorithm, Flow shop, Makespan, Memetic algorithm, Multiobjective, Total flow time",
author = "Tsung-Che Chiang and Cheng, {Hsueh Chien} and Fu, {Li Chen}",
year = "2009",
month = "11",
day = "11",
doi = "10.1007/978-3-642-04070-2_87",
language = "English",
isbn = "3642040691",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "813--825",
booktitle = "Emerging Intelligent Computing Technology and Applications - 5th International Conference on Intelligent Computing, ICIC 2009, Proceedings",

}

TY - GEN

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

AU - Chiang, Tsung-Che

AU - Cheng, Hsueh Chien

AU - Fu, Li Chen

PY - 2009/11/11

Y1 - 2009/11/11

N2 - 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.

AB - 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.

KW - Evolutionary algorithm

KW - Flow shop

KW - Makespan

KW - Memetic algorithm

KW - Multiobjective

KW - Total flow time

UR - http://www.scopus.com/inward/record.url?scp=70350773801&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350773801&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-04070-2_87

DO - 10.1007/978-3-642-04070-2_87

M3 - Conference contribution

AN - SCOPUS:70350773801

SN - 3642040691

SN - 9783642040696

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 813

EP - 825

BT - Emerging Intelligent Computing Technology and Applications - 5th International Conference on Intelligent Computing, ICIC 2009, Proceedings

ER -