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

Слайд 1

Слайд 2

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

Слайд 3

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

Слайд 4

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

Слайд 5

Последовательность повторяющихся ребер, ведущая от некоторой вершины к другой, образует путь Дерево представляет собой связный граф без циклов, имеющий исходную вершину (корень) и крайние вершины; пути от исходной вершины к крайним вершинам называются ветвями. Сеть - это ориентированный конечный связный граф, имеющий начальную вершину (источник) и конечную вершину (сток). Таким образом, сетевая модель представляет собой граф вида «сеть».

Слайд 6

Элементы сетевой модели События: исходное (начальное), завершающее (конечное) Работы : действительная работа; ожидание; фиктивная работа (зависимость) Путь : полный путь, критический путь

Слайд 7

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

Слайд 8

Событие - это итог проведенных работ, который дает начало для дальнейших (последующих) работ. Событие не имеет продолжительности во времени. Событие, за которым начинается данная работа, называется начальным для данной работы; оно обозначается символом i . Событие, которое наступает после выполнения данной работы, называется конечным для данной работы; оно обозначается символом j . В каждой сети имеются два крайних события - исходное и завершающее. Исходным называется событие в сети, не имеющее предшествующих событий и отражающее начало выполнения всего комплекса работ. Оно обозначается символом I . Завершающим называется событие, которое не имеет последующих событий и показывает достижение конечной цели выполнения комплекса работ. Оно обозначается символом К. В одно и то же событие может входить и выходить из него несколько видов работ.

Слайд 9

Путь - это любая последовательность работ в сетевом графике, в котором конечное событие каждой работы совпадает с начальным событием следующей за ней работы. Если известна продолжительность каждой работы tij , то для каждого пути может быть вычислена его общее время выполнения - длина, т. е. общая сумма продолжительности всех работ пути ТLi . В сетевом графике следует различать несколько видов путей: v полный путь - путь от исходного события до завершающего; v полный путь с максимальной продолжительностью называется критическим путем Lкр ; v путь, предшествующий данному событию, - путь от исходного события до данного; v путь, следующий за данным событием, - путь от данного события до завершающего; v путь между событиями i и j ; v подкритический путь - полный путь, ближайший по длительности к критическому пути; v ненагруженный путь - полный путь, длительность которого значительно меньше длительности критического пути. Продолжительность пути определяется суммой продолжительностей составляющих его работ. Например, t (L1) =t (1,2)+ t (2,3)+ t (3,4)+ t (4,7)=2+4+6+11=23, t (L2)=28, t (L3)=37.

Слайд 10

Сетевая модель на рисунке 1 состоит из 7 событий и 8 работ, продолжительность выполнения которых указана под работами. Правила построения сетевого графика А 2 Б 4 В 6 10 Ж Г 11 З 15 8 Е Д 3 1 2 5 6 3 4 7

Слайд 11

1. Если работы А, Б, В выполняются последовательно, то на сетевом графике они изображаются по горизонтали одна за другой 1 2 3 4 А Б В 2.Если результат работы А необходим для выполнения работ Б и В, то на сетевом графике это изображается следующим образом

Слайд 12

3.Если результат работ А и Б необходим для выполнения работы В, то на сетевом графике это изображается следующим образом 1 2 3 4 А Б В 4.Работы сетевого графика не должны иметь одинакового кода Если работы А 1 , А 2 ,..., А п выходят из одного события и их выполнение необходимо для свершения одного и того же события, то вводятся дополнительные фиктивные работы. 1 2 А 2 А 3 А 1 1 2 3 4 А 1 А 2 А 3

Слайд 13

5. Если работы Б, В, Г начинаются после частичного выполнения работы А, то работа А разбивается на части: А 1 , А 2 , А 3 и т.д., при этом каждая часть работы А в сетевом графике считается самостоятельной работой. А 1 А 2 А 3 А 4 Б В Г 1 2 4 6 8 3 5 7 6. Если для начала работы В необходимо выполнение работ А и Б, а для начала работы Г  выполнение работы А, то в сетевой график вводится дополнительная фиктивная работа. 1 3 5 6 2 4 А Г Б В

Слайд 14

7. Если после окончания работы А можно начать работу Б, а после окончания работы В - работу Г и работа Д может быть начата только после окончания работ А и В, то на сетевом графике это изображается при помощи двух дополнительных фиктивных работ . 1 3 6 7 2 4 5 8 А Б Д В Г 8. В сетевом графике не должно быть замкнутых контуров. 9. События следует кодировать так, чтобы номер начального события данной работы был меньше номера конечного события.

Слайд 15

10. В одноцелевом графике не должно быть “тупиков”, т.е. таких событий, из которых не выходит ни одной работы . 1 2 3 5 4 А Г Б В Д 11. В сетевом графике не должно быть “хвостов”, т.е. событий, в которые не входит ни одной работы, если эти события не являются исходными для данного сетевого графика 1 2 3 5 4 А Г Б В Д

Слайд 16

12. При укрупнении сетевых графиков группа работ может изображаться как одна работа, если в этой группе имеется одно конечное событие и работы выполняются одним исполнителем. Продолжительность укрупненной работы равна продолжительности наибольшего пути от начального до конечного события этой группы работ б – график после укрупнения. 1 2 3 4 5 6 7 А 5 Б 2 В 2 Г 5 Д 5 Е 1 Ж 8 З 5 К(Б,В,Г,Д,Е,Ж) а – график до укрупнения; 1 2 6 7

Слайд 17

Пример 1 . Построить топологию сетевого графика, представленного в таблице 1, закодировать работы, поставить их продолжительность и определить коэффициент сложности сети. Работы, окончание которых является необходимым условием для начала рассматриваемой Рассматриваемая работа Продолжи­тельность работ, дн - - - А А,Б Б Б Б,В Г Д Д,Е,Ж Ж Ж,З А Б В Г Д Е Ж З И К Л М Н 5 7 4 8 12 11 7 5 7 8 4 4 7

Слайд 18

Решение : изображение топологии сетевого графика начинаем с исходного события и работ, выходящих из него. Работы, не имеющие предшествующих работ, должны выходить из исходного события. Это работы А, Б, В. Поставив событие после окончания работы А, вычертим работу Г. Правильное изображение работы Д достигается путем введения фиктивных работ А  , Б  . Далее изображаются работы Е, Ж, З. Работы И, К, Л, М, Н не являются условиями для выполнения других работ, и поэтому их концы сводятся в одно общее завершающее событие. 1 2 3 5 4 6 111 9 7 8 10 А Г Б В З Н Ж Е Д И К Л М А  Б  5 8 7 7 11 12 8 4 7 4 4 5 7

Слайд 19

Затем производим кодирование работ топологии сетевого графика. Для определения коэффициента сложности К сл подсчитаем число событий n , действительных (Д) и фиктивных (Ф) работ и число ожиданий (О). n =11, Д=13, Ф=6, О=0 К сл = (Д+Ф+О)/ n К сл = (13+6+0)/11=1,73

Слайд 20

В ременные параметры сетевых графиков Сетевая модель имеет ряд характеристик, которые позволяют определить степень напряженности выполнения отдельных работ, а также всего их комплекса и принять решение о перераспределении ресурсов. Ранний срок наступления события t р ( i ) - самый ранний из возможных сроков наступления события. Он равен продолжительности максимального пути от исходного события до данного. t р ( i ) = max t[L р ( i )] Например, t р (7)=19, т.к. L 1 =(1,2,4,7), L 2 =(1,3,4,7), t ( L 1 )=5+12=17  t ( L 2 )=7+12=19.

Слайд 21

Ранний срок начала работы t р.н. ( i , j ) равен продолжительности максимального пути от исходного до начального события данной работы. t р . н . ( i,j )=max t[ L n ( i )] (2.2) Например, t р.н. (7,11)=19, т.к. L 1 =(1,2,4,7), L 2 =(1,3,4,7), t ( L 1 )=5+12=17  t ( L 2 )=7+12=19. Ранний срок начала работы равен раннему сроку наступления начального события данной работы. t р.н. ( i , j ) = t р ( i ) (2.3) Ранний срок окончания работы t р.о. ( i , j ) равен сумме раннего срока начала работы и продолжительности данной работы. t р . о . ( i,j )= t р . н . ( i,j ) + t( i,j ) (2.4) Например, t р.о. (7,11)= t р.н. (7,11) + t (7,11)= 19+8=27. Поздний срок наступления события t п ( i ) равен разности между продолжительностью критического пути и продолжительностью максимального пути от данного события до завершающего. t п ( i ) =T кр - max t[L к ( i )] (2.5) Например, t п (7)=19, т.к. L 1 =(7,11), L 2 =(7,9,11), t ( L 1 )=8 > t ( L 2 )=4, t п (7) = T кр  max t [ L к (7)]=27  8=19. Для событий критического пути t р ( i )= t п ( i ), для других событий t р ( i )< t п ( i ).

Слайд 22

t п . о . ( i,j )=T кр  max t[L к (j)] (2.6) Поздний срок окончания работы равен позднему сроку наступления конечного события t п.о. ( i , j ) = t п ( j ). Например, t п.о. (4,7) = t п (7)=19. Поздний срок начала работы t п.н. ( i , j ) – самый поздний срок начала работы, при котором планируемый срок окончания проекта не меняется. t п . н . ( i,j )= t п . о . ( i,j ) - t( i,j ) (2.7) Например, t п.н. (4,7)= t п.о. (4,7) - t (4,7)=19-12=7. Для работ критического пути ранние и поздние сроки начала и окончания работ равны: t р.н. (4,7)= t п.н. (4,7)=7, t р.о. (4,7)= t п.о. (4,7)=19. Работы, не лежащие на критическом пути, могут иметь резервы времени. Полный резерв времени R п ( i , j ) – максимальное время, на которое можно увеличить продолжительность данной работы, не изменяя продолжительности критического пути. R п ( i,j )= t п (j) - t р ( i ) - t( i,j ) R п ( i,j )= t п . н ( i,j ) - t р . н . ( i,j ) (2.8) R п ( i,j )= t п . о . ( i,j ) - t р . о . ( i,j ) Свободный резерв времени R с ( i , j ) равен разности между ранним началом последующей работы и ранним окончанием рассматриваемой работы. R с ( i,j )= t р . н (j, к ) - t р . о . ( i,j ) (2.9)

Слайд 23

Расчет сетевого графика начинается с вычерчивания матрицы. В верхней строке и крайнем левом столбце записываются все события сетевого графика в порядке возрастания их номеров. В клетках ( i , j ) таблицы записываются продолжительности работ сетевого графика t ( i , j ) Справа присоединяют 2 столбца:  j и i  . Столбец  j заполняют сверху вниз, путем сложения t ( i , j ), расположенного в j - м столбце, с числами  j , вычисленными ранее и расположенными в i - й строке. Если в j -м столбце находится несколько t ( i , j ), то получается несколько  j , и в i - ю строку столбца  j записывают наибольшую  j , а в соседний столбец - номер i - й строки, по которой получается максимальное  j . Снизу к таблице присоединяют 3 строки. Строку j заполняют аналогично верхней строке. Вычисление  j проводится аналогично вычислению  j . Строка max  j - j получается путем вычитания из max  j величины  j . Затем в столбце  j и строке max  j - j по диагонали находим одинаковые числа. Они определяют цифры критических работ, события которых записаны рядом - в столбце i  и строке j .

Слайд 24

Пример 2. Определить на сетевом графике работы критического пути и его продолжительность матричным методом. i j 1 2 3 4 5 6 7 8 9 10 11  j i  1 5 7 4 0 1 2 0 8 5 1 3 0 0 7 11 7 1 4 12 7 3 5 5 7 3 6 7 1 3 2 7 0 8 19 4 8 0 0 4 14 3 9 4 19 7 10 7 14 8 11 27 7 max  j -  j 0 7 7 7 15 20 19 20 23 20 27 j  1 2 3 4 5 6 7 8 9 10 11  j 27 20 20 20 12 7 8 7 4 7 0 Таблица – Матричный метод расчета сетевого графика Критический путь (1,3), (3,4), (4,7), (7,11). Т кр =27 дней.

Слайд 25

Г рафический метод расчета параметров сетевого графика Расчеты производятся непосредственно на графике 1 2 3 4 А Б 1- номер события; 2 - ранний срок начала работы Б; 3 - поздний срок окончания работы А; 4 - номер предшествующего события, через которое к рассматриваемому идет путь максимальной продолжительности. Ранний срок начала работы находится по формуле: t р . н . (j, к )= max t р . о . ( i,j ) = max{t р . н . ( i,j )+ t( i,j )}