Performance Analysis of the (1+1) Evolutionary Algorithm for the Multiprocessor Scheduling Problem
In recent years, there has been considerable progress in the theoretical study of evolutionary algorithms (EAs) for discrete optimization problems. However, results on the performance analysis of EAs for NP-hard problems are rare. This paper contributes a theoretical understanding of EAs on the NP-hard multiprocessor scheduling problem. The worst-case bound on the (1+1)EA for the multiprocessor scheduling problem and a worst-case example are presented. It is proved that the (1+1)EA on \(Q2\mid \mid C_\mathrm{max}\) problem achieves an approximation ratio of \(\frac{1+\sqrt{5}}{2}\) in expected time \(O(n^2)\). Finally, the theoretical analysis on three selected instances of the multiprocessor scheduling problem shows that EAs outperform local search algorithms on these instances.
evolutionary algorithms scheduling problem local search algorithms approximation algorithms analysis of algorithms