A Polynomial Time Approximation Scheme for a Single Machine Scheduling Problem Using a Hybrid Evolutionary Algorithm
This work addresses a foundational combinatorial optimization problem for scheduling applications, offering a mathematically rigorous approach to computational complexity, which is incremental in applying evolutionary algorithms with formal guarantees.
The paper tackles the single machine scheduling problem without precedence constraints, an NP-hard optimization problem, by designing a parameterized family of hybrid evolutionary algorithms that achieve a polynomial time approximation scheme, providing solutions with guaranteed approximation quality in polynomial time.
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.