On the Runtime of Randomized Local Search and Simple Evolutionary Algorithms for Dynamic Makespan Scheduling
This provides theoretical insights for researchers in evolutionary computation and dynamic optimization, but it is incremental as it extends known methods to a dynamic variant of a classical problem.
The paper tackled the problem of dynamic makespan scheduling by analyzing the computational complexity of evolutionary algorithms, showing that randomized local search and a simple evolutionary algorithm effectively track changes with a strong adversary and random modifications.
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.