NNMA: An effective memetic algorithm for solving multiobjective permutation flow shop scheduling problems

Tsung-Che Chiang, Hsueh Chien Cheng, Li Chen Fu

Research output: Contribution to journalArticle

46 Citations (Scopus)

Abstract

The permutation flow shop scheduling problem is addressed in this paper. Two objectives, minimization of makespan and total flow time, are considered. We propose a memetic algorithm, called NNMA, by integrating a general multiobjective evolutionary algorithm (NSGA-II) with a problem-specific heuristic (NEH). We take NEH as a local improving procedure in NNMA and propose several adaptations including the acceptance criterion and job-insertion ordering to deal with multiple objectives and to improve its performance. We test the performance of NNMA using 90 public problem instances with different problem scales, and compare its performance with 23 algorithms. The experimental results show that our NNMA provides close performance for 30 small-scale instances and better performance for 50 medium- and large-scale instances. Furthermore, more than 70% of the net set of non-dominated solutions is updated by NNMA for these 50 instances.

Original languageEnglish
Pages (from-to)5986-5999
Number of pages14
JournalExpert Systems with Applications
Volume38
Issue number5
DOIs
Publication statusPublished - 2011 May 1

Fingerprint

Scheduling
Evolutionary algorithms

Keywords

  • Makespan
  • Memetic algorithm
  • Multiobjective optimization
  • NEH heuristic
  • Permutation flow shop scheduling
  • Total flow time

ASJC Scopus subject areas

  • Engineering(all)
  • Computer Science Applications
  • Artificial Intelligence

Cite this

NNMA : An effective memetic algorithm for solving multiobjective permutation flow shop scheduling problems. / Chiang, Tsung-Che; Cheng, Hsueh Chien; Fu, Li Chen.

In: Expert Systems with Applications, Vol. 38, No. 5, 01.05.2011, p. 5986-5999.

Research output: Contribution to journalArticle

@article{4c4a0e4c1cf942b6bce724a574272ac0,
title = "NNMA: An effective memetic algorithm for solving multiobjective permutation flow shop scheduling problems",
abstract = "The permutation flow shop scheduling problem is addressed in this paper. Two objectives, minimization of makespan and total flow time, are considered. We propose a memetic algorithm, called NNMA, by integrating a general multiobjective evolutionary algorithm (NSGA-II) with a problem-specific heuristic (NEH). We take NEH as a local improving procedure in NNMA and propose several adaptations including the acceptance criterion and job-insertion ordering to deal with multiple objectives and to improve its performance. We test the performance of NNMA using 90 public problem instances with different problem scales, and compare its performance with 23 algorithms. The experimental results show that our NNMA provides close performance for 30 small-scale instances and better performance for 50 medium- and large-scale instances. Furthermore, more than 70{\%} of the net set of non-dominated solutions is updated by NNMA for these 50 instances.",
keywords = "Makespan, Memetic algorithm, Multiobjective optimization, NEH heuristic, Permutation flow shop scheduling, Total flow time",
author = "Tsung-Che Chiang and Cheng, {Hsueh Chien} and Fu, {Li Chen}",
year = "2011",
month = "5",
day = "1",
doi = "10.1016/j.eswa.2010.11.022",
language = "English",
volume = "38",
pages = "5986--5999",
journal = "Expert Systems with Applications",
issn = "0957-4174",
publisher = "Elsevier Limited",
number = "5",

}

TY - JOUR

T1 - NNMA

T2 - An effective memetic algorithm for solving multiobjective permutation flow shop scheduling problems

AU - Chiang, Tsung-Che

AU - Cheng, Hsueh Chien

AU - Fu, Li Chen

PY - 2011/5/1

Y1 - 2011/5/1

N2 - The permutation flow shop scheduling problem is addressed in this paper. Two objectives, minimization of makespan and total flow time, are considered. We propose a memetic algorithm, called NNMA, by integrating a general multiobjective evolutionary algorithm (NSGA-II) with a problem-specific heuristic (NEH). We take NEH as a local improving procedure in NNMA and propose several adaptations including the acceptance criterion and job-insertion ordering to deal with multiple objectives and to improve its performance. We test the performance of NNMA using 90 public problem instances with different problem scales, and compare its performance with 23 algorithms. The experimental results show that our NNMA provides close performance for 30 small-scale instances and better performance for 50 medium- and large-scale instances. Furthermore, more than 70% of the net set of non-dominated solutions is updated by NNMA for these 50 instances.

AB - The permutation flow shop scheduling problem is addressed in this paper. Two objectives, minimization of makespan and total flow time, are considered. We propose a memetic algorithm, called NNMA, by integrating a general multiobjective evolutionary algorithm (NSGA-II) with a problem-specific heuristic (NEH). We take NEH as a local improving procedure in NNMA and propose several adaptations including the acceptance criterion and job-insertion ordering to deal with multiple objectives and to improve its performance. We test the performance of NNMA using 90 public problem instances with different problem scales, and compare its performance with 23 algorithms. The experimental results show that our NNMA provides close performance for 30 small-scale instances and better performance for 50 medium- and large-scale instances. Furthermore, more than 70% of the net set of non-dominated solutions is updated by NNMA for these 50 instances.

KW - Makespan

KW - Memetic algorithm

KW - Multiobjective optimization

KW - NEH heuristic

KW - Permutation flow shop scheduling

KW - Total flow time

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

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

U2 - 10.1016/j.eswa.2010.11.022

DO - 10.1016/j.eswa.2010.11.022

M3 - Article

AN - SCOPUS:79151476944

VL - 38

SP - 5986

EP - 5999

JO - Expert Systems with Applications

JF - Expert Systems with Applications

SN - 0957-4174

IS - 5

ER -