|
графа, связано с я(тах) узлами с наивысшими индексами через соотношение TV >д(тах). Оптимальные решения для задач, описанных ранее, рассмотрим для корневых деревьев. Используя процедуру разметки, изложенную выше, можно получить оптимальный план для т ресурсов, организуя дерево задач единичной длины следующим образом: Алгоритм генерации 2-В. 1. Включаем в план первые т начальных узлов с наивысшими индексами меток. Термин «начальный узел» применяется к узлу без предшественников. Если количество таких узлов больше т, то выбрать т узлов с наибольшими значениями В случае нескольких одинаковых величин выбор производится случайным образом. Рисунок 2.1.9 Оптимальный алгоритм Хыо: а корневое дерево, размеченное в соответствии с процедурой Хью; b оптимальный план для трех процессоров 55 |
графа, связано с д(тах) узлами с наивысшими индексами через соотношение Tmin > a(max). Оптимальные решения для задач, описанных ранее, рассмотрим для корневых деревьев. Используя процедуру разметки, изложенную выше, можно получить оптимальный план для т процессоров, организуя дерево задач единичной длины следующим образом: Алгоритм генерации 2-В. 1. Включаем в план первые т начальных узлов с наивысшими индексами меток. Термин «начальный узел» применяется к узлу без предшественников. Если количество таких узлов больше т, то выбрать т узлов с наибольшими значениями В случае нескольких одинаковых величин выбор производится случайным образом. 2. Удаляем т обслуженных узлов из графа. 3. Повторяем шаги 1 и 2 для оставшегося графа. Т„ Т16 Т,5 Т„ Т8 Т5 Т2 Т, Т,„ Т„ Т,з Т,о Т7 Т4 Тп Т,2 Т, Т6 т о ж 0123456 78 (Ь) Рис. 2.14. Оптимальный алгоритм Хью: а корневое дерево, размеченное в соответствии с процедурой Хью; b оптимальный план для трех процессоров 61 |