Построение сетевого графика
Основные правила
На сетевом графике каждая работа изображается в
виде дуги графа, т.е. стрелки, содержащей две вершины, представляющие собой события, соответствующие началу и окончанию работы, как показано на рис, а. Начало и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями.
(i,j) A=(1,2)
объединение работ (б) и расчленение работ (в)
Сетевой моделью для исходного проекта называется графический образ исходного проекта в виде графа, т.е. набора вершин и направленных дуг (операций), который содержит все операции, имеющиеся в проекте.
Пример
Событие, не имеющее предшествующих ему событий, т.е.
с которого начинается проект, называют исходным. Событие, которое не имеет последующих событий и отражает конечную цель проекта, называется завершающим
длина стрелки не зависит от времени выполнения работы
стрелка не обязательно должна представлять прямолинейный отрезок;
для действительных работ используются сплошные линии, а для фиктивных - пунктирные стрелки;
каждая операция должна быть представлена только одной стрелкой;
не должно быть параллельных работ между одними и теми же событиями, для избежания такой ситуации используют фиктивные работы;
следует избегать пересечения стрелок;
не должно быть стрелок, направленных справа налево;
номер начального события должен быть меньше номера конечного события;
не должно быть висячих событий, кроме исходного;
не должно быть тупиковых событий, кроме завершающего;
не должно быть циклов.
Перед построением сетевого графика
Какие работы должны непосредственно следовать после завершения данной работы?
Какие операции могут выполняться одновременно с рассматриваемой работой?
Какие работы необходимо завершить непосредственно перед началом рассматриваемой работы?
Фиктивная работа. Ни одна пара работ не может отображаться в сетевой модели одной парой событий. Графически такая ситуация для операции А, В невозможна:
A
B
Рис.3
Например, из условий задачи, в которой присутствует работы A, B, C, D известно, что работы А, В предшествуют операции D, а операции C предшествует только операция A
Построение сетевого графика. Обозначим работы через события, соответствующие им. Событие, означающее начало комплекса работ обозначим – 0, работа С завершается событием 1, работа D – событием 2, работа А – событием 3, работа Е – событием 4 и т.д. Тогда работа С представляется (0,1), работа D – (0,2), работа А – (0,3), работа Е – (0,4), работа H – (1,6), работа B – (3,7), работа F – (4,5), работа G – (5,8), работа I – (8,9).
Построение начинается с критического пути LKP в соответствии с табл.3, который изображается двойными стрелками. Он включает в себя критические работы
=
.
Исходное событие обозначаем - 0, в этот момент начинаются работы A, C, D, E.
№ работы |
Средства bij (у.е.) |
Длитель ность |
Непосред. предшест. работы |
Непосред. следующ. работы |
|
|
Резерв времени
|
Раннее начало работы |
D |
2 |
1 |
- |
B, F |
1 |
2 |
1 |
0 |
C |
13 |
1 |
- |
B, H |
1 |
5 |
4 |
0 |
E |
5 |
2 |
- |
F |
2 |
2 |
0 |
0 |
A |
5 |
1 |
- |
B |
1 |
5 |
4 |
0 |
F |
2 |
3 |
D, E |
G |
5 |
5 |
0 |
2 |
B |
12 |
4 |
A, C, D |
I |
5 |
9 |
4 |
1 |
G |
5 |
4 |
F |
I |
9 |
9 |
0 |
5 |
H |
1 |
1 |
C |
- |
2 |
14 |
12 |
1 |
I |
4 |
5 |
B, G |
- |
14 |
14 |
0 |
9 |
Табл.3
Рис. 9
Анализ сетевых моделей. Анализ сетевой модели проводим с целью выявления резервов и «узких мест».
Анализ сетевой модели рис. 9 начинаем с определения времени выполнения всего комплекса работ. Для этой цели проследим все возможные пути перехода из исходного события (0) к завершающему (9). Таких путей шесть:
Общий срок выполнения проекта будет определяться путем максимальной продолжительности, называемым критическим:
.
Длительность пути L2, составляющая t(L2) = 2 мес., минимальна, однако не позволяет выполнить все работы комплекса.
Теперь определим резервы времени по всем путям:
Наиболее напряженными являются работы критического пути L1 которые не имеют резервов и поэтому являются «узкими местами» комплекса работ.
Наличие резервов
позволяет
провести оптимизацию сетевого графика
Для этого определим работы, обладающие свободным резервом времени - максимальным временем, на которое можно отсрочить начало или увеличить продолжительность работы при условии, что все события сети наступают в свои ранние сроки
,
где - работа, непосредственно следующая за -й работой
Согласно табл.3 и рис. 1 такими работами являются:
- работа D,
имеющая свободный резерв, равный
мес.;
- работа В,
имеющая свободный резерв
мес.;
- работа Н,
имеющая свободный резерв
мес.
Оптимизация
сетевой модели.
Сетевой
график работ составлен таким образом,
что
все ресурсы (средства)
,
отпускаемые на каждую работу
,
будут полностью
израсходованы.
Оптимальным
сетевым планом
будет
такой план, когда
получится
наименьшим из всех возможных
в данных условиях. Очевидно, новые
длительности всех путей
в таком случае будут равны, т.е.
.
Механизм
перераспределения
средств включает уменьшение средств
части некритических работ
на некоторую величину
что приводит,
естественно, к увеличению времени ее
выполнения. *
.
Средства
,
вложенные
в другую работу
,
приводят
к уменьшению времени ее выполнения:
.
Продолжительность выполнения работ зависит от объема выделенных ресурсов, работает формула «время - деньги»
Сумма средств, снимаемых с работ , должна быть равна сумме средств, передаваемых работам (h,k):
где М - множество работ, с которых средства снимались; N - множество работ, на которые средства переносились.
В
процессе перераспределения средств
необходимо соблюдать
ограничение на величину снимаемых
средств
с работы
,
которое определяется наличием свободного
резерва времени
у этой работы, и определяется формулой
и, следовательно, удовлетворять условию
.
Увеличение продолжительности некритической работы не должно превосходить свободного резерва времени этой работы.
Перед началом оптимизации расположим длительности всех путей последовательно в порядке увеличения их резервов.
На
первом этапе
оптимизации
выбираем ближайший к критическому
пути L1
-
14
мес, путь L4
= 13
мес. На этом пути L4
некритическая
работа D=(0,2)
имеет свободный резерв времени
мес.
Условие допустимости решения по величине
переносимых средств определяется
выражением
.
Перенесем часть средств работы (0,2) на работу Е=(0,4) критического пути.
Замечание. Переносить средства с работы одного пути, например (0,2) пути L4, на любую работу, даже и критическую, но входящую в этот же путь L4, нельзя.
Величину
переносимых средств и длительности
новых равных
критических путей
можно найти, составив и решив
следующую систему уравнений:
При
система имеет следующее решение
.
Найдя величину переносимых средств, проверяем допустимость такого решения по ограничению
.
Если оно недопустимо, то переносим средства на любую другую работу; опять составляем новую систему уравнений и таким образом продолжаем оптимизацию.
Новые длительности работ (0,2) и (0,4) находим по формулам
Длительности новых критических путей определяем из выражения:
мес.
При
этом длительность пятого пути увеличилась
и стала равной
мес.
На втором этапе рассматриваем следующий ближайший некритический путь
длительностью мес., на котором у работы В=(3,7) имеется свободный резерв времени .
Переносим
часть средств
работы (3,7)
на работу
=(5,
8)
для сокращения времени выполнения работ
первого и
пятого путей. Для нахождения величин
переносимых средств
составим систему уравнений:
При
система имеет
следующее решение
.
Определив величину переносимых средств, проверяем допустимость такого решения по ограничению
.
Если оно недопустимо, то переносим средства на любую другую работу; опять составляем новую систему уравнений и таким образом продолжаем оптимизацию.
Новые длительности работ (3,7) и (5,8) находим по формулам
Длительности новых критических путей определяем из выражения:
мес.
Теперь три пути от исходного события к завершающему стали критическими и равными. Выбирается ближайший по длительности к ним некритический путь и повторяется процедура переноса средств с работы, имеющей свободный резерв времени, на критическую работу (или работы) критических путей.
Конечным результатом выполняемых на сетевой модели расчетов является календарный график, который иногда называют графиком привязки.
Календарный график отображает взаимосвязь выполняемых работ во времени и строится на основе данных о ранних сроках начала и окончания работ. Для удобства дальнейшей работы на этом графике могут быть указаны величины полных и свободных резервов работ. По вертикальной оси графика привязки откладываются виды работ, по горизонтальной оси - длительность работ (раннее начало и раннее окончание работ).
Календарный график можно построить без предварительного расчета ранних сроков начала и окончания всех работ, используя только данные о продолжительности работ. При этом необходимо помнить, что работа k может начать выполняться только после того как будут выполнены все предшествующие ей работы.
Обозначим работы через события, соответствующие им. Событие, означающее начало комплекса обозначим – 0, работа С завершается событием 1, работа D – событием 2, работа А – событием 3, работа Е – событием 4 и т.д. Тогда работа С представляется (0,1), работа D – (0,2), работа А – (0,3), работа Е – (0,4), работа H – (1,6), работа B – (3,7), работа F – (4,5), работа G – (5,8), работа I – (8,9).
Построим календарный график для следующих исходных данных.
№ работы |
|
|
Количество исполнителей в месяц |
D |
0,2 |
1 |
20 |
C |
0,1 |
1 |
20 |
E |
0,4 |
2 |
4 |
A |
0,3 |
1 |
8 |
F |
4,5 |
3 |
16 |
B |
3,7 |
4 |
13 |
G |
5,8 |
4 |
5 |
H |
1,6 |
1 |
4 |
I |
8,9 |
5 |
5 |
Практическая ценность графика заключается в том, что с его помощью можно улучшать эффективность использования ресурса рабочей силы, т.е. проводить оптимизацию сетевой модели.
На календарном графике на горизонтальной оси откладывается время, например в днях, по вертикальной - количество человек, занятых работой в каждый конкретный день. Кроме календарного графика для проведения оптимизационных операций необходим график загрузки.
Для построения графика загрузки необходимо:
на календарном графике над каждой работой написать количество ее исполнителей;
подсчитать количество работающих в каждый месяц исполнителей и отложить на графике загрузки.
Для удобства построения и анализа, графики загрузки и привязки следует располагать один над другим.
Вид работы |
Код работы |
График выполнения по месяцам |
|||||||||||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I |
8,9 |
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
G |
5,8 |
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
F |
4,5 |
|
|
|
16 |
|
|
|
|
|
|
|
|
|
|
|
|
B |
3,7 |
|
13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
H |
1,6 |
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
E |
0,4 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A |
0,3 |
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
D |
0,2 |
20 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C |
0,1 |
20 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
График выполнения по месяцам |
|||||||||||||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
||||
60 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
50 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
40 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
30 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
20 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||