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/

[1] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR | MR | Zbl

[2] A. V. Eremeev, Yu. V. Kovalenko, “On scheduling with technology based machines grouping”, Diskretn. Anal. Issled. Oper., 18:5 (2011), 54–79 | MR | Zbl

[3] A. V. Eremeev, Yu. V. Kovalenko, “On complexity of optimal recombination for one scheduling problem with setup times”, Diskretn. Anal. Issled. Oper., 19:3 (2012), 13–26 | MR | Zbl

[4] R. W. Conway, W. L. Maxwell, L. W. Miller, Theory of Scheduling, Addison-Wesley, Reading, MA, USA, 1967 | MR | MR | Zbl

[5] T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990 | MR | Zbl

[6] D. Rutkowska, M. Piliński, L. Rutkowski, Neural Networks, Genetic Algorithms and Fuzzy Systems, Naukowe PWN, Warsaw, 1997 (Polish)

[7] A. I. Serdyukov, “On travelling salesman problem with prohibitions”, Controlled Systems, 17, Inst. Mat. SO AN SSSR, Novosibirsk, 1978, 80–86 | MR | Zbl

[8] V. S. Tanaev, Yu. N. Sotskov, V. A. Strusevich, Theory of Scheduling. Multi-Stage Systems, Nauka, Moscow, 1989 | MR

[9] Balas E., Niehaus W., “Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems”, J. Heuristics, 4:2 (1998), 107–122 | DOI | MR | Zbl

[10] Cheng B.-W., Chang C.-L., “A study on flowshop scheduling problem combining Taguchi experimental design and genetic algorithm”, Expert. Syst. Appl., 32:2 (2007), 415–421 | DOI

[11] Chvatal V., “Probabilistic methods in graph theory”, Ann. Oper. Res., 1:3 (1984), 171–182 | DOI | MR | Zbl

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

[13] 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 (Amsterdam, Sept. 27–30, 1998), Lect. Notes Comput. Sci., 1498, Springer-Verl., Heidelberg, 1998, 305–314 | DOI

[14] Cotta C., Troya J. M., “Genetic forma recombination in permutation flowshop problems”, Evol. Comput., 6:1 (1998), 25–44 | DOI

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

[16] Eremeev A. V., Kovalenko Yu. V., “Optimal recombination in genetic algorithms for combinatorial optimization problems: Part I”, Yugoslav J. Oper. Res., 24:1 (2014), 1–20 | DOI | MR

[17] Eremeev A. V., Kovalenko Yu. V., “Optimal recombination in genetic algorithms for combinatorial optimization problems: Part II”, Yugoslav J. Oper. Res., 24:2 (2014), 165–186 | DOI | MR

[18] Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., “Optimization and approximation in deterministic sequencing and scheduling: A survey”, Discrete Optimization, v. II, Ann. Discrete Math., 5, North-Holland, Amsterdam, 1979, 287–326 | DOI | MR

[19] Holland J. H., Adaptation in natural and artificial systems, Univ. Michigan Press, Ann Arbor, 1975, 183 pp. | MR

[20] Nagano M. S., Ruiz R., Lorena L. A. N., “A constructive genetic algorithm for permutation flowshop scheduling”, Comput. Ind. Eng., 55:1 (2008), 195–207 | DOI | MR

[21] Pinedo M. L., Scheduling: theory, algorithms and systems, Prentice Hall, Upper Saddle River, NJ, 2002, 676 pp. | Zbl

[22] Radcliffe N. J., “The algebra of genetic algorithms”, Ann. Math. Artif. Intell., 10:4 (1994), 339–384 | DOI | MR | Zbl

[23] Tinós R., Whitley D., Ochoa G., “Generalized asymmetric partition crossover (GAPX) for the asymmetric TSP”, Proc. 2014 Annu. Conf. Genetic and Evolutionary Computation (Vancouver, Canada, July 12–16, 2014), ACM, New York, 2014, 501–508

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

[25] Wang L., Zhang L., “Determining optimal combination of genetic operators for flow shop scheduling”, Int. J. Adv. Manuf. Technol., 30:3–4 (2006), 302–308 | DOI

[26] Zhang L., Wang L., Zheng D.-Z., “An adaptive genetic algorithm with multiple operators for flowshop scheduling”, Int. J. Adv. Manuf. Technol., 27:5–6 (2006), 580–587 | DOI