Geodesic
On complexity of optimal recombination for one scheduling problem with setup times
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 3, pp. 13-26

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2012_19_3_a1,
     author = {A. V. Eremeev and Yu. V. Kovalenko},
     title = {On complexity of optimal recombination for one scheduling problem with setup times},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {13--26},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_3_a1/}
}
TY  - JOUR
AU  - A. V. Eremeev
AU  - Yu. V. Kovalenko
TI  - On complexity of optimal recombination for one scheduling problem with setup times
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 13
EP  - 26
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_3_a1/
LA  - ru
ID  - DA_2012_19_3_a1
ER  - 
%0 Journal Article
%A A. V. Eremeev
%A Yu. V. Kovalenko
%T On complexity of optimal recombination for one scheduling problem with setup times
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 13-26
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_3_a1/
%G ru
%F DA_2012_19_3_a1
A. V. Eremeev; Yu. V. Kovalenko. On complexity of optimal recombination for one scheduling problem with setup times. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 3, pp. 13-26. http://geodesic.mathdoc.fr/item/DA_2012_19_3_a1/