Параллельное программирование



              

Временные оценки на информационных графах - часть 2


Если все строки обработаны, выполнение алгоритма заканчивается.
  • Пусть j — номер найденной необработанной строки. Если j-я строка не содержит единичных элементов, полагаем ?1j = tj. Переходим к выполнению шага 6.
  • Если j-я строка содержит единичные элементы, выбираем элементы множества {?11 , ... , ?1m}, соответствующие номерам единичных элементов j-й строки.
  • Если все выбранные таким образом элементы, образующие множество {?1j(?)}, ? = 1, ... , kj, отличны от нуля, полагаем ?1j = max ?1 j? + tj.

    Если хотя бы один из выбранных элементов нулевой (соответствующий ранний срок ещё не найден), выполняем шаг 2.

  • Обработанную j-ю строку метим, чтобы исключить её повторную обработку. Переходим к выполнению шага 2.

    Примечание. Если граф G не содержит контуров, зацикливание при этом невозможно.

  • Конец алгоритма.

    Если матрица S треугольная, то никогда не складываются условия для многократного циклического обзора строк. Тогда ранние сроки окончания выполнения работ находятся за один последовательный просмотр строк матрицы S.

    Очевидно, что Tкр = max {?11 , ... , ?1m}.

    По матрице S* ( S — треугольная) на рис. 7.5 (граф G — на рис. 7.1) находим

    ?11 = t1 = 2, ?12 = t2 = 3, ?13 = ?11 + t3

    =3, ?14

    = ?11 + t4 = 4, ?15 = max {?11, ?12 + t5= 7, ?16 = max {?11, ?14} + t6 = 8, ?17 = max {?12,?14 } + t7 = 6, ?18 = max {?13, ?15, ?16, ?17} + t8 = 9; Tкр = 9.

    Чтобы рассмотреть пример с нетреугольной матрицей следования, выберем граф G без контуров с "неправильно" пронумерованными вершинами (рис. 7.10).

    Информационный граф с не треугольной матрицей следования

    Рис. 7.10.  Информационный граф с не треугольной матрицей следования

    После обработки первой строки ?11 = 1. Попытка обработать вторую строку неудачна, т.к. ?13 и ?14 ещё не найдены. После обработки третьей строки ?13 = ?11 + t3 = 3. Обработка четвёртой строки даёт ?14 = 2. После обработки пятой строки ?15 = ?13 + t5 = 4. Попытка обработки шестой строки неудачна, т.к. не найдено значение ?12. Приступаем к следующему циклу обзора необработанных строк S. Обрабатываем вторую строку: ?12 = max {?13, ?14} + t2 = 6.


    Содержание  Назад  Вперед