Использование чередующихся окрестностей для приближенного решения задачи календарного планирования с ограниченными ресурсами

Рассматривается известная NP-трудная задача календарного планирования с ограниченными ресурсами. Для ее решения предлагается новый алгоритм локального поиска, основанный на идее чередующихся окрестностей. Рассматриваются два типа дополняющих друг друга окрестностей. Одна из них строится по так называемым активным расписаниям, вторая окрестность – по $T$-поздним расписаниям. Окрестности имеют линейный размер относительно числа рассматриваемых работ и строятся с привлечением задачи о многомерном рюкзаке. Разработанный алгоритм тестировался на примерах из электронной библиотеки PSPLib. Для многих примеров алгоритм позволяет находить наилучшие уже известные решения, а для ряда наиболее трудных примеров – новые лучшие значения целевой функции.