Граф вершины-работы

Граф вершины-работы (англ. activity-on-vertex graph, AOV-сеть) — это ориентированный граф, используемый в теории расписаний и управлении проектами, в котором вершины соответствуют отдельным работам (операциям, задачам, этапам), а дуги — отношениям предшествования (зависимостям) между ними. В такой модели дуга, направленная от вершины A к вершине B, означает, что работа A должна быть полностью завершена до начала работы B. Граф вершины-работы является одним из основных способов представления сетевых графиков проектов, наряду с графом вершины-события (англ. activity-on-arrow graph).

История

Методология сетевого планирования и управления (СПУ) начала развиваться в середине XX века. В 1956—1957 годах в США компаниями DuPont и Remington Rand был разработан метод критического пути (CPM, Critical Path Method), первоначально ориентированный на графы вершины-события. В 1958 году в рамках программы «Поларис» ВМС США был создан метод PERT (Program Evaluation and Review Technique), также использующий вершины-события.

Однако в 1960-х годах, с развитием вычислительной техники и усложнением проектов, возникла потребность в более гибкой модели, где каждая работа представляется отдельной вершиной. Это позволило упростить алгоритмы расчёта временных параметров и сделать граф более наглядным для исполнителей. Граф вершины-работы получил широкое распространение в системах автоматизированного управления проектами (например, в Microsoft Project, Oracle Primavera) и в теории графов для задач топологической сортировки.

Определение и формальные свойства

Формально граф вершины-работы определяется как пара \( G = (V, E) \), где:

• \( V \) — конечное множество вершин, каждая из которых представляет собой одну работу (операцию, задачу). Каждая работа \( i \) характеризуется длительностью \( d_i \) (временем выполнения) и, возможно, другими параметрами (стоимость, ресурсы).
• \( E \subseteq V \times V \) — множество направленных дуг (рёбер). Дуга \( (i, j) \) означает, что работа \( i \) является непосредственным предшественником работы \( j \). Работа \( j \) не может начаться, пока работа \( i \) не завершена.

Граф вершины-работы должен быть ациклическим (не содержать ориентированных циклов), так как цикл означал бы логически невозможное условие — работа не может зависеть сама от себя через последовательность других работ. Ацикличность является необходимым условием для корректного расчёта временных параметров.

Отличие от графа вершины-события

В графе вершины-события (AOA-сеть) работы изображаются дугами, а вершины — событиями (моментами начала или окончания работ). В графе вершины-работы (AOV-сеть) работы — вершины. Основные различия:

Классификация работ

В графе вершины-работы все вершины делятся на три типа в зависимости от их положения в сети:

• Исходные работы (вершины без входящих дуг) — работы, которые не имеют предшественников и могут начинаться немедленно после старта проекта.
• Завершающие работы (вершины без исходящих дуг) — работы, после завершения которых проект считается оконченным.
• Промежуточные работы — все остальные, имеющие как предшественников, так и последователей.

В некоторых моделях вводятся фиктивные начальная и конечная вершины с нулевой длительностью, чтобы унифицировать расчёты.

Применение

Управление проектами

Граф вершины-работы лежит в основе метода критического пути (CPM) и метода PERT. На его основе вычисляются:

• Раннее время начала (ES) — самый ранний момент, когда работа может быть начата.
• Раннее время окончания (EF) — ES + длительность работы.
• Позднее время начала (LS) — самый поздний момент, когда работа может быть начата без задержки проекта.
• Позднее время окончания (LF) — LS + длительность работы.
• Полный резерв времени (TF) — LF - EF (или LS - ES). Показывает, на сколько можно задержать работу, не увеличивая общую длительность проекта.
• Критический путь — последовательность работ с нулевым полным резервом времени. Любая задержка на критическом пути приводит к задержке всего проекта.

Топологическая сортировка

Граф вершины-работы является классическим объектом для алгоритма топологической сортировки — упорядочения вершин в линейный порядок, при котором для каждой дуги \( (i, j) \) вершина \( i \) предшествует вершине \( j \). Этот алгоритм используется в компиляторах (для разрешения зависимостей между модулями), в системах сборки (Make, Gradle) и в планировщиках задач.

Анализ зависимостей

В инженерии знаний и управлении бизнес-процессами граф вершины-работы применяется для моделирования последовательности операций, выявления узких мест и оптимизации ресурсов. Например, в строительстве с его помощью строят календарные графики, в разработке ПО — диаграммы Ганта (которые являются временным отображением AOV-сети).

Пример

Рассмотрим простой проект «Строительство дачного дома»:

1. Заливка фундамента (длительность 5 дней).
2. Возведение стен (10 дней).
3. Монтаж крыши (7 дней).
4. Проводка электричества (3 дня).
5. Внутренняя отделка (6 дней).

Зависимости:

• Стены можно начинать только после фундамента.
• Крышу — только после стен.
• Электричество можно начинать после стен, но до отделки.
• Отделку — после крыши и электричества.

Граф вершины-работы будет содержать 5 вершин и дуги: (1→2), (2→3), (2→4), (3→5), (4→5). Критический путь: 1→2→3→5 (5+10+7+6 = 28 дней). Работа 4 (электричество) имеет резерв времени: её можно задержать на 2 дня, не сдвигая проект.

Ограничения и критика

• Сложность для больших проектов. При тысячах работ граф становится трудночитаемым, и его анализ требует автоматизации.
• Необходимость ацикличности. Реальные проекты могут содержать обратные связи (например, итерации в разработке), которые не моделируются в классическом AOV-графе. Для таких случаев применяют расширения — графы с циклами, но с дополнительными условиями.
• Игнорирование ресурсов. Базовая модель не учитывает ограничения на количество исполнителей или оборудования. Для этого используются ресурсные календари и методы выравнивания ресурсов.
• Статичность. Граф вершины-работы предполагает, что зависимости и длительности известны заранее и не меняются. В реальности проекты подвержены изменениям, что требует пересчёта сети.

См. также

• Метод критического пути
• PERT
• Диаграмма Ганта
• Сетевое планирование
• Топологическая сортировка

Источники

• Керниган Б., Ричи Д. «Язык программирования C». — Глава по алгоритмам (топологическая сортировка).
• Управление проектами: учебник / под ред. И. И. Мазура, В. Д. Шапиро. — М.: Омега-Л, 2010.
• Ahuja, R. K., Magnanti, T. L., Orlin, J. B. «Network Flows: Theory, Algorithms, and Applications». — Prentice Hall, 1993.
• ГОСТ Р 54869—2011 «Проектный менеджмент. Требования к управлению проектом».