Evolutionary algorithms for the project scheduling problem: Runtime analysis and improved design

Leandro L. MINKU; Dirk SUDHOLT; Xin YAO

doi:10.1145/2330163.2330332

Evolutionary algorithms for the project scheduling problem: Runtime analysis and improved design

Leandro L. MINKU, Dirk SUDHOLT, Xin YAO

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

15 Citations (Scopus)

Abstract

Even though genetic algorithms (GAs) have been used for solving the project scheduling problem (PSP), it is not well understood which problem characteristics make it difficult/easy for GAs. We present the first runtime analysis for the PSP, revealing what problem features can make PSP easy or hard. This allows to assess the performance of GAs and to make informed design choices. Our theory has inspired a new evolutionary design, including normalisation of employees' dedication for different tasks to eliminate the problem of exceeding their maximum dedication. Theoretical and empirical results show that our design is very effective in terms of hit rate and solution quality. © 2012 ACM.

Original language	English
Title of host publication	GECCO'12 - Proceedings of the 14th International Conference on Genetic and Evolutionary Computation
Pages	1221-1228
Number of pages	8
DOIs	https://doi.org/10.1145/2330163.2330332
Publication status	Published - 7 Jul 2012
Externally published	Yes

Keywords

evolutionary algorithms
project scheduling
runtime analysis
search-based software engineering
theory

Access to Document

10.1145/2330163.2330332

Cite this

@inproceedings{598d6ccf9fcf4be389b737cce691e93d,

title = "Evolutionary algorithms for the project scheduling problem: Runtime analysis and improved design",

abstract = "Even though genetic algorithms (GAs) have been used for solving the project scheduling problem (PSP), it is not well understood which problem characteristics make it difficult/easy for GAs. We present the first runtime analysis for the PSP, revealing what problem features can make PSP easy or hard. This allows to assess the performance of GAs and to make informed design choices. Our theory has inspired a new evolutionary design, including normalisation of employees' dedication for different tasks to eliminate the problem of exceeding their maximum dedication. Theoretical and empirical results show that our design is very effective in terms of hit rate and solution quality. {\textcopyright} 2012 ACM.",

keywords = "evolutionary algorithms, project scheduling, runtime analysis, search-based software engineering, theory",

author = "MINKU, {Leandro L.} and Dirk SUDHOLT and Xin YAO",

year = "2012",

month = jul,

day = "7",

doi = "10.1145/2330163.2330332",

language = "English",

isbn = "9781450311779",

pages = "1221--1228",

booktitle = "GECCO'12 - Proceedings of the 14th International Conference on Genetic and Evolutionary Computation",

}

Evolutionary algorithms for the project scheduling problem: Runtime analysis and improved design. / MINKU, Leandro L.; SUDHOLT, Dirk; YAO, Xin.
GECCO'12 - Proceedings of the 14th International Conference on Genetic and Evolutionary Computation. 2012. p. 1221-1228.

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

TY - GEN

T1 - Evolutionary algorithms for the project scheduling problem: Runtime analysis and improved design

AU - MINKU, Leandro L.

AU - SUDHOLT, Dirk

AU - YAO, Xin

PY - 2012/7/7

Y1 - 2012/7/7

N2 - Even though genetic algorithms (GAs) have been used for solving the project scheduling problem (PSP), it is not well understood which problem characteristics make it difficult/easy for GAs. We present the first runtime analysis for the PSP, revealing what problem features can make PSP easy or hard. This allows to assess the performance of GAs and to make informed design choices. Our theory has inspired a new evolutionary design, including normalisation of employees' dedication for different tasks to eliminate the problem of exceeding their maximum dedication. Theoretical and empirical results show that our design is very effective in terms of hit rate and solution quality. © 2012 ACM.

AB - Even though genetic algorithms (GAs) have been used for solving the project scheduling problem (PSP), it is not well understood which problem characteristics make it difficult/easy for GAs. We present the first runtime analysis for the PSP, revealing what problem features can make PSP easy or hard. This allows to assess the performance of GAs and to make informed design choices. Our theory has inspired a new evolutionary design, including normalisation of employees' dedication for different tasks to eliminate the problem of exceeding their maximum dedication. Theoretical and empirical results show that our design is very effective in terms of hit rate and solution quality. © 2012 ACM.

KW - evolutionary algorithms

KW - project scheduling

KW - runtime analysis

KW - search-based software engineering

KW - theory

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

U2 - 10.1145/2330163.2330332

DO - 10.1145/2330163.2330332

M3 - Conference paper (refereed)

SN - 9781450311779

SP - 1221

EP - 1228

BT - GECCO'12 - Proceedings of the 14th International Conference on Genetic and Evolutionary Computation

ER -

Evolutionary algorithms for the project scheduling problem: Runtime analysis and improved design

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this