|
(а) Т19 Т,7 Т,6 Т,4 тМ2 Т,о т9 Т7 Ts тг Т,„ Т« Т,5 Т,, L Т8 и Т, Т, ) I 2 3 4 5 7 9 1 (b) Рисунок 2.1.8 Алгоритм генерации 2-Б: а граф задач с переназначенными нижними индексами L* = (Ti9,T]g,...,Ti); b оптимальный план. Первым шагом в решении этой задачи является разметка узлов произвольного графа. Узлу Nj присваивается метка а,= X,+ 1, где X/ длина наидлиннейшего пути от Nj до конечной вершины в графе. Разметка начинается с конечной вершины, которой присваивается метка й/ = 1. Узлы, на единицу отдаленные от конечного, получают метку 2 и т. д. Смысл этой схемы меток в том, что минимальное время Tniin. необходимое для обработки 54 |
2) определение количества процессоров, необходимых для обработки графа за заданное время. (а) Т19 Т17 Т1б Т,4 Т12 Т,о Т9 Т7 Т5 Т2 Т18 Т6 Т15 Т,з Т„ Т4 Т8 Тз Т, 0123456 78 9 10 (Ь) Рис. 2.13. Алгоритм генерации 2-Б: а граф задач с переназначенными нижними индексами £* = (Ti9,Ti8,...,Ti); Ь оптимальный план. Первым шагом в решении этой задачи является разметка узлов произвольного графа. Узлу N( присваивается метка я,= + 1, где X длина наидлиннейшего пути от Nt до конечной вершины в графе. Разметка начинается с конечной вершины, которой присваивается метка ai = 1. Узлы, на единицу отдаленные от конечного, получают метку 2 и т. д. Смысл этой схемы меток в том, что минимальное время Tmjn, необходимое для обработки 60 |