Применение логики построений на графах к исполнению моделей бизнес-процессов
Автор: Кочуров Евгений Владимирович
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Искусственный интеллект, интеллектуальные системы, нейронные сети
Статья в выпуске: 4 (27) т.6, 2015 года.
Бесплатный доступ
В статье предлагается подход к исполнению бизнес-процессов, который основан на логическом синтезе программ по модели бизнес-процесса. В подходе используется логика построений на графах GL5
Моделирование бизнес-процессов, построения на графах, конструктивная логика
Короткий адрес: https://sciup.org/14336174
IDR: 14336174
Текст научной статьи Применение логики построений на графах к исполнению моделей бизнес-процессов
В последнее время были получены результаты, позволяющие синтезировать доказуемо правильные программы, которые реализуют иерархические [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) могут использоваться в нескольких различных бизнес-процессах, будь то простое согласование пресс-релиза, сразу же завершающееся его публикацией, или согласование договора, в рамках которого происходит последовательное согласование документа в нескольких службах с последующей отправкой по почте контрагенту.
Список литературы Применение логики построений на графах к исполнению моделей бизнес-процессов
- Е. В. Кочуров. Конструктивный синтез пользовательских интерфейсов Web-приложений//Программные системы: теория и приложения, Т. 4, №. 4(18). 2013. С. 3-25, URL: http://psta.psiras.ru/read/psta2013_4_45-59.pdf.
- Е. В. Кочуров, Н. Н. Непейвода, И. Н. Григоревский. Замечания о логиках построений на графах и их применении//Вторая международная научно-практическая конференция "Технические науки: теория, методология и практика", Сб. науч. докл. (г. Москва, 28 ноября 2014 г.), АНО Издательский дом "Научное обозрение", М., 2014. С. 8-18.
- BPMN Specification -Business Process Model and Notation (дата обращения: 30.11.2015), URL: http://www.bpmn.org/.
- Business process management -Wikipedia, the free encyclopedia (дата обращения: 30.11.2015), URL: https://en.wikipedia.org/wiki/Business_process_management.
- Е. В. Кочуров. Об одной конструктивной логике построений на графах//Девятые Смирновские чтения по логике, Материалы международной научной конференции (г. Москва, 17-19 июня 2015 г.), Издательство "Современные тетради", М., 2015. С. 22-24.
- Yu. Gurevich, I. Neeman. DKAL: Distributed-Knowledge Authorization Language//21st IEEE Computer Security Foundations Symposium CSF 2008 (June 23-25, 2008, Carnegie Mellon University, Pittsburgh, USA). P. 149-162.
- Yu. Gurevich, I. Neeman. Logic of infons: The propositional case//ACM Transactions on Computational Logic, 12 2011. P. 1-28.