  Nowadays hybrid evolutionary algorithms, i.e, heuristic search algorithms
combining several mutation operators some of which are meant to implement
stochastically a well known technique designed for the specific problem in
question while some others playing the role of random search, have become
rather popular for tackling various NP-hard optimization problems. While
empirical studies demonstrate that hybrid evolutionary algorithms are
frequently successful at finding solutions having fitness sufficiently close to
the optimal, many fewer articles address the computational complexity in a
mathematically rigorous fashion. This paper is devoted to a mathematically
motivated design and analysis of a parameterized family of evolutionary
algorithms which provides a polynomial time approximation scheme for one of the
well-known NP-hard combinatorial optimization problems, namely the "single
machine scheduling problem without precedence constraints". The authors hope
that the techniques and ideas developed in this article may be applied in many
other situations.
