ПРИМЕНЕНИЕ  МЕТОДОВ  ТЕОРИИ  ГРАФОВ  ПРИ  ОЦЕНКЕ  ЭФФЕКТИВНОСТИ  БИЗНЕС-ПРОЦЕССОВ

Петрова  Марина  Александровна

студент  2  курса  магистратуры,  кафедра  УИТЭС  ВлГУ  им.  А.Г.  и  Н.Г.  Столетовых,  РФ,  г.  Владимир

Е-mail :  pma-33@yandex.ru

Шутов  Антон  Владимирович

научный  руководитель,  канд.  физ.-мат.  наук,  доцент  кафедры  УИТЭС

ВлГУ  им.  А.Г.  и  Н.Г.  Столетовых,  РФ,  г.  Владимир

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

Допустим,  что  задан  определенный  граф,  в  котором  для  каждой  дуги  (i;  j)  указаны  два  числа    которые  можно  определить  как  эффект  при  выполнении  конкретной  операции  —    и  затраты  на  эту  операцию  —  .  Эффективность    пути    определяется  как  отношение  его  эффекта    к  затратам  ,  то  есть    Сама  задача  подразумевает  поиск  пути  *  максимальной  эффективности:    

Допустим,  что  решение    поставленной  задачи  уже  известно,  то  по  факту  в  данном  случае  выполнено: 

                          (1)

Соответственно,  задача  сводится  к  поиску  минимального  значения  ,  для  которого  выполняется  (1).  Иначе  говоря,  необходимо  выполнить  поиск  минимального  ,  такого,  чтобы  все  пути  (длина  которых  равна)  в  графе  имели  неположительную  длину  (неравенство  (1)  должно  быть  соблюдено  также  и  для  пути  максимальной  длины). 

Алгоритм  решения: 

1.  Допустим,  что  .  Ищем  путь  m₁  максимальной  длины.  Допускаем,  что    (при    длина  пути    равна  нулю). 

2.  Найдем  максимальный  путь    при  .  Если  длина  пути  ,  обозначаемая  как  ,  равна  нулю,  то  рассматриваемая  задача  уже  решена.  Если  ,  то  считаем    и  отсюда  можно  найти  максимальный  путь    при    и  т.  д. 

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

где  коэффициенты  a  и  b  могут  быть  и  отрицательными,  и  положительными. 

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

Определим,  что  ,  где  l  —  некоторый  параметр,    —  длительность  (продолжительность)  наиболее  оптимального  пути  при  параметре  l,  т.  е.  пути,  который  имеет  максимальную  длину,  при  этом  подразумевая,  что  длина  измеряется  в    [1]  .

Из  рассмотренного  видно,  что  при  увеличении  l  величина  не  возрастает.  Определим    и    как  длительности  (продолжительности)  наиболее  оптимального  пути  при  условии,  что  l  равна  a  и,  соответственно,  b;    —  сами  пути  (для  того,  чтобы  их  найти,  нужно  решить  2  задачи,  каждая  из  которых  задача  на  поиск  пути  максимальной  длины).  Рассмотрим  6  случаев  (первоначальную  задачу  можно  разделить  на  2  подзадачи  —  поиска  максимума    при    и  при  ). 

Допустим,  что  в  этом  случае    и:

1.  если  ,  то    —  оптимальное  решение;

2.  если  ,  то    —  оптимальное  решение;

3.  если  ,  то,  при  сравнении  по  длинам    и    ,  выбирать  необходимо  именно  путь  максимальной  длины.

Допустим,  что  тогда  в  этом  случае    и:

4.  если  ,  то    —  оптимальное  решение;

5.  если  ,  то    —  оптимальное  решение;

6.  если  ,  то  данная  задача  вообще  не  имеет  рациональных  методов  решения.

Для  обеспечения  возможности  применения  данного  алгоритма  для  задачи  оценки  эффективности  бизнес-процессов  (БП)  нужно  найти  отображение  множества  БП  в  множество  элементов  графа  [1].

Ориентированный  граф  включает  три  множества:  множество  вершин  (V),  множество  дуг  графа  (Е)  и  множество  весов  графа  (L).

Бизнес-процесс  можно  описать  следующими  множествами:  множество  участников  бизнес-процесса  (S),  множество  документов,  сообщений,  файлов  (D),  множество  трудоемкостей  выполнения  функций  бизнес-процесса  (Т_О),  множество  функций  бизнес-процесса  (O).

В  данном  случае  возможны  различные  варианты  отображения.  Рассмотрим  только  некоторые  из  них.

1.  D®V,  S®Е  —  данное  отображение  определяет  состояния  БП  и  участников  БП  на  каждом  этапе  обработки  информации.

Рассмотрим  пример.

Рисунок  1  –  Граф  отображения  D→V,  S→Е

Таблица  1.

Множество  E   —  множество  участников  БП  (Пример)

Таблица  2.

Множество  V   —  элементов  множество  документов,  сообщений,  файлов

2.  D®V,  О®Е  —  данное  отображение  показывает  состояния  БД  и  функций  БП.  Рассмотрим  пример.

Рисунок  2.  Граф  отображения  D→V,  О→Е

Таблица  3.

Множество  E   —  множество  функций  БП

Таблица  4.

Множество  V   —  множество  документов,  сообщений,  файлов

3.  D®V,  О®Е,  Т®L  —  данное  отображение  показывает  состояния  БП  и  функций  БП,  а  также  трудоемкость  их  выполнения.  Рассмотрим  пример.

Рисунок  3.  Граф  отображения  D→V,  О→Е,  Т→L

Таблица  5.

Множество  E   —  множество  функций  БП

Таблица  6.

Множество  V   —  множество  документов,  сообщений,  файлов

Таблица  7.

Множество  L  —  множество  трудоемкостей  выполнения  функций  БП

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

Список  литературы:

1.Альпин  Ю.А.,  Ильин  С.Н.  Дискретная  математика:  графы  и  автоматы.  Учебное  пособие.  Казань:  Казанский  государственный  университет  им.  В.И.  Ульянова-Ленина,  2006.  —  78  с

2.Cardoso  J.,  «How  to  measure  the  control-flow  complexity  of  web  processes  and  workflows»  in  The  Workflow  Handbook,  pp.  199—212,  2005.

3.Rol´on  E.,  Ruiz  F.,  Garc´ıa  F.,  and  Piattini  M.,  «Towards  a  suite  of  metrics  for  business  process  models  in  BPMN»  in  8th  International  Conference  on  Enterprise  Information  Systems,  Paphos,  Cyprus,  2006.