Сетевой график

Приступая к построению сетевого графика, следует установить:

1. какие работы должны быть завершены ранее, чем начнется данная работа;
2. какие работы могут быть начаты после завершения данной работы;
3. какие работы могут выполняться одновременно с данной работой.
4. Кроме того, надо придерживаться общих положений и правил:
5. сеть вычерчивается слева направо. Это же направление имеют и стрелки-работы;
6. каждое событие с большим порядковым номером изображается правее предыдущего;
7. график должен быть простым, без лишних пересечений;
8. все события, кроме завершающего, должны иметь последующую работу. В сети не должно быть события, кроме исходного, в которое не входила бы ни одна работа;
9. один и тот же номер события нельзя использовать дважды;
10. в сетевом графике ни один путь не должен проходить дважды через одно и то же событие. Если такие пути обнаружены, то это свидетельствует об ошибке;
11. если начало какой-либо работы зависит от окончания двух предшествующих работ, выходящих из одного события, тогда между событиями — окончаниями этих двух работ — вводится фиктивная работа (зависимость).

 

2.2. Сетевой график.

Путь — это цепочка следующих друг за другом работ, соединяющих начальную и конечную вершины, например, в приведенной на рис.2 модели путями являются L 1= (1, 2, 3, 5, 6, 8), L 2=(1, 2, 4, 8,) и др.

3

2

4

6

8

7

5

1

Рис.1.  Сетевая  модель.

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

1. События правильно занумерованы, т. е. для каждой работы (i,j) i <j. При невыполнении этого требования необходимо использовать алгоритм перенумерации событий;
2. Отсутствуют тупиковые (кроме завершающего) события, т.е. такие, за которыми не следует хотя бы одна работа.
3. Отсутствуют (за исключением исходного) события, которым не предшествует хотя бы одна работа.
4. Отсутствуют циклы, т. е. замкнутые пути, соединяющие событие с ним же самим.

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

Расчет  временных характеристик проекта

Основными задачами сетевого анализа являются календарное планирование и оперативный контроль сроков начала и завершения выполнения отдельных работ и этапов проекта с использованием его сетевой модели. Для этого предварительно выполняется расчет двух групп временных характеристик проекта – параметров свершения событий и параметров выполнения работ. К первой группе относятся: 1) ранние сроки свершения событий; 2) поздние сроки свершения событий; 3) резервы событий; 4) продолжительность критического пути. Ко второй группе относятся: 1) ранние сроки начала и окончания работ; 2) поздние сроки начала и окончания работ; 3) резервы работ (полный резерв, свободный резерв, частный резерв первого рода, частный резерв второго рода).

Ранний срок свершения события – это наиболее раннее время свершения данного события относительно начала выполнения комплекса работ. Ранний срок свершения события (t_pj) численно равен величине наиболее длительного отрезка пути от исходного до рассматриваемого события, причем для начального события сети  t_p (1) = 0, а для каждого последующего события по порядку выбирается максимум по всем его предкам t_p (N) = t_Kp(L):

t_p (j) = max{ t_p (i) + t(i,j)}.                                      (1)

                                                          i

Результаты расчетов сводятся в таблицу. Форма которой представлена ниже (таблица 1).

Поздний срок свершения события "i" характеризует самый поздний допустимый срок, к которому должно свершиться событие, не вызывая при этом срыва срока свершения конечного события:

t_п (j) = max{ t_п (j) + t(i,j)}.                                              (2)

                       i

Этот показатель определяется "обратным ходом", начиная с  завершающего события, с учетом соотношения  t_п (N) = t_p (N)

Все события, за исключением  событий, принадлежащих критическому пути, имеют резерв R (i):

R (i) = t_п (i) - t_p (i)

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

Для всех работ (i,j) на основе ранних и поздних сроков свершения событий можно определить показатели:

Ранний срок начала            t_рн (i,j)= t_p (i)                                             (4)

Ранний срок окончания   t_ро (i,j)= t_p (i)+t(i,j)                                (5)      

Поздний срок окончания  t_по (i,j)= t_п (j)                                          (6)

Поздний срок начала t_пн (i,j)= t_п (i)-t(i,j)                                            (7)

Полный резерв времени   R_п (i,j)= t_п (j)- t_p (i) - t(i,j)                     (8)

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

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

Перечисленные выше характеристики СМ могут быть получены на основе приведенных аналитических формул, а процесс вычислений отображен либо непосредственно на графике, либо в матрице (размером N на N), либо в таблице.

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

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

В 1 графе поставим число, характеризующее количество непосредственно предшествующих работ (Кпр) тому событию, с которого начинается рассматриваемая работа. Для работ, начинающихся с номера "1", предшествующих работ нет. Для работы, начинающейся на номер "К", просматриваются все верхние строчки второй графы таблицы и отыскиваются строки, оканчивающиеся на этот номер. Количество найденных работ записывается во все строчки, начинающиеся с номера "К". Например, для работы (5, 6) в гр. 1 поставим цифру "3", так как в гр. 2 на номер 5 оканчиваются три работы: (2, 5); (3, 5) и (4, 5).

 Заполнение таблицы  начинается с раннего срока  начала работ. Для работ, имеющих  цифру "ноль" в гр. 1, в гр. 4 также заносятся нули, а их  значение в гр. 5 получаются в  результате суммирования гр. 3 и  4 (см. формулу 4). В нашем случае  таких работ только одна —  (1, 2), поэтому в гр. 4 в соответствующей  ей строке проставим "0", а  в гр. 5 — 10 + 0 = 10.

Таблица 1.

Расчет основных показателей  сетевого графика.

Кпр	(i, j)	t(i, j)	tрн(i, j) =  =tр   (j)	tpo(i, j)	tпн(i, j)	tпо(i, j)= =tп(j)	Rп	kн
1	2	3	4	5 (4+3)	6 (7-3)	7	8	9
1	(1-2)	10	0	10	0	10	0	1
1	(1-3)	7	0	7	5	12	5	0,6
1	(2-4)	6	10	16	10	16	0	1
1	(3-4)	4	7	11	12	16	5	0,6
1	(4-5)	13	16	29	16	29	0	0,6
1	(4-6)	3	16	19	24	27	8	0,1
1	(4-7)	19	16	35	16	35	0	1
3	(5-7)	6	29	35	29	35	0	1,2
1	(6-7)	8	14	22	27	35	13	0,7
1	(6-8)	12	14	26	30	42	16	0,6
1	(7-8)	7	35	42	35	42	0	1

 

 

 

 

 

 

 

 

 

 

 

Для заполнения следующих  строк гр. 4, т. е. строк, начинающихся с номера 2, просматриваются заполненные строки гр. 5, содержащие работы, которые оканчиваются на этот номер, и максимальное значение переносится в гр. 4 обрабатываемых строк. В данном случае такая работа лишь одна (1, 2), о чем можно судить по гр. 1. Цифру "10" из гр. 5 переносим в гр. 4 для всех работ, начинающихся с номера 2, т.е. в три последующих строки с номерами (2, 3), (2, 4), (2, 5). Далее для каждой из этих работ путем суммирования их значений граф 3 и 4 сформируем значение гр.5:

tpo (2,3) = 7 + 10 = 17,

tpo (2, 4) = 6 + 10 = 16,

tpo (2, 5) = 3 + 10 = 13.

Этот процесс повторяется  до тех пор, пока не будет заполнена  последняя строка таблицы.

Графы 7 и 6 заполняются "обратным ходом", т. е. снизу вверх. Для этого  просматриваются строки, оканчивающиеся на номер последнего события, и из гр. 5 выбирается макс. величина, которая записывается в гр. 7 по всем строчкам, оканчивающимся на номер последнего события (см. формулу t_n(N) = t_p(N)). В нашем случае t(N) = 56. Затем для этих строчек находится содержание гр. 6 как разность между 7 и 3 графами (см. формулу 7). Имеем: t_po (7, 8) = 56 - 4 = 52.

Далее просматриваются строки, оканчивающиеся на номер события, которое предшествует завершающему событию (8). Для определения гр. 7 этих строк (работы (4-7), (6-8), (7-8), просматриваются все лежащие ниже строчки гр. 6, начинающиеся с номера 8.

В гр. 6 среди них выбирается минимальная величина, которая переносится в гр. 7 по обрабатываемым строчкам. В нашем случае она одна (7, 8), поэтому заносим во все строки указанных работ цифру "56". Процесс повторяется до тех пор, пока не будут заполнены все строки по графам 6 и 7.

Содержимое гр.8 равно разности граф 6 и 4 или граф 7 и 5 (см. фор-лу 3).

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

L_кр=(l,2,3,5,6,8),   а t_кр= 52 дня.

 

2.3. Оптимизация.

 

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

                                     

 

                                     t(L_max) – t´кр                   R_п(i,j)

                    Кн (i,j) =                               = 1 -

                                             t_кр - t´_кр                    t_кр - t´_кр

 

где t(L_max) - продолжительность максимального пути, проходящего через работу (i,j);

t'_кр - продолжительность отрезка рассматриваемого пути, совпадающая с критическим путем.

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

1. напряженные (К_н (i,j)> 0,8);
2. подкритические (0,6 < K_н(i,j) < 0,8);
3. резервные (K_н (i,j) < 0,6).

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

При расчете этих показателей целесообразно пользоваться графиком СМ. Итак, для работ критического пути (1-2), (2-4), (4-7), (7-8) К_н =1.

 

= 0,6.                     К = 0,6

 

= 0,6.                      К = 0,11

 

= 1,2.                        К = 0,7

 

К = 0,6

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

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

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

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

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

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