Генетический алгоритм для задачи календарного планирования с ограниченными ресурсами

Рассматривается задача календарного планирования с ограниченными ресурсами по критерию минимизации длины расписания. В задаче учитываются технологические ограничения предшествования работ, а также ресурсные ограничения. Предложен генетический алгоритм с двумя вариантами кроссовера, основанные на идее наиболее рационального использования ограниченных ресурсов. В кроссоверах применяется эвристика, учитывающая степень критичности ресурсов, которая выявляется из решения релаксированной задачи с ограничением на ресурсы складируемого типа. Численный эксперимент на примерах из библиотеки PCPLIB показал конкурентоспособность предложенного алгоритма. Для нескольких примеров из тестовой серии j120 были найдены лучшие решения, а для j60 (50000 и 500000 итераций) и для j120 (500000 итераций) получены лучшие средние отклонения решений от величины критического пути.