EN|RU

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

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

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

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

Еремеев Антон Валентинович 1
Коваленко Юлия Викторовна 2

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

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

 © Институт математики им. С. Л. Соболева, 2015