Менеджер проекта на этапе планирования часто сталкивается с ситуацией, когда одних структуры, плана по вехам и недостаточно для разработки календарного плана проекта. Такое возникает для весьма крупных проектных задач, где содержательную часть планируемых работ требуется осуществить наиболее рационально, снизив при этом расход временных ресурсов. На помощь проектному менеджеру может прийти сетевое планирование как инструментальное решение, реализуемое по стандартному оптимизационному алгоритму.
Метод сетевого моделирования
Сетевое планирование и управление получило активное развитие с 50-х годов прошлого века сначала в США, затем в других развитых странах и в СССР. Такие методы сетевого планирования, как CPM, PERT позволили существенно поднять «планку» проектного управления в направлении оптимизации временных и содержательных параметров графиков работ. Это дало возможность разрабатывать расписания проектных задач на основе более эффективной методологии сетевого моделирования, вобравшей в себя весь лучший опыт (схема методов календарного планирования приведена ниже). Сетевая диаграмма имеет различные названия, среди них:
- сетевой график;
- сетевая модель;
- сеть;
- граф сети;
- стрелочная диаграмма;
- PERT-диаграмма, и т.д.
Визуально сетевая модель проекта представляет собой графическую схему последовательного комплекса работ и связей между ними. Стоит заметить, что система планирования и управления проектом целостно отображается в графической форме состава операций, их временных протяженностей и взаимосвязанных событий. Основой метода построения модели служит раздел математики, именуемый теорией графов, сформировавшийся в начале 50-х – конце 60-х годов.
Методы календарного планирования и управления проектам
В модели сетевого планирования и управления под графом понимается геометрическая фигура, включающая бесконечное или конечное множество точек и линий, соединяющих между собой эти линии. Граничные точки графа называют его вершинами, а ориентированные в направлениях соединяющие их точки – ребрами или дугами. Сетевая модель в свой состав включает именно ориентированные графы.
Вид ориентированного графа
Разберем другие основные понятия сетевой модели проекта.
- Работа – часть производственного или проектного процесса, имеющая начало и окончание в форме количественно описываемого результата, требующая затрат времени и других ресурсов. Работа отражается на диаграмме в форме однонаправленной стрелочной линии. Формой работ мы можем считать операции, мероприятия и действия.
- Событие – факт завершения работ, результат которых необходим и достаточен для начала реализации следующих операций. Вид события на модели отражается в форме кружков, ромбиков (вехи) или других фигур, внутри которых помещается идентификационный номер события.
- Веха представляет собой работу с нулевой продолжительностью и обозначает важное, значимое событие в проекте (например, утверждение или подписание документа, акт окончания или начала проектного этапа и т.п.).
- Ожидание – это процедура, которая не потребляет никаких ресурсов, кроме затрат времени. Отображается как линия со стрелкой на конце с отметкой длительности и указанием наименования ожидания.
- Фиктивная работа или зависимость – вид технологической и организационной связи работ, не требует никаких усилий и ресурсов, в том числе затрат времени. На сетевой диаграмме показывается как пунктирная стрелка.
Варианты связей и отношение предшествования
Сетевые методы планирования строятся по моделям, в которых проект представляется как целостная совокупность взаимосвязанных работ. Данные модели во многом формируются типом и видом связей между операциями реализации проекта. С позиции типа различаются жесткие, мягкие и ресурсные связи. Видовое различие взаимосвязанности операций основано на отношения предшествования. Рассмотрим основные типы связи.
- Мягкие связи. Им соответствует особая, «дискреционная» логика, дающая «мягкую» основу для выбора операций к размещению на диаграмму, диктуемого технологией. В то время как технология длительный период развивалась на протяжении многих циклов, вырабатываются правила делового оборота, не требующие дополнительной фиксации и планирования. Это экономит время, место модели, стоимость и не требует дополнительного контроля со стороны PM. Поэтому менеджер проекта сам решает, нужна ему такая выделенная операция, или нет.
- Жесткие связи. Данный вид связей основан на технологической логике. Они предписывают выполнение конкретных действий строго после других, что сообразно с процессуальной логикой. Например, наладку оборудования можно осуществлять только после его монтажа. Тестирование недочетов технологии допустимо проводить, если сдача ее в опытную эксплуатацию произошла и т.д. Иными словами, принятая технология (неважно, в какой сфере она реализуется) жестко навязывает последовательность мероприятий и событий проекта, что и обуславливает соответствующий тип связи.
- Ресурсные связи. В условиях назначения на один ответственный ресурс нескольких задач возникает его перегруженность, что может привести к удорожанию проекта. За счет подведения под менее критичную задачу дополнительного ресурса этого можно избежать, и такие связи называются ресурсными.
В момент формирования расписания проекта сначала применяются жесткие, а затем – мягкие связи. Далее, по необходимости, некоторые мягкие связи подлежат сокращению. Благодаря этому может быть достигнуто некоторое сокращение общей длительности проекта. В условиях перегруженности некоторых ответственных ресурсов из-за параллельных работ допустимо разрешение возникших конфликтов введением ресурсных связей. Однако следует контролировать, чтобы новые связи не привели к значительным изменениям общего плана.
Сопряженные работы как некая последовательность проектной задачи связаны друг с другом. Назовем их операциями А и В. Введем понятие отношения предшествования, которое рассматривается как некое ограничение на сроки и общую продолжительность, так как операция В не может начаться до момента окончания операции А. Это означает, что В и А связаны отношением простого предшествования, при этом вовсе не обязательно, чтобы В начиналось одномоментно с окончанием А. Например, отделочные работы начинаются после возведения крыши дома, но это не означает, что выполняться они должны в тот же момент, когда наступит указанное событие.
Метод сетевой модели номер один
Сетевое планирование и управление (СПУ) предполагает два варианта построения сетевой диаграммы проекта: «ребро – работа» и «вершина – работа». При первом варианте отображения диаграммы реализуются метод критического пути и метод PERT. Метод имеет и иное название – «вершина – событие», что, по сути отражает другую сторону единого содержания. В англоязычной интерпретации данный вариант построения сетевой модели по аббревиатуре называют АоА (Activity on Arrow Diagramming). Доминирующее место в методе занимают события проекта. События различают трех видов:
- начальное событие;
- промежуточное событие;
- конечное событие.
Устройство проектной задачи таково, что в процессе ее реализации место есть только одному начальному и одному конечному событию. До начального события и после конечного события работы не выполняются. В момент конечного события проект считается завершенным. До наступления промежуточного события все входящие операции должны быть выполнены. Оно дает старт всем исходящим из него операциям. Фиктивные работы применяются после работ, если неизвестно, какая из них окажется последней.
Пример сетевой диаграммы метода «ребро – работа»
Сетевое планирование при построении сетевой диаграммы АоА руководствуется следующим набором основных правил.
- Проектные события подлежат последовательной нумерации. Номера присваиваются событиям без пропусков.
- Начального и конечного события должно быть только по одному.
- Работа не может планироваться и размещаться в направлении события проекта, имеющего меньший номер, чем у исходного события.
- Недопустима замкнутая последовательность операций, а линии стрелок размещаются в направлении слева-направо.
- Двойные связи между событиями недопустимы.
Алгоритм формирования диаграммы следующий.
- Разместить слева поля начальное событие.
- Найти в списке работы, не имеющие предшественников, и разместить их итоговые события на диаграмме правее начального события без указания номеров.
- Соединить стрелочными линиями работ начальное и только что размещенные события.
- Из состава работ, которых еще нет на диаграмме, выбрать работу, для которой предшественник уже размещен.
- Справа от предшествующего события вставить новое событие без номера и связать их выбранной работой.
- С учетом отношения предшествования соединить фиктивной работой начальное событие размещенной работы и событие, размещенное на сетевом графике.
Проект - это деятельность, смыслом которой является эффективное достижение цели в условиях ограничения времени и ресурсов. Целью может быть открытие своего дела, исследование, создание новых систем, модернизация процесса производства или строительство дома.
Методы сетевого планирования позволяют завершить проект и достичь цели по возможности за минимум времени. Каким образом? Сетевой метод помогает выбрать оптимальную последовательность действий, работ, обоснованно распределить ресурсы, повысить эффективность управленческих функций.
Сетевое планирование. Что это?
Методы сетевого планирования широко применяются при создании планов на перспективу, производственных моделей, проектов для долгосрочного применения. Сети или планы по созданию нового продукта, повышению конкурентоспособности состоят из раздела с общей продолжительностью цикла производства и разделов, описывающих конкретные направления, требуемые ресурсы.
Составление плана и анализ сети осуществляются поэтапно:
- разработка модели сетевого планирования, комплекса действий;
- математические расчеты для определения важности конкретных операций.
Графики-сети
Сетевые планы содержат экономические вычисления, аналитику в графической форме, решения руководства, среднесрочные и перспективные планы. Преимущества графиков-сетей кроются не только в наглядном изображении, но и в возможной подготовке моделей, изучении и повышении эффективности проектов.
Сетевое планирование, сетевые графики - это изображения системы взаимосвязанных действий в логической последовательности. Они отражают период работ, позволяют улучшать готовый график на компьютере и практикуются в управлении.
Объединенные в график элементы, описывающие увязку поэтапных рабочих действий, именуются ориентированным графом.
Где внедряется сетевое планирование?
Планы-сети используются во многих сферах и позволяют осуществлять:
- НИОКР;
- проектирование технологий;
- производство опытных и серийных образцов;
- ремонтные работы и модернизирование оборудования;
- строительные и монтажные работы;
- инновационную деятельность;
- рыночные исследования;
- бизнес-планирование;
- управление и перестановку кадров.
Задачи, решаемые методом сетей
Состояние современного рынка подталкивает руководство к постоянной работе над многими текущими и стратегическими вопросами. Разнообразные задачи сетевого планирования способствуют повышению эффективности управления.
Управленческие задачи, решение которых осуществляется методом сетевых планов | Другие задачи, решаемые сетевым методом |
Выбор целей развития организации и отделов с учетом внешней среды. | Эффективное распределение и рациональное применение ресурсов. |
Формулировка взаимоувязанных со стратегией заданий для подразделений. | Составление прогнозов по поэтапному выполнению работы, корректировка сроков. |
Привлечение к проектированию опытных исполнителей, ответственных за определенный этап работы. | Экономический анализ применяемых технологий и способов выполнения заданий. |
Внесение изменений в планы-графики с учетом условий рынка. | Применение компьютеров для расчетов, обработки информационных данных и моделирования. |
Осуществление увязки стратегии и целей краткосрочного уровня. | Оперативное получение информации о проделанной работе. |
Граф
Методы сетевого планирования и управления основаны на применении комплексного изображения предполагаемых работ в форме графа, схемы, состоящей из установленных точек (вершин), объединенных отрезками (ребрами). Если их направления обозначены стрелками, схема именуется ориентированным графом.
Графы имеют разнообразные наименования: от лабиринтов до диаграмм. Теоретическое изучение сетей опирается на ряд понятий.
Термин графической теории | Значение термина |
Чередование ребер в последовательности, при которой их концы являются началом для следующих дуг. |
|
Путь, в котором вершина сходится с точкой конца. |
|
Ребра, дуги | Работы, производственные этапы, результативные действия. |
Вершины, точки | Событие, результат, итог выполненных действий. |
Сетевой график | Ориентированный граф без контуров с ребрами, отмеченными характерными числами. |
Действия и события
Сетевое планирование проекта связано с изображением последовательности работ и выполненных результативных действий (событий). Процессы подразделяются на три категории:
- действительные работы, конкретные действия;
- работы фиктивного характера, не требующие каких-либо действий (связи или зависимости между событиями), изображаются пунктиром;
- работы-ожидания, не связанные с применением ресурсов (остывание полуфабрикатов, затвердевание деталей, застывание бетона).
Итог выполненной работы или момент решения задачи обозначается событием. Например, цель определена, план готов, задача выполнена, оплата продукции переведена, денежные средства поступили на счет, готовая продукция произведена. События классифицируются как:
- Начало или исход.
- Предшествующие, последующие.
- Конечные, промежуточные или завершающие.
- Простые, сложные.
Считается, что графики «вершины-работы» имеют больше преимуществ, так как они удобнее, естественнее и проще в использовании, чем «вершины-события».
Этапы планирования сети
Сетевое планирование |
|
| Разделение совокупности работ на этапы осуществляет руководитель двумя методами. Горизонтальный метод предполагает разбивку совокупности на элементы. Вертикальный способ - деление с учетом управленческой структуры, задействованной в проекте. |
| Менеджеры или рядовые работники на своем участке действий подробно описывают этапы, суть работ и событий. |
| Менеджеры или рядовые работники на своем участке готовят график, сообщают руководству о ходе работ, привлекают сотрудников отделов. Требуется подробная детализация графов с совокупностью всех действий и их увязкой. |
| Построение общего графика осуществляют с первого события (круг с номером) до конечного, слева направо. Действия обозначают стрелками, над которыми отмечают срок решения задачи. |
| Учитываются нормативы, особенности и характер работы в организации. |
Основы построения графа-сети
Рассмотрим основы построения графа-сети по типу «вершина-событие». Сетевое планирование и управление в российских компаниях опирается в большинстве своем на графы именно данного типа.
- Все действия поочередно заключаются между событиями, обозначаются номером. Например, рыночные исследования на графе отмечаются цифрами 3 - 4.
- Тупиковые события не допустимы, лучше, если преобладают завершающие. Появление тупиков говорит о неточности схемы или проблемном применении рабочего результата.
- Необходимо наличие только одного начального события.
- Замкнутые контуры, соединения события следующего за предыдущим, не допустимы.
- Увязка стоящих рядом событий не может изображаться двумя и более действиями.
Плановые параметры
Любой рабочий процесс, рассмотренный в графике-сети, осуществляется при доступе к ресурсам. Расход времени, показатели стоимости конкретных работ и их объединения являются главными параметрами в схеме-сети.
Сетевое планирование и управление предполагает выделение ряда временных значений:
- период работы над этапами проекта ;
- критический путь;
- временные резервы на совершение событий.
Критическим путем именуется самая большая по временным расходам цепочка работ, начавшаяся в первом событии и завершаемая в последнем. События и рабочие действия обозначаются цифрами. Путь (рисуется жирной линией) может выглядеть так: 11 - 12 - 14 - 16 - 17; составит 24 человеко-дня.
Временные резервы на совершение действий становятся временными промежутками, обозначающими дополнительный срок, в который планируется уложить завершение события. Определяется он как разница поздних и ранних сроков.
Оценка времени
При составлении общего графика устанавливается промежуток времени на совершение каждой операции. Ограничиться одним значением календарно-сетевое планирование не позволяет. Осуществляется определение минимума времени (Тмин), максимума (Тмакс) и вероятного значения (Твер) продолжительности каждого действия. Период обозначается человеко-часами, человеко-днями.
Оценка временного периода по принципу вероятности не принимается как норматив в виду своей необъективности. Ожидаемое время (Тож) на выполнение каждого этапа работ обрабатывается на основе статистической формулы.
Тож = (Тмин + 4 Твер + Тмакс) / 6 |
Рассчитанное, усредненное время ожидаемого срока действий указывается на схеме-сети или в таблице с цифровыми данными. Найденный для каждого этапа период времени используется при следующих вычислениях.
Оптимизация схем-сетей
Достигнет ли организация запланированных целей? Ответ на данный вопрос будет найден при проведении анализа модели сети. Анализ социального и экономического уровня эффективности итога работ дает возможность оптимизировать сетевое планирование.
Пример долгосрочного планирования практически всегда связан с факторами внешней и внутренней среды фирмы. Для учета разных условий, влияний применяют оптимизацию в частном и общем порядке.
Частная оптимизация - это подход, подразумевающий минимизацию совокупного срока на совершение всех действий с неизменной стоимостью проекта, или, наоборот, снижение цены до минимума с неизменным общим временем на проект. Оптимизация в комплексе - это вариант с соразмерной, оптимальной увязкой расходов и сроков.
Рыночные условия заставляют учитывать при планировании сети максимальную прибыль, минимальные потери ресурсов и времени, производительность персонала.
Итак, оптимизирование графика-сети - это повышение эффективности всех управленческих функций. Задачей оптимизации является сокращение расходов, получение прибыли при ограничениях плана.
Заключение
Методы сетевого планирования и управления в отечественных организациях могут активно применяться для разрешения многих сложных вопросов, задач. Графы применимы для бизнес-планирования, моделирования, формирования и разработки краткосрочных, среднесрочных, стратегических планов.
Графики-сети дают возможность объединить производственные средства и ресурсы: материальные, трудовые, финансовые; указать желаемые и реально действующие условия. Сетевое планирование поможет не просто выявить требуемый объем ресурсов для будущего проекта, но и рационально осуществить их применение уже сегодня.
Сетевая модель - это разновидность планов-графиков выполнения производственных процессов, которые впервые были применены на американских фирмах Г. Ганттом. На линейных или ленточных графиках по горизонтальной оси в выбранном масштабе времени откладывается продолжительность работ по всем стадиям, этапам производства, т.е. календарные дни фиксируются от начала производства до его окончания. Содержание циклов работ изображается по вертикальной оси с необходимой степенью их расчленения на отдельные части или элементы. Такие графики называют графиком Гантта. Цикловые или линейные графики обычно применяются на отечественных предприятиях в процессе краткосрочного или оперативного планирования производственной деятельности. Основным недостатком таких планов является отсутствие возможности тесной взаимоувязки отдельных работ в единую производственную систему или общий процесс достижения запланированных конечных целей предприятия (фирмы).
Другим вариантом плана-графика является сетевое планирование - одна из форм графического отражения содержания работ и продолжительности выполнения планов и проектных, плановых, организационных и других видов деятельности предприятия.
Под сетевым планированием принято понимать графическое изображение определенного комплекса выполняемых работ, отражающее их логическую последовательность, существующую взаимосвязь и планируемую продолжительность и обеспечиваю- гцее последующую оптимизацию разработанного графика на основе экономико-математических методов и компьютерной техники с целью его использования для текущего управления ходом работ.
Сетевые модели предназначены для проектирования сложных производственных объектов и работ, включающих большое число различных элементов. Для несложных работ обычно используются линейные (или цикловые) графики.
Применение сетевого планирования в современном производстве способствует решению следующих задач: обоснованно выбирать цели развития каждого подразделения предприятия с учетом планируемых конечных результатов; устанавливать конкретные задания всем подразделениям и службам предприятия на основе их взаимоувязки с единой стратегической целью в планируемом периоде; привлекать к составлению планов-проектов непосредственных исполнителей основных этапов предстоящих работ, имеющих производственный опыт и необходимую квалификацию; рационально распределять и использовать имеющиеся ресурсы; прогнозировать своевременность выполнения основных работ, сосредоточенных на критическом пути, принимать упреждающие решения по корректировке планов-графиков выполнения работ с учетом изменения внешней и внутренней сред.
Сетевые модели могут быть весьма разнообразны как по организационной структуре производственной системы, так и по назначению сетевых графиков, а также по используемым нормативным данным и средствам обработки информации.
По организационной структуре различают внутрифирменные или отраслевые модели сетевого планирования, по назначению - единичного и постоянного действия. Сетевые модели бывают детерминированные, вероятностные и смешанные. В детерминированных сетевых графиках все работы стратегического проекта, их продолжительность и взаимосвязь, а также требования к ожидаемым результатам являются заранее определенными. В вероятностных моделях многие процессы носят случайный характер. В смешанных сетях одна часть работ является определенной, а другая - неопределенной. Модели могут быть также одноцелевые и многоцелевые.
Основным плановым документом в сетевой системе является график (или просто сеть), в котором отражаются логические взаимосвязи и результаты выполняемых работ.
Граф - это условная схема, состоящая из заданных точек (вершин), соединенных между собой определенной системой линий. Отрезки, соединяющие вершины, называются ребрами (дугами) графа. Ориентированным считается такой граф, на котором стрелками указаны направления всех его ребер или дуг. Графы носят название карт, лабиринтов, сетей и диаграмм. Исследование этих схем проводится методами теории, получившей название «теории графов», т.е. методы сетевого планирования базируются на теории графов. Она оперирует такими понятиями, как пути, контуры и др. Путь - это последовательность дуг или работ, когда конец каждого предыдущего отрезка совпадает с началом последующего. Контур означает такой конечный путь, у которого начальная вершина или событие совпадает с завершающим, конечным. Другими словами, сетевой график - это ориентированный граф без контуров, дуги, ребра которого имеют одну либо несколько числовых характеристик. На графике «вершины - события» ребрами считаются работы, а вершинами - события.
Основными элементами сетевой модели являются: работа, событие, продолжительность работы, различные виды путей.
Работа в сетевом графике изображается стрелкой. Различают несколько видов этого понятия:
- ? действительная работа - это процесс, требующий затрат времени и ресурсов (например, любая технологическая операция, выполняемая на производственном оборудовании, наладка этого оборудования); отражается в сетевом графике сплошной стрелкой;
- ? ожидание - это процесс, требующий только затрат времени и не нуждающийся в использовании ресурсов (например, процесс высыхания клея или краски, процесс брожения); отражается в сетевом графике сплошной стрелкой;
- ? зависимость, или « фиктивная работа », - логическая
связь между двумя или несколькими событиями, не требующая для своего осуществления ни затрат времени, ни ресурсов; указывающая на то, что определенное событие (работа) не может начаться без осуществления другого события (работы); отражается в сетевом графике пунктирной стрелкой.
Событие - это момент времени, определяющий возможность осуществления начала или окончания данной работы или нескольких работ. Продолжительность во времени события равна нулю, т.е. событие не имеет продолжительности и осуществляется мгновенно после выполнения предшествующих ему работ; обозначается кружком, его номер проставляется внутри кружка. Событие является разграничителем работ плана, т.е. это результат выполнения предшествующей работы, а также необходимое условие для начала следующей. События могут носить промежуточный или окончательный характер. Если событие имеет промежуточный характер, то оно является предпосылкой для начала следующих за ним работ. Таким образом, события имеют свойство соединения предшествующих работ с последующими.
Кроме промежуточных событий в сетевом графике имеются:
- ?исходное (начальное ) - не имеет входящих в него работ и обозначается как нулевое, оно выражает собой момент наступления условий для начала выполнения всего комплекса работ;
- ? завершающее (конечное ) - событие, в котором сходятся все работы, и ни одна работа из него не выходит, означающее собой момент окончания всего комплекса работ и достижения намеченной цели.
Любая работа может обозначаться двумя номерами событий (рис. 7.1):
- 1) номер события, от которого работа исходит (работа А обозначается (1 - 2) или (1->2));
- 2) в которое работа входит (работа Б обозначается (2 - 3)).
Рис. 7.1.
Взаимосвязанные между собой работы и события сетевого графика образуют пути , т.е. непрерывную последовательность работ. Путь определяется по направлению стрелок, причем ни один путь не должен дважды проходить через одно и то же событие. Длина пути рассчитывается как сумма продолжительности составляющих его работ. Различают несколько видов путей".
я полный - это последовательность работ по направлению стрелок от исходного до завершающего события;
- ? предшествующий - последовательность работ по направлению стрелок от начального до рассматриваемого; путь, следующий за данным событием до завершающего;
- ? путь между несколькими событиями",
я критический - полный путь максимальной продолжительности, определяющий конечный срок выполнения всего комплекса работ и достижения намеченной цели. Работы, расположенные на критическом пути, называют критическими (напряженными ). Все остальные работы являются некритическими (ненапряженными) и обладают резервами времени, которые позволяют передвигать сроки их выполнения и сроки свершения событий, не влияя на общую продолжительность выполнения всего комплекса работ.
Решение задач сетевого планирования студенты изучают на различных дисциплинах, связанных с теорией графов и методами оптимального решения. В данной статье будут рассмотрены два примера решения таких задач. Мы постараемся не использовать сложных и запутанных формул, чтобы показать, как на самом деле всё просто.
Суть задачи
Задачи сетевого планирования сводятся к двум целям:
- Найти оптимальный маршрут;
- Определить, как максимально быстро выполнить проект.
В первом случае рассматриваются такие случаи, когда необходимо соединить несколько независимых узлов, находящихся в одной сети. Сделать это необходимо максимально коротким способом.
Например, в некотором районе города требуется провести трубопровод к нескольким домам. Понятно, что к разным домам могут вести несколько дорог. Таким образом, нам нужно определить, какой из маршрутов прокладки будет наиболее коротким. Узлами в этом случае будут наши дома.
Во втором случае задачи предполагают, что существует некий проект, который состоит из нескольких работ. Работы могут выполняться поочередно, друг за другом, но не каждая из них для начала выполнения требует завершения какой-то из предыдущих работ. За счет этого можно оптимизировать проект, выполняя несколько задач параллельно, не тратя время впустую.
Соответственно, обе задачи решаются с помощью графов – точек, соединенных между собой произвольными линиями. В задаче первого типа граф даётся, как правило, условием задачи, а во втором случае его необходимо изобразить самостоятельно. Этим мы сейчас и займёмся.
Первый случай
Выше вы видите граф. Цифры в кружках – это дома, к которым телевизионная компания планирует подвести кабеля. Как мы видим, к одному кружку могут вести два или три пути. Пути называются рёбрами графа. У каждого пути есть свой вес. Это наше расстояние. Нам нужно выбрать из всего этого обилия путей самый короткий, который объединит каждый кружок – вершину графа.
Для этой цели существует специальный алгоритм «Прима». Его суть заключается в следующем:
Мы начинаем идти из первой вершины и присоединяем к ней ребро, имеющее самый маленький вес. В нашем случае – это ребро 1;2. Его вес равен 1.
Теперь мы присоединяем самое короткое ребро, из всех выходящих из вершин 1 и 2. Это ребро 2;5. Его вес – 3.
У нас уже три вершины – 1,2,5. Присоединяем самое короткое ребро, выходящее из них. И это – 2;4. Его вес – 4.
Самое короткое ребро, выходящее из вершин 1,2,4,5 – 4;6. Оно равно 3.
Последнее ребро – 4;3. Мы объединили все вершины. Наш путь в сумме составляет: 1 + 3 + 4 + 3 + 5 = 16.
Второй случай
Здесь всё немного сложнее, чем в вышеописанном примере. По условию даётся таблица примерно следующего характера.
На основании данной таблицы мы рисуем следующий граф.
Правила при составлении графа простые:
Каждая следующая работа всегда находится правее предшествующей.
Никакая работа не может быть начата без выполнения всех предыдущих по условию. Мы не могли бы начать делать b10, не сделав b3, выполнение которой приходится на вершину 3. Мы не можем строить стены, не возведя фундамент.
Тупиков быть не должно. Из каждой вершины выходит как минимум, одно ребро.
Далее мы находим так называемый «критический путь». Это самое длинное расстояние от 0 до 6. Мы начинаем двигаться из нуля и присоединяем каждую вершину самым длинным путём. Например, 3 мы можем присоединить, пройдя ребро 0;3, вес которого – 8 или два ребра – 0;1 и 1;3, а так же 0;2 и 2;3. Из этого мы выбираем второй вариант, потому что так мы пройдём самое большое расстояние.
Подпишем расстояния, до каждой вершины сверху.
Теперь нам нужно пройти этот же граф, но уже в обратную сторону, от вершины 6. Только обратно мы следуем, присоединяя каждую вершину самым КОРОТКИМ путём. Обратите внимание, что ребро 3;5 имеет нулевой вес, поэтому и кратчайший путь к вершине 3 будет равен 12. Подпишем самые короткие пути снизу вершин.
Там, где разница между самым коротким и самым длинным путём будет равна нулю, проходит критический путь. На рисунке ниже он подчёркнут двойными чертами.
Это крайний срок выполнения проекта. Он равен 3 + 9 + 7 = 19. Раньше этого успеть нельзя. По остальным работам есть резерв времени. Чтобы его посчитать, отнимите верхнее число от нижнего над каждой вершиной.
Назначение сервиса . Онлайн-калькулятор предназначен для нахождения параметров сетевой модели :- ранний срок свершения события , поздний срок свершения события, ранний срок начала работы, ранний срок окончания работы, поздний срок начала работы, поздний срок окончания работы;
- резерв времени на свершение события, полный резерв времени, свободный резерв времени;
- продолжительность критического пути;
Инструкция . Решение в онлайн режиме осуществляется аналитически и графически. Оформляется в формате Word (см. пример). Ниже представлена видеоинструкция.
Пример . Описание проекта в виде перечня выполняемых операций с указанием их взаимосвязи приведено в таблице. Построить сетевой график, определить критический путь, построить календарный график.
| Работа (i,j) | Количество предшествующих работ | Продолжительность t ij | Ранние сроки: начало t ij Р.Н. | Ранние сроки: окончание t ij Р.О. | Поздние сроки: начало t ij П.Н. | Поздние сроки: окончание t ij П.О. | Резервы времени: полный t ij П | Резервы времени: свободный t ij С.В. | Резервы времени: событий R j |
| (0,1) | 0 | 8 | 0 | 8 | 0 | 8 | 0 | 0 | 0 |
| (0,2) | 0 | 3 | 0 | 3 | 1 | 4 | 1 | 0 | 1 |
| (1,3) | 1 | 1 | 8 | 9 | 8 | 9 | 0 | 0 | 0 |
| (2,3) | 1 | 5 | 3 | 8 | 4 | 9 | 1 | 1 | 0 |
| (2,4) | 1 | 2 | 3 | 5 | 13 | 15 | 10 | 10 | 0 |
| (3,4) | 2 | 6 | 9 | 15 | 9 | 15 | 0 | 0 | 0 |
Критический путь: (0,1)(1,3)(3,4) . Продолжительность критического пути: 15.
Независимый резерв времени работы
R ij Н - часть полного резерва времени, если все предшествующие работы заканчиваются в поздние сроки, а все последующие работы начинаются в ранние сроки.
Использование независимого резерва времени не влияет на величину резервов времени других работ. Независимые резервы стремятся использовать, если окончание предыдущей работы произошло в поздний допустимый срок, а последующие работы хотят выполнить в ранние сроки. Если R ij Н ≥0, то такая возможность имеется. Если R ij Н <0 (величина отрицательна), то такая возможность отсутствует, так как предыдущая работа ещё не оканчивается, а последующая уже должна начаться (показывает время, которого не хватит у данной работы для выполнения ее к самому раннему сроку совершения ее (работы) конечного события при условии, что эта работа будет начата в самый поздний срок ее начального события). Фактически независимый резерв имеют лишь те работы, которые не лежат на максимальных путях, проходящих через их начальные и конечные события.