A polynomial time approximation scheme for a single machine scheduling problem using a hybrid evolutionary algorithm

Boris Mitavskiy, Jun He

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

2 Citations (SciVal)

Abstract

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.
Original languageEnglish
Title of host publication2012 IEEE Congress on Evolutionary Computation (CEC)
PublisherIEEE Press
Pages1-8
ISBN (Electronic)978-1-4673-1508-1
ISBN (Print)978-1-4673-1510-4
DOIs
Publication statusPublished - Jun 2012
Event2012 IEEE Congress on Evolutionary Computation (CEC) - Brisbane, Australia, United Kingdom of Great Britain and Northern Ireland
Duration: 10 Jun 201215 Jun 2012

Conference

Conference2012 IEEE Congress on Evolutionary Computation (CEC)
Country/TerritoryUnited Kingdom of Great Britain and Northern Ireland
Period10 Jun 201215 Jun 2012

Fingerprint

Dive into the research topics of 'A polynomial time approximation scheme for a single machine scheduling problem using a hybrid evolutionary algorithm'. Together they form a unique fingerprint.

Cite this