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/

[1] Berzh K., Teoriya grafov i eë primeneniya, Izd-vo inostr. lit-ry, M., 1962, 319 pp.

[2] Borisovskii P. A., “Geneticheskii algoritm dlya odnoi zadachi sostavleniya proizvodstvennogo raspisaniya s perenaladkami”, Tr. XIV Baik. mezhdunar. shk.-seminara “Metody optimizatsii i ikh prilozheniya”, v. 4, ISEM SO RAN, Irkutsk, 2008, 166–173

[3] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[4] Eremeev A. V., “O slozhnosti optimalnoi rekombinatsii dlya zadachi kommivoyazhëra”, Diskret. analiz i issled. operatsii, 18:1 (2011), 27–40 | MR | Zbl

[5] Eremeev A. V., Kovalenko Yu. V., “O zadache sostavleniya raspisanii s gruppirovkoi mashin po tekhnologiyam”, Diskret. analiz i issled. operatsii, 18:5 (2011), 54–79 | Zbl

[6] Karp R. M., “Svodimost kombinatornykh problem”, Kibernet. sb., 12, Mir, M., 1975, 16–38

[7] Kormen T., Leizerson Ch., Rivest R., Algoritmy: postroenie i analiz, MTsIMO, M., 2001, 960 pp.

[8] Reingold E., Nivergelt Yu., Deo N., Kombinatornye algoritmy, teoriya i praktika, Mir, M., 1980, 476 pp. | MR | Zbl

[9] Serdyukov A. I., “O zadache kommivoyazhëra pri nalichii zapretov”, Upravlyaemye sistemy, 17, 1978, 80–86 | MR | Zbl

[10] Tanaev V. S., Kovalev M. Ya., Shafranskii Ya. M., Teoriya raspisanii. Gruppovye tekhnologii, In-t tekhn. kibernetiki NAN Belarusi, Minsk, 1998, 290 pp.

[11] Cook W., Seymour P., “Tour merging via branch-decomposition”, INFORMS J. Comput., 15:2 (2003), 233–248 | DOI | MR | Zbl

[12] Cotta C., Alba E., Troya J. M., “Utilizing dynastically optimal forma recombination in hybrid genetic algorithms”, Proc. 5th Int. Conf. Parallel Problem Solving from Nature, Lect. Notes Comput. Sci., 1498, Springer-Verl., Berlin, 1998, 305–314 | DOI

[13] Dolgui A., Eremeev A. V., Kovalyov M. Y., Multi-product lot-sizing and scheduling on unrelated parallel machines, Res. Rep. No 2007–500–011, Ecole des Mines de St. Etienne, St. Etienne, 2007, 15 pp.

[14] Eremeev A. V., “On complexity of optimal recombination for binary representations of solutions”, Evolutionary Comput., 16:1 (2008), 127–147 | DOI | MR

[15] Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., “Optimization and approximation in deterministic sequencing and scheduling: a survey”, Ann. Discrete Math., 5 (1979), 287–326 | DOI | MR | Zbl

[16] Hazir Ö., Günalay Y., Erel E., “Customer order scheduling problem: a comparative metaheuristics study”, Int. J. Adv. Manuf. Technology, 37 (2008), 589–598 | DOI

[17] Held M., Karp R. M., “A dynamic programming approach to sequencing problems”, SIAM J. Appl. Math., 10 (1962), 196–210 | DOI | MR | Zbl

[18] Reeves C. R., “Genetic algorithms for the operations researcher”, INFORMS J. Comput., 9:3 (1997), 231–250 | DOI | Zbl

[19] Yagiura M., Ibaraki T., “The use of dynamic programming in genetic algorithms for permutation problems”, Eur. J. Oper. Res., 92 (1996), 387–401 | DOI | Zbl