Dynamic hard-real-time scheduling using genetic algorithm for multiprocessor task with resource and timing constraints

Shu Chen Cheng, Der Fang Shiau, Yueh-Min Huang, Yen Ting Lin

Research output: Contribution to journalArticle

29 Citations (Scopus)

Abstract

Most publications in shop scheduling area focus on the static scheduling problems and seldom take into account the dynamic disturbances such as machine breakdown or new job arrivals. Motivated by the computational complexity of the scheduling problems, genetic algorithms (GAs) have been applied to improve both the efficiency and the effectiveness for NP-hard optimization problems. However, a pure GA-based approach tends to generate illegal schedules due to the crossover and the mutation operators. It is often the case that the gene expression or the genetic operators need to be specially tailored to fit the problem domain or some other schemes may be combined to solve the scheduling problems. This study presents a GA-based approach combined with a feasible energy function for multiprocessor scheduling problems with resource and timing constraints in dynamic real-time scheduling. Moreover, an easy-understood genotype is designed to generate legal schedules. The results of the experiments demonstrate that the proposed approach performs rapid convergence to address its applicability and generate good-quality schedules.

Original languageEnglish
Pages (from-to)852-860
Number of pages9
JournalExpert Systems With Applications
Volume36
Issue number1
DOIs
Publication statusPublished - 2009 Jan 1

Fingerprint

Scheduling algorithms
Genetic algorithms
Scheduling
Gene expression
Computational complexity
Experiments

All Science Journal Classification (ASJC) codes

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

Cite this

@article{3962b1beb08d4ac384eb80c44c52e956,
title = "Dynamic hard-real-time scheduling using genetic algorithm for multiprocessor task with resource and timing constraints",
abstract = "Most publications in shop scheduling area focus on the static scheduling problems and seldom take into account the dynamic disturbances such as machine breakdown or new job arrivals. Motivated by the computational complexity of the scheduling problems, genetic algorithms (GAs) have been applied to improve both the efficiency and the effectiveness for NP-hard optimization problems. However, a pure GA-based approach tends to generate illegal schedules due to the crossover and the mutation operators. It is often the case that the gene expression or the genetic operators need to be specially tailored to fit the problem domain or some other schemes may be combined to solve the scheduling problems. This study presents a GA-based approach combined with a feasible energy function for multiprocessor scheduling problems with resource and timing constraints in dynamic real-time scheduling. Moreover, an easy-understood genotype is designed to generate legal schedules. The results of the experiments demonstrate that the proposed approach performs rapid convergence to address its applicability and generate good-quality schedules.",
author = "Cheng, {Shu Chen} and Shiau, {Der Fang} and Yueh-Min Huang and Lin, {Yen Ting}",
year = "2009",
month = "1",
day = "1",
doi = "10.1016/j.eswa.2007.10.037",
language = "English",
volume = "36",
pages = "852--860",
journal = "Expert Systems with Applications",
issn = "0957-4174",
publisher = "Elsevier Limited",
number = "1",

}

Dynamic hard-real-time scheduling using genetic algorithm for multiprocessor task with resource and timing constraints. / Cheng, Shu Chen; Shiau, Der Fang; Huang, Yueh-Min; Lin, Yen Ting.

In: Expert Systems With Applications, Vol. 36, No. 1, 01.01.2009, p. 852-860.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Dynamic hard-real-time scheduling using genetic algorithm for multiprocessor task with resource and timing constraints

AU - Cheng, Shu Chen

AU - Shiau, Der Fang

AU - Huang, Yueh-Min

AU - Lin, Yen Ting

PY - 2009/1/1

Y1 - 2009/1/1

N2 - Most publications in shop scheduling area focus on the static scheduling problems and seldom take into account the dynamic disturbances such as machine breakdown or new job arrivals. Motivated by the computational complexity of the scheduling problems, genetic algorithms (GAs) have been applied to improve both the efficiency and the effectiveness for NP-hard optimization problems. However, a pure GA-based approach tends to generate illegal schedules due to the crossover and the mutation operators. It is often the case that the gene expression or the genetic operators need to be specially tailored to fit the problem domain or some other schemes may be combined to solve the scheduling problems. This study presents a GA-based approach combined with a feasible energy function for multiprocessor scheduling problems with resource and timing constraints in dynamic real-time scheduling. Moreover, an easy-understood genotype is designed to generate legal schedules. The results of the experiments demonstrate that the proposed approach performs rapid convergence to address its applicability and generate good-quality schedules.

AB - Most publications in shop scheduling area focus on the static scheduling problems and seldom take into account the dynamic disturbances such as machine breakdown or new job arrivals. Motivated by the computational complexity of the scheduling problems, genetic algorithms (GAs) have been applied to improve both the efficiency and the effectiveness for NP-hard optimization problems. However, a pure GA-based approach tends to generate illegal schedules due to the crossover and the mutation operators. It is often the case that the gene expression or the genetic operators need to be specially tailored to fit the problem domain or some other schemes may be combined to solve the scheduling problems. This study presents a GA-based approach combined with a feasible energy function for multiprocessor scheduling problems with resource and timing constraints in dynamic real-time scheduling. Moreover, an easy-understood genotype is designed to generate legal schedules. The results of the experiments demonstrate that the proposed approach performs rapid convergence to address its applicability and generate good-quality schedules.

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

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

U2 - 10.1016/j.eswa.2007.10.037

DO - 10.1016/j.eswa.2007.10.037

M3 - Article

VL - 36

SP - 852

EP - 860

JO - Expert Systems with Applications

JF - Expert Systems with Applications

SN - 0957-4174

IS - 1

ER -