ВУЗ:
Составители:
104
Для оценки изменения длины критического пути может использоваться
оценка, определяемая неравенством (7.7). При этом полезно использовать два
следующих утверждения.
1. Если связь
привела к формированию графа, длина критического
пути в котором превышает T, т. е.
tT
21
, то следующее введение
связей не может исправить положение и вновь привести к уменьшению длины
критического пути. Это означает, что сокращение длины критического пути
может быть достигнуто лишь путем замены «неудачных» связей.
2. Если оператор
, входящий в некоторое полное множество ВНО, кото-
рое содержит
n
r
операторов, удалось назначить для выполнения, так что
ранние и поздние сроки окончания выполнения оставшихся операторов этого
множества не изменились, то это назначение не ограничивает числа вариантов
распределения этих операторов.
Последнее утверждение говорит о том, что можно перебирать не полные
множества ВНО, а их подмножества, если удается заранее назначить некоторые
операторы так, что на отрезке времени их выполнения плотность загрузки не
превышает заданное число n процессоров.
Важнейшим этапом алгоритма поиска решения методом направленного
перебора является ветвление при построении графа
'
G
, заключающееся в раз-
личных способах введения дополнительных связей. Как способ сокращения пе-
ребора на шаге 6 алгоритма, описанного в разделе 8.2, рекомендуется введение
дополнительных связей не только по критерию допустимого увеличения длины
критического пути, но и по значениям функции минимальной загрузки отрезка.
Для этого, вводя очередную комбинацию связей на -м шаге, которая не
приводит к увеличению длины критического пути сверх заданного значения T,
необходимо вновь пересчитать значение функции
21
,,T
с учетом новых
связей на всех отрезках
T,, 0
21
. Если при этом выполняется соотноше-
ние (7.7), данная комбинация связей может считаться удачной.
Страницы
- « первая
- ‹ предыдущая
- …
- 102
- 103
- 104
- 105
- 106
- …
- следующая ›
- последняя »
