Применение логики построений на графах к исполнению моделей бизнес-процессов

В последнее время были получены результаты, позволяющие синтезировать доказуемо правильные программы, которые реализуют иерархические [1] и сетевые [2] структуры вычислений. Существует целый ряд областей, в которых подобные подходы могу быть применены.

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

Если рассматривать задачи (аctivity в нотации BPMN [3] ) биз-нес-процесса, как программы, которые должны выполняться в соответствии с правилами, заданными моделью бизнес-процесса, то такой подход позволяет привнести в область управления бизнес-процессами (Business Process Management [4] ) сильные стороны доказательного программирования.

Поддержана Минобрнауки России по теме: «Исследования и разработка технических решений по теме Развитие инфраструктуры суперкомпьютерных центров в интересах инновационного развития государств участников СНГ» RFMEFI61314X0030.

○c Е. В. Кочуров, 2015

○c Институт программных систем имени А. К. Айламазяна РАН , 2015

○c Программные системы: теория и приложения, 2015

• 1.    Математическая модель

Пусть дан ориентированный граф G = ( V, E, begin , end ) , где

V           — множество вершин,

Е           — множество ребер, begin : Е ^ V  — функция, которая определяет вершину-начало ребра, end : Е ^ V   — функция, которая определяет вершину-конец ребра.

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

Для удобства будем использовать несколько дополнительных терминов для определения графов с определенными свойствами:

исходящее ребро е вершины v — такое, что begin (e) = v;

входящее ребро e вершины v — такое, что end (e) = v;

сеть        — ациклический граф;

связная сеть — сеть, которая состоит из единственной компоненты связности;

лес          — сеть, каждая вершина которой имеет не более одного входящего ребра;

дерево       — лес, который состоит из единственной компоненты связности;

начальная вершина — вершина сети, которая не имеет входящих ребер; конечная вершина — вершина сети, которая не имеет исходящих ребер.

Построением на графе G будем называть такую сеть

G s = ( V _S ,E _S , begin _s , ends ) , что существует отображение е, которое отождествляет вершины и ребра сети G _s с вершинами и ребрами графа G:

• a )    для любого х Е V _s : е(х) Е V ,

• b)    для любого х Е E _s : е(х) Е Е,

• c )    для любого х Е E _s : e( begin _s (x)) = begin (e(x)),

• d )    для любого х Е E _s : e( end _s (x)) = end (e(x)).

Содержательно, построение на графе G можно интерпретировать, как сеть из путей, допускаемых графом G. Введем отношение spiit (G, G1, G2) разбиения сети G = ( V, Е, begin , end ) на две компоненты G 1 = ( V 1 ,E 1 , begin i , end i ) и G 2 = ( V 2 , Е 2 , begin 2 , end 2 ) со следующими свойствами:

• i )    V 1 П V 2 = 0 ,

• ii )    V i U V 2 = V,

• iii )    Е 1 П Е 2 = 0 ,

• iv )    Для всякого ребра е е Е:

(е е E i ) V (е е Е 2 ) V ( begin (e) е V i Л end (e) е V 2 ).

Содержательно, отношение split разбивает сеть на компоненты связности либо, если это невозможно – на две сети так, чтобы связывающие их ребра были направлены строго в одном направлении.

Определение 1 . Будем называть отношение split модульным, если дополнительно выполняется свойство: подмножество всех ребер е из Е, таких, что begin (e) е V 1 &  end (e) е V 2 либо пусто, либо соединяет каждую конечную вершину G 1 с каждой начальной вершиной G 2 и только их.

Определение 2 . Будем называть сеть модульной, если она атомарна (состоит из единственной вершины без ребер), либо может быть разбита модульным отношением split на две модульных подсети.

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

• (1) Если А ^ В и В ^ С , то: А ^ (В ^ С ).

• (2) Если А ^ (В ^ С ), то: А ^ В и В ^ С .

• (3) Если А ^ В и В ^ С , то: (А ^ В ) ^ С .

• (4) Если (А ^ В ) ^ С , то: А ^ В и В ^ С .

• (5) Если А ^ В и А ^ С, то: А ^ (В

Рассмотрим следующую интерпретацию GL5. Граф G будем понимать, как модель бизнес-процесса: вершина графа интерпретируется, как задача, ребро – возможность передачи потока управления от одной задачи к другой.

Тогда теория в GL5 описывает задачи, которые могут возникнуть в ходе исполнения модели бизнес-процесса, а выводы в теории — сеть задач, которая реализует конкретный экземпляр бизнес-процесса.

Немаловажным аспектом использования логического вывода для решения практических задач является вычислительная эффективность. В большинстве случаев для этого выбирается фрагмент логики, который дает приемлемую вычислительную сложность. При разработке GL5 был применен другой подход, аналогичный примененному в работах Гуревича ( [6, 7] — система правил логического вывода изначально выбирается таким образом, чтобы обеспечить разрешимость и выводимость формул за линейное время.

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

Таким образом, постановка задачи на вывод в теории включает в себя:

∙ множество начальных вершин (одна или несколько задач, с которых начинается исполнение бизнес-процесса);

∙ множество промежуточных модульных подсетей (задачи или структуры задач, которые обязательно должны быть включены в вывод);

∙ множество конечных вершин (одна или несколько задач, по достижении которых исполнение бизнес-процесса можно считать завершенным).

2. Пример бизнес-процесса

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

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

Данный пример описывается теорией со следующими аксиомами:

• (9)    ПодготовитьДокумент(Автор) ^ Согласовать(Рецензент,Автор)

• (10)    Согласовать(Рецензент,Автор) ^ ИсправитьДокумент(Рецензент,Автор)

⇒ Согласовать(Рецензент,Автор)

• (11)    Согласовать(Рецензент,Автор) ^ ОпубликоватьДокумент .

Обращаем внимание на правило (10) – если рецензент высказал замечания к документу, задачу подготовки очередной версии документа следует адресовать тому же автору, от которого пришла предыдущая версия документа. Также следует обратить внимание на отсутствие скобок в правиле (10) – оно связано с ассоциативностью импликации в GL5.

Далее, пусть нам требуется бизнес-процесс, в котором документ должен быть согласован с двумя рецензентами Рецензент1 и Рецензент2 . Тогда постановка задачи на вывод выглядит следующим образом:

∙ Начать с :

o ПД(А)

∙ Пройти через :

• ∙ Завершить на :

o ОД

Сокращения:

ПД = ПодготовитьДокумент,

С = Согласовать,

ИД = ИсправитьДокумент,

ОД = ОпубликоватьДокумент,

А = Автор,

Р1 = Рецензент1,

Р2 = Рецензент2.

На первом шаге вывода по правилу (9) получим:

Требования « Начать с » и « Пройти через » выполнены, осталось выполнить требование « Завершить на ». После первого шага каждый из рецензентов получит входящее задание на согласование. Пусть Рецензент1 с документом согласился, а Рецензент2 – высказал замечания. Тогда на следующем шаге по правилам (11) для Рецензент1 и (10) для Рецензент2 мы получим:

Несмотря на то, что в выводе появилась вершина ОД , процесс не завершается, т.к. ОД не является единственной конечной вершиной. Далее, появилось новое входящее задание для Автора. После его выполнения будет сделан следующий шаг вывода:

Пусть теперь Рецензент2 согласен с документом:

В соответствии с правилами вывода GL5 данная формула преобразуется к виду:

Поскольку теперь достигнута искомая конечная вершина, бизнес-процесс завершается.

Заключение

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

Кроме того, описания бизнес-процессов становятся переиспользуемыми – на одном и том же множестве базовых правил (теории) могут порождаться различные схемы бизнес-процессов. Например, правила рецензирования (9) и (10) могут использоваться в нескольких различных бизнес-процессах, будь то простое согласование пресс-релиза, сразу же завершающееся его публикацией, или согласование договора, в рамках которого происходит последовательное согласование документа в нескольких службах с последующей отправкой по почте контрагенту.