номер события, из которого работа выходит, а j – номер события, в которое она входит. Работа не может начаться раньше, чем свершится событие, из которого она выходит. Каждая работа имеет предельную продолжительность t(i,j). Например, запись t(2,5)=4 означает, что работа (2,5) имеет продолжительность 4 единицы. К работам относятся также такие процессы, которые не требуют ни ресурсов, ни времени выполнения. Они заключаются в установлении логической взаимосвязи работ и показывают, что одна из них непосредственно зависит от другой; такие работы называются фиктивными и в графике изображаются пунктирными стрелками.
Событиями называются результаты выполнения одной или нескольких работ. Они не имеют протяжённости во времени. Они не имеют протяжённости во времени. Событие свершается в тот момент, когда оканчивается последняя из работ, входящая в него. События обозначаются одним числом и при графическом представлении СМ изображаются кружком (или иной геометрической фигурой), внутри которого проставляется его порядковый номер (i=1,2,…,N). В СМ имеется начальное событие (с номером 1), из которого работы только выходят, и конечное событие (с номером N), в которое работы только входят.
Путь – это цепочка следующих друг за другом работ, соединяющих начальную и конечную вершины, например, в приведённой выше модели путями являются L1=(1,2,3,7,10,11), L2=(1,2,4,6,11) и др. Продолжительность пути определяется суммой продолжительностей составляющих его работ. Путь, имеющий максимальную длину, называют критическим и обозначают Lкр, а его продолжительность – tкр. Работы, принадлежащие критическому пути, называются критическими. Их несвоевременное выполнение ведёт к срыву всего комплекса работ.
СМ имеет ряд характеристик, которые позволяют определить степень направленности выполнения отдельных работ, а также всего их комплекса и принять решение о перераспределении ресурсов. Однако перед расчётом СМ следует
26
убедиться, что она удовлетворяет следующим основным требованиям [1]:
1.События правильно пронумерованы, т.е. для каждой работы (i,j) i<j. При невыполнении этого требования необходимо использовать алгоритм перенумерации событий, который заключается в следующем:
-нумерация событий начинается с исходного события, которому присваивается №1;
-из исходного события вычёркиваются все исходящие из него работы (стрелки), и на оставшейся сети находят событие, в которое не входит ни одна работа, ему и присваивается №2;
-затем вычёркивают работы, выходящие из события №2, и вновь находят событие, в которое не входит ни одна работа, и ему присваивают №3, так продолжается до завершающего события, номер которого должен быть равен количеству событий в сетевом графике.
-если при очередном вычёркивании работ одновременно несколько событий не имеют, входящих в них работ, то их нумеруют очередными номерами в произвольном порядке.
2.Отсутствуют тупиковые события (кроме завершающего его), т.е. такие, за которыми не следует хотя бы одна работа.
3.Отсутствуют события (за исключением исхода его), которым не предшествует хотя бы одна работа.
4.Отсутствуют циклы, т.е. замкнутые пути, соединяющие событие с ним же самим.
Для событий рассчитывают три характеристики: ранний и поздний срок совершения события, а также его резерв.
Ранний срок свершения события определяется величиной наиболее длительного отрезка пути от исходного до рассматриваемого события, причём tP(1)= 0, и tP(N)= tKP(L):
|
( j) max tP (i) t(i, j) ; j |
|
. |
(6.7) |
tP |
2, N |
|||
|
i |
|
||
27
Поздний срок свершения события характеризует самый поздний допустимый срок, к которому должно свершится событие, не вызывая при этом срыва срока конечного события:
t (i) min t ( j) t(i, j) ;i |
|
|
|
2, N 1. |
(6.8) |
||
j |
|
||
Этот показатель определяется «обратным ходом», начиная с завершающего события, с учётом соотношения t (N)=tP(N).
Все события, за исключением событий, принадлежащих критическому пути, имеют резервы R(i):
R(i) t (i) tP (i). |
(6.9) |
Резерв показывает, на какой предельно допустимый срок можно задержать наступление события, не вызывая при этом увеличения срока выполнения всего комплекса работ.
Для всех работ (i,j) на основе ранних и поздних сроков свершения всех событий, можно определить показатели:
ранний срок начала –
tPH (i, j) tP (i), |
(6.10) |
ранний срок окончания –
tPO (i, j) tP (i) t(i, j), |
(6.11) |
поздний срок окончания –
28
t O (i, j) t ( j), |
(6.12) |
поздний срок начала - |
|
t H (i, j) t ( j) t(i, j), |
(6.13) |
полный резерв времени - |
|
R (i, j) t ( j) tP (i) t(i, j), |
(6.14) |
независимый резерв времени - |
|
RH (i, j) max 0,tP ( j) t (i) t(i, j) |
(6.15) |
max 0, R (i, j) R(i) R( j) . |
(6.16) |
Полный резерв времени показывает, на сколько можно увеличить время выполнения конкретной работы при условии, что срок выполнения всего комплекса работ не изменится.
Независимый резерв времени соответствует случаю, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие начинаются в ранние сроки. Использование этого резерва не влияет на величину резервов времени других работ.
Путь характеризуется двумя показателями – продолжительностью и резервом. Продолжительность пути определяется суммой продолжительностей составляющих его работ. Резерв определяется как разность между длинами критического и рассматриваемого путей. Из этого определения следует, что работы, лежащие на критическом пути, и сам критический путь имеют нулевой резерв времени. Резерв времени
29
пути показывает, насколько может увеличиться продолжительность работ, составляющих данный путь, без изменения продолжительности общего срока выполнения всех работ.
Результаты расчёта основных показателей СМ, изображённой на рис. 6.1, представлены в табл. 6.1.
Таблица 6.1
K |
(i,j) |
t(i,j) |
tPH(i,j) |
tPO(i,j) |
t H(i,j) |
t O(I,j) |
R |
RH |
KH |
|
|
|
=tP(i) |
|
|
=t (j) |
|
|
|
|
|
|
|
|
|
|
|
||
P |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5=4 |
6=7- |
7 |
8 |
9 |
10 |
|
|
|
|
+3 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
(1,2) |
6 |
0 |
6 |
0 |
6 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
1 |
(2,3) |
5 |
6 |
11 |
12 |
17 |
6 |
0 |
0, |
|
|
|
|
|
|
|
|
|
67 |
|
|
|
|
|
|
|
|
|
|
1 |
(2,4) |
3 |
6 |
9 |
6 |
9 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
1 |
(2,5) |
4 |
6 |
10 |
11 |
15 |
5 |
5 |
0, |
|
|
|
|
|
|
|
|
|
44 |
|
|
|
|
|
|
|
|
|
|
1 |
(3,7) |
1 |
11 |
12 |
17 |
18 |
6 |
0 |
0, |
|
|
|
|
|
|
|
|
|
67 |
|
|
|
|
|
|
|
|
|
|
1 |
(4,5) |
6 |
9 |
15 |
9 |
15 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
1 |
(4,6) |
4 |
9 |
13 |
17 |
21 |
8 |
0 |
0, |
|
|
|
|
|
|
|
|
|
47 |
|
|
|
|
|
|
|
|
|
|
1 |
(4,9) |
7 |
9 |
16 |
14 |
21 |
5 |
0 |
0, |
|
|
|
|
|
|
|
|
|
67 |
|
|
|
|
|
|
|
|
|
|
2 |
(5,8) |
3 |
15 |
18 |
17 |
20 |
2 |
0 |
0, |
|
|
|
|
|
|
|
|
|
78 |
|
|
|
|
|
|
|
|
|
|
2 |
(5,10) |
9 |
15 |
24 |
15 |
24 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
1 |
(6,9) |
0 |
13 |
13 |
21 |
21 |
8 |
0 |
0, |
|
|
|
|
|
|
|
|
|
38 |
|
|
|
|
|
|
|
|
|
|
1 |
(6,11) |
5 |
13 |
18 |
28 |
33 |
1 |
7 |
0, |
|
|
|
|
|
|
|
5 |
|
38 |
|
|
|
|
|
|
|
|
|
|
30