В
табл. 6.1 приведены основные
временные параметры сетевых графиков.
Таблица
6.1
|
Элемент cети, |
Наименование параметра |
Условное обозначение параметра |
|
Событие i |
Ранний |
tp(i) |
|
Поздний |
tn(i) |
|
|
Резерв |
R(i) |
|
|
Работа |
Продолжительность |
t(i,j) |
|
Ранний |
tрн(i |
|
|
Ранний |
tро(i, |
|
|
Поздний |
tпн(i, |
|
|
Поздний |
tпо(i, |
|
|
Полный |
RП(i, |
|
|
Частный |
R1(i, |
|
|
Частный |
Rс(i, |
|
|
Независимый |
RН(i, |
|
|
Путь L |
Продолжительность |
t(L) |
|
Продолжительность |
tкр |
|
|
Резерв |
R(L) |
Рассмотрим
содержание и расчет указанных параметров.
Начнем
с параметров
событий. Как
уже отмечалось, событие не может наступить
прежде, чем свершатся все предшествующие
работы. Поэтому ранний
(или ожидаемый) срок tp(i)
свершения i-го события определяется
продолжительностью максимального пути,
предшествующего этому событию:
,
(6.1)
где
LПi
—
любой путь, предшествующий i-му
событию, т.е. путь от исходного до
i-го
события сети.
Если
событие
i
имеет несколько предшествующих путей,
а следовательно, несколько предшествующих
событий j,
то ранний срок свершения события i
удобно находить по формуле:
. (6.2)
Задержка
свершения события i
по отношению к своему раннему сроку не
отразится на сроке свершения завершающего
события (а значит, и на сроке выполнения
комплекса работ) до тех пор, пока сумма
срока свершения этого события и
продолжительности (длины) максимального
из последующих за ним путей не превысит
длины критического пути.
Поэтому
поздний
(или предельный) срок tП(i)
свершения
i-го
события равен:
, (6.3)
где
Lci
— любой
путь, следующий за i-м
событием,
т.е. путь от
i-го
до завершающего события сети.
Если
событие i
имеет
несколько последующих путей, а,
следовательно, несколько последующих
событий j,
то
поздний срок свершения события i
удобно находить по формуле:
. (6.4)
Резерв
времени R(i)
i-го
события определяется как разность между
поздним и ранним сроками его свершения:
R(i)
=tП(i)
—tp(i). (6.5)
Резерв
времени события показывает, на какой
допустимый период времени можно задержать
наступление этого события, не вызывая
при этом увеличения срока выполнения
комплекса работ.
Критические
события резервов времени не имеют, так
как любая задержка в свершении события,
лежащего на критическом пути, вызовет
такую же задержку в свершении завершающего
события.
Из
этого следует, что для того чтобы
определить длину и топологию критического
пути, вовсе не обязательно перебирать
все полные пути сетевого графика и
определять их длины. Определив
ранний срок наступления завершающего
события сети, мы тем самым определяем
длину критического пути, а выявив события
с нулевыми резервами времени, определяем
его топологию.
Задача
1. Определить
временные параметры событий и критический
путь для сетевого графика, изображенного
на рис. 6.4.
Решение.
Найденные параметры сведем в табл. 6.2.
При
определении ранних сроков свершения
событий tp(i)
двигаемся
по сетевому графику слева направо и
используем формулы (6.1) и (6.2).
Для
i=0
(нулевого события) очевидно, что tР(0)
= 0.
Для i=1
tp(1)=tp(0)+t(0,1)
=
0+8 = 8 (суток), так как для события 1
существует только один предшествующий
путь Ln1:
0 →1. Для
i=
2 tp(2)
=
tp(1)+t(1,2)
= 8+9
= 17 (суток), так как для события 2
существует
только один предшествующий путь Ln2:
0 →1→2. Для
i
=
3 tp(3)
=
max{tp(0)+t(0,3);
tp(1)+t(1,3)}
= mах{0+13;
8+4} = mах{13;
12} = 13 (суток), так как для события 3
существуют
два предшествующих пути Ln3
0 →1→3 и
0→3
и
два предшествующих события –
0
и
1.
Таблица
6.2
|
Номер события |
Сроки свершения |
Резерв времени |
|
|
ранний tp(i) |
поздний tп(i) |
||
|
0 |
0 |
0 |
0 |
|
1 |
8 |
9 |
1 |
|
2 |
17 |
40 |
23 |
|
3 |
13 |
13 |
0 |
|
4 |
23 |
26 |
3 |
|
5 |
20 |
20 |
0 |
|
6 |
29 |
29 |
0 |
|
7 |
33 |
43 |
10 |
|
8 |
37 |
38 |
1 |
|
9 |
42 |
42 |
0 |
|
10 |
48 |
48 |
0 |
|
11 |
61 |
61 |
0 |
Аналогично:
tp(4)
=
max{tp(1)+t(1,4);
tp(3)+t(3,4)}
= mах{8+6;
13+10} = mах{14;
23} = 23(суткам),
tp(5)
=
max{tp(3)+t(3,5);
tp(0)+t(0,5)}
= mах{13+7;
0+9} = mах{20;
9} = 20(суткам),
tp(6)
=
max{tp(4)+t(3,4);
tp(3)+t(3,6);
tp(5)+t(5,6)}
= mах{23+3;
13+6; 20+9} = mах{26;
19; 29} = 29 (суткам) и т.д.
Длина
критического пути равна раннему сроку
свершения завершающего события 11
(см. табл.
6.2):
tкр=tр,(11)=61
(суткам).
При
определении поздних сроков свершения
событий tП(i)
двигаемся по сети в обратном направлении,
т.е. справа налево, и используем формулы
(6.3) и (6.4).
Для
i=11
(завершающего
события) поздний срок свершения события
должен равняться его раннему сроку
(иначе изменится длина критического
пути): tn(11)=tp(11)=61
(сутки).
Для
i=10
tП(10)=tp(11)-t(10,11)=61-13=48
(суток), так как для события 10
существует
только один последующий путь LС10:10→11.
Для
i=9
tП(9)
=
min{tП(10)-t(9,10);
tП(11)-t(9,10)}
= min{48-6;
61-17} = min{42;
44}=42 (суткам), так как для события 9
существуют два последующих пути
LC9:9→10→11
и
9→11
и
два последующих события –
10
и
11.
Аналогично:
tП(8)=tП(9)-t(8,9)=42-4=
38 (суткам);
tП(7)=tП(10)-t(7,10)=
48-5
= 43 (суткам);
tП(6)
=
min{tП(7)-t(6,7);
tП(10)-t(6,10);
tП(9)-t(6,
9); tП(8)-t(6,8);}
=min
(43-4;
48-5; 42-13; 38-8) = min
(39; 43; 29; 30)= 29 (суткам) и т.д.
По
формуле (6.5) определяем резервы времени
i-го
события:
R(0)
= 0; R(1)
= 9-8 = 1; R(2)=
40-17 = 23
и т.д.
Резерв
времени, например, события 2
— R(2)
= 23
–
означает, что время свершения события
2
может
быть задержано на 23 суток без увеличения
общего срока выполнения проекта.
Анализируя табл. 2, видим, что не имеют
резервов времени события 0,
3, 5, 6, 9, 11. Эти
события и образуют критический путь
(на рис. 5 он выделен жирным шрифтом)
Теперь
перейдем к параметрам
работ.
Отдельная работа
может начаться (и окончиться) в ранние,
поздние или другие промежуточные сроки.
В дальнейшем при оптимизации графика
возможно любое размещение работы в
заданном интервале.
Очевидно,
что ранний срок tрн(i,
j)
начала
работы
(i,
j)
совпадает
с ранним сроком наступления начального
(предшествующего) события i,
т.е.:
tрн(i,
j)
=
tp(i). (6.6)
Тогда
ранний срок tро(i,
j)
окончания
работы (i,j)
определяется
по формуле:
tрo(i,
j)
= ‘tp(i)+t(i,j).
(6.7)
Ни
одна работа не может окончиться позже
допустимого позднего срока своего
конечного события. Поэтому поздний срок
окончания работы (i,j)
определяется
соотношением:
tпо(i,
j)=tП(j),
(6.8)
а
поздний срок tnн(i,
j)
начала
этой работы — соотношением:
. (6.9)
(6.9)
Таким
образом, в рамках сетевой модели моменты
начала и окончания работы тесно связаны
с соседними событиями ограничениями
(6.6)—(6.9).
Прежде
чем рассматривать резервы времени
работ, обратимся к резерву времени пути.
Такие резервы имеют все некритические
пути. Резерв
времени пути
R(L)
определяется как разность между длиной
критического и рассматриваемого пути:
R(L)=tкр
— t(L). (6.10)
Он
показывает, насколько в сумме могут
быть увеличены продолжительности всех
работ, принадлежащих этому пути. Если
затянуть выполнение работ, лежащих на
этом пути, на время большее чем R(L),
то
критический путь переместится на путь
L.
Отсюда
можно сделать вывод, что любая
из работ пути L
на его участке, не совпадающем с
критическим путем (замкнутым между
двумя событиями критического пути),
обладает резервом времени.
Среди
резервов времени работ выделяют четыре
разновидности.
Полный
резерв времени RП(i,
j)
работы (i,
j)
показывает, насколько можно увеличить
время выполнения данной работы при
условии, что срок выполнения комплекса
работ не изменится. Полный резерв RП(i,
j)
определяется по формуле:
. (6.11)
Полный
резерв времени работы равен резерву
максимального из путей, проходящего
через данную работу. Этим резервом можно
располагать при выполнении данной
работы, если ее начальное событие
свершится в самый ранний срок, и можно
допустить свершение конечного события
в его самый поздний срок (рис. 6.6).
(6.11)
Важным
свойством полного резерва времени
работы является то, что он принадлежит
не только этой работе, но и всем полным
путям, проходящим через нее. При
использовании полного резерва времени
только для одной работы резервы времени
остальных работ, лежащих на максимальном
пути, проходящем через нее, будут
полностью исчерпаны. Резервы времени
работ, лежащих на других (не максимальных
по длительности) путях, проходящих через
эту работу, сократятся соответственно
на величину использованного резерва.
Остальные
резервы времени работы являются частями
ее полного резерва.
Частный
резерв времени первого вида ri
работы
(i,
j)
есть часть полного резерва времени, на
которую можно увеличить продолжительность
работы, не изменив при этом позднего
срока ее начального события. Этим
резервом можно располагать при выполнении
данной работы в предположении, что ее
начальное и конечное события свершаются
в свои самые поздние сроки (см. рис. 6.6).
R1
находится по формуле:
R1(i,j)=tn(j)-tp(i)-t(i,j), (6.12)
R1(i,
j)=RП(i,
j)-R(i). (6.13)
Частный
резерв времени второго вида, или
свободный
резерв времени Rc
работы
(i,
j)
представляет часть полного резерва
времени, на которую можно увеличить
продолжительность работы, не изменив
при этом раннего срока ее конечного
события. Этим
резервом можно располагать при выполнении
данной работы в предположении, что ее
начальное и конечное события свершатся
в свои самые ранние сроки.
Rc
находится по формуле:
Rc(i,
j)=tp(j)-tp(i)-t(i,
j),
(6.14)
R1(i,
j)=RП(i,
j)-R(j). (6.15)
Свободным
резервом времени можно пользоваться
для предотвращения случайностей, которые
могут возникнуть в ходе выполнения
работ. Если планировать выполнение
работ по ранним срокам их начала и
окончания, то всегда будет возможность
при необходимости перейти на поздние
сроки начала и окончания работ.
Независимый
резерв времени Rн,
работы (i,
j)
— часть полного резерва времени,
получаемая для случая, когда все
предшествующие работы заканчиваются
в поздние сроки, а все последующие работы
начинаются в ранние сроки.
Rн(i,
j)=tp(j)-tП(i)-t(i,
j), (6.16)
или
Rн(i,j)=RП(i,j)-r(i).
(6.17)
Использование
независимого резерва времени не влияет
на величину резервов времени других
работ. Независимые резервы стремятся
использовать тогда, когда окончание
предыдущей работы произошло в поздний
допустимый срок, а последующие работы
хотят выполнить в ранние сроки. Если
величина независимого резерва,
определяемая по формуле (6.16) или (6.17),
равна нулю или положительна, то такая
возможность есть. Если же величина Rн(i,
j)
отрицательна,
то этой возможности нет, так как предыдущая
работа еще не оканчивается, а последующая
уже должна начаться. Поэтому отрицательное
значение Rн(i,
j)
не имеет
реального смысла. А фактически независимый
резерв имеют лишь те работы, которые не
лежат на максимальных путях, проходящих
через их начальные и конечные события.
Следует
отметить, что резервы времени работы
(i,
j),
показанные на рис. 6.6, могут состоять из
двух временных отрезков, если интервал
продолжительности работы t(i,
j)
занимает
промежуточную позицию между двумя его
крайними положениями, изображенными
на графиках.
Таким
образом, если
частный резерв времени первого вида
может быть использован на увеличение
продолжительности данной и последующих
работ без затрат резерва времени
предшествующих работ, а свободный резерв
времени — на увеличение продолжительности
данной и предшествующих работ без
нарушения резерва времени последующих
работ, то независимый резерв времени
может быть использован для увеличения
продолжительности только данной работы.
Работы,
лежащие на критическом пути, так же как
и критические события, резервов времени
не имеют.
Если
на критическом пути лежит начальное
событие i,
то
Rп(i,
j)
=R1(i,
j).
(6.18)
Если
на критическом пути лежит конечное
событие j,
то
Rп(i,
j)
=Rс(i,
j).
(6.19)
Если
на критическом пути лежат начальное и
конечное события i
и j,
но
сама работа не принадлежит этому пути,
то
Rп(i,
j) =R1(i,
j)=Rс(i,
j) =Rн(i,
j). (6.20)
Соотношения
(6.18) — (6.20) можно использовать при проверке
правильности расчетов резервов времени
отдельных работ.
Задача
2.
Вычислить временные параметры работ
для сетевого графика, изображенного на
рис. 6.4.
Результаты
расчетов сведем в табл. 6.3.
Вычисление
временных параметров работы (i,
j)
покажем
на примере работы (1,
4):
ранний
срок начала работы (по формуле (6.16)):
tpн(1,4)=tр(1)=8(суток),
ранний
срок окончания работы (по формуле 6.17):
tpо(1,4)=tр(1)+t(1,4)=
=8+6=14
(суток);
поздний
срок начала работы (по формуле 6.19):
tпн(1,4)=tп(4)-t(1,4)=
26
—6 = 20 (суток), где tn(4)
= 26
(см. табл. 6.2);
поздний
срок окончания работы (по формуле 6.18):
tпо(1
4)=tп(4)=26(суток).
Таким
образом, работа (t,
4) должна
начаться в интервале [8; 28] (суток) и
окончиться в интервале [12; 26] (суток) от
начала выполнения проекта.
Полный
резерв работы (1,
4) (по формуле
6.11): Rn(1,4)=tп(4)-tp(1)-
—t(1,4)
= 26-8-6=12
(суток), т.е. срок выполнения данной
работы можно увеличить на 12 суток, при
этом срок выполнения комплекса работ
не изменится.
Таблица
6.3
|
№ п/п |
Работа (i,j) |
Продолжитель- ностьработы t(i,j) |
Сроки начала |
Резервы |
||||||
|
tрн(i,j) |
tрo(i,j) |
tпн(i,j) |
tпо(i,j) |
Rп(i,j) |
Rj(i,j) |
Rc(i,j) |
Rн(i,j) |
|||
|
1 |
(0,1) |
8 |
0 |
8 |
1 |
9 |
1 |
1 |
0 |
0 |
|
2 |
(0,3) |
13 |
0 |
13 |
0 |
13 |
0 |
0 |
0 |
0 |
|
3 |
(0,5) |
9 |
0 |
9 |
11 |
20 |
11 |
11 |
11 |
11 |
|
4 |
(1,2) |
9 |
8 |
17 |
31 |
40 |
23 |
22 |
0 |
|
|
5 |
(1,4) |
6 |
8 |
14 |
20 |
26 |
12 |
11 |
9 |
8 |
|
6 |
(1,3) |
4 |
8 |
12 |
9 |
13 |
1 |
0 |
1 |
0 |
|
7 |
(2,7) |
3 |
17 |
20 |
40 |
43 |
23 |
0 |
13 |
|
|
8 |
(3,4) |
10 |
13 |
23 |
16 |
26 |
3 |
3 |
0 |
0 |
|
9 |
(3,5) |
7 |
13 |
20 |
13 |
20 |
0 |
0 |
0 |
0 |
|
10 |
(3,6) |
б |
13 |
19 |
23 |
29 |
10 |
10 |
10 |
10 |
|
11 |
(4,7) |
8 |
23 |
31 |
35 |
43 |
12 |
9 |
2 |
— |
|
12 |
(4,6) |
3 |
23 |
26 |
26 |
29 |
3 |
0 |
3 |
0 |
|
13 |
(5,6) |
9 |
20 |
29 |
20 |
29 |
0 |
0 |
0 |
0 |
|
14 |
(5,8) |
10 |
20 |
30 |
28 |
38 |
8 |
8 |
7 |
7 |
|
15 |
(5,9) |
6 |
20 |
26 |
36 |
42 |
16 |
16 |
16 |
16 |
|
16 |
(6,7) |
4 |
29 |
33 |
39 |
43 |
10 |
10 |
0 |
0 |
|
17 |
(6,10) |
5 |
29 |
34 |
43 |
48 |
14 |
14 |
14 |
14 |
|
18 |
(6,9) |
13 |
29 |
42 |
29 |
42 |
0 |
0 |
0 |
0 |
|
19 |
(6,8) |
8 |
29 |
37 |
30 |
38 |
1 |
1 |
0 |
0 |
|
20 |
(7,10) |
5 |
33 |
38 |
43 |
48 |
10 |
0 |
10 |
0 |
|
21 |
(8,9) |
4 |
37 |
41 |
38 |
42 |
1 |
0 |
1 |
0 |
|
22 |
(9,10) |
6 |
42 |
48 |
42 |
48 |
0 |
0 |
0 |
0 |
|
23 |
(9,11) |
17 |
42 |
59 |
44 |
61 |
2 |
2 |
2 |
2 |
|
24 |
(10,11) |
13 |
48 |
61 |
48 |
61 |
0 |
0 |
0 |
0 |
Покажем
на примере работы (1,
4), что
полный резерв времени работы равен
продолжительности максимального из
путей, проходящих через данную работу.
Через
работу (1,
4)
проходят
семь полных путей (см. рис. 6.4):
|
Путь |
Продолжительность, |
|
|
L1 |
0→1→4→6→7→10→11 |
39 |
|
L2 |
0→1→4→6→8→9→10→11 |
48 |
|
L3 |
0→1→4→6→8→9→11 |
46 |
|
L4 |
0→1→4→6→9→10→11 |
49 |
|
L5 |
0→1→4→6→9→11 |
47 |
|
L6 |
0→1→4→6→10→11 |
35 |
|
L7 |
0→1→4→7→10→11 |
40 |
Отсюда
максимальным из путей, проходящих через
работу (1,
4),
является
путь L4
продолжительностью
49 (суток), резерв времени которого (по
формуле (6.10)) R(L4)
=61-49=12
(суток).
Как
видим, полный резерв времени работы (1,
4)
оказался
равным резерву пути L4
–
максимального из путей, проходящих
через эту работу. Если увеличить
продолжительность выполнения работы
t(1,
4) на
12 суток, т.е. с 6 до 18 суток, то полностью
будет исчерпан резерв времени пути L4
, т.е.
этот путь станет также критическим, а
резервы времени других путей уменьшатся
соответственно на 12 суток.
Частный
резерв времени работы (1, 4)
первого
вида определим по формуле (6.12) (или по
формуле 13): R1(1,
4) = tn(4)-tn(1)=t(1,
4)= 26-9-6=11
(суток) (или R1(1,
4)
=
Rn(1,
4)
– Rn(1,4)-R(1)
= 12
— 1 = 11 (суток), т.е. при сохранении общего
срока выполнения проекта на 11 суток
может быть задержано выполнение работы
(1, 4)
и
последующих работ (по любому из путей
L1,
l2,,
…,
L7)
без затрат резерва времени предшествующих
ей работ (в данном случае без затрат
резерва времени одной предшествующей
работы (0,1)).
Частный
резерв времени второго вида, или свободный
резерв времени, работы (1,
4) найдем
по формуле (6.14) (или 6.15)): Rc(1,
4)
= tp(4)-tp(1)
— —t(l,4)
= 23-8-6
= 9 (суток) (или Rc(1,
4)
= Rn(1,
4)-R(4)
= 12-3
= 9 (суток), т.е. при сохранении общего
срока выполнения проекта на 9 суток
может быть задержано выполнение работы
(1,
4) и
предшествующих ей работ (в данном случае
работы (0,
1)) без
нарушения резерва времени последующих
работ.
Независимый
резерв времени работы (1,
4)
определим
по формуле (6.16) (или (6.17)): RH(1,
4) = tp(4)-tn(1)-t(1,
4) =
23-9-6 = 8 (суток) (или Rн(1,4)
=
=Rn(1,4)-R(1)-R(4)
= 12-1-3
= 8 (суток), т.е. на 8 суток может быть
увеличена продолжительность работы
(1,
4)
без
изменения резервов времени всех остальных
работ.
Обратим
внимание на то, что независимые резервы
работ (1,
2),
(2, 7) и
(4,
7) отрицательны
(в табл. 6.3 они обозначены прочерком).
Например, Rн(2,
7) =tp(7)-tn(2)-t(2,
7)
= 33-40-3 = -10. Это означает, что работа (2,
7) продолжительностью
3 (суток) должна закончиться на 33-и сутки
после начала комплекса работ, а начаться
на 40-е сутки, что, естественно, невозможно.
Подчеркнем,
что резервы критических работ (0,
3), (3, 5), (5, 6), (6, 9), (9, 10), (10, 11), так
же как и резервы критических событий,
равны нулю.
Следует
отметить, что в случае достаточно простых
сетевых графиков результаты расчета
их временных параметров можно фиксировать
прямо на графике. Параметры событий
записываются в кружках, разделенных на
четыре части, а параметры работ –
над соответствующими стрелками (рис.
6.7). При этом отпадает необходимость
составления таблиц.
Задание: Упорядочить исходный сетевой граф и определить временные характеристики
Решение:
Исходный граф содержит замкнутый контур – работы 4, 6, 7. Путем введения фиктивной работы 11 получают следующий сетевой граф без замкнутого контура:
Упорядочивание сетевого графа производится путем размещения всех событий по слоям: слева направо. Исходное событие 1 размещают на первом слое. Далее вычеркиваются из графа все исходящие работы из исходного события. На втором слое размещаются события без входящих работ 2, 4. Далее вновь вычеркиваются работы из события второго слоя. Аналогично размещаются события на следующих слоях. В результате получается следующий граф:
Все работы в сетевом графе должны быть направленными от события с меньшим номером к событию с большим. Поэтому необходимо произвести перенумерацию событий:.
Определим параметры сетевых графов.
Если событие j имеет несколько предшествующих событий i, то ранний срок свершения события j удобно находить по формуле:
Задержка свершения события I по отношению к своему раннему сроку не отразится на сроке свершения завершающего события (а значит на сроке выполнения комплекса работ) до тех пор, пока сумма срока свершения этого события и продолжительности (длины) максимального из последующих за ним путей не превысит длины критического пути.
Если событие i имеет несколько последующих событий j, то поздний срок свершения события I удобно находить по формуле:
Аналогично определены остальные поздние сроки
Резерв времени R(i) i-го события определяется как разность между поздним и ранним сроками его свершения:
Резерв времени события показывает, на какой допустимый период времени можно задержать наступление этого события, не вызывая при этом увеличение срока выполнения комплекса работ.
В результате получили следующую таблицу:
Lкр={0,2,4,6,7,10,11}
Lкр= 45
Определим параметры работ.
Проведем оптимизацию сетевого графа.
Граничные значения продолжительностей работ a(i,j) и b(i,j), их стоимости с(i,j), коэффициенты затрат на ускорение работ h(i,j) приведены в таблице.
Ранний срок tрн(i,j) начала работы (i,j) совпадает с ранним сроком наступления начального (предшествующего) события i, то есть:
Тогда ранний срок tро(i,j) окончания работы (i,j) определяется по формуле:
Ни одна работа не может окончиться позже допустимого позднего срока своего конечного события i. Поэтому поздний срок tпо(i,j) окончания работы (i,j) определяется соотношением:
а поздний срок tпн(i,j) начала этой работы – соотношением:
Полный резерв времени Rп(i,j) работы (i,j) показывает, на сколько можно увеличить время выполнения данной работы при условии, что срок выполнения комплекса работ не изменится. Полный резерв времени Rп(i,j) определяется по формуле:
Резерв времени первого рода R1 работы (i,j) есть часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом позднего срока ее начального события. Этим резервов можно располагать при выполнении данной работы в предположении, то ее начальное и конечное события свершатся в свои самые поздние сроки.
Резерв времени второго рода, или свободный резерв времени Rc работы (i,j) представляет часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом раннего срока ее конечного события. Этим резервов можно располагать при выполнении данной работы в предположении, то ее начальное и конечное события свершатся в свои самые ранние сроки.
Независимый резерв времени Rн работы (i,j) – часть полного резерва времени, получаемая для случая, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие работы начинаются в ранние сроки:
После вычислений была получена следующая таблица:
Оптимизация стоимости выполнения работ.
Проведем оптимизацию сетевого графа по схеме «время-стоимость». Оптимизация сетевого графа представляет процесс улучшения организации выполнения комплекса работ с учетом срока его выполнения. При использовании метода «время-стоимость» предполагают, что уменьшение продолжительности работы пропорционально возрастанию ее стоимости. Каждая работа (i,j) характеризуется продолжительностью t(i,j), которая может находиться в пределах
где 
– минимально возможная (экстренная) продолжительность работы (i,j), которую только можно осуществить в условиях разработки (исходная величина);
–максимальная продолжительность выполнения работы (i,j) (исходная величина)
Величина 
равная тангенсу угла a наклона аппроксимирующей прямой, показывает затраты на ускорение работы (i,j) (по сравнению с нормальной продолжительность) на единицу времени:
Стоимость 
работы (i,j) заключена в границах от 
(при нормальной продолжительности работы) до 
(при экстренной продолжительности работы).
Допустимый размер увеличения продолжительности данной работы:
Оптимальное время продолжительности работы
Теперь можно найти изменение стоимости работы Dс(i,j) при сокращении ее продолжительности на величину
При этом стоимость проекта после оптимизации можно найти по формуле:
В результате всех вычислений получаем следующую таблицу:
Оптимальная стоимость работ равна Сопт=502,7 руб., то есть стоимость всех работ уменьшилась на величину:
руб.
dt(i,j) – размер увеличения продолжительности работы;
h(i,j) — коэффициент затрат на ускорение работ;
tопт — оптимальная продолжительность работы;
dC – изменение стоимости работы;
В результате такой оптимизации сетевого графа мы не меняем продолжительность выполнения всего проекта, а за счет увеличения продолжительности некоторых работ, имеющих свободный резерв времени, уменьшаем стоимость выполнения работ.
В результате получаем, что в критической зоне(
>0.8) находятся работы (0,2) (2,4) (4,6) (6,7) (6,9) (7,10) (7,11) (9,11) (10,11).
В подкритической зоне(
<0.8) находятся работы (0,1) (0,3) (1,2) (3,4).
В резервной зоне(
<0.6) находятся работы (1,5) (2,6) (3,5) (3,7) (4,10) (5,8) (5,11) (5,7) (8,9) (8,11).
Сетевое планирование в условиях неопределенности
При определении временных параметров сетевого графика до сих пор предполагалось, что время выполнения каждой работы точно известно. Но чаще всего продолжительность работы по сетевому графику не известна и может принимать лишь одно из возможных значений. Другими словами, продолжительность работы t(i, j) является случайной величиной, характеризующейся своим законом распределения, а значит, своими числовыми характеристиками – средним значением (математическим ожиданием) 
(i, j) и дисперсией 
(i, j).
Закон распределения обладает следующими свойствами:
- непрерывность;
- унимодальность, т. е. наличие единственного максимума у кривой распределения;
- положительная асимметрия, т. е. максимум кривой смещен влево относительно медианы.
Этими свойствами обладает ?-распределение.
Предположим, что даны 3 оценки продолжительности выполняемых работ:
На основе этих 3 величин можно выделить для ?-распределение среднее значение продолжительности работ по формуле:
Дисперсия находится по формуле:
Следует отметить, что обычно специалистам сложно оценить наиболее вероятное время выполнения работы 
(i, j) . Поэтому в проектах используется упрощенная оценка средней продолжительности работы (i,j) на основании лишь двух задаваемых временных оценок 
(i, j) и 
(i, j):
Кроме характеристик работ необходимо найти характеристики пути, для ?-распределения можно воспользоваться центральной предельной теоремой Ляпунова на основании которой можно утверждать, что продолжительность пути L имеет нормальный закон распределения (НЗР), тогда средняя продолжительность работ принадлежит этому пути и вычисляется как сумма средних значений:
Если продолжительность работ – случайная величина, то в качестве временных характеристик сетевого графа используется средние значения этих величин, т. е. 
, 
, 
. Весьма важным моментом является оценка вероятности того, что срок выполнения проекта 
не превзойдет заданного директивного срока Т.
Полагая 
случайной величиной, имеющей нормальный закон распределения, получим:
Если P(
? T) мала (например, меньше 0,3), то опасность срыва заданного срока выполнения комплекса велика, необходимо принятие дополнительных мер.
Если P(
? T) значительна (более 0,8), то очевидно, с достаточной степенью надежности можно прогнозировать выполнение проекта в установленный срок.
В некоторых случаях представляет интерес и решение обратной задачи: определение максимального срока выполнения проекта Т, который возможен с заданной надежностью (вероятностью) ?. В этом случае:
где, Z? — нормированное отклонение случайной величины, определяемое с помощью функции Лапласа Ф(z? ) = ?.
Рассмотрим сетевой граф в условиях неопределенности. Найдем для данного сетевого графика средние значения и дисперсии работ. При этом оценим вероятность выполнения проекта в срок Т = 50 суткам.
Вероятность того, что работы будут выполнены в срок 
.
Обратная задача – задача распределения максимального срока выполнения проекта Т с надежностью
, 
То есть с надежностью 0,95 срок выполнения проекта не превысит 52 дня.
То есть с надежностью 0,93 проекта в течении 52 дней будет выполнен.
Скачать прилагающиеся файлы
Система методов сетевого планирования и управления Лекции № 11, 12
Система методов сетевого планирования и управления (СПУ) — система методов разработки планов исполнения сложных управленческих решений, планирования и управления разработкой крупных народнохозяйственных комплексов, научными исследованиями, конструкторской и технологической подготовкой производства, новых видов изделий, строительством и реконструкцией, капитальным ремонтом основных фондов путем применения сетевых графиков
Система СПУ позволяет: • формировать календарный план реализации некоторого комплекса работ; • выявлять и мобилизовывать резервы времени, трудовые, материальные и денежные ресурсы; • осуществлять у п равление комплексом работ по принципу «ведущего звена» с прогнозированием и предупреждением возможных срывов в ходе работ; • повышать эффективность управления в целом за счет четко го распределени я ответственности между руководителями разных уровней и исполнителями работ.
Под комплексом работ (комплексом операций, или проектом) мы будем понимать всякую задачу, для выполнения которой необходимо осуществить достаточно большое количество разнообразных работ. Это может быть: строительство некоторого здания, корабля, самолета или любого другого сложного объекта, и разработка проекта этого сооружения, меры (действия для) реализации управленческих решений в любой сфере жизни и т. п.
Сетевая модель представляет собой план выполнения некоторого комплекса взаимосвязанных работ (операций), заданного в специфической форме сети, графическое изображение которой называется сетевым графиком. Отличительной особенностью сетевой модели является четкое определение всех временных взаимосвязей предстоящих работ. Главными элементами сетевой модели являются события и работы.
Событие — это завершени е какого либо процесса, отражающ его отдельный этап выполнения проекта. Событие может быть частным результатом отдельной работы или суммарным результатом нескольких работ.
Путь — любая последовательность работ, в которой конечное событие каждой работы совпадает с начальным событием следующей за ней работы. Полный путь — любой путь, начало которого совпадает с исходным событием сети, а конец — с завершающим. Критический путь наиболее продолжительный полный путь.
Пример сети
Диаграмма Ганта
Основные действия при использовании методов сетевого планирования: • Создание сетевого графика (модели); • Расчет временных параметров элементов сети; • Определение критического пути (путей); • Расчет коэффициента напряженности работы; • Анализ и оптимизация сетевого графика
Создание сетевого графика (модели) есть процесс разработки календарного плана исполнения соответствующего управленческого решения Создание сетевого графика – это искусство в рамках формальных и слабо формализуемых требований Содержательные требования: 1. В числе событий сетевого графика должны быть те, что означают получение результатов, предусматриваемых управленческим решением: результаты решения управленческих задач и достижение стратегических целей; 2. Среди работ сетевого графика не должны быть те, что в данном управленческом решении являются недопустимыми по содержанию, продолжительности, объемам используемых ресурсов; 3. При оптимизации сетевого графика необходимо учитывать последовательность и сроки решения управленческих задач, а также приоритеты управленческих задач и критериев оценки качества решения задач
При построении сетевого графика необходимо соблюдать формальные правила: 1. В сетевой модели не должно быть «тупиковых» событий, т. е. событий, из которых не выходит ни одна работа, за исключением завершающего события. 2. В сетевом графике не должно быть «хвостовых» событий (кроме исходного), которым не предшествует хотя бы одна работа. 3. В сети не должно быть замкнутых контуров и петель, т. е. путей, соединяющих некоторые события с ними же самими. 4. Любые два события должны быть непосредственно связаны не более чем одной работой стрелкой. 5. В сети рекомендуется иметь одно исходное и одно завершающее событие.
Обозначения временных параметров сетевого графика Элемент сети Наименование параметра Условн. обознач парам. Событие i Ранний срок свершения события tр(i) Поздний срок свершения события tп(i) Резерв времени события R(i) Работа Продолжительность работы t(i, j) Ранний срок начала работы tрн(i, j) Ранний срок окончания работы tро(i, j) Поздний срок начала работы tпн(i, j) Поздний срок окончания работы tпо(i, j) Полный резерв времени работы R п ( Частный резерв времени работы первого вида R 1(i, j) Частный резерв времени работы второго вида, или Rс(i, j) свободный резерв времени работы Независимый резерв времени работы (i, j) Rн (i, j) Путь L Продолжительность пути t(L) Продолжительность критического пути tkp Резерв времени пути R(L)
Дополнительные понятия Критическое время комплекса работ равно координате на оси времени самого правого конца всех отрезков линейной диаграммы (диаграммы Ганта) Критические работы и события – это работы и события расположенные на критическом пути. Резерв времени – это время, на которое может быть увеличена продолжительность работы иили один из моментов свершения события, без изменения параметров критического пути
Определение критического пути может осуществляться двумя способами: 1. Нахождение всех полных путей и выбор из них самого продолжительного (длинного); 2. Расчет временных параметров графика и выбор полного пути с нулевыми резервами времени событий
Основные свойства работ сетевого графика Резервы времени имеют все некритические пути. Резерв времени пути R(L) определяется как разность между длиной критического и рассматриваемого пути : R(L) = t Kp t(L). Любая из работ пути L на его участке, не совпадающем с критическим путем (замкнутым между двумя событиями критического пути), обладает резервом времени.
Полный резерв времени работы (i, j) показывает, насколько можно увеличить время выполнения данной работы при условии, что срок выполнения комплекса работ не изменится. Полный резерв времени работы равен резерву максимального из путей, проходящего через данную работу. Этим резервом можно располагать при выполнении данной работы, если ее начальное событие свершится в самый ранний срок, и можно допустить свершение конечного события в его самый поздний срок
Полный резерв Rп(i, j) определяется по формуле Частный резерв времени первого вида R 1 работы (i, j) есть часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом позднего срока ее начального события. Этим резервом можно располагать при выполнении данной работы в предположении, что ее начальное и конечное события свершаются в свои самые поздние сроки
Частный резерв времени второго вида, или свободный резерв времени Rc работы (i, j), представляет часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом раннего срока ее конечного события. Этим резервом можно располагать при выполнении данной работы в предположении, что ее начальное и конечное события свершатся в свои самые ранние сроки
Независимый резерв времени Rн работы (i, j) — часть полного резерва времени, получаемая для случая, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие работы начинаются в ранние сроки. Использование независимого резерва времени не влияет на величину резервов времени других работ. Независимые резервы стремятся использовать тогда, когда окончание предыдущей работы произошло в поздний допустимый срок, а последующие работы хотят выполнить в ранние сроки. Если величина независимого резерва равна нулю или положительна, то такая возможность есть. Если же величина Rн (i, j) отрицательна, то этой возможности нет, так как предыдущая работа еще не окончена, а последующая уже должна начаться.
Основные свойства работ сетевого графика (продолжение) Частный резерв времени первого вида может быть использован на увеличение продолжительности данной и последующих работ без затрат резерва времени предшествующих работ, а свободный резерв времени — на увеличение продолжительности данной и предшествующих работ без нарушения резерва времени последующих работ. Независимый резерв времени может быть использован для увеличения продолжительности только данной работы.
Ранний (или ожидаемый) срок t(i) свершения i го события определяется продолжительностью максимального пути, предшествующего этому событию: где Lпi — любой путь, предшествующий i му событию, т. е. путь от исходного до i го события сети. Если событие имеет несколько предшествующих путей, а следовательно, несколько предшествующих событий i, то ранний срок свершения события j удобно находить по формуле: Поздний (или предельный) срок tп(i) свершения i го события равен: где L ci — любой путь, следующий за i м событием, т. е. путь от i ro до завершающего события сети. Если событие i имеет несколько последующих путей, а следовательно, несколько последующих событий j, то поздний срок свершения события i удобно находить по формуле:
Резерв времени R(i) i го события определяется как раз ность между поздним и ранним сроками его свершения: Ранний срок t (i, j) начала работы (i, j) совпадает с ранним сроком наступления начального (предшествующего) события i, tpн(i, j) = tp(i) Ранний срок tpo (i, j) окончания работы (i, j) определяется по формуле tpo(i, j) = tp(i) + t(i, j). Поздний срок tпo(i, j) окончания работы (i, j) определяется соотношением tпo(i, j) = tн(j) Поздний срок tnн(i, j) начала этой работы — соотношением tпн(i, j) = tн(j) t(i, j)
Номер Сроки свершения события, сутки Резерв события времени R ( i ), сутки ранний tp(j) поздний tп (i) 0 0 1 8 9 1 2 17 40 23 3 13 0 4 23 26 3 5 20 0 6 29 0 7 33 43 10 8 37 38 1 9 42 0 10 48 0 11 61 0 Временные параметры сети предыдущего рисунка
№ Работа Продол ж Сроки начала и окончания работы Резервы времени работы итель нос ть п/ (i, f) работы п t(i, f) tрн (i, j) tpo(i, j) tпн (i, j) tпo(i, j) Rп(i, j) R 1(i, j) Rс(i, j) Rн(i, j) 2 6 7 8 1 3 4 5 9 10 11 1 (0, 1) 8 0 8 1 9 1 0 2 (0, 3) 13 0 13 0 0 3 (0, 5) 9 0 9 11 20 11 11 4 (1, 2) 9 8 17 31 40 23 22 0 — 5 (14) 6 8 14 20 26 12 11 9 8 6 (1, 3) 4 8 12 9 13 1 0 7 (2, 7) 3 17 20 43 23 0 13 — 8 (3, 4) 10 13 23 16 26 3 0 9 (3, 5) 7 13 20 0 0 10 (3, 6) 6 13 19 23 29 10 10 11 (4 J) 8 23 31 35 43 12 9 2 — 12 (4, 6) 3 26 29 3 0
№ Работ Продол Сроки начала и окончания Резервы времени работы а житель работы ность п/ (i, f) работы п t(i, f) t рн tpo(i, j) t пн tпo(i, j) Rп(i, j) R 1(i, j) Rс(i, j) Rн(i, j) (i, j) 13 (5, 6) 9 20 29 0 0 14 (5, 
10 20 30 28 38 8 7 15 (5, 9) 6 20 26 36 42 16 16 16 (6, 7) 4 29 33 39 43 10 0 17 (6, 10) 5 29 34 43 48 14 14 18 (6, 9) 13 29 42 29 42 0 0 19 (6, 8 29 37 30 38 1 0 20 (7, 10) 5 33 38 43 48 10 0 21 (8, 9) 4 37 41 38 42 1 0 22 (9, 10) 6 42 48 42 48 0 0 23 (9, 11) 17 42 59 44 61 2 2 24 (10, 11) 13 48 61 48 61 0 0
Расчет коэффициента напряженности работы Коэффициентом напряженности Кн работы (i, j) называется отношение продолжительности несовпадающих (заключенных между одними и теми же событиями) отрезков пути, одним из которых является путь максимальной продолжительности, проходящий через данную работу, а другим — критический путь: где t(Lmax) — продолжительность максимального пути, проходящего через работу (i, j); t кр — продолжительность (длина) критического пути; t’ кр — продолжительность отрезка рассматриваемого пути, совпадающего с критическим путем.
или где Rп(i, j) — полный резерв времени работы (i, j). Коэффициент напряженности Кн(i, j) может изменяться в пределах от нуля (для работ, у которых отрезки максимального из путей, не совпадающие с критическим путем, состоят из фиктивных работ нулевой продолжительности) до единицы (для работ критического пути). Коэффициенты напряженности позволяют дополнительно классифицировать работы по зонам. В зависимости от величины Кн (i, j) выделяют три зоны: критическую (Kн(i, j)> 0, 8); подкритическую (0, 6 ≤K н(i, j)≤ 0, 8); резервную (Кн (i, j)< 0, 6).
Оптимизация сетевого графика представляет процесс улучшения организации выполнения комплекса работ с учетом срока его выполнения. Оптимизация проводится с целью сокращения длины критического пути, выравнивания коэффициентов напряженности работ, рационального использования ресурсов. В первую очередь принимаются меры по сокращению продолжи тельности работ, находящихся на критическом пути. Это достигается: перераспределением всех видов ресурсов, как временных (использование резервов времени некритических путей), так и трудовых, материальных, энергетических (например, перевод части исполнителей, оборудования с некритических путей на работы критического пути); при этом перераспределение ресурсов должно идти, как правило, из зон, менее напряженных, в зоны, объединяющие наиболее напряженные работы; сокращением трудоемкости критических работ за счет передачи части работ на другие пути, имеющие резервы времени; параллельным выполнением работ критического пути; пересмотром топологии сети, изменением состава работ и структуры сети.
Оптимизация сетевого графика (продолжение) В процессе сокращения продолжительности работ критический путь может измениться, и в дальнейшем процесс оптимизации будет направлен на сокращение продолжительности работ нового критического пути, и так будет продолжаться до получения удовлетворительного результата. В идеале длина любого из полных путей может стать равной длине критического пути или по крайней мере пути критической зоны. Тогда все работы будут вестись с равным напряжением, а срок завершения проекта существенно сократится.
Оптимизация сетевого графика (продолжение) Оптимизация сетевого графика методом «время — стоимость» Оптимизация сетевого графика в зависимости от полноты решаемых задач может быть условно разделена на частную и комплексную. Видами частной оптимизации сетевого графика являются: минимизация времени выполнения комплекса работ при заданной его стоимости; минимизация стоимости комплекса работ при заданном времени выполнения проекта. Комплексная оптимизация представляет собой нахождение оптимального соотношения величин стоимости и сроков выполнения проекта в зависимости от конкретных целей, ставящихся при его реализации. При использовании метода «время — стоимость» предполагают, что уменьшение продолжительности работы пропорционально возрастанию ее стоимости. Комплексная оптимизация осуществляется путем выбора компромисса между вариантами с минимально возможным временем и с минимально возможной стоимостью выполнения комплекса работ.
Сетевое планирование в условиях неопределенности Чаще всего продолжительность работы по сетевому графику заранее не известна и может принимать лишь одно из ряда возможных значений. Другими словами, продолжительность работы t(i, j) является случайной величиной, характеризующейся своим законом распределения, а значит, своими числовыми характеристиками — средним значением, или математическим ожиданием, t(i, j) и дисперсией. Практически во всех системах СПУ априори принимается, что распределение продолжительности работ обладает тремя свойствами: а) непрерывностью; б) унимодальностью, т. е. наличием единственного максимума у кривой распределения; в) двумя точками пересечения кривой распределения с осью Ох, имеющими неотрицательные абсциссы. Кроме того, принято, что распределение продолжительности работ обладает положительной асимметрией, т. е. максимум кривой смещен влево относительно медианы (линии, делящей площадь под кривой на две равные части). Распределение, как правило, более круто поднимается при удалении от минимального значении t и полого опускается приближении к максимальному значению t
Простейшим распределением с подобными свойствами является известное в математической статистике β распределениие. Анализ большого количества статистических данных (хронометражи времени реализации отдельных работ, нормативные данные и т. д. ) показывает, что β распределениие можно использовать в качестве априорного для всех работ. Для определения числовых характеристик t(i, j) и дисперсии(i, j) этого распределения для работы (i, j) на основании опроса ответственных исполнителей проекта и экспертов определяют три временные оценки а)оптимистическую оценку to(i, j), т. е. продолжитель ность работы (i, j) при самых благоприятных условиях; б)пессимистическую оценку tп(i, j), т. е. продолжитель ность работы (i, j) при самых неблагоприятных условиях; в) наиболее вероятную оценку tнв(i, j), т. е. продолжительность работы (i, j) при нормальных условиях.
Оценка временных параметров в условиях неопределенности (продолжение) Предположение о β распределении продолжительности работы ( i , j ) позволяе получить следующие оценки ее числовых характеристик: В реальных проектах используется упрощенная (и менее точная) оценка средней продолжительности работы ( i , j ) на основании лишь двух задаваемых временных оценок to(i, j) и tп(i, j):
Виды обеспечения решений по социально экономическому и политическому развитию территорий Интеллектуальное 1 Финансовое 2 Техническое 3 Ресурсное 4 Организационное 5 Кадровое 6 Информационное, PR сопровождение 7 Правовое 8 36
Обеспечить решение по социально экономическому и политическому развитию территорий – значит выполнить какой то комплекс работ План исполнения соответствующего управленческого решения может формироваться в виде сетевого графика, с учетом всех работ, которые надо выполнить в рамках указанных видов обеспечения решения. Сетевой график может оптимизироваться по методу «время стоимость» . При этом могут использоваться методы линейного и нелинейного программирования. 37