Применение методов теории графов в сетевом планировании и управлении

Сетевые методы – это совокупность математических методов, в основе которых лежит графическое представление комплекса работ в виде сетевого графика (сети).

Таким образом, основным элементом систем СПУ является сетевая модель, которая моделирует процесс выполнения комплекса работ для достижения определенной цели (в дальнейшем комплекс работ для достижения определенной цели будем называть проектом). Графическое изображение сетевой модели называется сетевым графиком.

Сетевой график с математической точки зрения представляет собой ориентированный граф без петель и контуров. Обозначим его G = (), где Е – непустое конечное множество вершин, а  – конечное множество ориентированных дуг, соединяющих некоторые пары вершин.

Дугам на сетевом графике соответствуют работы, а вершинам – события.

(в мировой практике встречается и другое представление: работы – вершины; события – дуги).

Работа – это любые действия, трудовые процессы, сопровождающиеся затратами времени или (и) ресурсов и приводящие к определенным результатам.

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

Событие – обозначает факт окончания работ, в него входящих или начала работ из него выходящих, оно не имеет продолжительности и не потребляет ресурсов. На графике изображается кружочками, квадратами или прямоугольниками. На любом сетевом графике можно выделить исходное, промежуточное и завершающее события.

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

Событие выражает логическую связь между работами, заключающуюся в том, что работы, входящие в данное событие, непосредственно предшествуют работам, выходящим из него; ни одна, выходящая из данного события работа, не может начинаться до окончания всех работ, входящих в это событие.

 Любая работа сетевой модели соединяет два события: начальное событие работы и конечное событие работы. Для однозначного обозначения работ используют идентификаторы (i, j), где i – номер начального события работы, j – номер конечного события работы. Обычно на сетевых графиках события упорядочены, то есть i < j.