Электронный научный журнал
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,682

ИСПОЛЬЗОВАНИЕ АППАРАТА ОПЕРАЦИОННОГО АНАЛИЗА ВЕРОЯТНОСТНЫХ СЕТЕЙ ДЛЯ ОПРЕДЕЛЕНИЯ СРЕДНЕГО КОЛИЧЕСТВА ПРИБОРОВ ОБСЛУЖИВАНИЯ МУЛЬТИАГЕНТНОЙ МОДЕЛИ

Ван Кай В.В. 1 Аксенов К.А. 1 Аксенова О.П. 1 Киселёва М.В. 1
1 ФГАОУ ВПО “Уральский федеральный университет им. первого Президента России Б.Н. Ельцина”
Использование аппарата систем массового обслуживания при анализе бизнес-процессов позволяет решать задачу анализа узких мест и определять среднее количество обслуживающих устройств. Современные методы анализа и динамического моделирования бизнес-процессов часто сталкиваются с объектами, в которых количество элементов составляет сотни, а то и тысячи. Производственные и бизнес-процессы, организационно-технические системы относятся к процессам преобразования ресурсов. Для моделирования таких объектов требуются все больше вычислительных ресурсов и машинного времени. В связи с этим является актуальным выявление и использование новых принципов построения, анализа и изменения мультиагентных моделей процессов преобразования ресурсов с помощью реинжиниринга бизнес-процесса (РБП) на основе процедур сверток/разверток. Свертка – процедура уменьшения размерности модели динамического процесса, позволяющая сократить время эксперимента и снизить затраты вычислительных ресурсов за счет выявления и сжатия неиспользуемых или неэффективно используемых элементов (цепочек) процесса. Развертка – процедура, увеличивающая размерность модели за счет добавления новых параллельных элементов (цепочек) процесса, решающих задачу повышения пропускной способности системы и эффективности ее функционирования.
анализ узких мест
синтез систем
мультиагентное моделирование
реинжинирниг бизнес-процессов
1. Аксенов К. А., Ван Кай Задача свертки (уменьшения размерности) имитационной модели мультиагентного процесса преобразования ресурсов // Научно-технические ведомости СПбГПУ, Информатика. Телекоммуникации. Управление. - 2011. - № 1 (115). - С. 126-133.
2. Аксенов К. А. Теория и практика средств поддержки принятия решений: монография / Germany,Saarbrucken: LAP LAMBERT Academic Publishing GmbH & Co. KG, 2011. - 341 с.
3. Аксенов К. А. Модель мультиагентного процесса преобразования ресурсов и системный анализ организационно-технических систем // Вестник компьютерных и информационных технологий. - 2009. - № 6. - С. 38-45.
4. Литвин В. Г., Аладышев В. П., Винниченко А. И. Анализ производительности мультипрограммных ЭВМ. M.: Финансы и статистика, - 1984. - 159 c.
5. Томашевский В., Жданова E. Имитационное моделирование в среде GPSS. М.: Бестселлер, - 2003. - 416 c.
Введение

Использование аппарата систем массового обслуживания при анализе бизнес-процессов (БП) позволяет решать задачу анализа узких мест и определять среднее количество обслуживающих устройств. Однако задача анализа узких мест мультиагентой модели БП на данный момент не решена [1-3]. Распространенные системы имитационного моделирования (СИМ) БП (Arena; ARIS; GPSS; Pilgrim; AnyLogic; BPsim) не содержат инструментов реинжиниринга и ориентированы на документирование моделей. На основе систем Pilgrim и AnyLogic возможно построение мультиагентных моделей. К достоинствам пакетов AnyLogic и Pilgrim относится использование языка высокого уровня. Только в системе BPsim есть встроенные средства анализа узких мест мультиагентной модели.

Мультиагентная модель строительного холдинга

С применением системы BPsim была разработана имитационная модель (ИМ) строительного холдинга CHINA WANBAO ENGINEERING Corp. (BEIJING XIANGFU.LTD), которая состоит из 128 операций, 90 ресурсов, 11 агентов (задача строительства 11 многоэтажных зданий). Результаты экспериментов модели «как есть» показали, что при моделировании строительства двух и более объектов, возникают перегрузки отдельных цепочек операций, что ведет к увеличению очередей заявок и простою дальнейших работ. Для устранения «узких мест» был проведено совершенствование мультиагентной модели с помощью реинжиниринга и применения процедур свертки / развертки модели [1].

Применение процедур свертки / развертки обеспечило проведение анализа загрузок цепочек операций и построение параллельных веток операций к цепочкам, загрузка которых превышает допустимую норму (возникают очереди). Реинжиниринг операций позволил снять их перегрузку и сократить общее время выполнения. Данные экспериментов исходной модели согласуются со статистикой работой холдинга «Wan Bao». Динамика использования грузовиков показана на рисунке 1.

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

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

Для исследования БП и ОТС предложено использовать подход процессов преобразования ресурсов [2-3], представляющий интеграцию методов имитационного, экспертного, ситуационного и мультиагентного моделирования. Множество элементов модели мультиагентного процесса преобразования ресурсов (МППР) представляет собой набор [2-3]: MPPR={ Goal, Res, Mech, Order, Op, Agent }, где Goal - множество целей модели; Res - множество ресурсов; Mech - множество средств; Order - множество заявок; Op - множество операций модели; Agent - множество агентов модели, содержащих AgentGoal (множество целей агентов) и AgentSolution (база знаний).

В качестве теоретической основы метода анализа узких мест взят операционный анализ вероятностных сетей [4-5]: узкое место создается узлом, у которого коэффици­ент загрузки Uk приближается к единице; узкие места в сети определяют время пре­бывания в сети. , где Uk - коэффициент использования узла; - общее время обслуживания требований узлом k; Т - общее время наблюдения за системой или время моделиро­вания.

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

Разработан метод реинжиниринга модели МППР. В результате проведения эксперимента с моделью МППР формируется статистика, диагностируются узкие места, и принимается решение о свертке / развертке модели. Критерием остановки метода РБП является снижение времени ожидания до допустимых значений по всем блокам модели.

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

Среднее количество работающих устройств определяется согласно [5]:

M = (Z + R)X0 , (1)

где X0 - интенсивность потока требований; Z - среднее время обслуживания требования; R - среднее время ожидания требования.

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

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

Рис. 2. Представление модели строительства в виде многоканальной СМО

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

Рис. 3. Распределение длительностей работ (модели - исходная и субподряд 2)

Из графика видно, что длительность работ уменьшается с применением модели субподряда 2.

1. На основе данных хронометража и привязки к технологическим особенностям строительства разбили все работы на 4 группы и применили экспоненциальный закон распределения длительности интервалов между поступлениями заявок. Входные данные модели были получены в результате ручной обработки экспериментального распределения длительности работ (рис. 3) и приведены в таблице 1 (моделируется ситуация, соответствующая среднему объему работ строительства).

Таблица 1 Входные данные модели

Заявка

Округленная периодич-ность возникновения, дни

Коли-чество заявок, шт.

Средняя длитель-ность обработки заявки, дни

Количество используемой техники для обработки одной заявки, шт.

Грузовики

Краны

Бетономешалки

z1

24

63

12

от 6 до 8

0,25

0,2

z2

23

65

16

от 18 до 22

0,5

0,2

z3

31

46

18

от 12 до 14

0,25

-

z4

69

21

25

от 16 до 18

0,25

0,4

В результате калибровки имитационной модели были получены интенсивности поступления для каждой группы заданий: 0.04, 0.043, 0,03, 0.015.

2. Проведены имитационные эксперименты с моделью, реализованной в системе ИМ AnyLogic. Смоделированы следующие ситуации:

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

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

Модель СМО была реализована в СИМ AnyLogic. В модели генерируются 4 потока заявок (заданий для грузовиков) с разными интенсивностями. Ресурсы (грузовики) имитируются многоканальным устройством с заданной емкостью. Задания требуют определенного количества ресурсов и занимают их на определенное время. Время моделирования - 4 года, единица модельного времени - 1 день. На выходе оценивается загрузка многоканального устройства и среднее время пребывания заявки в системе. Результат прогона модели показан на рис. 4. Как видно из графиков очередей дополнительный канал (субподряд) не подключается. Канал подключается при условии превышения длины очереди к ресурсам более 10.

Рис. 4. Результаты прогона модели в AnyLogic

Увеличивая интенсивность поступления заявок (моделируя ситуации пиковых объемов работ строительства), можно убедиться, что при 50 грузовиках основные каналы не справляются с нагрузкой, и подключается запасной канал. Среднее время выполнения заявки составляет 46 дней.

С другой стороны при увеличении пула ресурсов среднее время нахождения заявки в системе уменьшается до 21,196. Запасной канал не подключается. Загрузка каналов достаточно высокая.

3. Для каждой из рассмотренных ситуаций согласно формуле (1) на основе результатов имитационных экспериментов (таблица 2) было получено среднее количество работающих грузовиков. Расчет производился с учетом следующих особенностей: 1) «общей» интенсивности  (т.к. рассматриваем простейшие потоки); 2) обработки определенного количества ресурсов (здесь предполагаем захват заявкой в среднем 15 ресурсов).

Таблица 2

Ситуация (объем работ)

Интенсивность поступления заявок, X0

Среднее время нахождения заявки,

Z + R

Количество каналов, которое захватывает одна заявка

Среднее

количество работающих каналов, M

Время эксперимента

Средний

0,128

16

15

30,72

23 мин 59 с

Выше среднего

0,200

18

15

54,00

24 мин. 58 с

Большой

0,256

21

15

80,64

25 мин. 49 с

Максимальный

0,324

23

15

111,78

26 мин. 58 с

Результаты имитационных экспериментов модели строительства в виде СМО (реализованной в СИМ AnyLogic) и в виде МППР (реализованной в системе BPsim.MAS) хорошо согласуются. Так, среднее время нахождения заявки (для грузовиков) в мультиагентной модели «субподряд 2» составляет 17.29, а свой парк состоит из 30 грузовиков. Максимальное количество используемых грузовиков в модели «субподряд 2» составляет 106, что также хорошо согласуется с результатами модели СМО (ситуации большой и максимальной загрузки). Таким образом, можно сделать вывод об адекватности модели СМО, в части моделирования загрузки грузовиков.

Данная модель, несмотря на свою компактность и ресурсоемкость, имеет следующие недостатки по сравнению с имитационной моделью МППР:

  1. не позволяет задать технологическую последовательность требований - работ по строительству здания;
  2. не позволяет оценить длительность строительства отдельных объектов;
  3. не имеет возможности оценки экономических характеристик проекта строительства.

Заключение

Применение модели СМО и операционного анализа позволило сократить количество экспериментов с мультиагентной моделью, направленных на определение среднего количества грузовиков. Реинжиниринг мультиагентной модели строительного холдинга позволил уменьшить среднее время ожидания в узлах. Применение метода привело к уменьшению сроков выполнения строительства на 42 % (1,6 года / 580 дней) и повышению загрузки средств по сравнению с вариантом закупки грузовиков, эффект от внедрения составляет 4,6 млрд юаней.

* Работа выполнена в рамках государственного контракта 02.740.11.0512.

[1] ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б. Н. Ельцина»

Рецензенты:

  • Поршнев Сергей Владимирович, д.т.н., профессор, заведующий кафедрой Автоматики и информационных технологий, ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б. Н. Ельцина», г. Екатеринбург.
  • Доросинский Леонид Григорьевич, д.т.н., профессор, заведующий кафедрой Информационных технологий, ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б. Н. Ельцина», г. Екатеринбург.

Библиографическая ссылка

Ван Кай В.В., Аксенов К.А., Аксенова О.П., Киселёва М.В. ИСПОЛЬЗОВАНИЕ АППАРАТА ОПЕРАЦИОННОГО АНАЛИЗА ВЕРОЯТНОСТНЫХ СЕТЕЙ ДЛЯ ОПРЕДЕЛЕНИЯ СРЕДНЕГО КОЛИЧЕСТВА ПРИБОРОВ ОБСЛУЖИВАНИЯ МУЛЬТИАГЕНТНОЙ МОДЕЛИ // Современные проблемы науки и образования. – 2012. – № 3.;
URL: http://www.science-education.ru/ru/article/view?id=6290 (дата обращения: 17.10.2018).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.252