Алгоритм построения критического пути

Алгоритм построения критического пути

Начинают построение с конечной вершины. В её левой трети стоит номер той вершины, при движении из которой определялся ранний срок наступления события. Критический путь идёт из конечной вершины в вершину с этим номером; затем в вершину, номер которой стоит в левой трети полученной при движении вершины, и так до начальной вершины.

Если для критических событий никакие отсрочки их наступления недопустимы без угрозы срыва всего проекта, то для некритических событий такие отсрочки возможны. На нашем графике некритических событий всего три: 2, 5 и 9. Возьмём событие 9. По графику оно наступает через 36 дней после начального события, но могло бы наступить и через 40 дней, если к 40 добавить 11 дней на работу 9 – 10, то получится 51 день, т.е. срок наступления события 10 не будет нарушен. Если же событие 9 наступит через 41 день, то это уже приведёт к отсрочке завершения всего комплекса работ. Таким образом, 40 дней – это наиболее поздний допустимый срок наступления события 9.

Событие 5 совершается через 19 дней после начала работ, но следующее за ним критическое событие 8 наступает лишь через 42 дня, и этот срок не был бы нарушен, если бы событие 5 наступило даже через 37 дней после начального события (42 – 5) = 37). Тогда и событие 2 могло бы наступить через 28 дней после события 1 (37 – 9 = 28).

Таким образом, некритические события наряду с ожидаемым сроком наступления имеют наиболее поздний допустимый срок наступления (даны в скобках у некритических событий). Для критических событий эти сроки совпадают.

Некритические работы также могут иметь известные резервы времени своего выполнения. Возьмём, например, работу 4 – 7. Предшествующее ей события 4 наступает через 11 дней, а завершающие событие 7 – лишь через 30 дней после начала работ. Очевидно, что срок наступления события 7 не был бы нарушен, если бы работа 4 – 7 продолжалась 19 дней – на 15 дней больше её продолжительности по графику. Эти 15 дней и составляют свободный резерв времени работы 4 – 7.

Свободный резерв времени работы 6 – 9 составляет 8 дней (36 – 7 – 21 = 8). Работа 7 – 9, хотя и является некритической, свободного резерва времени не имеет, то же относится к работе 1 – 2 и 2 – 5 (свободные резервы времени указаны на рисунке в скобках у стрелок работ). Ясно, что критические работы резервов времени не имеют.

При определении резервов времени работ можно принять и другую линию рассуждений. Скажем, для работы 6 – 9 максимально допустимое время выполнения составляет 19 дней (резерв 12 дней). Но при такой длительности работ 6 – 9 событие 9 наступит не в ожидаемый, а в наиболее поздний допустимый срок (40 дней), что, как мы видели, сроков выполнения всего проекта не нарушает. Итак, наряду со свободным резервом времени, равным 8 дням, работа 6 – 9 имеет полный резерв времени – 12 дней.

Работа 7 – 9 свободного резерва времени не имеет, однако её полный резерв составляет 4 дня (40 – 6 – 30 = 4). Полные резервы времени, отличные от свободных резервов, имеют также работа 1 – 2 (18 дней), 2 – 5 (18 дней), 4 – 5 (23 дня).

Рекомендуемые материалы

Запишем эти временные характеристики сетевого графика в общем виде:

Поздним сроком окончания работы называется наиболее позднее допустимое время окончания работы без нарушения срока завершения всего проекта  . Поздний срок окончания работы  обозначается   и определяется по формуле: .

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

1. Полагают (срок завершения всего проекта, номер  конечной вершины).

2. Для  вычисляют   (Читается: выбор происходит среди таких  k, что работы    принадлежат множеству дуг, выходящих из вершины  ).

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

Из алгоритма вычисления поздних сроков следует, что увеличение наиболее позднего срока окончания проекта    на    единиц ведёт к увеличению поздних сроков наступления всех событий также на    единиц.

После определения    можно вычислить поздние сроки начала и окончаний всех работ проекта: .

Резервы времени.

Рассмотрим некоторую работу . Найдём время, которое можно выделить для выполнения этой работы без задержки срока окончания всего проекта. Работа  не может быть начата раньше срока    и должна быть закончена не позднее времени  . Для выполнения этой работы нужно затратить не более    единиц времени. По плану эту работу можно сделать за    единиц времени.

Максимально допустимое время, на которое можно увеличить продолжительность выполнения работы  или отложить начало так, что это не вызовет задержки выполнения всего проекта называется полным резервом времени.

Полный резерв времени работы  обозначают  , он равен:

.

Если полный резерв времени некоторой работы равен нулю, то задержка её выполнения вызовет такую же по времени задержку выполнения всего проекта.

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

Найдём время, которое можно дополнительно выделить для выполнения работы  без введения дополнительных ограничений на время выполнения последующих работ. Для этого выполнения работы должно быть законченно к моменту времени  . Таким образом, можно выделить    единиц времени на выполнение работы .

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

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

Во-первых, в проекте могут оказаться “узкие места” с точки зрения обеспечения трудовыми или материальными ресурсами одновременно ведущихся работ. Предположим, например, что при анализе нашего графика – примера обнаружились трудности комплектования исполнителей в период после 21 дня, когда выполняются работы 5 – 8,     6 – 7 и 6 – 9. Эти трудности исчезают с наступлением события 7 (30-й день). Очевидно, что тогда для более равномерного распределения исполнителей можно отсрочить до наступления события 7 начало работы 5 – 8, имеющий значительный свободный резерв времени. Такая отсрочка, как уже отмечалось, отражается на графике введением фиктивной работы.

Во-вторых, в первоначально составленном графике общая продолжительность работ может оказаться выше директивно установленного срока. Чтобы уложиться в этот срок, нужно  очевидно сократить длительность некоторых работ критического пути. Обычно это оказывается возможным, но при условии привлечения на эти работы дополнительных ресурсов. Их можно высвободить за счёт удлинения продолжительности некритических работ, причем вычисленные резервы времени покажут, до какого предела такое удлинение допустимо. (Нужно, однако, учитывать, что при сокращении продолжительности критических работ и увеличении некритических работ сам критический путь может измениться).

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

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

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

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

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

а) оценка    минимального времени, за которое может быть выполнена работа при самом благоприятном стечении обстоятельств   (её называют также оптимистической оценкой).

б) оценка    максимального времени, которое потребуется на выполнение работы при самых неблагоприятных условиях (пессимистическая  оценка)  .

в) оценка      наиболее вероятного времени выполнения работы при нормальных условиях  .

Указанные три оценки и являются основой для расчета её дисперсии. При этом используется гипотеза об определённом законе вероятности длительностей работ (так называемое   - распределение). В алгоритмическом смысле гипотеза даёт возможность построить простые формулы определения для каждой работы средней ожидаемой продолжительность    и дисперсии    при заданных    и   .

.

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

Алгоритм расчёта сетевого графика с вероятностным временем выполнения операций включает следующие основные этапы:

1. Расчёт ожидаемого времени выполнения работ    и дисперсии .

.

2. Расчёт наиболее раннего возможного срока наступления конечного события   (алгоритм изложен ранее).

3. Определение аргумента нормальной функции распределения вероятностей  .

4. По определённому аргументу, используя данные таблицы 10.3, определяется вероятность свершения завершающего события в заданный срок  .

Построение сетевой модели

Таблица 10.3

В качестве расчётного времени выполнения операций принимается ожидаемое время (таблица 10.4).

                                                                   Таблица 10.4