Volume 19, No 3, 2012, P. 13-26
UDC 519.718
A. V. Eremeev, Yu. V. Kovalenko
On complexity of optimal recombination for one scheduling problem with setup times
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.
Eremeev Anton Valentinovich 1
Kovalenko Yulia Viktorovna 2
1. Omsk department of S. L. Sobolev Institute of Mathematics, SB RAS,
13 Pevtsova str., 644099 Omsk, Russia
2.
Dostoevsky Omsk State University,
55a Mira ave., 644077 Omsk, Russia
e-mail: eremeev@ofim.oscsbras.ru, juliakoval86@mail.ru
