Стрелочный граф

Стрелочный граф (также известный как граф-стрелка, диаграмма предшествования, PERT-диаграмма или сетевой график) — это ориентированный граф, используемый для моделирования последовательности и взаимозависимости работ (операций, задач) в проекте. Каждая дуга (стрелка) такого графа представляет собой отдельную работу, а вершины (узлы) — события, обозначающие начало или окончание одной или нескольких работ. Стрелочные графы являются основным инструментом методов сетевого планирования и управления (СПУ), таких как метод критического пути (CPM) и метод оценки и пересмотра планов (PERT).

История

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

В СССР теория сетевого планирования и стрелочные графы активно развивались с 1960-х годов. Работы советских учёных, таких как С. И. Зуховицкий, И. А. Радчик, В. Н. Бурков, внесли значительный вклад в формализацию и применение этих методов в строительстве, промышленности и научных исследованиях. В 1970—1980-х годах стрелочные графы стали стандартным инструментом в проектных институтах и на крупных стройках.

Основные элементы

Стрелочный граф состоит из двух типов элементов:

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

Правила построения

При построении стрелочного графа соблюдаются следующие правила:

1. Уникальность событий: каждое событие должно иметь уникальный номер. Номера присваиваются по возрастанию, причём номер начального события работы всегда меньше номера конечного.
2. Отсутствие тупиков и циклов: в графе не должно быть событий (кроме завершающего), из которых не выходит ни одной работы, и событий (кроме исходного), в которые не входит ни одной работы. Запрещены замкнутые контуры (циклы), так как они означают бесконечное повторение работ.
3. Правило изображения параллельных работ: если две или более работы имеют одинаковые начальное и конечное события, их нельзя изображать параллельными дугами между одними и теми же вершинами. Для разрешения этой ситуации вводится дополнительное событие и фиктивная работа.
4. Правило предшествования: работа может начаться только после наступления её начального события, то есть после завершения всех работ, входящих в это событие.

Методы расчёта

Основная задача анализа стрелочного графа — определение временных параметров проекта. Для этого рассчитываются:

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

Расчёты выполняются в два этапа: прямой ход (от исходного события к завершающему) для определения ранних сроков и обратный ход (от завершающего к исходному) для определения поздних сроков. На основе этих вычислений выделяется критический путь — последовательность работ от исходного до завершающего события, имеющая нулевой полный резерв времени. Любая задержка на критическом пути приводит к задержке всего проекта.

Применение

Стрелочные графы широко применяются в различных областях:

• Строительство: планирование возведения зданий, мостов, дорог. Например, строительство БАМа в СССР активно использовало сетевые графики.
• Производство: управление технологическими процессами, ремонт оборудования, запуск новых продуктов.
• Научные исследования и разработки: планирование сложных проектов, таких как создание космических аппаратов (проект «Поларис»).
• Логистика: оптимизация цепочек поставок и транспортных маршрутов.
• Управление проектами (Project Management): в современных методологиях, таких как PMBOK, стрелочные графы являются одним из стандартных инструментов для разработки расписания.

Достоинства и недостатки

Достоинства

• Наглядное отображение логических связей между работами.
• Возможность точного расчёта критического пути и резервов времени.
• Удобство для анализа «что, если» (имитационное моделирование).
• Хорошая формализация для автоматизированного расчёта.

Недостатки

• Сложность построения и восприятия для крупных проектов (сотни и тысячи работ).
• Необходимость введения фиктивных работ, что усложняет граф.
• Трудоёмкость ручного расчёта для больших проектов (до появления компьютеров).
• Меньшая наглядность по сравнению с диаграммами Ганта для отображения календарного плана.

Сравнение с другими методами

Стрелочный граф (Activity-on-Arrow, AoA) часто противопоставляется графу «вершины-работы» (Activity-on-Node, AoN), где работы изображаются вершинами, а связи — дугами. В современном управлении проектами графы «вершины-работы» (например, диаграммы предшествования в Microsoft Project) используются чаще, так как они проще для построения и не требуют фиктивных работ. Однако стрелочные графы остаются важным инструментом для анализа временных параметров и критического пути, особенно в теоретических и учебных целях.

Интересные факты

• Метод PERT, использующий стрелочные графы, позволил сократить сроки создания ракет «Поларис» на два года (с 7 до 5 лет).
• В СССР в 1960-х годах была разработана система «СПУ-1» (Сетевое Планирование и Управление), которая использовала стрелочные графы для управления строительством крупных промышленных объектов.
• Стрелочные графы являются частным случаем сетей Петри, используемых для моделирования параллельных и асинхронных процессов.

Источники

• Зуховицкий С. И., Радчик И. А. Математические методы сетевого планирования. — М.: Наука, 1965.
• Бурков В. Н., Новиков Д. А. Теория активных систем: состояние и перспективы. — М.: СИНТЕГ, 1999.
• Абдикеев Н. М., Данько Т. П., Ильдеменов С. В., Киселёв А. Д. Реинжиниринг бизнес-процессов. — М.: Эксмо, 2005.
• Project Management Institute. A Guide to the Project Management Body of Knowledge (PMBOK Guide). — 6th ed. — PMI, 2017.
• Модер Дж., Филлипс С. Метод сетевого планирования в организации работ. — М.: Мир, 1966.