A. V. Eremeev, Yu. V. Kovalenko, “On complexity of optimal recombination for one scheduling problem with setup times”, Diskretn. Anal. Issled. Oper., 2012, Volume 19, Issue 3,Pages <nobr>13

This article is cited in 1 paper

On complexity of optimal recombination for one scheduling problem with setup times

A. V. Eremeev^a, Yu. V. Kovalenko^b

^a Omsk department of S. L. Sobolev Institute of Mathematics, SB RAS, Omsk, Russia
^b Dostoevsky Omsk State University, Omsk, Russia

Abstract: Computational complexity of optimal recombination for one scheduling problem with setup times is considered. Strong NP-hardness of this optimal recombination problem is proven and an algorithm for its solution is proposed. The algorithm is shown to be polynomial for “almost all” instances of the optimal recombination problem. Ill. 2, bibliogr. 19.

Keywords: scheduling, setup time, genetic algorithm, optimal recombination.

UDC: 519.718

Received: 19.07.2011
Revised: 17.11.2011