Как стать автором
Обновить

WF2M сеть. Формализм и математика workflow

Уровень сложностиПростой
Время на прочтение24 мин
Количество просмотров2.3K

Кому нужны книжки без картинок … или хоть стишков, не понимаю! – думала Алиса

Кому нужны регламенты бизнес-процессов без схемок … или хоть скриптов, не понимаю! –осенило бизнес-аналитика Алису

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

Существует широкий спектр workflow нотаций (стандартов): от классических ГОСТ 19.701-90 (ИСО 5807-85, flowchart), IDEF3, UML2-AD и XML-сериализованных BPMN\YAWL\XPDL\EPML до специфических, например, Дракон.

Ведутся споры «насколько хороша» та или иная нотация: насколько интуитивно понятно передает она в графическом представлении модели (в картинке) суть процесса (упрощенная нотация, понятная рядовому бизнес-пользователю), но не встречал обсуждения их математических представлений и вообще workflow-модели с простой и прозрачной математической абстракцией: математической интерпретацией объектов модели и механики процесса (метамодели алгоритма).

Ниже предложен математический формализм workflow-сетей: Модель WF2M (From workflow to mathematic), WF2M-сеть, как механизм формализации алгоритмов бизнес-процессов в части потока работ (workflow) путем задания аналитическими выражениями функций переходов между дискретными состояниями, маркировки состояний моделируемого объекта. Механизм (механика интерпретации алгоритма бизнес-процесса) заимствует от сетей Петри терминологию (маркировка сети, активация перехода, реализация перехода и т.п.) и частично концептуализм и классификацию. Предложенная WF2M сеть имеет иной механизм формализации (абстракцию) по сравнению с WF-nets.

Если переходы WF-nets назначаются задачам или действиям, а места назначаются предварительным / пост-условиям, то в WF2M сети задачи – это места.


1 Базовые положения на примере

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

На рис. 1 показан пример алгоритма и его представление в виде графа состояний и переходов, матрицы смежности, скрипта dot. Элемент pN – «операция» (узел, вершина графа = шаг процесса, действие), переход из одного шага к другому обозначен в виде дуги (ребро графа). 

Жаль, что нельзя загружать svg.  

Рис. 1 Граф алгоритма и его матричное, аналитическое и языковое представление
Рис. 1 Граф алгоритма и его матричное, аналитическое и языковое представление

Таблица переходов определяет возможность перехода из одного узла ориентированного графа в другой. В таблице кроме «1» может быть указана ссылка на условие, необходимое для осуществления перехода. Для упрощения, будем считать такую «таблицу достижимости по условию», таблицу переходов синонимом классической «матрице смежности». Таким образом, Матрица смежности строится на основе приведенных выражений для переходов, указатель s говорит, что есть соответствующее выражение для проверки условия, см. «Условия (s)». На рис. 1с показан скрипт на языке dot, автоматически генерирующий схему графа.

Сокращенный варианта графа (по ссылке будет показан сгенерированный по скрипту граф) и полный вариант в online Graphviz Visual Editor

Рис. Сокращенный вариант
Рис. Сокращенный вариант

Однако графовое представление недостаточно «красноречиво», поэтому применяются специальные графические нотации. На рис. 2 приведен пример алгоритма в нотациях ЕРС (EPC-диаграмма, event-driven process chain) и WF2M.  

Рис. 2 Алгоритм в нотации ЕРС и WF2M
Рис. 2 Алгоритм в нотации ЕРС и WF2M

Отличие WF2M нотации от ЕРС в части отображения логики workflow: отсутствие логических операторов И, ИЛИ, а также запись условий не в выделенном элементе (шестиугольник), а в подписи к дуге. Элемент «операция» (EPC: «function») в обоих нотациях совпадает.  

В базовом варианте WF2M не различает ИЛИ (OR)/ исключающее ИЛИ (XOR), в терминах BPMN: разделяющие Неэксклюзивный Шлюз и Эксклюзивный Шлюз. В зависимости от содержания условий, указанных в s, может быть организована логика OR / XOR, формально заданная содержанием условий. При этом указание на OR / XOR можно добавить в подпись дуги на графе, но исключительно как подсказка, визуализированная на схеме процесса, т.е. без обработки внутри модели. Считается, что разработчик алгоритма через формулирование условий (s) сам задает логику OR / XOR.

При необходимости «отработки» моделью исключительности веток XOR, в низкоуровневом представлении модели WF2M «исключающее ИЛИ» может быть формализовано (и кодировано) алгоритмом моделирования полной группы несовместных событий [MG16]. Однако основное внимание в статье уделяется «нормальному» представлению модели.

Отрытый Вопрос по визуализации схем процессов. Каким инструментом можно по скрипту (не обязательно на языке dot) генерировать диаграммы ЕРС или WF2M, подобные приведенным на рис. 2б и c?

Одной из требуемых технических особенностей – это необходимость задания на фигуре (shape) точек соединения (connection point), т.к. необходимо разнесение всех входящих и всех исходящих линий (стрелок). Например, в graphviz «некрасиво» строится (смотрится) граф (в twopi немного лучше, но все равно не так как нужно):

digraph G {
    p1 -> p2
    p2 -> p3
    p3 -> p2 [label=no]
    p3 -> p4 [label=yes]
    p4 -> p5
}

Все дуги, «входящие в узел», должны быть присоединены к «connection point» типа «Входящие», а все дуги, исходящие из узла, - присоединены к «connection point» типа «Исходящие». Dot \ graphviz похоже так умеет (см. комментарии).

Также требуется перенос слов в названии элемента, см. приведенные примеры «неуклюжих» схем, построенных по dot. Желательно уметь позиционировать подпись к фигуре, например, снизу под фигурой, как например, подпись к элементу cluster (dot): т.е. dot подпись к листу и кластеру умеет позиционировать, а подпись к фигуре (не надпись в фигуре) наносит в произвольное место.

Кроме инструментов «из мира» графов (gephi, cytoscape), векторной графики (drawio, visio) и CASE (plantuml, Visio Data Visualizer), хотелось бы найти Linked Data инструменты с поддержкой графической нотации. Не обязательно workflow – EPC или BPMN, хотя бы структурных схем, но с разным типом объектов, например, в аналоге Protege иметь возможность задавать отображаемый графический примитив в зависимости от типа объекта.

2 Аналогии с сетями Петри и диаграммами ЕРС

Для ассоциации с сетями Петри можно трактовать: места – это операции (действия, шаги процесса), а переходы – это дуги (не путать с абстракциями в «низкоуровневом представлении» модели, рассмотренной в разделе 4). Преобразование на две ветви «разветвителя по условию», используемого в блок-схемах (flowchart), аналогично сетям Петри [Pete84] и ЕРС, см. рис. 3.

Рис. 3 Преобразование условного разветвителя в блок-схемах в раздельные ветви через фильтры с условием
Рис. 3 Преобразование условного разветвителя в блок-схемах в раздельные ветви через фильтры с условием

При ассоциации EPC с WF2M с можно считать, что шестиугольник – это подпись дуг соответствующего перехода в WF2M (подпись перехода в виде элемента «шестиугольник»), а условные операторы опущены. 

Возможная интерпретация дуги «s-переход» (фильтр) в WF2M приведена на рис. 4.

Рис. 4 Интерпретация перехода в WF2M
Рис. 4 Интерпретация перехода в WF2M

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

3 Алгоритм обработки workflow на примере Excel представления

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

Если требуется вычислить следующий шаг алгоритма, например, следующий после p1: смотрим строку p1. Если в строке указана «1», то переход «безусловный», т.е. константа «s = 1», на схеме значение «1» в подписи дуги можно не указывать. Если в строке указаны «s», то определяем при каких условиях, такой шаг будет выполнен. Считается, что после выполнения шага условие (s), определяющее следующий переход, должно быть вычисляемое, т.е. имеются все необходимые исходные данные для подстановки в условие s для проверки его истинности. Номер следующего шага, как условного, так и безусловного, определяет номер столбца на пересечении с непустой ячейкой по строке р1.  

Excel

Рассмотрим формализацию алгоритма в Excel, как наиболее наглядный вариант представления объектов (переменных) МетаМодели. Ровно тоже самое кодируется массивами (переменными) или таблицами СУБД.

Предусматриваются следующие таблицы (листы):

- «model» - матрица смежности,

- «s» (stipulation) – наименования условий условных переходов s(I,j)

- «action» - текущая маркировка сети и технологические состояния синхронизаторов

- «label» - наименования узлов (операций). При необходимости лист можно дополнить полем «тип», например, для пояснения, что данный узел является синхронизатором потоков.

В таблице «model» - номера строк и полей являются индексами узлов (задают ID узла: pi, pj).  

В таблице «s» - номера строк и полей задают единый индекс перехода (задают ID перехода: s(i,j).  

На листе «label» указаны все названия шагов. Нумерация индекса в p1, p2 … pN совпадает с нумерацией строк в Excel.

В необязательный лист «log» (журнал) может записываться история прохождения маркера по схеме процесса (история реализованных шагов процесса). В привязке к шагу в журнале может фиксироваться фактическое время выполнение операции (шага), например, в единицах времени или в интервалах дискретизации.

На рис. 5 показана Excel-таблица (лист «model») с таблицей переходов согласно рис. 1. Переключение на стиль R1C1: Файл \ Параметры \ Формулы.

Рис. 5 Матрица смежности \ Таблица переходов в Excel (лист «model»)
Рис. 5 Матрица смежности \ Таблица переходов в Excel (лист «model»)

Для расчета следующего за p1 шага нужно просмотреть все столбцы по строке 1:  

- если на пересечении будет «1», то за p1 «безусловно» следует, указанный в столбце элемент (может быть несколько),

- если на пересечении будет «s», то нужно вычислить соответствующий s(i,j) и подставить полученное значение в ячейку (значение 1 или 0). Если значение s(i,j)=1 (true), то переход выполняется, если «0» (false), что равнозначно пустой ячейке в таблице переходов, то переход не выполняется.

На основе данных из указанных листов, включая «label» для получения именованных узлов вместо их ID, формируется скрипт (dot или подобный) и далее подставляется в генератор схемы бизнес-процесса. Для генерации как самого dot-скрипта, так и по нему схемы процесса (в любой нотации) можно использовать Excel-образный визуализатор dot: Excel to Graphviz

Формирование таблицы переходов можно на основе таблицы последовательности шагов. Пользователь заполняет таблицу с полями: номер шага; имя шага; номер следующего шага, а при наличии условия (s), заполняется поле «формализация условия». По такой таблице автоматически строится матрица смежности (таблица переходов) или скрипт алгоритма. Получается подобие ARIS Smart Design.

4 Синхронизаторы join

Для реализации параллельных операций (шагов процесса) требуется оператор синхронизации – синхронный join (объединитель параллельных ветвей). Заданный ветвями виртуальный в WF2M оператор split проводит расщепление параллельных потоков путем разветвления потоков из одного элемента p и в общем случае (есть исключения, например, OR-join) не требует специального формализма, т.к. он неявно (несколько непустых позиций в одной строке) определен в таблице переходов.

Синхронный оператор join требует явного определения в таблице переходов, иначе будет не задано условие, что переход на следующий шаг осуществляется после прихода маркеров из всех параллельных ветвей, см. рис. 6. Классическим примером синхронного join является AND-join (объединитель «И»).

Условием перехода в таблице переходов является наличие «1», т.е. «true» (в том числе, полученное в результате вычисления условия s для «условных переходов»).  

Рис. 6 Пример AND-join
Рис. 6 Пример AND-join

Для фиксации текущего состояния требуется ведение отдельного реестра (списка или таблицы).  Если на листе «model» (рис. 6) закодирована модель алгоритма, то на листе «action» отражается текущая маркировка, например, p1=1 на листе «action» будет обозначать текущую позицию с активным маркером (маркировка сети, положение маркера) вида {1,0,0,0,0}. Пример листа «action» для модели рис. 6 с маркировками сети (p1,p2,p3,p4): {0,1,1,1,0}, {0,0,1,1,0}, {0,0,0,0,1} приведены на рис. 7.

Для вычисления срабатывания оператора AND-join информации только о текущей разметки сети недостаточно. Некоторые маркеры могли уже покинуть одно из параллельных состояний и для вычисления условия «И» (реализации синхронизатора) требуется об этом информация.

Для этого в модель вводится дробное значение «веса» параллельной ветви – как технологический прием реализации синхронизатора. При завершении шага p2 происходит удаление из p2 маркера и передача маркера в ветвь, ведущую в p5 (рис. 7б). Так как ветвь имеет идентификатор «&» (в общем случае, нумерованный), то выполняется специальная обработка ветви (дуги).

Рис. 7 Маркировка сети при обработке AND-join («лист action»)
Рис. 7 Маркировка сети при обработке AND-join («лист action»)

Первая строка листа «action» содержит текущую маркировку (пустая ячейка эквивалентна значению «0»). Вторая и третья кодирует состояние синхронизатора перехода: в столбце p5 строкой «2» кодируются полученные, но не реализованные маркеры, а строкой «3» общее число входящих в синхронизатор дуг в состоянии «взведено».

Изначально в строке «3» установлены нули (пустая ячейка). При каждой попытке передать маркер в узел p5, т.е. при попытке перехода происходит проверка условия: равно ли нулю в третьей строке значение. Если равно, то в ней устанавливается значение, равное числу входящих дуг (взведение всех входящих дуг). Далее производится увеличение счетчика в строке «2» и деление на число входящих (взведенных) дуг. Если полученное при делении число менее «1», то маркер удаляется (переход не реализовывается), если число равно «1» (условие перехода в синхронизатор, по аналогии с условным переходом в дуге), то маркер передается в позицию (узел) p5, а счетчик строк «2» и «3» обнуляется, т.е. счетчики всех реализованных и взведенных дуг сбрасываются (синхронизатор переходит в исходное состояние).   

Сокращенно для AND-join: если маркер перешел в дугу типа «дуга в синхронизатор» (обозначение «&», т.е. дуга, ведущая в узел-синхронизатор), то увеличиваем счетчик синхронизатора. Проверим значение счётчика синхронизатора: если число менее суммарного числа всех дуг, входящих в узел-синхронизатор, то сброс маркера, иначе передача маркера в узел-синхронизатор и сброс счётчика синхронизатора.

Можно провести следующую аналогию механизма синхронизатора WF2M с сетью Петри. Можно считать, что есть два уровня представления модели WF2M: нормальное и низкоуровневое представление (НУП). Всё, что рассказано без уточнения – это нормальный (основной) уровень модели. Поведение маркера в обоих представлениях моделях разное (вообще разные концепты моделей). Для реализации синхронизатора может быть применена НУП сети Петри (СП), т.к. в эти сети «встроен» закон распределения между двумя операциями с отражением принципа параллелизма. СП-маркер в таком представлении (НУП) будет находиться в состоянии, например, «p2 выполнено» и «дожидаться» выполнения остальных ветвей. При получении СП-маркера от каждой параллельной ветви сработает переход штатным для обычных сетей Петри образом. Такая двухуровневая модель позволяет использовать разные абстракции (дуализм) в рамках одной модели.

Анимацию работы синхронизатора AND-join см. Workflow Pattern WCP3: Synchronization

Описание WCP3

OR-join. Оператор «синхронный OR-join» работает аналогично, т.е. технически в WF2M: «OR-join» = «AND-join». Однако, при реализации пары OR-split / OR-join не все ветви могут быть выполнены и синхронизатор (join) должен знать, какое количество дуг должно быть синхронизировано, т.е. знать значение в строке «3» листа «action». Для этого выше использовалось уточнение «взведенных» дуг и проверка на 0. В случае AND-join все дуги взводятся первым прошедшим к AND-join маркером до общего числа ветвей AND-join, в случае синхронного OR-join взведение дуги осуществляет соответствующий OR-split. Таким образом, предложен концепт универсального синхронизатора «OR-join» = «AND-join» для работы которого требуется учет взведенных дуг (для «AND-join» все дуги, входящие в синхронизатор взведенные «по умолчанию») и реализованных дуг (маркер вышел из синхронизируемой дуги).

Информацию о том, нужно ли синхронизировать дугу в OR-join или нет можно получить только при анализе реализации фильтра «OR-split» - расщепителя потоков, которые потенциально могут стать ветвями, требующими синхронизации. Поэтому при пересечении этого фильтра («V(») маркером, для поддержки элемента абстракции «универсальный синхронизатор» (его алгоритм един для объединения AND и синхронного OR), модель вынуждена вычислять значения системных переменных:

- счетчик числа проходов (реализаций, входящих в синхронизатор дуг) и

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

При наличии в схеме OR-join (синхронизатора) помечаются соответствующие ему ветви OR-split (OR-split взводный). При прохождении маркера через OR-split производится взведение новой дуги, требующей последующей синхронизации, путем увеличения счетчика в строке «3» листа «action». Если дуги будут не помечены, то алгоритм будет исполнен не корректно.

Для обозначения OR-split на схеме и в таблице могут быть использованы обозначения «OR» или «OR-split» или «V(» («входящая скобка условия OR») с указанием узла синхронизации (имени OR-join), например, «V(-p5». Указание узла синхронизации явно указывает в какой счетчик добавлять значения при реализации перехода в ветви парном OR-split.

Следует учитывать, что при ветвлении алгоритма посредством операторов «OR» в общем случае, часть исходящих веток может требовать синхронизации (общий «V)» - «закрывающая скобка условия OR»), а часть нет (в большинстве случаев операторы парные). В то же время в один узел синхронизации может входить несколько групп параллельных ветвлений, что требует введение идентификатора для каждой группы («V(-p5-1») и ведение счётчика для каждой группы.

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

Вопросы по инклюзивному шлюзу (OR-split / OR-join) в BPMN указаны в PS1.

5 Типы соединителей - переходов и состояния модели

Предусмотрены следующие типы дуг (переходов) по особенностям их обработки (в базовой версии WF2M):

Группа «пользовательские условия» (условия, заданные бизнес-пользователем ):
- безусловный переход (s=1);
- условный переход (s);

Группа «технологические условия» (tech-условия):
- синхронизатор join (&);
- OR-split взводный («взводитель»), который взводит связанную с ней дугу для вычисления соответствующего ей значения счетчика OR-join (см. предыдущий раздел).

Нумерация дуг. Если шаг процесса (состояние, узел) имеет собственный номер (p1, p2, … pN), то для идентификации дуги достаточно указания пары номеров, определяющих исходный (начало направленной дуги) и конечный узел, например, s(I, j) – переход (соединитель) от узла pi к pj.

Предполагается, что маркер в дуге проходит через три мгновенных (t=0) состояния:

- маркер на входе в дугу: происходит активация перехода;

- маркер в середине дуги: вычисление условия в переходе (пользовательского или технологического, включая изменение значения технологических счетчиков синхронизаторов);

- маркер на выходе из дуги: происходит реализация перехода и маркер передается в следующий блок (операцию).

Если вычисленное условие в переходе не равно «1», то маркер удаляется (переход не реализован), иначе (т.е. «=true») маркер пропускается на выход дуги (переход реализован).

Также предусматривается три положения маркера в блоке «Операция» (узел, вершина): на входе в блок (старт операции), в середине (исполнение операции) и на выходе из блока (операция завершена). Начальное и финальное состояние предполагают специальную обработку, для остальных блоков предполагается, что вошедший в блок маркер сможет покинуть блок после завершения времени обработки операции (передача эстафетной палочки).

Из перечисленных шести состояний только состояние «исполнение операции» имеет время более 0, остальные мгновенные.

Алгоритм расчета маркировки сети

Граф переходов и внутренние состояния модели при отработке шага дискретизации модели показаны на рис. 8.

Рис. 8 Граф переходов и внутренние состояния модели
Рис. 8 Граф переходов и внутренние состояния модели

А) «Операция завершена»: маркер находился в узле pi и в момент шага дискретизации «вышел» из узла (pi), т.е. операция была выполнена на текущем шаге и модель приняла это событие «в работу».

В момент перехода (пересечение границы узла, т.е. подразумевается не «СП-переход») генерируется внутреннее (системное) событие «stop», по которому модель рассчитывает следующий шаг (переход от текущей маркировки сети).

Б) В таблице переходов определяется первый претендент: перебираются все ненулевые ячейки в строке pi листа «model» (таблица переходов). Например, в таблице на пересечении строки pi и столбца pj установлен «s». Если вместо «s» указан специальный символ, например, «&» то происходит его обработка (работа синхронизатора по рассмотренному ранее алгоритму).

В результате анализа таблицы переходов активируется соответствующая дуга s(i,j), далее происходит вычисление условия s(i,j).

Согласно рис. 4:

- если s(i,j) = false, то маркер удаляется и переход не реализовывается;

- если s(i,j) = true, то маркер передается в узел pj и генерируется внутреннее (системное) событие «start».   

В) Далее проводится поиск следующего узла в таблице переходов (в рамках этого же шага дискретизации), т.е. происходит «размножение маркеров», при отсутствии следующего «ненулевого значения» в таблице переходов – фиксируется завершение обработки шага дискретизации (шага модели).

Г) При обработке системного события «start» (sys start) включается фиксатор времени выполнения операции и фиксируется текущая маркировка сети (запись «единички» в первую строку листа «action»). При завершении операции (время, вычисленное по формуле в системе имитационного моделирования или по получению соответствующего сигнала в реальном процессе) генерируется внутреннее событие «stop», фиксируется время выполнения операции и далее рассчитывается следующий шаг алгоритма (расчет новой маркировки сети).

Рис. 8 зеленым цветом выделяет сегмент обработки (вычислений) «в узле», а красным - сегмент вычислений «в дуге» (дуга с вычислителем). Ключевыми системными событиями являются «start» и «stop», т.к. передают «эстафетную палочку» (маркер) в смежный сегмент.

6 Расширения модели WF2M

В базовой модели рассмотрены только два синхронизатора. В общем случае, реализация объединителей потоков может быть разнообразной и требует специальной конфигурации алгоритма в составе расширенной WF2M. Например, объединитель типа «Пропускать только первого» предполагает пропуск из параллельных веток только первого маркера (остальные удаляются), при этом работает приведенный для AND-join механизм, но пропускается не последний, а первый маркер, прошедший одну из параллельных веток (технологический счетчик сбрасывается по тому же принципу ,т.е. когда был пройден последний маркер). При этом будет добавлен еще один тип дуги (см. раздел 5 Типы соединителей - переходов и состояния модели), например, «first-joint». 

WF2Me (WF2M.event)

В WF2M используются «дуги с вычислением» условий. Другим расширением модели WF2M может служить выделение таких дуг в отдельный графический элемент, например, переход (в аналогии с сетью Петри). Таким образом получим двудольный граф (биграф), узлы которого соединены уже «простыми» соединителями (дугами). Такое представление будет иметь преимущество перед базовой моделью WF2M в том, что если после выполнения условия (s) требуется выполнение сразу нескольких операций, то не нужно дублировать дуги с одноименным условием s (стрелка подразумевает одно начало и один конец).

Добавление нового типа узла графа - перехода, отражающего проверку условия или свершение события, - потребует нанесение на схему и добавление в матрицу переходов дополнительных элементов. Примером может служить классическая ЕРС-диаграмма с элементом типа «событие» («event», шестиугольник) после каждого элемента типа «операция» (function), например, «Выполнение операции Ы» -> «Операция Ы выполнена». Введение подобных элементов иногда загромождает схему и усложняет представление математической модели (увеличивает число аналитических выражений, более сложная таблица переходов).      

WF2Me по сравнению с базовой моделью имеет больше сходств с сетями Петри и ЕРС. Если в ЕРС исключить логические операторы И-ИЛИ (XOR), а функции (function) моделировать метами, события (event) моделировать переходами, то получится WF2Me (с учетом задания логики работы синхронизаторов). Частично схожий маппинг элементов workflow в сети Петри показан в [Kopp03] и [MMP15], однако WF-nets исползают иной маппинг, см. [Aal98fwm] и [Aal98epc]: «event to place \ function to transition».

Если в WF2M применена «дуга с вычислителем» (вычисления и проверки условия проводятся «в дуге»), то в WF2Mе вычисления условий вынесены в отдельный компонент (что делает граф двудольным), а сама дуга тогда будет «дуга без вычислителя» (простой соединитель без права принимать решения).

Пример алгоритма в нотации WF2Me показан на рис. 9 с учетом того, что безусловные дуги показаны без элемента «event», т.е. «безусловные» - без элемента «Условие» («Событие»).

Несколько экземпляров процесса. Другим расширением сети может служить обработка нескольких экземпляров процесса (в базовой – один экземпляр). Для этого может быть использован подход, аналогичный цветным сетям Петри (CPN), с учетом, что каждому цвету соответствует отдельный экземпляр процесса. При этом можно учитывать конкуренцию за ресурс: когда в одном узле одновременно находятся несколько маркеров разного цвета и требуется обеспечить вычисление времени выполнения операции (функции) с учетом ограниченности ресурса (исполнителя операции).

7 Метамодель WF2M

Алгоритм чтения алгоритмов бизнес-процессов представлен на рис. 9.

Рис. 9 Алгоритм Метамодели в нотации WF2Me
Рис. 9 Алгоритм Метамодели в нотации WF2Me

Для вычисления очередного шага алгоритма для Метамодели WF2M необходимо два внешних вычисления (входные данные):

- функция вычисления завершения каждой операции (функция распределения или проверка на наличие внешнего сигнала о завершении операции);

- функция вычисления истинности условия (s) в каждой ветви.  

Для иллюстрации работы метамодели введем следующие правила имитатора:

- функция вычисления завершения каждой операции численно равна 1 (единичному шагу дискретизации);

- функция вычисления истинности условия (s) в каждой ветви численно равна чередованию «нет» \ «да», т.е. {0,1,0,1,0,1 …}. Условно: лицо принятия решения (р3) не подкидывает монетку для определения решения (орел\ решка), а каждый раз ее переворачивает.

Функция вычисления истинности условия (s) в рамках базовой WF2M сети выражена как некий параметр (атрибут) маркера, который переносит информационный результат операции (событийный результат = функция завершила работу). При интеграции workflow сети с docflow сегментов, вычисление истинности условия (s) может проводиться на основе текущего состояния соответствующего документа (doc), включая: шаблон заявления, заявление заполнено (подписано заявителем), заявление с резолюцией директора «утвердить», заявление с резолюцией директора «не утвердить», оформленный приказ на отпуск. Таким образом, проверка s будет включать: документ находится в состоянии «утвердить» и «не утвердить» в советующей ветви. Граф переходов сети docflow - как отдельный сегмент «дуальной сети» - организован аналогично (напоминает) workflow. Например, для выделенного выше состояния маркировка docflow будет: doc{0,0,1,0,0}, которая и будет проверяться в сети workflow.

Разбор работы алгоритма, приведенного на рис. 1 с состояниями {р1, р2, р3, р4, р5, р6}, определит следующий маршрут движения маркера: p1-p2-p3-p4-p2-p3-p5-p6, т.е. будет выполнено 8 шагов. Начальная маркировка сети: {1,0,0, 0,0,0}, финальная: {0,0,0, 0,0,1}.   

Коротко и упрощенный алгоритм имитационной модели для сети с одним маркером (нет параллельных вычислений) по графу рис. 1 и рис. 2. См. также раздел «3 Алгоритм обработки workflow на примере Excel представления».

1 Инициализация.

Если требуется подсчет числа пройдённых шагов, то вводим n = номер шага дискретизации, например, ячейка А1 на листе «run», изначально n=0.

Рассчитываем максимальный индекс узла модели: p_max = номер последнего узла (вычисляется максимальный индекс с ненулевым значением на листе «model»). Если «1» - номер начального узла, то начальная маркировка = {1,0,0 …0}, а последний узел всегда с максимальным значением индекса.

Запишем номер начального узла в переменную i, например, ячейка А2 на листе «run», и далее в ней будем сохранять индекс текущего узла. Если начальная маркировка начинается не с узла с номером «1», то «пробегаемся» от 1 до p_max по первой строке листа «action» и смотрим где «не ноль» - это и будет индекс i (начальный узел).

2 Увеличиваем шаг дискретизации (основной цикл).

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

Если операция закончена на текущем шаге дискретизации, то меняем маркировку (для текущего шага ставим «0») и вычисляем переход: по таблице переходов (лист «model») смотрим какой следующий узел и какой фильтр на пути к нему (условный или безусловный переход).

Например, условие перехода (для упрощения) будет значение ячейки А3 (на листе «run») и будет чередоваться «нет» \ «да» при каждой процедуры принятия решения: первый раз подумали – «нет», второй раз – уже «да» (и т.д.). Напомним, что получение исходных данных для вычисления условия s выходит за рамки метамодели workflow сети.  

Для расчета перехода образуется цикл, перебирающий все ненулевые ячейки («0» и «пусто») в таблице переходов по строке i (индекс текущего узла). После вычисления значения перехода (s) определяется - реализован ли переход («true» – реализован, иначе не реализован).

4 Для реализованных переходов меняется маркировка: на листе «action» ставится «1» для узла с реализованным переходом (для условий примера, достаточно знать i, т.к. в остальных будут нули). Проверяется: достигла ли новая маркировка финальной позиции (i=6): если да, то конец алгоритма, если нет, то увеличивается шаг дискретизации, т.е. переходим к пункту 2.

Основные процедуры метамодели: Определение исходящей дуги (следующего узла, куда возможно переместится маркер) и Вычисление истинности условия (действительно ли маркер переместится) на рис. 9 выделены «жирным».

Кроме расчета значений имитационной модели в ячейках Excel можно на каждом шаге дискретизации макросом корректировать лист значений в Excel – листе («data») Excel to Graphviz и вызывать перерисовку графа на каждом шаге с подсвечиванием текущего узла (движение «бегунка» может задаваться выделением контура текущего узла), тем самым получая представление системы (генерируя граф под текущую разметку) на каждом шаге в нужной нотации, заданной на листе «styles» (с учетом ограничений, указанных в Отрытый Вопрос по визуализации схем процессов).

8 Математические свойства модели

Применительно к классификации сетей Петри в базовом варианте модели WF2M свойственно:

А) безопасная (safe, 1-bounded net), т.е. не более одного маркера в позиции (k-ограниченная сеть, при k=1). Безопасность / ограниченность понимается по условию, что если в элементе «операция» окажется более одного маркера, то это ошибочная работа алгоритма целевого бизнес-процесса;

Б) чистая сеть. Переход (дуга) не может иметь позицию в качестве входной и выходной, в расширениях WF2M может быть иначе;

С) ординарная, т.е. вес каждой дуги равен 1;

Д) свойства WF-сети, в части: есть начальное место (начало алгоритма), объединяющее начальные события, есть финальное место, объединяющее финальные события. Каждый промежуточный узел сети расположен на пути от начального места к финальному;

Е) бездефектная (soundness), включая:

- сеть безопасная,

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

- конечная вершина достижима из любой разметки,

- живая сеть (liveness, живость): содержит только живые переходы, т.е. сеть не содержит лишних переходов. (которые никогда не будут выполнены). При этом подразумевается выполнение соответствующих условий, заданных в s;

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

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

Заключение

Предложенная WF2M модель позволяет формализовать алгоритмы бизнес-процессов в части workflow визуально простым и формально точным (однозначно) образом. Представлен инструментарий WF2M в виде графической нотации, математической модели (аналитическая форма), матричного представления, скриптового языка (на примере dot) и программной реализации (алгоритм преобразования и представление переменных на листах Excel).

Модель WF2M может быть полезна:

- при верификации алгоритмов, анализе схем бизнес-процессов путем ее уточнения в терминах WF2M: устранение неоднозначностей, присутствующих в иных нотациях, например, ЕРС;

- в системах имитационного моделирования бизнес-процессов при задании логики исполнения алгоритма (набора состояний, логики срабатывания переходов и ветвлений алгоритма и т.п.);

- для формирования «понятному непрограммисту» скриптового (языкового) описания алгоритма (от схемы к скриптовому описанию) или наоборот: формирование скрипта для генерации схемы процесса (от скрипта к схеме процесса);

- при разработке «стандартной машины чтения алгоритма», т.е. абстрактной машины, которая при заданном алфавите (набор символов) читает пользовательский алгоритм, составленный на заданном алфавите (типа машины Тьюринга \ Поста для чтения алгоритмов бизнес-процессов).

Формализация потока документов (материалов, заготовок и т.п.) docflow вынесена в связанную задачу: можно дополнить модель WF2M сегментом docflow: моделирование данных, например, состояний документов, потока данных - как это принято в классической ЕРС нотации. Предполагается, что в общую модель будет добавлена отдельная docflow сеть, наложенная на WF2M, где элемент «операция» будет уже выполнять не роль «место, состояние», роль перехода документа из одного состояния в другое (переключателя состояний в docflow). Есть какая-либо модификация сети Петри с таким дуализмом: в одной сети места одного сегмента (измерения, проекции) сети становятся переходами для другого сегмента сети? Дуализм dPN-сети про иное.

Предпосылка статьи. Предварительно была проведена безрезультативная попытка на основе запроса «A Mathematical Modelling for Workflows» найти материалы, которые позволят на математическом языке описать как общий сценарий обработки workflow (алгоритма «в целом», включая движение маркера-бегунка по сети, определенную алгоритмом бизнес-процесса), так и его элементы (логические блоки): and-join, or-split и т.п., т.е. формальное описание основных паттернов workflow. Уровень (формализм) описания должен был быть достаточен для введения формул в excel (т.е. не просто абстракции, не имеющие конкретной реализации) и получения имитационной модели workflow-алгоритма. Пример, приведенный при формализации AND-join, показывает, что сети Петри (как математическая модель workflow) могут быть использованы только для низкоуровневого представления сети (поведение маркера в НУП иное, чем в привычном понимании «работающего» узла алгоритма), поэтому «нормальное» представление workflow-алгоритма требует иной математической и имитационной модели.

Также не дали ответа (на запрос): спецификации workflow нотаций, например, BPMN2, пояснения реализаций Workflow Patterns, например, в BPMN Camunda, или в системах имитационного моделирования, например, ARENA.

Литература:

[Pete84] Питерсон Дж. Теория сетей Петри и моделирование систем

https://scask.ru/k_book_petri.php

[Kopp03] Geschäftsprozessmodellierung und Reengineering mittels prozess- und objektorientierter Methoden. Tabelle 14: Transformation eEPK und Petri – Netz

http://www.veit-koeppen.de/pub/frei/K03.pdf

[MMP15] А.М. Миронов, А.Г. Михеев, В.Е. Пятецкий, Алгоритм проверки ограниченности числа точек управления в экземпляре бизнес-процесса, Пробл. управл., 2015, выпуск 1, 30–37

https://www.mathnet.ru/links/71ea03a13298c5172292ff2fb0fac851/pu896.pdf

[Aal98epc] W.M.P. van der Aalst. Formalization and Verification of Event-driven. Figure3: Events are mapped on to places and functions are mapped on to transitions.

https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=5eea124c2cff41a3eca438acc7077f02cb61c683

[Aal98wfm] W.M.P. van der Aalst. The Application of Petri Nets to Workflow Management.
The Journal of Circuits, Systems and Computers, 1998.

https://web.archive.org/web/20040501022418id_/http://home.ifi.uio.no:80/~andersmo/petrinet/papers/workflow/application_workflow_management53.pdf

[MG16] А.А. Мицель, Е.Б. Грибанова Имитационное моделирование экономических процессов в Excel. Рис. Алгоритм моделирования полной группы несовместных событий

https://portal.tpu.ru/SHARED/k/KATAEV/academics/Tab1/MIM_P_Lab_Excel.pdf

PS1 Вопросы по инклюзивному шлюзу (OR-split / OR-join) в BPMN

1 Для анализа логики BPMN нужна математика, однако часто дается лишь неформальное описание "словами", например, inclusive-gateway.md Camunda.

2 Пример формального описания:

Formal Semantics and Implementation of BPMN 2.0 Inclusive Gateways

Проблема обозначена, формулы приведены, но не совсем понятно решение, вкл. BPMNinc: NonBlocking, StepPathAnnotation, ComputePathAnnotation. В целом как и в сети WF2M проводится анализ пути маркера и связывание OR-split с OR-join.

3 Симулятор BPMN

Можно попробовать посмотреть симуляторы BPMN. Обычно инклюзивный шлюз симуляторы BPMN не поддерживают, см. мин. 8:30:

BPMN: Как работает симуляция токена в CAMUNDA Modeler

Однако со временем инклюзивный шлюз стал поддерживаться плагином:

https://github.com/camunda/camunda-modeler-token-simulation-plugin

Однако логика его работы все равно не понятна.

В 2024 планируется обновление плагином версии с поддержкой inclusive-gateway он-лайн симулятора Storm

4 Реализация Inclusive Gateways в WF2M (упрощено). В WF2M модели (схеме, таблице переходов) для каждого "или разветвления" даётся ссылка на связанный с ним "или объединитель". Не обязательно один к одному (связь через идентификаторы).

При реализации модели экземпляром при прохождении маркера через «или разветвитель» взводится ветвь «или объединителя» через увеличение счетчика его. В итоге «или объединитель» точно знает, сколько маркеров нужно для выполнения синхронизации.

Ситуация, когда маркер, который взвел ветвь объединителя, но до прихода в взведенный объединитель потерялся (удален на пути к связанному «или объединителю», т.е. где "его ждут") - не учитывается в базовом варианте сети (может быть учтена расширением, опять же удалением единицы из счётчика объединителя). Это странный случай, впрочем, как и образование в той же ветви нового маркера, вместо удаленного.

PS2

Формализация WF2M сети на примере алгоритма Кофе-машина и два ученых

https://habr.com/ru/articles/789570/

Теги:
Хабы:
Всего голосов 7: ↑7 и ↓0+7
Комментарии8

Публикации

Истории

Работа

Ближайшие события

Конференция HR API 2024
Дата14 – 15 июня
Время10:00 – 18:00
Место
Санкт-ПетербургОнлайн
Конференция «IT IS CONF 2024»
Дата20 июня
Время09:00 – 19:00
Место
Екатеринбург
Summer Merge
Дата28 – 30 июня
Время11:00
Место
Ульяновская область