7.5.1.Алгоритм расчета наиболее ранних сроков наступления событий

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

Рассмотрим фрагмент некоторого сетевого графика, представленный на рис.7.22. Пусть известны наиболее ранние сроки наступления 5,8 и 9 события, т.е. известно, что событие 5 в наилучшем случае (наиболее рано) произойдет через четыре единицы времени после начала работы над проектом, событие 8 - через 7 единиц времени, а событие 9 - через 6. Также известны времена выполнения операций (5,14), (8,14) и (9,14), которые равны 6,4 и 3 единицам времени соответственно. Требуется рассчитать наиболее ранний срок наступления события 14. Очевидно, что событие 14 не может произойти, пока не завершатся все операции (5,14), (8,14) и (9,14). Операция (5,14) в лучшем случае завершиться через E(5)+t(5,14)=4+6=10 единиц времени после начала работы над проектом. Аналогично операция (8,14) в лучшем случае завершиться через E(8)+t(8,14)=7+4=11, а операция (9,14) - через E(9)+t(9,14)=6+3=9 единиц времени после начала работы над проектом. Таким образом, все операции (5,14), (8,14),(9,14) завершаться через max(10,11,9)=11 единиц времени и наиболее ранний срок наступления события 14 также равен 11 единицам времени.

В общем случае наиболее ранний срок события j в сетевом графике G=(V,E) рассчитывается по формуле:

Алгоритм расчета наиболее ранних сроков наступления событий представлен на рис.7.23.

7.5.2.Алгоритм расчета наиболее поздних сроков наступления событий

Проанализируем сетевой график, с целью определения для каждого события x наиболее поздний срок его наступления L(x), т.е. срок появления события x, еще допускающий своевременное окончание всего проекта.

Рассмотрим фрагмент некоторого сетевого графика, представленный на рис.7.24. Пусть известны наиболее поздние сроки наступления 20,24 и 29 события и эти сроки соответственно равны 16, 19 и 22 единицам времени. Другими словами, если событие 20 наступит через 16 единиц времени после начала работы над проектом, то еще можно в намеченный срок завершить весь проект. Если же событие 20 наступит по прошествии более 16 единиц времени от начала работы над проектом, то это приведет к задержке выполнения проекта. Аналогично, если 24 или 29 событие наступят соответственно по прошествии 19 и 22 единиц времени от начала работы над проектом, то это также приведет к задержке выполнения проекта.

Требуется рассчитать наиболее поздний срок наступления события 17. Очевидно, что событие 17 не может произойти позже, чем через L(20)-t(17,20)=16-5=11 единиц времени после начала работы над проектом. Кроме того, событие 17 не может произойти позже, чем L(24)-t(17,24)=19-4=15 единиц времени, иначе событие 24 наступит слишком поздно, (более 19 единиц времени). Также событие 17 не может произойти позже, чем L(29)-t(17,29)=22-8=16 единиц времени, иначе событие 29 наступит слишком поздно, (более 22 единиц времени).

Таким образом, наиболее ранний срок наступления события 17 равен min(11,15,16)=11 единицам времени.

В общем случае наиболее поздний срок события i в сетевом графике G=(V,E) рассчитывается по формуле:

Алгоритм расчета наиболее поздних сроков наступления событий представлен на рис.7.25.

Пример расчета наиболее ранних и наиболее поздних сроков наступления событий представлен на рис.7.26. Расчет состоит из следующих этапов:

E(1)=0;

E(2)=E(1)+t(1,2)=0+4=4;

E(3)=max{E(1)+t(1,3), E(2)+t(2,3)}=max{4+1, 0+3}=5;

E(4)=E(1)+t(1,4)=0+4=4;

E(5)=max{E(2)+t(2,5), E(3)+t(3,5)}=max{4+7, 5+4}=11;

E(6)=max{E(4)+t(4,6), E(5)+t(5,6)}=max{4+2, 11+1}=12;

E(7)=max{E(2)+t(2,7), E(5)+t(5,7), E(6)+t(6,7)}=max{4+8, 11+3, 12+4}=16;

L(7)=E(7)=16;

L(6)=L(7)-t(6,7)=16-4=12;

L(5)=min{L(7)-t(5,7), L(6)-t(5,6)}=min{16-3, 12-1}=11;

L(4)=L(6)-t(4,6)=12-2=10;

L(3)=L(5)-t(3,5)=11-4=7;

L(2)=min{L(7)-t(2,7), L(5)-t(2,5), L(3)-t(2,3)}=min{16-8, 11-7, 7-1}=4;

L (1)=min{L(4)-t(1,4), L(3)-t(1,3), L(2)-t(1,2)}=min{10-4, 7-3, 4-4}=0.

Операция (x,y), для которой E(x)=L(x) и E(y)=L(y) является критической и задержка ее выполнения приведет к задержке выполнения всего проекта. На рис.7.26 дуги, соответствующие критическим операциям выделены жирно. Такие дуги образуют путь из начального события в конечное событие. Этот путь называется критическим. В данном случае такой путь один, хотя в общем случае сетевой график может содержать много критических путей. Простейший пример сетевого графика содержащего два критических пути представлен на рис.7.27.