ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2012
81
С целью поиска эффективного решения этих задач вводят метри-
ки сети, которые локально представляют оптимизируемые критерии
качества системы. Пусть для определенности векторный критерий
качества системы составлен из продолжительностей
T
k
,
k
= 1, 2, …,
K
,
решения всех типов задач в сети. Для вычисления и оптимизации
этого векторного критерия введем функции задержек
f
l
(
z
l
),
значения
которых зависят от длин очередей
z
l
из активных заданий в узлах се-
ти
l
= 1, 2, …,
n
.
Задержка — это суммарное время пребывания ак-
тивного задания в
l-
м узле, включая его выполнение.
Длину
ρ
f
маршрута
L
(
метрику сети) определим как сумму задер-
жек:
( , )
( ),
f
l l
l L
L z
f z
ρ
∈
=
∑
(1)
где
z
= (
z
1
,
z
2
, …,
z
l
).
В выражении (1) не учитывается время передачи по линиям свя-
зи. Соответствующую задержку обычно рассматривают в качестве
метрики при решении задачи маршрутизации [4].
Теперь можно вычислить
T
k
=
T
k
(
z
) —
время решения каждой
k-
й
задачи, как наибольшую длину среди всех максимальных
k-
цепей в
сетевой метрике (1).
Определение функций задержек
f
l
(
z
l
),
l
∈
V
,
составляет самостоя-
тельную задачу. Во всяком случае, они неотрицательны, монотонно и
неограниченно возрастают при увеличении числа заданий в узле.
Непрерывно продолжим функции задержек на множество всех веще-
ственных неотрицательных чисел и будем считать, что
f
l
(0)
= 0.
Длины
z
l
≥
0
и подчиняются балансовым соотношениям
a
,
1, 2, ..., ,
h
l
h
l V
z z
h
H
∈
=
=
∑
(2)
означающим постоянство числа
z
a
h
активных заданий, распределяе-
мых среди процессоров любого
h-
го яруса сети. Предполагается, что
в момент принятия решения о выборе вектора
z
известен вектор
z
a
=
= (
z
a1
,
z
a2
, …,
z
a
H
).
Векторная задача о назначениях.
Рассмотрим задачу с вектор-
ным критерием быстродействия
T
(
z
),
T
= (
T
1
,
T
2
, …,
T
K
),
который требуется, по возможности, минимизировать:
T
(
z
)
→
min,
(3)
путем выбора неотрицательного вектора
z
,
удовлетворяющего соот-
ношению (2) и получаемого в результате допустимого проецирова-
ния
π
= (
π
1
,
π
2
, …,
π
K
)
графов алгоритмов в граф сети (см. выше).