Определим основные понятия и термины, используемые в моде­лировании.

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

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

Состояние системы - множество переменных, которые содер­жат всю информацию, необходимую для описания свойств системы в любое время.

Объект - любой элемент или компонент в системе, который должен быть представлен в модели в явном виде (например, обслу­живающее устройство, клиент, машина).

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

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

Событие - мгновенно возникающее изменение состояние сис­темы (например, прибытие нового требования).

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

Список событий - список намеченных будущих событий, упо­рядоченных по времени возникновения, известный также как список будущих событий (СБС).

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

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

Модельное время - неотрицательная возрастающая величина, отражающая течение времени в имитационной модели.

Часы - переменная, отражающая протекание времени модели­рования, называется в примерах ЧАСЫ (CLOCK).

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

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

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

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

В табл. 1.1 представлены интервалы времени между приходами покупателей в магазин и требуемыми временами их обслуживания продавцом, а на рис. 1.3 проведено графическим методом «ручное» моделирование СМО с одним устройством.

С точки зрения объектного подхода имеются динамические объ­екты - требования (ПОКУПАТЕЛИ) и некоторый ресурс - устройст­во обслуживания (статический объект ПРОДАВЕЦ), которое они используют. Если требование претендует на ресурс, а он занят, то оно становится в ОЧЕРЕДЬ к ресурсу. ОЧЕРЕДЬ может быть отдельным объектом или просто списком, связанным с ресурсом. Примем за пра­вило обслуживания - FIFO.

Целью дискретного имитационного моделирования является воспроизведение взаимодействий, в которых участвуют компо­ненты, и изучение поведения и функциональных возможностей исследуемой системы. Для этого выделяются состояния систе­мы и описываются действия, которые переводят ее из одного состояния в другое. Говорят, что система находится в опреде­ленном состоянии, когда все ее компоненты находятся в со­стояниях, совместимых с областью значений, описывающих это состояние характеристик. Таким образом, имитация – это динамический «портрет» состояний системы во времени, т. е. воспроизведение поведения системы во времени.

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

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

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

Взаимосвязь между понятиями событие, действие и процесс представлена на рис. 1.7.

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

Событийный подход

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

Для иллюстрации событийного подхода вновь рассмотрим пример банка с одним кассиром, приведенный ранее. Клиен­ты заходят в банк, после возможного ожидания обслужива­ются кассиром и затем уходят. Состояние системы в этом при­мере определяется состоянием кассира и числом ожидающих обслуживания клиентов. Оно остается неизменным, за исключением моментов, когда клиент прибывает в систему или покида­ет ее. Поэтому событийная модель в данном случае состоит из описания действий, происходящих в момент прибытия и окон­чания обслуживания очередного клиента. Так как изменения состояния системы могут происходить только в эти моменты времени, использование событий «прибытие» и «конец обслу­живания» полностью обеспечивает воспроизведение динамики функционирования системы.

Обсудим сначала логику события «прибытие». Оператор­ная схема этого события имеет следующий вид:

ПЛАНИРОВАНИЕ СЛЕДУЮЩЕГО ПРИБЫТИЯ.

ЕСЛИ КАССИР ЗАНЯТ: ЧИСЛО ОЖИДАЮЩИХ=ЧИСЛО ОЖИДАЮ-

ЩИХ+1; ВОЗВРАТ.

ЕСЛИ КАССИР СВОБОДЕН: ПЕРЕВОД КАССИРА В СОСТОЯНИЕ «ЗА­НЯТ»; ПЛАНИРОВАНИЕ СОБЫТИЯ «ОКОНЧАНИЕ» ОБСЛУЖИВА­НИЯ В МОМЕНТ ВРЕМЕНИ=ТЕКУЩЕЕ ВРЕМЯ+ВРЕМЯ ОБСЛУ­ЖИВАНИЯ; ВОЗВРАТ.

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

Рассмотрим теперь логику обработки события «конец обслу­живания». Операторная схема этого события имеет следующий вид:

ЕСЛИ ЧИСЛО ОЖИДАЮЩИХ БОЛЬШЕ НУЛЯ: ЧИСЛО ОЖИДАЮ­ЩИХ=ЧИСЛО ОЖИДАЮЩИХ-1; ПЛАНИРОВАНИЕ ОКОНЧАНИЯ ОБСЛУЖИВАНИЯ В МОМЕНТ ВРЕМЕНИ, РАВНЫЙ ТЕКУЩЕМУ ВРЕМЕНИ + ВРЕМЯ ОБСЛУЖИВАНИЯ; ВОЗВРАТ.

ЕСЛИ ЧИСЛО ОЖИДАЮЩИХ РАВНО НУЛЮ: ПЕРЕВОД КАССИРА В

СОСТОЯНИЕ «СВОБОДЕН»; ВОЗВРАТ.

Когда кассир заканчивает обслуживание очередного кли­ента, сначала проверяем, есть ли клиенты, ожидающие обслу­живания. Если такие клиенты есть, их число уменьшается на единицу и планируется событие «конец обслуживания» первого из ожидающих клиентов. В противном случае кассир перехо­дит в состояние «свободен».

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

Подход сканирования активностей

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

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

Процессно-ориентированный подход

Многие имитационные модели содержат последовательности компонентов, которые возникают в них по определенной схеме, например очередь, в которой клиенты ожидают обслуживания. Логика возникновения компонентов по требуемой схеме может быть обобщена и задана в одном операторе. Имитационный язык затем транслирует такие операторы в соответствующую последовательность событий, происходящих с компонентами модели. Имитационные языки, включающие операторы для моделирования процесса прохождения элементов через систе­му, обычно называются процессно-ориентированными. Эти опе­раторы определяют последовательность событий, которые ав­томатически выполняются имитационным языком, по мере того как элементы продвигаются через систему. Например, следую­щий набор операторов может быть использован для описания процесса в модели банка:

СОЗДАВАТЬ ПРИБЫВАЮЩИХ КЛИЕНТОВ ЧЕРЕЗ КАЖДЫЕ Т ЕДИНИЦ ВРЕМЕНИ;

ОЖИДАТЬ КАССИРА;

ПРОДВИНУТЬ ВРЕМЯ НА ПРОДОЛЖИТЕЛЬНОСТЬ ОБСЛУЖИВАНИЯ;

ОСВОБОДИТЬ КАССИРА;

УДАЛИТЬ КЛИЕНТА;

Первый оператор генерирует прибывающих в систему кли­ентов через каждые Т единиц имитационного времени. Величи­на Т может быть константой или принимать случайные значе­ния. Оператор «ожидать» определяет, что клиент ожидает до тех пор, пока кассир освободится. Этот тип оператора анало­гичен понятию действия по условию, применяемого в подходе сканирования активностей. Оператор «продвинуть время» мо­делирует тот период времени, в течение которого клиент обслу­живался кассиром. Этот тип оператора аналогичен оператору планирования в событийном подходе. Он помещает в кален­дарь событий метку о том, что обслуживание клиента будет закончено в момент, равный текущему имитационному времени плюс время обслуживания. После завершения обслуживания клиент покидает систему и кассир освобождается. Освобожде­ние кассира позволяет сразу же приступить к обработке како­го-либо ожидающего клиента из оператора «ожидать».

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

Статья посвящена аспектам дискретно-событийного моделирования сетевых компьютерных систем. Отличительной особенностью предлагаемого подхода является принятие во внимание условий высоких нагрузок функционирования сетевых компьютерных систем. В статье выделяются наиболее существенные характеристики сетевых компьютерных систем, которыми являются синхронизация событий и конкуренция за вычислительные ресурсы. Определены отличия предлагаемого подхода от двух известных подходов математического моделирования: методов теории автоматического управления и методов теории сетей и систем массового обслуживания. Рассмотрено идемпотентное (max,+) полукольцо, которое является основной алгебраической структурой, применяемой в рассматриваемом подходе к дискретно-событийному моделированию. Указаны основные алгебраические свойства (max,+) полукольца, именуемого также диоидом. Рассмотрен пример дискретно-событийного моделирования функционирования автоматизированных рабочих мест автоматизированной системы управления контейнерными перевозками на железнодорожном транспорте, функционирующей в условиях высоких нагрузок. Приведены числовые результаты дискретно-событийного моделирования рассматриваемой сетевой компьютерной системы.

дискретно-событийное моделирование

идемпотентное (max

+) полукольцо

1. Бражник А.Н. Имитационное моделирование: возможности GPSS WORLD. – СПб..: Реноме, 2006. – 439 с.

2. Бутакова М.А. Имитационное моделирование процессов возникновения ошибок для оценки надежности программного обеспечения / М.А. Бутакова, С.В. Чубейко // Известия высших учебных заведений. Северо-Кавказский регион. Технические науки. – 2012. – № 5 (168). – C. 29–34.

3. Глухов М.М., Елизаров В.П., Нечаева А.А. Алгебра. Т. 2. – М.: Гелиос АРВ. – 2003. – 416 с.

4. Гуда А.Н. Прогнозирование надежности программного обеспечения на основе модели неоднородного пуассоновского процесса и бутстреп-методов / А.Н. Гуда, С.В. Чубейко // Программные продукты и системы. – 2012. – № 3. – С. 131–135.

5. Котов В.Е. Сети Петри. – М.: Наука, 1984. – 160 с.

6. Маслов В.П. Идемпотентный анализ и его применение в оптимальном управлении / В.П. Маслов, В.Н. Колокольцов. – М.: ФИЗМАТЛИТ. – 1994. – 144 с.

7. Таха Х.А. Введение в исследование операций: пер. с англ. – 7-е изд. – М.: Издательский дом «Вильямс», 2005. – 912 с.

8. Чубейко С.В. Алгоритмы и программное обеспечение для имитационного моделирования сетевых систем на основе (min,+) фильтраций // Современные проблемы науки и образования. – 2013. – № 6; URL: http://www.science-education.ru/113-11545 (дата обращения: 13.01.2014).

9. Baccelli F. Synchronization and linearity: An algebra for discrete event systems / F. Baccelli, Cohen G., G.J. Olsder, J.-P. Quadrat. – Chichester: Wiley, 1992. – 514 p.

10. Cassandras C.G., Lafortune S. Introduction to Discrete Event Systems. Second Edition. – Springer, 2008. – 782 p.

11. Gondran M. Graphs, Dioids and Semirings. New Models and Algorithms / Gondran M., Minoux M. – Springer Science+Business Media, LLC. – 2008. – 384 p.

12. Heidergott B. Max Plus at Work. Modeling and Analysis of Synchronized Systems: A course on Max-Plus Algebra and Its Applications / B. Heidergott, G. Jan Olsder, J. van der Woude. – Princeton University Press, Princeton. – 2006. – 232 p.

13. Wainer G.A. Discrete Event Modeling and Simulation: A Practitioner’s Approach // CRC Press, 2009. – 486 p.

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

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

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

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

В итоге введения к статье следует заметить, что научные исследования в области дискретно-событийного моделирования сейчас достаточно широко развиты в различных направлениях , а также служат как существенное дополнение методов имитационного моделирования систем. Существуют также программные реализации дискретно-событийных систем моделирования, например AnyLogic, SimPy, SimEvents и другие. Однако в рамках данной статьи нас интересует вполне самостоятельное направление дискретно-событийного моделирования с применением алгебраических структур (max,+) подхода , который, на наш взгляд, адекватно отражает поставленную в названии статьи проблему - моделирование высоконагруженных сетевых компьютерных систем.

Применение метода (max,+) алгебры в дискретно-событийном моделировании

Основной структурой в рассматриваемом подходе является (max,+) полукольцо , являющееся числовым множеством (с элементами из множества ¡, включая -∞ и не включая +∞), снабженным операциями «максимума», играющего роль «сложения» и «сложения», играющего роль «умножения». Указанные операции (max,+) в специализированной литературе обозначаются соответственно ⊕ и ⊗ (то есть имеют другое значение в отличие от общепринятых - прямой суммы и прямого произведения матриц), то есть x⊕y = max{x, y}, x⊗y = x + y. Данное (mах,+) полукольцо является идемпотентным , то есть сложение a⊕a = a является идемпотентным, нулем считается ε = -∞, единицей, считается e = 0, которая нейтральна по операции ⊗, а для каждого ненулевого элемента по этой операции имеется обратный элемент. Для обеих операций выполняется коммутативность и ассоциативность, а операция ⊗ дистрибутивна относительно ⊕. Такая алгебраическая структура часто называется диоидом . Аналогичный подход с использованием (min,+) алгебраических структур рассмотрен в работе автора .

Данные свойства указанной алгебраической структуры оказываются существенно полезными для дискретно-событийного моделирования сетевых компьютерных систем с точки зрения оценки и достижения их максимальной производительности. Рассмотрим простой пример дискретно-событийного моделирования автоматизированной системы управления контейнерными перевозками (АСУ КП) на железнодорожном транспорте. В моделируемой системе имеются автоматизированные рабочие места (АРМ) работников АСУ КП на двух железнодорожных станциях:

1) узловой станции Ростов-Товарная;

2) припортовой станции Новороссийск.

Посредством единой сети передачи данных ОАО «РЖД» АРМы АСУ КП работают в сетевом режиме и между ними передается информация, сопутствующая технологическому процессу обработки документов. Будем рассматривать 4 события (конечно, в существенно упрощенной форме), соответствующие работе оператора АРМ АСУ КП:

1) подготовка пакета исходной документации с телеграмм-натурным листом поезда;

2) ввод и передача информации в сетевом режиме АРМ АСУ КП на первой станции;

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

4) подтверждение и корректировка принятых данных в АРМ АСУ КП на второй станции.

Естественным образом устанавливается порядок синхронизации событий, так, например, подтверждение и корректировка данных могут произойти не ранее, чем данные вообще будут получены, а подготовка документации может происходить не ранее прибытия поезда с контейнерами. Для того, чтобы не ограничиваться одним направлением и подчиняться общим принципам моделирования систем на рисунке показаны технологические процессы с АРМ АСУ КП на станциях и названы в целом «подготовкой данных». Различное время технологических операций на станциях, а также приема и передачи в разных направлениях может быть обусловлено различной производительностью АРМов, различным опытом операторов и другими аналогичными причинами. Приемы моделирования различных событий, связанных с интенсивной нагрузкой информационных систем и программного обеспечения, рассматривались ранее в работах автора .

Для дальнейшей определенности и конкретных расчетов положим, что время подготовки документации на железнодорожные платформы с контейнерами в АРМ АСУ КП занимает у оператора xA = 3 минуты; ввод данных на каждый вагон формируемого поезда из 60 вагонов на станции Ростов-Товарная составляет yBA = 12 минут при отправке телеграмм-натурного листа на станцию Новороссийск. Время, затрачиваемое на формирование принятого на припортовой станции Новороссийск телеграмм-натурного листа контейнерного поезда, составляет xB = 2 минуты, а время, затрачиваемое на согласование корректировок со станцией Ростов-на-Дону и внесение их в АРМ АСУ КП на станции Новороссийск, составляет yBA = 10 минут.

Графическая иллюстрация упрощенного технологического процесса контейнерной перевозки между станциями StA и StB

Поставим цели моделирования, состоящие в нахождении максимальных нагрузок на сетевые компьютерные АРМы АСУ КП при выполнении следующих ограничений:

1) нормативы времени на технологические операции, выполняемые операторами АРМ АСУ КП на станциях, являются максимально допустимыми;

2) операторы АРМов приступают к формированию пакетов поездной документации только после прибытия поезда, однако между технологическими операциями задержек не возникает;

3) интенсивность обработки документаций в АРМах должна учитывать максимальную производительность контейнерных перевозок, а следовательно, и максимально возможное количество поездов, курсирующих на участке между StA и StB.

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

а очередной прибывший пакет поездных документов будет обработан не ранее, чем будут переданы предыдущие корректировки на станцию St A со станции St B:

где t B (0) - начальный момент времени отправления корректировок со станции St B , который можно принять t B (0) = 0, Δ - некоторая временная задержка в технологических процессах на транспорте. Выражения (1) и (2) можно записать в более общем виде:

Приняв Δ = 0 и подставив значения из примера из (3) и (4), получим, что максимальная задержка отправления составит

а для станции StB аналогично (1)-(4)

Так же как и в работе , для k = 0, 1, 2, ... по (5) и (6) рассчитаем последовательность t A = {0, 10, 22, 32, ...} и t B = {0, 12, 22, 34, ...}.

Заметим, что выражения (3)-(4) и соответствующие им выражения (5)-(6) с подставленными в них максимальными значениями временных интервалов x A , x B , y AB , y BA можно переписать в общем виде следующим образом.

Пусть имеется n станций t i , t = 1, ..., n, а времена, необходимые на технологические операции по перемещению контейнерной документации между i-й и j-й станциями, обозначим z ij , тогда (5) и (6) имеет вид

Выражение (7) можно сравнить с выражением для линейной рекуррентной последовательности следующим образом:

(8)

В (9) применим метод (max, +)-алгебры, а для того, чтобы подчеркнуть дальнейшую возможность использования методов линейной алгебры в (max, +)-алгебре, выражение (9) запишем как

(10)

Также, по аналогии с линейной алгеброй, выражение (10) можно записать в матричном виде:

где e - (max, +) - операции; Z - матрица, содержащая коэффициенты преобразований.

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

таким образом,

Заключение

Дискретно-событийное моделирование с использованием (max,+) подхода является достаточно эффективной технологией моделирования систем с синхронизацией событий, Эта технология является пригодной для моделирования сетевых компьютерных систем, в частности АРМов и АСУ, применяемых на железнодорожном транспорте для определения режимов их функционирования в условиях максимальных нагрузок.

Работа выполнена при финансовой поддержке РФФИ, проекты 13-01-00325-а, 13-01-00637-а.

Рецензенты:

Павлов И.В., д.ф.-м.н., профессор, заведующий кафедрой высшей математики Ростовского государственного строительного университета, г. Ростов-на-Дону;

Чернов А.В., д.т.н., профессор, заведующий кафедрой прикладной математики и вычислительной техники Ростовского государственного строительного университета, г. Ростов-на-Дону.

Работа поступила в редакцию 21.05.2014.

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

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

Термин “дискретно-событийно моделирование” исторически закрепился за моделированием систем обслуживания потоков объектов некоторой природы: клиентов банка, автомобилей на заправочной станции, телефонных вызовов, пациентов в поликлиниках и т.п. Именно такие системы называются системами массового обслуживания.

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

В основе данного вида моделирования лежит концепция заявок (транзактов, entities), ресурсов и потоковых диаграмм (flowcharts), определяющих потоки заявок и использование ресурсов. Этот подход восходит к Джеффри Гордону, который в 1960х придумал и развил GPSS и реализовал её, работая в IBM. Заявки (транзакты в GPSS) – это пассивные объекты, представляющие людей, детали, документы, задачи, сообщения и т.п. Они путешествуют через flowchart, стоя в очередях, обрабатываясь, захватывая и освобождая ресурсы, разделяясь, соединяясь и т.д. Типичная потоковая диаграмма показана на рис. 1 в терминах продукта Arena. Вообще, существует около сотни коммерческих инструментов, так или иначе поддерживающих подобный стиль моделирования; некоторые общего назначения, большинство нацелено на определённые ниши: обслуживание, бизнес-процессы, производство, логистика и т.д. Их пользовательские интерфейсы могут существенно различаться из-за специализации, но за ними непременно стоит более или менее одинаковый дискретно-событийный “движок” (engine), который “гоняет” заявки через блоки.

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

В настоящее время делается большое количество исследований и разработок в различных областях под лозунгом многоагентные системы, например, в искусственном интеллекте, теории сложных систем, теории игр и т.д. Общепризнанного определения “что такое агент” не существует; люди до сих пор спорят о том, какими же качествами должен обладать объект, чтобы “заслужить” называться агентом: инициативность и реактивность, ориентация в пространстве, способность обучаться, общаться, “интеллект” и т.д. Таким обзором, существует множество определений понятия агента. Общим во всех этих определениях является то, что агент – это некоторая сущность, которая обладает активностью, автономным поведением, может принимать решения в соответствии с некоторым набором правил, может взаимодействовать с окружением и другими агентами, а также может изменяться (эволюционировать). Многоагентные модели используются для исследования децентрализованных систем, динамика функционирования которых определяется не глобальными правилами и законами, а наоборот, эти глобальные правила и законы являются результатом индивидуальной активности членов группы. Цель агентных моделей – получить представление об этих глобальных правилах, общем поведении системы, исходя из предположений об индивидуальном, частном поведении ее отдельных активных объектов и взаимодействии этих объектов в системе. Таким образом, агентное моделирование называют также моделированием снизу вверх. Пример агентной системы изображен на рис. 2.

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