IT-Reviews    

АЛГОРИТМ РАСЧЕТА МОДИФИЦИРОВАННОЙ ГЕРТ-СЕТИ

Рекомендуем: фильм Запрещенный прием (Россия) - пересказ сюжета, спойлеры
Источник:
Письман Д.М. Шабалин С.А. Статья в формате PDF 130 KB Стохастические ГЕРТ-сети [1] достаточно хорошо зарекомендовали себя в задачах оценки времени выполнения операции на сложном конвейере, допускающем отбраковку, возврат детали на доработку и т.п. Например, их применяют при оценке времени переработки сырья в производстве полупроводников, в производстве электроники и ремонте АУ электровоза [2, 3]. Также позволяют получить качественно новые результаты при оценке времени выполнения распараллеленной задачи на неспециализированном вычислительном кластере Condor [4, 5].

ГЕРТ-сеть требует выполнения условия марковости для вероятностей перехода по дугам (вероятность начала выполнения работы). Также ГЕРТ-сети не позволяют вводить дополнительные параметры для узлов-состояний и дуг-работ. Эти требования существенно ограничивают применимость данного метода моделирования.

Подробное описание ГЕРТ-сетей можно посмотреть в книге K. Neumann [1] и Д. Филлипс, А. Гарсиа-Диас [3].

Очень важными для стохастических сетей являются два понятия: выполнение и реализация сети. Выполнением сети будем называть процесс выполнения случайного эксперимента, тогда как реализацией сети будем называть итог одного случайного эксперимента.

Сеть G(N, A) называется МГ-сетью (модифицированной ГЕРТ-сетью), если:

  • она представлена ориентированной связанной сетью;
  • она обладает, по крайней мере, одним источником и одним стоком;
  • каждый узел из N достижим, по крайней мере, из одного источника и из каждого узла достижим, по крайней мере, один сток;
  • заданы типы входящих и выходящих функций узлов;
  • задано начальное распределение вероятности выполнения источников qsub, где subÍR;
  • в течение каждого выполнения проекта для каждого стока активируется не более одного источника, из которого данных сток достижим;
  • задан набор параметров, которыми обладает каждый активированный узел (по крайней мере, вероятность активации);
  • для каждой дуги указаны функции преобразования параметров активированного узла, вычислимые в момент его активации;
  • хотя бы один источник активируется в момент времени 0 (если параметр, отвечающий за время, определен).

Условие марковости для вероятностей перехода по дугам ГЕРТ-сети позволяет применять аналитические методы расчета параметров данной сети. В результате его исключения единственным методом расчета МГ-сети является численный расчет всех реализаций сети.

Любая сеть, обладающая хотя бы одним циклом, имеет бесконечное количество реализаций, однако вероятность выполнения реализации на каждом последующем витке цикла уменьшается в геометрической прогрессии, следовательно, их вклад в конечный результат так же сокращается.

Таким образом, реализация сети является допустимой, если в процессе выполнения каждый из активированных узлов сети активируется не более, чем maxA>=1 раз, или он активируется с вероятностью, большей minP>0.

Результатом расчета МГ-сети является множество реализаций, удовлетворяющих приведенным выше условиям.

Наиболее простой алгоритм расчета МГ-сети без узлов с IOR- и AND-входными функциями - это алгоритм генерации всех возможных обходов графа (в глубину или в ширину) с последующим расчетом каждого перехода.

Для расчета параметров узла с IOR- или AND-входной функцией необходимо знать параметры «концов» всех дуг, входящих в него. Необходимо учитывать, что для каждой дуги , входящей в узел j, существует множество путей заканчивающихся дугой . Следовательно, для построения множества реализаций, заканчивающихся узлом j с IOR- или AND-входной функцией, необходимо построить множество всех возможных выборов путей по одному из каждой дуги, входящей в узел j.

Реализация такого алгоритма расчета МГ-сети при прямом обходе графа достаточно сложна из-за необходимости «фиксации» реализаций заканчивающейся дугой, входящей в узел j, до того момента, пока все возможные реализации по каждой из дуг, входящих в j, не будут получены.

Для расчета МГ-сетей автором предлагается алгоритм обратного обхода графа от стока к источнику. Данный алгоритм похож на алгоритмом разбора арифметических выражений.

Пусть A, B, C, D, E - некоторые участки сети. «*»- операция объединения сетей от первого аргумента ко второму. «( , , ..., )» - операция параллельного объединения, где сеть стоящая слева от открывающей скобки заканчивается узлом с детерминированным выходом, сеть, стоящая справа от закрывающей скобки, начинается узлом с IOR- или AND-входом, а сети, перечисленные внутри скобок, параллельные участки, их соединяющие.

Рассмотрим работу алгоритм на примере сети вида A*(B, C, D)*E.

  1. Последовательно перемещаемся по всем узлам сети E до узла j с IOR- или AND-входной функцией.
  2. Рассчитываем параметры узлов сети A. Результат: множество реализаций WA.
  3. Используя полученное множество реализаций WA, рассчитываем параметры узлов сетей B, C, D. Результат: множества реализаций WB, WC, WD.
  4. Строим множество всех возможных выборов путей по одному из каждой дуги входящей в узел j и для каждой комбинации рассчитываем параметры узла j.
  5. Рассчитываем параметры узлов сети E.

Данный алгоритм использован в созданной библиотеке для расчета модифицированной ГЕРТ-сети. Рекламно техническое описание библиотеки можно получить в ОФАП.

СПИСОК ЛИТЕРАТУРЫ

  1. K. Neumann. Stochastic Project Networks. Temporal Analysis, Scheduling and Cost Minimization. Springer-Verlag.
  2. Лебедев В. А., Трохов Н. Н., Царев Р. Ю. Параллельные процессы обработки информации в управляющих системах. - Красноярск, НИИ СУВПТ, 2001. Стр. 84-133.
  3. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей.-М.: Мир, 1984. стр. 387-411.
  4. Дегтерев А.С., Письман Д.М. GERT-сетевой анализ времени выполнения задачи на неспециализированном гетерогенном кластере. Фундаментальные Исследования. № 4. 2005. Стр. 79-80.
  5. Письман Д.М. Модели оценки времени выполнения задачи на кластере с последовательной и параллельной архитектурой обмена данными. Вестник университетского комплекса: Сб. научн. Трудов / Под общей ред. Профессора Н.В. Василенко; Красноярск: ВСФ РГУИТП, НИИ СУВПТ. - 2005. Вып. 3 (17). Стр. 161-175.



Отзывы (через Facebook):

Оставить отзыв с помощью аккаунта FaceBook:

ДИДАКТИЧЕСКИЕ ПРИНЦИПЫ ОРГАНИЗАЦИИ ПРОДУКТИВНОЙ УМСТВЕННОЙ ДЕЯТЕЛЬНОСТИ ШКОЛЬНИКОВ ПРИ ФОРМИРОВАНИИ ЗНАНИЙ

Рассматривается проблема организации продуктивной умственной деятельности учащихся общеобразовательных учреждений в системе дидактических принципов современной педагогики. Анализ принципов показывает, что отечественная дидактика в большой мере сохраняет черты традиционной модели обучения и недостаточно учитывает психологическую природу мышления и закономерности продуктивной умственной деятельности при разработке принципов обучения. Выделены основополагающие принципы организации продуктивной умственной деятельности на основе закономерностей развития знания и процесса познания, психологических закономерностей мышления. ...

09 05 2021 5:15:36

СИНТЕЗ САМАРИЙ-ХРОМАЛЮМИНИЕВОГО ГРАНАТА

Статья в формате PDF 273 KB...

05 05 2021 4:18:43

АЛГОРИТМ РАСЧЕТА МОДИФИЦИРОВАННОЙ ГЕРТ-СЕТИ

Статья в формате PDF 130 KB...

03 05 2021 10:25:48

ПРЕПОДАВАНИЕ ЭКОЛОГИИ В ТЕХНИЧЕСКОМ УНИВЕРСИТЕТЕ

Статья в формате PDF 110 KB...

01 05 2021 15:35:50

ПЕРЕСЕЛЕНЧЕСКИЙ КАПИТАЛИЗМ В США

Статья в формате PDF 320 KB...

23 04 2021 12:33:31

ЦИФРОВОЙ МОДЕМ ДЛЯ СЕТИ ISDN

Статья в формате PDF 297 KB...

19 04 2021 12:33:21

ОРГАНИЗАЦИЯ УПРАВЛЕНИЯ ПЕРСОНАЛОМ

Статья в формате PDF 103 KB...

17 04 2021 9:13:34

МОДЕЛЬ ПРОЦЕССА ПЕРЕНОСА КОЛИЧЕСТВА ЗАРЯДА – ЭЛЕКТРИЧЕСКАЯ ПРОВОДИМОСТЬ РАСТВОРОВ ХЛОРОВОДОРОДА В Н-СПИРТАХ

Ранее авторами была показана применимость плазмоподобной теории растворов для расчетов эквивалентной электропроводности растворов различных электролитов в воде и этаноле. В данной статье были экспериментально измерены значения электропроводности хлороводорода в четырех н-спиртах (этаноле, пропаноле, бутаноле и пентаноле) при различных температурах (278-328 К), а также получены расчетные значения электропроводности. Сделан вывод о хорошем соответствии расчетных данных экспериментальным. ...

16 04 2021 23:37:36

АНТИЦИПАТИВНЫЙ АНТИКРИЗИСНЫЙ МАРКЕТИНГ

Статья в формате PDF 342 KB...

15 04 2021 12:12:45

ИСТОРИЯ РАЗВИТИЯ ИСТИННЫХ УЧИТЕЛЕЙ

Статья в формате PDF 104 KB...

13 04 2021 7:18:55

ИММУНОЛОГИЧЕСКИЕ ПОКАЗАТЕЛИ ДЕТЕЙ г. КРАСНОЯРСКА

Статья в формате PDF 109 KB...

12 04 2021 22:50:22

АКСИОЛОГИЧЕСКИЕ АСПЕКТЫ ЗДОРОВОГО ОБРАЗА ЖИЗНИ

Статья в формате PDF 119 KB...

10 04 2021 5:24:14

ВЫВОД УРАВНЕНИЙ МАКСВЕЛЛА ИЗ ФУНКЦИИ СОСТОЯНИЯ. ЗАРЯДОВАЯ ФУНКЦИЯ СОСТОЯНИЯ И ЕЁ СВЯЗЬ С ЗАКОНОМ СОХРАНЕНИЯ ЗАРЯДА

На основе введённых функций состояния для электромагнитного поля и зарядовой функции состояния для частиц выведена полная система уравнений Максвелла для электродинамики. Показано, что закон сохранения зарядов есть следствие существования этой функции. Показано также, что в вакууме электромагнитное поле отсутствует, что подтверждает справедливость теории дальнодействия. ...

05 04 2021 19:29:30

ТИПОГРАФИКА (учебное пособие)

Статья в формате PDF 116 KB...

02 04 2021 1:28:32

ГАЗИФИКАЦИЯ ОРГАНИЧЕСКИХ ТОПЛИВ И БИОМАСС

В последние годы для сжигания как традиционных топлив, так и биомасс различного происхождения широко применяются газификационные технологии. Газификация чаще всего производится в кипящем слое при недостатке окислителя. Конструкции установок по газификации различных топлив отличаются, но не принципиально. Также близкими оказываются и параметры генераторного газа. Необходимо развитие установок и технологий по совместной переработке различных топлив. ...

21 03 2021 6:29:44

РАЗРАБОТКА АЛГОРИТМИЧЕСКИХ МОДЕЛЕЙ ОТБРАКОВОЧНЫХ ИСПЫТАНИЙ РПУ

Разработан пакет графических алгоритмических моделей отбраковочных испытаний радиоприемных устройств, изготавливаемых и выпускаемых предприятием, как первый шаг к последующей автоматизации. Показано преимущество разработанных моделей по сравнению с действующей текстовой инструкцией по проведению испытаний. ...

16 03 2021 17:12:16

ВОЗМОЖНЫЕ НАПРАВЛЕНИЯ ПСИХОЛОГИЧЕСКОЙ АДАПТАЦИИ ЛИЦ ПОЖИЛОГО ВОЗРАСТА

Изменяющиеся условия жизни приводят к изменению поведения и психологии наиболее уязвимых групп населения, к которым относятся пожилые и старые люди. Наиболее значимыми считаются адаптивные защитные реакции, такие как озабоченность, тревожность, депрессия. Работа поддержана и финансируется Министерством образования и науки. ...

13 03 2021 10:56:55

НЕКОТОРЫЕ АСПЕКТЫ НАРКОПРЕСТУПНОСТИ

Статья в формате PDF 251 KB...

12 03 2021 21:12:32

О СТРОЕНИИ И ТОПОГРАФИИ КРАНИАЛЬНЫХ БРЫЖЕЕЧНЫХ ЛИМФАТИЧЕСКИХ УЗЛОВ У НОВОРОЖДЕННЫХ БЕЛОЙ КРЫСЫ

Краниальные брыжеечные лимфатические узлы у новорожденных белой крысы располагаются главным образом вдоль ствола одноименной артерии и отличаются слабо дифференцированной паренхимой. ...

02 03 2021 11:46:32

К ПРОБЛЕМЕ ОТБОРА В ХОККЕЕ

Статья в формате PDF 262 KB...

01 03 2021 3:50:23

ЛИТЕРАТУРНОЕ ОБРАЗОВАНИЕ ДЕТЕЙ: КРИЗИС ЧТЕНИЯ

Статья в формате PDF 265 KB...

28 02 2021 14:25:18

Бозаджиев Владимир Лукьянович

Статья в формате PDF 144 KB...

24 02 2021 18:35:47

РОЛЬ АУДИТОРИИ В УЧЕБНОМ ПРОЦЕССЕ

Статья в формате PDF 108 KB...

14 02 2021 4:51:43

МОНИТОРИНГ НЕФТЯНОГО ЗАГРЯЗНЕНИЯ ВИННОВСКОЙ РОЩИ

Статья в формате PDF 305 KB...

08 02 2021 11:22:43

ВОДНЫЙ РЕЖИМ РЕК СЕВЕРО-ЗАПАДНОГО КАВКАЗА

Статья в формате PDF 126 KB...

06 02 2021 3:37:49

СОЦИАЛЬНЫЕ ФАКТОРЫ ЭЛЕКТОРАЛЬНОЙ ГЕОГРАФИИ

Территориальные различия электоральных предпочтений отличаются высокой устойчивостью в современной России. Этот феномен подтверждается методом корреляционного анализа. Выделяются шесть основных социальных факторов, влияющих на различия в электоральной географии: 1) доля городского населения; 2) приближенность к центру; 3) этнический фактор; 4) доля молодежи в составе населения; 5) преобладающие виды деятельности населения; 6) структура социальных связей. Электоральное поведение в России менее индивидуально, чем в западных странах, большее значение имеют объективные социальные факторы. ...

03 02 2021 21:57:14

ЮРЬЕВ АЛЕКСАНДР ГАВРИЛОВИЧ

Статья в формате PDF 320 KB...

29 01 2021 20:57:49

ЗДОРОВЬЕ ДЕТЕЙ ЛИЦ, ПЕРЕБОЛЕВШИХ ХЛОРАКНЕ

Статья в формате PDF 109 KB...

22 01 2021 19:58:24

ДИНАМИКА СОДЕРЖАНИЯ БЕЛКОВ В СЫВОРОТКЕ КРОВИ СЕГОЛЕТОК КАРПА ПРИ ХРОНИЧЕСКОМ ВОЗДЕЙСТВИИ ТЯЖЕЛЫХ МЕТАЛЛОВ

Изучено влияние солей кадмия, свинца и марганца на содержание белков в сыворотке крови сеголеток карпа. Показаны разнонаправленные изменения белкового состава сыворотки крови рыб при воздействии солей тяжелых металлов, о чем можно судить на основании изменения А/G индекса. При хроническом действии ионов кадмия отмечено значительное преобладание суммарного содержания альбуминов над глобулинами на протяжении всего эксперимента, пребывание рыб в среде с ионами свинца сопровождалось более значительным ростом содержания глобулинов, тогда как при действии ионов марганца не выявлен однонаправленный характер изменения соотношения альбуминов и глобулинов. ...

20 01 2021 1:38:45

УНИВЕРСАЛЬНОЕ ИСКУССТВОЗНАНИЕ КАК НАУЧНОЕ НАПРАВЛЕНИЕ

В статье доктора искусствоведения профессора Саратовской консерватории, члена-корреспондента Российской академии естествознания даётся обоснование нового научного направления – универсального искусствознания, целью которого является комплексное исследование художественного процесса с вовлечением всех видов искусства в их глобальном охвате, а также построение художественной картины мира как особого рода исторической памяти. ...

03 01 2021 21:34:45

ФУНКЦИИ СЕТЕВОГО ТРОЛЛИНГА

Статья в формате PDF 257 KB...

31 12 2020 16:20:55

РОЛЬ ГОСУДАРСТВА В УСЛОВИЯХ ГЛОБАЛИЗАЦИИ

Статья в формате PDF 277 KB...

30 12 2020 19:43:53

ВЛИЯНИЕ ХАРАКТЕРИСТИК СТРУКТУРНОЙ ГЕТЕРОГЕННОСТИ НА ПРОЦЕССЫ ИЗНАШИВАНИЯ ТЕРМОДИФФУЗИОННЫХ ПОКРЫТИЙ

В течение продолжительного времени проводились триботехнические испытания различных термодиффузионных покрытий на изнашивание при трении скольжения. Они позволили сделать ряд принципиальных обобщений по взаимообусловленности структурного состояния покрытий и кинетики процессов износа. В результате моделирования фрикционных процессов широкого класса материалов было получено эмпирическое уравнение для коэффициента трения, отражающее параметрическое влияние свойств материала покрытий, реологию поверхностного трения и свойство смазочного материала. ...

28 12 2020 1:41:16

АНАЛИЗ ГИДРОГЕОХИМИЧЕСКОЙ ИНФОРМАЦИИ

Статья в формате PDF 140 KB...

27 12 2020 10:37:19

Качество жизни детей, больных вирусными гепатитами

Статья в формате PDF 136 KB...

26 12 2020 13:16:39

СОСТОЯНИЕ НЕКОТОРЫХ ПОКАЗАТЕЛЕЙ ОКИСЛИТЕЛЬНОВОССТАНОВИТЕЛЬНЫХ ПРОЦЕССОВ У БОЛЬНЫХ ОСТРЫМ ХОЛЕЦИСТИТОМ И ИХ КОРРЕКЦИЯ

Под наблюдением автора было 262 больных острым холециститом. Обсуждаются вопросы адаптации больных к условиям операционного и послеоперационного периодов, которая зависит от окислительно-восстановительных процессов, обусловленных функционированием ферментативных систем, гипоксии тканей, снижения приспособительных реакций, особенно выраженных у лиц старше 50 лет. В контрольной группе (178) больных уже при поступлении в клинику намечалась тенденция к снижению Р О2 в подкожно-жировой основе, а в момент операции оно было выраженным и устойчивым, которое держалось в течение 6 дней. Так же на всем протяжении послеоперационного периода у больных наблюдалось уменьшение кислородной емкости крови, концентрации SH-групп в плазме крови, только к моменту выписки эти показатели приближались к норме. Концентрация молочной и пировиноградной кислот крови тоже было повышенным. В исследуемой группе (84) больных, которые получали в комплексном лечении во время операции и послеоперационном периоде ганглиоблокаторы и гепарин, напряжение кислорода во время операции повышалось на 68%, повышение сохранялось 2-3 дня, а к концу 5 дня р О2 было в пределах нормы. Намечалась тенденция увеличения кислородной емкости крови и SH-групп в плазме. Не смотря на то, что при поступлении лактат и пируват были выше контроля, уже в первый день после операции эти показатели были ниже контрольных. Автор делает вывод о том, что применение в комплексном лечении ганглиоблокаторов и гепарина, позволяло улучшать кислородный баланс крови и ткани и, улучшать окислительновосстановительные процессы, адаптацию организма больного к стрессовым условиям, что способствовало снижению процента послеоперационных осложнений и летальности. ...

22 12 2020 4:47:35

Молекулы средней массы плазмы крови при сифилисе

Статья в формате PDF 106 KB...

21 12 2020 10:21:38

ЛЕЧЕНИЕ БОЛЬНЫХ С УКУШЕННЫМИ РАНАМИ

Статья в формате PDF 121 KB...

20 12 2020 18:56:56

ПСИХОСОМАТИЧЕСКИЙ ПОДХОД В ГЕРОНТОПСИХИАТРИИ

Статья в формате PDF 95 KB...

15 12 2020 23:10:49

Еще:
Обзоры -1 :: Обзоры -2 :: Обзоры -3 :: Обзоры -4 :: Обзоры -5 :: Обзоры -6 :: Обзоры -7 :: Обзоры -8 :: Обзоры -9 :: Обзоры -10 :: Обзоры -11 ::

Последовательность подготовки научной работы может быть такой:

Выбор темы. Это важный этап. Во-первых, тема должна быть интересна не только вам, но и большинству слушателей, которым вы будете её докладывать, чтобы вы видели заинтересованность в их глазах, а не откровенную скуку.

Выбор целей и задач своей научной работы. То есть, нужно сузить тему. Например, тема: «Грудное вскармливание», сужение темы: «Грудное вскармливание среди студенток нашего ВУЗа». И если общая тема мало кому интересна, то суженная до рамок собственного института или университета, она становится интересной практически для всех слушателей. Целью может стать: «Содействие оптимальным условиям вскармливания грудью детей студентов нашего ВУЗа», а задачей — доказать, что специальные условия, созданные для кормящих студенток, не помешают их успеваемости, но уменьшат количество пропусков, академических отпусков и способствуют выращиванию здоровых детей — нашего будущего. Понятно, что эта тема подходит для студентов медицинских и педагогических ВУЗов, но и в других учебных учреждениях можно найти темы, интересные всем.

Разработать методы исследования и сбора информации. В случае с естественным вскармливанием, скорее всего, это будет анкетирование студенток, имеющих детей.

Систематизировать материал и подготовить презентацию.

Подготовиться к выступлению.

Выступить и получить: награду, удовольствие и опыт, чтобы в следующем году выступить ещё лучше и сорвать шквал аплодисментов, стать узнаваемым, а значит — более конкурентоспособным!