Основними часовими парамерами мережевого графа з детермінованим часом виконання операцій розраховують за наступними формулами:
1) ранній термін настання події j
æ t i p + t i j, якщо до події j підходить одна
t j p = í операція
è max {t i p + t i j}, якщо до події j підходить
{i} декілька операцій;
2) пізній термін настання події j
æ t j п - t i j якщо від події j відходить одна
t i п = í операція;
è min {t j п - t i j}, е якщо від події j відходить одна
{j} декілька операцій
3) резерв часу подій
R = t n - t p ;
4) ранній термін закінчення операції (i, j)
t p о = t p + t i j, при t p o = 0
5) пізній термін закінчення операції (i, j)
t n о = t n
6) повний резерв часу операції(i, j)
R n = Tn - Tp - t i j ;
де R n – максимальний час на який можна відкласти, або збільшити тривалість роботи (i, j), не змінюючи директивного або раннього терміну настання завершаючої події;
за Rп приймають мінамальне значання для операцій, що лежать на кретичном шляху; ці мінімальні значення дорівнюють нулю, якщо директивний термін настання завершаючої події не вказаний, або перевищую начало виконання операції на час, що дорівнює тривалості критичного шляху.
Критичний шлях мережевого графу Lкр – це послідовність операцій, тривалість яких дорівює максимальному часу виконання всього комплексу операцій. Тривалість критичного шляху називають критичним часом Tkp. Критичний шлях Lkp визначається як полідовність операцій з найменшим повним резервом.
Розрахунок t p o і t p ведеться від начала мережевого графа до кінця, а розрахунок t n и t n о - від кінця до начала. При цьому для кінцевої події t p = t n .
Для розрахунку часових параметрів мережевого графу з детермінованим часом виконання операцій не враховують випадкові зміни тривалості операцій, які можуть суттєво вплинуть на термін завершення всього комплексу операцій.
 |
Ітак, рогзлянемо умову нашого графу.
| i | |||||||||||||||
| j | |||||||||||||||
| tij |
Для розрахунків нам будуть необхідні такі позначення:
t p - ранній термін настання події;
t n - пізній термін настання події;
t i.j - час операції;
i - номер передуючої події;
j - номер наступної події;
R n - повний резерв часової операції (i, j);
R - резерв часу операції;
t p o - ранній термін закінчення операції (i, j);
t n о - пізній термін закінчення операції (i, j);
1) t p - ранній термін настання події;
t p (1)=1;
t p (2)= t p (1) + t1.2=0+5
t p (3)= max [t p (1)+t1.3 ; t p (2)+ t2.3]= max[0+4;5+7]=12
t p (4)=max[t p (1)+t1.4 ; t p (3)+ t3.4 ]=max[0+5; 12+4]=16
t p (5)= t p (2) + t2.5=5+7=12
t p (6)=max[t p (3)+t3.6 ; t p (5)+ t5.6 ]=max[12+7; 12+3]=19
t p (7)=max[t p (4)+t4.7 ; t p (6)+ t6.7 ]=max[16+5; 19+3]=22
t p (8)=max[t p (5)+t5.8 ; t p (6)+ t6.8 ]=max[12+3; 19+2]=21
t p (9)=max[t p (6)+t6.9 ; t p (7)+ t7.9; t p (8) + t8.9]=max[19+4; 22+4; 21+6]=27
2) t n - пізній термін настання події
t n(9) = tp(9) = 27
t n (8) = t n (9) - t 8.9 = 27-6= 21
t n (7) = t n (9) - t 7.9 = 27-4= 23
t n (6) =min[ t n (9) - t 6.9 ; t n (8) - t 6.8 ; t n (7) - t 6.7 ] = min[27-4; 21-2; 23-3] =19
t n (5) =min[ t n (8) - t 5.8 ; t n (6) - t 6.8 ] = min[21-3; 19-3] =16
t n (4) = t n (7) - t 4.7 = 23-5= 18
t n (3) =min[ t n (6) - t 3.6 ; t n (4) - t 3.4 ] = min[19-7; 18-4] =12
t n (2) =min[ t n (5) - t 2.5 ; t n (3) - t 2.3 ] = min[16-7; 12-7] =5
t n(1) = tp(1) = 0
3) R - резерв часу операції; R(i)=tn(i)-tp(i)
R(1) = 0
R(2) = 5-5=0
R(3) = 12-12=0
R(4) = 18-16=2
R(5) = 16-2=4
R(6) = 19-19=0
R(7) = 23-22=1
R(8) = 21-21=0
R(9) = 27-27
4) t p o - ранній термін закінчення операції (i, j);
t p o(i,j)= t p(i)+ti,j
t p o(1.2)= t p(1) + t1.2 = 0+5=5
t p o(1.3)= t p(1) + t1.3 = 0+4=4
t p o(1.4)= t p(1) + t1.4 = 0+5=5
t p o(2.3)= t p(2) + t2.3 = 5+7=12
t p o(2.5)= t p(2) + t2.5 = 5+7=12
t p o(3.4)= t p(3) + t3.4 = 12+4=16
t p o(3.6)= t p(3) + t3.6 = 12+7=19
t p o(4.7)= t p(4) + t4.7 = 16+5=21
t p o(5.6)= t p(5) + t5.6 = 12+3=15
t p o(5.8)= t p(5) + t5.8 = 12+3=15
t p o(6.7)= t p(6) + t6.7 = 19+3=22
t p o(6.8)= t p(6) + t6.8 = 19+2=21
t p o(6.9)= t p(6) + t6.9 = 19+4=23
t p o(7.9)= t p(7) + t7.9 = 22+4=26
t p o(8.9)= t p(8) + t8.9 = 21+6=27
5) t n о - пізній термін закінчення операції (i, j);
t n о (1.2) = t n о(2) = 5
t n о (1.3) = t n о(3) = 12
t n о (1.4) = t n о(2) = 18
t n о (2.3) = t n о(2) = 12
t n о (2.5) = t n о(2) = 16
t n о (3.4) = t n о(2) = 18
t n о (3.6) = t n о(2) = 19
t n о (4.7) = t n о(2) = 23
t n о (5.6) = t n о(2) = 19
t n о (5.8) = t n о(2) = 21
t n о (6.7) = t n о(2) = 23
t n о (6.8) = t n о(2) = 21
t n о (6.9) = t n о(2) = 27
t n о (7.9) = t n о(2) = 27
t n о (8.9) = t n о(2) = 27
6) R - резерв часу операції;
Rn(i,j) = tn(j) – tp(i) – ti.j
Rn(1.2) = tn(2) – tp(1) – t1.2 = 5-0-5=0
Rn(1.3) = tn(3) – tp(1) – t1.3 = 12-0-4=8
Rn(1.4) = tn(4) – tp(1) – t1.4 = 18-0-5=13
Rn(2.3) = tn(3) – tp(2) – t2.3 = 12-5-7=0
Rn(2.5) = tn(5) – tp(2) – t2.5 = 16-5-7=4
Rn(3.4) = tn(4) – tp(3) – t3.4 = 18-12-4=2
Rn(3.6) = tn(6) – tp(3) – t3.6 = 19-12-7=0
Rn(4.7) = tn(7) – tp(4) – t4.7 = 23-16-5=2
Rn(5.6) = tn(6) – tp(5) – t5.6 = 19-12-3=4
Rn(5.8) = tn(8) – tp(5) – t5.8 = 21-12-3=6
Rn(6.7) = tn(7) – tp(6) – t6.7 = 23-19-3=1
Rn(6.8) = tn(8) – tp(6) – t6.8 = 21-19-2=0
Rn(6.9) = tn(9) – tp(6) – t6.9 = 27-19-4=4
Rn(7.9) = tn(9) – tp(7) – t7.9 = 27-22-4=1
Rn(8.9) = tn(9) – tp(8) – t8.9 = 27-21-6=0
1.3 Розрахунок мережевого графу.
В результаті проведених розрахунків було з’ясоване наступне, що даний мережевий граф має два критичних шляхи і вони такі:
перший 1-3-6-9 та другий 1-2-3-6-8-9.
Розділ 2.
