6. МЕТОДЫ АГРЕГИРОВАНИЯ КОМПЛЕКСА ОПЕРАЦИЙ
W3(t) = F3(N(t)) (6.1)
Определение.
Агрегирование называется идеальным, если для любой функции N(t) существует оптимальное распределение ресурсов {ui(t)} по операциям комплекса, такое что? Ui(t) ? N(t),
i=1
а минимальная продолжительность комплекса удовлетворяет условию:
-*-тт
J F3 (N( t ))dt = W3.
0
Классическим примером идеального агрегирования является случай степенных зависимостей скоростей операций от количества ресурсов:
fi(ui) = u«, а ? 1, i = 1, n. (6.2)
Действительно, в этом случае доказано ([3]), что существует эквивалентный объем комплекса Wэ и зависимость
F3(N) = Na,
такие, что для любого уровня ресурсов N(t) имеет место
т ¦
mm
J F [ N (t )]dt = W3
При этом, существует оптимальное распределение ресурсов {ui0(t)}, такое что
n
Z U0 (t) = N( t),
i=1
а время выполнения комплекса равно Tmin.
Пусть N(t) = N при любом t. В этом случае распределение ресурсов {ui0(t)} имеет следующие интересные свойства:
1. Каждая операция выполняется без перерывов постоянным количеством ресурсов, то есть
tH t0
u0 (t) = ui, t
H0
где ti , ti - моменты начала и окончания i-ой операции.
2. Ресурсы {ui} образуют поток по сетевому графику.
Существует интересная геометрическая интерпретация этого результата.
Поставим в соответствие комплексу операций некоторую область m- мерного фазового пространства. Эта область строится следующим образом. Сначала находим минимальное множество путей, покрывающих сетевой график, то есть таких, что кажая операция комплекса принадлежит хотя бы одному пути.
Для построения такого множества путей необходимо определить минимальный поток в сети при условии, что поток в каждой дуге (исключая фиктивные дуги, соответствующие зависимостям)не меньше 1, применяя известные алгоритмы.Пример 6.1. Пусть сеть имеет вид рис. 6.1 (зависимости показаны пунктирными дугами)
Минимальный поток в данном случае, очевидно, равен 3.Соответствующие пути, покрывающие сеть:
m = (0, 1, 3), m = (0, 2, 3), m = (0, 3).
Минимальное число г путей, покрывающее сеть, называется размерностью комплекса операций. Поставим в соответствие каждому пути координатную ось г-мерного фазового пространства. Построим в этом пространстве область возможных состояний комплекса. Способ построения показан на примере 6.1. На первой координатной оси откладываем два отрезка, длины которых равны w01 и w12, то есть объемам соответствующих операций, на второй координатной оси откладываем, соответственно, отрезки длины w02 и w23, а на третьей - w03 (рис 6.2). Теперь необходимо изобразить зависимость (1, 2), отражающую тот факт, что операцию (2, 3) нельзя начинать, пока не закончена операция (0, 1). Это значит, что запрещено находиться в параллелограмме, верхняя и нижняя грани которого на рис. 6.2 закрашены. Область допустимых состояний комплекса представляет собой параллелограмм 0ABC0\'A\'B\'C\