Далее цитата — В.Н. Бурков, Д.А. Новиков. Элементы теории графов.
Задача определения продолжительности проекта (управление временем). Продолжительность проекта определяется путем максимальной длины, называемым критическим путем. Критический путь в сети на рисунке выделен двойными дугами.
Операции, принадлежащие критическому пути, называются критическими. Остальные (некритические) операции имеют резерв времени, характеризуемый максимальной задержкой операции, при которой продолжительность проекта не изменяется. Критические операции имеют нулевой резерв.
Задачи распределения ресурса на сетях удобно рассматривать, изображая операции вершинами сети, а зависимости – дугами (представления «операции-дуги, события-вершины» и «зависимости-дуги, операции-вершины» эквивалентны [10]). Пунктиром могут быть отражены ресурсные зависимости – когда для выполнения одних и тех же операций должны быть использованы одни и те же ресурсы. Примером могут являться сети, изображенные на рисунках 6 и 7. Полным резервом операции (i; j) называется величина = — , где — поздний срок начала (окончания) операции, а — ранний срок начала (окончания) операции.
Для определения оптимального распределения ресурса необходимо найти критические пути для каждого из вариантов распределения ресурса и сравнить длины этих путей (в сети, приведенной на рисунке 7, существует общий для операций «0-1» и «0-2» ресурс; потенциалы вершин, соответствующие различным способам использования этого ресурса – сначала выполняется операция «0-1», затем «0-2» и наоборот, приведены на рисунке 7 соответственно в квадратных скобках и без скобок). Универсальных эффективных точных методов решения задач распределения ресурсов на сетях не существует, но с помощью механизма суперприведения такие задачи можно решать.
Обширный класс задач календарно-сетевого планирования и управления (КСПУ) составляют задачи агрегирования – представления комплекса операций (проекта) в виде одной операции и исследования свойств таких представлений, для которых оптимизация в рамках агрегированного описания дает решение, оптимальное для исходного (детального) описания.
Конец цитаты — В.Н. Бурков, Д.А. Новиков. Элементы теории графов.
Все рассмотренные задачи формализуются в нотацию позиционной алгебры логики – см. статью М.И.Тельпиза «NP-полнота, суперприведение и проблема 4 красок» — http://www.tarusa.ru/~mit/RUS/NP_4col.php