Алгоритм нахождения операторов входящих только в одно множество ВНО

Пусть в ВС имеется N_i процессоров i-ого типа, i=1,…,k.

Рассмотрим частный случай. Под весами будем понимать время выполнения j-ого оператора на данном типе процессора i: . “∞” – на данном типе процессора эта операция не может быть выполнена.

Для решения таких задач полезен алгоритм нахождения операторов, входящих в одно множество ВНО. Рассматривается матрица ST'.

Алгоритм.

1. Матрицу ST' посматриваем сверху вниз по строкам. Если просмотрены все строки, то конец алгоритма.

2. В i-й строке находим множество элементов , , равных 0

3. Получим дизъюнкцию строк .

4. Если i-я строка матрицы ST' совпала со строкой , то i-й оператор входит в одно и только в одно множество ВНО. Совпадающие нулевые столбцы i-ой строки (их номера) образуют множество ВНО.

Конец описания алгоритма.

Пример:

Тогда {ВНО}={{1}, {2,3},{4,5}}.