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

Рассмотрим алгоритм, представляемый информационным гра­фом (без связей по управлению), не имеющим контуров. Тогда оче­видно, что момент окончания выполнения любого из операторов не может быть меньше максимальной из длин всех путей, заканчива­ющихся вершиной, соответствующей этому оператору. Таким обра­зом, для каждого оператора алгоритма j = 1,..., т. можно найти ранний срок окончания его выполнения.

Если окончание выполнения алгоритма ограничено временем , то для каждого оператора можно найти и поздний срок окончания его выполнения (Т). Здесь Т_КР — максимальная ха­рактеристика пути в графе со скалярными весами, она определяет минимальное время, за которое может быть решена данная задача.

Окончание выполнения любого оператора позже этого позднего срока приводит к тому, что все последующие за ним операторы не смогут быть выполнены в заданный срок Т, поэтому без задания Т определение поздних сроков не имеет смысла. При Т = Т_кр ранние и поздние сроки выполнения операторов, входящие в критический путь, совпадают.

Алгоритм. Нахождение ранних сроков окончания выполне­ния операторов.

1. Положим где .

2. Просмотрим строки матрицы S сверху вниз, выберем первую необработанную строку матрицы и осуществим переход к следую­щему шагу. Если обработаны все строки, то конец алгоритма,

3.Пусть выбрана j-я строка, не содержащая единичных элемен­тов. Далее вычислим где — вес j-гo оператора, затем выполним переход к шагу 5.

4.Если j-я строка содержит единичные элементы, то вычислим где есть множество времен, которым соответствует единица в данной строке. Затем выполним переход на шаг 5. Если во множестве есть нулевые элементы, то вы­полним шаг 6.

5.Обработанную j-ю строку исключим из рассмотрения и осу­ществим переход к шагу 2.

6.Если найдена строка , для которой , то вычислим строку j= , и осуществим переход к шагу 3.