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

                                      

Оглавление

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

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

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

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

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

 

 

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

 

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

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

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

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

 

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

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

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

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

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

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

 

 

 

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

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

 

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

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

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

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

 

 

                                               (12)(6)

h

 

 

 

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

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

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

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

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

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

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

 

                                                                  Измененная таблица исходных данных

Работы	Нормальный вариант		Ускоренный вариант		Прирост затрат на одни сутки  ускорения
	Время  (сутки)	Затраты (у.е.)	Время  (сутки)	Затраты (у.е.)
1 – 2	4	100	3	120	20
2 – 3	10	150	5	225	15
2 – 4	6	50	4	100	25
4 – 5	5	70	2	100	10
3 – 6	12	250	6	430	30
5 – 6	11	260	6	435	35
4 – 6	9	180	6	300	40
	ВСЕГО	1060	ВСЕГО	1710

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

       

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

Расчет полных путей:

                                                                              Таблица 1а

Полные пути	Продолжительность (сутки)
	Нормальный режим	Ускоренный режим
1 – 2 – 4 – 5 – 6	4 + 6 + 5 + 11 = 26	3 + 4 + 2 + 6 = 15
1 – 2 – 4 – 6	40 + 6 + 9 = 19	3 + 4 + 6 = 13
1 – 2 – 3 – 6	4 + 10 + 12 = 26	3 + 5 + 6 = 14

 

        Проведем анализ сетевого графика:

                                                                                       Таблица 1б

Полные пути	Продолжительность (сутки)
	Нормальный режим	Ускоренный режим
1 – 2 – 4 – 5 – 6	26	15
1 – 2 – 4 – 6	19	13
1 – 2 – 3 – 6	26	14

 

В нормальном режиме у  нас 3 полных пути и два критических: – 2 – 4 – 5 – 6 и 1 – 2 – 3 – 6. В ускоренном – 3 полных пути и один критический: 1 – 2 – 4 – 5 – 6. Продолжительность работ в нормальном режиме по критическим путям – 26 суток, а в ускоренном – 15. Требуется довести продолжительность работ при нормальном режиме с 26 до 20 суток, а при ускоренном режиме с 15 до 20 суток.

3. Оптимизация  сетевого графика

 

После расчета сетевого графика любым из указанных способов его анализируют. Корректировку сетевого графика называют оптимизацией сетевого графика.

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

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

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

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

Исходными данными для  проведения оптимизации являются:

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

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

 

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

Представим алгоритм решения поставленной оптимизационной  задачи первым способом (нормальный вариант  выполнения комплекса работ) в таблице:

Таблица 2

№ шага	Суточный прирост затрат	Работа	Количество сокращаемых  суток	Продолжительность полного  пути			Общий прирост затрат
				1-2-3-6	1-2-4-6	1-2-4-5-6
0	-	-	-	26	19	26	-
1	10	4 – 5	(3) 3	-	-	23	30
2	15	2 – 3	(5) 5	21	-	-	75
3	20	1 – 2	(1) 1	20	18	22	20
4	25	2 – 4	(2) 2	-	16	20	50
5	30	3 – 6	(6)	-	-	-	-
6	35	5 – 6	(5)	-	-	-	-
7	40	4 – 6	(3)	-	-	-	-
Всего							175