Расчет временных параметров сетевого графика 2.2.1. Расчет критического пути

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

Путь, имеющий наибольшую протяженность, называется критическим путем . Протяженность критического пути обозначаем t ( ) или .

Замечание. В сети может быть несколько критических путей.

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

Ранним сроком (j) свершения события j называется самый ранний момент времени, к которому завершаются все предшествующие этому событию работы. Счет времени ведется от момента наступления начального события. Ранний срок начального события равен 0. (0) = 0. Ранний срок любого другого j-гo события определяется продолжительностью самого длительного из предшествующих путей. Определяем ранние сроки свершения событий по рекуррентному соотношению:

Полный срок наступления события - время, при котором планируемый срок окончания проекта не меняется. Обозначается (i) - для i -гo события.

Замечание. Для завершающего события К поздний срок наступления совпадает с ранним, т. е.

(К) = (К).

При определении поздних сроков наступления события расчет ведут от завершающего события к исходному. Каждую вершину орграфа (событие сетевой модели) разобьем на 3 сектора: в нижнем проставляем номер события; в левом - ранний срок; в правом - поздний срок.

Резервы времени каждого события находятся по формуле:

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

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

Если какое-то событие i наступает позднее (i), то принимают меры для ускорения работ в этой части проекта. Если ускорить работу не удается, то полный срок выполнения проекта будет превышен. Время, на которое задерживаются все работы, можно тоже вычислить по сетевому графику.

Метод расчета сетевых графиков выполняется в четыре этапа:

1. Определение ранних сроков наступления событий (i)

2. Нахождение критического пути

3. Определение поздних сроков наступления события (i)

4. Определение резерва времени события.

Замечание. Использование независимого резерва времени на i-й работе, которая его имеет, не влияет на ранние и поздние сроки совершения всех событий и работ сети. Его нельзя передать ни предшествующим, ни последующим работам.

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

где t ( ) - продолжительность максимального пути, проходящего через работу (i, j);

- продолжительность отрезка рассматриваемого пути, совпадающего с критическим путем.

Коэффициент напряженности изменяется от 0 до 1. Чем ближе он к 1, тем сложнее выполнить данную работу в установленный срок.

Самыми напряженными являются работы критического пути, для которых = 1.

На основе этого коэффициента все работы сетевого графика подразделяются на три группы:

1) (i,j) > 0,8 - напряженные;

2) 0,6 < (i,j) < 0,8 - подкритические;

3) (i,j) < 0,6 - резервные.

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

Пример 1. Ставропольский кондитерский цех решил закупить новое оборудование. Исходные данные по основным операциям проекта представлены в таблице. Необходимо построить сетевую модель проекта, определить временные параметры модели, критический путь и проанализировать, как влияет на ход выполнения проекта задержка определенного типа оборудования на 12 часов.

Решение. Построим сетевую модель по условию задачи.

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

Найдем ранние сроки наступления событий:

Найдем поздние сроки наступления событий для завершающего события 6 (6) = (6).

(5) = (6)-t (5, 6) = 52 -18 = 34.

(4) = (5) – t (4, 5) = 34-19 = 15.

(3) = min { (4); (2)} = min {15, 16} = 15.

(2) = (5) – t (2, 5) = 34 - 18 = 16.

(1)=min { (2) -t (1, 2); (3) - t (1, 3);

(4) - t (1, 4)} =min {6; 0; 10} = 0

При поиске критических путей на сетевом графике будем использовать следующие условия его критичности:

• необходимое условие - нулевые резервы событий, лежащих на критическом пути;

• достаточное условие - нулевые полные резервы работ, лежащих на критическом пути.

Согласно необходимому условию два полных пути сетевой модели могут быть критическими:

L₁ =1, 3, 4, 5, 6 и L₂ =1, 4, 5, 6. Проверим достаточное условие критичности для работ (1, 3) и (1, 4)

Путь L₂, начинающийся с работы (1, 4) не является критическим, так как минимум одна (1, 4) из его работ не является критической. Работа (1, 4) имеет не нулевой полный резерв, а значит, может быть задержана с выполнением, что недопустимо для критических работ.

Таким образом, сетевая модель имеет единственный критический путь ,=1, 3, 4, 5, 6, длительностью

= 52 часа. За выполнением работ этого пути необходим особый контроль, так как любое увеличение их длительности нарушит срок выполнения проекта в целом.

Работа А или (1, 2) не является критической, ее полный резерв равен 1 часу.

Это означает, что при задержке работы в пределах 1 часа срок выполнения проекта не будет нарушен. Поэтому, если согласно условию работа А задержится на 12 часов, то весь проект задержится на 11 часов.

Пример 2. Компания «АВC» реализует проекты серийного производства различных видов продукции. Каждый проект обеспечивает получение в неделю 100 тыс. у. д. е. дополнительной прибыли. Перечень работ и их характеристики представлены в таблице.