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

 
 

      Москва, 2011 г.

      

                                           

     Оглавление 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Исходные  данные 

Вариант № 26 

 
 

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

20 суток.

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

Введение 

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

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

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

     Для достижения цели ставятся следующие  задач:

• на основании исходных данных по комплексу производственных работ построить сетевой график;
• провести анализ сетевого графика;
• оптимизировать сетевой  график.

 
 

1. Построение сетевого графика 

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

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

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

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

Подготовка  исходных данных для построения сетевого графика включает:

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

     При построении сетевого графика для СПУ должны учитываться следующие четыре правила:

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

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

       
 
 

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

      Из  события 2 (по горизонтали) выходят две работы, завершающиеся в событиях (по вертикали), которые нужно обозначить по порядку числами 3 и 4. Те же события по горизонтали обозначаются тем же числами 3 и 4. 

      Из  события 3 (по горизонтали) выходит одна работа, завершающаяся в событии (по вертикали), которое уже обозначено  числом 6.

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

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

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

    

      

        
 

                                                       (12)(6)

       h 
 
 

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

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

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

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

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