A two-stage hybrid memetic algorithm for multiobjective job shop scheduling

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

Research output: Contribution to journalArticle

20 Citations (Scopus)

Abstract

In this paper we address multiobjective job shop scheduling problems. After several decades of research in scheduling problems, a variety of heuristics have been developed. The proposed algorithm is a hybrid of three frequently applied ones: the dispatching rule, the shifting bottleneck procedure, and the evolutionary algorithm. It is a two-stage algorithm, which integrates a rule-based memetic algorithm in the first stage and a re-optimization procedure of shifting bottleneck in the second. We conduct experiments using benchmark instances found in the literature to assess the performance of the proposed method. The experimental results show that the proposed method is effective and efficient for multiobjective scheduling problems.

Original languageEnglish
Pages (from-to)10983-10998
Number of pages16
JournalExpert Systems with Applications
Volume38
Issue number9
DOIs
Publication statusPublished - 2011 Sep 1

Fingerprint

Scheduling
Evolutionary algorithms
Job shop scheduling
Experiments

Keywords

  • Dispatching rules
  • Genetic algorithm
  • Job shop
  • Multiobjective
  • Scheduling
  • Shifting bottleneck heuristic

ASJC Scopus subject areas

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

Cite this

A two-stage hybrid memetic algorithm for multiobjective job shop scheduling. / Cheng, Hsueh Chien; Chiang, Tsung-Che; Fu, Li Chen.

In: Expert Systems with Applications, Vol. 38, No. 9, 01.09.2011, p. 10983-10998.

Research output: Contribution to journalArticle

@article{64a5c72671544d2aadd4defb164a6e3c,
title = "A two-stage hybrid memetic algorithm for multiobjective job shop scheduling",
abstract = "In this paper we address multiobjective job shop scheduling problems. After several decades of research in scheduling problems, a variety of heuristics have been developed. The proposed algorithm is a hybrid of three frequently applied ones: the dispatching rule, the shifting bottleneck procedure, and the evolutionary algorithm. It is a two-stage algorithm, which integrates a rule-based memetic algorithm in the first stage and a re-optimization procedure of shifting bottleneck in the second. We conduct experiments using benchmark instances found in the literature to assess the performance of the proposed method. The experimental results show that the proposed method is effective and efficient for multiobjective scheduling problems.",
keywords = "Dispatching rules, Genetic algorithm, Job shop, Multiobjective, Scheduling, Shifting bottleneck heuristic",
author = "Cheng, {Hsueh Chien} and Tsung-Che Chiang and Fu, {Li Chen}",
year = "2011",
month = "9",
day = "1",
doi = "10.1016/j.eswa.2011.02.142",
language = "English",
volume = "38",
pages = "10983--10998",
journal = "Expert Systems with Applications",
issn = "0957-4174",
publisher = "Elsevier Limited",
number = "9",

}

TY - JOUR

T1 - A two-stage hybrid memetic algorithm for multiobjective job shop scheduling

AU - Cheng, Hsueh Chien

AU - Chiang, Tsung-Che

AU - Fu, Li Chen

PY - 2011/9/1

Y1 - 2011/9/1

N2 - In this paper we address multiobjective job shop scheduling problems. After several decades of research in scheduling problems, a variety of heuristics have been developed. The proposed algorithm is a hybrid of three frequently applied ones: the dispatching rule, the shifting bottleneck procedure, and the evolutionary algorithm. It is a two-stage algorithm, which integrates a rule-based memetic algorithm in the first stage and a re-optimization procedure of shifting bottleneck in the second. We conduct experiments using benchmark instances found in the literature to assess the performance of the proposed method. The experimental results show that the proposed method is effective and efficient for multiobjective scheduling problems.

AB - In this paper we address multiobjective job shop scheduling problems. After several decades of research in scheduling problems, a variety of heuristics have been developed. The proposed algorithm is a hybrid of three frequently applied ones: the dispatching rule, the shifting bottleneck procedure, and the evolutionary algorithm. It is a two-stage algorithm, which integrates a rule-based memetic algorithm in the first stage and a re-optimization procedure of shifting bottleneck in the second. We conduct experiments using benchmark instances found in the literature to assess the performance of the proposed method. The experimental results show that the proposed method is effective and efficient for multiobjective scheduling problems.

KW - Dispatching rules

KW - Genetic algorithm

KW - Job shop

KW - Multiobjective

KW - Scheduling

KW - Shifting bottleneck heuristic

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

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

U2 - 10.1016/j.eswa.2011.02.142

DO - 10.1016/j.eswa.2011.02.142

M3 - Article

AN - SCOPUS:79955605067

VL - 38

SP - 10983

EP - 10998

JO - Expert Systems with Applications

JF - Expert Systems with Applications

SN - 0957-4174

IS - 9

ER -