Расчет параметров сетевого графика

 

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

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

Путь от исходного события до любого взятого предшествует данному событию. Предшествующий событию путь, имеющий наибольшую длину, называется максимальным предшествующим. Он обозначается L1(i), а его продолжительность t[L1(i)].

Путь, соединяющий любое взятое событие с завершающим, называется последующим путем. Такой путь с наибольшей длиной называется максимально последующим и обозначается L2(i), а его продолжительность t[L2(i)].

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

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

Рассмотрим алгоритм определения критического пути на сетевом графике, использующий алгоритм метода динамического программирования.

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

Рис. 10.7

 

Согласно принципу оптимальности Беллмана, оптимальное управление на каждом этапе определяется целью управления и состоянием на начало этапа. Состояние системы – это события, лежащие на рангах. Для совершения конечного события Х16 необходимо совершение предшествующих событий. Возможные состояния системы на начало последнего этапа работ – совершение событий Х14 и Х15. В кружках у точек Х14 и Х15 поставим максимальную продолжительность работ на последнем этапе: Х14 5 , Х15 7 . Найдем максимальную продолжительность работ на двух последних этапах. Состояние системы на начало предпоследнего этапа обусловлено событием Х13. Максимальная продолжительность пути, ведущая из Х13 к Х16 равна . Следовательно, в кружке у события Х13 нужно поставить число 14 и т.д. Проводя этапы от конца к началу, узнаем длину критического пути tкр=96. Чтобы найти сам критический путь, процесс вычислений пройдем от начального события Х1 к конечному Х16. Число 96 на первом этапе (от начала) мы получили, прибавив 16 к числу 80. Следовательно, критический путь на этом этапе будет равен (Х1, Х3). Число 80=16+64. Следовательно, критический путь на втором этапе проходит через работу (Х3, Х4) и т.д. На графике он выделен жирной линией:

X1 – X3 – X4 – X7 – X8 – X10 – X11 – X12 – X13 – X15 – X16 .

 

10.4.2. Ранние и поздние сроки свершения событий. Резерв времени событий.Все пути, отличные по продолжительности от критического, располагают резервами времени. Разность между длиной критического пути и любого некритического называется полным резервом времени данного некритического пути и обозначается : .

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

или

Чтобы найти ранний срок совершения события j , нужно знать критический путь ориентированного подграфа, состоящего из множества путей, предшествующих данному событию j . Ранний срок исходного события равен нулю: tp(1)=0.

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

или

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

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

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

 

 

Для вычисления раннего срока свершения событий: , применяем формулу , рассматривая события в порядке возрастания номеров, от начального к завершающему, по входящим в это событие работам. Поздний срок свершения событий вычисляем по формуле , начиная с конечного события, для которого (- номер конечного события), по выходящим из него работам.

Критические события имеют резерв времени равный нулю. Они и определяют критические работы и критический путь.

Пример 10.2. Пусть задан сетевой график, изображенный на рис. 10.8.

Рис. 10.8

 

Решение. Вычислим ранние сроки свершения событий :

Итак, завершающее событие может произойти лишь на 14-ый день от начала выполнения проекта. Это максимальное время, за которое могут быть выполнены все работы проекта. Оно определяется самым длинным путем. Ранний срок свершения работы 6 =14 совпадает с критическим временем кр - суммарной продолжительностью работ, лежащих на критическом пути. Теперь можно выделить работы, принадлежащие критическому пути, возвращаясь от завершающего события к исходному. Из двух работ, входящих в событие 6 , , длина критического пути определила работы (5, 6), так как (5+56)=14. Поэтому работа (5, 6) – критическая и т.д. Работы (1, 3), (3, 4), (4, 5), (5, 6) определили критический путь: кр = (1-3-4-5-6).

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

, так как после события 5 для завершения проекта нужно выполнить работу (5, 6) длительностью 3 дня. Из события 4 выходят две работы, поэтому:

Резерв времени для события 2 равен: . Резервы остальных событий равны нулю, так как эти события критические.

10.4.3. Ранние и поздние сроки начала и окончания работ. Определение резервов времени работ. Полный резерв времени работ.Событие, непосредственно предшествующее данной работе, будем называть начальным и обозначать , а событие, непосредственно следующее за ней, – конечным и обозначать . Тогда любую работу будем обозначать . Зная сроки свершения событий, можно определить временные параметры работ.

Ранний срок начала работы равен раннему сроку свершения события : .

Ранний срок окончания работы равен сумме раннего срока свершения начального события и продолжительности этой работы: или .

Поздний срок окончания работы совпадает с поздним сроком свершения ее конечного события : .

Поздний срок начала работы равен разности между поздним сроком свершения ее конечного события и величиной этой работы:

.

Поскольку сроки выполнения работ находятся в границах, определяемых и , то они могут иметь разного вида резервы времени.

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

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

Свободный резерв времени работы – это запас времени, которым можно располагать при выполнении данной работы при условии, что начальное и конечное ее события наступят в свои ранние сроки: .

Свободный резерв присущ только данной работе, и его использование никак не повлияет на выполнение последующих работ. Только отдельные работы проекта обладают свободным резервом времени.

Независимый резерв времени - это запас времени, которым можно располагать при выполнении данной работы при условии, что начальное ее событие наступит в свой поздний срок, а конечное – в ранний срок:

. Использование независимого резерва времени на работе, которая его имеет, не влияет на ранние и поздние сроки свершения всех событий и работ сети. Если , то это показывает недостаток времени для выполнения данной работы к самому раннему сроку свершения ее конечного события, если начальное свершилось в поздний срок.

Независимый резерв времени работы (если он имеется) представляет собой остаток от ее полного резерва, если за счет последнего полностью сохранены резервы времени у начального события данной работы и конечного : . Величина независимого резерва времени работы показывает продолжительность вынужденного ожидания наступления конечного события данной работы. Это позволяет снять с работы часть ресурсов с тем, чтобы перебросить их на другие более напряженные работы.

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

Пример 10.3. Рассмотрим сетевой график, заданный на рис. 10.8. Вычислим временные параметры работ.

Ранние сроки начала работ:

Ранние сроки окончания работ:

Поздние сроки окончания работ:

Поздние сроки начала работ:

Полные резервы времени работ:

Свободные резервы времени работ:

Независимые резервы времени работ:

, так как эти работы принадлежат критическому пути.

Составим линейный график Ганта. Начало каждой работы совпадает с ожидаемым сроком свершения ее начального события.

 

 

Работы изображены в той же последовательности, что и на сети.