Сетевые методы планирования и управления

Лекция 7. Сетевые методы планирования и управления   3.1. Постановка  задачи Система методов СПУ – система методов планирования и управления разработкой крупных народно-хозяйственных комплексов, научными исследованиями, конструкторской и технологической подготовкой производства новых видов изделий, строительством и реконструкцией, капитальным ремонтом основных фондов путем применения сетевых графиков. Основу сетевой модели составляет сетевой график – наглядное отображение плана работ. Главными элементами сетевого графика являются события и работы. Событие – состояние, момент достижения промежуточной или конечной цели разработки. Событие не имеет протяжённости во времени. Работа – протяжённый во времени процесс, необходимый для совершения события. События на сетевом графике (или на графе) изображаются кружками (вершинами графа), а работы – стрел­ками (ориентированными дугами), показывающими связь между работами. При построении сетевого графика необходимо соблюдать ряд правил. 1. В сетевой модели не должно быть «тупиковых» событий, т. е. событий, из которых не выходит ни одна работа, за исключением завершающего события. 2. В сетевом графике не должно быть «хвостовых» событий (кроме исходного), которым не предшествует хотя бы одна работа. 3.  В сети не должно быть замкнутых контуров и петель, т. е. путей соединяющих некоторые события с ними же самими. При возникновении контура необходимо вернуться к исходным данным и путем пересмотра состава работ добиться его устранения 4.  Любые два события должны быть непосредственно связаны не более чем одной работой-стрелкой. 5. В сети рекомендуется иметь одно исходное и одно завершающее событие. 6. Длина стрелки не зависит от времени выполнения работы. 7. Каждая операция должна быть представлена только одной стрелкой. 8. Следует избегать пересечения стрелок. 9. Не должно быть стрелок, направленных справа налево. 10. Номер начального события должен быть меньше номера конечного события. 3.2. Расчет параметров сетевого графика 3.2.1. Временные параметры сетевых графиков  Начало и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями. Поэтому для указания конкретной работы используют код работы Рi,j, состоящий из номеров начального (i-го) и конечного (j-го) событий (рис. 3.1, а). На рис. 3.1, б изображен пример кодирования работ и событий в принятых обозначениях: tij – продолжительность работы Рi,j, t – ранний срок (ожидаемый момент) осуществления события, t* – поздний срок (предельный момент) осуществления события, n – номер события, nсм – номер предшествующего (смежного) события.   Рис. 3.1. Обозначение элементов сетевого графика: а – код работы; б – пример кодирования событий в при­нятых обозначениях; в – пример изо­бражения события в принятых вы­ше обозначениях На рис. 3.1 в приведён пример изображения события в принятых выше обозначениях. Обозначим через  множество работ, входящих в j-е событие, а через  – множество работ, выходящих из  i-го события. Ранний срок (ожидаемый момент) осуществления j-го события представляет собой момент времени, раньше которого событие произойти не может и рассчитывается по формуле .                                       (3.1) Поздний срок (предельный момент) осуществления i-го собы­тия показывает максимальную задержку во времени наступления данного события: .                                      (3.2) Одно из важнейших понятий сетевого графика – понятие пути L. Критический путь – последовательность работ между начальными и конечными событиями сети, имеющих наибольшую продолжительность во времени. Минимальное время, необходимое для выполнения проекта, запланированного сетевым графиком, равно длине критического пути. Сетевой график может содержать не один, а несколько критических путей. Критическими называются также работы и события, расположенные на этом пути. Резервный интервал от t до t* для событий, лежащих на критическом пути, равен 0. Для завершающего события сетевого графика поздний срок свершения события должен равняться его раннему сроку, т. е. tп = t*п. Длина критического пути равна раннему сроку свершения завершающего события, т. е. tкр = tп = t*п. 3.2.2. Резервы времени работ Любая из работ пути L на его участке, не совпадающем с критическим путем (замкнутым между двумя событиями критического пути), обладает резервом времени. Среди резервов времени работ наиболее часто используют полный и свободный резервы времени работ. Полный резерв времени  работы Pi,j показывает, на сколько можно увеличить время выполнения данной работы при условии, что срок выполнения комплекса работ не изменится. Полный резерв  определяется по формуле .                                          (3.3) Свободный резерв времени  работы Pi,j представляет часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом раннего срока ее конечного события.  находится по формуле .                                         (3.4) Работы, лежащие на критическом пути, так же, как и критические события, резервов времени не имеют.   3.3. Сетевой график в условиях неопределённости.  Анализ и оптимизация сетевого графика 3.3.1. Сетевое планирование в условиях неопределенности Чаще всего продолжительность работы по сетевому графику заранее не известна и может принимать лишь одно из ряда возможных значений, т. е. продолжительность работы tij является случайной величиной, характеризующейся своим законом распределения, а значит, своими числовыми ха­рактеристиками – средним значением, или математическим ожиданием,  и дисперсией σ2 i,j. Для определения числовых характеристик  и σ2i,j работы Pi,j на основании опроса ответственных исполнителей проекта и экспертов определяют три временные оценки: а) оптимистическую оценку аij; б) пессимистическую оценку bij; в) наиболее вероятную оценку mij. Указанные три оценки являются основой для расчета средней ожидаемой продолжительности работы () и ее дисперсии (). При этом используется гипотеза об определенном законе распределения длительностей работ (так называемое β-распределение). Предположение о β-распределении продолжительности работы Рi,j позволяет получить следующие оценки ее числовых характеристик: ;                                          (3.5) .                                           (3.6) Общая продолжительность пути L имеет нормальный закон распределения со средним значением  (L), равным сумме средних значений продолжительности составляющих его работ  и дисперсией σ2 (L), равной сумме соответствующих дисперсий σ2i,j: ;                                           (3.7) .                                         (3.8) Требуется оценить вероятность того, что срок выполнения проекта tкр не превзойдет заданного директивного срока Т. Полагая tкp случайной величиной, имеющей нормальный закон распределения, получим ,                                 (3.9) где Ф(z) – значение интеграла вероятностей Лапласа, где ,                                         (3.10) где σкр – среднее квадратическое отклонение длины критического пути: .                                         (3.11) Если P(tкp ≤ Т) мала (например, меньше 0,3), то опасность срыва заданного срока выполнения комплекса велика, необходимо принятие дополнительных мер (перераспределение ресурсов по сети, пересмотр состава работ и событий и т. п.). Если P(tкp ≤ Т) значительна (например, более 0,8), то, очевидно, с достаточной степенью надежности можно прогнозировать выполнение проекта в установленный срок. Значения функции Лапласа определяются с помощью значений таблицы функций Лапласа или с помощью функции «НОРМРАСП» в среде MS Excel (см. подразд. 3.4). 3.3.2. Анализ сетевого графика Сложность сетевого графика оценивается коэффициентом сложности, который определяется по формуле ,                                          (3.12) где Kсл – коэффициент сложности сетевого графика; nраб – количество работ, ед.; nсоб – количество событий, ед. Сетевые графики, имеющие коэффициент сложности от 1,0 до 1,5, являются простыми, от 1,51 до 2,0 – средней сложности, более 2,1 – сложными. Определить степень трудности выполнения в срок каждой группы работ некритического пути можно с помощью коэффициента напряженности работ. Коэффициентом напряженности Кн работы Pi,j называется отношение продолжительности несовпадающих (заключенных между одними и теми же событиями) отрезков пути, одним из которых является путь максимальной продолжительности, проходящий через данную работу, а другим – критический путь: ,                                      (3.13) где t(Lmax) – продолжительность максимального пути, проходящего через работу Pi,j , от начала до конца сетевого графика; tкр – продолжительность (длина) критического пути; t'кр – продолжительность отрезка рассматриваемого максимального пути, совпадающего с критическим путем. Коэффициент напряженности Кн работы Pi,j может изменяться в пределах от 0 (для работ, у которых отрезки максимального из путей, не совпадающие с критическим путем, состоят из фиктивных работ нулевой продолжительности) до 1 (для работ критического пути). Чем ближе к 1 коэффициент напряженности Кн работы Pi,j, тем сложнее выполнить данную работу в установленные сроки. Чем ближе Кн работы Pi,j к нулю, тем большим относительным резервом обладает максимальный путь, проходящий через данную работу. Вычисленные коэффициенты напряженности позволяют дополнительно классифицировать работы по зонам. В зависимости от величины Кн выделяют три зоны: критическую (Кн > 0,8); подкритическую (0,6 < Кн < 0,8); резервную (Кн  < 0,6). 3.3.3. Оптимизация сетевого графика методом «время-стоимость» При использовании метода «время-стоимость» предполагают, что уменьшение продолжительности работы пропорционально возрастанию ее стоимости. Каждая работа Pi,j характеризуется продолжительностью ti,j, которая может находиться в пределах ,                                         (3.14) где аij – минимально возможная (экстренная) продолжительность работы Pi,j, которую только можно осуществить в условиях разработки; bij – нормальная продолжительность выполнения работы Pi,j. При этом стоимость сi,j работы Pi,j заключена в границах от cmin (при нормальной продолжительности работы) до сmах (при экстренной продолжительности работы). Затраты на ускорение работы Pi,j (по сравнению с нормальной продолжительностью) на единицу времени рассчитываются по формуле ,                                 (3.15) где hi,j – коэффициент затрат на ускорение работы Pi,j. Вариант частной оптимизации сетевого графика с учетом стоимости предполагает использование резервов времени работ. Продолжительность каждой работы, имеющей резерв времени, увеличивают до тех пор, пока не будет исчерпан этот резерв или пока не будет достигнуто верхнее значение продолжительности bij. Стоимость выполнения проекта до оптимизации .                                          (3.16) Стоимость выполнения проекта после оптимизации уменьшится на величину .                                (3.17) Для проведения частной оптимизации сетевого графика, кроме продолжительности работ ti,j, необходимо знать их граничные значения аij и bij, а также показатели затрат на ускорение работ hi,j, вычисляемые по формуле (3.15). Продолжительность каждой работы ti,j целесообразно увеличить в таком размере, чтобы не изменить ранние (ожидаемые) сроки наступления всех событий сети, т. е. на величину свободного резерва времени .   3.4. Методика решения задачи Методику решения задач СПУ рассмотрим на следующем примере. Предположим, что при составлении некоторого проекта выделено 12 событий: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 и 24 связывающие их работы: (0→1), (0→3), (0→5), (1→2), (1→3), (1→4), (2→7), (3→4), (3→5), (3→6), (4→6), (4→7), (5→6), (5→8), (5→9), (6→7), (6→8), (6→9), (6→10), (7→10), (8→9), (9→10), (9→11), (10→11). Необходимо: 1) составить и упорядочить сетевой график; 2) определить временные параметры сетевого графика; 3) оценить вероятность выполнения проекта в установленный срок; 4) оптимизировать сетевой график методом «время-стоимость». На основании исходных данных был построен и упорядочен сетевой график (рис 3.2). Рис. 3.2. Сетевой график Каждая работа имеет три временные оценки: оптимистическую, пессимистическую и наиболее вероятную; по формуле (3.5) определяется среднее время выполнения работы (табл. 3.1). Таблица 3.1 - Временные параметры работ Работа Pi,j аij bij mij   Работа Pi,j аij bij mij   Работа Pi,j аij bij mij   0,1 2 10 9 8 3,5 1 9 8 7 6,10 4 6 5 5 0,3 14 16 12 13 3,6 3 9 6 6 6,9 14 16 12 13 0,5 2 12 10 9 4,7 2 10 9 8 6,8 7 9 8 8 1,2 1 13 10 9 4,6 2 4 3 3 7,10 2 8 5 5 1,4 4 12 5 6 5,6 2 12 10 9 8,9 3 5 4 4 1,3 2 10 3 4 5,8 6 18 9 10 9,10 5 7 6 6 2,7 2 4 3 3 5,9 4 12 5 6 9,11 5 21 19 17 3,4 5 19 9 10 6,7 1 7 4 4 10,11 14 20 11 13   Далее по формулам (3.1) и (3.2) определяются временные параметры событий (ранний и поздний срок), после чего они наносятся на  сетевой график (рис. 3.3). Критический путь находят, следуя от завершающего события к исходному, по номерам смежных событий. Рис. 3.3 Определение критического пути сетевого графика После определения временных параметров событий по формулам (3.3), (3.4) рассчитываются резервы времени работ (графы 6, 7). Результаты расчетов сведены в табл. 3.2. В графе А указан порядковый номер работ, в графе Б – код работы. В графах со 2 по 5 приведены временные параметры событий (см. рис. 3.1. в).   Таблица 3.2 - Расчет резервов времени работ № п/п Работа   Рi,j Продолжитель-ность работы ti,j Ожидаемое время Предельное время Резервы времени работ ti tj t*i t*j А Б 1 2 3 4 5 6 7 1 0,1 8 8 9 1 2 0,3 13 13 13 3 0,5 9 20 20 11 11 4 1,2 9 8 17 9 40 23 5 1,4 6 8 23 9 26 12 9 6 1,3 4 8 13 9 13 1 1 7 2,7 3 17 33 40 43 23 13 8 3,4 10 13 23 13 26 3 9 3,5 7 13 20 13 20 10 3,6 6 13 29 13 29 10 10 11 4,7 8 23 33 26 43 12 2 12 4,6 3 23 29 26 29 3 3 13 5,6 9 20 29 20 29 14 5,8 10 20 37 20 38 8 7 15 5,9 6 20 42 20 42 16 16 16 6,7 4 29 33 29 43 10 17 6,10 5 29 48 29 48 14 14 18 6,9 13 29 42 29 42 19 6,8 8 29 37 29 38 1 20 7,10 5 33 48 43 48 10 10 21 8,9 4 37 42 38 42 1 1 22 9,10 6 42 48 42 48 23 9,11 17 42 61 42 61 2 2 24 10,11 13 48 61 48 61  Пусть требуется оценить вероятность выполнения проекта в директивный срок, равный 63 временным единицам. Для данного сетевого графика дисперсии продолжительности работ критического пути рассчитываются по формуле (3.6); они равны: σ2 (0→3) = 0,1; σ2 (3→5) = 1,8; σ2(5→6) = 2,8; σ2 (6→9) = 0,1; σ2 (9→10) = 0,1; σ2 (10→11) = 1. Используя формулы (3.9)–(3.11), получим Тогда искомая вероятность . Нормальную функцию распределения можно рассчитать с помощью функции «НОРМРАСП» в среде MS EXCEL. Пример расчета показан на рис. 3.4. Рис. 3.4 Пример расчета нормальной функции распределения в Excel Так как значение вероятности составляет 0,8, то с достаточной степенью надежности можно спрогнозировать выполнения проекта в установленный срок (63 временные единицы). По формуле (3.12) рассчитывается коэффициент сложности сетевого графика: . Следовательно, сетевой график средней сложности. Для заданной работы (например, 1→4) по формуле (3.13) рассчитывается коэффициент напряжённости ; . Максимальный путь, проходящий через работу 1→4: 0→1→4→6→9→ 10→11, имеет продолжительность t(Lmax) = 49 (временных единиц). Максимальный путь L4 совпадает с критическим (см. рис. 3.2) на отрезке 6→9→ 10→11 продолжительностью t'кр = 13 + 6 + 13 = 32 временные единицы. Работу 1→4 можно отнести к резервной зоне (Кн i,j < 0,6). Проведём частную оптимизацию сетевого графика методом «время-стоимость». Граничные значения продолжительностей работ аij и bij, их стоимости сij, коэффициенты затрат на ускорение работ hi,j приведены в табл. 3.3. Свободные резервы времени работ были вычислены ранее (см. табл. 3.2). Их ненулевые значения даны в табл. 3.3. Там же представлены результаты частной оптимизации рассматриваемой сети. Таблица 3.3 - Оптимизация сетевого графика методом «время-стоимость» № п/п Работа, Рi,j Продолжительность работы сi,j Коэффициент затрат на ускорение работы, hi,j Уменьшение удельной стоимости проекта, ΔСij ai,i bi,i 1 0,5 5 9 14 11 60 8 5 ∙ 8 = 40 2 1,4 4 6 10 9 28 4 4 ∙ 4 = 16 3 1,3 3 4 6 1 37 12 1 ∙ 12 = 12 4 2,7 2 3 7 13 86 6 4 ∙ 6 = 24 5 3,6 4 6 9 10 92 10 3 ∙ 10 = 30 6 4,7 3 8 14 2 48 5 2 ∙ 5 = 10 7 4,6 1 3 6 3 64 12 3 ∙ 12 = 36 8 5,8 5 10 18 7 15 1 7 ∙ 1 = 7 9 5,9 3 6 12 16 86 7 6 ∙ 7 = 42 10 6,1 2 5 10 14 44 5 5 ∙ 5 = 25 11 7,10 1 5 15 10 74 4 10 ∙ 4 = 40 12 8,9 2 4 8 1 20 3 1 ∙ 3 = 3 13 9,1 11 17 23 2 40 4 2 ∙ 4 = 8 Итого 694 – 293   В табл. 3.3 представлены параметры лишь тех работ, которые имеют свободный резерв времени. Стоимости ci,j остальных работ: c(0,1) = 50; c(0,3) = 45; c(1,2) = 82; с(3,4) = 55; с(3,5) = 72; с(5,6) = 30; с(6,7) = 26; с(6,9) = 75; с(6,8) = 42; с(9,10) = 35; с(10,11) = 10 (усл. ден. ед.). Подчеркнуты те работы, свободные резервы времени которых полностью использованы на увеличение их продолжительности. Стоимость первоначального варианта сетевого графика или плана по формуле (3.16) равна сумме стоимостей всех работ (в том числе работ, не имеющих резервов и не включенных в табл. 3.3): С = 694 + 50 + 45 + 82 + 55 + 72 + 30 + 26 + 75 + 42 + 35 + 10 = = 1216 усл. ден. ед. Стоимость нового плана C' = С – ΔС = 1216 – 293 = 923 усл. ден. ед., т. е. стоимость уменьшилась почти на 25 %. В результате оптимизации сети получился план, позволяющий выполнить комплекс работ в срок tкр = 61 ед. времени при минимальной его стоимости С = 923 усл. ден. ед. В реальных условиях выполнения проекта может потребоваться ускорение его выполнения, что, естественно, отразится на стоимости проекта – она увеличится.   3.5. Последовательность решения задачи   Выполнение задачи осуществляется в следующем порядке: 1)  постановка задачи (что такое сетевой график, его элементы и правила построения, правила организации работ); 2)  составление сетевого графика в соответствии с заданием (по данным о кодах и длительностях работ); 3)  расчёт временных параметров сетевого графика (среднего времени выполнения работы, раннего и позднего сорока свершения событий); 4)  определение полного и свободного резервов времени выполнения работ; 5)  определение критического пути сетевого графика и его выделение на рисунке; 6)  оценка вероятности выполнения комплекса работ в установленный срок; 7)  расчёт коэффициента сложности сетевого графика и определение коэффициентов напряжённости для заданных работ; 8)  оптимизация сетевого графика методом «время-стоимость». Расчет вариантов должен быть приведен в работе. Таблицы необходимо составлять по предложенной форме. По результатам работы следует сделать выводы: 1)  определить сложность сетевого графика: простой, средней сложности, сложный; 2)  в зависимости от коэффициентов напряжённости классифицировать работы по зонам (в соответствии с предложенным вариантом): критическая, подкритическая, резервная; 3)  оценить опасность срыва выполнения комплекса работ в установленный директивный срок: высокая, низкая степень вероятности; 4)  определить, на сколько процентов уменьшилась стоимость выполнения комплекса работ, в результате оптимизации методом «время-стоимость».   3.6. Исходные данные Решение задачи осуществляется по вариантам применительно к табл. 3.5, 3.8. Исходная информация, необходимая для решения задачи, приведена в табл. 3.4–3.8. 1.  По данным о кодах и длительностях работ необходимо построить график привязки сетевой модели, рассчитать среднее время выполнения работ, временные параметры событий и резервы времени работ. Определяются номера вариантов исходных данных применительно к табл. 3.5 и 3.8 следующим образом. Две последних цифры номера зачетной книжки студента делятся с остатком на количество вариантов, представленных в табл. 3.4. К остатку от деления прибавляется единица. Полученное число явится номером варианта для информации соответствующего вида. Значения длительности и стоимости работ округлять до целых. Увеличивать все (аij, bij,mij, сi,j сi,jmax сi,jmin) показатели. Для табл. 3.6–3.7 варианты рассчитываются отдельно. Таблица 3.4 Определение коэффициентов для таблиц 3.5 и 3.8 № варианта 1 2 3 4 5 6 7 8 9 10 11 12 Процент увеличения показателей 5 7 10 12 15 18 20 22 25 27 30 32   Таблица 3.5 - Коды и длительности работ Работа, Рi,j аij bij mij Работа Рi,j аij bij mij 1,2 1 12 6 9,12 2 15 11 1,3 4 8 5 10,12 5 8 7 1,4 3 10 5 10,16 6 16 13 1,5 2 7 6 10,13 2 19 13 1,7 4 12 9 11,13 5 8 6 1,9 2 11 7 12,15 2 19 13 2,6 5 17 9 12,16 5 26 17 3,6 5 17 15 12,18 9 25 20 3,9 6 13 11 13,16 2 9 7 4,7 1 4 2 13,19 8 16 11 4,10 1 9 5 14,17 2 8 6 4,13 3 16 14 15,17 1 9 5 4,11 2 7 6 15,21 6 13 10 5,11 8 19 16 15,20 5 15 12 6,8 4 9 5 15,18 8 16 12 6,9 10 20 16 16,18 9 15 12 6,15 9 13 10 16,20 2 5 3 7,9 8 22 15 16,19 4 9 7 7,12 7 19 12 17,21 4 9 7 7,10 1 6 4 18,20 2 8 5 8,14 9 15 12 19,20 8 16 12 8,15 8 15 13 19,21 1 9 7 9,15 14 23 18 20,21 7 12 10   2.  Оценить вероятность выполнения проекта в директивный срок, равный Т = tкр ∙ k временных единиц, где k – коэффициент, на который необходимо увеличить полученную продолжительность критического пути. Варианты приведены в табл. 3.6. Таблица 3.6 - Коэффициенты для расчета директивного срока   № варианта 1 3 3 4 5 6 7 8 9 10 k 1,03 1,05 1,07 1,09 1,1 1,12 1,14 1,15 1,17 1,2   3.  Рассчитать коэффициенты напряжённости работ по вариантам, представленным в табл. 3.7.   Таблица 3.7 - Номера работ для расчёта коэффициентов напряжённости Работа,  Рi,j Вариант 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Графа Б табл. 3.2 1,2 1,3 1,4 1,5 1,7 1,9 2,6 3,6 3,9 4,7 4,10 4,13 4,11 5,11 6,8 6,9 6,15 7,9 7,12 7,10 8,14 8,15 9,15 9,12 10,12 10,16 10,13 11,13 12,15 12,16 12,18 13,16 13,19 14,17 15,17 15,21 15,20 15,18 16,18 16,20 16,19 17,21 18,20 19,20 19,21   Таблица 3.8 - Стоимости работ Работа, Рi,j сi,j сi,jmax сi,jmin Работа Рi,j сi,j сi,jmax сi,jmin 1,2 16 52 13 9,12 34 58 21 1,3 32 43 24 10,12 25 55 5 1,4 27 31 15 10,16 31 36 1 1,5 29 52 23 10,13 24 32 15 1,7 19 59 18 11,13 37 39 28 1,9 37 45 25 12,15 40 41 5 2,6 29 53 23 12,16 22 42 9 3,6 33 47 14 12,18 10 50 9 3,9 30 50 22 13,16 27 45 6 4,7 36 42 27 13,19 21 31 19 4,10 26 54 20 14,17 14 34 1 4,13 18 44 5 15,17 47 52 24 4,11 16 52 13 15,21 34 58 21 5,11 32 43 24 15,20 25 55 5 6,8 27 31 15 15,18 31 36 1 6,9 29 52 23 16,18 24 32 15 6,15 19 59 18 16,20 37 39 28 7,9 37 45 25 16,19 40 41 5 7,12 29 53 23 17,21 22 42 9 7,10 33 47 14 18,20 10 50 9 8,14 30 50 22 19,20 27 45 6 8,15 36 42 27 19,21 21 31 19 9,15 26 54 20 20,21 32 43 24   4.  Оптимизировать сетевой график методом «время-стоимость». Для этого условно принять, что в соотношении (3.14) i,j = ti,j, i,jрассчитывается по формуле (3.5). Коэффициенты для расчета показателей соответствующих вариантов приведены в табл. 3.4.