Правила построения сетевого графика

При построении сетевого графика необходимо соблюдать ряд правил.

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

2. В сетевом графике не должно быть "хвостовых" событий (кроме исходного), которым не предшествует хотя бы одна работа.

Рис.2.4.

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

Рис. 2.5.

4. Любые два события должны быть непосредственно связаны не более чем одной работой стрелкой.

5. В сети рекомендуется иметь одно исходное и одно завершающее событие.

Если в соответственной сети это не так, то добиться желаемого можно путём введения фиктивных событий и работ.

2.3.6. Основные понятия сетевого графика

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

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

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

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

Рассмотрим содержание и расчёт временных параметров. Начнём с параметров событий.

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

Если событие "j" имеет несколько предшествующих путей, а следовательно несколько предшествующих событий "i", то ранний срок свершения события "i" удобно находить по формуле:

t_p(j)=max[t_p(i)+t(i,j)] (1)

Ранний срок свершения последнего события представляет сбой величину критического пути.

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

последнего события совпадают, а для остальных событии рекомендуется воспользоваться формулой:

tn(j)=min[tn(i)-t(i,j)] (2)

2. Резерв времени "i"-ro события определяется следующим образом:

R(i)=t_n(i)- t_p(i) (3)

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

Теперь перейдем к параметрам работ.

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

Ранний срок начала работы:

t _рn(i,j)=t_p(i) (4)

Ранний срок окончания работы:

t _po(i,j)=t_p(i) +t(i,j) (5)

Поздний срок окончания работы:

t_no(i.j)=t_n(j) (6)

Поздний срок начала работы:

t_nn(i,j)=t_n(j)-t(i,j) (7)

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

Резерв некритического пути:

R(L)=t_kp-t(L) (8)

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

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

R_п(i,j)=t_n(j)-t_р(i)- t(i,j) (9)

Остальные резервы времени работы являются частями полного ее резерва.

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

R₁(i,j)=t_n(j)-t_n(i)- t(i,j) (10)

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

R_c(j.j)=t_p(i)-t_p(i)-t(i,j) (11)

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

R_н(i,j)=t_P(j)-tn(i)-t(i.j) (12)

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

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

Приведённые выше временные параметры событий и работ могут быть использованы для оптимизации сетевого графика.

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

a(i,j)<=t(i,j)<=b(i,j) (13)

где b(i,j) – нормальная продолжительность работы. a(i,j) – минимально возможная. При этом стоимость c(i,j) работы (i,j) заключена в границах от с_min–(i,j) до с_max(i,j). Тогда затраты на ускорение работы (i,j) можно вычислить:

h(i,j)=(c_max(i,j)-c_min(i,j))/(b(i,j)-a(i,j)) (14)

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

уменьшится на величину

ΔС= Σ min[b(i,j)-t(i,j),Rc(i,j)]*h(i,j) (15)

Таким образом, в результате оптимизации сети удалось осуществить выполнение комплекса работ в те же сроки при минимальной его стоимости.

Что Вы должны знать:

(вопросы для самоконтроля

1. Каковы правила построения сетевых моделей?

2. Как определяются ранний и поздний сроки свершения события?

3. Как определяется резерв времени события?

4. Что показывают ранние начала и ранние окончания работ?

5. Что показывают поздние начала и поздние окончания работ?

6. Как можно использовать сведения о резервах времени работ?

7. Как определяется критический путь и что он означает?

8. В чем состоит метод оптимизации сетевой модели по принципу «Время – стоимость»?

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

Пример:

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

Работа	0,1	0,2	1,2	1,3	2,7	3,4	3,5	4,6	5,6	6,7	7,8
Длительность

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

Временные параметры событий Таблица 1.

№ ранний срок поздний срок резерв времени

события tр(i) tп(i) R(i)

0 0 0 0

1 20 20 0

2 32 81 49

3 27 27 0

4 53 53 0

5 40 50 10

6 75 75 0

7 88 88 0

8 99 99 0

Критическому пути соответствуют нулевые значения резервов времени.

0—1—3—4—6—7—8

Длина критического пути равна 99.

Примеры для закрепления:

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

1)

Работа	0,1	0,2	1,2	1,3	2,7	3,4	3,5	4,6	5,6	6,7	7,8
Длительность

2)