Модели сетевого планирования и управления

Модели сетевого планирования и управления Сетевые методы и модели Во многих областях экономики, технологии, проектирования, строительства, научных исследований важное значение имеют задачи оптимизации распределения ресурсов (трудовых, финансовых и др.) в условиях реализации новых проектов. В этих случаях управление работами усложняется новизной разработки, трудностью точного определения сроков и затрат ресурсов на том или ином этапе. Высокоэффективными инструментами для решения таких задач являются сетевые методы и модели. 2 Основные даты • 1956 г., коллективом, возглавляемым Morgan R. Walker (Du Pont de Nemours) и James E. Kelley, Jr. (Remington Rand), разработан метод критического пути (critical path method, СРМ) и программная реализация CPM для ЭВМ UNIVAC. • 1958 г., консалтинговой фирмой Booz Allen Hamilton совместно с корпорацией «Локхид» по заказу Подразделения специальных проектов ВМС США разработана и опробована система планирования PERT (Program Evaluation and Review Technique). • В 1960-е годы сфера применения сетевых методов PERT и СРМ расширяется. Разрабатываются методы и средства оптимизации стоимости для СРМ и PERT (PERT/COST), распределения и планирования ресурсов (RPSM, RAMPS и др.). 3 Основные даты • 1966 г., Alan Pritsker представляет новую генерацию сетевых моделей ̶ GERT (graphical evaluation and review technique). • 1970-е гг. • Техника сетевого анализа и его компьютерные приложения вводятся в учебных заведениях США в качестве обязательных инженерных предметов. • Метод СРМ получает законодательную поддержку ‒ ряд судов США рассматривает претензии участников проектов только при представлении соответствующих расчетов на ЭВМ 4 Назначение и области применения СПУ Модели СПУ получили широкое применение в областях: • научно-исследовательские и опытно-конструкторские работы (НИОКР) проектирование и производство; • строительство и монтаж оборудования на предприятиях; • ремонтные работы; • подготовка и освоение производства новых видов продукции. Диапазон применения СПУ: от задач, касающихся деятельности отдельных лиц, до проектов, в которых участвуют сотни организаций и десятки тысяч людей. 5 Возможности СПУ Система СПУ позволяет: • формировать календарный план реализации некоторого комплекса работ; • выявлять и мобилизовывать резервы времени, трудовые, материальные и денежные ресурсы; • осуществлять управление комплексом работ по принципу «ведущего звена» с прогнозированием и предупреждением возможных срывов в ходе работ; • повышать эффективность управления в целом при четком распределении ответственности между руководителями разных уровней и исполнителями работ. 6 Сетевая модель Комплекс работ (проект) ‒ задача, для выполнения которой необходимо осуществить достаточно большое количество разнообразных работ. Сетевая модель ‒ план выполнения некоторого комплекса взаимосвязанных работ (операций), заданного в форме сети, графическое изображение которой называется сетевым графиком. • Отличительной особенностью сетевой модели является четкое определение всех временных взаимосвязей предстоящих работ. • Главными элементами сетевой модели являются события и работы. 7 Виды работ в СПУ Действительная работа ‒ протяженный во времени процесс, требующий затрат ресурсов (например, сборка изделия, испытание прибора и т.п.). Ожидание ‒ протяженный во времени процесс, не требующий затрат труда (например, процесс сушки после покраски, старения металла, твердения бетона и т.п.). Фиктивная работа ‒ логическая связь между двумя или несколькими работами (событиями), не требующими затрат труда, материальных ресурсов или времени. Она указывает, что возможность одной работы непосредственно зависит от результатов другой. Продолжительность фиктивной работы принимается равной нулю. 8 События в СПУ Событие ‒ это момент завершения какого-либо процесса, отражающий отдельный этап выполнения проекта. Событие может являться: • частным результатом отдельной работы • суммарным результатом нескольких работ. Двойственный характер события: для всех непосредственно предшествующих ему работ оно является конечным, а для всех непосредственно следующих за ним ‒ начальным. При этом предполагается, что событие не имеет продолжительности и свершается как бы мгновенно. Среди событий сетевой модели выделяют исходное и завершающее события. Исходное событие не имеет предшествующих работ и событий, относящихся к представленному в модели комплексу работ. Завершающее событие не имеет последующих работ и событий. 9 Сетевой график События на сетевом графике изображаются кружками (вершинами графа), а работы ‒ стрелками (ориентированными дугами), показывающими связь между работами. 10 График «события-работы» Чтобы решить эту задачу, необходимо провести следующие работы: А ‒ сформулировать проблему исследования; Б ‒ построить математическую модель изучаемого объекта; В ‒ собрать информацию; Г ‒ выбрать метод решения задачи; Д ‒ разработать, отладить или найти готовую программу для ЭВМ; Е ‒ рассчитать оптимальный план; Ж ‒ проанализировать результаты. 11 График «работы-связи» Преимущества: • не содержит фиктивных работ; • имеет более простую технику построения и перестройки; • включает только хорошо знакомое исполнителям понятие работы без менее привычного понятия события. Недостатки: • сети без событий оказываются значительно более громоздкими (т.к. событий обычно значительно меньше, чем работ); • сети менее эффективны с точки зрения управления комплексом. 12 Порядок построения сетевых графиков 1. Планируемый процесс разбивается на отдельные работы. 2. Составляется перечень работ и событий, продумываются их логические связи и последовательность выполнения. 3. Работы закрепляются за ответственными исполнителями. 4. Оценивается длительность каждой работы. 5. Составляется («сшивается») сетевой график. 6. Осуществляется анализ сетевого графика: • • рассчитываются параметры событий и работ; определяются резервы времени и критический путь. 7. По результатам анализа осуществляется его оптимизация сетевого графика. При необходимости сетевой график вычерчивается заново с пересчетом параметров событий и работ. 13 Правила построения сетевых графиков 1. В сетевой модели не должно быть «тупиковых» событий, т.е. событий, из которых не выходит ни одна работа, за исключением завершающего события. 14 Правила построения сетевых графиков 2. В сетевом графике не должно быть «хвостовых» событий (кроме исходного), которым не предшествует хотя бы одна работа 15 Правила построения сетевых графиков 3. В сети не должно быть замкнутых контуров и петель, т.е. путей, соединяющих некоторые события с ними же самими. 16 Правила построения сетевых графиков 4. Любые два события должны быть непосредственно связаны не более чем одной работой-стрелкой. 17 Правила построения сетевых графиков 5. В сети рекомендуется иметь одно исходное и одно завершающее событие. 18 Правила построения сетевых графиков Фиктивные работы и события необходимо вводить для отражения: • зависимости событий, не связанных с реальными работами; • неполной зависимости работ; • реальных отсрочек и ожидания. 19 Правила построения сетевых графиков 6. Упорядочение – расположение событий и работ таким образом, что для любой работы предшествующее ей событие расположено левее и имеет меньший номер по сравнению с завершающим эту работу событием. 20 Понятие о пути. Критический путь. Путь – любая последовательность работ. Длина пути – сумма длин дуг, входящих в последовательность. Полный путь – любой путь, начало которого совпадает с исходным событием сети, а конец – с завершающим. Критический путь – наиболее продолжительный полный путь в сетевом графике. Критическими называются также работы и события, расположенные на этом пути. Критический путь имеет особое значение в системе СПУ: для сокращения продолжительности проекта необходимо в первую очередь сокращать продолжительность работ, лежащих на критическом пути. 21 Пример 1 Длина I-го пути: 1 + 3 + 6 + 8 = 18 22 Пример 1 Длина I-го пути: 1 + 3 + 6 + 8 = 18 Длина II-го пути: 2 + 4 + 8 = 14 23 Пример 1 Длина I-го пути: 1 + 3 + 6 + 8 = 18 (критический) Длина II-го пути: 2 + 4 + 8 = 14 Длина III-го пути: 2 + 5 + 6 = 13. 24 Линейная диаграмма проекта Классический вид сетевого графика – это сеть, вычерченная без масштаба времени. Поэтому сетевой график рекомендуется дополнять линейной диаграммой проекта. При построении линейной диаграммы: • Каждая работа изображается параллельным оси времени отрезком, длина которого равна продолжительности этой работы. • При наличии фиктивной работы нулевой продолжительности (в рассматриваемой сети ее нет) она изображается точкой. • События i и j, начало и конец работы (i, j) помешают соответственно в начале и конце отрезка. • Отрезки располагают один над другим, снизу вверх в порядке возрастания индекса i, а при одном и том же i – в порядке возрастания индекса j. 25 Линейная диаграмма проекта (Пример 1) 26 Временные параметры сетевых графиков 27 Параметры событий Ранний (ожидаемый) срок tр(i) свершения i-го события определяется продолжительностью максимального пути, предшествующего этому событию: t р (i ) = max t ( LП i ) LП i где LПi – любой путь, предшествующий i-му событию, т.е. путь от исходного до i-го события сети. Если событие j имеет несколько предшествующих событий i, то ранний срок свершения события j удобно находить по формуле: t р ( j ) = max t[t р (i ) + t (i, j )] i, j 28 Параметры событий Поздний (предельный) срок tп(i) свершения i-го события равен: t п (i ) = t кр − max t ( Lс i ) Lс i где Lс i – любой путь, следующий за i-м событием, т.е. путь от i-го до завершающего события сети. Если событие i имеет несколько последующих событий j, то поздний срок свершения события i удобно находить по формуле: t п (i ) = min[t п ( j ) − t (i, j )] 29 Параметры событий Резерв времени R(i) i-го события определяется как разность между поздним и ранним сроками его свершения: R(i) = tп(i) – tр(i) Резерв времени события показывает, на какой допустимый период времени можно задержать наступление этого события, не вызывая при этом увеличения срока выполнения комплекса работ. Критические события резервов времени не имеют. 30 Пример 1 При определении tр(i) двигаемся по сетевому графику слева направо: i = 0: tр(0) = 0. i = 1: tр(1) = tр(0) + t(0, 1) = 0 + 1 = 1 (сутки). i = 2: tр(2) = tр(0) + t(0, 2) = 0 + 2 = 2 (суток). i = 3: tр(3) = tр(1) + t(1, 3) = 1 + 3 = 4 (суток). i = 4: tр(4) = max{tр(2) + t(2, 4); tр(3) + t(3, 4)} = max{6; 10} = 10 (суток). i = 5: tр(5) = tр(2) + t(2, 5) = 2 + 5 = 7 (суток). i = 6: tр(6) = max{tр(4) + t(4, 6); tр(5) + t(5, 6)} = max{18; 13} = 18 (суток) = tкр 31 Пример 1 При определении tп(i) двигаемся по сети справа налево: i = 6: tп(6) = tр(6) = 18 (суток). i = 5: tп(5) = tп(6) – t(5, 6) = 18 – 6 = 12 (суток). i = 4: tп(4) = tп(6) – t(4, 6) = 18 – 8 = 10 (суток). i = 3: tп(3) = tп(4) – t(3, 4) = 10 – 6 = 4 (суток). i = 2: tп(2) = min{tп(4) – t(2, 4); tп(5) – t(2, 5)} = min{6; 7} = 6 (суток). i = 1: tп(1) = tп(3) – t(1, 3) = 4 – 3 = 1 (сутки). i = 0: tп(0) = min{tп(1) – t(0, 1); tп(2) – t(0, 2)} = min{0; 4} = 0 (суток). 32 Параметры событий (Пример 1, Таблица 1) 33 Параметры работ Ранний срок tрн(i, j) начала работы (i, j): tрн(i, j) = tр(i) Ранний срок tро(i, j) окончания работы (i, j): tро(i, j) = tр(i) + t(i, j) Поздний срок tпо(i, j) окончания работы (i, j): tпо(i, j) = tп(j) Поздний срок tпн(i, j) начала работы (i, j) : tпн(i, j) = tп(i) – t(i, j) 34 Резерв времени пути а) имеют все некритические пути; б) определяется как разность между длиной критического и рассматриваемого пути R(L) = tкр – t(L) в) показывает, на сколько в сумме могут быть увеличены продолжительности всех работ, принадлежащих этому пути. Если затянуть выполнение работ, лежащих на этом пути, на время большее чем R(L), то критический путь переместится на путь L. Вывод: любая из работ пути L на его участке, не совпадающем с критическим путем (замкнутым между двумя событиями критического пути), обладает резервом времени. 35 Полный резерв времени Полный резерв времени Rп(i, j) работы (i, j) показывает, на сколько можно увеличить время выполнения данной работы при условии, что срок выполнения комплекса работ не изменится. Полный резерв Rп(i, j) определяется по формуле Rп(i, j) = tп(j) – tр(i) – t(i, j) 36 Частный резерв времени 1-го вида Частный резерв времени 1-го вида R1 работы (i, j) – часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом позднего срока ее начального события: R1(i, j) = tп(j) – tп(i) – t(i, j) или R1(i, j) = Rп(i, j) – R(i) 37 Частный резерв времени 2-го вида Частный резерв времени 2-го вида (свободный резерв времени) Rс работы (i, j) – часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом раннего срока ее конечного события: Rс(i, j) = tр(j) – tр(i) – t(i, j) или Rс(i, j) = Rп(i, j) – R(j) 38 Независимый резерв времени Независимый резерв времени Rн работы (i, j) – часть полного резерва времени, получаемая для случая, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие работы начинаются в ранние сроки: Rн(i, j) = tр(j) – tп(i) – t(i, j) или Rн(i, j) = Rп(i, j) – R(i) 39 Выводы 1) частный резерв времени 1-го вида является частью полного резерва времени и может быть использован на увеличение продолжительности данной и последующих работ без затрат резерва времени предшествующих работ; 2) частный резерв времени 2-го вида (свободный резерв) является частью полного резерва времени и может быть использован на увеличение продолжительности данной и предшествующих работ без нарушения резерва времени последующих работ; 3) независимый резерв времени также является частью полного резерва времени и может быть использован для увеличения продолжительности только данной работы. 4) работы, лежащие на критическом пути, так же как и критические события, резервов времени не имеют. 40 Параметры работ (Пример 1, Таблица 2) 41 Параметры работ (Пример 1, Таблица 2) 42 Параметры работ (Пример 1, Таблица 2) 43 Пример 1 Рассчитаем полные резервы работ: Rп(0, 1) = tп(1) – tр(0) –t(0, 1) = 1 – 0 – 1 = 0 Rп(0, 2) = tп(2) – tр(0) –t(0, 2) = 6 – 0 – 2 = 4 Rп(1, 3) = tп(3) – tр(1) –t(1, 3) = 4 – 1 – 3 = 0 Rп(2, 4) = tп(4) – tр(2) –t(2, 4) = 10 – 2 – 4 = 4 Rп(2, 5) = tп(5) – tр(2) –t(2, 5) = 12 – 2 – 5 = 5 Rп(3, 4) = tп(4) – tр(3) –t(3, 4) = 10 – 4 – 6 = 0 Rп(4, 6) = tп(6) – tр(4) –t(4, 6) = 18 – 10 – 8 = 0 Rп(5, 6) = tп(6) – tр(5) –t(5, 6) = 18 – 7 – 6 = 5 44 Коэффициент напряженности работы Величина полного резерва времени не всегда может достаточно точно характеризовать насколько напряженным является выполнение той или иной работы некритического пути. Все зависит от следующих обстоятельств: • на какую последовательность работ распространяется вычисленный резерв; • какова продолжительность этой последовательности. Определить степень трудности выполнения в срок каждой работы некритического пути можно с помощью коэффициента напряженности работ. Коэффициентом напряженности Kн работы (i, j) называется отношение продолжительности несовпадающих отрезков пути, одним из которых является путь максимальной продолжительности, проходящий через данную работу, а другим – критический путь. 45 Коэффициент напряженности работы K н (i, j ) = t ( Lmax ) − t 'кр t кр − t 'кр где t(Lmax) – продолжительность максимального некритического пути, проходящего через работу (i, j); t кр – продолжительность (длина) критического пути; t´кр – продолжительность отрезка рассматриваемого пути, совпадающего с критическим путем. Коэффициент напряженности Kн(i, j) может изменяться в пределах от 0 (для работ, у которых отрезки максимального из путей, не совпадающие с критическим путем, состоят из фиктивных работ нулевой продолжительности) до 1 (для работ критического пути). 46 Коэффициент напряженности работы (Пример 1) 47