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

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

      tр.н(i,j) = tp(i),                                                                                                     (3)

      tп.н(i,j) = tп(j) – t(i,j),                                                                                          (4)

      tp.o(i,j) = tp(i) + t(i,j),                                                                                          (5)

      tп.о(i,j) = tп(j).                                                                                                     (6)

      Для всех работ критического пути  

      tр.н(i,j) = tп.н(i,j) и tр.о(i,j) = tп.о(i,j),                                                                (7) 

      так как начальное и конечное события этих работ находятся на критическом пути, а следовательно,  

tp(i) = tп(i) = tп(j) – t(i,j) и tп(j) = tp(j) = tp(i) + t(i,j).                                                (8) 

      Разница между продолжительностью критического пути и любого другого пути сети t(L) называется полным резервом времени пути и обозначается через P(L): 

      P(L) = tкр – t(L).                                                                                                  (9) 

      Величина P(L) показывает, насколько в сумме может быть увеличена продолжительность всех работ, принадлежащих пути L, чтобы при этом не изменилась продолжительность критического пути tкр.

      Резерв  времени события i обозначается через P(i) и определяется как разница между поздним и ранним сроками свершения данного события, то есть: 

      P(i) = tп(i) – tp(i);                                                                                              (10)

      легко показать, что 

      P(i) = P[L(i)max],                                                                                              (11) 

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

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

      В системах СПУ используются четыре вида резервов времени работ: полный, свободный, и два вида частных резервов времени.

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

      Для всех работ критического пути Рп(i,j) = 0.

      Величина  полного резерва времени может  быть определена по следующей формуле:

      Рп(i.j) = tп(j) – tp(i) – t(i,j).                                                                               (12) 

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

      Следует различать два вида частных резервов:

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

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

      P’п(i,j) = Рп(i,j) – P(i),                                                                                      (13)

      P”п(i,j) = Pп(i,j) – P(j).                                                                                     (14) 

      Свободным резервом времени работы (i,j) называется та часть ее полного резерва, которая сохраняется у нее при условии, что начальное событие данной работы свершится в самый поздний срок tп(i), а конечное – в самый ранний tp(j): 

      Pc(i.j) = tp(j) – tп(i) – t(i,j).                                                                               (15) 

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

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

      kн(i.j) = 1 – Рп(i,j) / t”кр(i,j)max.                                                                     (16) 

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

      Величина  коэффициента напряженности у разных работ в сети лежит в пределах 0 ≤ kн(i,j) ≤ 1, причем у работ критического пути kн(i,j) = 1.

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

2. Методы  сетевого планирования.

2.1 Метод критического  пути. 

    Конечным  результатом применения метода критического пути (СРМ) будет построение временного графика выполнения проекта. Для этого проводятся специальные вычисления, в результате чего получаем следующую информацию.

1. общая длительность выполнения проекта;
2. разделение множества процессов, составляющих проект, на критические 
   и некритические.

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

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

    □_j — самое раннее возможное время наступления события j,

    ∆_j самое позднее возможное время наступления события j,

    D_ij — длительность процесса (i, j).

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

    Проход  вперед. Вычисления начинаются в узле 1 и заканчиваются в последнем узле n.

    Начальный шаг. Полагаем П₁ = 0; это указывает на то, что проект начинается в нулевой момент времени.

    – Основной шаг j. Для узла j определяем узлы – р, q, ..., v, непосредственно связанные с узлом j процессами (p,j), {q, j), ..., (v, j), для которых уже вычислены самые ранние времена наступления соответствующих событий. Самое раннее время наступления события j вычисляется по формуле 

    □_{j =} max(□_P, +D_pj , □_q+D_qj, ..., U_v+D_vj)                                                                         (17) 

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

    Проход  назад. В этом проходе вычисления начинаются в последнем узле n и заканчиваются в узле 1.

    – Начальный шаг. Полагаем ∆_n = □_n это указывает, что самое раннее и самое позднее времена для завершения проекта совпадают.

    – Основной шаг j. Для узла j определяем узлы р, q, ..., v, непосредственно связанные с узлом j процессами (j, р), (j, q), ..., (j, v), для которых уже вычислены самые поздние времена наступления соответствующих событий. Самое позднее время наступления события у вычисляется по формуле: 

    ∆_j = min(∆_P - D_jp, ∆_q - D_jq, ..., ∆_{v -}-D_jv.)                                                                         (18) 

    Проход  назад завершается при вычислении величины ∆₁ для узла 1. Процесс (i, j) будет критическим, если выполняются три условия.

1. ∆_i = □_i
2. ∆_j = □_j
3. ∆_j.-∆_i = □_j - □_I = D_ij

    Если  эти условия не выполняются, то процесс некритический.

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

2.2 Метод оценки и пересмотра планов (ПЕРТ, PERT) 

     Метод оценки и пересмотра планов PERT представляет собой разновидность анализа по методу критического пути с более критичной оценкой продолжительности каждого этапа проекта. При использовании этого метода необходимо оценить наименьшую возможную продолжительность выполнения каждой работы, наиболее вероятную продолжительность и наибольшую продолжительность на тот случай, если продолжительность выполнения этой работы будет больше ожидаемой. Метод ПЕРТ допускает неопределенность продолжительности операций и анализирует влияние этой неопределенности на продолжительность работ по проекту в целом.

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

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

      Метод PERT отличается от СРМ тем, что здесь  длительность процессов характеризуется тремя оценками.

    1) оптимистичная оценка времени а, когда предполагается, что выполнение 
процесса будет происходить максимально быстро.

    2) наиболее вероятная оценка времени m, когда предполагается, что выполнение процесса будет происходить нормально.

    3) пессимистическая оценка времени b, когда предполагается, что выполнение процесса будет происходить очень медленно.

    Любая возможная оценка времени выполнения процесса будет лежать в интервале (а, b). Поэтому оценка времени m также должна лежать в этом интервале. На основе этих оценок среднее время D выполнения процесса и дисперсия v вычисляются пo формулам