Задача календарного планирования с ограниченными ресурсами (RCPSP)

Математическая модель RCPSP формулируется в виде задачи целочисленного линейного программирования. Задано множество работ (операций), каждая из которых имеет фиксированную длительность. Технологические зависимости представлены в виде ориентированного ациклического графа (работа Б не может начаться до завершения работы А). Но главным дополнением является множество возобновляемых ресурсов (например, 5 кранов и 20 инженеров). Каждая работа требует для своего выполнения определенное количество единиц каждого ресурса в каждый момент времени. Целевая функция заключается в минимизации общего времени завершения проекта (Makespan) при жестком условии: ни в один момент времени суммарное потребление любого ресурса всеми активно выполняющимися работами не должно превышать его доступный лимит.

Вычислительная сложность RCPSP классифицируется как сильно NP-трудная. Попытка решить ее точными методами (с помощью классических решателей Branch-and-Bound на основе непрерывной релаксации) часто терпит крах даже для проектов, состоящих всего из 60-100 работ. Причина заключается в слабости линейной релаксации (Duality Gap): когда переменные времени старта работ принимают дробные значения, алгоритм ветвей и границ не может эффективно отсекать неоптимальные ветви, и дерево перебора разрастается экспоненциально. Для преодоления этого барьера исследователи операций применяют неявное перечисление и генерацию специализированных отсечений, основанных на минимальных запрещенных множествах (Minimal Frobidden Sets) — группах независимых работ, которые физически не могут выполняться вместе из-за нехватки ресурсов.

Для реальных индустриальных графиков, насчитывающих тысячи задач, применяются мощные эвристические алгоритмы на основе правил приоритета (Priority Rule-Based Heuristics). Алгоритм генерации расписания (Schedule Generation Scheme, SGS) шаг за шагом двигается по оси времени. На каждом шаге он составляет список всех работ, которые технологически готовы к выполнению и обеспечены свободными ресурсами. Из этого списка жадно выбирается работа с наивысшим приоритетом. Приоритеты расставляются по алгебраическим правилам: LST (самое позднее допустимое время старта), SPT (кратчайшая продолжительность работы) или MIS (максимальная потребность в дефицитном ресурсе). Серийная схема генерации (Serial SGS) и параллельная схема (Parallel SGS) обеспечивают молниеносное получение вполне приемлемых графиков для гигантских строительных проектов.

Развитие RCPSP привело к созданию множества индустриальных модификаций. Модель с многорежимными работами (Multi-Mode RCPSP) позволяет одну и ту же задачу выполнять разными способами: либо долго и дешево с помощью двух рабочих, либо быстро, но с привлечением дорогостоящей бригады из пяти человек и экскаватора. Это превращает задачу календарного планирования в одновременную задачу бюджетирования (Time-Cost Trade-off). Применение метаэвристик (генетических алгоритмов и имитации отжига) для поиска оптимальных комбинаций режимов и времени старта работ стало основой современного программного обеспечения (Oracle Primavera, Microsoft Project), позволяющего корпорациям избегать ресурсных коллапсов и штрафов за срыв контрактов.