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

Frank Neumann, Carsten Witt

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.

Introduction

In real-world optimization, environments are rarely static. Constraints, objective functions, and problem parameters often shift over time, requiring algorithms that can not only find an initial solution but also adapt to changes efficiently. While Evolutionary Algorithms (EAs) are a popular choice for these dynamic optimization problems in practice, their theoretical foundation has historically lagged behind. This paper addresses this gap by providing the first rigorous computational complexity analysis of EAs applied to a dynamic version of the makespan scheduling problem.

Problem Formulation

The authors focus on the classic problem of makespan scheduling on two machines. Given $n$ jobs with processing times $p_1, \dots, p_n$, the goal is to partition the jobs into two sets (machines) such that the maximum load (the makespan) is minimized. In the two-machine case, this is equivalent to minimizing the "discrepancy" $D$, defined as the absolute difference between the total loads of the two machines: $D = |L_1 - L_2|$.

In the dynamic variant, the processing times of jobs are subject to change. The paper investigates how quickly simple search heuristics can minimize discrepancy and how effectively they can "track" the optimal solution as the environment evolves.

Algorithms and Dynamic Models

The study evaluates two fundamental search heuristics:

  1. Randomized Local Search (RLS): A simple hill-climber that, in each step, selects one job at random and moves it to the other machine.
  2. (1+1) Evolutionary Algorithm (EA): A more flexible heuristic that, in each step, flips the machine assignment of each job independently with a probability of $1/n$.

These algorithms are analyzed under two distinct dynamic models:

  • The Adversary Model: A powerful adversary selects a job and changes its processing time to any value within a bounded range $[L, U]$. This represents a worst-case scenario for the algorithm.
  • The Random Model: Job sizes are integers in the range $[1, n]$. An adversary selects a job, but its size changes via a random walk, increasing or decreasing by exactly 1. This represents a more stable, stochastic environment.

Theoretical Analysis and Methodology

To derive runtime bounds, the authors employ drift analysis, a mathematical framework used to estimate the time until a random process reaches a target state based on its expected progress in each step.

A significant technical challenge arises when analyzing the (1+1) EA. Unlike RLS, which moves only one job at a time, the (1+1) EA can move multiple jobs simultaneously. This can lead to "chaotic" behavior where several large jobs move to one machine while many small jobs move to the other, potentially increasing discrepancy in the short term even if the move is accepted. To overcome this, the authors introduce a novel potential function that accounts for the variance in job sizes across different mathematical regimes, allowing for a rigorous proof of the algorithm's convergence.

Key Results

The Adversarial Model

The analysis shows that both algorithms are robust against adversarial changes, though RLS generally performs more efficiently due to its restricted search operators.

  • Initial Convergence: RLS achieves a discrepancy of at most $U$ (the maximum job size) in an expected $O(n \min\{\log n, \log R\})$ steps, where $R = U/L$ is the ratio of maximum to minimum job size. The (1+1) EA reaches this state in $O(n^{3/2})$ steps.
  • Recovery Time: If the adversary changes a single job, both algorithms recover a discrepancy of $\le U$ very quickly, specifically in $O(\min\{R, n\})$ expected steps.

The Random Model

In the less hostile random model, the algorithms can achieve much higher precision.

  • Tighter Bounds: The (1+1) EA can maintain a discrepancy of $O(\log n)$, which is significantly smaller than the maximum job size $U$.
  • Efficiency: Starting from a worst-case initialization, the (1+1) EA reaches this $O(\log n)$ discrepancy in $O(n^4 \log n)$ steps. If the algorithm is initialized randomly, this time improves to $O(n^{3.5} \log^2 n)$.
  • Optimality: The expected ratio between the discrepancy and the total makespan is bounded by $6/n$, indicating that the solutions tracked by the EA are exceptionally close to the global optimum.

Discussion and Conclusion

This research demonstrates that simple evolutionary heuristics are surprisingly effective at tracking solutions in dynamic environments. RLS is highly efficient for maintaining basic bounds, while the (1+1) EA's ability to perform multi-bit flips allows it to navigate more complex landscapes, albeit with a slightly more complex analysis.

The findings suggest that as long as the frequency of environmental changes is not overwhelmingly high, these algorithms can maintain high-quality solutions. While this study is limited to two machines and simple mutation operators, it provides the theoretical groundwork for future analysis of more complex systems, such as population-based EAs, crossover operators, and problems involving $m > 2$ machines or different combinatorial structures like the Traveling Salesperson Problem.

Summary updated

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.
BibTeX
@inproceedings{neumann2015runtime,
  author = {Frank Neumann and Carsten Witt},
  title = {{On the Runtime of Randomized Local Search and Simple Evolutionary Algorithms for Dynamic Makespan Scheduling}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=B1VMFSfubH},
}
Figure