ТЕХНОЛОГИЯ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

Б. Г. Ослин (Томск)
 

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

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

Работу любой СМО можно представить как процесс ее перехода из одного состояния в другое в последовательные моменты времени t0, t1, ..., ti,…, когда в СМО происходят события, предусмотренные дисциплиной обслуживания. Иначе процесс функционирования СМО можно представить как совокупность некоторого множества отдельных элементарных процессов, длительность каждого из которых определена некоторым заданным законом. Такие элементарные процессы далее будем называть локальными процессами. Моменты окончания локальных процессов и есть моменты наступления тех основных событий, которые изменяют состояния системы.

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

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

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

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

Универсальным методом исследования СМО является имитационное моделирование, т. е. написание компьютерной программы, имитирующей процесс функционирования системы, и проведение экспериментов на этой программе с целью получения статистических оценок характеристик моделируемой системы. Существует достаточно много различных технологий, приемов и методов имитационного моделирования.

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

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

-        количество последовательностей локальных процессов K;

-        модельное время t. В процессе моделирования эта переменная будет последовательно принимать значения t0, t1, ..., ti,…, моментов наступления основных событий;

-        вектор состояния S. В качестве компонент этого вектора выбираются такие переменные, значения которыХ однозначно определяют состояние системы в любой момент времени ее работы. Этих переменных должно быть достаточно для того, чтобы по их значениям до наступления любого события в системе можно было бы вычислить их новые значения после наступления события. Количество их не имеет большого значения. Их должно быть столько, сколько удобно для написания имитационной модели и подсчета результатов моделирования4

-        вектор событий Т с компонентами ti, i=0,1,...,K. Каждая компонента этого вектора соответствует одной из последовательностей локальных процессов. Если в момент t система находится в состоянии S и при этом состоянии происходил процесс в i-й последовательности локальных процессов, то компонента ti равна моменту окончания этого процесса. Если же локального процесса в i-й последовательности нет, то компонента получает некоторое большое значение BigC, заведомо превышающее интервал моделирования;

-        индекс события m. Эта переменная в каждый момент модельного времени принимает значение номера той компоненты вектора событий, которая имеет минимальное значение;

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

-        параметр критерия окончания эксперимента. Например, это может быть длительность интервала моделирования, или количество изменения состояния системы за время эксперимента, или, наконец, точность, с которой необходимо вычислить характеристики системы;

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

-        переменные для подсчета характеристик моделируемой системы.

 

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

Сначала выполняется обращение к процедуре ввода исходных данных, входящей в состав программы эксперимента. В этой процедуре организуется ввод параметров СМО, значения K, исходного числа датчика случайных чисел, начального значения модельного времени t и значений компонент вектора состояния, определяющих состояние системы до начала моделирования. Затем в процедуре формируется вектор событий, соответствующий начальному состоянию системы. Для этого, если необходимо, моделируются длительности локальных процессов, которые должны происходить при начальном состоянии, полученные значения суммируются со значением t и результаты присваиваются соответствующим компонентам вектора событий. Таким образом вычисляются моменты наступления тех основных событий, которые могут изменить состояние системы. Остальным компонентам присваивается значение BigC.

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

Далее необходимо ввести значения параметра критерия окончания эксперимента и присвоить начальные значения переменным, которые необходимы для обработки результатов моделирования.

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

После того, как сформировано новое состояние системы и скорректирован вектор событий, ищется минимальная компонента вектора событий. Найденное значение присваивается модельному времени t, а номер минимальной компоненты – индексу события m. При этом определяется, до какого момента времени система будет находиться в сформированном состоянии и какое событие изменит это состояние на новое.

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

Данная структура программы может быть легко реализована на любом из универсальных языков программирования.