Для расчета параметров сетевых моделей применяют следующие три метода:
– метод вычислений непосредственно на сетевом графике;
– матричный метод,
– табличный метод.
Все эти методы основываются на формулах (6), (7) и отличаются только процедурами вычислений.
Метод вычислений на сетевом графике. Предварительно каждый кружок, изображающий вершину графика (событие), делится на четыре сектора: в верхний сектор записывается номер события k, в левый – значение Тk(p), в правый – Tk(n), а в нижний – Rk = Tk(n) – Тk(p) (рис. 3).
Согласно формуле (6) ранний срок наступления данного события определяется как сумма раннего срока непосредственно предшествующего события и длины дуги (продолжительности работы), которая их соединяет.
Если к событию подходят две или большее число дуг, то вычисляют указанные суммы для каждой из входящих дуг; максимальная из сумм и есть ранний срок наступления данного события, который записывается в левый сектор.
Расчет ведется последовательно от исходящего события к завершающему.
При расчете параметров сетевой модели непосредственнонаграфике можно не нумеровать события так, чтобы выполнялось условие i < j для любой дуги (i, j).
Рис. 3 Упрощенный граф отношения «быть делителем»
Матричный метод. Метод сводится к простым формальным операциям над величинами tij без необходимости обращаться к графику. Процедуру расчета рассмотрим на примере сетевой модели, изображенной на рис. 3
Представим сетевой график в виде матрицы смежности, но вместо единиц запишем соответствующие значения tij. В результате получим табл. 2 (в таблицу также записаны величины Ti(p) и Tj(n), которые еще нужно вычислить).
Таблица может быть составлена как по сетевому графику, так и по упорядоченному перечню событий и работ.
Правило определения раннего срока событий вытекает из выражения (6) и формулируется следующим образом: ранний срок события с номером j, j=1̅,̅N̅ равен сумме элемента матрицы tij с ранним сроком предшествующего события, причем если предшествующих событий несколько, то берется максимальная из сумм, результат записывается в строку с номером i=j.
Так как ранний срок нулевого события равен нулю, то сразу записывают в нулевую строку значение T 0 (p) = 0. Дальше последовательно просматриваются столбцы (последующие события), начиная с первого (j =1). Из матрицы видим, что событие 1 связано только с одним предшествующим событием, а именно – с нулевым, причем t 0,1=20. Складываем t 0,1 со значением Т 0 (p) = 0, записанным в столбце Тi(p) по нулевой строке, а результат t 0,1+ T 0 (p) = 20 записываем в первую строку в столбец Тi(p). Это и будет значение T 1 (p).
Переходим ко второму столбцу (j =2). Событие 2 связано с двумя предшествующими событиями: 0 и 1, причем t 0,2=45; t 1,2=0. Составляем две суммы t 0,2+ Т 0 (p) =45+0=45; t 1,2 +T 1 (p)= 0+20=20 и большую записываем во вторую строку в столбец Тi(p).
Таблица 2 Матрица смежности
j i | Ранний срок Tj(p) | |||||||||||
Поздний срок Tj(n) |
Рассмотрим еще восьмой столбец (j =8). Событие 8 связано с тремя предшествующими событиями 5, 6 и 7. Составляем суммы 10+85=95; 10+105=115; 5+105=110 и в восьмую строку в столбец Тi(p) записываем наибольшую, равную 115.
Правило вычисления позднего срока события следует из выражения (10) и формулируется следующим образом: поздний срок события с номером i, i=N̅-̅1̅,̅1 определяется путем вычитания элемента матрицы tij из позднего срока последующего события, причем если последующих событий несколько, то берется минимальная из разностей; результат записывается в столбец с номером j = i.
Вычисления начинают с завершающего события и сразу записывают в столбец для j=N величину TN(n)= ТN(p). В нашем случае в столбец для j =10 записывают Т 10 (n) =305. Теперь просматриваем последовательно строки, начиная с N– 1 (в нашем случае девятой). Из таблицы видно, что событие 9 связано с одним последующим событием 10, причем t 9,10=100. Вычитаем согласно правилу из T 10 (n) =305 величину t 9,10=100 и разность, равную 205, записываем в девятый столбец в строку Тj(n). Это и будет величина T 9 (n) =205.
Переходим к следующей, восьмой строке (i =8). Событие 8, как видно из матрицы, связано с одним последующим событием 9, причем t 8,9=90. Составим разность 205–90=115 и результат запишем в восьмой столбец в строку Tj(n).
Рассмотрим пятую строку. Событие 5 связано с двумя последующими событиями 7 и 8, а соответствующие элементы матрицы t5,7=0 и t 5,8=10. Составляем две разности 110–0=110; 115–10=105 и меньшую из них запишем в пятый столбец в строку Tj(n). Это и будет T 5 (n) =105.
Остальные параметры вычисляют по формулам (8) – (14), записывают их в табл. 2 и определяют критический путь.
Табличный метод в принципе не отличается от изложенных методов и преимуществ перед ними не имеет.