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

Тема 1. «Сетевое планирование и управление» 1.1 Сущность, задачи и этапы сетевого планирования и управления В начале 50-х годов 20 века возникла необходимость планирования и реализации крупных проектов, состоящих из большого количества разнообразных взаимосвязанных работ и их исполнителей, размещенных в различных регионах мира. Для реализации этой задачи были разработаны методы, получившие название методы сетевого планирования и управления. Задачи методов сетевого планирования и управления: 1) формирование календарного плана реализации некоторого проекта; 2) реализация проекта в запланированные сроки; 3) эффективное расходование ограниченных временных, трудовых, материальных денежных ресурсов; 4) четкое разделение обязанностей и ответственности между исполнителями работ. Этапы сетевого планирования и управления проектом: 1. Планируемый проект разбивается на отдельные работы. 2. Составляется перечень работ и событий. 3. Определяются логические связи между работами и событиями, то есть их последовательность. 4. Работы закрепляются за конкретными исполнителями. 5. Экспертно определяется длительность каждой работы. 6. Составляется сетевая модель. 7. Рассчитываются параметры событий и работ, определяются резервы времени и критический путь. 8. Проводятся анализ и оптимизация сетевого графика. В настоящее время методы сетевого планирования и управления применяются как для планирования деятельности отдельных работников, так и предприятий, отраслей, комплексов, государств. 1.2 Сетевая модель и основные ее элементы Сетевая модель – это план выполнения взаимосвязанных работ, графическое изображение которого похоже на сеть. Поэтому сетевую модель еще называют сетевым графиком или сетевым графом. Отличительной особенностью сетевой модели является четкое определение всех временных взаимосвязей между работами, входящими в нее. Основными элементами сетевой модели являются: событие и работа. 1 I. Работа (в сетевой модели изображается стрелочкой) – это некоторый процесс, выполнение которого приводит к достижению конкретного результата. Виды работ в сетевом планировании и управлении: а) Действительная работа – протяженный во времени процесс, состоящий из операций, выполнение которых требует затрат ресурсов. Каждая действительная работа должна быть четко описанной и иметь исполнителя. б) Ожидание – протяженный во времени процесс, не требующий затрат ресурсов (например, процесс сушки после покраски). в) Фиктивная работа (зависимость) – логическая связь между двумя событиями, не требующая затрат ресурсов. Эта зависимость указывает на то, что одна работа не может начаться без окончания другой работы. Длительность фиктивной работы равна нулю. На графике изображается пунктирной стрелкой. II. Событие (в сетевой модели изображается кружком) – это момент времени, в котором завершаются одни работы и начинаются другие. Любая работа состоит из двух событий: начального (i) и конечного (j). – работа, связывающая событие i с j. Событие наступает только тогда, когда завершаются все предшествующие ему работы. Соответственно до этого момента не могут начаться работы, исходящие из этого события. При этом предполагается, что событие не имеет продолжительности и свершается как бы мгновенно. Названия работ в сетевом графике отражают сущность данной работы, а название события отражает результат выполнения предшествующей данному событию работы (или нескольких работ). Например, работа называется «возведение стен», а название конечного события данной работы – «стены возведены». Любой проект начинается с исходного нулевого события, то есть события, не имеющего предшествующих работ и событий, а заканчивается завершающим событием, то есть событием, не имеющим последующих работ и событий. 1.3. Правила построения сетевых графиков 2 1. В сетевом графике не должно быть «тупиковых» событий, т.е. событий, из которых не выходит ни одна работа (исключением является завершающее событие). 1 4 6 2 5 3 2. В сетевом графике не должно быть «хвостовых» событий, т.е. событий которым не предшествует хотя бы одна работа (исключением является исходное событие). 1 4 6 2 5 3 3. В сетевом графике не должно быть замкнутых контуров и петель, то есть путей, соединяющих событие с ним же самим. 1 2 4. Любые два события должны быть связаны не более чем одной работой. 5. В сетевой модели должно быть одно исходное и одно завершающее событие. Если в составленной модели это правило не выполнено, то необходимо ввести в нее фиктивные события и работы. Было: Стало: 1 4 3 2 1 3 5 4 2 6 5 1.4. Условный пример построения сетевого графика 3 Планируемый проект: строительство дачного домика. Этап 1. Разбиваем данный проект на отдельные работы. Покупка песка. Покупка цемента. Набор воды в емкость. Доставка песка к месту строительства. Доставка цемента к месту строительства. Доставка воды к месту строительства. Выкапывание контуров будущего фундамента. Замешивание раствора для заливки фундамента. Заливка фундамента. Ожидание затвердевания фундамента дома. Покупка кирпичей. Доставка кирпичей к месту строительства. Возведение стен дома. Покупка балок и досок. Доставка балок и досок к месту строительства. Наложение перекрытий на стены дома. Возведение крыши. Вставка оконных рам. Внутренняя отделка дома. Этапы 2, 3, 4, 5. Определяем работы и события проекта, их взаимосвязи, длительность работ и их исполнителей: Все эти этапы мы объединим в одной таблице: 1 Обозначение работы (0;1) 2 (0;2) Покупка цемента 3 (0;3) Набор воды в емкость 4 (0;4) Выкапывание контуров будущего фундамента 5 (1;5) 6 (2;6) 7 (3;7) 8 (4;8) (5;8) (6;8) Доставка песка к месту строительства Доставка цемента к месту строительства Доставка воды к месту строительства Создание условий для строительства фундамента № Наименование работы Покупка песка Наименование начального события Исходное событие проекта Исходное событие проекта Исходное событие проекта Исходное событие проекта Наименование конечного события Длительность работы, дней Песок куплен 0,5 Цемент куплен 0,5 Вода набрана 0,5 3 Песок куплен Контуры будущего фундамента выкопаны Песок доставлен Цемент куплен Цемент доставлен 1 Вода набрана Вода доставлена 1 Контуры будущего фундамента выкопаны; Песок доставлен; Созданы условия для строительства фундамента Исполнитель 1 4 № Обозначение работы (7;8) 9 (8;9) 10 11 (9;10) (10;11) 12 13 (10;12) (12;13) 14 15 (13;14) (11;14) (14;15) 16 (15; 16) 17 (16;17) 18 (17;18) 19 20 21 (18;19) (19;20) (20;21) Наименование работы Наименование начального события Наименование конечного события Цемент доставлен; Вода доставлена Замешивание раствора для заливки фундамента Заливка фундамента Ожидание затвердевания фундамента дома Покупка кирпичей Доставка кирпичей к месту строительства Создание условий для возведения стен дома Возведение стен дома Покупка деревянных балок и досок Доставка к месту строительства деревянных балок и досок Наложение перекрытий на стены дома Возведение крыши Вставка оконных рам Внутренняя отделка дома Длительность работы, дней Созданы условия для строительства фундамента Раствор замешан Фундамент залит Раствор замешан 0,5 Фундамент залит Фундамент затвердел 0,5 2 Фундамент залит Кирпичи куплены Кирпичи куплены Кирпичи доставлены 0,5 1 Фундамент затвердел Кирпичи доставлены Созданы условия для возведения стен дома Стены дома возведены Созданы условия для возведения стен дома Стены дома возведены Деревянные балки и доски куплены Балки и доски доставлены Деревянные балки и доски куплены Балки и доски доставлены Перекрытия наложены Крыша возведена Окна вставлены Исполнитель Перекрытия наложены Крыша возведена Окна вставлены Внутренняя отделка завершена 0,5 1 3 3 0,5 7 Этап 6. Составляется сетевая модель. Над работами цифрой указывается их продолжительность. 1.5. Упорядочение сетевого графика Упорядоченный сетевой график представляет собой такое расположение работ и событий, при котором для любого события все предшествующие ему события расположены левее и имеют меньший порядковый номер. 5 Таким образом, в упорядоченном сетевом графике все работы должны быть направлены слева направо, и каждая работа должна соединять событие с меньшим номером с событием с большим номером. Упорядочение сетевого графика осуществляется размещением событий по слоям. На первом слое размещается исходное событие и мысленно вычеркиваются все исходящие из него работы. На втором слое размещаются события, оставшиеся после этого мысленного вычеркивания, без предшествующих работ. Затем мысленно вычеркиваются все исходящие из событий второго слоя работы, а на третьем слое размещаются все события, оставшиеся после этого вычеркивания без входящих работ. Эта процедура продолжается до тех пор, пока не будет размещено завершающее событие на последнем слое. В упорядоченном сетевом графике в одном слое не могут находиться события, соединенные работой. Если после упорядочения сетевого графика номера событий располагаются не по порядку, то следует произвести их перенумерацию, а также поменять нумерацию соответствующих им работ с сохранением их длительности. Пример. Необходимо упорядочить следующий сетевой график: Упорядоченный сетевой график будет иметь следующий вид: 6 В полученном после упорядочения сетевом графике все события размещены на слоях и все работы направлены слева направо. В данном графике не для всех работ выполняется условие соединения события с меньшим порядковым номером с событием с большим номером. Исправим это путем перенумерации событий. В результате получим следующий полностью упорядоченный график: После полного упорядочения сетевого графика необходимо провести перенумерацию работ и событий в таблице данных (см.этапы 2,3,4 в условном примере), при этом длительность работ и их взаимосвязи остаются без изменения: № Номер работы Номер работы п/п до перенумерации после перенумерации 1 (0;1) (0;3) 2 (0;3) (0;1) 3 (0;4) (0;2) 4 (1;2) (3;4) 5 (1;5) (3;5) 6 (3;1) (1;3) 7 (3;2) (1;4) 8 (3;5) (1;5) 9 (4;5) (2;5) 10 (4;8) (2;8) 11 (2;6) (4;6) 1.6. Понятие «путь» и его виды. Методы определения критического пути Путь – это любая последовательность связанных работ, в которой конечное событие каждой работы совпадает с начальным событием следующей за ней работы. 7 Полный путь – это любая последовательность связанных работ от исходного события до завершающего. Критический путь – это наиболее продолжительный полный путь в сетевом графике. В сетевом графике может быть несколько критических путей. Критический путь показывает наименьшее время, необходимое для выполнения всех работ по проекту. Критическими работами и событиями называются все работы и события, расположенные на критическом пути. Существуют следующие методы определения критического пути: 1. Метод простого перебора. Предполагает определение всех полных путей сетевого графика, расчет длительности каждого из них путем суммирования длительности входящих в него работ, и выбор пути с максимальной продолжительностью. Пример. Определить методом простого перебора критический путь следующего сетевого графика. 5 1 4 4 2 2 3 1 1 2 4 5 2 Топология полного пути Время полного пути Поскольку наиболее продолжительным является первый путь , то . 2. Графический метод. Необходимо построить линейную диаграмму проекта в декартовой системе координат, в которой по оси ОХ откладываются длительности работ, а по оси ОУ – сами работы. Действительная работа и ожидание на диаграмме изображается в виде отрезка, фиктивная работа изображается точкой. События i и j, определяющие начало и конец работы, размещаются над отрезком в его начале и конце. 8 Критическим будет тот путь, последний отрезок которого располагается дальше всех от нуля по оси ОХ. Для определения критических работ и событий, вычерчиваем критический путь от последнего отрезка до начального события. Пример. Определить графическим методом критический путь вышерасположенного сетевого графика. Строим линейную диаграмму проекта: Необходимо обратить внимание на следующее: событие 3 наступает после окончания работ (0;3) и (2;3). Исходящую из события 3 работу (3;5) на линейной диаграмме проекта мы отражаем после работы (2;3), так как она заканчивается позднее работы (0;3). Из графика видно, что самым дальним отрезком от нуля по оси ОХ является отрезок 4-5, завершающийся на временном промежутке 11. Это число показывает длительность критического пути. Таким образом, критическим будет следующий путь: 3. Метод определения критического пути по резервам (рассмотрим его в параграфе 1.7) 1.7. Временные характеристики событий 1. Ранний (ожидаемый) срок наступления i-го события равен: (1.1) где – любой путь, предшествующий i-му событию. 2. Ранний срок наступления j–го события равен: 9 (1.2) где – время выполнения работы ; Данная формула применяется в том случае, если событию j предшествует несколько путей, а значит, есть несколько предшествующих событий. j 3. Поздний (предельный) срок i-го события равен: (1.3) - любой путь следующий за i-м событием; – продолжительность критического пути. (1.4) Данная формула применяется в том случае, если событие i имеет несколько последующих путей, а значит, есть несколько последующих событий j. i Для завершающего события поздний срок его свершения равняется раннему сроку его наступления. 4. Резерв времени i-го события равен: (1.5) Резерв времени события показывает на какой допустимый период времени можно задержать наступление этого события, не изменяя при этом сроки выполнения всего проекта. 10 Для определения длительности критического пути необходимо определить ранний срок наступления завершающего события сетевого графика. События, лежащие на критическом пути, резервов времени не имеют. Поэтому работы, составляющие критический путь, определяются на основе анализа событий с нулевыми резервами времени. Пример. Сроки свершения события, сутки Резерв времени Номер события ранний R(i) поздний 1 4 4 2 1 7 6 3 3 10 7 4 9 9 5 11 11 Примечание: поскольку событию 3 предшествуют несколько путей, то ранний срок наступления события 3 определяем по формуле (1.2): =max2;3=3 1.8. Временные характеристики работ 1. Ранний срок начала работы : (1.6) 2. Ранний срок окончания работы : (1.7) 3. Поздний срок окончания работы : (1.8) 4. Поздний срок начала работы : (1.9) 1.9. Резервы времени пути и работ 1. Резерв времени рассматриваемого полного пути R(L): 11 (1.10) - продолжительность критического пути; – продолжительность рассматриваемого пути. Резерв времени полного пути показывает время, на которое могут быть увеличены входящие в него работы, без изменения срока выполнения проекта. 2. Полный резерв времени работы : (1.11) Полный резерв времени работы показывает насколько можно увеличить время выполнения данной работы без увеличения сроков выполнения проекта. Важным свойством полного резерва времени работы является принадлежность не только конкретной работе, но и полному пути, проходящему через данную работу. Если полный резерв времени одной работы будет использован, то полные резервы времени других работ, лежащих на этом пути, сократятся на величину использованного резерва. 3. Частичный резерв времени первого вида R1 работы : (1.12) (1.13) Частичный резерв времени первого вида работы показывает время, на которое можно увеличить продолжительность работы, не изменив при этом позднего срока ее начального события. 4. Частичный резерв времени второго вида, или свободный резерв времени Rс работы : (1.14) (1.15) Частичный резерв времени второго вида, или свободный резерв времени Rс работы показывает время, на которое можно увеличить продолжительность работы, не изменив при этом раннего срока ее конечного события. 5. Независимый резерв времени Rн работы : 12 (1.16) (1.17) Независимый резерв времени – это часть полного резерва времени, получаемая для случая, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие работы начинаются в ранние сроки. Работы, лежащие на критическом пути, резервов времени не имеют. Если на критическом пути лежит начальное событие i, то: (1.18) Если на критическом пути лежит конечное событие j, то: (1.19) Результаты расчетов параметров работ необходимо представить в следующей таблице: № п/п Работа Продолжительность работы Сроки начала и окончания работы Резервы времени работы Примечание: если при расчетах резервов времени работ получились отрицательные значения, то в расчетной таблице их заменяем на нули. 1.10. Сетевое планирование в условиях неопределенности При планировании длительности работ, входящих в проект, часто бывают такие ситуации, когда точно определить длительность той или иной работы невозможно. В этих ситуациях можно лишь предположить, сколько времени потребуется для выполнения работы. Другими словами, в этих условиях каждая работа представляет собой случайную величину, которая характеризуется своим законом распределения, а значит, следующими индивидуальными числовыми характеристиками: 1. Математическим ожиданием (или средним значением) – . 2. Дисперсией – . Для определения математического ожидания и дисперсии определить экспертным путем три временные оценки каждой работы: 13 а) оптимистическую оценку при самых благоприятных условиях; б) пессимистическую оценку при самых неблагоприятных условиях; в) наиболее вероятную оценку при нормальных условиях. , т.е.продолжительность работы , т.е.продолжительность работы , т.е. продолжительность работы Математическое ожидание (или среднее значение) найдем по следующей формуле: Менее точное значение математического ожидания можно найти по следующей формуле: Дисперсию найдем по следующей формуле: При достаточно большом количестве работ, принадлежащих пути L, можно применить центральную теорему Ляпунова: если случайная величина представляет собой сумму большого числа взаимно независимых случайных величин, влияние каждой из которой ничтожно мало, то случайная величина имеет распределение, близкое к нормальному. На основании центральной теоремы Ляпунова можно утверждать, что продолжительность пути L имеет нормальный закон распределения со средним значением : и дисперсией равной: 14 Критический путь, рассчитанный в условиях неопределенности, будет средним критическим сроком . Дисперсия критического пути будет обозначена как . При планировании длительности всего проекта в условиях неопределенности, возможны значительные отклонения длины критического пути от значения, рассчитанного по формулам параграфа 1.6. По этой причине важными при анализе сетевого графика являются следующие задачи: I. Оценка вероятности того, что время критического пути не превзойдет директивного срока некоторого директивного (максимально приемлемого по данному проекту) срока Т. Данная вероятность рассчитывается по следующей формуле: кр кр кр где – значение интеграла вероятностей Лапласа; кр кр кр ; (1.27) - среднее квадратическое отклонение длины критического пути: Если вероятность достаточно мала (меньше 0,3), то опасность некр выполнения проекта в директивный срок Т велика, а значит, необходимо принятие дополнительных мер. Если вероятность значительна (больше 0,8), то с достаточной стекр пенью надежности можно прогнозировать выполнение проекта в установленный срок. II. Определение максимального срока выполнения проекта Т, который возможен с заданной вероятностью (надежностью) : кр – нормированное отклонение случайной величины, определяемое с помощью функции Лапласа ; значение определяем по таблице значений функции Лапласа; - это заданная вероятность (уровень надежности). 15 Например, если требуется определить максимальный срок Т выполнения проекта с вероятность 0,95, то . 16 1.11. Сущность, задачи и способы оптимизации сетевого графика Оптимизация сетевого графика заключается в изменении параметров сетевого графика с целью его улучшения, в частности, решаются следующие задачи: а) сокращение длительности критического пути; б) выравнивания коэффициентов напряженности работ с целью снижения вероятности невыполнения проекта в запланированные сроки; в) более рациональное использование ресурсов. Способы оптимизации сетевого графика: 1. Перераспределение всех видов ресурсов между работами. При этом ресурсы перераспределяются от участков путей, содержащих менее напряженные работы, к участкам, состоящим из более напряженных работ (см. параграф 1.12). 2. Сокращение трудоемкости и времени выполнения критического пути за счет передачи части работ критического пути на другие пути, имеющие резервы времени; 3. Параллельное, а не последовательное выполнение работ критического пути. 4. Пересмотр взаимосвязей между работами сетевого графика (т.е. топологии сетевого графика), их длительности за счет изменения технологии выполнения работы. 1.12. Коэффициент напряженности работы. Зоны напряженности. Коэффициентом напряженности работы называется соотношение продолжительности несовпадающих (заключенных между одними и теми же событиями) отрезков пути, одним из которых является путь максимальной продолжительности, проходящий через данную работу, а другим – критический путь: где - продолжительность максимального пути, проходящего через работу ; - продолжительность критического пути; 17 - продолжительность отрезка рассматриваемого максимального пути, проходящего через работу , совпадающего с критическим путем. - полный резерв времени работы . Рассчитанные коэффициенты напряженности позволяют сгруппировать все работы проекта по трем зонам напряженности: 1. критическая зона: 2. подкритическая зона: 3. резервная зона: Чем ближе к единице, тем сложнее выполнить данную работу в установленные сроки. Чем ближе к нулю, тем большим относительным резервом времени обладает максимальный путь, проходящий через данную работу. При реализации реального проекта работы с высокими коэффициентами напряженности пытаются облегчить путем перенесения нагрузки на работы и участки полных путей с меньшими коэффициентами напряженности. Если большая часть работ проекта относится к критической зоне, то это говорит о высокой вероятности превышения запланированных сроков реализации проекта. Пример. Имеется следующий полностью упорядоченный сетевой график, соответствующий всем правилам построения сетевых графиков. 4 1 2 2 4 3 1 1 1 2 5 4 5 3 Методом простого перебора определим длительность критического пути и полных путей сетевого графика: 18 Топология полного пути Время полного пути Рассчитаем коэффициенты напряженности сетевого графика по формуле (1.30): Рассчитаем коэффициенты напряженности сетевого графика по формуле (1.31): Построим вспомогательную таблицу: 19 Номер события 1 2 3 4 5 Работа Сроки свершения события, сутки ранний поздний 2 3 1 7 5 5 6 8 9 9 Полный резерв времени работы Резерв времени R(i) 1 6 2 Коэффициент напряженности работы 1.13. Оптимизация сетевого графика методом «время-стоимость» В зависимости от полноты решаемых задач, выделяют частную и комплексную оптимизацию сетевого графика. В рамках частной оптимизации решается одна из следующих задач: 20 1. Минимизация времени выполнения проекта при неизменной его стоимости. 2. Минимизация стоимости проекта при неизменном времени его выполнения. Комплексная оптимизация сетевого графика представляет собой нахождение оптимального соотношения времени выполнения проекта и его стоимости с учетом целей проекта. При использовании метода «время-стоимость» предполагают, что уменьшение продолжительности работы пропорционально возрастанию ее стоимости. Длительность выполнения каждой работы варьируется в следующих пределах: где - минимально возможная продолжительность работы ; - максимально возможная продолжительность работы ; - наиболее вероятная продолжительность работы . Стоимость выполнения каждой работы варьируется в следующих пределах: где - минимально возможная стоимость работы при ее максимальной продолжительности ; - максимально возможная стоимость работы при ее минимально продолжительности ; – стоимость работы при наиболее вероятной ее продолжительности. До начала расчетов для каждой работы должны быть определены: , , , , , . На основе этих параметров рассчитывается коэффициент изменения затрат от изменения длительности работы : 21 Рис. График зависимости продолжительности и стоимости работы Из приведенного графика видно, что возможно снижение затрат на выполнение работы в случае увеличения ее длительности. Исходя из этого, одним из самых очевидных способов уменьшения стоимости проекта (частичной оптимизации сетевого графика) будет увеличение длительности работ, не лежащих на критическом пути, и имеющих резервы времени. Рассмотрим, как будут рассчитываться длительности работ и их стоимость в случае такой оптимизации сетевого графика. Продолжительность работ целесообразно увеличивать таким образом, чтобы не изменить ранние (ожидаемые) сроки наступления всех событий сети, т.е. на величину свободного резерва времени работы . Продолжительность каждой работы целесообразно увеличивать до тех пор, пока не будет исчерпан ее свободный резерв времени работы или не будет достигнута максимально возможная продолжительность работы , т.е. оптимальная продолжительность работы должна быть определена по формуле: где - наиболее вероятная продолжительность работы ; - свободный резерв времени работы ; - максимально возможная продолжительность работы . Величина, на которую уменьшится стоимость работы, при увеличении ее длительности рассчитывается по следующей формуле: 22 где – величина, на которую уменьшится стоимость работы при увеличении ее длительности; - коэффициент изменения затрат от изменения длительности работы ; - время, на которое увеличилась продолжительность работы. Оптимальная стоимость работы рассчитывается по формуле: где – стоимость работы при наиболее вероятной ее продолжительности. Стоимость проекта после оптимизации составит: где - стоимость проекта до оптимизации. Результаты расчетов необходимо представить в следующей таблице: Работа Продолжительность работы Свободный резерв времени работы Стоимость работы Коэффициент Величина, на которую изменится стоимость работы Условный пример. Необходимо провести частную оптимизацию сетевого графика, исходные данные приведены в таблице. 23 Работа Продолжительность работы (0,5) (1,4) (1,3) (2,7) 5 4 3 2 ИТОГО Работа 9 6 4 3 14 10 6 7 Свободный резерв времени работы 11 9 1 13 Стоимость работы 31 22 32 70 60 28 37 86 Х 103 46 68 100 Коэффициент Величина, на которую изменится стоимость работы 8 4 12 6 У Коэффициент (0,5) (1,4) (1,3) (2,7) Работа (0,5) (1,4) (1,3) (2,7) 24 25