Имитационное моделирование систем массового обслуживания

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

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

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

Опишем кратко основное назначение блоков моделирующего алгоритма.

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

Блок 2 – это программный модуль для моделирования входного (однородного или неоднородного) потока заявок с помощью доступных вероятностных характеристик – законов распределения. Пусть поток заявок на входе описывается с помощью последовательностей { } или { }, j = 1, 2, … , где – моменты поступления заявок, - промежутки времени между моментами поступления, – набор признаков, характеризующих конкретную заявку (ее приоритет, параметры обслуживания и др.). Предполагается, что все независимы и одинаково распределены по закону распределения, который мы обозначим через Если - функция распределения непрерывной случайной величины X, то моделирование реализаций { } этой величины можно осуществить на основе метода обратной функции [1, 2 ]

Рис.2.4. Логическая схема моделирующего алгоритма СМО.

r_i = F_X(x_i) = (4.1)

где (x) – функция вероятности, – реализация равномерно распределенной в интервале (0,1) случайной величины R. Так как - монотонно возрастающая функция, реализацию можно определить как Например, для экспоненциального закона распределения имеем откуда следует моделирующая формула (моделирующий алгоритм) Величины и одинаково распределены, поэтому более экономна формула

При моделировании дискретного распределения, в том числе и целочисленного, заданного последовательностью { }, моделирующим алгоритмом служит правило

£ r < « x = x_k, k = 1, … , n. (4.2)

При моделировании нормального закона распределения с параметрами ( ) можно, вместо преобразования (4.1), воспользоваться центральной предельной теоремой теории вероятностей, согласно которой величина при достаточно большом N распределена по нормальному закону. В приложениях ограничиваются значениями N=12, тогда эта сумма имеет среднее значение, равное 6, и единичную дисперсию. Таким образом, величины и имеют одно и то же распределение, поэтому реализацию x можно определить с помощью моделирующего алгоритма

x = m_x + s_x( . (4.3)

Различным наборам будут соответствовать фиксированные реализации имеющие нормальный закон распределения с параметрами и Это распределение обычно обозначается через

Последовательность { } можно получить с помощью программных датчиков псевдослучайных чисел, основанных на мультипликативных алгоритмах типа [1, 2]

a) X_i+1 º X_i (modM),

б) X_i+1 º X_i + m (modM). (4.4)

Их действие основано на свойстве конгруэнтности чисел: числа a и b называются конгруэнтными (или сравнимыми) по модулю M, если их разность кратна M. Соответствующим подбором параметров и можно достичь высокой точности сгенерированных с помощью алгоритмов (4.4) псевдослучайных чисел

Блок 3 устанавливает «текущее» время в системе: при нулевом начальном значении переменной Т оператор Т: = Т+q фиксирует моменты поступления очередной (j–й) заявки в систему, что изменяет значение счетчика N на единицу, другими словами, N: = N + 1 (начальное значение показания счетчика N равно нулю).

Блок 4 реализует правило остановки. Остановка процесса моделирования может быть осуществлена либо по ограничению на время моделирования T ≤ , где - максимально допустимое время моделирования (или работы системы), либо по ограничению на число прогонов модели, т. е. по максимальному количеству заявок (транзактов), обслуживаемых системой. Второе правило является более универсальным, так как оно позволяет контролировать точность результатов моделирования. Например, если в качестве критерия интерпретации результатов моделирования выступает средняя величина показателя эффективности системы (или ее функционирования), то исходным соотношением, связывающим число реализаций N, точность оценивания и доверительную вероятность P₀ является условие

P_r{| - m| < e} = P₀. (4.5)

Для того чтобы сделать эту связь явной, достаточно воспользоваться соотношением

- e / (s_x/ ) £ ( - m) /(s_x/ ) £ e / (s_x/ ) (4.6)

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

U_a £ e / (s_x/ ) « N^* ³ s_x² U_a² / e ². (4.7)

В этой формуле величину заменяют эмпирической дисперсией .

Блок 5 устанавливает, должна ли поступившая заявка непосредственно обслуживаться одним из свободных каналов, или она должна ждать в очереди. Пусть переменная величина TOS характеризует ближайший момент освобождения одного из обслуживающих каналов. Ее можно определить с помощью условия

TOS = (4.8)

где t_oc.k – момент освобождения k – го канала, k = 1, … , m. Если выполняется условие

Т ³ TOS, (4.9)

Следовательно, в момент поступления очередной заявки один из каналов, номер которого устанавливается в соответствии с правилом (4.8), уже свободен и может обслужить эту заявку, тогда управление передается блоку 7. Если же условие (4.9) не выполняется, то заявка должна ждать в очереди, что осуществляется в блоке 6: определяется на основе закона распределения _ож(t) допустимое время ожидания , которое затем сравнивается с величиной TOS – Т. При выполнении условия

³ TOS – Т (4.10)

заявка будет обслужена после ожидания, поэтому для нее определяется фактическое время ожидания

(4.11)

после чего управление вновь передается блоку 7. Если же условие (4.10) не имеет места, данная заявка получает отказ, что фиксируется в счетчике отказанных заявок с помощью оператора N_отл: = N_отл + 1, после чего управление передается блоку 2.

Блок 7 моделирует процесс обслуживания в соответствии с набором признаков для данной заявки. Для нее определяется время обслуживания на основе закона распределения моменты начала ( ) и конца ( ) обслуживания, время пребывания в системе которое определяется соотношением

= + , (4.12)

и осуществляется возврат к блоку 2. Если заявка обслуживается без ожидания в очереди, то для нее = 0, а в случае ожидания эта величина равна фактическому времени ожидания, т. е. Для отказанных в обслуживании заявок время обслуживания равно нулю, т. е. , следовательно, = . В случае необходимости фиксируется номер обслуживающего канала, другие статистические данные.

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

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

(4.13)

построение доверительных интервалов, оценку соответствия между эмпирическим и теоретическим распределениями, например, по критерию – Пирсона

(4.14)

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

Планирование машинного