Том 23, номер 2, 2016 г., Стр. 41-62

УДК 519.8
Коваленко Ю. В.
О сложности оптимальной рекомбинации для задач составления расписаний в многостадийной системе поточного типа

Аннотация:
Рассматривается вычислительная сложность оптимальной рекомбинации для различных вариантов задачи составления поточного расписания (flowshop) с критериями минимизации общего времени завершения работ и максимального временного смещения. Доказана NP-трудность этих задач, и предложен точный алгоритм их решения. Показано, что в случае перестановочной задачи flowshop трудоёмкость предложенного алгоритма полиномиальна для «почти всех» пар родительских решений при числе работ, стремящемся к бесконечности.
Ил. 4, библиогр. 26.

Ключевые слова: задача flowshop, перестановка, генетический алгоритм, оптимальная рекомбинация.

DOI: 10.17377/daio.2016.23.524

Коваленко Юлия Викторовна ¹
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: julia.kovalenko.ya@yandex.ru

Статья поступила 21 января 2016 г.
Исправленный вариант — 11 февраля 2016 г.

Литература

[1] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

[2] Еремеев А. В., Коваленко Ю. В. О задаче составления расписаний с группировкой машин по технологиям // Дискрет. анализ и исслед. операций. 2011. Т. 18, № 5. C. 54–79.

[3] Еремеев А. В., Коваленко Ю. В. О сложности оптимальной рекомбинации для одной задачи составления расписаний с переналадками // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 3. С. 13–26.

[4] Конвей Р. В., Максвелл В. Л., Миллер Л. В. Теория расписаний. М.: Наука, 1975. 360 с.

[5] Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2001. 960 с.

[6] Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечёткие системы. М.: Горячая линия-Телеком, 2006. 452 с.

[7] Сердюков А. И. О задаче коммивояжёра при наличии запретов // Управляемые системы. 1978. Вып. 17. С. 80–86.

[8] Танаев В. С., Сотсков Ю. Н., Струсевич В. А. Теория расписаний. Многостадийные системы. М.: Наука, 1989. 328 с.

[9] Balas E., Niehaus W. Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems // J. Heuristics. 1998. Vol. 4, No. 2. P. 107–122.

[10] Cheng B.-W., Chang C.-L. A study on flowshop scheduling problem combining Taguchi experimental design and genetic algorithm // Expert. Syst. Appl. 2007. Vol. 32, No. 2. P. 415–421.

[11] Chvátal V. Probabilistic methods in graph theory // Ann. Oper. Res. 1984. Vol. 1, No. 3. P. 171–182.

[12] Cook W., Seymour P. Tour merging via branch-decomposition // INFORMS J. Comput. 2003. Vol. 15, No. 3. P. 233–248.

[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). Heidelberg: Springer-Verl., 1998. P. 305–314. (Lect. Notes Comput. Sci.; Vol. 1498).

[14] Cotta C., Troya J. M. Genetic forma recombination in permutation flowshop problems // Evol. Comput. 1998. Vol. 6, No. 1. P. 25–44.

[15] Eremeev A. V. On complexity of optimal recombination for binary representations of solutions // Evol. Comput. 2008. Vol. 16, No. 1. P. 127–147.

[16] Eremeev A. V., Kovalenko Yu. V. Optimal recombination in genetic algorithms for combinatorial optimization problems: Part I // Yugoslav J. Oper. Res. 2014. Vol. 24, No. 1. P. 1–20.

[17] Eremeev A. V., Kovalenko Yu. V. Optimal recombination in genetic algorithms for combinatorial optimization problems: Part II // Yugoslav J. Oper. Res. 2014. Vol. 24, No. 2. P. 165–186.

[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 II. Amsterdam, North-Holland: 1979. P. 287–326. (Ann. Discrete Math., Vol. 5).

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

[20] Nagano M. S., Ruiz R., Lorena L. A. N. A constructive genetic algorithm for permutation flowshop scheduling // Comput. Ind. Eng. 2008. Vol. 55, No. 1. P. 195–207.

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

[22] Radcliffe N. J. The algebra of genetic algorithms // Ann. Math. Artif. Intell. 1994. Vol. 10, No. 4. P. 339–384.

[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). New York: ACM, 2014. P. 501–508.

[24] Yagiura M., Ibaraki T. The use of dynamic programming in genetic algorithms for permutation problems // Eur. J. Oper. Res. 1996. Vol. 92, No. 2. P. 387–401.

[25] Wang L., Zhang L. Determining optimal combination of genetic operators for flow shop scheduling // Int. J. Adv. Manuf. Technol. 2006. Vol. 30, No. 3–4. P. 302–308.

[26] Zhang L., Wang L., Zheng D.-Z. An adaptive genetic algorithm with multiple operators for flowshop scheduling // Int. J. Adv. Manuf. Technol. 2006. Vol. 27, No. 5–6. P. 580–587.