A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling

Andrew M. Sutton; Frank Neumann

doi:10.1007/978-3-642-32937-1_6

A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling

Andrew M. Sutton, Frank Neumann

Computer Science (Duluth)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

22 Scopus citations

Abstract

We consider simple multi-start evolutionary algorithms applied to the classical NP-hard combinatorial optimization problem of Makespan Scheduling on two machines. We study the dependence of the runtime of this type of algorithm on three different key hardness parameters. By doing this, we provide further structural insights into the behavior of evolutionary algorithms for this classical problem.

Original language	English (US)
Title of host publication	Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings
Pages	52-61
Number of pages	10
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-32937-1_6
State	Published - 2012
Event	12th International Conference on Parallel Problem Solving from Nature, PPSN 2012 - Taormina, Italy Duration: Sep 1 2012 → Sep 5 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	7491 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	12th International Conference on Parallel Problem Solving from Nature, PPSN 2012
Country/Territory	Italy
City	Taormina
Period	9/1/12 → 9/5/12

Publisher link

10.1007/978-3-642-32937-1_6

Find It

Find It at U of M Libraries

Cite this

Sutton, A. M., & Neumann, F. (2012). A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling. In Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings (PART 1 ed., pp. 52-61). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7491 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-32937-1_6

A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling. / Sutton, Andrew M.; Neumann, Frank.
Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings. PART 1. ed. 2012. p. 52-61 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7491 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Sutton, AM & Neumann, F 2012, A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling. in Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 7491 LNCS, pp. 52-61, 12th International Conference on Parallel Problem Solving from Nature, PPSN 2012, Taormina, Italy, 9/1/12. https://doi.org/10.1007/978-3-642-32937-1_6

Sutton AM, Neumann F. A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling. In Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings. PART 1 ed. 2012. p. 52-61. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-32937-1_6

Sutton, Andrew M. ; Neumann, Frank. / A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling. Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings. PART 1. ed. 2012. pp. 52-61 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{9eb9c473d66c46b9acc068eb810b7ff2,

title = "A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling",

abstract = "We consider simple multi-start evolutionary algorithms applied to the classical NP-hard combinatorial optimization problem of Makespan Scheduling on two machines. We study the dependence of the runtime of this type of algorithm on three different key hardness parameters. By doing this, we provide further structural insights into the behavior of evolutionary algorithms for this classical problem.",

author = "Sutton, {Andrew M.} and Frank Neumann",

year = "2012",

doi = "10.1007/978-3-642-32937-1_6",

language = "English (US)",

isbn = "9783642329364",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "52--61",

booktitle = "Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings",

edition = "PART 1",

note = "12th International Conference on Parallel Problem Solving from Nature, PPSN 2012 ; Conference date: 01-09-2012 Through 05-09-2012",

}

TY - GEN

T1 - A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling

AU - Sutton, Andrew M.

AU - Neumann, Frank

PY - 2012

Y1 - 2012

N2 - We consider simple multi-start evolutionary algorithms applied to the classical NP-hard combinatorial optimization problem of Makespan Scheduling on two machines. We study the dependence of the runtime of this type of algorithm on three different key hardness parameters. By doing this, we provide further structural insights into the behavior of evolutionary algorithms for this classical problem.

AB - We consider simple multi-start evolutionary algorithms applied to the classical NP-hard combinatorial optimization problem of Makespan Scheduling on two machines. We study the dependence of the runtime of this type of algorithm on three different key hardness parameters. By doing this, we provide further structural insights into the behavior of evolutionary algorithms for this classical problem.

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

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

U2 - 10.1007/978-3-642-32937-1_6

DO - 10.1007/978-3-642-32937-1_6

M3 - Conference contribution

AN - SCOPUS:84866390440

SN - 9783642329364

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 52

EP - 61

BT - Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings

T2 - 12th International Conference on Parallel Problem Solving from Nature, PPSN 2012

Y2 - 1 September 2012 through 5 September 2012

ER -

A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling

Abstract

Publication series

Other

Publisher link

Find It

Other files and links

Fingerprint

Cite this