Geodesic
On complexity of optimal recombination for flowshop scheduling problems
Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 2, pp. 41-62

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

Under study is the complexity of optimal recombination for various flowshop scheduling problems with the makespan criterion and the criterion of maximum lateness. The problems are proved to be NP-hard, and a solution algorithm is proposed. In the case of a flowshop problem on permutations, the algorithm is shown to have polynomial complexity for “almost all” pairs of parent solutions as the number of jobs tends to infinity. Ill. 4, bibliogr. 26.
Keywords: flowshop problem, genetic algorithm, optimal recombination.
Mots-clés : permutation 
@article{DA_2016_23_2_a2,
     author = {Yu. V. Kovalenko},
     title = {On complexity of optimal recombination for flowshop scheduling problems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {41--62},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2016_23_2_a2/}
}
TY  - JOUR
AU  - Yu. V. Kovalenko
TI  - On complexity of optimal recombination for flowshop scheduling problems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2016
SP  - 41
EP  - 62
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2016_23_2_a2/
LA  - ru
ID  - DA_2016_23_2_a2
ER  - 
%0 Journal Article
%A Yu. V. Kovalenko
%T On complexity of optimal recombination for flowshop scheduling problems
%J Diskretnyj analiz i issledovanie operacij
%D 2016
%P 41-62
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2016_23_2_a2/
%G ru
%F DA_2016_23_2_a2
Yu. V. Kovalenko. On complexity of optimal recombination for flowshop scheduling problems. Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 2, pp. 41-62. http://geodesic.mathdoc.fr/item/DA_2016_23_2_a2/