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

 
 
 

2. АНАЛИЗ  СЕТЕВОГО ГРАФИКА

 

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

     Полными путями будут:

путь  1-2-3-4-6

путь  1-2-4-6

путь 1-2-5-6

     Рассчитаем  продолжительность путей в нормальном режиме:

4+5+11+12=32

4+10+12=26

4+6+9=19

     Рассчитаем  продолжительность путей в ускоренном режиме:

3+2+6+6=17

3+5+6=14

3+4+6=13

      Рассчитаем  продолжительность путей в оптимальном  режиме:

3+2+11+8=24

3+10+8=21

3+6+9=18

     Критическим путем будет путь 1-2-3-4-6. Его продолжительность при нормальном режиме составит 32 суток, а при ускоренном режиме – 17 суток. Максимальный срок завершения всей совокупности работ составит 32 суток, а минимальный – 17 суток. Требуется довести продолжительность работ при нормальном режиме с 32 до 24 суток, а при ускоренном режиме с 17 суток до 24 суток. 

        

 

3. ОПТИМИЗАЦИЯ СЕТЕВОГО ГРАФИКА

 

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

     Оптимизация сетевого графика может осуществляться по следующим двум критериям:

1. минимизация времени выполнения комплекса работ при заданных затратах на это выполнение;
2. минимизация затрат на выполнение комплекса работ при заданном времени этого выполнения.

     Целью оптимизации является сокращение времени  выполнения проекта в целом. Нельзя добиться выполнения комплекса работ  одновременно в минимальные сроки  и с наименьшими затратами.

     Оптимизацию можно провести двумя способами:

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

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

        

     На  первом шаге рассматривается работа 2-3, которая входит в первый путь, сокращаем её продолжительность на 3 суток. Увеличение затрат составит 3·10=30 у.е. На втором шаге рассматривается работа 2-4, которая входит во второй путь, пропускаем этот шаг. На третьем шаге рассматривается работа 1-2, сокращаем её продолжительность на 1 сутки. Увеличение затрат составит 1·20=20 у.е. На пятом шаге рассматривается работа 4-6, сокращаем её продолжительность на 4 суток. Увеличение затрат составит 4·30=120 у.е. Четвертый, шестой и седьмой шаги не используются. Прирост затрат на сокращение продолжительности работ составляет 170 у.е. Складываем его с первоначальной стоимостью всего комплекса работ 1060 + 170 = 1230 у.е.

      Представим  решение задачи вторым способом в  таблице:

        

     На  первом шаге продолжительность работы 5-6 может быть увеличена на 3 суток. Тогда затраты на эту работу, с  более поздним сроком выполнения, снизятся на 3·40=120 у.е. На втором шаге продолжительность  работы 3-4 увеличиваем на 5 суток. Затраты снижаются на 5·35=175 у.е. На третьем шаге увеличиваем продолжительность работы 4-6 на 2 суток. Это снизит затраты на 2·30=60 у.е. На четвертом шаге увеличиваем продолжительность работы на 2 суток. Затраты снижаются на 2·25=50 у.е. На шестом шаге увеличиваем продолжительность работ на 5 суток. Затраты снижаются на 5·15=75 у.е.  Пятый и седьмой шаги не используем. Суммарное снижение затрат из-за произведенного увеличения продолжительностей работ составит -480 у.е. Суммируем снижение затрат и первоначальную стоимость работ в ускоренном режиме  1710+(-480)=1230 у.е.

     Стоимости выполнения всего комплекса работ  после оптимизации совпадают  – 1230 у.е. Также совпадают полные  пути после оптимизации: 24,21,18 . 

4. РАСЧЕТ  ПАРАМЕТРОВ ОПТИМИЗИРОВАННОГО  СЕТЕВОГО ГРАФИКА

 

     Рассчитываем  ранний срок свершения событий:

Ранний  срок свершения события – это ранний срок, необходимый для выполнения всех работ, предшествующих данному событию. 

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+2=5

t_p(4) =max{ t_p(2)+t(2,4); t_p(3)+t(3,4)}=max{3+10;5+11}=max{13,16}=16

t_p(5) = t_p(2) + t(2,5) =3+6=9

t_p(6) =max{ t_p(4)+t(4,6); t_p(5)+t(5,6) =max{16+8;9+9}=max{24,18}=24 

     Рассчитываем  поздний срок свершения событий:

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

t_n(6) = 24

t_n(5) = t_n(6) – t(5,6) = 24–9=15

t_n(4) = t_n(6) – t(4,6) = 24–8=16

t_n(3) = t_n(4) – t(3,4) = 16–11=5

t_n(2) = min{t_n(3) –t(2,3); t_n(4) - t(2,4); t_n(5) - t(2,5)}=min{5-2;16-10;15-                   -6}=min{3,6,9}=3

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

      Далее рассчитываем резерв времени событий: 

_{R1 =  tn(1) – tp(1) = 0 – 0 = 0}

_{R2 = tn(2) – tp(2) = 3 – 3 = 0}

R₃ = tn(3) – tp(3) = 5 – 5 = 0

R₄ = tn(4) – tp(4) = 16 – 16 = 0

R₅ = tn(5) – tp(5) = 15 – 9 = 6

R₆ = tn(6) – tp(6) = 24 – 24 = 0 

     Полученные  данные представлены в виде таблицы: 

        

Получаем  новый сетевой график:

     

     Рассчитаем  полный резерв времени работы:

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

 

R_n(1,2) = t_n(2)-t_p(1)-t(1,2) = 3-0-3=0

R_n(2,3) = t_n(3)-t_p(2)-t(2,3) = 5-3-2=0