An improved multiobjective memetic algorithm for permutation flow shop scheduling

Tsung Che Chiang, Li Chen Fu

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

2 Citations (Scopus)

Abstract

This paper addresses a multiobjective scheduling problem in the permutation flow shop. The objectives are to minimize makespan and total flow time. The proposed approach is based on the framework of memetic algorithm, which is known as a hybrid of genetic algorithm and local search. The local search procedure is an iterative process repeating neighbor generation, neighbor evaluation, and neighbor selection. We take a problem-specific heuristic for neighbor generation and propose several strategies for neighbor evaluation and neighbor selection. Archive injection (adding non-dominated solutions to the population) is another issue under investigation. We examine the effects of the proposed strategies through experiments using forty widely used problem instances with different scales. We also evaluate the proposed approach by comparing it with other twenty-six ones in terms of three performance metrics. Our approach outperforms all benchmarks and updates a large portion of the sets of best known non-dominated solutions for large-scale instances.

Original languageEnglish
Title of host publication2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010
DOIs
Publication statusPublished - 2010 Dec 1
Event2010 6th IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010 - Barcelona, Spain
Duration: 2010 Jul 182010 Jul 23

Publication series

Name2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010

Other

Other2010 6th IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010
CountrySpain
CityBarcelona
Period10/7/1810/7/23

Fingerprint

Permutation Flowshop
Nondominated Solutions
Memetic Algorithm
Flow Shop Scheduling
Local Search
Scheduling
Flow Time
Evaluation
Performance Metrics
Iterative Process
Scheduling Problem
Injection
Genetic algorithms
Update
Genetic Algorithm
Heuristics
Benchmark
Minimise
Evaluate
Experiment

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Applied Mathematics

Cite this

Chiang, T. C., & Fu, L. C. (2010). An improved multiobjective memetic algorithm for permutation flow shop scheduling. In 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010 [5586141] (2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010). https://doi.org/10.1109/CEC.2010.5586141

An improved multiobjective memetic algorithm for permutation flow shop scheduling. / Chiang, Tsung Che; Fu, Li Chen.

2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010. 2010. 5586141 (2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010).

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

Chiang, TC & Fu, LC 2010, An improved multiobjective memetic algorithm for permutation flow shop scheduling. in 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010., 5586141, 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010, 2010 6th IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010, Barcelona, Spain, 10/7/18. https://doi.org/10.1109/CEC.2010.5586141
Chiang TC, Fu LC. An improved multiobjective memetic algorithm for permutation flow shop scheduling. In 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010. 2010. 5586141. (2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010). https://doi.org/10.1109/CEC.2010.5586141
Chiang, Tsung Che ; Fu, Li Chen. / An improved multiobjective memetic algorithm for permutation flow shop scheduling. 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010. 2010. (2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010).
@inproceedings{524c80c062bc4f9eb808cd7cfe4c5f1c,
title = "An improved multiobjective memetic algorithm for permutation flow shop scheduling",
abstract = "This paper addresses a multiobjective scheduling problem in the permutation flow shop. The objectives are to minimize makespan and total flow time. The proposed approach is based on the framework of memetic algorithm, which is known as a hybrid of genetic algorithm and local search. The local search procedure is an iterative process repeating neighbor generation, neighbor evaluation, and neighbor selection. We take a problem-specific heuristic for neighbor generation and propose several strategies for neighbor evaluation and neighbor selection. Archive injection (adding non-dominated solutions to the population) is another issue under investigation. We examine the effects of the proposed strategies through experiments using forty widely used problem instances with different scales. We also evaluate the proposed approach by comparing it with other twenty-six ones in terms of three performance metrics. Our approach outperforms all benchmarks and updates a large portion of the sets of best known non-dominated solutions for large-scale instances.",
author = "Chiang, {Tsung Che} and Fu, {Li Chen}",
year = "2010",
month = "12",
day = "1",
doi = "10.1109/CEC.2010.5586141",
language = "English",
isbn = "9781424469109",
series = "2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010",
booktitle = "2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010",

}

TY - GEN

T1 - An improved multiobjective memetic algorithm for permutation flow shop scheduling

AU - Chiang, Tsung Che

AU - Fu, Li Chen

PY - 2010/12/1

Y1 - 2010/12/1

N2 - This paper addresses a multiobjective scheduling problem in the permutation flow shop. The objectives are to minimize makespan and total flow time. The proposed approach is based on the framework of memetic algorithm, which is known as a hybrid of genetic algorithm and local search. The local search procedure is an iterative process repeating neighbor generation, neighbor evaluation, and neighbor selection. We take a problem-specific heuristic for neighbor generation and propose several strategies for neighbor evaluation and neighbor selection. Archive injection (adding non-dominated solutions to the population) is another issue under investigation. We examine the effects of the proposed strategies through experiments using forty widely used problem instances with different scales. We also evaluate the proposed approach by comparing it with other twenty-six ones in terms of three performance metrics. Our approach outperforms all benchmarks and updates a large portion of the sets of best known non-dominated solutions for large-scale instances.

AB - This paper addresses a multiobjective scheduling problem in the permutation flow shop. The objectives are to minimize makespan and total flow time. The proposed approach is based on the framework of memetic algorithm, which is known as a hybrid of genetic algorithm and local search. The local search procedure is an iterative process repeating neighbor generation, neighbor evaluation, and neighbor selection. We take a problem-specific heuristic for neighbor generation and propose several strategies for neighbor evaluation and neighbor selection. Archive injection (adding non-dominated solutions to the population) is another issue under investigation. We examine the effects of the proposed strategies through experiments using forty widely used problem instances with different scales. We also evaluate the proposed approach by comparing it with other twenty-six ones in terms of three performance metrics. Our approach outperforms all benchmarks and updates a large portion of the sets of best known non-dominated solutions for large-scale instances.

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

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

U2 - 10.1109/CEC.2010.5586141

DO - 10.1109/CEC.2010.5586141

M3 - Conference contribution

AN - SCOPUS:79959436321

SN - 9781424469109

T3 - 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010

BT - 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010

ER -