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

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

Московский государственный индустриальный университет

Институт дистанционного образования (ГОУ ИДО МГИУ)

КУРСОВАЯ РАБОТА

по дисциплине «Экономико-математическое моделирование».

На тему «Сетевое планирование и управление»

Выполнила:

студентка

группы 01Э31П

Фаттахова Г. М.

Проверил:

Смирнов Г. Б.

Москва 2006 г.

Содержание

Введение

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

2.  Анализ сетевого графика

3.  Способы оптимизации сетевого графика

Заключение

Список использованных источников

Введение

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

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

планировать размещение оборудования, рассчитывать требуемые площади и строить помещения;

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

набирать и готовить кадры будущих работников.

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

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

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

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

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

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

Для отображения процесса выполнения проекта и управления им в системах СПУ используется сетевая модель.

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

Система сетевого планирования и управления (СПУ) – система, применяемая в строительстве, в управлении крупными научно-техническими разработками и другими комплексами работ, основанная на использовании ЭВМ и сетевых графиков.

Системы СПУ можно характеризовать следующими признаками, определяющими структуру, основные принципы построения и функционирования СПУ, объемы информации, методы и технические средства ее сбора, передачи, переработки и отображения:

а) уровень руководства, использующий данную систему СПУ;

б) количество сетей, описывающих проект;

в) число конечных целей проекта;

д) ограничения по ресурсам;

е) планируемые и контролируемые параметры проекта.

На практике структура систем СПУ обусловлена необходимостью выполнения основных процессов управления, получения информации о состоянии проекта (комплекса работ), преобразования информации, формирования команд управления, передачи и исполнения команд управления.

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

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

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

Сетевые графики составляются на начальном этапе планирования. Главными элементами сетевой модели являются события и работы.

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

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

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

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

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

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

Если на ребре указано направление связи между вершинами, то оно называется дугой. Ориентация дуги указывается стрелками. Дуга, соединяющая вершину i с вершиной j, обозначается символом (i, j) или pij.

Если все соединения в графе изображаются дугами, то граф называется ориентированным, или орграфом.

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

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

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

Вершина, в которую дуги только входят, но не выходят, называется стоком.

Любой путь в сетевом графике от истока к стоку называется полным.

Если дугам (ребрам) графа сопоставлены какие-то числовые характеристики – весами.

Вершина хi («предок») предшествует в графе вершине хj («потомок»), если существует путь из хi в хj .

Граф является упорядоченным, если в нем порядковый номер «предка» всегда меньше порядкового номера «потомка».

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

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

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

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

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

Сетевой график – это связанный взвешенный орграф без контуров (петель).

На изображении комплекса работ с помощью сетевого графика основано сетевое планирование и управление (СПУ).

События обозначаются на сетевом графике вершинами.

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

- определение начального и конечного событий;

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

- составление списка работ, соединяющих намеченные события;

- определение продолжительности выполнения каждой работы.

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

график должен иметь только одно начальное событие (исток) и только одно конечное событие (сток);

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

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

график должен быть упорядоченным;

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

в сетевом графике не должно быть «хвостовых» событий, кроме, исходного (начального), которым не предшествует хотя бы одна работа;

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

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

В случае нарушения условия 1 или 8 рекомендуется ввести фиктивное событие и фиктивную работу. Последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом следующей, называется путем. Любой путь от начальной вершины (истока) к конечной вершине (стоку) называется полным. Если дугам графа сопоставлены какие-то числовые характеристики, то граф называется взвешенным, а числовые характеристики – весами.

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

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

Задача. Построить сетевой график выполнения работ:

упорядочить построенный график;

отметить весами работы построенного графика;

определить полные пути для нормального и ускоренного срока выполнения работ;

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

Таблица 1

Cобытия (потомки) Cобытия (предки) Начало работ Готовность деталей Готовность документации Поступление дополнительного оборудования Готовность блоков Готовность деталей Изготовление деталей (4/3) Готовность документации Подготовка документации (5/2) Установка дополнительного оборудования (12/6) Составление инструкций (11/6) Поступление дополнительного оборудования Закупка дополнительного оборудования (10/5) Готовность блоков Сборка блоков (6/4) Готовность изделия Компоновка изделия (9/6)

Решение.

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

2. Анализ сетевого графика

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

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

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

Полные пути и их продолжительности:

1 – 2 - 4 – 5 – 6 → 4/3 + 6/4 + 11/6 + 9/6 = 30/19

1 – 2 – 5 – 6 → 4/3 + 5/2 + 9/6 = 18/11

1 – 3 – 5 – 6 → 10/5 + 12/6 + 9/6 = 31/17

Нахождение критического пути.

Путь 1 – 3 – 5 – 6 – наиболее продолжительный из полных путей называется критическим.

31/17 – это минимальное время выполнения работ для достижения поставленной задачи является критическим сроком и обозначается tкр. Работа и события, лежащие на критическом пути, называют критическими.

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

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

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

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

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

tp(j) = max t (Lnj),

где t (Lnj) – любой путь, предшествующий j-му событию, т.е. путь от исходного до j-го события сети. Если событие имеет несколько предшествующих путей, а следовательно несколько предшествующих событий i, то для оценки раннего срока совершения j-го события следует выбирать максимальный из предшествующих путей,

tp(j) = maxi,j [tp (i) + t (i, j)].

Расчет раннего срока наступления событий для примера на рис. 1.

tp1 = 0;

tp2 = tp1 + t (1, 2) = 0 + 4= 4;

tp3 = tp1 + t (1, 3) = 0 + 10 = 10;

tp4 = tp2 + t (2, 4) = 4 + 6 = 10;

tp5 = max [ tp4 + t (4, 5); tp2 + t (2, 5); tp3 + t (3; 5)] = max [(10 + 11); (4 + 5); (10 + 12)] = [21; 9; 22] = 22;

tp6 = tp5 + t (5; 6) = 22 + 9 = 31

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

Поэтому поздний (или предельный) срок tp(j) свершения j-го события равен:

tp(j) = tкр – max t(Lnj)

где Lnj – любой путь следующий за j-м событием, т.е. путь от j-го до завершающего события сети.

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

tp(j) = min j,i [ tn(i) – t(j, i)].

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

tn6 = tкр = 31;

tn5 = tn6 – t (5, 6) = 31 – 9 = 22;

tn4 = tn5 – t (4, 5) = 22 – 11 = 11;

tn3 = tn5 – t (3, 5) = 22 – 12 = 10;

tn2 = min [tn4 – t (2, 4); tn5 – t (2, 5)] = [(11 – 6); (22 – 5)] = [5, 17] = 5;

tn1 = min [tn2 – t (1, 2); tn3 – t (1, 3)] = [(5 – 4); (10 – 10)] = [1, 0] = 0;

Определение резерва времени события.

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

R(j) = tn(j) – tp(j).

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

Rпол(i, j) = tn(j) – tp(i) - t(i, j). Для этого примера

Rп (2, 5) = tп (5) - tр (2) - t(2, 5) = 22 – 4 – 5 = 13;

Rп (4, 5) = tп (5) - tр (4) - t(4,5) = 22 – 10 – 11 = 1;