Improved Precedence Preservation Crossover for Multi-objective Job Shop Scheduling Problem

K.S.N. Ripon, N.H. Siddique, J. Torresen

Research output: Contribution to journalArticle

16 Citations (Scopus)

Abstract

Over the last three decades, a great deal of research has been focused on solving the job-shop scheduling problem (JSSP). Researchers have emerged with a wide variety of approaches to solve this stubborn problem. Recently much effort has been concentrated on evolutionary techniques to search for the near-optimal solutions optimizing multiple criteria simultaneously. The choice of crossover operator is very important in the aspect of genetic algorithms (GA), and consequently a wide range of crossover operators have been proposed for JSSP. Most of them represent a solution by a chromosome containing the sequence of all the operations and decode the chromosome to a real schedule from the first gene to the last gene. However, these methods introduce high redundancy at the tail of the chromosome. In this paper, we address this problem in case of precedence preservation crossover (PPX) which is regarded as one of the better crossover operators and propose an improved version, termed as improved precedence preservation crossover (IPPX). Experimental results reveal that our proposed approach finds the near-optimal solutions by optimizing multiple criteria simultaneously with better results and also reduces the execution time significantly.
LanguageEnglish
Pages119-129
JournalEvolving Systems
Volume2
Issue number2
DOIs
Publication statusPublished - 1 Jun 2011

Fingerprint

Chromosomes
Mathematical operators
Genes
Redundancy
Genetic algorithms
Job shop scheduling

Cite this

@article{65496e7b22fd42cca76a8d954006fed6,
title = "Improved Precedence Preservation Crossover for Multi-objective Job Shop Scheduling Problem",
abstract = "Over the last three decades, a great deal of research has been focused on solving the job-shop scheduling problem (JSSP). Researchers have emerged with a wide variety of approaches to solve this stubborn problem. Recently much effort has been concentrated on evolutionary techniques to search for the near-optimal solutions optimizing multiple criteria simultaneously. The choice of crossover operator is very important in the aspect of genetic algorithms (GA), and consequently a wide range of crossover operators have been proposed for JSSP. Most of them represent a solution by a chromosome containing the sequence of all the operations and decode the chromosome to a real schedule from the first gene to the last gene. However, these methods introduce high redundancy at the tail of the chromosome. In this paper, we address this problem in case of precedence preservation crossover (PPX) which is regarded as one of the better crossover operators and propose an improved version, termed as improved precedence preservation crossover (IPPX). Experimental results reveal that our proposed approach finds the near-optimal solutions by optimizing multiple criteria simultaneously with better results and also reduces the execution time significantly.",
author = "K.S.N. Ripon and N.H. Siddique and J. Torresen",
year = "2011",
month = "6",
day = "1",
doi = "10.1007/s12530-010-9022-x",
language = "English",
volume = "2",
pages = "119--129",
journal = "Evolving Systems",
issn = "1868-6478",
number = "2",

}

Improved Precedence Preservation Crossover for Multi-objective Job Shop Scheduling Problem. / Ripon, K.S.N.; Siddique, N.H.; Torresen, J.

In: Evolving Systems, Vol. 2, No. 2, 01.06.2011, p. 119-129.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Improved Precedence Preservation Crossover for Multi-objective Job Shop Scheduling Problem

AU - Ripon, K.S.N.

AU - Siddique, N.H.

AU - Torresen, J.

PY - 2011/6/1

Y1 - 2011/6/1

N2 - Over the last three decades, a great deal of research has been focused on solving the job-shop scheduling problem (JSSP). Researchers have emerged with a wide variety of approaches to solve this stubborn problem. Recently much effort has been concentrated on evolutionary techniques to search for the near-optimal solutions optimizing multiple criteria simultaneously. The choice of crossover operator is very important in the aspect of genetic algorithms (GA), and consequently a wide range of crossover operators have been proposed for JSSP. Most of them represent a solution by a chromosome containing the sequence of all the operations and decode the chromosome to a real schedule from the first gene to the last gene. However, these methods introduce high redundancy at the tail of the chromosome. In this paper, we address this problem in case of precedence preservation crossover (PPX) which is regarded as one of the better crossover operators and propose an improved version, termed as improved precedence preservation crossover (IPPX). Experimental results reveal that our proposed approach finds the near-optimal solutions by optimizing multiple criteria simultaneously with better results and also reduces the execution time significantly.

AB - Over the last three decades, a great deal of research has been focused on solving the job-shop scheduling problem (JSSP). Researchers have emerged with a wide variety of approaches to solve this stubborn problem. Recently much effort has been concentrated on evolutionary techniques to search for the near-optimal solutions optimizing multiple criteria simultaneously. The choice of crossover operator is very important in the aspect of genetic algorithms (GA), and consequently a wide range of crossover operators have been proposed for JSSP. Most of them represent a solution by a chromosome containing the sequence of all the operations and decode the chromosome to a real schedule from the first gene to the last gene. However, these methods introduce high redundancy at the tail of the chromosome. In this paper, we address this problem in case of precedence preservation crossover (PPX) which is regarded as one of the better crossover operators and propose an improved version, termed as improved precedence preservation crossover (IPPX). Experimental results reveal that our proposed approach finds the near-optimal solutions by optimizing multiple criteria simultaneously with better results and also reduces the execution time significantly.

U2 - 10.1007/s12530-010-9022-x

DO - 10.1007/s12530-010-9022-x

M3 - Article

VL - 2

SP - 119

EP - 129

JO - Evolving Systems

T2 - Evolving Systems

JF - Evolving Systems

SN - 1868-6478

IS - 2

ER -