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

Задача календарного планирования с ограниченными ресурсами  — достаточно общая задача теории расписаний, которая включает в себя ограничения предшествования работ и ресурсные ограничения. Все ресурсы возобновимы, прерывания работ запрещены. Эта задача NP-трудна в сильном смысле. Мы предлагаем новый детерминированный жадный алгоритм. Он основан на эвристике, использующей информацию, полученную в результате решения релаксированной задачи с кумулятивными ресурсами. Алгоритм протестирован на стандартных наборах данных j60, j90 и j120, предоставляемых библиотекой PSPLIB; показана его эффективность. Табл. 2, библиогр. 17.