GERT-сетевой анализ производственных процессов

Антамошкина Е.А. (nii suvpt@wave.krs.ru)(1), Дегтерев А.С.(2), Ерыгин Ю.В.(1)

(1)Сибирский государственный аэрокосмический университет, (2)ФГУП ЦКБ «Геофизика»

Ранее нами рассматривались оптимизационные модели производственных процессов в детерминированной постановке (в [1] - оптимизации производственной программы, в [2] - оптимизации инновационной программы). Однако в реальности на реализацию производственных процессов влияют многие случайные факторы, основными из которых являются финансовые поступления и изменение конъюнктуры рынка.

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

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

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

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

Процедура, предлагаемая для анализа вероятностных характеристик процесса реализации производственных операций, базируется на стохастических сетях типа GERT (Graphical Evaluation and Review Technique) [5] и совмещает теорию потоков в графах, функции генерации момента и PERT - анализ [4] для получения результата. Можно установить следующие соотношения между сетями PERT-типа, графами с потоками и стохастическими сетями.

1.Сети PERT-типа соответствуют стохастическим GERT-сетям, в которых все узлы являются детерминированными "И"-узлами (And - Deterministic).

2.Графы с потоками соответствуют стохастическим сетям с простым мультипликативным параметром (все аддитивные параметры, такие как время, установлены равными нулю). Вероятностная интерпретация для мультипликативного параметра исключена из рассмотрения.

Рассмотрим реализацию производственного процесса (программы), заданную сетью G=(N, A), которая содержит только GERT-узлы, образующие множество N. Пусть время выполнения операции (i, j) (для стохастической интерпретации реализации) есть случайная величина Иц. По определению (i, j) может быть

выполнена только в том случае, если выполнен узел i. Поэтому для изучения вопросов, связанных с выполнением этой операции, необходимо знать условную вероятность (в дискретном случае) случайной величины H ц при условии, что узел i

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

В [4] описаны некоторые наиболее важные функции распределения и указаны соответствующие производящие функции моментов и первые (математические ожидания) и вторые центральные моменты.

Пусть рц - вероятность того, что операция (i, j) будет выполнена при условии,

что узел i выполнен. Для случайной величины Hj определим W-функцию как Wtj (s) = pi]Mi] (s), где Mj - условная производящая функция моментов случайной величины Hij [4].

С помощью этого преобразования всегда можно определить сеть G, структура которой идентична структуре сети G, только вместо двух параметров дуг p j и H j

присутствует один параметр Wij.

Согласно системе GERT-моделей можно включить в описание в качестве параметра дуги время выполнения соответствующей операции производственного процесса. Однако в действительности можно рассматривать любой характерный параметр, обладающий аддитивностью по дугам любого пути. Если времена выполнения сети G представляются независимыми случайными величинами, то для G справедливы правила эквивалентности (с вычислительной точки зрения):

а)для случая, когда G состоит из двух последовательных дуг;

б)G - из двух параллельных ветвей;

в)G - из одной ветви и одной петли.

Перечислим основные этапы решения поставленных задач моделирования посредством стохастических сетей типа GERT.

1.Перевести качественное описание рассматриваемых производственных процессов в GERT-сетевую модель.

2.Собрать необходимые структурные данные для описания связей в GERT-сети (включая характеристики операций).

3.Применить топологическое уравнение для определения эквивалентной функции (или функций) GERT-сети.

4.Вычислить через эквивалентную функцию две следующие характеристики функционирования сети:

-вероятность выполнения конкретного узла;

-функции генерации момента для времени, связанного с узлом, если он выполняется.

5.Сделать выводы относительно реализации производственных процессов на основе информации, полученной в пункте 4.

В нашем случае важно рассмотреть подход к минимизации времени и максимизации прибыли при анализе реализуемости с учетом стохастической реализации производственного процесса. Первоначально рассмотрим простой ациклический детерминированный процесс, который имеет "GERT-подобную узловую логику" [6]. Такую модель будем называть сетью для планирования. Термин "планирование/решение" показывает, что осуществляется процесс выбора, т. е. принимается решение о том, какие операции должны быть выполнены для оптимизации некоторой целевой функции. Это приводит к задаче комбинаторной оптимизации, частным случаем которой является, например, "decision CMP" - метод критического пути для случая, когда присутствуют только узлы двух типов AND и OR [7].

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

Пусть N - ациклическая сетевая модель с источниками и стоками (действия, соответствующие операциям процесса, представляются дугами), где множество узлов обозначается V, а множество дуг - E. Предположим, что N имеет только один исток, который обозначается через r и соответствует началу рассматриваемого процесса. Предполагается также, что один из стоков N представляет собой успешное завершение и обозначается s. Оставшиеся стоки, если они есть, могут представлять собой различные виды неудачного завершения или прерывания. Будем использовать следующие Определения, введенные в [8].

Определение (1) Ациклическую сетевую модель - N(V,E) только с одним истоком и со стоками назовем сетью для планирования/решения, если каждый узел i из N определен через входную характеристику X- е 0,1,...,\p(i) и выходную

характеристику X+ е 0,1,...,\S(i), где множество узлов обозначается V, а множество

дуг - E; \P(i)\, \Sмощность множества предшественников и последователей узлов I