К решению задачи построения расписания выполнения проекта

Рассматривается задача построения расписания проекта с учетом ограничений на ресурсы (RCPSP) и ее частные случаи. Проведен сравнительный анализ известных нижних оценок целевой функции – минимизации общего времени выполнения проекта. Выдвинута гипотеза, что для задачи RCPSP без прерываний в обслуживании требований оптимальное значение целевой функции не более чем в два раза больше оптимального значения целевой функции соответствующей задачи с прерываниями. Представлены доказательства гипотезы для случаев задачи с параллельными машинами и без отношений предшествования.