Экзамен 2021 / Панков Пособие по АСП

Операции в системах массового обслуживания выполняются приборами.

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

Операции, выполняемые приборами, называют ещё операциями обслуживания требований.

Приборов в системе массового обслуживания конечное или счётное множество.

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

многоканальной (многолинейной).

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

(конечный накопитель) и бесконечной (бесконечный накопитель).

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

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

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

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

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

дисциплиной обслуживания.

51

В большинстве моделей принята дисциплина «первый пришёл – первый обслужен» - это прямой порядок обслуживания (возможны и инверсный, и случайный порядки).

Рассмотрим функционирование простейших систем массового обслуживания.

1). Одноканальная система с ожиданием.

Графически ее можно изобразить следующим образом:

где a – поток требований на обслуживание, b – поток обслуженных требований,

-источник требований,

-накопитель,

- обслуживающий прибор.

Из источника требование поступает в накопитель, затем, если прибор свободен, то требование обслуживается, иначе требование остаётся в накопителе, становясь в конец очереди.

Пример такой системы - приём экзамена одним экзаменатором. 2). Система с конечным накопителем.

где с – поток потерянных требований.

В системе может находиться N требований (в накопителе может находиться N 1 требование).

Если в накопителе N 1 место уже занято, то очередное требование теряется. Самостоятельно приведите пример такой системы.

3.Система с потерями или отказами.

Это вариант системы 2, в которой N 1. Ожидание здесь не допускается, так как нет накопителя.

Пример такой системы – поток вызовов на телефонный номер.

52

Для классификации систем массового обслуживания используется символика, предложенная в середине 50-х годов XX века Д. Кендаллом. Систему обслуживания кодируют символами:

G1 / G2 / n/ m/ Q*,

где G1 обозначает входящий поток требований (поток с соответствующим распределением интервалов между моментами поступления требований); G2 - распределение времени обслуживания; n - число обслуживающих приборов, m - максимальная длина очереди или емкость накопителя (может быть m=∞:, если m=0 - это система с отказами, 0<m<∞ - система с конечным накопителем), вместо A / B / n / ∞ часто пишут A / B / n; Q* - вводится для описания системы массового обслуживания с приоритетами и для однородного потока требований не рассматривается.

Итак, буквы на первом и втором месте обозначают входящий поток требований и распределение времени обслуживания. Причем, буква М означает, что поток пуассоновский, а время обслуживания распределено по экспоненциальному закону; Ek — эрланговский, т.е. такой, у которого времена между поступлениями требований или время обслуживания распределены по закону Эрланга; Н — гиперэрланговский, в котором времена между поступлениями требований распределены по гиперэрланговскому закону; D — детерминированный (время обслуживания постоянно) и G — произвольный (произвольное распределение). Иногда используется обозначение GI, означающее произвольный стационарный поток.

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

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

Конкретной моделью системы массового обслуживания, описываемой Марковским процессом, является одноканальная система массового обслуживания

M / M / 1 / ∞ или M / M / 1.

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

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

n - число каналов (приборов) в систему массового обслуживания;

λ - интенсивность поступления в систему массового обслуживания заявок;

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

m - число мест в очереди;

prej=pотк - вероятность отказа в обслуживании поступившей в систему массового обслуживания заявки (вероятность потери заявки, требования, т.е. того, что заявка покинет систему массового обслуживания необслуженной);

Q = pser =pобс - вероятность обслуживания поступившей в систему массового обслуживания заявки (относительная пропускная способность системы массового обслуживания, т.е. средняя доля пришедших заявок, обслуживаемых системой); при этом

Q = pser =pобс = 1 - prej;

А - среднее число заявок, обслуживаемых в системе массового обслуживания в единицу времени (абсолютная пропускная способность

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

А = λQ;

LQS=LСМО - среднее число заявок, находящихся в системе массового обслуживания;

nb n З - среднее число каналов в системе массового обслуживания, занятых обслуживанием заявок. В то же время это Lmt=Lобс - среднее число заявок, обслуживаемых системой массового обслуживания за единицу времени:

nb Lmt

Величина nb определяется как математическое ожидание случайного числа занятых обслуживанием каналов:

n m

nb k pk n pn i

k 1 i 1

где pk - вероятность системы находиться в Sk состоянии;

Kb=KЗ = nb - коэффициент занятости каналов; n

twait=tож - среднее время ожидания (обслуживания) заявки в очереди,

1 = - интенсивность потока ухода заявок из очереди.

twait

LQ=Lоч - среднее число заявок в очереди (если очередь есть); определяется как математическое ожидание случайной величины m - числа заявок, состоящих в очереди

m

LQ i pn i

i 1

где pn+i - вероятность нахождения в очереди i заявок;

TQS tQS =TСМО = t СМО - среднее время пребывания заявки в системе массового обслуживания;

TQ tQ t оч. - среднее время пребывания заявки в очереди (если есть

очередь); Для открытых систем массового обслуживания справедливы соотношения

54

TQ tQ LQ

называемые формулами Литтла и применимые только для стационарных потоков заявок и обслуживания.

Рассмотрим некоторые конкретные типы систем массового обслуживания. При этом будет предполагаться, что плотность распределения промежутка времени между двумя последовательными событиями в системе массового обслуживания имеет показательное распределение, а все потоки являются простейшими, т.е. G1 = М, G2 = М.

Одноканальная СМО с отказами

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

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

1

Taverage Tcp .

В символике Кендалла данная система может быть записана как M / M / 1 / 0. Система массового обслуживания имеет два состояния: S0 - канал свободен, S1 - канал занят обслуживанием заявки. Размеченный граф состояний такой

системы массового обслуживания представлен на рисунке:

Система дифференциальных уравнений Колмогорова для такой системы массового обслуживания имеет вид:

55

где p0(t) и p1(t) - вероятности нахождения системы массового обслуживания в состояниях S0 и S1 соответственно. Уравнения для предельных вероятностей p0 и p1 получим, приравнивая нулю производные в первых двух уравнениях системы. В результате получим:

Вероятность p0 по своему смыслу есть вероятность обслуживания заявки pser, т.к. канал является свободным, а вероятность p1 по своему смыслу является вероятностью отказа в обслуживании поступающей в систему массового обслуживания заявки prej, т.к. канал занят обслуживанием предыдущей заявки. Остальные характеристики системы массового обслуживания найдём, рассмотрев конкретный пример.

Пример. Секретарю директора завода поступает в среднем 1,2 телефонных вызовов в минуту. Средняя продолжительность разговора составляет 2 минуты. Найдем основные характеристики системы массового обслуживания и оценим эффективность её работы.

По условию λ = 1,2, 2 = 1/µ, откуда ρ = λ / µ = 2,4. По полученным выше формулам находим pser и prej:

1

pser p0 1 0,294,

prej p1 1 0,706.

Таким образом, обслуживается лишь 29,4% звонков, что нельзя считать удовлетворительным.

Почему p0 Q? В самом деле, p0 есть вероятность того, что заявка будет принята к обслуживанию (система находится в состоянии S0, т.е. канал свободен). Всего в единицу времени приходит в среднем заявок и из них обслуживается p0 заявок. Тогда доля обслуживаемых заявок по отношению ко всему потоку заявок определяется величиной, которая и равна относительной пропускной способности

Q p0 p0 .

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

A p0 pser 1 0,353,

56

т.е. в среднем обслуживается 0,35 звонка в минуту. Очевидно, что при наличии только одного телефонного номера система массового обслуживания будет плохо справляться с потоком заявок.

Многоканальная система с отказами (задача Эрланга).

Здесь мы рассмотрим одну из первых по времени, «классических» задач теории массового обслуживания; эта задача возникла из практических нужд телефонии и была решена в 1909 г. датским инженеромматематиком А.К. Эрлангом. Задача ставится так: имеется п каналов (линий связи), на которые поступает поток заявок с интенсивностью . Поток обслуживаний каждого канала имеет интенсивность . Найти предельные вероятности состояний системы и показатели ее эффективности.

Система массового обслуживания имеет следующие состояния (нумеруем их по числу заявок, находящихся в системе): S0, S1..., Sn, где Sk - состояние системы, когда в ней находится к заявок, т.е. занято k каналов.

Граф состояний системы массового обслуживания соответствует процессу гибели и размножения с конечным числом состояний (при g=n, λi = λ, µi = (i+1)µ)

В символике Кендалла данная система может быть записана как M / M / n / 0. Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсивностью . Интенсивность же потока обслуживаний, переводящих систему из любого правого состояния в соседнее левое, постоянно меняется в зависимости от состояния. Действительно, если система массового обслуживания находится в состоянии S2 (два канала заняты), то она может перейти в состояние S1 (один канал занят), когда закончит обслуживание либо первый, либо второй канал, т. е. суммарная интенсивность их потоков обслуживаний будет 2 . Аналогично суммарный поток обслуживаний, переводящий системe массового обслуживания из состояния S3 (три канала заняты) в S2, будет иметь

интенсивность 3µ, т.е. может освободиться любой из трех каналов, и т. д.

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

из соответствующего раздела, учитывая, что . Тогда

57

k

p p ,k 1,n.

k k! 0

Эти формулы называются формулами Эрланга - основателя теории массового обслуживания.

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

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

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

Осталось только найти среднее число занятых каналов nb . Эту величину можно было бы найти «впрямую», как математическое ожидание дискретной случайной величины с возможными значениями 0,1,..., п и вероятностями этих значений p0 , p1 ,... , pп . Однако среднее число занятых каналов можно найти проще, если учесть, что абсолютная пропускная способность A системы есть не что иное, как интенсивность потока обслуженных системой заявок (в единицу времени). Так как каждый занятый канал обслуживает в среднем заявок (в единицу времени), то среднее число занятых каналов

Пример. Найдем оптимальное число телефонных номеров на предприятии, если заявки на переговоры поступают с интенсивностью 1,2 заявки в минуту, а средняя продолжительность разговора по телефону составляет Taverage = 2

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

По условию λ = 1,2 мин-1, µ = 1/2 мин-1, откуда ρ = λ / µ = 2,4. Оптимальное число каналов n неизвестно. Используя выведенные выше формулы найдём характеристики системы массового обслуживания при различных значениях n и заполним таблицу:

58

Оптимальным числом телефонных номеров можно считать n = 6, когда выполняется 97,6% заявок. При этом за каждую минуту обслуживается в среднем 1,171 заявки. Для решения 2-го и 3-го пунктов задачи воспользуемся формулой из теоремы Хинчина для пуассоновского процесса:

P 3 2 1,2 3 2 e 1,2 3 0,049 2!

P 3 2 P 3 0 P 3 1 P 3 2 0,175

В данной задаче проглядывает некоторый намек на оптимизацию. В самом деле, содержание каждого канала в единицу времени обходится в какую-то сумму. Вместе с тем, каждая обслуженная заявка приносит какой-то доход (если речь идет о системе массового обслуживания, для которых этот доход можно оценить). Умножая этот доход на среднее число заявок А, обслуживаемых в единицу времени, мы получим средний доход от систем массового обслуживания в единицу времени. Естественно, при увеличении числа каналов этот доход растет, но растут и расходы, связанные с содержанием каналов. Что перевесит - увеличение доходов или расходов? Это зависит от условий операции, т. е. от «платы за обслуживание заявки» и от стоимости содержания канала. Зная эти величины, можно найти оптимальное число каналов, наиболее экономически эффективное.

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

Всистеме массового обслуживания с ограниченной очередью число мест m

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

Всимволике Кендалла данная система выглядит как M / M / 1 / m. Состояния системы массового обслуживания представляются следующим

образом:

S0 - канал обслуживания свободен,

59

S1 - канал обслуживания занят, но очереди нет,

S2 - канал обслуживания занят, в очереди одна заявка,

…

Sk+1 - канал обслуживания занят, в очереди k заявок,

…

Sm+1 - канал обслуживания занят, все т мест в очереди заняты.

Для получения необходимых формул можно воспользоваться тем обстоятельством, что система массового обслуживания на рисунке является частным случаем процесса гибели и размножения с конечным числом состояний, если в последнем принять g = m+1, λi = λ, µi = µ.

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

из соответствующего раздела, учитывая, что . Тогда:

i 1

pk k p0,k 1,m 1.

При m=0 (очереди нет) мы получим те же формулы, как и для одноканальной системы массового обслуживания с отказами M / M / 1 / 0, а при ρ = 1 эти же формулы принимают вид

1

p0 pk m 2,k 1,m 1.

Поступившая в систему массового обслуживания заявка получает отказ в обслуживании, если система массового обслуживания находится в состоянии Sm+1, т.е. вероятность отказа в обслуживании заявки равна

prej m 1 p0 .

Относительная пропускная способность системы массового обслуживания

равна

Q = pser = 1 - prej = 1 –ρm+1p0,

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

A = λQ = λ (1 –ρm+1p0).

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

m

LQ i p1 i 1 и может быть записано в виде

i 1

При ρ = 1 формула принимают вид:

m m 1

LQ | 1 2 m 2 .

60