7. Теория массового обслуживания
Предмет, цель и задачи теории массового обслуживания
Во многих областях экономики, финансов, производства и быта важную роль играют системы специального вида, реализующие многократное выполнение однотипных задач. Подобные системы называют системами массового обслуживания (СМО). В качестве примеров СМО в финансово-экономической сфере можно привести системы, представляющие собой банки различных типов (коммерческие, инвестиционные, ипотечные, инновационные, сберегательные), страховые организации (государственные, акционерные общества, компании, фирмы, ассоциации, кооперативы), налоговые инспекции, аудиторские службы, различные системы связи (в том числе телефонные станции), погрузочно-разгрузочные комплексы (порты, товарные станции), автозаправочные станции, различные предприятия и организации сферы обслуживания (магазины, справочные бюро, парикмахерские, билетные кассы, пункты по обмену валюты, ремонтные мастерские, больницы). Такие системы как компьютерные сети, системы сбора, хранения и обработки информации также могут рассматриваться как своеобразные СМО.
Каждая СМО включает в свою структуру некоторое число обслуживающих устройств, которые называют каналами (приборами, линиями) обслуживания. Роль каналов могут играть различные приборы, лица, выполняющие те или иные операции (кассиры, операторы, продавцы), линии связи и т.д.
Системы массового обслуживания могут быть одноканальными или многоканальными.
необслуженными. Схема СМО изображена на рис. 1.1.
Рис. 1.1
Таким образом, во всякой СМО можно выделить следующие основные элементы:
1) входящий поток заявок;
2) очередь;
3) каналы обслуживания;
4) выходящий поток обслуженных заявок.
Потоком событий (в данном случае заявок) называют последовательность событий, наступающих одно за другим в какие-то заранее неизвестные, случайные моменты времени ([5], с. 68).
Каждая СМО в зависимости от своих параметров: характера потока заявок, числа каналов обслуживания и их производительности, а также от правил организации работы обладает определенной эффективностью функционирования (пропускной способностью), позволяющей ей более или менее успешно справляться с потоком заявок.
Предметом изучения теории массового обслуживания является СМО.
Цель теории массового обслуживания — выработка рекомендаций по рациональному построению СМО, рациональной организации их работы и регулированию потока заявок для обеспечения высокой эффективности функционирования СМО.
Для достижения этой цели ставятся задачи теории массового обслуживания, состоящие в установлении зависимостей эффективности функционирования СМО от ее организации (параметров): характера потока заявок, числа каналов и их производительности и правил работы СМО).
В качестве характеристик эффективности функционирования СМО можно выбрать три основные группы (обычно средних) показателей:
1. Показатели эффективности использования СМО:
1.1. Абсолютная пропускная способность СМО — среднее число заявок, которое сможет обслужить СМО в единицу времени.
1.2. Относительная пропускная способность СМО — отношение среднего числа заявок, обслуживаемых СМО в единицу времени, к среднему числу поступивших заявок за это же время.
1.3. Средняя продолжительность периода занятости СМО.
1.4. Коэффициент использования СМО — средняя доля времени, в течение которого СМО занята обслуживанием заявок, и т.п.
2. Показатели качества обслуживания заявок:
2.1. Среднее время ожидания заявки в очереди.
2.2. Среднее время пребывания заявки в СМО.
2.3. Вероятность отказа заявке в обслуживании без ожидания.
2.4. Вероятность того, что поступившая заявка немедленно будет принята к обслуживанию.
2.5. Закон распределения времени ожидания заявки в очереди.
2.6. Закон распределения времени пребывания заявки в СМО.
2.7. Среднее число заявок, находящихся в очереди.
2.8. Среднее число заявок, находящихся в СМО, и т.п.
3. Показатели эффективности функционирования пары "СМО — потребитель", где под "потребителем" понимают всю совокупность заявок или некий их источник (например, средний доход, приносимый СМО в единицу времени и т.п.) '
Отметим, что третья группа показателей оказывается полезной в тех случаях, когда некоторый доход, получаемый от обслуживания заявок и затраты на обслуживание измеряются в одних и тех же единицах. Эти показатели обычно носят вполне конкретный характер и определяются спецификой СМО, обслуживаемых заявок и дисциплиной обслуживания.
Случайный характер потока заявок и длительности их обслуживания порождает в СМО случайный процесс.
Случайный процесс, протекающий в СМО, называется марковским (или процессом без последействия), если вероятность любого состояния СМО в будущем зависит только от ее состояния в настоящем и не зависит от ее состояний в прошлом.
Этот процесс назван "марковским" по имени математика А.А. Маркова, впервые исследовавшего эти процессы.
Поэтому для решения задач теории массового обслуживания необходимо этот случайный процесс изучить, т.е. построить и проанализировать его математическую модель.
Математическое изучение функционирования СМО значительно упрощается, если протекающий в ней случайный процесс является марковским. В этом случае работа СМО сравнительно легко описывается с помощью аппарата конечных систем обыкновенных линейных дифференциальных уравнений первого порядка, а в предельном режиме (при достаточно длительном функционировании СМО) — с помощью аппарата конечных систем линейных алгебраических уравнений, и в результате удается выразить в явном виде основные характеристики эффективности функционирования СМО через параметры СМО, потока заявок и дисциплины работы СМО.
Чтобы случайный процесс был марковским, необходимо и достаточно, чтобы все потоки событий, под воздействием которых происходят переходы системы из состояния в состояние, были пуассоновскими. В СМО потоками событий являются потоки заявок, потоки "обслуживании" заявок и т. д. Если СМО такова, что хотя бы один из ее потоков не является пуассоновским, то характеристики ее эффективности все же могут быть приближенно оценены с помощью марковской теории массового обслуживания. При этом, чем сложнее СМО, чем больше в ней каналов обслуживания — тем точнее оказываются приближенные формулы, полученные при предположении выполнимости в СМО марковских условий. Полезность марковских моделей мотивируется и тем, что во многих случаях для обоснованных рекомендаций по практическому управлению СМО совсем не требуется знаний точных ее характеристик, а вполне достаточно иметь в своем распоряжении ИХ; приближенные значения.
В зависимости от характера потоков СМО можно разделить на марковские и немарковские.
Под марковской СМО будем понимать систему, в которой все потоки событий, переводящие ее из состояния в состояние, пуассоновские. Если хотя бы один из потоков не является пу-ассоновским, то СМО будет называться немарковской.
Элементы теории марковских случайных процессов.
Марковские процессы с непрерывным временем.
В
марковских процессах с непрерывным
временем некоторая система S
с конечным или счётным числом состояний
в случайные моменты времени переходит
из одного состояния в другое. Вероятность
(
)
перехода из состояния
в состояние
за время
не зависит от момента времени переходаt,
а зависит только от
(
)=
+
(
)
,
;
тогда
=1-
+
(
)
= 1+
+
(
),
где
(
)
– бесконечно малая величина,
-
интенсивность
перехода,
=
-
.
Марковский
процесс с непрерывным временем можно
задать с помощью помеченного графа.
Узлы графа – состояния системы; если
0,
то рядом с дугой (i,j
) пишется интенсивность
.
Пример графа приведён на рис. 1.
рис. 1.
Обозначим
через
(t)
событие, состоящее в том, что в момент
времени t
система S
будет находиться в состоянии
,
(t)
– вероятность события
(t).
События
,
(t),…,
(t)
образуют полную группу событий. Тогда,
по формуле полной вероятности, получаем
=
(t)
=
=
(1+
)
(t)
+
(t)
+
(
)
=
(t)+
(t)
+
(
),
откуда
.
Переходя
к пределу при
0,
получаем систему дифференциальных
уравнений Колмогорова-Чепмена для
вероятностей состояний
=
(t)
, j=1,2,…,n
. (2.1)
Полученная
линейная система (2.1) может быть решена
с помощью методов, изучаемых в курсе
“Дифференциальные уравнения”. Для
решения системы надо задать начальное
распределение вероятностей
(0)
= (
)
(T
– знак транспонирования вектор-столбца)
.
Если
существует предельное распределение
вероятностей
(t)
= (
)
при
t
(а
оно заведомо существует для эргодических
процессов, для которых существует t
такое, что все
0), то из (2.1) получаем систему линейных
уравнений для предельных вероятностей
состояний, то есть для вероятностей
состояний в установившемся режиме,
когда
(t)
уже не зависит от начального распределения
(0).
Обозначим
=
.
Приt
.
Переходя в (2.1) к пределу приt
, воспользовавшись тем, что
=
-
и добавив условие, чтобы сумма вероятностей
равнялась единице, получаем системуn+1
линейных уравнений для предельных
вероятностей состояний
:
(2.2)
В
левой части j-го
уравнения системы (2.2) (j=1,…,n)
столько членов, сколько дуг помеченного
графа марковского процесса инцидентно
вершине
.
При этом, если дуга направленаиз
,
то соответствующий член имеет знак “
- “ , если же дуга направлена
в
,
то слагаемое имеет знак “ + “ .
Интенсивности в каждом слагаемом
умножаются на вероятность состояния,
из
которого исходит дуга.
Пример 2.1. Запишем систему линейных уравнений для предельных вероятностей состояний процесса, заданного графом, изображённом на рис. 2.1.
Далее рассмотрим так называемый процесс размножения и гибели, поскольку именно он используется в анализе марковских СМО. Процесс размножения и гибели – это марковский случайный процесс, граф состояний которого имеет вид:
S2 Sk Sn
21
32
…
k,k-1
Система уравнений (2.2) для предельных вероятностей состояний примет вид:
1,0
p1
-
0,1
p0
=
0
0,1
p0
-
1,0
p1
+
2,1
p2
-
1,2
p1
= 0
1,2
p1
-
2,1
p2
+
3,2
p3
-
2,3
p2
= 0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
k-1,k
pk-1
-
k,k-1
pk
+
k+1,kpk+1
-
k,k+1
pk
=0 (2.3)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
n-1,n
pn-1
-
n,n-1
pn
= 0
p1 + p2 + … +pn =1
Учитывая, что сумма первых двух слагаемых, подчёркнутых в (2.3), равна нулю, получаем
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Вероятность
находится из условияp1
+
p2
+ … +pn
=1:
+
+
+…+
=
1,откуда
=
(
+
+
+…+
)-1.
В итоге получили
=
,k
= 1,2,…,n
, (2.4)
где
=
(
+
+
+…+
)-1.