Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

Personal portfolio

Стохастические ГЕРТ-сети [1] достаточно хорошо зарекомендовали себя в задачах оценки времени выполнения операции на сложном конвейере, допускающем отбраковку, возврат детали на доработку и т.п. Например, их применяют при оценке времени переработки сырья в производстве полупроводников, в производстве электроники и ремонте АУ электровоза [2, 3].

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

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

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

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

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

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

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

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

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

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

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

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

Действия:

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

<2, 3> Изготовление нормальной детали. pij = pн. Сij=Cij+1;

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

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

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

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

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

Начальные значения источника: p1 = 1, F1(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.