A rule-centric memetic algorithm to minimize the number of tardy jobs in the job shop

T. C. Chiang, L. C. Fu

Research output: Contribution to journalArticle

20 Citations (Scopus)

Abstract

This paper addresses the job shop-scheduling problem with minimizing the number of tardy jobs as the objective. This problem is usually treated as a job-sequencing problem, and the permutation-based representation of solutions was commonly used in the existing search-based approaches. In this paper, the flaw of the permutation-based representation is discussed, and a rule-centric concept is proposed to deal with it. A memetic algorithm is then developed to realize the proposed idea by tailored genome encoding/decoding schemes and a local search procedure. Two benchmark approaches, a multi-start hill-climbing approach and a simulated annealing approach, are compared in the experiments. The results show that the proposed approach significantly outperforms the benchmarks.

Original languageEnglish
Pages (from-to)6913-6931
Number of pages19
JournalInternational Journal of Production Research
Volume46
Issue number24
DOIs
Publication statusPublished - 2008 Dec 1

Fingerprint

Simulated annealing
Decoding
Genes
Defects
Experiments
Job shop scheduling
Local search (optimization)
Memetic algorithm
Job shop

Keywords

  • Job shop-scheduling
  • Memetic algorithm
  • Priority rules

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Cite this

A rule-centric memetic algorithm to minimize the number of tardy jobs in the job shop. / Chiang, T. C.; Fu, L. C.

In: International Journal of Production Research, Vol. 46, No. 24, 01.12.2008, p. 6913-6931.

Research output: Contribution to journalArticle

@article{8d49dfbe998e4a0da3374cb2cc1a09e7,
title = "A rule-centric memetic algorithm to minimize the number of tardy jobs in the job shop",
abstract = "This paper addresses the job shop-scheduling problem with minimizing the number of tardy jobs as the objective. This problem is usually treated as a job-sequencing problem, and the permutation-based representation of solutions was commonly used in the existing search-based approaches. In this paper, the flaw of the permutation-based representation is discussed, and a rule-centric concept is proposed to deal with it. A memetic algorithm is then developed to realize the proposed idea by tailored genome encoding/decoding schemes and a local search procedure. Two benchmark approaches, a multi-start hill-climbing approach and a simulated annealing approach, are compared in the experiments. The results show that the proposed approach significantly outperforms the benchmarks.",
keywords = "Job shop-scheduling, Memetic algorithm, Priority rules",
author = "Chiang, {T. C.} and Fu, {L. C.}",
year = "2008",
month = "12",
day = "1",
doi = "10.1080/00207540701420578",
language = "English",
volume = "46",
pages = "6913--6931",
journal = "International Journal of Production Research",
issn = "0020-7543",
publisher = "Taylor and Francis Ltd.",
number = "24",

}

TY - JOUR

T1 - A rule-centric memetic algorithm to minimize the number of tardy jobs in the job shop

AU - Chiang, T. C.

AU - Fu, L. C.

PY - 2008/12/1

Y1 - 2008/12/1

N2 - This paper addresses the job shop-scheduling problem with minimizing the number of tardy jobs as the objective. This problem is usually treated as a job-sequencing problem, and the permutation-based representation of solutions was commonly used in the existing search-based approaches. In this paper, the flaw of the permutation-based representation is discussed, and a rule-centric concept is proposed to deal with it. A memetic algorithm is then developed to realize the proposed idea by tailored genome encoding/decoding schemes and a local search procedure. Two benchmark approaches, a multi-start hill-climbing approach and a simulated annealing approach, are compared in the experiments. The results show that the proposed approach significantly outperforms the benchmarks.

AB - This paper addresses the job shop-scheduling problem with minimizing the number of tardy jobs as the objective. This problem is usually treated as a job-sequencing problem, and the permutation-based representation of solutions was commonly used in the existing search-based approaches. In this paper, the flaw of the permutation-based representation is discussed, and a rule-centric concept is proposed to deal with it. A memetic algorithm is then developed to realize the proposed idea by tailored genome encoding/decoding schemes and a local search procedure. Two benchmark approaches, a multi-start hill-climbing approach and a simulated annealing approach, are compared in the experiments. The results show that the proposed approach significantly outperforms the benchmarks.

KW - Job shop-scheduling

KW - Memetic algorithm

KW - Priority rules

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

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

U2 - 10.1080/00207540701420578

DO - 10.1080/00207540701420578

M3 - Article

AN - SCOPUS:55349112552

VL - 46

SP - 6913

EP - 6931

JO - International Journal of Production Research

JF - International Journal of Production Research

SN - 0020-7543

IS - 24

ER -