Построение BPMN-модели процесса, поведенчески эквивалентной заданной каузальной сети - Дипломная работа

Национальный исследовательский университет Высшая школа экономики Кафедра Управления разработкой программного обеспечения На тему: Построение BPMN-модели процесса, поведенчески эквивалентной заданной каузальной сетиК тому же BPMN-модели обладают рядом положительных особенностей: модели могут быть импортированы и выполнены в любой BPMN-ориентированной программной системе; модели подходят для интеграции с точки зрения различных перспектив (от перспективы потока управления до перспективы ресурсов). С другой стороны, каузальные сети (causal nets, C-nets) - одна из основных моделей, рассматриваемая в рамках этой работы и широко используемая в системе PROM [5] - основаны на декларативной семантике, обеспечивающей только корректное поведение, то есть свободное от различных процессных аномалий: взаимных блокировок (deadlocks), ?зацикливаний? (livelocks) и других ошибок синхронизации. В работе используются понятия сетей Петри и work?ow-сетей (WF-сетей) для оценки семантики каузальных сетей и BPMN-моделей. Рассмотрим отношение между каузальными сетями и сетями Петри (WF-сетями в частности). Тогда помеченная система переходов, построенная по данной сети, определяется как LTS = (P;Act;!), где P множество состояний каузальной сети, достижимых из начального состояния 0, Act множество действий каузальной сети, участвующих хотя бы в одной связи = (a;ASI;ASO), такой что O jВ рамках работы была решена актуальная задача преобразования каузальной сети в BPMN-модель. Каузальные сети используются в рамках дисциплины Process Mining как результат извлечение модели процесса из лога этого процесса, так как семантика C-net не рассматривает последовательности действий с ошибками синхронизации.

Оглавление

1 Обзор используемых моделей 5 1.1 Сети Петри и WF-сети . . . . . . . . . . . . . . . . . . . . . 5 1.2 Каузальные сети . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Системы переходов . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 BPMN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Посtrialие BPMN-модели процесса по каузальной сети 14 2.1 Ограничения преобразования . . . . . . . . . . . . . . . . . 14 2.2 Приведение C-net к LTS . . . . . . . . . . . . . . . . . . . . 15 2.3 Соответствие каузальной сети и BPMN-модели . . . . . . . 16 2.3.1 Построение BPMN-модели по каузальной сети . . . 16

2.3.2 Пример построения . . . . . . . . . . . . . . . . . . . 18 2.3.3 Приведение BPMN-модели к LTS . . . . . . . . . . . 19 2.3.4 Корректность построения BPMN-модели по каузальной сети . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 Анализ результатов 24 3.1 Оценка сложности алгоритма преобразования . . . . . . . . 24 3.2 Плагин BPMNCONVERSIONS для PROM . . . . . . . . . . . . . 25

1

Process mining (извлечение моделей процессов) - относительно новая и стремительно развивающаяся дисциплина, изучающая взаимосвязь журнала (лога) событий некоторого бизнес-процесса и модели этого процесса, описанная в [4]. Лог процесса (process log) представляет собой последовательность сценариев (cases), каждый из которых является упорядоченной последовательностью действий (activities), происходящих в рамках некоторой деятельности. Также логи могут хранить некоторую метаинформацию: время выполнения действий, исполнителей, стоимость, и т.д. Запись лога в реальных бизнес-процессах обычно осуществляется специальной информационной системой; количество записей может быть значительным, что делает анализ ?вручную? крайне неэффективным. Таким образом, process mining как дисциплина лежит на стыке машинного обучения и data mining с одной стороны и моделированием процессов - с другой.

Важно отметить, что основная идея дисциплины это обнаружение, отслеживание и улучшение реальных процессов с помощью информации, находящейся в логе. В итоге, проецируя данные цели на отношения между логом и моделью процесса, можно определить три основные задачи process mining: извлечение модели процесса (discovery), проверка согласованности модели и лога (conformance checking) и улучшение модели (enhancement). Эти задачи представлены на рис. 1.

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

2

Рис. 1: Основные задачи process mining ничениями. Подобные особенности образуют смещение представления (representational bias), которое значительно влияет на границы моделируемого поведения.

BPMN 2.0 (BPMN) - Business Process Model and Notation (Модель и Нотация Бизнес Процессов) [1] - является стандартом де-факто для моделирования бизнес-процессов. BPMN-модели понятны широкой аудитории аналитиков и исследователей. К тому же BPMN-модели обладают рядом положительных особенностей: модели могут быть импортированы и выполнены в любой BPMN-ориентированной программной системе; модели подходят для интеграции с точки зрения различных перспектив (от перспективы потока управления до перспективы ресурсов). Таким образом, BPMN-модель позволяет получить целостный взгляд на исследуемый процесс и подходит для человеческого анализа.

С другой стороны, каузальные сети (causal nets, C-nets) - одна из основных моделей, рассматриваемая в рамках этой работы и широко используемая в системе PROM [5] - основаны на декларативной семантике, обеспечивающей только корректное поведение, то есть свободное от различных процессных аномалий: взаимных блокировок (deadlocks), ?зацикливаний? (livelocks) и других ошибок синхронизации.

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

3

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

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

4

1 Обзор используемых моделей

1.1 Сети Петри и WF-сети

В работе используются понятия сетей Петри и work?ow-сетей (WF-сетей) для оценки семантики каузальных сетей и BPMN-моделей.

Сеть Петри (Petri net) - это тройка PN = (P;T;F), где P и T - непересекающиеся множества позиций и переходов, образующие множество вершин, а F (P T) [ (T P) - множество потоков управления. Пусть E - конечное множество событий, - специальное скрытое событие, и : T ! E [ fg - функция пометки. Тогда PN = (P;T;F;)

- помеченная сеть Петри.

Маркировка сети Петри - это мультимножество над множеством позиций. Маркированная сеть Петри (PN;m0) - это сеть Петри со своей начальной маркировкой.

Графически позиции обычно представлены кружками, переходы - квадратами, а потоки из F - направленными дугами. Позиции могут содержать фишки (tokens), представленные закрашенными кружками. Текущая маркировка m обозначается количеством фишек m(p) в каждой позиции p 2 P.

Для любой вершины n 2 P [T дуга (x;n) называется входящей дугой, а дуга (n;x) - исходящей дугой; предусловие (preset) n и постусловие (postset) n определяются как мультимножества над P [ T, такие, что n(x) = 1, если (x;n) 2 F, иначе n(x) = 0, и n(x) = 1 если (n;x) 2 F, иначе n(x) = 0. Заметим, что предусловия и постусловия являются множеством вершин.

5

Переход t 2 T называется активным (enabled) в маркировке m тогда и только тогда, когда t m. Активный переход t может сработать (?re), производя новую маркировку m0 =def m t t (обозначается m ! m0, m ! m0, или m ! m0).

(t) t

Маркировка m0 называется достижимой (reachable) из m, если и только если существует (возможно, пустая) последовательность срабатываний m = m1 ! ! mn = m0.

R(PN;m) обозначает множество всех маркировок, достижимых в PN из маркировки m.

(Помеченная) Сеть Петри PN называется (помеченной) WF-сетью тогда и только тогда, когда: 1. Существует единственная начальная позиция (source place) i 2 P и единственная конечная позиция (sink place) o 2 P, причем i не имеет входящих дуг, а o - исходящих;

2. Каждая вершина из P [ T лежит на пути из i в o;

3. Начальная маркировка в PN содержит единственную фишку в i.

1.2 Каузальные сети

Модель каузальных сетей, представленная в [3], определяется следующим образом.

Каузальная сеть (Causal net, C-net) - это кортеж C = (A;ai;ao;D;I;O), где

A - множество действий;

ai, ao 2 A - начальное и конечное действия;

D A A - отношение зависимостей;

AS = FX P(A)1JX = f;g _ ; 2= Xg;

1P(A) = FA0 j A0 Ag - показательное множество A. Таким образом, элементы AS - множества множеств действий.

6

I 2 AS определяет множество возможных входных связей;

O 2 AS - множество возможных выходных связей, такие, что: D = f(a1;a2) 2 A Aja1 2 Sas2I(a2) as, a2 2 Sas2O(a1) asg;

faig = fa 2 AJI(a) = f;gg;

faog = fa 2 AJO(a) = f;gg;

все действия в графе (A;D) лежат на пути от ai до ao.

Таким образом, каузальная сеть состоит из множества действий, связанных между собой каузальными зависимостями. Каузальные зависимости основаны на понятии связи. Пусть имеется сеть C, тогда связью (activity binding) называется b 2 B = f(a;ASI;ASO) 2 A P(A) P(A)g. Последовательность связей 2 B - это упорядоченное множество связей. book flight register pay book hotel

Рис. 1.1: Каузальная сеть, моделирующая процесс бронирования

Рассмотрим C-net на рис. 1.1. Данная сеть моделирует процесс бронирования билетов на самолет и/или места в отеле. Сеть содержит действия регистрации (register), бронирования билета на самолет (book flight), места в отеле (book hotel) и оплаты (pay). Ребра графа отражают возможность следования одного действия за другим, а черные точки с дугами определяют множество входных и выходных связей действия. Например, действие register имеет 3 выходных связи: fbook flightg, fbook hotelg и

7

fbook flight;book hotelg, и ни одной входной, а действие book hotel имеет по одной входной и выходной связи.

Для последовательности связей каузальной сети определено понятие состояния. Состояние задается рекурсивно на множестве последовательностей связей: (hi) = []; ( (a;ASI;ASO)) = ( ()n(ASI fag)) ] (a ASO).2

Состояние в каузальной сети задает множество ?задолженностей? для каждой последовательности связей. ?Задолженность? является парой действий (a;b) и означает, что для корректного завершения процесса необходимо выполнение связи вида (b;asb;asb ), где a 2 asb.

I O I

В отличие от многих моделей процессов семантика каузальных сетей является декларативной а не операционной, то есть последовательности связей рассматриваются целиком, и не вводится понятие фишки, как, например, в сетях Петри. Более того, рассматриваемое поведение C-net ограничивается только корректными последовательностями связей.

I O I O

Последовательность связей = h(a1;as1;as1 );:::;(an;asn;asn )i для каузальной сети C является корректной, если выполняются следующие условия: a1 = ai, an = ao и ak 2 A ai;ao, 1 < k < n;

() = [];

для любого не пустого префикса 0 = h(a1;ASI;as1 );:::;(ak;ASI ;ASO)i, 1 k n следует, что (ASI ak) (00), где

O

1 k k k

00 = h(a1;ASI;ASO);:::;(ak 1;ASI 1;ask 1)i.

O

1 1 k

Множество корректных последовательностей связей сети C обозначается VCN(C).

Рассмотрим отношение между каузальными сетями и сетями Петри (WF-сетями в частности). Любая устойчивая WF-сеть может быть преобразована в эквивалентную3 C-net, однако не каждая каузальная сеть

2 - операция присоединения элемента (или упорядоченного множества) к концу упорядоченного множества. Например, fa;bg c = fa;b;cg. ] - операция объединения двух мультимножеств.

3Здесь имеется в виду трассовая эквивалентность.

8

может быть переведена в эквивалентную WF-сеть. Тем не менее может быть определено соответствие между каузальной сетью и WF-сетью, описанное в [3]. Пусть C = (A;ai;ai;D;I;O) - некоторая каузальная сеть, и NC = (P;T;F) - соответствующая work?ow-сеть. Тогда: P = FPI j a 2 Ag [ FPO j a 2 Ag [ fp(a1;a2) j (a1;a2) 2 Dg, D a a TI = FAI j a 2 A ^ X 2 I(a) ^ X = ;g, X

TO = FAO j a 2 A ^ X 2 O(a) ^ X = ;g, X

T = A [ TI [ TO, F = f(PI;a) j a 2 Ag [ f(a;PO) j a 2 Ag [ f(AI ;PI) j AI 2 a a a X X

TIG [ f(PO;AO ) j AO 2 TOG [ f(PD1;a);AI ) j AI 2 TI ^ a1 2 Xg [ f(AO ;p(a;a2)) j AO 2 TO ^ a2 2 Xg. a (a X X X X

D

X

X book flight

T1

P1 register pay

T2

P2

book hotel

Рис. 1.2: Work?ow-сеть, построенная из каузальной сети на рис. 1.1

1.3 Системы переходов

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

9

аппарата. Определим ( [2]) помеченную систему переходов (LTS) как тройку LTS = (P;Act;!), где P - множество, называемое доменом LTS, Act - множество действий и ! P Act P. P ! Q ) 9(P;a;Q) 2!. Q называется а-производной от P. a Переход P =) P0 называется слабым, если для n 0 существуют P1;:::;Pn, такие, что P0 = Pn и P ! P1::: ! Pn, где скрытое действие. Заметим, что если 2 Act, то P =) P0 , P =) P1 ! P2 =) P0.

Рассмотрим две системы переходов: LTSP и LTSQ. Бинарное отношение R является ветвящейся симуляцией тогда и только тогда, когда для любого P0, где P ! P0 либо

(a) = и P0 R Q или (b) существуют Q0;Q1;Q2, такие, что Q =) Q1 ! Q2 =) Q0, где P R Q1, P0 R Q2 и P0 R Q0;

Если LTSP R LTSQ, то LTSQ симулирует все последовательности переходов из LTSP .

1.4 BPMN

Нотация BPMN (Business Process Model and Notation, нотация и модель бизнес-процессов) является одним из самых популярных языков представления бизнес-процессов. BPMN имеет собственный стандарт, постоянно развиваемый и дополняемый. Стандарт имеет значительное число элементов, однако для целей данной работы будут использованы только некоторые из них.

Рассмотрим формальное определение BPMN-процесса. BPMN-процесс - это кортеж BPMNPROC = (N;S;A;GXOR;GAND;estart;eend), где N множество вершин, S N N - множество элементов потока управления. Множество вершин разделено на следующие не пересекающиеся подмножества: A - множество действий, GXOR, GAND - множества исключающих (XOR) и параллельных (AND) операторов (gates) и festartg и feendg - единичные множества, состоящие из начального и конечного события

10

book hotel register pay book flight

Рис. 1.3: Пример BPMN-модели процесса соответственно. Дадим определение согласованного (well-formed) BPMN-процесса. Рассмотрим вершину n 2 N, для которой вход (preset) n и выход (postset) n определяются как мультимножества над S, так что n(s) = 1, если s является входным элементом потока управления для n, в противном случае n(s) = 0, и n(s) = 1 если s - выходной поток управления для n, иначе n(s) = 0.

Согласованный BPMN-процесс

BPMNPROC = (N;S;A;GXOR;GAND;estart;eend) - это BPMN-процесс, который удовлетворяет следующие базовые аксиомы: 1. Начальное событие estart не имеет входящих потоков управления;

2. Конечное действие eend не имеет исходящих потоков управления;

3. Каждая вершина из N лежит на пути из estart в eend.

В отличие от сетей Петри, где фишки располагаются на позициях, маркировка BPMN-процесса является мультимножеством над множеством элементов потока управления, и обозначается как m : S ! N. Начальная маркировка - это такая маркировка, что m(s) = 1, если s исходящий поток управления из estart, m(s) = 0 иначе. Каждая вершина в BPMN-процессе может быть активированной (enabled). Рассмотрим правила срабатываний переходов в BPMN: 1. Действие a 2 A активируется в маркировке m тогда и только тогда, когда 9s 2 S : a(s) = 1 и m(s) 1. Другими словами, дей-

11

ствие a активируется в маркировке m если и только если существует хотя бы один входной поток управления, имеющий по крайней мере одну фишку. Выполняемое действие a может сработать, тем самым производя маркировку m0, такую что m0(s) = m(s) 1, и m0(s0) = m(s0) a(s0) для s0 2 S, причем s0 = s. Когда действие срабатывает, то поглощается по одной фишке на каждом входящем потоке управления, а на всех исходящих потоках управления появляется по одной новой фишке.

2. Исключающие операторы соединяют альтернативные пути: фишка на входящем потоке управления передается на один из исходящих потоков. Так же, как и действия, GXOR 2 GXOR активируются в маркировке m тогда и только тогда, когда 9s 2 S : GXOR(s) = 1, содержащий по крайней мере одну фишку в m: m(s) 1. Шлюз производит фишку только на один из исходящих потоков: новая маркировка m0(s) = m(s) 1 если s 2 S является одним из исходящих потоков управления, 8s0 2 S, таких что s0 = s, m0(s0) = m(s0).

3. Параллельный оператор GAND 2 GAND активируется в m тогда и только тогда, когда (GAND) m, т.е. каждый входящий поток управления имеет по крайней мере одну фишку. Выполняемый оператор GAND может сработать и произвести новую маркировку: m0, такую, что m0 = m GAND GAND, т.е. параллельный оператор поглощает фишку на каждом входящем потоке управления и производит фишку на каждом исходящем.

4. Стартовое событие никогда не срабатывает, так как оно не имеет входных элементов потока управления.

5. Конечное событие активируется, если в m 9s 2 S : eend(s) = 1; когда конечное действие срабатывает, то все фишки на входных элементах потока управления поглощаются, и производится новая маркировка m0 = m eend.

BPMN-процесс останавливает свое выполнение, если ни одна вершина не может сработать.

12

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

13

2 Построение BPMN-модели процесса по каузальной сети

2.1 Ограничения преобразования

Рассмотрим WF-сеть на рис. 1.2, построенную по trial. Заметим, что T1 = FP1g и T2 = FP1;P2g. По определению сети свободного выбора, сеть Петри является сетью свободного выбора тогда и только тогда, когда для любых двух переходов t1 и t2: t1 \ t2 = ; ) t1 = t2. Таким образом, рассматриваемая WF-сеть не является сетью свободного выбора.

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

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

14

2.2 Приведение C-net к LTS

Рассмотрим преобразование каузальной сети к LTS.

Определение 1 (Приведение C-net к LTS). Рассмотрим произвольную каузальную сеть C = (A;ai;ao;D;I;O), которая имеет определенное пространство состояний S. Тогда помеченная система переходов, построенная по данной сети, определяется как LTS = (P;Act;!), где P множество состояний каузальной сети, достижимых из начального состояния 0, Act множество действий каузальной сети, участвующих хотя бы в одной связи = (a;ASI;ASO), такой что O j

I i

(); ( ) 2 P. Переходы P ! P1 ! P2 ! P0 существуют в LTS тогда и только тогда, когда 9;s;s0; = (;MI;MO), такие что I 2 MI, O 2 MO, () = s; ( ) = s0 и является частью корректной последовательности в C. i j

Важно отметить, что если MI = ; или MO = ;, то P = P1 или P2 = P0 соответственно. b [(b,d)] d

[(a, b)] a b [(a, c), (b, d)] c

[] a [(a, b), (a, c)] [(b, d), (c, d)] d []

c [(a, b), (b, d)] b a [(a, c)] c [(c, d)] d

Рис. 2.1: Система переходов, построенная по каузальной сети на рис. 1.1

На рис. 2.1 представлена система переходов, моделирующая поведение каузальной сети на рис. 1.1. Домен системы состоит из конечного

15

пространства состояний исходной C-net. Несмотря на то, что начальное и конечное элементы домена LTS представляют одно и то же состояние каузальной сети, следует различать их, так как C-net не моделирует последовательности связи вида = 1:::n (n > 1), где i корректная последовательность связей.

Стоит отметить, что в случае неограниченной каузальной сети (unbounded C-net)1 домен системы переходов может быть бесконечным множеством. Метод построения из определения 1 гарантирует, что LTS содержит все корректные последовательности исходной каузальной сети.

2.3 Соответствие каузальной сети и BPMN-модели

2.3.1 Построение BPMN-модели по каузальной сети

Алгоритм 1 (Построение BPMN-процесса по каузальной сети). Вход: Каузальная сеть C = (AC;ai;ao;D;I;O).

Построим соответствующую BPMN-модель BPMN = (N;SF;ABPMN; GXOR;GAND;estart;eend) по следующим шагам: Шаг 1. Конвертация действий

(a) Для каждого AC 2 AC построим действие ABPMN и добавим его в ABPMN.

(b) Если AC = ai, то добавим начальное событие estart, соединенное с ABPMN исходящим потоком управления.

(c) Если AC = ao, то добавим конечное событие eend, соединенное входящим потоком управления с ABPMN.

Шаг 2: Конвертация входов и выходов.

Шаг 2.1: Конвертация выходов

1Каузальная сеть неограниченна, если она имеет бесконечное число состояний.

16

i. Для каждого действия AC 2 AC установим соответствующее действие ABPMN как текущую вершину

(NCUR := ABPMN). ii. Рассмотрим выходы действия AC: O(AC) = FO1;:::;Okg. Если JO(AC)j > 1, добавим в BPMN-модель исключающий оператор GXOR 2 GXOR, установим его как текущую вершину (NCUR := GXOR) и соединим входящим потоком управления с ABPMN. iii. Для каждой связи Oi;i 2 1::k if JOIJ > 1 добавим параллельный оператор GAND 2 GAND, соединим его входящим потоком управления с текущей вершиной, установим GAND как вершину связи (ni := GAND), иначе установим вершину связи как текущую вершину (ni := NCUR). i i i

Шаг 2.2: Конвертация входов i. Для каждого действия AC 2 AC установим соответствующее действие ABPMN как текущую вершину

(NCUR := ABPMN). ii. Рассмотрим входы действия AC: I(AC) = FI1;:::;Ikg. Если JI(AC)j > 1, добавим в BPMN-модель исключающий оператор GXOR 2 GXOR, установим его как текущую вершину (NCUR := GXOR) и соединим исходящим потоком управления с ABPMN. iii. Для каждой связи Ii;i 2 1::k if JIIJ > 1 добавим параллельный оператор GAND 2 GAND, соединим его исходящим потоком управления с текущей вершиной, установим GAND как вершину связи (ni := GAND), иначе установим вершину связи как текущую вершину (ni := NCUR). i i i

Шаг 3: Моделирование дуг.

Для каждой дуги d = (AC;AC) добавим в BPMN-модель исключающий оператор gd 2 GXOR, моделирующий дугу.

0

Шаг 4: Связывание входов и выходов.

17

(a) Для каждого действия AC рассмотрим его входы I(AC). Для каждого входа Ii и каждой дуги d = (AC;AC), где AC 2 Ii, поставим в соответствие вершину связи ni и соединим ее в BPMN-модели исходящим потоком управления с вершиной gd.

0 0

(b) Для каждого действия AC рассмотрим его выходы O(AC). Для каждого выхода Oi и каждой дуги d = (AC;AC), где AC 2 Oi, поставим в соответствие вершину связи ni и соединим ее в BPMN-модели входящим потоком управления с вершиной gd.

0 0

Выход: BPMN = (N;S;ABPMN;GXOR;GAND;estart;eend).

2.3.2 Пример построения

Каузальная сеть на рис. 1.1 соответствует BPMN-модели на рис. 2.2. Рассмотрим процесс построения более подробно. На первом шаге построения (на рис. 2.2 отмечено синим цветом) в BPMN-модель добавляются все действия из исходной каузальной сети и два события: начальное и конечное. События привязываются соответственно к начальному и конечному действию модели. В рассматриваемом примере такими действиями являются register и pay.

На втором шаге создаются операторы для моделирования входов и выходов каждого действия в каузальной сети (помечены зеленым цветом). Если у действия несколько входов/выходов, то добавляется оператор исключающего ?ИЛИ?, связанный потоком управления с рассматриваемым действием. Таким образом, после срабатывания любого действия поток управления может пойти лишь по одному из его выходов, что соответствует поведению каузальной сети. Если какой-либо вход/выход действия a исходной C-net содержит несколько действий, то для этого выхода создается оператор ?И?, связанный выходным/входным потоком управления либо с a, либо с оператором ?ИЛИ? (в случае, если a имеет несколько входов/выходов).

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

18

(register, book flight)

(book flight, pay)

{register} book flight {pay}

{book flight} {book flight}

register {book flight, book hotel}

{book flight, pay book hotel}

{book hotel} {book hotel}

{register} book hotel {pay} First step

(register, book hotel)

(book hotel, pay)

Second step

Third step

Fourth step

Рис. 2.2: BPMN-процесс, построенный по каузальной сети синхронизации выходов одного действия и входов связанного действия в BPMN-модели.

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

2.3.3 Приведение BPMN-модели к LTS

Для доказательства симуляции BPMN-моделью поведения каузальной сети в работе используются системы переходов как промежуточный язык. Приведение C-net к LTS было рассмотрено в подразделе 2.2. Рассмотрим свойства системы переходов, построенной по BPMN-модели.

Определение 2 (Приведение BPMN-модели к LTS). Рассмотрим произвольную BPMN-модель BPMN = (N;S;ABPMN;GXOR;GAND;estart; eend), имеющую определенное множество маркировок M = fm(s) j s 2 Sg. Тогда система переходов, построенная по BPMN-модели определяется как граф достижимости LTS = (P;A;!), где P = M и A =

19

ABPMN [ fg, причем переходы по соответствуют срабатываниям операторов g 2 GXOR [ GAND.

В корректности построения системы переходов можно легко убедиться. Так как домен LTS состоит из маркировок BPMN-модели, и переходы между маркировками обеспечиваются срабатыванием действий и операторов, то в LTS такие переходы моделируются переходами по действиям и слабыми переходами (в случае срабатывания операторов).

Лемма 1. Рассмотрим модель BPMN = (N;S;ABPMN;GXOR; GAND;estart;eend) и построенная по определению 2 система переходов LTS = (P;A;!). Пусть в BPMN существуют маркировка m, в которой активируется действие a, и маркировка m0, достижимая из m, в которой активируются действия B A, и не существует маркировка m00, такая, что m ! :::m00 ! :::m0, и в m00 активируются действия C A, причем C \ (B [ fag) = ;. Тогда в LTS для любого b 2 B существуют переходы P ! P1 =) P0. a b

Доказательство. Возможность активации действия a в маркировке m означает, что имеется маркировка m1, достижимая из m путем срабатывания a. Следовательно, LTS содержит переход P ! P1. a Отсутствие маркировки m00 в переходах от m к m0 говорит о том, что m0 достижима из m только путем срабатывания некоторого числа (возможно, нулевого) операторов. Но срабатывания операторов в LTS отображаются как скрытые переходы, следовательно, в LTS переход в маркировку m2 после срабатывания действия b может быть отображено как P1 =) P0. b b a Итого, LTS содержит переходы P ! P1 =) P0.

2.3.4 Корректность построения BPMN-модели по каузальной сети

Критерием корректного построения BPMN-модели по каузальной сети является симуляция построенной моделью всех корректных последовательностей связей исходной C-net.

20

Лемма 2. Пусть имеется каузальная сеть

C = (A; ai; ao; D; I; O) и построенная по ней BPMN-модель BPMNPROC = (N; S; A; GXOR; GAND; estart; eend). Тогда для любой связи = (a; Ii(a); Oj(a)) каузальной сети, где принадлежит некоторой корректной последовательности связей справедливо следующее: 1. При параллельном срабатывании в BPMN-модели всех действий из Ii(a), активируемых в маркировке m, существует такая маркировка m0, достижимая из m, при которой возможно срабатывание действия a.

2. При срабатывании действия a, активируемого в маркировке m, существует такая маркировка m0, достижимая из m, при которой возможно параллельное срабатывание всех действий из Oj(a).

Доказательство. Докажем первый пункт леммы. Рассмотрим некоторое действие b 2 Ii(a). Так как - корректная последовательность связей в C, то 9Ok(b) : a 2 Ok(b). Если b имеет несколько выходов, то после срабатывания его в BPMN-модели в маркировке m, новая маркировка m1 будет содержать фишку на входящем потоке управления в ис- b ключающий оператор GXORO . Если Ok(b) содержит несколько действий, то m2(s) = 1, где GANDO (s) = 1. Так как оператор GANDO является разветвляющим, то 9s 2 S;m3 такие, что g(b;a) (s) = 1 и m3(s) = 1. За- b b k k

XOR метим, что при любой конфигурации выходов действия b маркировка m3, активирующая исключающий оператор, моделирующий дугу (b;a) каузальной сети, достижима из маркировки m.

Подобный принцип можно применить и для входов действия a. Так как для любого действия b 2 Ii(a) существует маркировка ml, активирующая оператор g(b;a) , связанный одним или несколькими потоками

XOR управления с соответствующими входами действия a, то существует маркировка m0 такая, что m0(s) = 1, где a(s) = 1.

Второй пункт леммы доказывается аналогично первому. Заметим, что в случае, когда множество входов или выходов действия a является пустым (т.е. a - начальное или конечное действие), то в одном из пунктов m = m0.

21

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

Теорема 1 (Симуляция BPMN-моделью каузальной сети). Пусть имеется некоторая каузальная сеть C = (A;ai;ao;D;I;O) и BPMN-модель BPMN = (N;S;A;GXOR;GAND;estart;eend), построенная по каузальной сети с помощью алгоритма 1. Тогда C BPMN, где - отношение симуляции.

Доказательство. Рассмотрим множество корректных последовательностей связей VCN каузальной сети C. Если VCN = ;, то теорема верна.

Рассмотрим случай, когда VCN имеет один или более элементов. Для доказательства симуляции будем использовать две системы переходов: LTSC = (P;A;!), построенную по C, и LTSBPMN = (Q;A [ fg;!), полученную из BPMN. Рассмотрим произвольную последовательность связей 2 VCN.

База индукции. trialem 0 = (ai;;;ASO) 2 . По определению 1 LTSC

O as j a i содержит переходы P ! P0 ! P00 для любого действия из ASO. Из

O as j a i лемм 2 и 1 следует, что в LTSBPMN существуют переходы Q ! Q0 =) Q00 для любого действия из ASO. Таким образом, P R Q, P0 R Q0 и P00 R Q00, где R отношение симуляции.

Шаг индукции. Пусть i 2 симулируется BPMN-моделью. Рассмотрим i 1 = (a;ASI;ASO). По определению 1 LTSC содержит переходы

O a j as

I i a P ! P0 ! P00 ! P000 для любых действий из ASI и ASO. В LTSBPMN

O as j as

I i a присутствуют переходы Q =) Q0 ! Q00 =) Q000 для любых действий из ASI и ASO. Таким образом, P0 R Q0, P00 R Q00 и P000 R Q000.

Итого, рассмотрев все корректные последовательности связей подобным образом, получаем, что для любого P0, такого что P ! P0, суще- a

22

ствуют Q;Q1;Q2;Q0, такие, что Q =) Q1 ! Q2 =) Q0. Таким образом, BPMN-модель симулирует поведение каузальной сети. a Вследствие концептуальных отличий операционной семантики от декларативной обратная симуляция не может быть доказана. Если в исходной каузальной сети имеются связи, не участвующие ни в одной корректной последовательности связей, но присутствующие в итоговой BPMN-модели, то срабатывание действий этих связей с большой вероятностью приведет к ошибкам синхронизации.

Ошибки синхронизации могут возникать и в BPMN-модели, построенной по устойчивой каузальной сети. Например, если в модели на рис. 2.2 срабатывают действия register и book flight, но не срабатывает действие book hotel, после срабатывания исключающего оператора (book flight;pay) может стать активный параллельный оператор входа к действию pay.

23

3 Анализ результатов

3.1 Оценка сложности алгоритма преобразования

Оценим сложность алгоритма конвертации каузальной сети в BPMN-модель. Пусть в C-net имеется n действий, а общее количество входов и выходов на все действия m.

На первом шаге алгоритма происходит прямая конвертация действий каузальной сети в действия BPMN-модели, поэтому сложность первого шага O(n). На втором шаге все входы и выходы моделируются не более двумя операторами и не более двумя потоками управления, поэтому справедливо считать сложность второго шага как O(m).

Третий шаг алгоритма для каждой дуги создает исключающий оператор в BPMN-модели. Так как число дуг заведомо меньше числа связей (на одну дугу в каузальной сети приходится по крайней мере две связи: выход одного действия и вход другого), то трудоемкость этого шага заведомо меньше, чем O(m).

Четвертый шаг для каждого входа, выхода и дуги, участвующей в данном входе или выходе добавляет поток управления. Таким образом, сложность четвертого шага равна O(m).

Итого, сложность алгоритма может быть оценена как O(n m).

24

3.2 Плагин BPMNCONVERSIONS для PROM

Алгоритм преобразования каузальной сети в BPMN-модель был реализован в процессно-ориентированной информационной системе PROM в рамках плагина (plug-in) BPMNCONVERSIONS. Основная задача плагина конвертация различных моделей (в том числе и каузальных сетей) в BPMN-модели.

В рамках плагина реализовано также исправление каузальной сети. Так как процесс может иметь несколько начальных или конечных действий, то результат работы ?майнера? (программы, извлекающей модель процесса из лога) может представлять собой каузальную сеть с несколькими начальными или конечными действиями соответственно, что противоречит семантике C-net. В этом случае плагин непосредственно перед конвертацией добавляет единое начальное (common start) или конечное действие (common end) и связывает его со всеми начальными или конечными действиями соответственно.

Следует отдельно отметить случай, когда действие a в логе появляется в качестве как начального, так и конечного действия, но в разных последовательностях действий. Тогда в исправленной модели каузальной сети будет существовать корректная последовательность действий hstart;a;endi, которая может быть не отражена в логе.

Рассмотрим пример результатов работы алгоритма в рамках BPMNCONVERSIONS. На рис. 3.1 представлена некоторая каузальная сеть, полученная из лога, которую необходимо конвертировать в BPMN-модель. Зеленым цветом помечены начальные действия, красным цветом конечные. Заметим, что в визуализации модели отсутствуют черные точки, обозначающие связи. Эти связи можно посмотреть при наведении курсора мыши на действие.

На рис. 3.2 показан результат конвертации. Заметим, что в модели появились действия start и end, которые добавились в результате исправления каузальной сети.

Техническое задание на реализацию алгоритма конвертации приведено в Приложении А. Код алгоритма приведен в Приложении Б.

25

Рис. 3.1: Пример каузальной сети, извлеченной из лога процесса

Рис. 3.2: Пример BPMN-модели, построенной по каузальной сети на рис.3.1

26

В рамках работы была решена актуальная задача преобразования каузальной сети в BPMN-модель. Каузальные сети используются в рамках дисциплины Process Mining как результат извлечение модели процесса из лога этого процесса, так как семантика C-net не рассматривает последовательности действий с ошибками синхронизации. Однако представление модели процесса в виде каузальной сети может быть не очевидным для исследователей и аналитиков вследствие новизны нотации и сложности семантики.

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

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

Алгоритм был реализован в рамках плагина BPMNCONVERSIONS в системе PROM.

27

[1] OMG. Business Process Model and Notation (BPMN). Object Management Group, formal/2011-01-03, 2011.

[2] Davide Sangiorgi. Introduction to Bisimulation and Coinduction. Cambridge University Press.

[3] Wil Van Der Aalst, Arya Adriansyah, and Boudewijn Van Dongen. Causal nets: A modeling language tailored towards process discovery. In Proceedings of the 22Nd International Conference on Concurrency Theory, CONCUR’11, pages 28-42, Berlin, Heidelberg, 2011. Springer-Verlag.

[4] Wil M. P. van der Aalst. Process Mining - Discovery, Conformance and Enhancement of Business Processes. Springer, 2011.

[5] H.M.W. Verbeek, J.C.A.M. Buijs, B.F. van Dongen, and W.M.P. van der Aalst. PROM 6: The Process Mining Toolkit. In Proc. of BPM Demonstration Track 2010, volume 615 of CEUR Workshop Proceedings, pages 34-39, 2010.

28