Том 10, серия 2, номер 2, 2003 г., Стр. 29-55
УДК 519.85
Ю. А. Кочетов, А. А. Столяр
Использование чередующихся окрестностей для приближенного решения задачи календарного планирования с ограниченными ресурсами
Аннотация:
Рассматривается известная NP-трудная задача календарного планирования с ограниченными ресурсами. Для ее решения предлагается новый алгоритм локального поиска, основанный на идее чередующихся окрестностей. Рассматриваются два типа дополняющих друг друга окрестностей. Одна из них строится по так называемым активным расписаниям, вторая окрестность – по$T$ -поздним расписаниям. Окрестности имеют линейный размер относительно числа рассматриваемых работ и строятся с привлечением задачи о многомерном рюкзаке. Разработанный алгоритм тестировался на примерах из электронной библиотеки PSPLib. Для многих примеров алгоритм позволяет находить наилучшие уже известные решения, а для ряда наиболее трудных примеров – новые лучшие значения целевой функции.
Кочетов Ю. А. 1
Столяр А. А. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 17 сентября 2003 г.
Исправленный вариант —10 ноября 2003 г.
