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

arXiv: https://arxiv.org/abs/1504.06363 · HTML: https://mlsanity.com/paper/1504.06363/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2015.

## Built on by (most cited first, 2 of 2)

- [Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover](https://mlsanity.com/paper/2208.08759/) (2022)
- [Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees](https://mlsanity.com/paper/2110.09332/) (2021)

## Abstract (arXiv)

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.