Кроме того, справедливо: d„> t^we?. d^>t^, если сток л активируется, пока некоторые действия при w,y=l все еще выполняются. Так как te= min t? самое раннее из возможныхJ X J wee времен задействования узла j в течение какой-либо возможной реализации процесса, то, очевидно, te s = min max {(z* + dif )w,y}. wee eE J Далее будем обозначать через £Л= e £ Wy=l) множество операций, выполняемых в течение m-й реализации процесса. Учитывая вышесказанное, можно утверждать, что минимальная длительность успешной реализации процесса равна самому раннему моменту задействования стока s: d*=te s для £*^0. Таким образом, можно найти величину г/*, вычисляя минимально возможные моменты задействования V). Перепишем (2.2.11) в более детальной форме. Для этого будем рассматривать моменты вектора временной развертки t„ которые удовлетворяют ограничениям: (^-^>0, (,;>е£); (2.2.12) f,->0, (ie V//r/); z)=0 для некоторой vv-й реализации процессаа (wefr) и, очевидно, отвечают этим ограничениям, а самые ранние // удовлетворяют (2.2.12) для соответствующей минимальной we£. Итак, для (2.2.11) имеем: минимизировать max {(Z, + djj) eE при условии, ЧТО Ywki>x^ui IcePi (ieV/S); jeS(i) Wijt={Q,\} (eE); (ieV/{s}); us=l и при выполнении ограничений (2.2.12). 84 |
Предположим, что каждая реализация набора алгоритмов начинается с задействования истока г в момент 0. Будем считать для we б, Ресть время активации узла je V для w-й реализации, причем t^=0 и если j не активируется в течение w-й реализации алгоритма. Для j eV/{r} имеем: ?y'=min{Z 0) существуют XJ, отличные от ie P(j) такие, что w,y=l; tr+di} t}. Кроме того, справедливо dw t™Vw еР~. d^t™, если сток s активируется, пока некоторые действия при и>у=1 все еще выполняются. Так как te: = min t™ самое раннее из возможныхJ Y J времен задействования узла j в течение какой-либо возможной реализации алгоритма, то, очевидно, zf = min max {(/^ + d^Wy}. Далее будем обозначать через £w={ Учитывая вышесказанное, можно утверждать, что минимальная длительность успешной реализации алгоритма равна самому раннему моменту задействования стока s: d*=t^ для s*^0. Таким образом, можно найти величину d*, вычисляя минимально возможные моменты задействования По аналогии с задачами предыдущего раздела перепишем (1.28) в более детальной форме. Для этого будем рассматривать моменты вектора временной развертки которые удовлетворяют ограничениям: (tj-t-dij)Wij >0, ( е Е)\ (1.29) Zz>0, (ie V/{r})', tf=O 107 |