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:

Изомерия и гомеостаз популяций

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

27 01 2020 2:13:15

ЭКОЛОГИЯ СИБИРСКОГО РЕГИОНА: К ИСТОРИИ ПРОБЛЕМЫ

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

26 01 2020 5:19:47

МОТОВИЛОВ КОНСТАНТИН ЯКОВЛЕВИЧ

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

20 01 2020 23:30:47

ПРОБЛЕМА ПОЛУЧЕНИЯ ВЫСОКОКАЧЕСТВЕННОГО ФАРФОРА

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

16 01 2020 8:30:40

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

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

11 01 2020 13:30:34

ДИНАМИЧЕСКАЯ МОДЕЛЬ КОНКУРЕНЦИИ ДВУХ ФИРМ НА ОДНОРОДНОМ РЫНКЕ

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

04 01 2020 1:12:34

НЕКОТОРЫЕ АСПЕКТЫ СОВЕРШЕНСТВОВАНИЯ ТЕХНОЛОГИИ ХЛЕБА ИЗ ЦЕЛОГО ЗЕРНА

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

01 01 2020 16:38:29

ТЕРАПЕВТИЧЕСКАЯ ИГРА КАК МЕТОД ОБУЧЕНИЯ ПАЦИЕНТОВ

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

22 12 2019 22:44:31

МОДУЛЬНЫЕ ТЕХНОЛОГИИ РЕАЛИЗАЦИИ УЧЕБНОГО ПРОЦЕССА

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

20 12 2019 8:16:49

КОНТАКТНАЯ АКТИВАЦИЯ АРТЕРИАЛЬНОЙ КРОВИ

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

15 12 2019 2:17:44

Максимальная скорость окисления оксида азота

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

11 12 2019 22:39:21

КОНВЕКЦИЯ СМЕСЕЙ В МАГНИТНОМ ПОЛЕ

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

06 12 2019 12:22:37

РОЛЬ ВОДЫ В ОСНОВНЫХ СТРУКТУРАХ ЖИВОГО ОРГАНИЗМА

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

01 12 2019 22:42:39

РАСПРОСТРАНЕНИЕ ПОЛИМОРФИЗМА ИНТЕРЛЕЙКИНА – 8 – 251 ТА СРЕДИ ЖЕНЩИН АЗЕРБАЙДЖАНА БОЛЬНЫМИ ЭНДОМЕТРИОЗОМ

Впервые было изучено интерлейкина – 8 – 251 Т А среди женщин Азербайджана больными эндометриозом. 50 практически здоровых и 70 женщин больных эндомертиозом находились под нашем наблюдением. Исследование показали что, генетический полиморизм интерлейкина – 8 А/ Т 251 играет роль в потогенезе эндометриоза. ...

25 11 2019 13:25:58

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

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

24 11 2019 13:29:44

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

При управлении автоматическими космическими аппаратами ( К А) важной проблемой является обеспечение надежного и оперативного анализа и диагностирования работоспособности бортовых систем. Это позволит своевременно выявить негативные тенденции в работе бортовой аппаратуры и предотвратить их развитие. Наибольшую актуальность проблема приобретает при управлении К А со сложными бортовыми системами, характеризующимися большим объемом телеметрических параметров, а так же при необходимости выдачи командных воздействий непосредственно в сеансах связи. Существующий опыт управления К А показывает, что в ряде случаев только своевременная выдача команд немедленного исполнения позволила обеспечить выполнение программы полета К А [1]. В настоящей работе предлагается общий подход к решению указанной проблемы, основанный на создании адекватных моделей анализа и диагностики функционирования бортовых систем и алгоритмов автоматизированной выработки рекомендаций по воздействию на К А. Ожидается, что использование в практике управления таких моделей и алгоритмов даст возможность существенно повысить эффективность работы аппаратуры, в том числе за счет оперативного устранения возникающих на борту нештатных ситуаций. ...

18 11 2019 10:58:34

ГЛУЩЕНКО ЛЮДМИЛА ФЁДОРОВНА

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

12 11 2019 23:35:31

РОЖИХИНА ИРИНА ДМИТРИЕВНА

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

08 11 2019 17:37:46

ИСКУССТВОВЕДЕНИЕ В СИСТЕМЕ ГУМАНИТАРНОГО ЗНАНИЯ

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

01 11 2019 1:39:34

К ОЦЕНКЕ КАЧЕСТВА ВОД ОЗЕР ЯКУТСКА

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

30 10 2019 21:19:37

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

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

28 10 2019 3:20:18

СТОЙКОСТЬ ПРОМЫШЛЕННО ОПАСНЫХ ОБЪЕКТОВ

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

26 10 2019 16:39:53

МЕТОДЫ УПРОЧНЕНИЯ ИОННО-ПЛАЗМЕННОЙ ОБРАБОТКОЙ

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

25 10 2019 13:56:10

ЭКОЛОГИЧЕСКАЯ БЕЗОПАСНОСТЬ И ЗДОРОВЬЕ НАСЕЛЕНИЯ

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

23 10 2019 3:20:55

Клиника и лечение кишечного амебиаза

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

18 10 2019 13:42:53

ПРОБЛЕМЫ ЕСТЕСТВЕННОНАУЧНОГО ОБРАЗОВАНИЯ

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

08 10 2019 6:26:20

ОСОБЕННОСТИ ГУМУСООБРАЗОВАНИЯ В СТЕПНОЙ ЗОНЕ ТУВЫ

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

01 10 2019 14:31:40

Селицкий Александр Яковлевич

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

29 09 2019 23:44:13

ГРИПП. КЛИНИЧЕСКАЯ СИМПТОМАТИКА

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

19 09 2019 13:39:22

АЛЕКСАНДР НАЗАРОВИЧ БЕЛЯЕВ

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

18 09 2019 22:35:27

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

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

17 09 2019 23:56:47

ФАКТОРЫ ОБЕСПЕЧЕНИЯ КОНКУРЕНТОСПОСОБНОСТИ ТОВАРОВ

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

09 09 2019 13:17:16

КЛЕТКИ СТЕКЛОВИДНОГО ТЕЛА ГЛАЗА ЧЕЛОВЕКА

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

05 09 2019 19:49:39

МИРОВАЯ КУЛЬТУРА В СИСТЕМЕ РАЗВИТИЯ ЕСТЕСТВЕННОНАУЧНОГО ИНТЕЛЛЕКТА УЧАЩИХСЯ

Умелое использование сокровищницы мировой культуры, достойное место в которой занимают поэтические и художественные произведения М. В. Ломоносова, М. И. Алигер, И. В. Гёте, И. А. Ефремова, К. Г. Паустовского, в педагогической практике обеспечивает эффективное развитие естественнонаучного интеллекта и формирование мировоззрения школьников. ...

03 09 2019 18:20:35

РОССИЙСКАЯ АКАДЕМИЯ ЕСТЕСТВОЗНАНИЯ

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

31 08 2019 9:55:10

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

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

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

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

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

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

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

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