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

        
        
      

      Москва, 2011 г.

             

Оглавление

ИСХОДНЫЕ ДАННЫЕ 3

ВВЕДЕНИЕ 5

1. ПОСТРОЕНИЕ СЕТЕВОГО ГРАФИКА 6

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

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

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

ЗАКЛЮЧЕНИЕ 17

СПИСОК ЛИТЕРАТУРЫ: 18 
 

 

ИСХОДНЫЕ  ДАННЫЕ 

Вариант № 10.  
 

      

  
 
 
 
 
 
 

        
 
 

Заданная  продолжительность выполнения всего  комплекса производственных работ  – 

24 суток. 

Руководитель  работы к.т.н., доцент                                      Петренко А.А.

 

ВВЕДЕНИЕ

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

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

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

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

1. ПОСТРОЕНИЕ СЕТЕВОГО ГРАФИКА

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

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

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

 

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

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

     Начальным событием-истоком  является «начало  работ», а завершающим событием – стоком – «готовность изделия». Поэтому обозначим их соответственно буквами A и F.

     Из  события A (по горизонтали) выходит одна работа-дуга, которая ведет к соответствующему событию по вертикали. Его обозначим В. Соответствующему событию по горизонтали присвоим то же имя.

     Из  события В (по горизонтали) выходят три работы-дуги, ведущие к событиям по вертикали, которые  обозначим C, D, E. Те же события по горизонтали обозначим теми же буквами. Событие «готовность документации»0 обозначим С и т.д. 

        

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

    Упорядочим  график по алгоритму Фалкерсона:

1-ый  шаг: выделяем вершины, не имеющие  "предков", и последовательно  нумеруем их в произвольном  порядке; 

2-ой  шаг: мысленно вычеркиваем из  графа все вершины, имеющие  номера, и дуги, из них выходящие;

3-ий  шаг: в получившемся графе повторяем  процедуры 1-ого и 2-ого шагов  до тех пор, пока все вершины  не будут пронумерованы. 

 

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

      

 
 
 

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