для последовательных дуг , Полученный граф G’ является потоковым графом. 2. Дополнение полученного потокового графа вспомогательной дугой от стока к источнику. Дополнив полученный потоковый граф G’ дугой от стока к источнику WA(s), получим замкнутый потоковый граф G” . 3. Топологическое уравнения Мейсона для замкнутых потоковых графов. Найдем все петли графа G” . Будем называть петлю петлей первого порядка. Петлей порядка п будем называть множество не связанных между собой петель первого порядка. Для каждой петли Lпервого порядка коэффициент пропускания Тк равен произведению коэффициентов пропускания ветвей, принадлежащих этой петле. тк = п > № /«! Выразим из полученного уравнения дугу WA(s). 4. Вычисление математического ожидания и дисперсии. По определению функции Mjj(O), Mij(s) = 1 при s=0. Следовательно, Mij(s)= W,(s)/PlJ= Wy(S)AV4(0). (2.27). 47 |
Алгоритм расчета EOR сети. 1. Преобразование ГЕРТ сети к потоковому графу. Пусть Ту случайная величина времени выполнения работы соответствующей дуге при условии, что узел i активирован. Тогда условная производящая функция моментов случайной величины Ту определяется как Mtj(s) Е[е‘Т)!]. Введем вспомогательную функцию Wy(s) = pyMy(s). Тогда с помощью данного преобразования всегда можно определить сеть G’, структура которой идентична структуре исходной EOR-сети G, и вместо двух параметров дуг ру и Ту присутствует один параметр W y(s). Функция Wy(s) обладает следующими свойствами: для последовательных дуг , Полученный граф G’ является потоковым графом. 2. Дополнение полученного потокового графа вспомогательной дугой от стока к источнику. Дополнив полученный потоковый граф G’ дугой от стока к источнику WA(s), получим замкнутый потоковый граф G” . 3. Топологическое уравнения Мейсона для замкнутых потоковых графов. Найдем все петли графа G ” . Будем называть петлю петлей первого порядка. Петлей порядка п будем называть множество не связанных между собой петель первого порядка. Для каждой петли Lk первого порядка коэффициент пропускания Тк равен произведению коэффициентов пропускания ветвей, принадлежащих этой петле. тк = n * w eLki 35 Для петли порядка п эквивалентный коэффициент пропускания T(Ln) равен i w f p i i i п » . « ' *•»! к=\ eLtl Топологическое уравнение Мейсона для замкнутых потоковых графов имеет вид: 1+ E ( 1)/E 7’(i .) = 0 (2.26). /«! Выразим из полученного уравнения дугу W a ( s ) . 4. Вычисление математического ожидания и дисперсии. По определению функции Mjj(O), Mjj(s) = 1 при s=0. Следовательно, М, (s) = W,(s)/py= W(j(s)/Wij(0). (2.27). Вычисляя k-ю частную производную по s функции Mij(s) при s=0, находим left момент Mij = ~ Л /,( ,) ^ (2.28). Тогда Е(.Тц) =Ри> (779) л(т;.) = сг2= ^ ( д ') 2. Данный алгоритм был применен в задачах оценки времени выполнения операции на сложном конвейере, допускающем отбраковку, возврат детали на доработку [25] и т.п. Например, их применяют при оценке времени переработки сырья в производстве полупроводников, в производстве электроники и ремонте АУ электровоза [37; 75] и при управлении производственным процессом [6; 23; 26; 72]. Также позволяют получить качественно новые результаты при оценке времени выполнения распараллеленной задачи на неспециализированном вычислительном кластере Condor [24; 36; 60]. 36 |