Основные принципы построения сетевой модели

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

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

Рис. 6.1.1.

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

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

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

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

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

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

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

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

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

Основой успешного построения сетевой модели является хорошее знание проекта и технологии выполнения работ. При этом используется ряд определенных правил и приемов.

Принципы построения сетевых графиков.

1. Как правило, последовательность работ изображается слева направо.

2. Если работы А и В выполняются последовательно:

Рис.6.1.2.

3. Если для выполнения работ А и В необходим результат работы С:

Рис.6.1.3

4.

Рис. 6.1.4

5. Если работа С следует за двумя параллельно идущими работами А и В, а работа D только за работой В, то:

Рис. 6.1.5

6. Одноцелевые графики имеют одно начальное событие и одно конечное.

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

8. Не должно быть событий, которым на предшествует ни одна работа (кроме исходного).

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

Рис. 6.1.6

10. Два события не могут быть соединены более чем одной работой (петля). В этом случае рекомендуется ввести дополнительное событие и фиктивную работу.

Рис. 6.1.7

11. В сетевых моделях следует соблюдать определенную последовательность в нумерации событий от исходного к завершающему. События должны быть упорядочены по рангам, так как графики, у которых нумерация осуществлена по правилу i< j, очень удобны для анализа и проведения расчетов.

Для упорядочения вершин можно воспользоваться графическим способом (методом вычеркивания дуг).

1. Исходную вершину (в которую не входит ни одна дуга) отнесем к рангу 0 и присвоим ей номер 1.

2. Вычеркнем все дуги, выходящие из вершины 1. И отнесем события, оказавшиеся без входящих дуг, к первому рангу. Этим событиям присвоим в произвольном порядке номера 2, 3… k ₁.

3. Вычеркнув все дуги, выходящие из вершин предыдущего ранга, отнесем вершины, оказавшиеся без входящих дуг, к следующему рангу и последовательно пронумеруем их. Этот шаг повторяем до тех пор, пока все вершины не будут пронумерованы. При этом получается, что события одного и того же ранга между собой не соединены работами, а события старших рангов имеют больший номер. Порядок нумерации событий одного и того же ранга может быть произвольным.

В случае необходимости упорядочения сетей большой размерности удобно пользоваться аналитическим методом – алгоритмом Форда.

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

Рассмотрим пример.

Пример 6.1.1. Университет рассматривает предложение о строительстве нового корпуса. Работы, которые следует выполнить перед началом строительства, представлены в табл.

Таблица

Исходные данные примера 6.1.1

Требуется построить сетевой график проекта.

Решение.

Рис. Сетевой график примера 6.1.1.

Работа А₁ не имеет предшествующих, поэтому изображается дугой, выходящей из события 1. Масштаб при этом не соблюдается. Работе А₂ предшествует работа А₁, поэтому дуга А₂ изображается на сетевом графике вслед за дугой А₁. А₃ изображается аналогично А₂. Далее надо изобразить работы А₄ и А₅, выполняющиеся после работы А₃. Чтобы изобразить работы А₆ и А₇, приходится ввести фиктивную работу, так как работе А₆ предшествуют три работы А₂, А₄ и А₅, а работе А₇ только работы А₂ и А₅. И наконец, дуга А₈, моделирующая выполнение заключительной работы А₈. Правильность нумерации событий можно проверить, воспользовавшись вышеизложенным алгоритмом.