Научный журнал

Современные наукоемкие технологии

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

• Авторы
• Файлы

Дегтерев А.С. Письман Д.М.

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

134 KB

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

Например, задача об оценке времени изготовления N деталей на конвейере, допускающем устранение брака в процессе производства, неразрешима стандартными ГЕРТ-сетями.

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

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

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

1. она представлена ориентированной связанной сетью;
2. она обладает, по крайней мере, одним источником и одним стоком;
3. каждый узел из N достижим, по крайней мере, из одного источника и из каждого узла достижим, по крайней мере, один сток;
4. заданы типы входящих и выходящих функций узлов;
5. задано начальное распределение вероятности выполнения источников q_sub, где subÍR;
6. в течение каждого выполнения проекта для каждого стока активируется не более одного источника, из которого данных сток достижим;
7. задан набор параметров, которыми обладает каждый активированный узел (по крайней мере, вероятность активации);
8. для каждой дуги указаны функции преобразования параметров активированного узла, вычислимые в момент его активации;
9. хотя бы один источник активируется в момент времени 0 (если параметр, отвечающий за время, определен).

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

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

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

Полученная модель позволяет легко ввести дополнительные параметры для узлов и функции их преобразования для дуг МГ-сети. Следовательно, ограничение на количество циклов стохастической сети можно записать в виде: p_ij=1-1(C-MaxC), p_ik=1(C-MaxC), где 1(x) - единичная ступенчатая функция, C - количество активации дуги <i, j> принадлежащей циклу, <i, k> - дуга «выход» из цикла, MaxC - максимальное количество циклов в ходе реализации.

В результате, возможность МГ-сети ограничить количество циклических переходов в реализации стохастической сети позволяет провести оценку времени изготовления MaxC деталей на конвейере, допускающем устранение брака в процессе производства.

Для этого введем следующие параметры узлов: p_i - вероятность активации узла, F_i(t) - функция распределения времени выполнения производства и C_i - количество произведенных деталей. Для каждого действия задается функция распределения времени его выполнения F_ij(t) или 1(0), если время нулевое. Вероятность изготовления нормальной детали - p_н, бракованной, доработка которой невозможна - p_бд, бракованной, доработка которой возможна - p_бн. Все узлы имеют EOR-вход и стохастический выход.

Действия:

<1, 2> Изготовление детали. p_ij = 1;

<2, 3> Изготовление нормальной детали. p_ij = p_н. С_ij=C_ij+1;

<2, 4> Изготовление бракованной детали, доработка которой невозможна. p_ij = p_бд;

<2, 5> Изготовление бракованной детали, доработка которой возможна. p_ij = p_бн;

<5, 2> Доработка детали. p_ij = 1;

<3, 1> Холостое действие. p_ij = 1-1(MaxC-C);

<3, 6> Холостое действие. p_ij = 1(MaxC-C).

Начальные значения источника: p₁ = 1, F₁(t) = 1(0), Counter=0.

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

1. K. Neumann. Stochastic Project Networks. Temporal Analysis, Scheduling and Cost Minimization. Springer-Verlag.
2. Лебедев В. А., Трохов Н. Н., Царев Р. Ю. Параллельные процессы обработки информации в управляющих системах. - Красноярск, НИИ СУВПТ, 2001. Стр. 84-133.
3. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей.-М.: Мир, 1984. стр. 387-411.
4. German Reinhard. Non-Markovian Analysis. In: n.b. (Hrsg.): Tutorial at the 2001 Aachen International Multiconference on Measurement, Modelling, and Evaluation of Computer-Communication Systems, (PNPM, MMB, and Probmiv/PAPM), 2001
5. German, Reinhard: Non-Markovian Analysis . In:n.b. (Hrsg.): Lectures on Formal Methods and Performance Analysis, First EEF/Summer School on Trends in Computer Science. Heidelberg: Springer, 2001, (LNCS Bd.2090), S.156-182
6. Bazan Peter; German Reinhard. An iterative approximate analysis method for non-Markovian models based on supplementary variables . In: n.b. (Hrsg.) : Proc. of in 12th GI/ITG Conference on Measuring, Modelling and Evaluation of Computer and Communication Systems (MMB & PGTS 04 (12th GI/ITG Conference on Measuring, Modelling and Evaluation of Computer and Communication Systems (MMB & PGTS 04 Dresden September 2004). 2004.

Библиографическая ссылка