Материал: Панков Пособие по АСП

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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