Том 19, номер 3, 2012 г., Стр. 13-26

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

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

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

Еремеев Антон Валентинович ¹
Коваленко Юлия Викторовна ²
1. Омский филиал Института математики им. С. Л. Соболева СО РАН,
ул. Певцова, 13, 644099 Омск, Россия
2. Омский гос. университет им. Ф. М. Достоевского,
пр. Мира, 55а, 644077 Омск, Россия
е-mail: eremeev@ofim.oscsbras.ru, juliakoval86@mail.ru

Статья поступила 19 июля 2011 г.
Исправленный вариант — 17 ноября 2011 г.

Литература

[1] Берж К. Теория графов и её применения. — М.: Изд-во иностр. лит-ры, 1962. — 319 с.

[2] Борисовский П. А. Генетический алгоритм для одной задачи составления производственного расписания с переналадками // Тр. XIV Байк. междунар. шк.-семинара «Методы оптимизации и их приложения». Т. 4. — Иркутск: ИСЭМ СО РАН, 2008. — С. 166–173.

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

[4] Еремеев А. В. О сложности оптимальной рекомбинации для задачи коммивояжёра // Дискрет. анализ и исслед. операций. — 2011. — Т. 18, № 1. — С. 27–40.

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

[6] Карп Р. М. Сводимость комбинаторных проблем // Кибернет. сб. — М.: Мир, 1975. — Вып. 12. — С. 16–38.

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

[8] Рейнгольд Э., НивергельтЮ., Део Н. Комбинаторные алгоритмы, теория и практика. — М.: Мир, 1980. — 476 с.

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

[10] Танаев В. С., Ковалев М. Я., Шафранский Я. М. Теория расписаний. Групповые технологии. — Минск: Ин-т техн. кибернетики НАН Беларуси, 1998. — 290 с.

[11] Cook W., Seymour P. Tour merging via branch-decomposition // IN?FORMS J. Comput. — 2003. — Vol. 15, N 2. — P. 233–248.

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

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

[14] Eremeev A. V. On complexity of optimal recombination for binary representations of solutions // Evolutionary Comput. — 2008. — Vol. 16, N 1. — P. 127–147.

[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. — 1979. — Vol. 5. — P. 287–326.

[16] Hazir Ö., Günalay Y., Erel E. Customer order scheduling problem: a comparative metaheuristics study // Int. J. Adv. Manuf. Technology. — 2008. — Vol. 37. — P. 589–598.

[17] Held M., Karp R. M. A dynamic programming approach to sequencing problems // SIAM J. Appl. Math. — 1962. — Vol. 10. — P. 196–210.

[18] Reeves C. R. Genetic algorithms for the operations researcher // INFORMS J. Comput. — 1997. — Vol. 9, N 3. — P. 231–250.

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