Системы и сети массового обслуживания

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

Работа любой СМО заключается в обслуживании поступающего на нее потока требований, или заявок. Заявками могут быть заказы на производство изделий, задачи, решаемые в вычислительной системе, клиенты в банках, грузы, поступающие на транспортировку, и так далее. Заявки поступают на систему одна за другой в некоторые, вообще говоря, случайные моменты времени. Обслуживание поступившей заявки продолжается какое-то время, после чего система освобождается для обслуживания очередной заявки [1]. Обобщенная схема СМО изображена на рисунке 1.

Рисунок 1 – Обобщенная схема СМО.

Основными компонентами СМО являются следующие.

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

2) Выходящий поток заявок – поток заявок, покидающих систему.

3) Система обслуживания состоит из накопителя и одного или нескольких каналов. Каналы предназначены для обслуживания заявок. Накопители предназначены для моделирования очереди, в которой заявки ожидают обслуживания. Каждая заявка должна поступить в один из каналов, чтобы пройти обслуживание. Может оказаться, что заявкам придется ожидать, пока каналы освободятся. В этом случае заявки находятся в накопителе, образуя очередь. Будем полагать, что переход заявки из накопителя в канал происходит мгновенно.

В практике моделирования систем, имеющих более сложные структурные связи и алгоритмы, для формализации используются не отдельные обслуживающие системы, а структурные схемы СМО, образуемые композицией многих каналов и накопителей – сети массового обслуживания (СеМО). Сеть массового обслуживания представляет собой совокупность конечного числа обслуживающих узлов (источников заявок, накопителей и каналов), в которой циркулируют заявки, переходящие в соответствии с маршрутной матрицей из одного узла в другой. Так если каналы обслуживающей системы соединены параллельно, то имеет место многоканальное обслуживание, а если параллельные композиции каналов соединены последовательно, то имеет место многофазное обслуживание. Связи между элементами таких схем изображают в виде стрелок, отражающих направление движения заявок [2]. Например, на рисунке 2 представлена структурная схема многофазной СМО.

	И

H_i - накопитель i-ой фазы, =1¸n,

K_ij - j-ый канал i-ой фазы, j=1¸r_i.

И – некоторый источник заявок, реализующий входящий поток

Рисунок 2 – Структурная схема многофазной СМО.

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

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

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

3) Дисциплина выбора из очереди – совокупность правил, в соответствии, с которыми заявка выбирается из очереди. Выделим следующие дисциплины: FIFO (первым пришел - первым обслужен), LIFO (последним пришел - первым обслужен), случайный выбор из очереди, выбор заявки по минимальному времени, оставшемуся до отказа. Также при этом может учитываться приоритет заявки, определяющий преимущественное право на обслуживание [3].

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

Таблица 1 – Параметры и переменные модели СМО

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

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

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