Сетевой анализ и календарное планирование проектов

Рис. 6. Новый чертеж стрелочного  графа для примера 1 

Пример 2. Компания "Delco plc" является участником другого проекта, детали которого приведены ниже:

Таблица 2. Таблица операций для примера 2

Изобразим данный проект при  помощи стрелочного  графа. 

Решение

     Построение  начинаем с начального события, обозначенного  кружком 1. Из таблицы  следует, что существуют три операции —  А, В и С, которым не предшествует ни одна из операций. Поэтому из начального события выходят три стрелки. На первый взгляд таблица операций выглядит чрезвычайно простой, однако отразить присущую ей логику с помощью сетевого графа достаточно трудно, вследствие чего мы вынуждены использовать три фиктивные логические операции (см. рис. 7).

Рис. 7. Стрелочный граф для примера 2 
 

     1.2 Вершинные графы 

     В этом типе сетевых графов операции представлены узлами графа, а стрелками  изображаются их взаимосвязи. В таких  графах не возникает необходимости  вводить фиктивные операции. Как  и в предыдущем случае, течение  времени следует изображать в  направлении слева направо. 

     Пример  3. Обратившись к данным из примера 2, модифицируем полученную в этом примере схему, поставив в соответствие операциям узлы графа. 

Решение

     Логическую  схему, приведенную  в данном примере, гораздо проще  проиллюстрировать  используя метод  построения сетевых  графов по схеме "операция- узел", однако с его помощью труднее получить общую картину переходов от одной операции к другой. Построение вершинного графа начинают с начального узла, за которым следуют первые три операции — А, В и С. Построить такой граф достаточно просто. 

 

Рис. 8. Вершинный граф 

     Каждый  из описанных типов  графов имеет свои преимущества и недостатки. Обычно не имеет принципиального  значения, какая из систем используется. Если в стрелочные графы приходится вводить достаточно большое число  фиктивных операций, то гораздо более  предпочтительным является выбор вершинного графа. Ниже приведено  сравнение двух видов  изображения операций и их основных особенностей (см. рис. 9). 
 
 
 
 
 

     2 Анализ критического пути  

     После того как проведена идентификация  операций, можно оценить их продолжительность. На основе продолжительности выполнения каждой операции и руководствуясь логической схемой, можно найти время выполнения проекта в целом. На данном этапе  предполагается, что продолжительность  выполнения каждой операции является фиксированной величиной, не испытывающей влияния неопределенности. В последнем  разделе главы мы рассмотрим вопрос о том, какие поправки следует  внести в этот анализ, чтобы учесть неопределенность времени выполнения операций. В каждом графе существует несколько возможных путей. Общее  время, необходимое для того, чтобы  пройти какой-либо путь, есть сумма  времени выполнения всех операций, принадлежащих данному пути. Продолжительность  выполнения всего проекта занимает наибольшее время. Более длительные операции называются критическими. Любая  задержка срока начала или окончания  выполнения этих работ повлечет за собой задержку срока выполнения проекта в целом. Критические  операции образуют непрерывную цепь, проходящую через весь граф. Эта  цепь критических операций называется критическим путем. В каждом графе  найдется по крайней мере один критический путь. 

 

Рис. 9. Сравнение  сетевых стрелочного и вершинного графов 

     Для того чтобы найти общую продолжительность  выполнения проекта, нужно определить продолжительность критического пути. В большинстве графов идентифицировать все идущие сквозь граф пути, чтобы  выявить среди них тот, который  занимает наибольшее время, достаточно трудно. Существуют два возможных  метода, позволяющих отследить движение времени в графе:

1. Определение  для  каждой операции  наиболее  ранних  сроков  начала и окончания  ее выполнения.

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

     2.1 Анализ критического пути с применением вершинных графов 

       Пример 4. В табл.3 указана продолжительность выполнения каждой операции проекта, о котором шла речь в примерах 2 и 3. Определим общую продолжительность выполнения проекта.

Таблица 3. Операции и их продолжительность  для примера 10.4

Вершинный граф, соответствующий  данному проекту, был построен в  примере 3. 

Решение

     Предположим, что каждая из исходных операций А, В и С начинается в нулевой момент времени. Это наиболее ранний срок начала этих ES операций. Наиболее ранний срок, к которому их выполнение может быть завершено, определяется следующим образом: 

Наиболее  ранний срок окончания  EF=ES+ Продолжительность операции. 

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

Таблица 4. Расчет наиболее ранних сроков начала и окончания  операций для примера 4

     Наиболее  ранние сроки начала и окончания операций занесены в вершинный  граф, изображенный на рис. 10.10. Нетрудно заметить, что операция Н завершится на 39-й  день, следовательно, это значение дает нам искомую продолжительность  выполнения проекта  в целом.

Рис. 10 Вершинный граф для примера 4 

     На  данном этапе мы еще  не можем определить критические операции. Чтобы это осуществить, необходимо для каждой операции рассчитать два срока, ей соответствующие, а именно наиболее поздний срок начала LS и наиболее поздний  срок окончания LF операции. В данном случае процедуру  расчетов мы начнем с последней операции в графе и предположим, что наиболее поздний  и наиболее ранний сроки ее окончания  совпадают. Затем  вычитанием из этой величины продолжительности  выполнения операций находим наиболее поздний срок ее начала. Ход выполнения расчетов показан в табл.5.

Таблица 5. Расчет наиболее поздних  сроков начала и окончания  операций для примера 4

Критической является операция, для которой справедливы  следующие соотношения : 

ES = LS                   и                 EF = LF, 

т. е. операция, для которой  не существует резерва  времени между  наиболее ранним сроком ее начала и наиболее поздним сроком ее окончания. Нетрудно заметить, что в  нашем примере  критическими являются операции В, Е, G и Н. Путь в вершинном графе, соединяющий эти операции, называется критическим путем. В нашем примере критическим является путь В —Е —G —H. 

     2.2 Анализ критического пути с применением стрелочных графов 

     Приведенная выше методика анализа аналогичным  образом может использоваться и  для стрелочных графов. Значения сроков ES, EF, LS и LF записываются в графе вдоль  стрелок, соответствующих операциям:

Рис.11. Нанесение на стрелочный граф сроков, соответствующих операциям

     Можно провести подобный анализ в терминах сроков наступления каждого  события. Производится расчет наиболее раннего  срока, к которому может завершиться  каждое событие. Этот срок называется наиболее ранним сроком события (earliest event time - ЕЕТ). Общая продолжительность выполнения проекта определяется ЕЕТ конечного узла графа. ЕЕТ исходного события равен нулю.

     Для того чтобы выявить  критические операции, необходимо, начиная  с конца графа, вычислить наиболее поздние сроки  событий (latest event time - LET), к которым события могут закончиться. События, для которых выполняются соотношения

LЕТначала - ЕЕТокончания + продолжительность = 0

или 

ЕЕТначала - LЕТокончания + продолжительность = 0,

являются  критическими. 

Пример 5. Применив ЕЕТ и  LET, повторим задачу из примера 10.4 при условии, что продолжительность выполнения фиктивных операций равна нулю. 

Решение

     В первую очередь для  каждого события  вычислим значение наиболее раннего срока. Если некоторому событию  соответствует более  одной операции, появляется проблема выбора соответствующего значения. Поскольку  событие считается  незавершенным до тех пор, пока не будет  завершено выполнение всех составляющих его  операций, следует  выбрать наибольшее из значений.