Моделирование и оптимизация workflow-процессов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Горбунов, Олег Евгеньевич
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Ярославль
МЕСТО ЗАЩИТЫ
|
||||
|
2006
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
Горбунов Олег Евгеньевич
МОДЕЛИРОВАНИЕ И ОПТИМИЗАЦИЯ \У01*КР1,0\У-ПР0ЦЕСС0В
01.01.09 - дискретная математика и математическая кибернетика
Автореферат
диссертации на соискание ученой степени кандидата физико-математических наук
Ярославль - 2006
Работа выполнена на кафедре теоретической информатики Ярославского государственного университета им. П.Г. Демидова.
Научный руководитель: кандидат физико-математических наук,
профессор
Соколов Валерий Анатольевич
Официальные оппоненты: доктор физико-математических наук,
профессор
Ломазова Ирина Александровна
доктор физико-математических наук, профессор
Угланов Алексей Владимирович
Ведущая организация: Ивановский государственный химико-
технологический университет
Защита диссертации состоится «22» декабря 2006 г. в часов на заседании диссертационного совета Д 212.002.03 при Ярославском государственном университете им. П.Г. Демидова по адресу: 150008, г. Ярославль, ул. Союзная, 144.
С диссертацией можно ознакомиться в библиотеке Ярославского государственного университета им. П.Г. Демидова
Автореферат разослан «££» ноября 2006 г.
Ученый секретарь диссертационного совета
Яблокова С,И.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Объект исследований и актуальность темы
Современные подхода к решению задач повышения эффективности систем управления в значительной мере основаны на новых информационных технологиях, важнейшей из которых является технология управления и оптимизации бизнес-процессов.
В настоящее время благодаря появлению мощной вычислительной техники, распространению сетевых технологий и развитию новых концепций в сфере ведения бизнеса (ERP - Enterprise Resource Planning, CRP - Capacity Requirements Planning, ... ) растет интерес к электронным средствам поддержки ведения бизнеса. Об этом свидетельствует, в частности, появление нескольких стандартов на языки описания бизнес-процессов и на автоматическое взаимодействие приложений через Web-сервисы от таких компаний, как SAP AG, Sun Microsystems, IBM, Microsoft
До недавнего времени не существовало специального средства поддержки управления workflow-процессами. Поэтому отдельные части бизнес-процесса реализовывались в разных прикладных программах и были относительно разрозненны. Взаимосвязь этих частей осуществлялась в самих программах, что нежелательно, так как при изменении бизнес-процесса приходится изменять программное обеспечение. Это трудоемко и негибко. Более того, похожие программные блоки необходимо реализовывать в нескольких программах и невозможно осуществлять мониторинг и контроль всего workflow-процесса как единого целого. Управление workflow-процессами предлагает новый подход к контролю, мониторингу, оптимизации и сопровождению бизнес-процессов. В настоящее время, с развитием вычислительных средств и коммуникаций, возникла возможность охватить всю систему целиком, рассмотрев составляющие ее процессы как единое целое, и выводя контур исполнительного управления на передний план.
Появились электронные системы управления бизнес-процессами. Многочисленные примеры внедрения подобных систем и значительного улучшения экономических показателей на предприятиях за рубежом говорят об очередном прорыве в сфере ведения бизнеса. Выделение бизнес-
процессов, их анализ, совершенствование и управление ими - колоссальный резерв для повышения конкурентоспособности компаний и эффективности их работы.
Идея представления организации в виде набора бизнес-процессов, а управления ее деятельностью - как управление бизнес-процессами стала распространяться в конце 80-х годов. Лучшие компании мира на практике доказали важность, эффективность, экономичность и прогрессивность перехода на клиептно-ориентнровагаюе производство и процессно-ориентированную структуру управления производством. Тогда же начали появляться стандарты ИСО серии 900х на деятельность организации, которые предполагают как минимум определение и документирование бизнес-процессов.
Сегодня система управления большинства российских предприятий имеет ярко выраженную функциональную направленность. В основе подобной организации управления лежит принцип разделения и специализации труда, описанный в работе А. Смита «Достояние народа», опубликованной еще в конце XVIII века. Однако в нынешних условиях этот подход к управлению оказывается неэффективным. Реальная деятельность не осуществляется в соответствии с линейно-функциональной иерархией - она пронизывает предприятие в виде набора бизнес-процессов, которые в большинстве своем никем не управляются, не описаны и не документированы. Пятьдесят лет назад и ранее, когда вычислительные средства поддержки информационной деятельности не были доступны, существование функционально-ориентированного подхода к управлению было не только оправданным, ио и единственно возможным решением в управлении сложными объектами.
В настоящее время компании мирового уровня используют методы управления процессами в рамках реализации стратегии всеобщего управления качеством (TQM, Total Quality Management).
Переход па процессную ориентацию - та неизбежность, с которой придется столкнуться практически каждому среднему и крупному российскому предприятию, если оно хочет не только выжить, но и успешно развиваться. . Для обеспечения конкурентоспособности российских
предприятий необходимо учитывать не только технологии вчерашнего дня, но и развивающиеся в текущий момент, разрабатывать новые.
В диссертации для управления бизнес-процессами предлагается применять различные классы сетей Петри. Такой подход позволяет использовать наглядные и математически строгие модели в качестве языка описания луогкАоту-процессов. С другой стороны, теория сетей Петри предоставляет мощные средства анализа. Они позволяют проверить корректность моделей \тогкйо«г-процессов во избежание негативных ситуаций (блокировок, бесконечно повторяющихся циклов и т.п.).
Для оценки производительности и оптимизации работы \vorkflow-процессов в диссертации введен новый подкласс сетей Петри - ЗКСФР' -сети.
В диссертации дня моделирования луогкйо№-процессов используется несколько подклассов сетей Петри, позволяющих учитывать различные аспекты процесса.
Целя и задачи диссертационной работы
Цель работы заключается в разработке методов моделирования \уогкЛо№-процессов с учетом времени, их анализа и оптимизации.
Для достижения этой цели были поставлены следующие задачи:
]. Изучить разные классы сетей Петри для моделирования \vorkfl сиг-процессов.
2. Определить и исследовать новый класс сетей Петри, позволяющий моделировать \уогкАо\у-процессы с учетом ресурсов и времени.
3. Исследовать взаимосвязь моделей \уогкАо\у-процессов с моделями теории массового обслуживания.
4. Разработать методы анализа и оптимизации моделей на основе теории массового обслуживания.
5. Провести эксперименты с тестовыми моделями \vorkflow-процессов.
6. Проанализировать результаты экспериментов и проверить результата анализа и эффективность оптимизации.
Методы исследования и формальный аппарат
Методы исследования основаны на использовании аппарата сетей Петри, теории массового обслуживания, стохастических процессов. Исследование моделей у/огкЯочу-процессов в программе ЕхЗрей опирается на специфический язык программы с одноименным названием.
Научная новизна
Научная новизна работы обусловливается тем, что теория бизнес-процессов только развивается. В связи с этим, отсутствует единая универсальная методология по моделированию и анализу бизнес-процессов, а существующие отдельные коммерческие продукты, использующие разные методологические базы наряду с достоинствами обладают и недостатками. В диссертации разработаны новые методы моделирования, анализа и оптимизации лтогкЯоадг-процессов с учетом ресурсов и времени. Получены результаты симуляции некоторых моделей мгогкАо\у-процессов в программе ЕхЗрес!.
Практическая значимость работы
Работа содержит описания новых формализмов сетей Петри для моделирования тл'огкЛочл'-процессов. Проведены исследования по анализу и оптимизации таких моделей. Теоретические выводы подтверждены результатами численных экспериментов. Полученные результаты могут быть использованы для решения прикладных задач при разработке моделей \уогкЯо\У-процессов1 а также для разработки блоков распределения ресурсов в системах управления хдгагкйоту-процессами.
Апробация работы
Основные положения и "результаты работы докладывались и обсуждались на следующих международных и российских конференциях:
Междисциплинарной (медицина, биология, физика, радиоэлектроника, химия, математика, информатика, педагогика .,.) конференции с международным участием «Новые биокибернетические н телемеднци некие технологии 21 века для диагностики и лечения заболеваний человека» («НБИТТ-21»), г, Петрозаводск, 23-25 июня 2003 года.
Международной научно-практической конференции «Актуальные проблемы развития экономики», Иваново, 2003.
6-ой всероссийской научно-практической конференции «Стратегия бизнеса и социально-экономическое развитие региона», пЯрославль, 27 ноября 2003 года.
Ш научно-практической конференции студентов и аспирантов (с международным участием) «Экономика и бизнес: позиция молодых ученых», г.Барнаул, 28-29 апреля 2004.
Полученные результаты обсуждались на научном семинаре «Моделирование и анализ информационных систем» факультета информатики и вычислительной техники Ярославского государственного университета им. П.Г. Демидова.
Публикация результатов работы
По теме диссертации опубликовано 7 научных работ. Из них 3 статьи в местных изданиях, 4 доклада на конференциях.
Личный вклад автора.
Выносимые на защиту результаты получены соискателем лично.
Структура я объем работы.
Диссертация состоит из введения, двух глав, заключения и приложений. Работа изложена на 153 страницах и иллюстрирована 25 рисунками. Список литературы содержит 113 наименований.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Введение-
Во введении обосновывается актуальность выбранной тематики исследований, формулируется цель и поставленные задачи, характеризуются научная новизна и практическая ценность работы, дается краткий обзор диссертации.
Глава 1. Моделирование workflow-шкщессов специальными классами сетей Пиан
Глава посвящена моделированию workilow-процессов сетями Петри, широко используемым средством моделирования и анализа процессов.
В этой главе для того, чтобы учитывать время, необходимое для выполнения задач workflow-npouecca, и вероятности различных альтернатив, введен новый подкласс сетей Петри - SRCWF* -сети. Он обобщает WF- и RCIW-сети. .Для введенных SRCWF' -сетей предлагаются методы оценки производительности и оптимизации их работы.
В главе вводятся различные специальные классы сетей Пеггри и рассматриваются вопросы моделирования и анализа workflow-процессов с их помощью.
Эти специальные классы сетей Петри опираются на более общие, использующиеся для моделирования широкого круга систем. Поэтому в разделе 1.1 приводятся необходимые определения, обозначения и результаты для общих классов сетей Петри.
В пункте 1.1.1 содержатся необходимые определения, связанные с обычными сетями Петри (с единичной кратностью дуг), так как все классы сетей Петри так или иначе опираются на них. Определяются свойства обычных сетей Петри, которые будут использоваться в диссертации. Приведенные свойства касаются как структуры сети (структурные свойства), так и ее поведения (поведенческие свойства).
В пункте 1.1.2 описываются сети Петри с приоритетами и исследуются их свойства. Доказывается следующая теорема.
Теорема 1.1.
Если в некоторой /W^-сети Л',, со свободным выбором переходы из некоторого класса SC4 имеют разные приоритеты, то в этом классе существуют мертвые переходы.
В пункте 1.13 приводятся основные направления расширения обычных сетей и определяются сети Петри высокого уровня.
В пункте 1.1.4 описываются вложенные сети Петри.
В пункте 1.1.5 вводится класс стохастических сетей Петри с приоритетами £№, сочетающий особенности вВРН -сетей и интервальных сетей Петри.
В разделе 1.2 рассматриваются вопросы моделирования \vorkflow-процессов специальным классом сетей Петри - ЯУ -сетями. Этот класс позволяет моделировать структуру «'огкАо\у-процесса и проверять его свойства и будет необходим в следующих разделах диссертации в качестве основы для построения более сложных классов сетей.
В пункте 1.2.1 приводятся все основные типы связи задач, использующиеся при описании структуры \тогкйо1У-процесса.
В пункте 1.2.2 вводится подкласс сетей Петри, -сети, использующийся специально для моделирования \vorkflow-npoueccoB. Описывается метод моделирования и соответствие между ИТ -сетью и \уогкЯо\у-процессом. Определяется свойство надежности -сети, важнейшее свойство, предъявляемое к подобным моделям, и результаты по его доказательству. Перечисляются достоинства подхода к моделированию \тогкАо\у-процессов на основе сетей Петри.
В пункте 1.2.3 описан пример \тогкЯо\у-процесса в виде ИТ -сети . Во многом этот пример является ключевым, так как далее в диссертации на его основе будут строится другие модели и проводиться симуляция.
В разделе 13 рассматривается метод моделирования \vorkflow-процессов с учетом ресурсов организации (машины, персонал и так далее), необходимых для выполнения задач процесса. Для этого в работе используются КСУГР -сети.
В пункте и .2 приводятся пример модели угогкАочг-процесса в виде ЛСГРГ-сети
В разделе 1.4 рассматривается метод моделирования луогкЙоэдг-лроцессов вложенными сетями Петри, Такие сети позволяют компактно представлять ч/огкАо\у-процеесы со сложной многоуровневой структурой, где объекты, участвующие в процессе, имеют некоторую структуру, могут проявлять активность И изменять свои состояния.
Приводится характерный пример, когда такой подход целесообразен.
Ра мел 1.5 посвящен новым методам моделирования workflow-процессов, позволяющим делать оценки производительности моделей и проводить их оптимизацию.
В пункте 1.5.1 вводится новый формализм - SW-сети. Сочетая возможности WF -сетей, SWF' -сети позволяют учитывать время, необходимое для выполнения задач workflow-nponecca, и вероятности различных альтернатив.
Рассматривается свойство надежности SWF' -сетей и доказывается следующая теорема.
Теорема
Если некоторая ИТ-сеть со свободным выбором N = {P,T,F'то сеть с приоритетами N'=(F,T',F*',F'',Pf): P'=P,r=r,F"= F~,F-'~ F-,4tl\t;eru1,Sa/=*Pi{t,,) = T>rt,t/) с той же начальной разметкой т'=т, надежна.
В пункте 1-5.2 вводится еще один новый формализм - SRCWF' -сети. В нем сочетаются возможности SWFи RCWF-сетей. SRCWF*-сети могут использоваться для моделирования, анализа и оптимизации workflow-процессов.
Таким образом, направление моделирования и анализа workflow-процессов получает в этой главе дальнейшее развитие.
Глава 2. Анализ и оптимизация молелен workflow-nnoiieccon в виде SRCWFe-сетей
В этой главе изучаются различные подклассы SRCWF' -сетей для моделирования, анализа и оптимизации workflow-процессов.
Приводятся методы анализа и оптимизации этих сетей на основе теории массового обслуживания. Даются соответствующие алгоритмы. Для иллюстрации разбираются несколько моделей workflow-процессов.
Приводятся результаты симуляции этих моделей в пакете ExSpecL
Раздел 2.1 посвящен анализу SRCWF'* -сетей.
В пункте 2.1.1 вводятся SRCWF'' - и SRCWF?- сети - подклассы SR.CWF* - сетей. Приводятся необходимые определения и обозначения, используемые на протяжении всей главы.
В пункте 2.1.2 ставится задача оптимизации SRC4T'1 -сети, заключающаяся в минимизации суммы штрафов от простоя выполнения задач workflow-процесса из-за занятости ресурсов:
FJ^E(WT,)PF(t) min.
Здесь E(WT,) - математическое ожидание времени простоя перехода / из-за занятости необходимого ресурса, PF(t) - функция штрафа, сопоставляющая каждому переходу штраф за простой в единицу времени.
В пункте 2.1.3 приводится пример SRCWF'' -сети - сеть Ns. В
последующих разделах будут приведены результаты экспериментов с сетью N,.
В пункте 2.1.4 отмечается, что в силу несложной структуры SRCWF? -сетей, лежащая в их основе RCWF -сеть надежна.
В разделе 2.2 приводятся методы анализа и оптимизации SRCWF
сетей на основе теории массового обслуживания. В начале раздела проводится соответствие между SRCM>F,°' -сетями и сетями массового
обслуживания. Существующего математического аппарата теории массового обслуживания недостаточно для анализа подобных сетей в общем виде. Поэтому в диссертации предлагается определенным образом модифицировать структуру и изменить приоритеты переходов SRCJVF,'' -сети, получив SRCWF* - сеть. Соответствующее преобразование приведено в пункте 2.2.1 и проиллюстрировано примером в пункт« 2.2.2.
В пункте 2.2.3 приводятся некоторые дополнительные предположения, касающиеся SRCiVF'' -сетей, позволяющие в пункте 2.2.5 от
сети массового обслуживания перейти к нескольким хорошо известным системам типа Af„[M|t иМ|М|<ю.
В пункте 2.2.4 приводится алгоритм определения ннтенсивностей входящего потока заявок в каждой из систем исходя из структуры SRCWF^ -
сети. Приведем этот алгоритм.
Алгоритм определения ннтенсивностей поступления фишек в позиции из множества Рр SRCWF*-сети.
Через О будем обозначать список позиций. Через кр обозначается
последний присвоенный позиции номер, через к, - последний присвоенный
переходу номер, V - текущая просматриваемая позиция, / - начальная позиция, с, - текущий просматриваемый переход.
ВХОД: ЖСТ^;1 - сеть Л^^и^о^.Г^г,,^}, р; иг; и{(Л(,(,х/,//)},(г,рг).
ВЫХОД:
Список /,0 - - интенсивность поступления фишек в позицию
список /(0: /, (с,) - интенсивность потребления фишек переходом с.еТ^У,};
список N¡0: -номерпозиции ср\
список Л7,0: - номер перехода с,.
ШАГ 1. Инициализация.
Из исходной ЗЯСИТ* - сети N выделим сеть ЛР (Р,,Г <-»{/,), ^ и ((*„»)}. . ^ Рг) ■ Все шаги алгоритма будут выполняться на
Л1.
поместить в О
ПОЗИЦИЮ I.
ШАГ 2. Выбор очередной вершины.
Если список 0 не пуст, присвоить и очередной элемент из £>, такой, что все его входные переходы помечены, и выполнить ШАГ 3. Если список пуст, то КОНЕЦ.
ШАГ 3. Обработка смежных позиций. Обозначим =
Для всех позиций и-, таких, что пУСО, выполнить следующие действия.
■ Введем вспомогательную переменную С„:=0. Для каждого (е (V . П . и>): к, ^ к, 4- (/)» А, ;С„ ^ С„ + /, (0 > /, О)^;
с
о кр^кр + (V) := к у, 1р (») ¡р 0)-^-; поместить и» в
если н> не помечена;
С
о /,0»}:^/,(») + /,(*)—если » помечена.
ШАГ 4. Переход к следующей вершине.
Удалить очередную позицию из б и вернуться к ШАГУ 2.
КОНЕЦ,
В пункте 2.2.6 дается алгоритм вычисления суммы штрафов от простоя выполнения задач \уогкАо\у-процесса из-за занятости ресурсов и среднего времени прохождения через сеть. В этом алгоритме используются результаты работы алгоритма
В этом алгоритме используются результаты работы алгоритма определения интенсивностеЙ поступления фишек в позиции сети, а именно, списки N,0 и 1,0. Заметим, что все переходы из 7" и {/,} будут помечены числами, которые будут занесены в список N, 0:
N,(1) - номер перехода Размер списка N,0 равен |Ги{/,} |= л+].
/,(/) - интенсивность потребления фишек переходом t.
Алгоритм определения значений 1(КТ,), Г и Н ВЯСЯТ'1- сети.
ВХОД:
жгжр;' - сеть N = (Рг иРг и^.Ги {/„//},
ВЫХОД:
Я(ИТ,у б Т„ - среднее время ожидания срабатывания перехода ( из-за занятости ресурса;
Р - значение функции штрафа; Я - среднее время прохождения фишек через сеть.
ШАГ 1. Инициализация.
Из исходной -сети N выделим сеть 1Г
(Рр,Т,и{г1},Р} Все шаги алгоритма будут выполняться на
Обозначим Л = IV(11 > - интенсивность поступления фишек в позицию I.
Применим алгоритм определения интенсивностей поступления фишек в позиции для сети /Г.
ШАГ 2. Перебор всех переходов из Т. Для } от 2доп+1 Начало
Пусть 0 = >.
-если г е Тг, то вычислить Е(№Т,) по формуле (1). Пусть / € Г^, и имеет обозначение /^^.Тогдав (1):
значение приоритетного класса к равно приоритету перехода Рг^^);
- число типов заявок п равно | Т„ |= пу;
- равна /ДО, где - переход из 7, с приоритетом г;
^ ^ «¡4). = ГДе '' ' ПереХ°Д И3
с приоритетом Р^+РРвюУЕфГ^);
- если 1еГ/Г, И Рг(Г) = 0,ТО
* гЬщдУ
Конец. КОНЕЦ.
Здесь формула (1) - это формула д м средних времен ожидании заявок нз приоритетного класса к системы М, | в„| 1 с относительными
приоритетами. Она приведена в приложении В.
Алгоритм определения приоритетов у переходов из множества Тг 5ЯСФР*- сети для минимизации суммы штрафа к = ^£(ИТ,)№(/)иш
Г»
Приводится в пункте 2,2.7.
Алгоритм оптимизации функции F ЗйСИТ/'-сети.
ВХОД:
- сеть N = ÍPíluPrupt,Tu{t„t/}, ВЫХОД:
- сеть N с модифицированными приоритетами у переходов из ШАГ ]. Инициализация.
Применим алгоритм определения интенсив!юстей поступления фишек в позиции сети N. В результате будет построен список /,(): 1,(1) -интенсивность потребления фишек переходом / е Т и {(,};
Найдем множества Г„ ,...,Г„;| Тл ¡= я, Т„ [=»яд1 и соответствующие системы массового обслуживания ■■■,<?, типа Мщ ]М\1 с дисциплинами обслуживания в порядке приоритета. ШАГ 2.
Для каждой системы ^ выполнить следующее.
Упорядочим все переходы '^хи»—в порядке убывания значения
-. В результате каждый переход получит некоторый номер
/.Сох.»)/«^.»)
Присвоим переходу 1им приоритет равный У^о*,))' РК'^*,))^',^,,) * КОНЕЦ.
В разделе 23 приведены результаты экспериментов с моделями лтогкйоаднпроцессов в виде ЯйСЖР," - и ЗКСВУ* - сетей в пакете Ех8рес1 Для
этого в пакете была разработана библиотека для удобного моделирования задач \гагкйо\у-процесса.
Эксперименты проводились с тремя моделями: сетью Л^,
полученной из нее ХИСЦ'Р? - сетью ИА со случайно выбранньши приоритетами из г, и сетью Ы, с приоритетами, полученными с помощью алгоритма из пункта 2.2,7.
Выполнялось 1000 серий экспериментов. Длительность каждой серии - 480 временных единиц. Если в качестве временной единицы считать минуту, то длительность эксперимента соответствует около 3,9 годам, если продолжительность рабочего дня считать равной 480 минутам, а количество рабочих дней в году равным 255.
Сеть Ы, в пакете ЕхБрей изображена на Рис. 1.
Рис.1 Сеть в пакете Бх8рес1.
Результаты экспериментов с сетью К, показали, что среднее время прохождения фишек через сеть примерно па 0,1333 временных единиц (порядка 1,3 %) меньше значения, полученного с помощью алгоритма из
ШЕЗ
раздела 2.2.6. Средний штраф примерно па 0,5023 (порядка 1,1 %) больше значения, полученного с помощью этого алгоритма.
Использование приоритетов, полученных с помощью алгоритма минимизации штрафов из пункта 2.2.7, дает сокращение среднего штрафа примерно на 8,7562 (порядка 15,6 %) по сравнению с аналогичной сетью без приоритетов. Среднее время прохождения фишек через сеть Л^ сократилось примерно на 0,7141 временных единиц (порядка 6,6 %).
На рис. 2 приведены значения среднего времени прохождения через сеть N1 по сериям экспериментов.
Рис. 2. Среднее время прохождения через сеть по сериям экспериментов.
Использование приоритетов, полученных с помощью алгоритма минимизации штрафовиз раздела 2.2.7, дает сокращение среднего штраф примерно на 26,2195 (порядка 35,7 %) по сравнению с сетью М, с
приоритетами, выбранными случайным образом. Среднее время прохождения фишек через сеть NJ сократилось примерно на 0,8357
временных единиц (порядка 7,6 %).
На рис. 3 приведены значения среднего времени прохождения через Л^ по сериям экспериментов.
« |Щ||
- ч» «я V» к* ям «м мо
Рис. 3. Среднее время прохождения через сеть Л^ по сериям экспериментов.
На рис. 4 приведены значения среднего времени прохождения через сеть л/} по сериям экспериментов.
•0 1
1]_* . , 4
Рис. 4, Среднее время прохождения через сеть Л^ по сериям экспериментов.
Приложения
В приложении А приводятся основные понятия и определения в области управления \тогкАо«г-процессами.
Описывается концепция архитектуры интегрированных информационных систем (АРИС) как базовой инфраструктуры для методов моделирования информационных систем. Указывается место управления №огкЯо№-процессами в этой архитектуре. Определяется понятие дуогкйочу-процесса, приводятся характеристики его производительности. Указываются пути улучшения этих характеристик.
В приложении В даются все необходимые сведения из теории массового обслуживания. Определяется общая модель, используемая в теории массового обслуживания, и параметры, необходимые для ее спецификации. Описываются некоторые частные системы, вероятностно-разделительная дисциплина обслуживания заявок нескольких типов.
В приложении С приведены некоторые окна пакета ЕхЗрей с моделями ягсти?*1 - и ЗНОТЕ* -сетей, па которых проводилась симуляционные эксперименты.
ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ
1. Изучены разные классы сетей Петри для моделирования workflow-процессов.
2. Определен и исследован новый класс стохастических сетей Петри (SRCfW'-cera), позволяющий моделировать workflow-процессы с учетом ресурсов и времени. SRCWF' -сети позволяют в рамках одной модели использовать методы анализа обычных сетей Петри (например, исследование дерева достижимости) и вычислять производительность на основе статистических методов и проводить оптимизацию.
3. Исследована взаимосвязь SRCWF" -сетей с моделями теории массового обслуживания.
4. Предложены методы анализа SRCWF" -сетей на основе теории массового обслуживания.
5. Разработан алгоритм нахождения параметров SRCWF'' -сети для оптимизации ее работы.
6. Построены модели и выполнена симуляция workflow-процессов в виде SRCWF" -сетей в программе ExSpect.
7. Исследованы результаты симуляции моделей workflow-процессов в программе ExSpect, подтверждающие теоретические выводы.
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
1. Горбунов O.E. Моделирование бизнес-процессов многоуровневыми сетями Петри // Междисциплинарная (медицина, биология, физика, радиоэлектроника, химия, математика, информатика, педагогика ...) конференция с международным участием «Новые биокибернетические и телемедицинские технологии 21 века для диагностики и лечения заболеваний человека» (НБИТТ-21).-Петрозаводск, 2003.-С. 83.
2. Соколов В.А., Горбунов O.E. Новые информационные технологии управления бизнес-процессами // 6-я всероссийская научно-практическая конференция «Стратегия бизнеса и социально-экономическое развитие региона». — Ярославль, 2003. — С. 23-26.
3. Горбунов O.E., Соколов В .А. Об использовании вложенных сетей Петри для моделирования бизнес-процессов // Проблемы экономики, финансов и управления производством. — Иваново: Ивановский гос. хим.-тех. университет, 2003.-Ме 14. - С. 253-263.
4. Горбунов O.E., Соколов В.А. Использование вложенных сетей Петри для моделирования бизнес-процессов // Международная научно-практическая конференция «Актуальные проблемы развития экономики». - Иваново, 2003. - С. 112-114.
5. Горбунов O.E. Моделирование и анализ бизнес-процессов с помощью сетей Петри // III научно-практическая конференция студентов и аспирантов (с международным участием) «Экономика и бизнес: позиция молодых ученых». - Барнаул, 2004. - С. 331-333.
6. Горбунов O.E. Моделирование и оптимизация workflow-процессов // Актуальные проблемы математики и информатики. — Сборник статей к 20-летию факультета ИВТ ЯрГУ им. П.Г. Демидова. - 2006.
7. Горбунов O.E. Оптимизация выполнения workflow-процессов. // Моделирование и анализ информационных систем. - Ярославль: ЯрГУ, 2005. -Т.12, № 1. — С. 45-51.
Формат А5. Печ. л. - 1Тираж 100 экз. Подписано к печати 21.11.2006. Захаз № 2660. Лицензия ЛР Хз 071542 от 24.11.97 Редакционио-издагельский центр МУБиНТ 150003 г. Ярославль, ул. Советская, 80
Введение
1 Моделирование workflow-процессов специальными классами сетей Петри
1.1 Сети Петри.
1.2 Моделирование workflow-процессов
W F- сетями.
1.3 Моделирование workflow-процессов
RCW F-сешш.
1.4 Моделирование workflow-процессов вложенными сетями Петри.
1.5 Моделирование workflow-процессов
SRCWFe-сетями.
2 Анализ и оптимизация моделей workflow-процессов в виде SRC'WFe-c&reik
2.1 Анализ SRCWFel-ceTe%
2.2 Применение теории массового обслуживания для анализа SRCWFcl-сетей.
2.3 Экспериментальные результаты.
Современные подходы к решению задач повышения эффективности систем управления в значительной мере основаны на новых информационных технологиях, важнейшей из которых является технология управления и оптимизации бизнес-процессов.
В настоящее время благодаря появлению мощной вычислительной техники, распространению сетевых технологий и развитию новых концепций в сфере ведения бизнеса (ERP - Enterprise Resource Planning, CRP - Capacity Requirements Planning, .) растет интерес к электронным средствам поддержки ведения бизнеса. Об этом свидетельствует, в частности, появление нескольких стандартов на языки описания бизнес-процессов и на автоматическое взаимодействие приложений через Web-сервисы от таких компаний, как SAP AG, Sun Microsystems, IBM, Microsoft
До недавнего времени не существовало специального средства поддержки управления workflow-процессами. Поэтому отдельные части бизнес-процесса реализовывались в разных прикладных программах и были относительно разрозненны. Взаимосвязь этих частей осуществлялась в самих программах, что нежелательно, так как при изменении бизнес-процесса приходится изменять программное обеспечение. Это трудоемко и негибко. Более того, похожие программные блоки необходимо реали-зовывать в нескольких программах и невозможно осуществлять мониторинг и контроль всего workflow-процесса как единого целого. Управление workflow-процессами предлагает новый подход к контролю, мониторингу, оптимизации и сопровождению бизнес-процессов. В настоящее время, с развитием вычислительных средств и коммуникаций, возникла возможность охватить всю систему целиком, рассмотрев составляющие ее процессы как единое целое, и выводя контур исполнительного управления на передний план [30].
Появились электронные системы управления бизнес-процессами. Многочисленные примеры внедрения подобных систем и значительного улучшения экономических показателей на предприятиях за рубежом [55] говорят об очередном прорыве в сфере ведения бизнеса. Выделение бизнеспроцессов, их анализ, совершенствование и управление ими - колоссальный резерв для повышения конкурентоспособности компаний и эффективности их работы.
Идея представления организации в виде набора бизнес-процессов, а управления ее деятельностью - как управление бизнес-процессами стала распространяться в конце 80-х годов. Лучшие компании мира на практике доказали важность, эффективность, экономичность и прогрессивность перехода на клиентно-ориентированное производство и процессно-ориентированную структуру управления производством. Тогда же начали появляться стандарты ИСО серии 900х на деятельность организации, которые предполагают как минимум определение и документирование бизнес-процессов.
Сегодня система управления большинства российских предприятий имеет ярко выраженную функциональную направленность. В основе подобной организации управления лежит принцип разделения и специализации труда, описанный в работе А. Смита «Достояние народа», опубликованной еще в конце XVIII века. Однако в нынешних условиях этот подход к управлению оказывается неэффективным. Реальная деятельность не осуществляется в соответствии с линейно-функциональной иерархией - она пронизывает предприятие в виде набора бизнес-процессов, которые в большинстве своем никем не управляются, не описаны и не документированы. Пятьдесят лет назад и ранее, когда вычислительные средства поддержки информационной деятельности не были доступны, существование функционально-ориентированного подхода к управлению было не только оправданным, но и единственно возможным решением в управлении сложными объектами.
В настоящее время компании мирового уровня используют методы управления процессами в рамках реализации стратегии всеобщего управления качеством (TQM, Total Quality Management).
Переход на процессную ориентацию - та неизбежность, с которой придется столкнуться практически каждому среднему и крупному российскому предприятию, если оно хочет не только выжить, но и успешно развиваться. Для обеспечения конкурентоспособности российских предприятий необходимо учитывать не только технологии вчерашнего дня, но и развивающиеся в текущий момент, разрабатывать новые.
В диссертации для управления бизнес-процессами предлагается применять различные классы сетей Петри. Такой подход позволяет использовать наглядные и математически строгие модели в качестве языка описания workflow-процессов. С другой стороны, теория сетей Петри предоставляет мощные средства анализа. Они позволяют проверить корректность моделей workflow-процессов во избежание негативных ситуаций блокировок, бесконечно повторяющихся циклов и т.п.).
Для оценки производительности и оптимизации работы workflow-npo-цессов в диссертации введен новый подкласс сетей Петри
SRCWF'-cffrti.
Классические сети Петри были изобретены К.А. Петри в шестидесятых годах 20 в. С тех пор было создано множество их модификаций (раскрашенные сети Петри [74], вложенные сети Петри [16], стохастические сети Петри [104, 85] и т.д.) и найдены приложения в самых разных областях. В диссертации для моделирования workflow-процессов используется несколько подклассов сетей Петри, позволяющих учитывать различные аспекты процесса. Перечислим эти подклассы, заодно делая краткий обзор работ других авторов.
Первым подклассом являются ИЛР-сети. WF-сети позволяют моделировать структуру workflow-процесса и проверять его свойства. WF-сети были введенны W.M.P. van der Aalst, одним из первых исследователей, использовавших сети Петри для моделирования workflow-процессов [32, 33, 35, 36, 37, 38]. Им же было сформулировано свойство надежности модели workflow-процесса в виде WF-сети и доказан способ его проверки исходя из структуры сети. M.Voorhoeve, N.Sidorova, К. van Нее [65, 66] и др. рассмотрели это свойство для модели, в которой участвуют несколько экземпляров workflow-процесса. Ими была доказана разрешимость задачи проверки надежности для этого случая и приведен соответствующий алгоритм.
Для моделирования workflow-процессов с учетом ресурсов организации (машины, персонал и так далее), способных выполнять задачи процесса, в диссертации используются ROW F-сети. Эти сети были выделены в отдельный подкласс M.Voorhoeve, N.Sidorova, К. van Нее [69].
Следующим подклассом являются вложенные сети Петри. Они позволяют компактно представлять workflow-процессы со сложной многоуровневой структурой, где объекты, участвующие в workflow-процессе, имеют некоторую структуру, могут проявлять активность и изменять свои состояния. Вложенные сети Петри были введены и исследованы И.А. Ломазовой [16].
В диссертации для того, чтобы учитывать время, необходимое для выполнения задач workflow-процесса, и вероятности различных альтернатив, введен новый подкласс сетей Петри - SRCWFe-сети. Он обобщает WF- и RCWF-сети. Для введенных SRCWFe-сетей предлагаются методы оценки производительности и оптимизации их работы.
Таким образом, направление моделирования и анализа workflow-npo-цессов получает дальнейшее развитие.
В SRCWFe-сетях с точки зрения временного поведения синтезируются некоторые возможности интервальных [34, 92] и стохастических сетей Петри (GSPNs) [41, 81]. Однако они обладают рядом уникальных особенностей, являясь новым средством моделирования и анализа workflow-процессов.
Напомним, что введение концепции времени в формализм сетей Петри было предложено C.Ramchandani [91], P.Merlin и D.Farber [84], J.Sifakis [99]. Множество последующих различных подходов в основном основывалось на использовании детерминированных временных задержек. Сети Петри с вероятностными временными задержками были введены F.Symons [104], G.Florin, S.Natkin и M.Molloy [85]. Эти подходы открыли возможность связи сетей Петри с оценкой производительности, обычно основанной на подходе с помощью вероятностного моделирования. Эти модели и их модификации сейчас называются Stochastic Petri nets (SPNs). Дальнейшее развитие подхода было предложено М. Ajmone Marsan, G. Balbo и G. Conte [82]. Вероятностные задержки сочетались с детерминированными нулевыми задержками. Таким образом, временное и логическое поведение системы могло быть описано в одной модели. G. Balbo исследовал стохастические сети Петри и их применение в различных областях, в том числе и в экономике [41]. В ранних работах W.M.P. van der Aalst также был введен класс сетей Петри со временем - интервальные стохастические сети Петри [34]. Исследовались их свойства и алгоритм мы расчета характеристик сети. Это направление получило дальнейшее развитие в работе Н.А. Reijers [92]. Им был построен ряд практических моделей и проведены численные эксперименты с ними.
Цель работы заключается в разработке методов моделирования workflow-процессов с учетом времени, их анализа и оптимизации.
Для достижения поставленной цели были сформулированы следующие задачи:
1. Изучить разные классы сетей Петри для моделирования workflow-процессов.
2. Определить и исследовать новый класс сетей Петри, позволяющий моделировать workflow-процессы с учетом ресурсов и времени.
3. Исследовать взаимосвязь моделей workflow-процессов с моделями теории массового обслуживания.
4. Разработать методы анализа и оптимизации моделей на основе теории массового обслуживания.
5. Провести эксперименты с тестовыми моделями workflow-процессов.
6. Проанализировать результаты экспериментов и проверить результаты анализа и эффективность оптимизации.
Методы исследования основаны на использовании аппарата сетей Петри, теории массового обслуживания, стохастических процессов. Исследование моделей workflow-процессов в программе ExSpect опирается на специфический язык программы с одноименным названием.
Научная новизна работы обусловливается тем, что теория бизнес-процессов только развивается. В связи с этим, отсутствует единая универсальная методология по моделированию и анализу бизнес-процессов, а существующие отдельные коммерческие продукты, использующие разные методологические базы наряду с достоинствами обладают и недостатками. В диссертации разработаны новые методы моделирования, анализа и оптимизации workflow-процессов с учетом ресурсов и времени. Получены результаты симуляции некоторых моделей workflow-процессов в программе ExSpect.
Теоретическая и практическая значимость. Работа содержит описания новых формализмов сетей Петри для моделирования workflow-процессов. Проведены исследования по анализу и оптимизации таких моделей. Теоретические выводы подтверждены результатами численных экспериментов. Полученные результаты могут быть использованы для решения прикладных задач при разработке моделей workflow-процессов, а также для разработки блоков распределения ресурсов в системах управления workflow-процессами.
Структура работы. Диссертация состоит из введения, двух глав, заключения, списка литературы и приложений.
ВЫХОД:
E(WTt), I G Тг - среднее время ожидания срабатывания перехода t из-за занятости ресурса; F - значение функции штрафа; Я - среднее время прохождения фишек через сеть.
ШАГ 1. Инициализация.
Из исходной SRG'WFf-сети N выделим сеть N' = (Pp,TU {U}, F+ U {(U,i)},F~, W, Рг). Все шаги алгоритма будут выполняться на N'.
Обозначим Л = W(U) - интенсивность поступления фишек в позицию г. Применим алгоритм определения интенсивностей поступления фишек в позиции для сети N'.
ШАГ 2. Перебор всех переходов из Т. Для j := 2 до п + 1 Начало
Пусть Nt{t) = j. - если I G Тг, то вычислить E(WTt) по формуле (В.9). Пусть t G Try и имеет обозначение Тогда в (В.9):
- значение приоритетного класса к равно приоритету перехода Pr(t^x))\
- число типов заявок п равно \Тту\ = пу;
- А(,;) равна It{tz), где 1г - переход из Тгу с приоритетом г\
- 4) Равен ^ = W2(l)(x)}, где tg - переход из Тгу с приоритетом г. Здесь используется то, что в SRCWFel-сетях у всех переходов из множества Тгу одно и то же значение функции W().
F:=F + PF(twx))E(WT4iimy,
H^H + ^f^EiWT^J-, - если t £ Т/Тт и Pr(t) = 0, то
Я ■= Я 4- /i(-t(y)(x)'> 1 а ЩЧм,))' Конец.
КОНЕЦ.
Легко убедиться, что приведенный алгоритм вычисляет значения среднего времени ожидания срабатывания перехода t из-за занятости ресурса (E(WTt), t £ Тг), функции штрафа F и среднего время Я прохождения фишек через сеть и для исходной SRCWFpl-сети N.
Численные эксперименты, приведенные в разделе 2.3, показали следующее. Для SRCWFf1-сети JV5 (см. таблицу 2.4) среднее время прохождения фишек через сеть примерно на 0,1333 временных единиц (порядка 1,3 %) меньше значения, полученного с помощью приведенного выше алгоритма, а средний штраф примерно на 0,5023 (порядка 1,1%) больше.
2.2.7 Оптимизация SRCWF^-сетей
Критерий оптимизации сети приведен в (2.1). Для удобства выпишем его еще раз:
F=Y, E{WTt)PF(t) min. texr
На величину E(WTt), t G Tr{ в SRCWF^1-сети можно влиять изменением приоритетов у переходов из Tri.
В разделе В приводится тот факт (из [24]), что минимум линейной функции от средних времен ожидания заявок в системе Mn\Gn\l достигается при дисциплине обслуживания с относительными приоритетами, и приводится метод определения ее параметров (перестановки а - (ci'i,. ,ап)).
Таким образом, для оптимизации (2.1) необходимо найти соответствующую расстановку приоритетов в каждой из систем систем </?ь </?2, • • •, </V
Приведем алгоритм, оптимизирующий функцию (2.1). Пусть дана сеть SR.CWF;l-ceTb N = {РриРМ)д,Ти{и,1;},Р+иР7+и{(и, г), (th рд)}, F~U F~ U {{рд,и), (/,£/)}, W,Pr). В результате работы алгоритма находятся оптимальные перестановки а в каждой из систем </?], </?2, • • •, </V
Алгоритм оптимизации функции F (2.1) S НС W Ff-сети. ВХОД: SRCWFf-сеть N. ВЫХОД:
SRCWFf-сеть с модифицированными приоритетами (значением функции PrQ) у переходов из Тг.
ШАГ 1. Инициализация.
Применим алгоритм определения интенсивностей поступления фишек в позиции для сети N. В результате будет построен список ItQ: lt(t) - интенсивность потребления фишек переходом t е Т.
Найдем множества Тг1,. ,Trs; \Тг1\ — щ,., |Tr,s| = ns, и соответствующие системы массового обслуживания • • •, типа МЩ\М\1 с дисциплинами обслуживания в порядке приоритета. Таким образом, в каждой системе щ типов заявок, интенсивности поступления равны h(t{j)(i)), параметр показательного распределения времени обслуживания равен W((t(j^) (см. раздел 2.2).
ШАГ 2.
Для каждого множества Trj выполнить следующее. Упорядочим все переходы i'(j)(i),., t{j){nj) в порядке убывания значения •)(.))■ ® результате каждый переход получит некоторый номер V{tfj){i)). Присвоим переходу ty)^ приоритет равный V(t^)(i)):
Рг(*ш) = у(Чт)
КОНЕЦ.
Приведенный алгоритм в каждой системе ^ устанавливает относительные приоритеты у заявок разных типов, что соответствует изменению функции Рг() у переходов из Trj SRCWFf -сети N. Приведенный алгоритм минимизирует функцию (2.1).
Численные эксперименты, приведенные в разделе 2.3, показали следующее. Для SRCWFf-сети No, (см. рисунок 2.1 и таблицу 2.1) с приоритетами, полученными по приведенному выше алгоритму оптимизации, среднее время прохождения фишек через сеть примерно на 0,7141 временных единиц (порядка 6,6 %) меньше соответствующего значения для сети SRCWFf-ceTttN3. Полученные данные штрафа у SRCWFf-сети Ns примерно на 8,7562 (порядка 15,6 %) меньше соответствующего значения для SRCW Ff- сети N3.
2.3 Экспериментальные результаты
Симуляция заключается в имитации действительности (в данном случае - организации и окружающей среды) на соответствующем программном обеспечении. На вход системы подаются экземпляры workflow-процессов. Далее измеряют все необходимые характеристики работы системы. Эксперименты в диссертации проводились для следующих основных целей: оценить влияние сделанных упрощений для анализа сети массового обслуживания и проверить эффективность алгоритмов из разделов 2.2.6 и 2.2.7.
Результаты экспериментов с тестовой моделью показали, что среднее время прохождения фишек через сеть примерно на 0,1333 временных единиц (порядка 1,3 %) меньше значения, полученного с помощью алгоритма из раздела 2.2.6. Средний штраф примерно на 0,5023 (порядка 1,1%) больше значения, полученного с помощью этого алгоритма.
Использование приоритетов, полученных с помощью алгоритма из раздела 2.2.7, дает сокращение среднего времени прохождения фишек через тестовую сеть примерно на 0,7141 временных единиц (порядка 6,6 %) по сравнению с аналогичной сетью без приоритетов. Средний штраф сократился примерно на 8,7562 (порядка 15,6 %).
Использование приоритетов, полученных с помощью алгоритма из раздела 2.2.7, дает сокращение среднего времени прохождения фишек через тестовую сеть примерно на 0,8357 временных единиц (порядка 7,6 %) по сравнению с аналогичной сетью с приоритетами, выбранными случайным образом. Средний штраф сократился примерно на 26,2195 (порядка 35,7 %).
В диссертации для симуляции использовался пакет ExSpect. Приведем необходимые сведения про этот пакет.
2.3.1 Пакет ExSpect
Пакет ExSpect разработан в техническом университете г.Эйндховен, Нидерланды. Начиная с 1980 года, выпущено несколько версий пакета. В настоящее время актуальна версия 6.41, включающая графическую оболочку, специфический язык описания моделей, синтаксический анализатор и симулятор. В основе языка ExSpect лежит формализм раскрашенных сетей Петри со временем.
Есть возможность создания библиотек компонентов из модулей для специфических предметных областей. Уже существуют модули для work-flow-процессов, процессов логистики, административных процессов и других. Это позволяет в графической оболочке быстро строить модели из соответствующих компонентов, проводить анализ их производительности и симуляцию. Анализ workflow-процессов с помощью ExSpect позволяет определять узкие места в процессах организации, принимать управленческие решения по реорганизации предприятия, проводить оптимизацию процессов и распределять кадровые n машинные ресурсы. Можно импортировать модели процессов, созданных в других пакетах и системах управления workflow, таких, как COSA Workflow (Ley GmbH, COSA Solutions) и Protos (Pallas Athena).
Модели могут быть проверены на синтаксическую корректность. Симуляция может проводиться по шагам, непрерывно или с точками останова.
Проведение верификации модели не предусмотрено в ExSpect. Однако есть возможность экспорта описания модели с последующим анализом в соответствующих программных пакетах.
Основными компонентами модели языка ExSpect являются процессоры и каналы (соответствующие переходам и позициям в сетях Петри), соединенные между собой (аналогично сетям Петри). Как в раскрашенных стохастических сетях Петри, фишки в каналах имеют некоторое значение и временную метку. С каждым каналом связан некоторый тип (определяющий тип фишек, которые могут в нем находиться), с каждым процессором - функция (задающая правило срабатывания процессора). Если не указывать временные задержки, получится модель без времени аналогично раскрашенным сетям Петри.
Язык ExSpect состоит из двух частей.
Первая часть используется для описания типов и функций. Имеется несколько примитивных типов и несколько конструкций для определения новых типов на основе базовых. По аналогии имеется несколько базовых функций и конструкции для определения новых. Допускается полиморфизм функций. ExSpect перед выполнением производит проверку типов.
Другая часть ExSpect используется для описания сети процессоров и каналов.
В ExSpect есть пять примитивных типов: void, bool, num, real, str. Операторы типов следующие: оператор множества ($), декартова произведения (><) и отображения (->). Из примитивных типов с помощью этих операторов формируются новые типы, которым присваиваются новые имена. Например: type weight from real with [x] x >= 0.0; type volume from real with [x] x >= 0.0; type manufacturer from str; type truck from manufacturer >< (weight >< volume); type truckid from num; type fleetoftrucks from truckid -> truck; type cargo from weight >< volume;
В ExSpect довольно обширный список базовых функций, из которых строятся новые функции. Например: transportablebytruck[c: cargo, t: truck] := pil(c) <= pil(pi2(t))) and (pi2(c) <= pi2(pi2(t))): bool; transportablebyfleet[c: cargo, f: fleetoftrucks]:= if f = О then false else transportablebytruck(c,pi2(pick(f))) or transportablebyfleet(c,frest(f)) fi: bool;
Функции pil, pi2 (проекции), pick и frest (соответственно взятие и удаление элемента из отображения) являются примерами базовых функций.
Определения процессоров разделены на заголовок и содержимое. Заголовок содержит имя процессора, его связи с входными и выходными каналами и параметры. Содержимое содержит выражения для выходных каналов. Например: proc transportfunction[in leave: truck, out arrive: truck, val d: time]:= arrive <- leave delay d;
Этот процессор может использоваться для моделирования транспортировки с временной задержкой. Время между прибытием и отправлением задается параметром d.
Система может содержать другие системы в качестве подсистем. В зависимости от того, есть ли у системы взаимодействие с внешней средой, системы делятся на открытые и закрытые. Открытые системы взаимодействуют с внешним миром через входные и выходные каналы и хранилища. Системы, подобно процессорам, состоят из заголовка, наподобие заголовка процессора, и содержимого. Системы могут иметь в качестве параметров значения, функции, процессоры и другие системы. Таким образом, молено создавать общие системы с последующей их настройкой для конкретных ситуаций. Системы можно соединять, образуя более большие системы. Это позволяет производить дизайн моделей сверху-вниз.
2.3.2 Результаты экспериментов
В разделе приведены результаты экспериментов с моделями workflow-процессов в виде SRCWFf- и SRCWFf -сетей в пакете ExSpect. Для этого в пакете была разработана библиотека для удобного моделирования задач workflow-процесса. Эксперименты проводились с тремя сетями: SRCWFf-сетью jV3j полученной из нее S-RCWFp1-сетью JV4 со случайно выбранными приоритетами из Тг и сетью N5 с приоритетами, полученными с помощью алгоритма из пункта 2.2.7. Результаты экспериментов с моделью N5 показали, что среднее время прохождения фишек через сеть примерно на 0,1333 временных единиц (порядка 1,3 %) меньше значения, полученного с помощью алгоритма из раздела 2.2.6. Средний штраф примерно на 0,5023 (порядка 1,1 %) больше значения, полученного с помощью этого алгоритма.
Для симуляции была создана библиотека в пакете ExSpect, позволяющая строить модели workflow-процессов в виде SRCWFf и SRCWЯ®1-сетей.
Исследуем SRCWFf-сеть 7V3, приведенную на рисунке 2.1. С помощью преобразования из раздела 2.2 получим SRCWF^1-сеть N3. Для определенности обозначим ее Л/4. Приоритеты добавленных в результате этого преобразования переходов выбраны произвольно. Параметры сети vV4 приведены в таблице 2.3.
С помощью алгоритма определения интенсивностей поступления фишек в позиции SRCWFf-сети, найдем соответствующие интенсивности для //4. Заметим, что It{tf) = It{k)
Применим алгоритм оптимизации функции F (2.1) для нахождения оптимальных приоритетов у переходов £ {1,2,., 5} и е
1,2}. Полученную сеть обозначим jV5.
Используя алгоритм определения значений E(WTt), F и Я, найдем соответствующие значения для сети Л/5.
Полученные значения интенсивностей /t(), приоритетов Рг() и средних времен ожидания E(WTt) приведены в таблице 2.4.
Значение функции штрафа F « 46,7393.
Среднее время прохождения фишек через сеть Я 10,2589 временных единиц.
Эксперименты проводились с тремя моделями: SRCWFf-сетью N3, SRCWFf-сетью N4 и SRCW F^-сетъю Nb. Выполнялось 1000 запусков системы (серий). Длительность каждой серии - 480 временных единиц. Если в качестве временной единицы считать минуту, то длительность эксперимента соответствует около 3,9 годам, если продолжительность рабочего дня считать равной 480 минутам, а количество рабочих дней в году равным 255.
В каждой серии с получались выборочные значения следующих величин:
• WT™. Измерения проводились по каждому переходу t £ Тт при прохождении через него фишки;
Переход Pr() wo PF{) к 0 0,5 к 6 7,0 к 6 3,0 к 6 2,0 к 6 8,0 к 0 15,0 к 0 5,0
Ь 6 1,0 km 0 2,0 3,0 km 2) 0 2,0 1,0 km 0 2,0 1,5 km 0 2,0 4,0 km) 0 2,0 5,0
2)(1) 0 0,75 7,0
2)(2) 0 0,75 5,0 ь{т 3 2,0 3,0
1)(2) 5 2,0 1,0
1)(3) 1 2,0 1,5 t'cm 2 2,0 4,0 f! W) 4 2,0 5,0
2 0,75 7,0 42) (2) 1 0,75 5,0
Заключение
В результате проведенной диссертационной работы были получены следующие основные результаты:
1. Изучены разные классы сетей Петри для моделирования workflow-процессов.
2. Определен и исследован новый класс стохастических сетей Петри (.SRCWFe-ceTit), позволяющий моделировать workflow-процессы с учетом ресурсов и времени. SRCW Fe-сети позволяют в рамках одной модели использовать методы анализа обычных сетей Петри (например, исследование дерева достижимости) и вычислять производительность на основе статистических методов и проводить оптимизацию.
3. Исследована взаимосвязь SRCWFel-сетей с моделями теории массового обслуживания.
4. Предложены методы анализа SRCWFel-ceTeft на основе теории массового обслуживания.
5. Разработан алгоритм нахождения параметров SRCWFel-ceTn для оптимизации ее работы.
6. Построены модели и выполнена симуляция workflow-процессов в виде Si?CW-Ре1-сетей в программе ExSpect.
7. Исследованы результаты симуляции моделей workflow-процессов в программе ExSpect, подтверждающие теоретические выводы.
Полученные результаты могут быть использованы для решения прикладных задач при разработке моделей workflow-процессов, а также для разработки блоков распределения ресурсов в системах управления workflow-процессами.
1. Ачасова С.М., Бандман О.Л. Корректность параллельных вычислительных процессов. Новосибирск: Наука, 1990. - 253 с.
2. Бандман О.Л. Корректность асинхронных параллельно-потоковых систем обработки данных. // Программирование. 1986. - № 1. - С. 13-22.
3. Бандман О.Л. Синтез асинхронного управления параллельными процессами. // Кибернетика. 1980. - № 1. - С. 42-49.
4. Белов Ю.А. Элементы теории множеств и математической логики. Учебное пособие. - Ярославль: Ярославский государственный университет, 2002. - 60 с.
5. Виленкин С.Я., Гольденберг Р.И., Розенблит С.И. Язык управления заданиями для вычислительных комплексов с централизованным управлением. // Программирование. 1982. - № 2. - С. 35-44.
6. Горбунов О.Е., Соколов В.А. Об использовании вложенных сетей Петри для моделирования бизнес-процессов. // Проблемы экономики, финансов и управления производством. Иваново: Ивановский гос. хим.-тех. университет, 2003. - № 14. - С. 253-263.
7. Горбунов О.Е., Соколов В.А. Использование вложенных сетей Петри для моделирования бизнес-процессов. // Международная научнопрактическая конференция «Актуальные проблемы развития экономики». Иваново, 2003. - С. 112-114.
8. Горбунов О.Е. Оптимизация выполнения workflow-процессов. // Моделирование и анализ информационных систем. Ярославль: ЯрГУ, 2005. - Т. 12, № 1. - С. 45-51.
9. Громов Александр, Каменнова Мария, Старыгин Александр. Управление бизнес-процессами на основе технологии Workflow. // Открытые системы. 1997. - № 1.
10. Карлин С. Основы теории случайных процессов. М.: Мир, 1971. -536 с.
11. Клейнрок JI. Теория массового обслуживания. Пер. с англ. / Пер. И.И. Грушко; ред. В.И.Нейман. - М.: Машиностроение, 1979. - 432 с.
12. Клейнрок Л. Вычислительные системы с очередями. Пер. с англ. под ред. Б.С.Цыбакова. - М.: Мир, 1979. - 600 с.
13. Котов В.Е. Сети Петри. М.: Наука, 1984. - 160 с.
14. Ломазова И.А. Вложенные сети Петри: моделирование и анализ распределенных систем с объектной структурой. Ярославль: ЯрГУ, 2002. - 151 с.
15. Ломазова И.А. Дискретная математика. Математические основы обработки информации: Учебное пособие. Ярославль: ЯрГУ, 2000. -80 с.
16. Минский М. Вычисления и автоматы. М.: Мир, 1971.
17. Мурата Т. Сети Петри: свойства, анализ, приложения. // ТИИЭР. 1989. - Т. 77, № 4.
18. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984. - 264 с.
19. Соколов В.А., Горбунов О.Е. Новые информационные технологии управления бизнес-процессами. // 6-я всероссийская научно-практическая конференция «Стратегия бизнеса и социально-экономическое развитие региона». Ярославль, 2003. - С. 23-26.
20. Тимофеев Е.А. Вероятностно разделительная дисциплина обслуживания и многогранник средних времен ожидания в системе GI\Gn\l. // Автоматика и телемеханика. - 1991. - № 10. - С. 121125.
21. Тимофеев Е.А. Оптимальные приоритеты в системе GI\Gn\l. // Кибернетика. 1990. - № 6. - С. 36-43.
22. Тимофеев Е.А. Оптимизация средних длин очередей в системе обслуживания с ветвящимися потоками вторичных требований. // Автоматика и телемеханика. 1995. - № 3. - С. 60-67.
23. Угланов А.В. Об оптимизации одной системы обслуживания. //5 международная вильнюсская конференция по теории вероятностей и математической статистике. Вильнюс, 1989. - Т.4. - С. 299.
24. Угланов А.В., Цыпленкова Е.В. Об оптимальной организации одной системы массового обслуживания. // Отраслевая научно-техническая конференция «Интегральные оптические сети связи».- Ленинград, 1989. Т.1. - С. 28-29.
25. Феллер В. Введение в теорию вероятностей и ее приложения, Том1. М.: Мир, 1964. - 498 с.
26. Феллер В. Введение в теорию вероятностей и ее приложения, Том2. М.: Мир, 1964. - 752 с.
27. Хинчин А.Я. Работы по математической теории массового обслуживания. М.: Физматгиз, 1963. - 236 с.
28. Шеер Август-Вильгельм. Бизнес-процессы. Основные понятия. Теория. Методы. 2-е издание. Пер. с англ. - М.: Весть - МетаТехноло-гия, 1999. - 152 с.
29. Яглом A.M., Яглом И.М. Вероятность и информация. 3-е издание.- М.: Наука, 1973. 512 с.
30. W. М. P. van der Aalst. The application of Petri Nets to Workflow Management. // The Journal of Circuits, Systems and Computers. -1998. № 8 (1). - P. 21-66.
31. W. M. P. vail der Aalst and К. M. van Нее. Workflow Management: Models, Methods, and Systems. MIT Press, 2002. - 359 p.
32. W. M. P. van der Aalst. Interval Timed Petri Nets and their analysis. // Computing Science Notes. Netherlands, Eindhoven: Eindhoven University of Technology, 1991. - № 91/09.
33. W. M. P. van der Aalst. Verification of workflow nets. // LNCS. -Springer-Velag, Berlin, 1997. Vol. 1248. - P. 407-426. (Conference Aplication and Thery of Petri Nets 1997, ICATPM'1997. In P.Azema and G.Balbo, editors).
34. W.M.P. van der Aalst. Structural Characterizations of Sound Workflow Nets. // Computing Science Reports. Eindhoven: Eindhoven University of Technology, 1996. - № 96/23.
35. W.M.P. van der Aalst. A class of Petri net for modeling and analyzing business processes. // Computing Science Reports. Eindhoven: Eindhoven University of Technology, 1995. - № 95/26.
36. W.M.P, van der Aalst. Modeling logistic systems with ExSpect. // Proc. of Dynamic modelling of Information Systems. In H.G. Sol and K.M. van Нее, editors. Amsterdam: Elsevier Science Publishers, 1991. - P. 269-288.
37. Rob Allen. Workflow: An Introduction. // http://wfmc.org/information/Workflow-AnIntroduction.pdf.
38. Gianfranco Balbo. Introduction to Stochastic Petri Nets. // LNCS.- Springer-Verlag, 2001. Vol. 2090. (Conference FMPA2000. In E. Brinksma, H. Hermanns, and J.-P. Katoen, editors). - P. 84-155.
39. Berthomieu B. and Diaz M. Modeling and verification of time dependent systems using time Petri nets. // IEEE Trans. Softw. Eng. 1991. - № 17(3). - P. 259-273.
40. Buy U. and Sloan R. A Petri-net-based approach to real-time program analysis. // Seventh Intrnat. Workshop on Software Specification and Design. Dec 1993. - P. 56-60.
41. J. A. Buzacott and J.G. Shanthikumar. Stochastic Models of Manufacturing Systems. Prentice Hall, 1993.
42. Casanave. Business-Object Architectures and Standards. 1997.
43. Cooper R. B. Introduction to queueing theory. Second edition. -Elsevier North Holland, Inc., 1981. - 347 p.
44. Corbett J.C. and Avrunin G.S. A practical technique for bounding the time between events in concurrent real-time systems. // Internat. Sympos. On Software Testing and Analysis. ACM, June 1993. - P.110-116.
45. Cormen Т.Н., Leiserson C.E., and Rivest R.L. Introduction to Algorithms. MIT Press / McGraw-Hill, 1990.
46. Hans Daduna. Queueing Networks with Discrete Time Scale. // LNCS.- Springer-Verlag, 2001. Vol.2046. - 138 p.http://www.daimi.au.dk/designCPN
47. J. Desel and J. Esparza. Free Choice Petri Nets. // Cambridge tracts in theoretical computer science. Cambridge: Cambridge University Press, 1995. - Vol. 40.http://www.exspect.com
48. ExSpect User Manual. // http://www.exspect.com. Fingar. Blueprint for Business Objects. 1996.
49. Fischer, Layna. Excellence in Practice Volume III. Future Strategies Inc., Lighthouse Point, 1999.
50. Peter J.Haas. Stochastic Petri Nets for modelling and simulation. // Proceedings of the 2004 Winter Simulation Conference. In R.Ingalls, M.Rossetti, J.Smith, B.Peters, editors. 2004.
51. Hack M. Petri Net Languages. Cambridge: MIT, 1976.
52. Hack M. Decidability Questions for Petri Nets, MIT Lab. // Computer Science. Springer-Verlag, 1980. - № 84.
53. Hammer M., Champy J. Re-engineering the corporation. London: Nicolas Brealey Publishing, 1995.
54. Hammer M., Champy J. Business Reengineering. 1995.
55. Harrington. Business Process Improvement. 1991.
56. Hauschildt D., Verbeek H.M.W., van der Aalst W.M.P. WOFLAN: a Petri-net-based Workflow Analyzer. // Computing Science Reports. -Eindhoven: Eindhoven University of Technology, 1997. № 97/12.
57. K. van Нее, Somers L. J., Vorhoeve M. A Formal Framework for Dynamic Modelling of Information Systems. // Dyn. Mod. Inf. Sys. North Holland, 1991. - P. 227-236.
58. Van Нее К., Sidorova N., Voorhoeve M. Resource-Constrained Workflow Nets. // Proc. of Concurrency Specification and Programming, CS&P'2004, Caputh, 2004. Informatik-Bericht Nr. 170, Humboldt-Universitet zu Berlin. - P. 166-177.
59. Heitmeyer C., Jeffords R., and Labaw M. A benchmark for comparing different approaches for specifying and verifying real-time systems. //
60. Proc. Tenth Internat. Workshop on real-time Operation Systems and Software, May 1993. 1993.
61. Hoare C.A.R. Commucication and Sequantial Processes. London.: Prentice Hall, 1985.
62. Jacobsen. Object-Oriented Software Engineering. 1996
63. Jancar P. and Moller F. Checking regular properties of Petri nets. // LNCS. Springer-Verlag, 1995. - Vol. 962. (Conference CONCUR'95).- P. 348-362.
64. Jensen K. Coloured Petri Nets. Vol.1: Basic Concepts. EATCS Monograph 28. - Springer-Verlag, 1992.
65. Jones N.D., Landweber L.H., and Lien Y.E. Complexity of some problems in Petri nets. // Theoretical Comput. Sci. 1977. - № 4. P. 277-299.
66. Johnsonbaugh R. and Murata T. Analysis of rsource requirements in marked graph computation models. // Procs. of the 1980 IEEE International Symposium on circuits and Systems, April 1980. 1980.- P. 342-345.
67. Kelly F.P. Reversibility and Stochastic Networks. England, Chichester: John Wiley and Sons Ltd., 1979. - 230 p.
68. Korenjak A. and Hopcroft J. Simple deterministic languages. // Procs. of 7th IEEE Switching and Automata Theory conference, 1966. -1966.- P. 36-46.
69. Zhen Liu, Don Towsley. Stochastic scheduling in in-forest networks. -Juillet, 1992. 34 p.1.mazova I. On Proving Large Distributed Systems: Petri Net Modules Verification. // LNCS. Springer-Verlag. - Vol. 1277 . - P. 70-75.
70. M. Ajmone Marsan, G. Balbo, G. Conte, S. Donatelli and G. Franceschinis. Modelling with generalised stochastic Petri nets. Wiley Series in Parallel Computing. - England: John Wiley and Sons, 1994. -316 p.
71. M. Ajmone Marsan, G. Balbo, G. Conte. A class of generalized stochastic Petri nets for the performance analysis of multiprocessor systems. // ACM Transactions on Computer Systems. May 1984. - № 2(1).
72. Mayr E. An algorithm for the general Petri net reachability problem. // SIAM Journal of Computing. 1984. - № 13(3). - P. 441-460.
73. P.M.Merlin and D.J.Farber. Recoverability of communication protocols: Implications of theoretical study. // IEEE Transactions of Communications. September 1976. - № 24(9). - P. 1036-1043.
74. Molloy. M.K. On the Integration of Delay and Throughput Measures in Distributed Processing Models: PhD thesis / UCLA. Los Angeles, CA, 1981.
75. Molloy. M.K. Performance analysis using stochastic Petri nets. // IEEE Transaction of Computers. September 1982. - № 31(9). - P. 913-917.
76. Murata T. Petri Nets: Properties, Analysis and Applications. // Procs. of the IEEE. 1989. - № 77(4). - P. 541-580.
77. Myers. Knowledge Management and Organizational Design. 1996.
78. Nain P. Basic elements of queueing theory. Application to the Modelling of Computer Systems. France, Sophia Antipolis, 2004. - 110 p.
79. Charles Plesums. Introduction to Workflow. // http://wfmc.org/information/introductiontoworkflow02.pdf.
80. C.Ramchandani. Analysis of Asynchromous Concurrent Systems by Timed Petri Net: PhD thesis / Cambridge: MIT, MA, 1974.
81. Hajo A.Reijers. Design and Control of Workflow Processes. Business Process Management for the Service Industry. // LNCS. Springer-Verlag, 2003. - Vol. 2617. - 308 p.
82. Reisig W. Petri Nets. Springer-Verlag, 1985.
83. Scheer August-Wilhelm. Business Process Engineering. 1994.
84. Scheer August-Wilhelm. Efficient Information Management. 1991.
85. Schmidt K. Symmetries of Petri Nets. // Petri Net Newsletter. 1993. - № 43. - P. 9-25.
86. Schroder. Business Engineer. 1997.
87. Sebestyen. Management «Geheimnis» Kaizen. 1994.
88. J.Sifakis. Petri nets for performance evaluation. Proc. 3rd Intern. Symp. IFIP. In B.Beilner and E.Gelenbe, editors. 1978. - P. 75-93.
89. Sloun R.H. and Buy U. Reduction rules for time Petri nets. // Information Processing Letters. 1994.
90. Sloun R.H. and Buy U. Analysis of real-time programs with simple-time Petri nets. // ISSTA. Seattle Washington USA, 1994. - № 94-8/94.
91. Starke P.H. Reachability analysis of Petri nets using symmetries. // Syst. Anal. Model. Sirnul., 1991. - .№ 8. - P. 293-303.
92. Suzuki I. and Murata T. A method of stepwise refimenet and abstraction of Petri nets. // Journal of Computer and System Sciences.- 1983. № 27. - P. 51-76.
93. Symons F.J.W. Modeling and Analysis of Communication Protocols Using Numerical Petri Nets: PhD thesis: 05.1978 / Univerity of Essex.- 1978.
94. Sokolov V.A., Tiinofeev E.A. Dynamical Priorities without Time Measurment and Modification of the TCP. //LNCS. Springer-Verlag, 2001. - Vol. 2244. (Conference PSI 2001). - P. 240-245.
95. Uglanov A.V. To optimization of unreliable systems. // Procs. of WSEAS Intern. Conference in Applied Mathematics, 2004. 288, 2004.- P. 488.
96. Uglanov A.V. Optimization of one unrealible system. // Sixth Jordanian Intern. Congress of Mathematics, 2005. Collection of Abstracts. Univ. Of Irbid. (Jordan) Press. - 2005.
97. Valette R. Analysis of Petri nets by stepwise refinements. //Journal of Computer and System Sciences. 1979. - № 18. - P. 35-46.
98. Valk R. and Vidal-Naquet G. Petri Nets and Regular Languages. // Journal of Computer and System Sciences. 1981. - № 23(3). - P. 299325.
99. H.M.W. Verbeek, T. Basten, and W.M.P. van der Aalst. Diagnosing workflow processes using Woflan. // The Computer Journal. 2001. -№ 44(4). - P. 246-279.
100. Vernadat. Enterprise Modeling and Integration. 1996.
101. Voorhoeve M. ExSpect Language Tutorial. Eindhoven: Endhoven University of Technology, 1998.
102. WfMC Glossary. // http://www.wfmc.org.
