Минимизировать С( у/) при условии у/е ЧР. 2.2.5. Минимизация по времени Ниже рассматривается решающая сеть N для формирования распределенных процессов, где вес дуги e Е это длительность d^e R+ соответствующей операции процесса вместо рассматривавшейся выше с,у. Отметим, что в нашем случае длительности и времена задействований детерминированные величины, т.е. рассматриваются только детерминированные акции или реализации процесса (wee). Что же касается случайных акций и направлений реализации процесса (последовательностей случайных акций) по времени, то эти модели аналогичны ранее рассмотренным. Пусть dw длительность W-й реализации процесса, т.е. время, требуемое для исполнения всех операций при w,y=l (согласно условиям а и б каждое действие начинается в наиболее ранний, возможный при данной w-й реализации рассматриваемого процесса, срок). Необходимо минимизировать dw (2.2.11) при условии, что w активирует 5 (wef). Обозначим через £*:={we£w активирует s) множество успешных реализаций процесса. Для J*=min dw соответствует минимальному значению целевой функции задачи (2.2.11). Предположим, что каждая реализация набора алгоритмов начинается с задействования истока г в момент 0. Будем считать для wee, tj есть время активации узла je V для w-й реализации, причем /*=0 и zj = l,2,.., если j не активируется в течение w-й реализации процессаа. Для j eV/frj имеем: zj=min{z> 0 существуют XJ, отличные от ie P(j) такие, что w,y=l; 83 |
C( у)=Му л/ Lv=i где индекс Му находится в зависимости от величины Ру вероятности выбора направления цг. Итак, ищется некоторое допустимое направление, минимизирующее общие ожидаемые затраты на реализацию алгоритма,, что соответствует задаче: Минимизировать С(у) при условии ц/е ¥< 3.1.5. Минимизация по времени Ниже рассматривается решающая сеть N для формирования распределенных алгоритмов, где вес дуги еЕэто длительность dyE R+ соответствующей задачи алгоритма вместо рассматривавшейся выше Су. Отметим, что в нашем случае длительности и времена задействований детерминированные величины, т.е. рассматриваются только детерминированные акции или реализации алгоритма (wes). Что же касается случайных акций и направлений реализации алгоритма (последовательностей случайных акций) по времени, то эти модели аналогичны соответствующим моделям предыдущего раздела. Пусть dw длительность 1К-й реализации алгоритма, т.е. время, требуемое для исполнения всех задач при vv;y=l (согласно Опр. 1а,б каждое действие начинается в наиболее ранний, возможный при данной w-ft реализации рассматриваемого алгоритма, срок). Необходимо Минимизировать dw (1-28) при условии, что w активирует s (yvEs). Обозначим через £*:={we£)w активирует 5} множество успешных реализаций алгоритма. Для £* О соответствует минимальному значению целевой функции задачи (1.28). 106 Предположим, что каждая реализация набора алгоритмов начинается с задействования истока г в момент 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 |