Транзитивное замыкание отношения предшествования. Построение конституент для множеств полных предшественников

Длина критического пути 1_кр — это основная характеристика сетевого графика. Смысл ее состоит в том, что если каждая работа i,j будет начинаться в тот момент, когда произойдет событие г (раньше она начаться не может), и выполняться точно за время tij, то вся совокупность работ будет выполнена за время, равное длине критического пути 1_кр.

Опишем алгоритм для построения критического пути в сетевом графике.   В процессе работы алгоритма для каждой вершины i рассчитывается величина t_p(i) — максимальная длина пути из начала в вершину i.

2.1.  Правильная нумерация сети.

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

22.          Расстановка отметок.

Пусть сеть правильно занумерована. Для каждой вершины i вычисляем отметку t_p{i) по следующим правилам:

-  полагаем t_p(0) равным нулю;

-  просматриваем вершины в порядке их номеров и для j-й вершины вычисляем *   t_p{j) по формуле

t_p(j) =

где максимум берется по всем вершинам i, имеющим дугу (i,j), направленную в вершину j.

По окончании процесса вычисления отметок величина 1_кр может быть найдена как отметка концевой вершины.

2.3. Построение критического пути.

Начиная с вершины-конца, последовательно находим дуги (i,j), для которых t_p(j) — t_p(i) = tij. Эти дуги и образуют критический путь.

8

Резервы времени и коэффициенты напряженности

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

Для каждого события можно рассчитать также поздний срок его свершения t_n(i). Смысл этого параметра состоит в следующем: если событие i "запоздает", однако, произойдет не позднее t_n(i), то длина критического пути, то есть время выполнения всего проекта не изменится.

Схема расчета поздних сроков получается, если схему расчетов t_p(i) "вывернуть наизнанку". Пусть сеть правильно занумерована и концевая вершина получила номер

N.                                                      ;                                        полагаем t_n(N) = 1_кр ;

-  просматриваем вершины в обратном порядке их номеров и для   i-й  вершины вычисляем t_n(i),) по формуле

-                                                                   

где минимум берется по всем вершинам  j,   в которые ведут дуги   (i,j)   из вершины i.

Резервом времени работы (i,j) называется величина P(i,j) = t_n(j) — t_p(i) — tij. Задержка в выполнении работы на величину, не превышающую P(i,j), не изменяет длину критического пути, то есть срока выполнения проекта.

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

ПРИМЕНЕНИЕ  СТАТИЧЕСКОГО МОДЕЛИРОВАНИЯ В СИСТЕМАХ СПУ

3.1.Общая блок-схема алгоритма статического моделирования.

«Розыгрыш» значения продолжительности выполнения каждой из работ