Временные параметры сетевых графиков

Для сетевых графиков справедливо следующее утверждение: из всех путей, соединяющих Р₀ и Р_n, критическим, т.е. имеющим максимальную длину T_n⁽⁰⁾, является только тот путь, для всех дуг (Р_i, Р_j) которого выполнено условие:

Свободным резервом времени работы (P_i, P_j) называется разность T_j⁽⁰⁾–T_i⁽⁰⁾–t_ij. Для любой работы, входящей в критическую последовательность, свободный резерв времени равен нулю, а для работ, не лежащих на критическом пути,

Вводится также временные параметры — максимальные времена наступления событий Максимальное или наиболее позднее время T_j⁽⁰⁾ наступления события Р_j означает, что окончание в момент T_j⁽¹⁾ всех работ, входящих в Р_j, не помешает окончанию всего комплекса работ за время Т_n; т.е. T_j⁽¹⁾ — наиболее позднее время окончания всех работ, входящих в P_j, T_j⁽¹⁾ равно разности между Т_n и максимальной длиной пути из Р_j, в Р_n.

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

Работа (Р_i, P_j) входит в некоторый критический путь тогда и только тогда, когда

Величина T_j⁽¹⁾–T_j⁽⁰⁾–t _ij называется полным резервом времени работы (Р_i, Р_j) Rn_(ij).

Полный резерв — это максимальное количество времени, которое необходимо для увеличения продолжительности выполнения работы (Р_i, Р_j) (если, конечно, это допустимо характером работы) без увеличения времени Т_n выполнения проекта.

Полный резерв означает также максимальное количество времени, на которое можно опоздать с началом работы (Р_i, P_j),по сравнению с наиболее ранним возможным временем ее начала T_i⁽⁰⁾, не увеличивая при этом времени Т_n выполнения проекта.

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

Полный резерв у критических работ равен нулю Некритические работы обладают ненулевым полным резервом.

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

Опоздание начала некритической работы (P_i, P_j) по сравнению с T_i⁽⁰⁾ на всю величину ее полного резерва повлечет за собой необходимость начинать все работы, выходящие из события Р_j, в наиболее позднее допустимое время T_j⁽⁰⁾ наступления этого события.

Свободный резерв времени T_j⁽⁰⁾–T_i⁽⁰⁾–t_ij работы (Р_i, Р_j), определенный выше, — это максимально допустимое увеличение продолжительности этой работы (или запаздывание ее начала по сравнению с наиболее ранним возможным временем ее начала T_i⁽⁰⁾), не нарушающее возможности начинать все работы (Р_i, Р_j), выходящие из Р_j, в наиболее раннее допустимое время T_j⁽⁰⁾.

Увеличение продолжительности работы (P_j, P_i) на часть ее свободного резерва T_j⁽⁰⁾–T_i⁽⁰⁾–t_ij может уменьшить полный резерв T_i⁽⁰⁾–T_k⁽⁰⁾–t_ki работ (Р_k, Р_i), входящих в событие Р_i, (конечно, если T_i⁽⁰⁾¹T_i⁽¹⁾), и не влияет на резервы работ, выходящих из события Р_j.

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

Кроме полного и свободного резервов времен работы (Р_i, Р_j), вводится еще понятие ее независимого резерва времени, который определяется по формуле (2.4):

(2.4)

Смысл независимого резерва заключается в том, что он означает максимально допустимое количество времени для увеличения продолжительности работы (Р_i, Р_j) или запаздывания ее начала при условии, что все работы (P_k, P_i), входящие в событие Р_i, заканчиваются в наиболее позднее допустимое время T_i⁽¹⁾, а все работы (P_j, P_i), выходящие из Р_j, начинаются в наиболее раннее допустимое время T_j⁽⁰⁾.

Таким образом, использование на работе (Р_i, Р_j) ее независимого резерва совершенно не влияет на резервы других работ.

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

Сетевой график, хотя и дает четкое представление о порядке следования работ, все же недостаточно нагляден для определения тех работ, которые должны выполняться в каждый данный момент времени, поэтому, в случае небольшого проекта, после составления пронумерованного сетевого графика рекомендуется составлять так называемую линейную диаграмму проекта. Линейная диаграмма — сетевой график, в котором каждая работа изображается параллельным оси времени отрезком, длина которого равна продолжительности этой работы, Фиктивная работа изображается точкой.

На горизонтальной оси наносится равномерная шкала времени t. Каждая работа изображается отрезком или полоской, параллельной оси времени, длиной, равной продолжительности этой работы (фиктивная работа нулевой продолжительности изображается точкой). События Р_i и Р_j — начало и конец работы (Р_i, Р_j) — ставят соответственно в начале и в конце полоски. Полоски, располагают одну над другой, снизу вверх, в порядке возрастания индекса j (окончания работы (Р_i, Р_j), а для работ, входящих в одно и то же Р_j — в порядке возрастания индекса i (начала работы). Момент наступления события Р₀ считают началом проекта и полагают его равным нулю, т.е. полоски (Р₀, Р_j) откладывают от вертикали t=0. Полоску (Р_i, Р_j) откладывают так, чтобы ее начало Р_i лежало на одной вертикали с самым правым концом всех полосок-работ (P_k, P_i), заканчивающихся в Р_i.

Таким образом, начало полоски (Р_i, Р_j) соответствует минимальному времени T_i⁽⁰⁾ наступления события P_i.

На рис. 16 приведена линейная диаграмма сети рис. 15.

Рис. 15. Пример сетевого графика

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

Критическое время проекта равно координате по оси времени самого правого конца всех полосок линейной диаграммы. В этом случае критическое время T_i⁽⁰⁾ равно 15.

Критический путь можно найти по диаграмме следующим образом. Рассматриваем полоски-работы с последним событием (Р₇) в правом конце, заканчивающиеся в критическое время, т.е. полоски, правый конец которых расположен на вертикали критического времени (на рис. 16 — это работы (Р₅, Р₇) и (Р₄, Р₇)).

Затем из полосок-работ, конечные события которых совпадают с начальными событиями (Р₅ и Р₄) рассмотренных полосок, выбираем те, у которых правые концы расположены на одной вертикали с левыми концами рассмотренных полосок (на рис. 16 — это работы (Р₁, Р₅) и (Р₃, Р₄)). Продолжаем так выделять полоски, пока не придем к полоскам, начинающимся в Р₀ (на рис. 16 — к полоскам (Р₀, P₁) и (Р₀, Р₃)). Выделенные полоски-работы образуют совокупность всех критических работ (на риc. 16 заштрихованы) и позволяют обнаружить все критические пути.

На рис 16 получилось два критических пути (P₀, P₁, P₅, P₇) и (P₀, P₃, P₄, P₇) которые выделены двумя ломаными.

Рис. 16. Линейная диаграмма сети

Свободный резерв времени T_j⁽⁰⁾–T_i⁽⁰⁾–t_ij работы (P_i, P_j) на линейной диаграмме определяется как наибольшая длина отрезка, на который можно сдвинуть вправо полоску (P_i, P_j), не сдвигая ни одной из полосок (P_i, P_j), т.е. не изменяя начало T_j⁽⁰⁾ работ (P_j, P_i), выходящих из события P_j.

На рис. 16 свободный резерв, например, работы (P₁, P₀) равен 3, т.к. полоску (P₁, P₆) можно сдвинуть вправо на 3, не сдвигая полоски (P₆, P₇). Работа же (P₅, P₆) не имеет свободного резерва, т.к. любой сдвиг вправо полоски (P₅, P₆) возможен лишь при таком же сдвиге полоски (P₆, P₇).

Для отыскания полных резервов времени покажем сначала, как определить по линейной диаграмме максимальные времена T_j⁽¹⁾ наступления событий P_j.

Для этого сдвигаем вправо до вертикали критического пути полоски работы, правым концом которых служит последнее событие (на рис. 17 это показано пунктиром для полоски работы (P₆, P₇)). Спускаясь затем сверху вниз сдвигаем одну за другой все полоски вправо на максимально допустимые отрезки (может быть нулевой длины), т.е. так чтобы правые концы P_j сдвигаемых полосок попали на одну вертикаль с самым левым концов P_j уже сдвинутых полосок. Этот самый левый конец P_j ранее сдвинутых полосок определяет (по шкале времени) максимальное время T_j⁽¹⁾ наступления события P_j. На рис. 17 сдвинутые работы (P₆, P₇), (P₅, P₆), (P₁, P₆), (P₃, P₅), (P₂, P₄), (P₂, P₃), (P₁, P₃), (P₀, P₂) показаны пунктиром.

Объясним сдвиг, например, полоски работы (P₀, P₂). Из двух ранее сдвинутых полосок (P₂, P₃) и (P₂, P₄) левее оказалось начало полоски (P₂, P₃). Вертикаль t=3 этого начала определяет конец сдвигаемой полоски (P₀, P₂), а также максимальное время T₂⁽¹⁾ наступления события P₂.

Теперь по полученной после сдвигов линейной диаграмме полный резерв времени T_j⁽⁰⁾–T_i⁽¹⁾–t_ij работы (P_i, P_j) определяется как величена ее сдвига, т.е. как длина отрезка от старого положения P_j (до сдвига) до нового положения P_j (после сдвига).

Например, полные резервы работ (P₁, P₆) и (Р₃, Р₅) равны соответственно 4 и 1; последний совпадает со свободным резервом работы (Р₃, Р₅).

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

Рис. 17. Анализ сетевого графика с помощью линейной диаграммы