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

Рассматривается задача календарного планирования с ограничениями на ресурсы и порядок выполнения работ. Эта задача NP-трудна в сильном смысле и является обобщением задач job-shop, flow-shop и др. Предложена ее геометрическая интерпретация, на основе которой разработан алгоритм построения оптимального расписания выполнения работ. Доказано, что если ширина графа редукции частичного порядка выполнения работ ограничена константой, то задача является псевдополиномиально разрешимой. Выделен полиномиально разрешимый случай задачи. Библиогр. 13.