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 logistics and manufacturing, optimization is rarely a static, one-time task. Environments are inherently dynamic: machines may fail, or the processing requirements of a job might fluctuate after a schedule has been established. While Evolutionary Algorithms (EAs) and Randomized Local Search (RLS) are frequently applied to these dynamic problems in practice, there has been a significant gap in our theoretical understanding of their performance. This paper provides the first rigorous computational complexity analysis of how these heuristics handle dynamic makespan scheduling.
The Dynamic Scheduling Model
The authors focus on the classic problem of makespan scheduling on two machines. Given a set of $n$ jobs with processing times $p_1, \dots, p_n$, the goal is to partition the jobs between two machines to minimize the makespan—the time at which the last machine finishes its work. In a two-machine setup, this is equivalent to minimizing the discrepancy, or the absolute difference in load between the two machines.
To model dynamic environments, the paper considers two distinct types of change:
- The Adversary Model: A "strong" opponent is permitted to select one job and change its size to any value within a fixed range $[L, U]$. This represents a worst-case scenario where changes are designed to disrupt the current schedule.
- The Random Model: A job is selected at random, and its size undergoes a "random walk," increasing or decreasing by a unit of 1. This simulates natural, stochastic fluctuations in processing times.
Algorithmic Approaches
The study evaluates two fundamental search heuristics to determine how quickly they can "track" the optimal solution after a change occurs:
- Randomized Local Search (RLS): This algorithm selects a single job at random and attempts to move it to the other machine. The move is accepted only if it does not increase the total makespan.
- (1+1) Evolutionary Algorithm (EA): A more flexible heuristic that uses bit-flip mutation, allowing it to move multiple jobs simultaneously in a single iteration. Like RLS, it only accepts changes that do not worsen the objective function.
Complexity Analysis and Key Insights
Using drift analysis—a mathematical technique that calculates the expected time to reach a goal based on the average progress per step—the authors derived several key insights into the robustness of these algorithms.
The Efficiency of RLS
One of the more surprising findings is that RLS is often more effective than the (1+1) EA in the adversary model. Specifically, RLS can maintain a discrepancy of at most $U$ (the maximum job size) in $O(n \min\{\log n, \log R\})$ expected iterations, where $R$ is the ratio of maximum to minimum job size. In contrast, the (1+1) EA requires $O(n^{3/2})$ iterations. The simplicity of RLS—moving only one job at a time—prevents the "chaos" that can occur in EAs when multiple simultaneous moves inadvertently increase the discrepancy.
The "Gap" Lemma and Random Fluctuations
In the random model, the authors prove a "Gap" Lemma, which demonstrates that large gaps in the distribution of job sizes are rare. This is mathematically significant because it ensures the algorithm can almost always find a job to move (or a pair to swap) that will incrementally reduce the discrepancy. Under this model, the (1+1) EA can achieve a very small discrepancy of $O(\log n)$ in $O(n^4 \log n)$ iterations.
Negligible Relative Error
The research also highlights the self-correcting nature of these heuristics. In the random model, the expected ratio between the discrepancy and the total makespan is at most $6/n$. As the number of jobs $n$ increases, this relative error becomes negligible, proving that these simple algorithms remain remarkably close to the true optimum even under constant change.
Conclusion
This work establishes a theoretical foundation for using EAs and RLS in dynamic scheduling. It proves that these algorithms are not just practical heuristics but are mathematically guaranteed to track optimal or near-optimal solutions in polynomial time. While this study is limited to the two-machine case, it opens the door for future research into $m$-machine scaling, population-based EAs, and more complex dynamic events such as the arrival or removal of jobs.
Summary updated