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

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

В составе СМО можно выделить следующие основные части (рис.3.1):

1. Входящий поток заявок;

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

3. Узел обслуживания - система приборов, обслуживающих заявки (устройства, каналы);

4. Выходящий поток заявок, т.е. заявок, которые обслужены, или тех, которым в обслуживании было отказано.

 

Рис. 3.1. Принципиальная схема системы массового обслуживания.

Система с накопителем называется СМО с ожиданием, без накопителя - СМО с отказами.

В зависимости от емкости накопителя различают СМО с конечной и бесконечной очередью.

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

1. Системы с отказами, в которых заявка, поступившая в момент, когда все каналы заняты, покидает СМО;

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

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

Важнейшие бесприоритетные дисциплины обслуживания:

· FIFO (First In, First Out — первым пришел, первым ушел): если заявка первой пришла в очередь, то она первой уйдет на обслуживание;

· LIFO (Last In, First Out — последним пришел, первым ушел): если заявка последней пришла в очередь, то она первой уйдет на обслуживание (пример — патроны в рожке автомата);

· SF (Short Forward — короткие вперед): в первую очередь обслуживаются те заявки из очереди, которые имеют меньшее время обслуживания.

· RANDOM (случайный выбор).

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

В системах с ожиданием накопитель в общем случае может иметь сложную структуру.

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

Основные показатели функционирования СМО могут быть вычислены в зависимости от типа СМО

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

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

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

где τ_j — интервал между событиями (случайная величина);

t _{с i} — момент совершения i -го события (отсчитывается от t = 0);

T _н — время наблюдения.

Рис. 3.2. Пример потока событий

Простейший поток определяется тремя условиями:

1. Стационарностью – среднее число требований в единицу времени постоянно;

2. Отсутствием последействия – число требований, поступающих в некоторый промежуток времени, не зависит от числа требований, поступивших в предыдущем промежутке;

3. Ординарностью – вероятность поступления более одного требования в малый промежуток времени есть малая величина более высокого порядка, чем , т.е. в очень малый промежуток времени поступает не более одного требования.

Типичный пример такого потока событий приведен на рис.3.3. На оси времени маркерами отмечены моменты времени, когда наступают события. Заметим, что визуально нельзя обнаружить закономерность появления событий, интервал времени между соседними событиями различен, а в единицу времени наступает различное количество событий. Так за 1-ую единицу времени наступает три события, за 6-ую - два события, за 7-ую -четыре события. Т.е. количество событий, наступающих в единицу времени является случайной величиной. Однако, если сосчитать N - количество событий наступивших за достаточно длинный интервал времени T _н (например, за 1 час, T _н =60 мин.) и вычислить среднее количество событий в минуту N / T _н., то это среднее количество будет приблизительно одинаковым, независимо от того с какого момента времени отсчитывать интервал времени.

Рис. 3.3. Пример простейшего потока событий

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

(3.1)

где - параметр распределения.

Как известно, математическое ожидание случайной величины M(X) распределенной по показательному закону; равно , а дисперсия D(X) равна 1/λ².

M(X)=1/λ; D(X)=1/λ²

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

Для непрерывного распределения, зная плотность распределения f (x),можно найти функцию распределения F (x)по формуле

. (3.2)

Случайная величина, следующая экспоненциальному распределению, имеет функцию распределения

(3.3)

Знание функции плотности и функции распределения позволит вычислить - вероятность того, что промежуток времени между двумя событиями в потоке не меньше a и меньше b. Эта вероятность равна определенному интегралу от плотности, взятому в пределах от a до b,

(3.4)

Если и , то

(3.5)

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

(3.6)

где λ>0 – параметр распределения.

Формула (3.6) позволяет вычислить вероятность того, что в течение одной минуты произойдет ровно k событий. Основные описательные статистики для распределения Пуассона, выражаются следующими соотношениями (3.7):

M(X)=λ; D(X)=λ (3.7)

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

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

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

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

В данной работе будем полагать, что интенсивность потока входящих заявок равна , для описания этого потока справедливы формулы (3.1)- (3.7).

Поскольку поток обслуженных требований также является простейшим, то он имеет свою интенсивность равную m. Для описания потока обслуженных требований также справедливы формулы (3.1)- (3.7), с заменой на m. Например, интервал времени между событиями в этом потоке (время обслуживания одного требования) есть случайная величина, распределенная по показательному закону:

(3.8)

где m - интенсивность обслуживания. При этом среднее время обслуживания одного требования равно

(3.9)

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

(3.10)

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

Судить о результатах работы СМО можно по следующим показателям:

· относительная пропускная способность системы;

· абсолютная пропускная способность системы;

· вероятность отказа клиенту в обслуживании;

· вероятность занятости всех каналов;

· среднее количество занятых каналов;

· вероятность простоя каждого канала;

· вероятность простоя всей системы;

· среднее количество заявок, стоящих в очереди;

· среднее время ожидания заявки в очереди;

· среднее время обслуживания заявки;

· среднее время нахождения заявки в системе;

· среднее время занятости каждого канала;

· вероятность занятости каждого из каналов.

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

МНОГОКАНАЛЬНАЯ СМО С ОТКАЗАМИ

Если в момент поступления требования нет свободных обслуживающих каналов (т.е. заняты все каналы, так как в системе уже находится n требований), то требование покидает систему не обслуженным. Все состояния системы приведены на рис. 3.4.

Рис. 3.4. Граф состояний для многоканальной СМО с отказами

S₀ – все каналы свободны;

S₁ – один канал занят, остальные свободны;

S₂ – два канала заняты, остальные свободны;

S_k – k каналов занято, остальные (n-k) свободны;

S_n – все n каналов заняты.

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

Вероятность наличия в системе k требований:

(3.11)

где - вероятность отсутствия требований в системе,

- приведенная интенсивность потока.

(3.12)

Вероятность потери требования (отказа) соответствует вероятности наличия в системе n требований, когда все n каналов заняты

(3.13)

Относительная пропускная способность

. (3.14)

Абсолютная пропускная способность

(3.15)

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

. (3.16)

ОДНОКАНАЛЬНАЯ СМО С ОЖИДАНИЕМ

Граф состояний одноканальной СМО с ожиданием приводится на рис. 3.5.

Рис. 3.5. Граф состояний для одноканальной СМО с ожиданием

S₀ – все каналы свободны;

S₁ – один канал занят, очереди нет;

S₂ –канал занят, одна заявка в очереди;

…

S_k – канал занят, k-1 заявка в очереди;

S_m+1 – канал занят, m заявок в очереди.

Вероятности состояний

(3.17)

Характеристики системы:

(3.18)

Среднее число заявок, находящихся в очереди

(3.19)

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

(3.20)

Среднее время пребывания заявки в очереди и в системе соответственно

(3.21)

ОДНОКАНАЛЬНАЯ СМО С НЕОГРАНИЧЕННЫМ ВРЕМЕНЕМ ОЖИДАНИЯ.

Вероятности состояний СМО с неограниченным числом мест в очереди можно получить предельным переходом (при ) из формул (3.8) - (3.11). Это возможно, если Тогда

(3.22)

При отсутствии ограничений по длине очереди каждая заявка, пришедшая в систему будет обслужена, поэтому Среднее число заявок в очереди и в системе соответственно при

(3.23)

Среднее время пребывания заявки в очереди и в системе

(3.24)

МНОГОКАНАЛЬНАЯ СМО С ОЖИДАНИЕМ

Рассмотрим n -канальную СМО с ожиданием (интенсивность потока заявок l; интенсивность обслуживания m, число мест в очереди m). Состояния системы (рис. 3.4) следующие:

Рис. 3.6. Граф состояний для многоканальной СМО с ожиданиями

S₀ - все каналы свободны;

S₁ – занят один канал, остальные свободны;

….

S_n – занято n каналов;

S_n+1 – занято n каналов, одна заявка в очереди;

S_n+m – занято n каналов, m заявок в очереди.

Вероятности состояний:

(3.25)

Показатели системы:

(3.26)

Среднее число занятых каналов и заявок в очереди соответственно

(3.27)

Обозначив получим

(3.28)

МНОГОКАНАЛЬНАЯ СМО С НЕОГРАНИЧЕННОЙ ОЧЕРЕДЬЮ

Снимем ограничение на длину очереди в задаче предыдущего раздела.

Вероятности состояний получим предельным переходом (при ); это возможно при x <1, т.е. при .

Получим выражения предельных вероятностей состояний:

Для такой системы в формулах (3.25) - (3.27) устремим , получим

ОПРЕДЕЛЕНИЕ ПОКАЗАТЕЛЕЙ СМО

П р и м е р 1. Имеем одну телефонную линию. Заявка-вызов, пришедшая в момент, когда линия занята, получает отказ. Интенсивность потока вызовов - l = 0,8 вызовов в минуту, средняя продолжительность разговора - t_обсл = 1,5 мин. Найти вероятности состояний, абсолютную пропускную способность А, относительную пропускную способность q и вероятность отказа r _отк.

Р е ш е н и е. Интенсивность обслуживания для одноканальной СМО с отказами m = 1/ t_обс =1/1,5 = 0,667.

Вероятность состояний согласно формулам (3.11) и (3.12)

q = 0,455» 45%; p _отк = 0,545; А = 0,8 × 0,455= 0,364.

Итак, относительная пропускная способность линии 45% вызовов, 55% вызовов получают отказ, абсолютная пропускная способность 0,364 разговоров в минуту.

П р и м е р 2. Пусть телефонных линий будет три (n =3); l = 0,8; m = 0,667. Найти вероятность состояний, абсолютную и относительную пропускную способность, вероятность отказа и среднее число занятых каналов.

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

· с помощью готовых формул (3.15 - 3.16);

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

Р е ш е н и е. Состояния системы следующие (рис. 3.4):

S₀ - все линии свободны;

S₁ - занята одна линия;

S₂ - занято две линии;

S₃ - занято три линии.

Вероятности состояний и характеристики многоканальной СМО с отказами вычислим по формулам (3.11 - 3.16):

р₁ = 0,374; р₂ = 0,224; р₃ = 0,090; р _отк = р₃ = 0,090;

q = 0,910; A = 0,728; k = 1,2 × 0,910 = 1,09.

Вычисление среднего числа занятых каналов приведено на рис.3.7-3.8. Ячейка С20 содержит искомое значение, которое совпало со значением, вычисленным по формуле (3.16).

Рис.3.7 Решение примера 2 в MS Excel в режиме отображения данных.

Рис.3.8 Решение примера 2 в MS Excel в режиме отображения формул.

П р и м е р 3. СМО представляет собой экскаватор, работающий на уступе в карьере. К нему на погрузку идет поток автосамосвалов с интенсивностью l = 1 машина в минуту. Процесс погрузки продолжается в среднем 1,25 мин. Площадка на уступе ограничивает количество машин в очереди до трех. Определить вероятность отказа р _отк ; относительную (q) и абсолютную (А) пропускную способности; среднее число машин, ожидающих погрузки ; среднее число машин, находящихся на уступе ; среднее время ожидания в очереди ; среднее время пребывания в системе .

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

· с помощью готовых формул (3.19 - 3.20);

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

Р е ш е н и е. Состояния системы (рис.3.5) следующие:

S₀ - экскаватор свободен, очереди нет;

S₁ - экскаватор занят, очереди нет;

S₂ - в очереди один автосамосвал;

S₃ - в очереди два автосамосвала;

S₄ - в очереди три автосамосвала.

Вероятности состояний:

(k =1, 2, 3, 4), где .

Характеристики системы вычислим по формулам (3.17-3.21).

Так как m = 1/1,25 = 0,8, соответственно r =1/0,8=1,25, то

p₀ = 0,122; p₄ = 0,297; р_отк = p₄ = 0,297;

q = 0,703; A = 0,703;

= 1,56; = 2,44; = 1,56 мин; = 2,44.

Вычисление средних количеств машин, стоящих в очереди, находящихся на обслуживании и находящихся в системе, приведено на рис.3.9-3.10. Ячейка С23 содержит искомое значение среднего количества машин стоящих в очереди. Ячейка С37 содержит искомое среднее количество загружаемых машин. Ячейка С50 содержит искомое значение - среднее количество машин, находящихся на обслуживании. Все эти значения совпали со значениями, вычисленными по формулам (3.17-3.21).

Рис.3.9 Решение примера 3 в MS Excel в режиме отображения данных(начало).

Рис.3.10 Решение примера 3 в MS Excel в режиме отображения данных(окончание).

Рис.3.11 Решение примера 3 в MS Excel в режиме отображения формул.

П р и м е р 4. На обогатительную фабрику прибывают составы с рудой с интенсивностью l = 2 состава в час. Среднее время обработки состава t_обсл = 0,4 ч. Очередь на разгрузку предполагается неограниченной. Найти среднюю длину очереди, среднее число составов в системе, среднее время ожидания и среднее время пребывания в системе.

Р е ш е н и е. Так как = 2× 0,4 = 0,8, т.е. < 1, то вероятности состояний и характеристики системы можно получить из формул (3.13 - 3.15). Таким образом, = 3,2 состава; = 1,6 час; = 2 ч.

П р и м е р 5. На уступе в карьере работает два экскаватора с одинаковой производительностью (n = 2). Поток автосамосвалов, прибывающих на уступ для погрузки, имеет интенсивность l = 2 машины в минуту; среднее время погрузки t_обсл = 2 мин. Площадка на уступе может вместить очередь не более трех машин (m = 3). Найти вероятность отказа, относительную и абсолютную пропускную способность, среднее число занятых экскаваторов и машин в очереди, среднее время ожидания и пребывания машин на уступе.

Р е ш е н и е. Состояния в системе следующие (рис. 3.4):

S₀ - система свободна;

S₁ - занят погрузкой один экскаватор;

S₂ - оба экскаватора заняты, очереди нет;

S₃ - оба экскаватора заняты, в очереди одна машина;.

S₄ - в очереди два автосамосвала;

S₅ - в очереди три автосамосвала.

Вероятности состояний и характеристики многоканальной СМО с ожиданием вычислим по формулам (3.16 - 3.20).

Итак, n = 2, m = 3; l = 2; m = 0,5; = 4; x = / n = 2.

Соответственно:

p₀ = 0,008; р_отк = 0,512; q = 0,488; A = 0,976;

= 2,18; = 1,952; = 1,09 мин; = 2,07.

РАСЧЕТ ОПТИМАЛЬНЫХ ПАРАМЕТРОВ СМО

П р и м е р. Некоторое предприятие, ведущее свой бизнес по телефону, имеет собственную АТС, которая имеет несколько каналов связи с городской АТС. Любой запрос на выход на номера городской АТС поступает на местную АТС, а затем, в случае наличия свободной линии (канала), абонент соединяется с городской АТС. Когда все каналы заняты, абонент получает отказ в соединении, и в этом случае фирма несет потери. Затраты на эксплуатацию канала равны Ск у.е. (условных единиц). Экономические потери от неудовлетворения 1% требований на соединение с абонентом равны Со у.е. (условных единиц).

Определить оптимальное количество линий связи для предприятия, если Ск =100 у.е., а Со =10 у.е. Данные по мониторингу запросов на соединение за единицу времени (в течение одной минуты) приведены в табл. 3.2, а по продолжительности разговора по телефону (хронометраж) - в табл. 3.3.

Таблица 3.2

Число запросов k
Число наблюдений

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

Таблица 3.3

Продолжительность разговора	Число разговоров
От	До
0,0	0,5
0,5	1,0
1,0	1,5
1,5	2,0
2,0	2,5
2,5	3,0
3,0	3,5
3,5	4,0
4,0	4,5
4,5	5,0
5,0	5,5
6,0	6,5
6,5	7,0
7,0	7,5