1.2 Правила построения сетевых графиков. Характеристики элементов сетевой модели

При построении сетевых графиков необходимо соблюдать следующие правила:

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

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

2) в сети не должно быть событий, в которые не входит ни одной работы, если только эти события не являются для данной сети исходными.

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

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

4) в сети не должно быть работ, имеющих одинаковые шифры, то есть работ с общими начальным и конечным событиями.

Для любого события i сетевая модель позволяет рассчитать наиболее ранний из возможных сроков его свершения tp(i) и наиболее поздний из допустимых сроков его свершения tп(i) (или для кратности: ранний и поздний сроки свершения события i).

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

Обозначив максимальный предшествующий событию i путь через L(I-i)max, получим

tp(i)=t[L(I-i)max]. (1)

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

Обозначим максимальный следующий за событием i путь через L(i-C)max, получим

tп(i)=tкр-t[L(i-C)max]. (2)

Зная tp(i) и tп(i) для всех событий сети, можно для любой работы (i, j) определить:

самый ранний из возможных сроков начала работы (i,j), или, кратко, ранний срок начала tр.н(i,j);

самый поздний из допустимых сроков начала работы, или поздний срок начала tп.н(i,j);

самый ранний из возможных сроков окончания работы, или ранний срок окончания tр.о(i,j);

самый поздний из допустимых сроков окончания работы, или поздний срок окончания tп.о(i,j).

Ранние сроки начала работ определяются ранними сроками свершения их начальных событий, а поздние сроки окончания работ – поздними сроками свершения их конечных событий. Поэтому, зная продолжительность работы t(i,j), указанные выше параметры определить по следующим формулам:

tр.н(i,j) = tp(i), (3)

tп.н(i,j) = tп(j) – t(i,j), (4)

tp.o(i,j) = tp(i) + t(i,j), (5)

tп.о(i,j) = tп(j). (6)

Для всех работ критического пути

tр.н(i,j) = tп.н(i,j) и tр.о(i,j) = tп.о(i,j), (7)

так как начальное и конечное события этих работ находятся на критическом пути, а следовательно,

tp(i) = tп(i) = tп(j) – t(i,j) и tп(j) = tp(j) = tp(i) + t(i,j). (8)

Разница между продолжительностью критического пути и любого другого пути сети t(L) называется полным резервом времени пути и обозначается через P(L):

P(L) = tкр – t(L). (9)

Величина P(L) показывает, насколько в сумме может быть увеличена продолжительность всех работ, принадлежащих пути L, чтобы при этом не изменилась продолжительность критического пути tкр.

Резерв времени события i обозначается через P(i) и определяется как разница между поздним и ранним сроками свершения данного события, то есть:

P(i) = tп(i) – tp(i); (10)

легко показать, что

P(i) = P[L(i)max], (11)

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

Резерв времени показывает, на какой предельно допустимый период времени можно задержать свершение этого события, не вызывая при этом увеличения tкр.

В системах СПУ используются четыре вида резервов времени работ: полный, свободный, и два вида частных резервов времени.

Полным резервом времени работ (i,j) называется резерв времени, равный величине резерва времени максимального из путей, проходящих через данную работу. Обозначается через Pп(i,j).

Для всех работ критического пути Рп(i,j) = 0.

Величина полного резерва времени может быть определена по следующей формуле:

Рп(i.j) = tп(j) – tp(i) – t(i,j). (12)

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

Следует различать два вида частных резервов:

1) частный резерв первого вида P’п(i,j) образуется у работ, непосредственно следующих за событием, в котором пересекаются пути различной продолжительности;

2) частный резерв второго вида P”п(i,j) образуется у работ, непосредственно предшествующих событию, в котором пересекаются пути различной продолжительности.

P’п(i,j) = Рп(i,j) – P(i), (13)

P”п(i,j) = Pп(i,j) – P(j). (14)

Свободным резервом времени работы (i,j) называется та часть ее полного резерва, которая сохраняется у нее при условии, что начальное событие данной работы свершится в самый поздний срок tп(i), а конечное – в самый ранний tp(j):

Pc(i.j) = tp(j) – tп(i) – t(i,j). (15)

Величина свободного резерва времени Pc(i,j) показывает, на какой период времени можно увеличить продолжительность данной работы (i,j), чтобы при этом сохранилась возможность свершения ее конечного события в самый поздний срок.

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

kн(i.j) = 1 – Рп(i,j) / t”кр(i,j)max. (16)

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

Величина коэффициента напряженности у разных работ в сети лежит в пределах 0 ≤ kн(i,j) ≤ 1, причем у работ критического пути kн(i,j) = 1.

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