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



              

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


После обработки шестой строки ?16 = ?12 + t6 = 7. Tкр = 7.

Для удобства представления наряду с другими способами будем пользоваться наглядными диаграммами выполнения работ при заданных значениях времени начала или окончания их выполнения. Работы обозначаются прямоугольниками с постоянной высотой и длиной, равной времени выполнения. Стрелки, связывающие прямоугольники-работы, соответствуют дугам в графе G. На рис. 7.11 представлена диаграмма выполнения работ, отраженных графом G на рис. 7.1 и расширенной матрицей следования на рис. 7.5 — при ранних сроках выполнения работ.

Временная диаграмма выполнения работ при ранних сроках окончания

Рис. 7.11.  Временная диаграмма выполнения работ при ранних сроках окончания

Алгоритм 3 нахождения поздних сроков окончания выполнения работ при заданном значенииТ.

  1. Полагаем первоначально ?21(T) = ... = ?2m(T) = 0.
  2. Производя циклический обзор справа налево столбцов матрицы S, находим очередной из не обработанных ещё столбцов. Если все столбцы обработаны, выполнение алгоритма заканчивается.
  3. Пусть j — номер найденного необработанного столбца. Если j-й столбец не содержит единичных элементов, полагаем ?2j(T) = T. Переходим к выполнению шага 6.
  4. Если j-й столбец содержит единичные элементы, выбираем элементы множества { ?21(T) , ... ,?2m(T) }, соответствующие номерам единичных элементов j-го столбца.
  5. Если все выбранные таким образом элементы {?2j?}(T)}

    {?21(T), ... , ?2m(T)}, ? = 1 , ... , kj, отличны от нуля, полагаем

    ?2j (T) = min {?2j? (T) - tj? }.

    В противном случае выполняем шаг 2.

  6. Обработанный j-й столбец метим с целью исключения его повторной обработки. Переходим к выполнению шага 2.

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

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

Для матрицы S* (матрица S — треугольная) на рис. 7.5 и для T = 10 за один просмотр находим

?28(10) = 10, ?27(10) = ?28(10) - t8 = 9, ?26(10) = ?28(10)- t8 = 9, ?25(10) = ?28(10) - t8 = 9 , ?24 = min {?26(10), - t6, ?27(10) - t7} = 5, ?23(10) = ?28(10) - t8 = 9, ?22(10) = min {?25(10) - t5, ?27(10) - t7 } = 5, ?21(10) = min {?23(10) - t3, ?24(10) - t4, ?25(10) - t5, ?26(10) - t6} = 3.




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