Алгоритм расчета параметров детерминированной сетевой модели

Расчет параметров сетевого графа можно выполнить непосредственно по графику, таблично и на ЭВМ.

Расчет параметров событий непосредственно по графику состоит из следующих этапов:

1.Каждое событие на графе изображается кругом, разделенным на 4 сектора.

- раннее время наступления i- го события (левый сектор).

- позднее время наступления i- го события (правый сектор).

В нижнем секторе проставляют номер предыдущего события.

Рис.2.3. Пример сетевого графа

2. Нумеруют события, применяя метод вычеркивания дуг. Проставляют номер события в верхнем секторе.

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

4. В правый сектор записывают позднее время наступления события.

5. Выделяют критический путь, используя свойство работ, лежащих на критическом пути:

а) ;

б) критические работы связывают данное событие с предыдущим, номер которого указан в нижнем секторе.

Рассмотрим расчет параметров событий сетевой модели «Работы-события» на примере сетевого графа.

Требуется рассчитать параметры сетевого графа (рис.2.3) и по нему определить критический путь.

Рис.2.4. Расчет параметров событий

Исходному событию присваивают номер 0 или 1. Вычеркивают работы выходящие из нулевого события и нумеруют сверху вниз (можно снизу вверх) события 1 и 2. Затем вычеркивают работы выходящие из первого события и нумеруют событие 3. Вычеркивая из второго события, выходящие работы, получают 4 и 5 событие и т.д., двигаясь по порядку номеров, получают последнее завершающее событие с номером 10.

Получили цепочку событий , образующих критический путь длиной =27. Критический путь обозначен на рисунке (Рис.2.3) двойными стрелками.

Расчет параметров работ сетевой модели «Работы-события»

Работы в таблицу заносятся в лексикографическом порядке. В начале записывают работы с меньшим номером начала. Если две работы имеют общее начало, то раньше заносится та работа, у которой меньше номер конца.

1 столбец i - номер начала работы;

2 столбец j - номер конца работы;

3 столбец - продолжительность работы;

4 столбец - время раннего наступления работ, причем время раннего наступления работ, выходящих из исходного события, равно 0.

Как только известно, раннее начало работы, сразу же вычисляется ее раннее окончание: , .

5 столбец - время раннего окончания работы;

6 столбец - время позднего наступления работ;

7 столбец - время позднего окончания работ.

6 и 7 столбцы заполняются “ снизу - вверх ”.

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

, .

8 столбец - полный резерв работы. .

9 столбец – работы критического пути.

Работы с нулевыми резервами образуют критический путь.

10 столбец – свободный резерв.

11 столбец – потребное количество ресурсов для выполнения работы. Например, количество трудовых ресурсов на графе обычно указывают в скобках 2(5), т.е. два дня работают пять человек.

Расчет параметров работ сетевого графа, изображенного на рис.2.3, представлен в таблице 2.1.

Таблица 2.1

Расчет параметров работ

i	j	tij						Крит. путь
								0 -2
								2 - 4
								4 - 7
								7 - 8
								8 - 10

L_кр =27. Критический путь образует цепочка работ: 0 - 2 -4 - 7 - 8 - 10.

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

Пояснение резервов времени.

Например, полный резерв времени работы 1 – 3, - это максимальное время, на которое можно увеличить продолжительность данной работы или отодвинуть ее начало, не изменив при этом продолжительность критического пути. Свободный резерв времени этой же работы , что говорит о невозможности увеличить продолжительность этой работы, не влияя на сроки наступления ее начального и конечного событий.