Том 7, серия 2, номер 1, 2000 г., Стр. 75-82

УДК 519.8519.8
В. В. Сервах
Эффективно-разрешимый случай задачи календарного планирования с возобновимыми ресурсами

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

Сервах В. В. ¹
1. Омский филиал Института математикиим. С. Л. Соболева СО РАН,
ул. Певцова, 13, 644099 Омск, Россия
е-mail: svv@iitam.omsk.net.ru

Статья поступила 15 апреля 1999 г.
Исправленный вариант — 23 февраля 2000 г.