Характеристики элементов сетевой модели

 

 

При расчетах для сетевой модели определяются следующие характеристики ее элементов.

Характеристики событий

1. Ранний срок свершения события tp(0) = 0, tp(j) = maxi{tp(i) + t(ij)}, j = 1 – N характеризует самый ранний срок завершения всех путей, в него входящих. Этот показатель определяется «прямым ходом» по графу модели, начиная с начального события сети.

2. Поздний срок свершения события tп(N) = tp(N), tп(i) = minj{tп(j) – t(ij)}, i = 1 – (N – 1) характеризует самый поздний срок, после которого остается ровно столько времени, сколько требуется для завершения всех путей, следующих за этим событием. Этот показатель  определяется «обратным ходом» по графу модели, начиная с завершающего события сети.

3. Резерв времени события R(i) = tп(i) – tp(i) показывает, на какой максимальный срок можно задержать наступление этого события, не вызывая при этом увеличения срока выполнения всего комплекса работ.

Резервы времени для событий на критическом пути равны нулю, R(i) = 0.

Характеристики работы (i, j)

1. Ранний срок начала работы: t pн(i, j) = t p(i).

2. Ранний срок окончания работы: t po(i, j) = t pн(i, j) + t ij = t p(i) + t ij.

3. Поздний срок начала работы: t пн(i, j) = t п(j) – t ij.

4. Поздний срок окончания работы: t по(i, j) = t п(j).

5 . Резервы времени работ:

• полный резерв R п(i, j) = t п(j) – t p(i) – t ij –

максимальный запас времени, на который можно отсрочить начало или

увеличить длительность работы без увеличения длительности критического пути. Работы на критическом пути не имеют полного резерва времени, для них Rп(i, j) = 0;

• частный резерв  R 1(i, j) = R п(i, j) – R(i) = t п(j) – t п(i) – t ij –

часть полного резерва, на которую можно увеличить продолжительность

работы, не изменив позднего срока ее начального события;

• свободный резерв R с(i, j) = R п(i, j) – R(j) = t p(j) – t p(i) – t ij –

максимальный запас времени, на который можно задержать начало работы или

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

• независимый резерв R н(i, j) = R п(i, j) – R(i) – R(j) = t p(j) – t п(i) – t ij –

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

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

Сделаем ряд замечаний. Работы, лежащие на критическом пути, резервов времени не имеют. Если на критическом пути Lкр лежит начальное событие i работы (i, j), то Rп(i, j) = R1(i, j). Если на Lкр лежит конечное событие j работы (i, j), то Rп(i, j) = Rc(i, j). Если на Lкр лежат и событие i, и событие j работы (i, j),  а сама работа  не принадлежит критическому пути, то Rп(i, j) = Rс(i, j) = Rн(i, j).

Характеристики путей

1. Продолжительность пути равна сумме продолжительностей составляющих ее работ.

2. Резерв времени пути равен разности между длинами критического

пути и рассматриваемого пути.

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

продолжительности срока выполнения всех работ.

В сетевой модели можно выделить так называемый критический путь. Критический путь Lкр состоит из работ (i, j), у которых полный резерв времени равен нулю Rп(i, j) = 0, кроме этого, резерв времени R(i) всех событий i на критическом равен 0. Длина критического пути определяет величину наиболее длинного пути от начального до конечного события сети и равна

),

tкр = tp(N) = tп(N). Заметим, что в проекте может быть несколько критических путей.

3. Коэффициент напряженности работ

Видно, что Кн(i, j) < 1. Чем ближе Кн(i, j) к 1, тем сложнее выполнить данную работу в установленный срок. Напряженность критических работ полагается равной 1. Все работы сетевой модели могут быть разделены на 3 группы: напряженные (Кн(i, j) > 0, 8), надкритические (0, 6 < Кн(i, j) < 0, 8) и резервные (Кн(i, j) < 0, 6).

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

 

6.  Временные параметры сетевых графиков.

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

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

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

Для каждого события, включенного в сетевой график, рассчитываются следующие показатели:

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

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

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

Зная указанные показатели для событий, для каждой из работ составленного графика можно определить следующие параметры: ранний срок начала работы, который определяется моментом наступления начального ной работы события в его ранний срок; поздний срок начала работы, определяемый моментом наступления конечного для данной работы события в его поздний срок за вычетом продолжительности работы (временной оценки); ранний срок окончания работы и, наконец, поздний срок окончания работы, т. е. предельно допускаемый срок окончания.

Линейный график Гранта

Для сетевого графика часто строится линейный график Грантта, на котором обозначаются ранние времена начала и продолжительности всех работ. На графике Гранта каждая работа (i, j) обозначена отрезком, который имеет длину tij и начинается в ранний срок tp(i) начального события (рис. 3.1).

Работы

 

(6, 7) (5, 7) (5, 6) (4, 6) (3, 5) (2, 7) (2, 5) (2, 3) (1, 4) (1, 3) (1, 2)

 

 

0

 

 

t tp(2) tkp = 16

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

 Пример вычисления характеристик сетевого графика

Пример. Определить характеристики сетевого графика, длительности работ которого представлены в табл. 3.1.

Таблица 3.1.

 

 

События (i)	События (j)
1	–	4	5	4	–	–	–
2	–	–	3	–	7	–	8
3	–	–	–	–	4	–	–
4	–	–	–	–	–	2	–
5	–	–	–	–	–	1	3
6	–	–	–	–	–	–	4
7	–	–	–	–	–	–	–

 

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

Решение. С помощью табл. 3.1 строится сетевой график (рис. 3.2) и рассчитываются все характеристики событий и работ.

Рис. 3.2. Сетевой график с х арактеристиками событий

1. Рассчитаем характеристики событий. При определении ранних сроков наступления событий двигаемся по сетевому графику слева направо и используем формулы tp(0) = 0, tp(j) = maxi{tp(i) + t(i, j)}, j = 1, 2, …, N. При определении поздних сроков наступления события двигаемся по сетевому графику справа налево и используем формулы tп(N) = tp(N), tп(i) = minj{tп(j –

– t(ij)}, i = 1, 2, …, N – 1. Для наглядности каждое событие сетевого графика

разделено на 4 сектора. Верхний сектор соответствует номеру события, в левом секторе записан ранний срок tp(i) наступления события i, в правом – поздний срок tп(i) наступления события i, в нижнем секторе представлен резерв времени R(i) события i. Эти же характеристики представлены в таблице, приведенной ниже.

 

 

i	tp(i)	tп(i)	R(i)
1	0	0	0
2	4	4	0
3	5	7	2
4	4	10	6
5	11	11	0
6	12	12	0
7	16	16	0

Анализ таблицы и сетевого графика показывает, что критический путь имеет вид (1-2-5-6-7), а его длина равна tкр = 16.

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

Расчет сроков начала и окончания работ проводим по формулам tрн(i, j) = tp(i), tро(i, j) = tp(i) – tij, tпн(i, j) = tп(j) – tij, tпо(i, j) = tп(j). Расчет резервов времени работ проводим по формулам

Rп(i, j) = tп(j) – tp(i) – tij, R1(i, j) = Rп(i, j) – R(i) = tп(j) – tп(i) – tij,

R с(i, j) = R п(i, j) – R(j) = tp(j) – tp(i) – tij,

R н(i, j) = R п(i, j) – R(i) – R(j) = t p(j) – t п(i) – t ij.

Все расчеты сведены в табл. 3.2 (столбцы 2-9).

Таблица 3.2

Работы	t ij	tрн(ij)	tр0(ij)	t пн	tп0 = tп(j)	Rп	R1	Rc	Rн	Кн
			(2 + 1)	(5 – 1)		(3 – 2 – 1)
	1	2	3	4	5	6	7	8	9	10
(1, 2)	4	0	4	0	4	0	0	0	0	–
(1, 3)	5	0	5	2	7	2	4	2	2	0, 8
(1, 4)	4	0	4	6	10	6	6	0	0	0, 5
(2, 3)	1	4	5	6	7	2	2	0	0	0, 7
(2, 5)	7	4	11	4	11	0	0	0	0	–
(2, 7)	8	4	12	8	16	4	4	4	4	0, 4
(3, 5)	4	5	9	7	11	2	0	2	0	0, 7
(4, 6)	2	4	6	10	12	6	0	6	0	0, 5
(5, 6)	1	11	12	11	12	0	0	0	0	–
(5, 7)	3	11	14	13	16	2	2	2	2	0, 6
(6, 7)	4	12	16	12	16	0	0	0	0	–

 

Анализ таблицы и сетевого графика показывает, что критический путь имеет вид (1-2-5-6-7), а его длина равна tкр = 16.

3. После нахождения критического пути (1-2-5-6-7) длины 16 перейдем к определению напряженности работ. Рассмотрим работу (3, 5) и найдем все полные пути, проходящие через эту работу, и соответствующие им длины:

L1: 1-2-3-5-7; t(L1) = 12; L2: 1-3-5-7; t(L2) = 12; L3: 1-3-5-6-7; t(L3) = 14; L4: 1-2-3-5-6-7; t(L4) = 14.

Через работу (3, 5) проходит два максимальных пути длины 14. Выберем

кр

 второй из них. Тогда t '
= 9 – длина части (1-2, 5-6-7) пути (1-2-3-5-6-7), совпадающей с критическим путем (1-2-5-6-7). Воспользуемся формулой расчета коэффициента напряженности, в результате получим, что

кр

Rн(3, 5) = 1 – Rп(3, 5) / (tкр – t') = 1 – 2 / (16 – 9) = 0, 7.

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

 

1. Построение «дерева» сетевого графика

На 1-й уровень помещается начальная вершина сетевого графика. На (n + 1)-й уровень помещаются все вершины графа, непосредственно связанные с уровнем (n) и соединяются с ним ребрами работ. Расположение вершин на каждом уровне осуществляется слева направо в порядке возрастания номеров.

 

2. Составление списка всех полных путей сетевого графика

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

 

7. Оптимизация сетевого графика по времени.

8. Оптимизация сетевого графика по стоимости.

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: