Первый этап построения графа (установление связей в графе)

Показываем первую (самую верхнюю) окружность с секторами (рис. 3).

От этой окружности стрелкой показываем работу A1, в скобках записываем её продолжительность (20). Стрелку упираем в новую окружность с секторами.

Аналогично показываем работы A2 и A3, упирающиеся в свои окружности.

Для работы A4 создаём две новые окружности (входную и выходную), Сплошной стрелкой между ними обозначаем работу A4, в скобках записываем длительность работы (40). Во входную окружность штриховыми стрелками проводим фиктивные работы, соответствующие работам A1 и A3, которые являются предшествующими для работы А4.

Для работы A5 создаём следующие две окружности. От входной окружности вниз показываем стрелку работы A5, в скобках записываем её длительность (5). Во входную окружность штриховыми стрелками проводим фиктивные работы, соответствующие предшествующим работам A2 и A3.

Аналогично для работы A6 создаём свои окружности. Во входную окружность штриховыми стрелками проводим фиктивные работы, соответствующие работам A4, A2 и A3. От входной окружности вниз к выходной окружности показываем работу A6, в скобках записываем её длительность (20).

Подобные построения выполним для оставшихся работ A7, A8, A9, A10.

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

Рис. 3

3.2.2. Второй этап построения графа – определение ранних сроков начала и окончания работ (прямой проход)

В верхнем секторе самой первой окружности записываем 0, что соответствует моменту начала всего плана. В нашем примере нулевой момент времени является ранним сроком начала работ (РСНР) A1, A2 и A3.

С учётом продолжительности этих работ в верхних секторах их выходных окружностей записываем соответствующие ранние сроки окончания работ (РСОР): 20, 60, 45.

Далее переходим к работе A4. По входящим штриховым стрелкам видим, что эта работа должна начаться тогда, когда закончатся предшествующие работы (A1 и A3). Поэтому в верхнем секторе входной окружности работы A4 записываем время её начала (РСНР), соответствующее максимальному значению из 20 и 45, т.е. 45. В верхнем секторе выходной окружности работы A4 записываем ранний срок окончания работы (РСОР), равный сумме времени начала и продолжительности: 45 + 40 = 85.

Переходим к работе A5. Судя по штриховым входящим стрелкам, эта работа должна начаться тогда, когда закончатся предшествующие работы A2 и A3. Поэтому в верхнем секторе входной окружности работы A5 записываем время её начала (РСНР), соответствующее максимальному значению из 60 и 45, т.е. 60. В верхнем секторе выходной окружности работы A5 записываем время окончания работы, равное сумме времени начала и продолжительности: 60 + 5 = 65. Это есть РСОР.

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

Для работы A6 РСНР равен 85, что соответствует наибольшему из ранних сроков окончания предшествующих работ А4, А2 и А3: max{85;60;45} = 85. С учётом продолжительности А6 РСОР равен 85 + 20 = 105 (запишем в верхний сектор выходной окружности).

Для работы А7: РСНР равен 85, т.к. max{85;65} = 85. РСОР равен 85 + 20 = 105.

Для работы А8: РСНР равен 105, т.к. max{105;105} = 105. РСОР равен 105 + 40 = 145.

Для работы А9: РСНР равен 105, т.к. max{20;105;45} = 105. РСОР равен 105 + 10 = 115.

Для работы А10: РСНР равен 145, т.к. max{145; 85;45} = 145. РСОР равен 145 + 20 = 165.

В верхнем секторе заключительной окружности запишем ранний срок выполнения всей операции: max{165;115} = 165.

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

3.2.3. Третий этап построения графа – определение поздних сроков начала и окончания работ (обратный проход)

Записи будем делать в нижние сектора окружностей. Расчёты начинаем с заключительной окружности. В нижнем её секторе записываем то же число, что и в верхнем секторе, т.е. 165.

Это же число записываем в нижние сектора выходных окружностей работ А10 и А9. Эти значения соответствуют поздним срокам окончания этих работ (ПСОР).

В нижний сектор входной окружности работы А10 с учётом её длительности 20 запишем 165 - 20 = 145, что соответствует позднему сроку началу этой работы (ПСНР).

Аналогично в нижний сектор входной окружности работы А9 с учётом её длительности 10 запишем 165 – 10 = 155, что соответствует позднему сроку началу этой работы (ПСНР).

Для работы А8 в нижний сектор выходной окружности записываем то же число, что и в нижнем секторе входной окружности работы А10, т.е. 145. В нижнем секторе входной окружности работы А8 с учётом времени её выполнения записываем 145 – 40 = 105.

В нижний сектор выходной окружности работы А7 запишем величину 105, т.к. min{105;155} = 105 (эта работа должна быть закончена до начала работ А8 и А9). В нижний сектор входной окружности работы А7 с учётом её длительности 20 записываем 105 – 20 = 85.

Для работ А6 и А5 в нижние сектора выходных окружностей переносим значения из нижних секторов входных окружностей работ А8 и А7 (105 и 85). В нижние сектора входных окружностей работ А6 и А5 с учётом их длительностей 20 и 5 записываем 105 – 20 = 85 и 85 – 5 = 80.

В нижний сектор выходной окружности работы А4 вносим min{145;85;85} = 85. В нижний сектор входной окружности работы А4 с учётом её длительности 40 записываем 85 – 40 = 45.

В нижний сектор выходной окружности работы А3 вносим min{45;80;85;145;155} = 45.

В нижний сектор выходной окружности работы А2 вносим min{85;80} = 80.

В нижний сектор выходной окружности работы А1 вносим min{45;155} = 45.

Проверяем, не оказалось ли, что разность между ПСОР для А1, А2 и А3 и их продолжительностью стала отрицательной. Для работы А1: 45 – 20 = 25. Для работы А2: 80 – 60 = 20. Для работы А3: 45 – 45 = 0. Эти значения не отрицательны, они соответствуют резерву времени, в течение которого работа не выполняется. Ненулевой резерв позволяет работу сдвигать в полученных пределах. Отсутствие резерва времени соответствует критической работе, начало и конец которой строго фиксированы. Критической в рассматриваемом примере является работа А3.

В заключение построения графа жирными сплошными линиями выделим критические работы, характерные тем, что у них совпадают РСНР и РСОР, а также ПСНР и ПСОР. Иными словами, выделим работы, у которых одинаковыми являются числа, записанные в верхнем и нижнем секторах входной окружности и в верхнем и нижнем секторах выходной окружности. В рассматриваемом примере критическими работами являются А3, А4, А6, А7, А8, А10.

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

На этом третий этап (обратный проход) построения графа заканчивается.

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

Так, например, для работы А5 можно назвать возможные сроки начала и окончания. Верхние сектора этой работы дают РСНР = 60, РСОР = 65, а нижние сектора: ПСНР = 80, ПСОР = 85.

Следовательно в зависимости от сроков других работ данная работа А5 может выполняться в течение 5 единиц времени в интервале не ранее 60 и не позже 85 единиц.