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

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

  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;,то отсюда получаем и преобразуем:

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

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

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

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

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

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

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

Для иллюстрации  принципа эксплуатации имитационных моделей  приведем простейший типовой пример.

Рассмотрим  одноканальную систему массового  обслуживания с простейшим входным потоком заявок и интенсивностью А = 3 (заявки в час). Время обслуживания одной заявки с вероятностью 0,5 равно 0,2 ч и с вероятностью 0,5 равно 0,6 ч. Заявки обслуживаются в порядке поступления. Длина очереди и источник заявок не ограничены. Предполагается, что в начальный момент времени канал обслуживания свободен и в очереди нет ни одной заявки.

Для простейшего  входного потока заявок с интенсивностью А = 3 (заявки в час) длительность временного интервала между двумя последовательно  поступившими заявками — случайная величина  ( ), распределенная по экспоненциальному закону с параметром А. Если ук — реализация случайной величины, равномерно распределенной на отрезке [0,1], то реализация  к длительности временного интервала между двумя последовательно поступившими заявками определяется следующим образом:

А так как  по условию с вероятностью 0,5 время  обслуживания одной заявки равно  либо 0,2 ч, либо 0,6 ч,  то реализация времени обслуживания.

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

I.   Действия, связанные с поступлением заявки в систему массового обслуживания:

1)  генерация момента поступления следующей заявки на обслуживание путем определения реализации  к длительности  ( ) временного интервала между двумя последовательно поступившими заявками и прибавлением  к текущему времени моделирования;

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

II.  Действия по окончании обслуживания заявки в системе связаны с проверкой состояния очереди:

1) если очередь  пуста, т.е. в ней нет заявок, то объявляется простой системы;

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

Одноканальная система начинает работать при пустой очереди и свободном канале обслуживания, т.е. ее функционирование начинается с простоя. Время  1 поступления первой заявки на обслуживание моделируется псевдослучайным числом:

Таким образом, в момент времени t = 0 +  1 = 0,31 происходит событие, состоящее в поступлении заявки на обслуживание. Вычисляем время поступления следующей заявки:

Поскольку в  начальный момент времени система  простаивает, то в момент времени t = 0,31 начинается обслуживание первой заявки. Время обслуживания  (0,66655) = 0,6 ч, т.е. время окончания обслуживания равно:

Система объявляется  работающей, а время простоя корректируется:

Следующее по времени  событие связано с поступлением заявки на обслуживание в момент времени t = 0,55 ч. Так как в это время происходит обслуживание первой заявки, то поступившая заявка становится в очередь, длина которой корректируется:

Следующая заявка поступает в момент времени

 

А так как  система все еще обслуживает  первую заявку, то длина очереди  увеличивается: 
Далее определяется время поступления следующей заявки:

А так как  система все еще обслуживает  первую заявку, то длина очереди  увеличивается:

Определим время  поступления следующей заявки:

Полезно отмечать новые события на рисунке по мере их реализации (на рис.3. символ аобозначает поступление заявки, символ Р — время окончания обслуживания заявки).

Рис 3

Следующее событие  наступает в момент времени t=0,91 ч и представляет собой окончание обслуживания первой заявки. А так как очередь не пуста, то начинается обслуживание следующей заявки и корректируется длина очереди:

При этом суммарное  время ожидания обслуживания равно

а время обслуживания второй заявки равно   (0,47764) = 0,2 ч. Таким образом, обслуживание второй заявки завершится в момент времени

t = 0,91 + 0,2 = 1,11 ч.

Процедура повторяется до тех пор, пока не будет промоделирован весь отрезок времени [0, Т] функционирования одноканальной системы массового обслуживания. При этом можно определить оценки основных характеристик этой системы и установить зависимость их качества от величины Т, т.е. от длительности времени моделирования процесса функционирования системы. Так, например: 
а)  доля времени простоя системы (в процентах) равна отношению суммарного времени простоя к величине Т, умноженному на 100; 
б)  среднее время ожидания обслуживания равно отношению суммарного времени ожидания к числу поступивших заявок; 
в)  средняя длина очереди равна отношению т(А)/Т, где т(А) — площадь плоской фигуры А,ограниченной осью времени и ступенчатой линией r = r(t), t   [0, Т], отражающей зависимость длины очереди от времени t.

Алгоритм моделирования  СМО: