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

Система массового обслуживания (СМО) — система, которая производит обслуживание поступающих в неё требований. Обслуживание требований в СМО производится обслуживающими приборами. Классическая СМО содержит от одного до бесконечного числа приборов. В зависимости от наличия возможности ожидания поступающими требованиями начала обслуживания СМО подразделяются на

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

Выбор требования из очереди на обслуживание производится с помощью так называемой дисциплины обслуживания. Их примерами являются FCFS/FIFO (пришедший первым обслуживается первым), LCFS/LIFO(пришедший последним обслуживается первым), random  (англ.)(случайный выбор). В системах с ожиданием накопитель в общем случае может иметь сложную структуру.

Основные понятие  СМО

Требование (заявка) — запрос на обслуживание.

Входящий поток  требований — совокупность требований, поступающих в СМО.

Время обслуживания — период времени, в течение которого обслуживается требование.

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

 

 

 

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

Рис. 7.20

Имеется семь дорог. Необходимо перевезти груз из А в Д. Пропускная способность каждого канала известна. Какова пропускная способность сети и каким путем должен следовать поток? Решить эту задачу можно с помощью теоремы о максимальном потоке, которую мы рассматривали ранее (рис. 7.20).  
Ко второму классу относятся случайные вероятные потоки, в которых время поступления требования не определено, число требований непредсказуемо. Решением таких задач и занимается теория массового обслуживания.  
В общем случае система массового обслуживания может быть представлена на рис. 7.21.

Рис. 7.21

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

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

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

 

 

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

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

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

Рис. 1

Основными элементами СМО являются:

1. входной поток заявок;
2. очередь;
3. каналы обслуживания;
4. выходной поток заявок (обслуженные заявки).

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

По числу каналов n все СМО разделяются на одноканальные (n= 1) и многоканальные (n >1). Многоканальные СМО могут быть как однородными (по каналам), так и разнородными (по продолжительности обслуживания заявок).  
По дисциплине обслуживания различаются три класса СМО.

1. СМО с отказами (нулевое ожидание или явные потери). «Отказная» заявка вновь поступает в систему, чтобы ее обслужили (например, вызов абонента через АТС).
2. СМО с ожиданием (неограниченное ожидание или очередь). При занятости всех каналов заявка поступает в очередь и в конце концов будет выполнена (торговля, сферы бытового и медицинского обслуживания).
3. СМО смешанного типа (ограниченное ожидание). Имеется ограничение на длину очереди (сервис по обслуживанию автомобилей). Другой вид ограниченного ожидания — ограничение на время пребывания заявки в СМО (ПВО, особые условия обслуживания в банке).

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

Многоканальная СМО с ожиданием и ограничением на длину очереди

Основные понятия и схема

Рассмотрим многоканальную СМО (n ? 1) с ожиданием, т. е. заявка, поступившая в СМО в момент времени, когда все каналы заняты, в отличие от СМО с отказами, не покидает систему необслуженной, а становится в очередь и ожидает обслуживания. Следует отметить, что большинство обслуживающих фирм и учреждений устроены как раз по такому принципу. Пусть максимальное число мест в очереди равно т ? 1, т. е. в очереди могут ожидать своего обслуживания не более т заявок. Поэтому заявка, пришедшая на вход в СМО в момент, когда в очереди уже находятся т заявок, получает отказ и покидает систему. Иными словами, «заполнение» СМО заявками из входного потока идет в два этапа: сначала происходит загрузка каналов обслуживания, затем заполняется очередь. Нумерация состояний системы в этом случае имеет следующий вид: от состояния s0 (в СМО нет заявок и все каналы свободны) до состояния sn (в СМО n заявок и все каналы заняты) очереди нет; от состояния sn+1 (в СМО n + 1 заявка, все каналы заняты и одна заявка находится в очереди) до состояния sn + m(все каналы заняты и все т мест в очереди заняты заявками) происходит заполнение очереди.  
Граф состояний СМО показан на рис. 2. Переход системы из состояния sk в состояние sk+1слева направо (k = 0, 1,..., n + т - 1) происходит под воздействием одного и того же входного потока заявок интенсивности  , следовательно, плотности вероятности перехода из состояния в состояние слева направо одинаковы и равны  .

рис. 2.

Переход системы  из состояния в состояние справа налево происходит с разными плотностями  вероятностей внутри двух циклов состояний, отмеченных выше. Если заявка продолжает оставаться в очереди (состояние sk, n+1?k?n+т), т. е. все каналы заняты, то эти переходы имеют плотность вероятности, равную n  (перемещение системы из состояния в состояние обусловлено общей работой n каналов). Если система находится в состоянии, когда занято k каналов (1 ? k ? n ), то переход ее в левое состояние обусловлен потоком, представляющим собой сумму k потоков обслуживании (общей работой k каналов); в таком случае плотность вероятности перехода равна k  .  
Следует отметить, что система не может «перескакивать» через промежуточное состояние, а переходит из состояния в состояние последовательно: либо слева направо, либо справа налево по графу состояний.

Основные соотношения

Предельные  вероятности р0, р1,..., рn, рn+1, ..., рn+т соответствующих состояний СМО удовлетворяют системе линейных однородных алгебраических уравнений, которая получается из системы дифференциальных уравнений Колмогорова путем, аналогичным описанному выше. Эта система имеет вид:

К этой системе  уравнений необходимо добавить нормировочное условие

Введем величину  = р/n =  /(n  ) -  показатель нагрузки на один канал. Решение системы уравнений выражается, как и в случае СМО с отказами, через вероятность простоя системы (или вероятность того, что все каналы свободны) р0:

Второе слагаемое  в правой части этого равенства  является суммой т членов геометрической прогрессии с первым членом   изнаменателем  , т. е. формула для р0упрощается:

Остальные предельные вероятности состояний имеют  вид, аналогичный формулам:

Характеристики СМО 
Вероятность отказа (заявка, поступившая в момент, когда заняты все n каналов и все т мест в очереди) есть вероятность того, что СМО находится в состоянии sn+m, откуда получаем:

Так как события  отказа заявки и приема ее в СМО  являются противоположными, то вероятность приема заявки в СМО равна вероятности psys и относительной пропускной способности системы:

Отсюда получаем формулу для абсолютной пропускной способности:

Так как каждый занятый канал обслуживает в  среднем ц заявок в единицу  времени, то среднее число заявок, находящихся под обслуживанием (или среднее число занятых каналов) подсчитывается по формуле:

Для вычисления среднего числа заявок  line, находящихся в очереди, рассмотрим дискретную случайную величину Nline, — число заявок в очереди. Закон распределенияNline имеет вид:

Nline	0	1	2	…	т
Р	Ps	Рп+1	Рп + 2	…	Рп + т

Здесь

,

поскольку событие, состоящее в том, что в очереди  нет ни одной заявки, является объединением событий, состоящих в том, что  СМО находится в одном из состояний s0,s1..., sn. Так как  lineявляется математическим ожиданием М случайной величины Nline;,то отсюда получаем и преобразуем:

Сумма в последнем  равенстве имеет выражение в  виде компактной формулы как при  (формула суммирования), так и при   (сумма отрезка натурального ряда чисел). Соответственно мы получаем окончательное выражение для среднего числа заявок в очереди:

Среднее число  заявок, находящихся в системе, равно  сумме средних чисел обслуживаемых  заявок и заявок, находящихся в  очереди: 

Для средних  величин времени обслуживания заявки, времени ожидания заявки в очереди и времени пребывания заявки в системе имеем, соответственно, следующие формулы (формулы Литтла):

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

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

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