Сетевое планирование и управление

σ²(i,j)=[(t_п(i,j)- t₀(i,j)) /6]² .

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

     t(i,j) = 2t₀(i,j)+3t_п(i,j)/5. 

Рисунок 6 – Временные оценки.

     Зная t(i,j) и σ²(i,j), можно определить временные параметры сетевого графика и оценивать их надежность.

     Так, при достаточно большом количестве работ, принадлежащих пути L, и выполнении некоторых весьма общих условий можно применить центральную предельную теорию Ляпунова, на основании которой можно утверждать, что общая продолжительность пути L имеет нормальный закон распределения со средним значением t(L), равным сумме средних значений продолжительности составляющих его работ t(i,j), и дисперсией σ²(L), равной сумме соответствующих дисперсий σ²(i,j):

     t(L) =∑t(i,j);

     σ²(L)=∑σ²(i,j).

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

     Полагая t_кр случайной величиной, имеющей нормальный закон распределения, получим

     Р(t_кр Т) = + Ф( ),

     На  рисунке 4 это площадь заштрихованной фигуры, где Ф(z) – значение интеграла вероятностей Лапласа, где z= (Т- )/ σ_кр; σ_кр – среднее квадратическое отклонение длины критического пути: σ_кр = .

     Если  Р(t_кр Т) мала (например, меньше 0,3), то опасность срыва заданного срока выполнения комплекса велика, необходимо принятие дополнительных мер (перераспределение ресурсов по сети, пересмотр состава работ и событий и т.п.). Если Р(t_кр Т) значительна( например, более 0,8), то с достаточной степенью надежности можно прогнозировать выполнение проекта в установленный срок. [6, c.342]

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

     Т= + z_β σ_кр,

     где z_β – нормированное отклонение случайной величины, определяемое с помощью функции Лапласа Ф(z_β)=β. 

     2.3 Оптимизация сетевого графика методом «время-стоимость» 

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

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

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

     a(i, j) ≤ t(i, j) ≤ b(i, j),

где a(i, j) - минимально возможная (экстренная) продолжительность работы  (i, j), которую можно осуществить только в условиях разработки;

      b(i, j) – нормальная продолжительность выполнения работы (i, j).

      При этом стоимость с(i, j) работы заключена в пределах от с_min(i, j) (при нормальной продолжительности работы) до с_мах(i, j) (при экстренной продолжительности работы).

      Используя аппроксимацию по прямой (рис. 5), можно  легко найти изменение стоимости  работы ∆c(i,j) при сокращении ее продолжительности на величину b(i, j) - t(i, j):

∆c(i,j)=[b(i, j) - t(i, j)]h(i, j).

Величина h(i, j), равная тангенсу угла α наклона аппроксимирующей прямой, показывает затраты на ускорение работы (i, j) (по сравнению с нормальной продолжительностью) за единицу времени:

h(i, j)=tg α= . 

     Рисунок 7 – Оптимизация сетевого графика методом «время-стоимость».

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

     С=∑c(i,j),

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

С=∑∆c(i,j)= ∑ [b(i, j) - t(i, j)]h(i, j).

     Для проведения частной оптимизации сетевого графика кроме продолжительности работ t(i,j) необходимо знать их граничные значение a (i.j) и b (i,j), их стоимости c(i,j), а также показатели затрат на ускорение работ h(i,j). Продолжительность каждой работы t (i,j) целесообразно увеличить на величину такого резерва, чтобы не изменить ранние (ожидаемые) сроки наступления всех событий сети, то есть на величину свободного резерва времени R_c(i,j).[6, c. 352] 
 
 
 
 
 
 
 
 
 
 
 
 
 

3. Моделирование процесса с помощью сетевого графика

3.1 Линейная диаграмма 

     Для нахождения критического времени и  критического пути сетевого графика  можно воспользоваться линейной диаграммой. Рассмотрим данный упорядоченный  сетевой график (рис. 8).

     

     Рисунок 8 – Сетевой график 

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

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

     Так, критическое время комплекса  работ равно координате на оси  времени самого правого конца  всех отрезков диаграммы. 

     Рисунок 9 – Линейная диаграмма проекта. 

     3.2 Определение временных параметров событий и критического пути

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

     Найденные параметры сведем в таблицу 2.

     Таблица 2 – Параметры сетевого графика.

Номер события	Сроки свершения  события, сутки		Резерв  времени R(i), сутки
	Ранний  tp(i)	Поздний tп(i)
0 1 2 3 4 5 6 7 8 9 10 11	0 8 17 13 23 20 29 33 37 42 48 61	0 9 40 13 26 20 29 43 38 42 48 61	0 1 23 0 3 0 0 10 1 0 0 0

 

     При определении ранних сроков свершения  событий t_р(i) двигаемся по сетевому графику слева направо.

     i = 0, t_р (0) =0;

     i = 1, t_р (1) = t_р(0)+ t_р(0,1)= 0+8 = 8;

     i = 2, t_р (2) = t_р(1)+ t_р(1,2)=8+9;

     i = 3, t_р(3) = max{ t_р(0)+ t(0,3); t_р(1)+ t(1,3)}=max{0+13; 8+4}=13;

     i =4, t(4)=max{t(1)+t(1,4); t(3)+t(3,4)}=max{8+6;13+10} =max{14,23}=23 (суткам);

     i = 5, max{t(3)+t(3,5); t(0)+t(0,5)}=max{13+7;0+9}=20 (суткам);

     i=6, max{t(4)+t(3,4); t(3)+t(3,6); t(5)+t(5,6)}=max{26;19;29}=29 (суткам) и т.д.

     Длина критического пути равна раннему  сроку свершения завершающего события 11: t_кр=t_р(11)=61 (суткам).

     При определении поздних сроков свершения  событий t_п(i) двигаемся в обратном направлении.

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

     Для i=10 t_п(10)=t_р(11)-t(10,11)=61-13=48 (суток), так как для события 10 существует только один последующий путь L_c10:10 11.

     Для i=9 t_п(9) = min{t_п(10)-t(9,10); t_п(11)-t(9,10)}=min {42; 44}=42 (суткам), так как для события 9 существует два последующих пути L_с9: 9 10 11 и 9-11 и два последующих события 10 и 11.

     t_п(8) = t_п(9)-t(8,9) = 42-4 =38 (суток);

     t_п(7)=t_п(10) – t(7,9) = 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{39,43,29,30} = 29 (суткам) и т.д.

     Определим резервы времени i-го события:

     R(0) = 0; R(1) = 9-8 =1; R(2) = 40-17=23 и т.д.

     Резерв  времени, например события 2 R(2) =23, означает, что время совершения события 2 может быть задержаны на 23 суток без увеличения общего срока выполнения проекта. Из таблицы видно, что события 0,3,5,6,9,10,11 резервов времени не имеют. Именно эти события и образуют критический путь. 

     3.3 Определение временных параметров работ 

     Вычислим  временные параметры работ данного  сетевого графика.

     Результаты  расчетов сведем в таблицу 3.

     Вычисление  временных параметров работы рассмотрим на примере работы (1,4):

- ранний  срок начала работы: t_рн (1,4) = t_р(1)=8 (суток);

- ранний  срок окончания работы: t_ро(1,4)=t_р(1)+t(1,4) = 8+6=14 (суток);

- поздний  срок начала работы: t_пн(1,4)=t_п(4)-t(1,4)=26-6=20 (суток);

- поздний  срок окончания работы: t_по(1,4)=t_п(4)=26 (cуток).

     Таким образом, работа должна начаться в интервале [8,28] (суток) и окончиться в интервале [12,26] (суток) от начала выполнения проекта.

     Полный  резерв работы (1,4): R(1,4)=t(4)-t(1)-t(1,4)=26-8-6=12 (суток), то есть срок выполнения данной работы можно увеличить на 12 суток, при этом срок выполнения комплекса работ не изменится.

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

     Таблица 3 – Результаты расчетов временных параметров работ.

Работа  (i,j)	Прод-сть раб.  t(i,j)	Cроки начала и окончания работы				Резервы времени работы
		tрн(i,j)	tро(i,j)	tпн(i,j)	tпо(i,j)	Rп(i,j)	R1(i,j)	Rс(i,j)	Rн(i,j)
(0,1) (0,3) (0,5) (1,2) (1,4) (1,3) (2,7) (3,4) (3,5) (3,6) (4,7) (4,6) (5,6) (5,8) (5,9) (6,7) (6,10) (6,9) (6,8) (7,10) (8,9) (9,10) (9,11) (10,11)	8 13 9 9 6 4 3 10 7 6 8 3 9 10 6 4 5 13 8 5 4 6 17 13	0 0 0 8 8 8 17 13 13 13 23 23 20 20 20 29 29 29 29 33 37 42 42 48	8 13 9 17 14 12 20 23 20 19 31 26 29 30 26 33 34 42 37 38 41 48 59 61	1 0 11 31 20 9 40 16 13 23 35 26 20 28 36 39 43 29 30 43 38 42 44 48	9 13 20 40 26 13 43 26 20 29 43 29 29 38 42 43 48 42 38 48 42 48 61 61	1 0 11 23 12 1 23 3 0 10 12 3 0 8 16 10 14 0 1 10 1 0 2 0	1 0 11 22 11 0 0 3 0 10 9 0 0 8 16 10 14 0 1 0 0 0 2 0	0 0 11 0 9 1 13 0 0 10 2 3 0 7 16 0 14 0 0 10 1 0 2 0	0 0 11 - 8 0 - 0 0 10 - 0 0 7 16 0 14 0 0 0 0 0 2 0