An Improved Multiobjective Evolutionary Algorithm for Solving the No-wait Flow Shop Scheduling Problem

Tsung Su Yeh, Tsung-Che Chiang

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

Abstract

The no-wait flow shop extends the classical flow shop by considering a practical constraint (in steel, plastic, and several industries) that operations of each job should be processed continuously on machines. In this paper, we propose to use a multiobjective evolutionary algorithm based on decomposition (MOEA/D) for no-wait flow shop scheduling with minimization of makespan and maximum tardiness as two objectives. First, we propose a crossover operator that inherits gene blocks with smaller machine idle time from parent solutions. Second, we investigate the effects of initial population by using different job ordering rules. Third, we generate ninety problem instances and conduct experiments on these instances. Experimental results confirm that our idle-time-based crossover and multi-rule initialization lead to good solution quality. We make all data of problem instances and sets of solutions publicly accessible to promote future research on this topic.

Original languageEnglish
Title of host publication2018 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2018
PublisherIEEE Computer Society
Pages142-147
Number of pages6
ISBN (Electronic)9781538667866
DOIs
Publication statusPublished - 2019 Jan 9
Event2018 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2018 - Bangkok, Thailand
Duration: 2018 Dec 162018 Dec 19

Publication series

NameIEEE International Conference on Industrial Engineering and Engineering Management
Volume2019-December
ISSN (Print)2157-3611
ISSN (Electronic)2157-362X

Conference

Conference2018 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2018
CountryThailand
CityBangkok
Period18/12/1618/12/19

Fingerprint

Evolutionary algorithms
Scheduling
Genes
Plastics
Decomposition
Steel
Industry
Experiments
Flow shop scheduling
Flow shop
No-wait
Crossover
Experiment
Operator
Tardiness
Makespan

Keywords

  • evolutionary algorithms
  • flow shop
  • idle time
  • multiobjective
  • no-wait

ASJC Scopus subject areas

  • Business, Management and Accounting (miscellaneous)
  • Industrial and Manufacturing Engineering
  • Safety, Risk, Reliability and Quality

Cite this

Yeh, T. S., & Chiang, T-C. (2019). An Improved Multiobjective Evolutionary Algorithm for Solving the No-wait Flow Shop Scheduling Problem. In 2018 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2018 (pp. 142-147). [8607486] (IEEE International Conference on Industrial Engineering and Engineering Management; Vol. 2019-December). IEEE Computer Society. https://doi.org/10.1109/IEEM.2018.8607486

An Improved Multiobjective Evolutionary Algorithm for Solving the No-wait Flow Shop Scheduling Problem. / Yeh, Tsung Su; Chiang, Tsung-Che.

2018 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2018. IEEE Computer Society, 2019. p. 142-147 8607486 (IEEE International Conference on Industrial Engineering and Engineering Management; Vol. 2019-December).

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

Yeh, TS & Chiang, T-C 2019, An Improved Multiobjective Evolutionary Algorithm for Solving the No-wait Flow Shop Scheduling Problem. in 2018 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2018., 8607486, IEEE International Conference on Industrial Engineering and Engineering Management, vol. 2019-December, IEEE Computer Society, pp. 142-147, 2018 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2018, Bangkok, Thailand, 18/12/16. https://doi.org/10.1109/IEEM.2018.8607486
Yeh TS, Chiang T-C. An Improved Multiobjective Evolutionary Algorithm for Solving the No-wait Flow Shop Scheduling Problem. In 2018 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2018. IEEE Computer Society. 2019. p. 142-147. 8607486. (IEEE International Conference on Industrial Engineering and Engineering Management). https://doi.org/10.1109/IEEM.2018.8607486
Yeh, Tsung Su ; Chiang, Tsung-Che. / An Improved Multiobjective Evolutionary Algorithm for Solving the No-wait Flow Shop Scheduling Problem. 2018 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2018. IEEE Computer Society, 2019. pp. 142-147 (IEEE International Conference on Industrial Engineering and Engineering Management).
@inproceedings{2c096bfeab9a48daabb78748d1894133,
title = "An Improved Multiobjective Evolutionary Algorithm for Solving the No-wait Flow Shop Scheduling Problem",
abstract = "The no-wait flow shop extends the classical flow shop by considering a practical constraint (in steel, plastic, and several industries) that operations of each job should be processed continuously on machines. In this paper, we propose to use a multiobjective evolutionary algorithm based on decomposition (MOEA/D) for no-wait flow shop scheduling with minimization of makespan and maximum tardiness as two objectives. First, we propose a crossover operator that inherits gene blocks with smaller machine idle time from parent solutions. Second, we investigate the effects of initial population by using different job ordering rules. Third, we generate ninety problem instances and conduct experiments on these instances. Experimental results confirm that our idle-time-based crossover and multi-rule initialization lead to good solution quality. We make all data of problem instances and sets of solutions publicly accessible to promote future research on this topic.",
keywords = "evolutionary algorithms, flow shop, idle time, multiobjective, no-wait",
author = "Yeh, {Tsung Su} and Tsung-Che Chiang",
year = "2019",
month = "1",
day = "9",
doi = "10.1109/IEEM.2018.8607486",
language = "English",
series = "IEEE International Conference on Industrial Engineering and Engineering Management",
publisher = "IEEE Computer Society",
pages = "142--147",
booktitle = "2018 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2018",

}

TY - GEN

T1 - An Improved Multiobjective Evolutionary Algorithm for Solving the No-wait Flow Shop Scheduling Problem

AU - Yeh, Tsung Su

AU - Chiang, Tsung-Che

PY - 2019/1/9

Y1 - 2019/1/9

N2 - The no-wait flow shop extends the classical flow shop by considering a practical constraint (in steel, plastic, and several industries) that operations of each job should be processed continuously on machines. In this paper, we propose to use a multiobjective evolutionary algorithm based on decomposition (MOEA/D) for no-wait flow shop scheduling with minimization of makespan and maximum tardiness as two objectives. First, we propose a crossover operator that inherits gene blocks with smaller machine idle time from parent solutions. Second, we investigate the effects of initial population by using different job ordering rules. Third, we generate ninety problem instances and conduct experiments on these instances. Experimental results confirm that our idle-time-based crossover and multi-rule initialization lead to good solution quality. We make all data of problem instances and sets of solutions publicly accessible to promote future research on this topic.

AB - The no-wait flow shop extends the classical flow shop by considering a practical constraint (in steel, plastic, and several industries) that operations of each job should be processed continuously on machines. In this paper, we propose to use a multiobjective evolutionary algorithm based on decomposition (MOEA/D) for no-wait flow shop scheduling with minimization of makespan and maximum tardiness as two objectives. First, we propose a crossover operator that inherits gene blocks with smaller machine idle time from parent solutions. Second, we investigate the effects of initial population by using different job ordering rules. Third, we generate ninety problem instances and conduct experiments on these instances. Experimental results confirm that our idle-time-based crossover and multi-rule initialization lead to good solution quality. We make all data of problem instances and sets of solutions publicly accessible to promote future research on this topic.

KW - evolutionary algorithms

KW - flow shop

KW - idle time

KW - multiobjective

KW - no-wait

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

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

U2 - 10.1109/IEEM.2018.8607486

DO - 10.1109/IEEM.2018.8607486

M3 - Conference contribution

AN - SCOPUS:85061840259

T3 - IEEE International Conference on Industrial Engineering and Engineering Management

SP - 142

EP - 147

BT - 2018 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2018

PB - IEEE Computer Society

ER -