On the Runtime of Randomized Local Search and Simple Evolutionary Algorithms for Dynamic Makespan Scheduling

Frank Neumann, Carsten Witt

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

143 Downloads (Pure)

Abstract

Evolutionary algorithms have been frequently used for dynamic optimization problems. With this paper, we contribute to the theoretical understanding of this research area. We present the first computational complexity analysis of evolutionary algorithms for a dynamic variant of a classical combinatorial optimization problem, namely makespan scheduling. We study the model of a strong adversary which is allowed to change one job at regular intervals. Furthermore, we investigate the setting of random changes. Our results show that randomized local search and a simple evolutionary algorithm are very effective in dynamically tracking changes made to the problem instance.
Original languageEnglish
Title of host publicationProceedings of the 24th International Conference on Artificial Intelligence (IJCAI '15)
PublisherAAAI Press
Publication date2015
Pages3742-3748
Article number3742
ISBN (Print)978-1-57735-738-4
Publication statusPublished - 2015
Event24th International Joint Conference on Artificial Intelligence - Buenos Aires, Argentina
Duration: 25 Jul 201531 Jul 2015
Conference number: 24
http://ijcai-15.org/

Conference

Conference24th International Joint Conference on Artificial Intelligence
Number24
Country/TerritoryArgentina
CityBuenos Aires
Period25/07/201531/07/2015
Internet address

Fingerprint

Dive into the research topics of 'On the Runtime of Randomized Local Search and Simple Evolutionary Algorithms for Dynamic Makespan Scheduling'. Together they form a unique fingerprint.

Cite this