PPSN XII - LNCS 7491-7492 CD-ROM

A Parameterized Runtime Analysis of Simple Evolutionary Algorithms for Makespan Scheduling

Andrew M. Sutton and Frank Neumann

School of Computer Science, University of Adelaide, Adelaide, SA 5005, Australia

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.

LNCS 7491, p. 52 ff.

Full article in PDF | BibTeX