Календарное планирование. Сетевые графики и оптимизационные задачи

3. Методы расчета сетевых графиков вручную

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

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

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

Рисунок 3.1. Сетевой график

Этап 1. Заполняем первые три графы табл.3.1, в которые заносим исходные данные по каждой работе: номера начальных событий предшествующих работ, код работы, продолжительность работ. При этом следует начинать с заполнения второй графы, придерживаясь следующего правила: сначала записываем в графу «2» все работы, выходящие из одного события в порядке возрастания номеров — работа первая 1-2, вторая 1-3, работа третья 1-4. Затем проставляются продолжительности работ в графу «3»: для работы 1-2 продолжительность работы на рис. 3.1 показана равной 5, для работ 1-3 и 1-4 — соответственно равной 4 и 2. В графе «1» — номера начальных событий предшествующих работ — проставляем прочерки, т. к. для работ, выходящих из исходного события сетевого графика, предшествующие работы отсутствуют. Закончив запись работ, выходящих из исходного события, переходим к работам, выходящим из второго события. В рассматриваемом графике это работы 2-3 и 2-7 с продолжительностью 0 и 4 и начальным событием 1 предшествующей работы 1-2. Для работ с начальным событием «3» (3-4, 3-5 и 3-6) рассматриваем две предшествующие работы 1-3 и 2-3 и соответственно два начальных события предшествующих работ заносим в графу «1» — 1, 2. В аналогичном порядке рассматриваем все работы сети.

Этап 2. Определяем ранний срок начала и ранний срок окончания работ, заполняя построчно для каждой работы графы 4 и 5. Расчет ведем от исходного события к завершающему событию сетевого графика (см. стрелку в табл.3.1).

Проставляем ранние сроки начала исходных работ, которые равны 0:

Трн1-2 = Трн1-3 = Трн1-4 = 0. Ранний срок окончания работ по формуле (1.1) равен сумме ее продолжительности и раннего начала работы: Троi-j = Tрнi-j + ti-j, тогда, например, для работы 1-2 Тро1-2 = Tрн1-2 + t1-2 = 0 + 5 = 5; для работ 1-3 Трн1-3 = 0 + 4 = 4; для работы 1-4 Трн1-4 = 0 + 2 = 2.

Ранний срок начала неисходных работ равен по формуле (1.3) наибольшему из ранних сроков окончания предшествующих работ данной работе: Трнi-j = max Tроh-i, тогда, например, для работ 2-3 и 2-7 Трн2-3,2-7 = Тро1-2 = 5; для работ 3-4, 3-5 и 3-6 выбираем наибольший срок из Тро1-3 и Тро2-3. Определяем Тро2-3: Тро2-3 = Тро1-2 + t2-3 = 5 + 0 = 5. Наибольшим сроком из Тро1-3 = 4 и Тро2-3 = 5 является Тро2-3 = 5, следовательно, Трн3-4,3-5,3-6 = 5.

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

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

Тро5-8, Тро6-8, Тро7-8 – Ткр = Т6-8 = 17.

Этап 3. Расчет поздних сроков начала и окончания работ выполняем построчно для каждой работы (графы 6, 7 табл. 3.1.) Графы заполняются снизу вверх от завершающего события к исходному событию сетевого графика (см. стрелку в табл.3.1).

Таблица 3.1. Таблица расчета сетевого графика

Поздний срок начала работы равен разности ее позднего окончания и продолжительности работы и определяется по формуле (1.9):

Тпн.i-j = Тпо.i-j – ti-j.

Например, Тпн7-8 = Тпо7-8 – t7-8 = 17 – 3 = 14.

Поздний срок окончания не завершающих сеть работ равен наименьшему из поздних начал работ, следующих за данной работой, например, за работой 3-5 следуют работы 5-7 и 5-8, у которых Тпн5-7 = 14, Тпн5-8 = 15, тогда Тпо3-5 = 14.

Позднее начало хотя бы одной из исходных работ должно быть равно нулю.

Этап 4. Определяем полный и свободный резервы времени и отмечаем знаком «+» работы, лежащие на критическом пути, заполняем графы 8, 9 и 10 таблицы 3.1.

Полные резервы времени работы определяются по формуле (1.11):

Ri-j = Тпн.i-j – Трн.i-j = Тпо.i-j – Тро.i-j.

Например, для работы 1-2 R1-2 = 0 - 0 = 5 – 5 = 0, для работы 3-6 R3-6 = 11 – 5 = 6.

Практически для заполнения графы 8 табл. 3.1 необходимо по каждой строчке определить разность значений граф 7 и 5 или 6 и 4.

Свободные резервы времени работы определяются по формуле (1.12): ri-j = Трн.j-k - Тро.i-j.

Например, для работы 1-2

r1-2 = Трн2-3,2-7 – Тро1-2 = 5 – 5 = 0,

для работы 3-6

r3-6 = Трн6-8 – Тро3-6 = 11 – 5 = 6.

Работы, не имеющие резервов времени, т. е. полный Ri-j и свободный ri-j резервы равны нулю, лежат на критическом пути. Эти работы отмечаем знаком «+» в 10 графе таблицы 3.1 и двойной или цветной линией на сетевом графике.

Расчет сетевого графика ведем непосредственно на самом графике. Для этого сетевой график вычерчивается с увеличенными кружками. Каждый круг делим на четыре сектора (рис.3.2); в каждый сектор записываем определенную информацию.

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

Рисунок 3.2. Содержание секторов событий при расчете сетевого графика графическим методом

Расчет проводим в четыре этапа (рис.3.3).

Рисунок 3.3. Расчет сетевого графика графическим методом

Этап 1. Определяем ранние сроки начала работ, т. е. заполняем левый сектор событий. Расчет ведём от исходного события последовательно к завершающему. Одновременно заполняем и нижний сектор событий. Ранний срок начала последующих работ определяем по формуле (1.3) как наибольший из сумм раннего начала и продолжительности предшествующих работ: Трн.i-j = max (Tрн.h-I + th-i). Например, для работы 4-6 Трн4-6 = mах [(Трн1-4 + t1-4); (Трн3-4 + t3-4)]; Трн4-6 = mах [(0 + 2); (5 + 0)] = 5. Для четвертого событии в левый сектор записываем 5, а в нижний — 3.

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

В левый сектор завершающего события записываем максимальную величину из суммы ранних сроков начала и продолжительностей завершающих работ. Эта величина является продолжительностью критического пути и равна Ткр = Т6-8 = 17.

Этап 2. Определяем поздние сроки окончания работ, т. е. заполняем правый сектор событий. Расчет ведем от завершающего события сети к исходному. Поздний срок окончания завершающих работ равен продолжительности критического пути и поэтому в правый сектор завершающего события 8 записываем рассчитанный в ходе 1 этапа критический срок, равный 17.

Поздний срок окончания предшествующих работ равен минимальной величине разности между поздним сроком окончания и продолжительности этих работ, определяемый по формуле (1.8): Тпо.i-j = min Tпн.j-k = min (Tпо.j-k – tj-k). Например, для работы 3-5 Тпо3-5 = min [(Tпо5-8 – -t5-8); (Тпо5-7 – t5-7)]; Тпо3-5 = min [(17 - 2); (14 - 0)] = 14.

В правый сектор события 5 записываем 14.

Если вычисления выполнены правильно, то в правом секторе исходного события сети должно получиться значение, равное разности между значениями правого и левого секторов завершающего события графика. Для сетевого графика на рис 3.3: 17-17=0 — эта величина записана в правом секторе первого события.

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

Полный резерв времени определяем по формуле (1.11):

Ri-j = Tпн.i-j – Tрн.i-j = Tпо.i-j – Tро.i-j.

Например, для работы 3-5 R3-5 = (Тпо3-5 – t3-5) – Трн3-5 = Тпо3-5 – (Трн3-5 + t3-5) = (14 – 2) – 5 = 14 – (5 + 2) = 7.

Свободный резерв времени определяем по формуле (1.12):

ri-j = Трн.j-k – Tро.i-j.

Например, для работы 3-5 ri-j = Трн5-7,5-8 – (Трн3-5 + t3-5) = 7 – (5 + 2) = 0.

Определение резервов может быть проведено как чисто механическая операция (рис. 3.4):

Рисунок 3.4. Определение резервов времени

Полный резерв времени Ri-j — сумма величин левого сектора события i и продолжительности работы ti-j вычитается из величины правого сектора события j; свободный резерв времени ri-j — эта же сумма величин левого сектора события i и продолжительности работы ti-j вычитается из величины левого сектора события j.

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

В данном сетевом графике критический путь Ткр проходит через события 1, 2, 3, 4, 6, 8 и равен 17. На этом пути лежат работы 1-2, 2-3, 3-4, 4-6, 6-8, для которых полный и свободный резервы времени равны 0.

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