Оптимизация сетевой модели комплекса производственных работ

      Таблица 3

 

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

     На  первом шаге  продолжительность  работы 4–6 может быть увеличена на максимально возможную величину, т.к. при этом продолжительность второго полного пути все равно будет ниже требуемой (13+3=16<20). Тогда затраты на эту работу, с более поздним сроком выполнения, снизится на 120 у.е. (3*40=120).

      Работа 5–6 входит в третий полный путь. Увеличиваем продолжительность на максимально возможную величину, и она становится равной заданной. Затраты на эту работу составят: 5*35=175 (у.е.)

      В третьем шаге работа 3-6 входит в первый полный путь. Увеличиваем продолжительность на максимально возможную величину, и она становится равной заданной. Затраты на эту работу, с более поздним сроком выполнения, снизятся на 6*30=180 (у.е.). 

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

     Подсчитав суммарное снижение затрат из-за произведенного увеличения продолжительностей работ (–120–175–180=–475 у.е.) и зная первоначальную стоимость (1710 у.е.) всего комплекса работ в рассматриваемом ускоренном варианте его выполнения, получим, что при увеличении продолжительности выполнения всего комплекса работ с 15 суток (критический путь) до 20 суток оптимальные затраты составят:

                                                 1710 – 475=1235 (у.е.)

  Итоговые  результаты, полученные двумя способами оптимизации, должны совпадать. Проверим это: 

                   Таблица 4а. Нормальный вариант выполнения комплекса работ

 
 

                 Таблица 4б.  Ускоренный вариант выполнения комплекса работ

 

      

        Продолжительности соответствующих полных путей после оптимизации совпадают – 20,16,20; стоимость выполнения всего комплекса после оптимизации совпадают – 1235. 

4. Расчет  параметров оптимизированного сетевого графика

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

     Ранний  срок tp(j) свершения события j - это ранний срок, необходимый для выполнения всех работ, предшествующих данному событию: tp(j) = max (tp(i) + t(i,j)), где

           tp(i) – ранний срок свершения события _i;

               t(i,j) – продолжительность работы (i,j);

              Uj – множество работ, входящих в событие j. 

      t_p(1) = 0;

      t_p(2) = t_p(1) + t(1,2)= 0 + 3 = 3;

      t_p(3) = t_p(2) + t(2,3)= 3 + 5 = 8;

      t_p(4) = t_p(2) + t(2,4)= 3 + 4 = 7;

      t_p(5) = t_p(4) + t(4,5)= 7 + 2 = 9;

      t_p(6) = max {(t_p(3) + t(3,6)), (t_p(4) + t(4,6), (t_p(5) + t(5,6))}, max {(8+12), (7+9), (9+11)} = max {20,16,20} = 20. 

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

        tn(i) – поздний срок свершения события j;

         t(i,j) – продолжительность работы (i,j);

         Ui – множество работ, выходящих из события i. 

      t_n(6) = 20;

      t_n(5) = t_n(6) – t(5,6) = 20 – 11 = 9;

      t_n(4) = min {(t_n(5) – t(4,5)), (t_n(6) – t(4,6))} = min {(9 – 2), (20 – 9)} = min {7,11} = 7;

      t_n(3) = t_n(6) – t(3,6) = 20 – 12 = 8;

      t_n(2) = min {(t_n(3) – t(2,3)), (t_n(4) – t(2,4))} = min {(8 – 5), (7 – 4)} = min {3,3} = 3;

      t_n(1) = t_n(2) – t(1,2) = 3 – 3 = 0. 

   Тогда резерв времени события i равен: R(i) = tn(i) – tp(i):

                   

                              R(1) = tn(1) – t_p(1) = 0 – 0 = 0;

                              R(2) = tn(2) – t_p(2) = 3 – 3 = 0;

                              R(3) = tn(3) – t_p(3) = 8 – 8 = 0;

                              R(4) = tn(4) – t_p(4) = 7 – 7 = 0;

                              R(5) = tn(5) – t_p(5) = 9 – 9 = 0;

                              R(6) = tn(6) – t_p(6) = 20 – 20 = 0. 

                                                                                                          Таблица 5

 

      Резервы времени работы (i,j) подразделяются на полный Rn(i,j) и свободный Rc(i,j).

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

                                        Rn(i,j) = tn(j) – tp(i) – t(i,j) 

   Rn(1,2) = tn(2) – tp(1) – t(1,2) = 3 – 0 – 3 = 0;

   Rn(2,3) = tn(3) – tp(2) – t(2,3) = 8 – 3 – 5 = 0;

   Rn(2,4) = tn(4) – tp(2) – t(2,4) = 7 – 3 – 4 = 0;