Курсовая работа: Контроль и диагностика систем

d_ij = (1.3)

- ∞, если (i,j) не принадлежит U

Введем следующие понятия:

а) наиболее раннее время начала модуля

Т_н (Z_к ) = max { Т_н (Z_i ) + b_ik }, Т_н (Z₀ ) = 0 (1.4)

0< i ≤ k

б) критический путь – самый длинный путь, ведущий от мажоранты графа к миноранте, причем за длину любого пути принимается сумма длительностей τ_i для всех модулей и всех задержек t_ij , входящих в этот путь.

Обозначим H = {L_ij } – множество всех независимых путей на графе (путей, отличающихся друг от друга хотя бы одной дугой), ведущих от вершины z_i к z_j , и H’ = {L_k }є H – множество всех независимых путей, ведущих от вершины z_k к миноранте. Тогда такой путь представляет собой частичный подграф G_L = (Z_L , U_L ), длина которого равна:

T(L) = ∑ τ_k + ∑ t_kl (1.5)

k:z_k є Z_L (k,l) є U_L

Длина критического пути может быть вычислена из рекуррентной формулы:

Т_кр = t(L₀ *) = max {t(L₀ )}= τ₀ + max {t_{0, j} + t(L_j *)} (1.6)

L₀ єH’

j:z_j єГ_{z 0}

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

∑τ_k ≤ t(L₀ *) и (VR)[t_k ≤T_k (z_k )] (1.7)

k:z_k є Z

где t_k – время завершения к-го модуля, определяемое из полученного решения D.

На основании приведенных выражений процесс преобразования графа G = (Z, Г) в граф очередности G = (Z, Г_D ) может быть интерпретирован следующим образом. Определим для каждой вершины S_k є S дерева ветвления вариантов Е множество

N(S_k ) = {z_{i ‌‌‌} │z_i є Z, Г^-1 z_i є Y(S_k )} (1.8)

которое определяет фронт упорядочения. Согласно априорной части упорядоченности модулей, выражаемой отображением Г, очередной модуль при пошаговом построении графа D может быть выбран только из │N(S_k )│, выражающего мощность фронта упорядочения.

На основе (6) можно записать выражение для оценки нижних границ для произвольного подмножества вариантов W(S_k ) в следующем виде:

Т_оц (S_k ) = t*(S_k ) + max {t(L_i *) + max [0, Т_н (z_i ) - t*(S_k )]} (1.9)

i:z_j є N(S_k )

где t*(S_k ) = max{t_i │i:z_i є Y(S_k )}

На каждом шаге для дальнейшего разветвления выбирается вершина S_{k *} , для которой справедливо равенство

Т_оц (S_{k *} ) = min{ Т_оц (S_k )│S_k є S*} (1.10)

Где S* с S – подмножество вершин, из которых можно продолжать ветвление, т.е.

S* = {S_i │S_i :│∆S_i │<│N(S_i )│} (1.11)