Контроль и диагностика систем

Дано: граф исходного множества модулей и таблицы длительности операций:

Рис 1.1. Исходный граф.

Таблица1.1.

Таблица1.2

Найти: последовательность проведения проверок методом ветвей границ.

Решение:

1. Найдем наиболее раннее время начала модуля Zk:

Тн(Zк) = max { Тн(Zi) + bik}, Тн(Z0) = 0

Тн(Z0) = 0

Тн(Z1) = 0

Тн(Z2) = 0

Тн(Z3) = 2+15 = 17

Тн(Z4) = 4+12 = 16 или Тн(Z4) = 2+15+5+7 = 29 тогда maxТн(Z4) = 29

Тн(Z5) = 4+3 = 7

Тн(Z6) = 4+3+8 = 15 или Тн(Z6) = 2+15+5+7+3 = 32 или Тн(Z6) = 4+12+3 = 19 тогда maxТн(Z6) =32

2. Найдем длину критического пути T(L):

T(L*( Z0)) = 0+2+15+5+7+3 = 32

T(L*( Z1)) = 0+2+15+5+7+3 = 32

T(L*( Z2)) = 0+4+12+3 = 19

T(L*( Z3)) = 0+5+7+3= 15

T(L*( Z4)) = 0+3= 3

T(L*( Z5)) = 0+8 = 8

T(L*( Z6)) = 0

Полученные данные сведем в таблицу

Таблица 1.3

3. Составим дерево проверок:

Рис. 1.2 – Дерево проверок

4. Рассчитаем t*(Sk) и полученные значения занесем в таблицу 1.4:

t*(S0) = 0

t*(S1) = 2

t*(S2) = 4

t*(S3) = 2+15+5=22

t*(S4) = 2+4=6

t*(S8) = 2+5+15=22

t*(S9) = 2+4+8+3=17

t*(S15) = 2+15+5+7+3 = 32

t*(S16) = 2+15+5+8 = 30

t*(S17) = 2+4+3+8+5 = 22

t*(S26) = 2+4+3+8+5+7+3=32

5. Рассчитаем оценку нижней границы для множества W(Sk) и полученные значения занесем в таблицу 1.4.

Tоц(S0) = 0 + max{(19,32) + max(0,(0,0)-0)} = 32

Tоц(S1) = 2 + max{(19,15) + max(0,(0,17-2)} = 32

Tоц(S2) = 4 + max{(32,7) + max(0,(0,7)-5)} = 36

Tоц(S3) = 22 + max{19 + max(0,0-22)} = 41

Tоц(S4) = 6 + max{(15,8) + max(0,(17,7)-6)} = 32

Tоц(S8) = 22 + max{(3,8) + max(0,(29,7)-22)} = 32

Tоц(S9) = 17 + max{15 + max(0,17-17)} = 32

Tоц(S15) = 32 + max{8 + max(0,7-32)} = 40

Tоц(S16) = 30+ max{3+ max(0,29-30)} = 33

Tоц(S17) = 22 + max{3 + max(0,29-22)} = 32

Tоц(S26) = 32 + max{0 + max(0,32-32)} = 32

Таблица 1.4.

 Скачать реферат