Алгоритм правильной нумерации.

Шаг 1. Нумеруем начальную вершину номером 1. Переходим к шагу 2.

Шаг 2. Удаляем из сети все выходящие из пронумерованных вершин дуги. Нумеруем в произвольном порядке вершины, в которые не входит ни одна дуга, произвольным образом возрастающими по порядку номерами. Шаг 2 проделываем до тех пор, пока не дойдем до конечной вершины, которой при­сваиваем следующий по порядку номер.

В результате правильной нумерации вершин сетевой график, приведен­ный на рис. 4 примет вид

Рис.5

Номера работ на дугах соответственно заменены продолжительностью их выполнения (продолжительность фиктивной работы соответствующей дуги-связи полагаем равной 0).

Рассмотрим основные временные параметры сетевого графика. Пусть t_ij – продолжительность работы, для которой соответствующая дуга (i, j) в сетевом графике имеет в качестве начальной – вершину с номером i, а в качестве конечной – вершину с номером j.

Ранним сроком начала работы (i, j) называется наименьшее допустимое время t_ij^PH, когда может быть начато ее выполнение.

Если работа начата в ранний срок, то время ее окончания t_ij^P0 называется ранним сроком окончания

t_ij^PН = t_ij^PО-t_ij

Ранний срок начала всех работ, для которых вершина i – начальная, называется ранним сроком наступления события i и обозначается T_i^P.

Ранний срок наступления конечного события называется критическим временем и обозначается Т_кр. Таким образом,критическое время – это мини­мальный срок, за который может быть выполнен весь комплекс работ.

Каждый путь из начальной вершины в конечную, состоящий из дуг (работ) и дуг-связей продолжительностью Т_кр, называется критическим путем, а работы, составляющие такие пути – критическими работами.

Поздними сроками начала и окончания работы (i, j) называется наиболь­шее допустимое время начала (t_ij^ПН) и окончания (t_ij^ПO) этой работы без нарушения сроков выполнения всего комплекса работ. Очевидно:

t_ij^ПН = t_ij^ПО-t_ij.

Наиболее поздний из поздних сроков окончания работ, входящих в вершину j, называется поздним сроком наступления события j и обозначается Т_j^П.

Рассмотрим работу (i, j). Плановая продолжительность этой работы равна t_ij. Максимально допустимое время, на которое можно увеличить продолжительность работы (i, j) или задержать начало ее выполнения, при котором не изменится время выполнения всего проекта, называется полным резервом R_ij времени этой работы. Он равен:

R_ij = T_j^П - T_i^P – t_ij.

Резерв времени для работы (i, j), использование которого не изменит ранние сроки наступления всех событий (т.е. все работы смогут начать выполняться в минимально возможные сроки), называется свободным и может быть вычислен по формуле

r_ij = T_j^P - T_i^P – t_ij.

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

Дата добавления: 2017-02-01