F удобно пользоваться временной диаграммой,
Рис. 7.13. Графики функции: а — для ранних сроков окончания работ,,б — для некоторого допустимого расписания
Для графического представления функции F удобно пользоваться временной диаграммой, которая для второго случая, например, имеет вид, представленный на рисунке 7.14..
Рис. 7.14. Временная диаграмма функции F
Пусть данный граф G, в котором учтены транзитивные связи, образует l полных множеств взаимно независимых работ (ПМВНР). (Каждая пара таких множеств может иметь непустое пересечение.) Обозначим ri, i = 1 , ... , l, число работ, образующих i-е полное множество и найдём
R = max {r1 , ... , rl}.
Тогда
т.к. возможно и такое распределение выполняемых работ во времени, задаваемое набором ?1 , ... , ?m, (т.е. допустимое расписание), когда на каком-то отрезке времени выполняются все работы, составляющие ПМВНР с числом R работ.
Например, для графа на рис. 7.1 мы нашли ПМВНР {3,5,6,7}, включающее четыре работы. Тогда существует допустимое расписание, например, ?1 = 2, ?2 = 3, ?3 = 5, ?4 = 4, ?5 = 8, ?6 = 8, ?7 = 6, ?8 = 9 такое, при котором максимальное значение плотности загрузки F равно четырём (рис. 7.15).
Рис. 7.15. Максимальное значение плотности загрузки
Таким образом, справедливо утверждение
Лемма. Минимальное число n процессоров одинаковой специализации и производительности (т.е. в однородной ВС), способных выполнить данный алгоритм за время T
Определение 8. Функцию
назовём загрузкой отрезка [?1, ?2]
Функция Ф определяет объём работ (суммарное время их выполнения) на фиксированном отрезке их выполнения при заданном допустимом расписании.
Так, для отрезка времени [0, 4]
