Материал: Экономико-математические методы и модели. Гасилов В.В., Околелова Э.Ю
• средний доход от функционирования системы в единицу времени.
Предметом теории массового обслуживания является установление зависимости между факторами, определяющими функциональные возможности системы массового обслуживания, и эффективностью ее функционирования. В большинстве случаев все параметры, описывающие системы массового обслуживания, являются случайными величинами или функциями, поэтому эти системы относятся к стохастическим системам.
Случайный характер потока заявок (требований), а также, в общем случае, и длительности обслуживания приводит к тому, что в системе массового обслуживания происходит случайный процесс. По характеру случайного процесса, происходящего в системе массового обслуживания (СМО), различают системы марковские и немарковские. В марковских системах входящий поток требований и выходящий поток обслуженных требований (заявок) являются пуассоновскими.
Пуассоновские потоки позволяют легко описать и построить математическую модель системы массового обслуживания. Данные модели имеют достаточно простые решения, поэтому большинство известных приложений теории массового обслуживания используют марковскую схему.
В случае немарковских процессов задачи исследования систем массового обслуживания значительно усложняются и требуют применения статистического моделирования, численных методов с использованием ЭВМ.
Независимо от характера процесса, протекающего в системе массового обслуживания, различают два основных вида СМО:
•системы с отказами, в которых заявка, поступившая в систему в момент, когда все каналы заняты, получает отказ и сразу же покидает очередь;
•системы с ожиданием (очередью), в которых заявка, поступившая в момент, когда все каналы обслуживания заняты, становится в очередь и ждет, пока не освободится один из каналов.
Системы массового обслуживания с ожиданием делятся на системы с ограниченным ожиданием и системы с неограниченным ожиданием.
В системах с ограниченным ожиданием может ограничиваться:
•длина очереди;
•время пребывания в очереди.
В системах с неограниченным ожиданием заявка, стоящая в очереди, ждет обслуживания неограниченно долго, т.е. пока не подойдет очередь.
Все системы массового обслуживания различают по числу каналов обслуживания:
•одноканальные системы;
•многоканальные системы.
Приведенная классификация СМО является условной. На практике чаще всего системы массового обслуживания выступают в качестве смешан-
116
ных систем. Например, заявки ожидают начала обслуживания до определенного момента, после чего система начинает работать как система с отказами.
7.1. Одноканальная модель с пуассоновским входным потоком с экспоненциальным распределением длительности обслуживания
Простейшей одноканальной моделью с вероятностными входным по-
током и процедурой обслуживания является модель, характеризуемая показательным распределением как длительностей интервалов между поступлениями требований, так и длительностей обслуживания. При этом плотность распределения длительностей интервалов между поступлениями требований имеет вид
f1 (t) = λ e−λt , |
(7.1) |
где λ - интенсивность поступления заявок в систему. Плотность распределения длительностей обслуживания:
f2 (t) = µ e−µt |
(7.2) |
где μ - интенсивность обслуживания.
Потоки заявок и обслуживаний простейшие.
Пусть система работает с отказами. Необходимо определить абсолютную и относительную пропускную способность системы.
Представим данную систему массового обслуживания в виде графа (рис.7.1), у которого имеются два состояния:
S0 - канал свободен (ожидание);
S1 - канал занят (идет обслуживание заявки).
λ
S0 |
S1 |
μ
Рис. 7.1. Граф состояний одноканальной СМО с отказами
Обозначим вероятности состояний:
P0(t) - вероятность состояния «канал свободен»; P1(t) - вероятность состояния «канал занят».
При этом выполняется условие P0(t) + P1(t) = 1. Следовательно,
P1(t)=1-P0(t).
Для одноканальной СМО с отказами вероятность P0(t) есть не что иное, как относительная пропускная способность системы q.
Действительно, P0 - вероятность того, что в момент t канал свободен и заявка, пришедшая к моменту t, будет обслужена, следовательно, для данного момента времени t среднее отношение числа обслуженных заявок к числу поступивших также равно P0(t)=q.
117
По истечении большого интервала времени (при t → ∞) достигается стационарный (установившийся) режим:
q = P0 = |
µ |
|
(7.3) |
|
µ + λ . |
||||
|
||||
Зная относительную пропускную способность, легко найти абсолютную. Абсолютная пропускная способность А - среднее число заявок, которое может обслужить система массового обслуживания в единицу времени:
A = λ q = |
λ µ |
(7.4) |
µ + λ . |
Вероятность отказа в обслуживании заявки будет равна вероятности состояния «канал занят»:
Pотк = P1 =1− P0 =1− |
µ |
= |
λ |
|
. |
(7.5) |
|
λ + µ |
λ + |
µ |
|||||
|
|
|
|
Данная величина Ротк может быть интерпретирована как средняя доля необслуженных заявок среди поданных.
Рассмотрим теперь одноканальную СМО с ожиданием.
Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание - простейший поток с интенсивностью λ. Интенсивность потока обслуживания равна μ (т. е. в среднем непрерывно занятый канал будет выдавать μ обслуженных заявок). Длительность обслуживания - случайная величина, подчиненная показательному закону распределения. Поток обслуживаний является простейшим пуассоновским потоком событий. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.
Предположим, что независимо от того, сколько требований поступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более N-требований (заявок), т.е. клиенты, не попавшие в ожидание, вынуждены обслуживаться в другом месте. Наконец, источник, порождающий заявки на обслуживание, имеет неограниченную (бесконечно большую) емкость.
Граф состояний СМО в этом случае имеет вид, показанный на рис. 7.2.
|
λ |
|
λ |
λ |
λ |
λ |
λ |
S0 |
μ |
S1 |
μ |
S2 μ |
μ Sn |
μ |
μ SN |
Рис. 7.2. Граф состояний одноканальной СМО с ожиданием
Состояния СМО имеют следующую интерпретацию: S0 - «канал свободен»;
S1 - «канал занят» (очереди нет);
S2 - «канал занят» (одна заявка стоит в очереди);
118
Sn - «канал занят» (п- 1 заявок стоит в очереди);
SN - «канал занят» (N - 1 заявок стоит в очереди).
Условие стационарности системы выполняется при ρ = |
λ < 1 . |
|
|
µ |
|
Следует отметить, что выполнение условия стационарности ρ = |
λ < 1 для |
|
|
|
µ |
данной СМО не обязательно, поскольку число допускаемых в обслуживающую систему заявок контролируется путем введения ограничения на длину очереди (которая не может превышать N - 1), а не соотношением между ин-
тенсивностями входного потока, т. е. не отношением ρ = λµ .
Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N - 1):
вероятность отказа в обслуживании заявки:
|
|
|
|
|
|
1− |
ρ |
|
|
N |
|
|
|
|
|
|
|
|
|
|
|
ρ |
|
, ρ ≠1, |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
N +1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
P |
= P |
= |
|
1 |
− ρ |
|
|
|
|
|
||
|
|
|
|
|
||||||||
отк |
N |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
, |
ρ =1; |
||
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
(N +1) |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|||
относительная пропускная способность системы:
q =1− Pотк ;
абсолютная пропускная способность: A=q·λ;
среднее число находящихся в системе заявок:
N
LS = ∑n Pn ;
n=0
среднее время пребывания заявки в системе:
WS = λ(1L−SPN ) ;
(7.6)
(7.7)
(7.8)
(7.9)
(7.10)
средняя продолжительность пребывания клиента (заявки) в очереди:
Wq=WS -1/μ; |
(7.11) |
среднее число заявок (клиентов) в очереди (длина очереди): |
|
Lq = λ(1-PN)Wq . |
(7.12) |
Рассмотрим одноканальную СМО с ожиданием без ограничения на вместимость блока ожидания (т. е. N → ∞). Остальные условия функционирования СМО остаются без изменений.
Стационарный режим функционирования данной СМО существует при t → ∞ для любого п = 0, 1, 2, ... и когда λ < μ.
Характеристики одноканальной СМО с ожиданием без ограничения на длину очереди следующие:
• среднее число находящихся в системе клиентов (заявок) на обслуживание:
119
LS = n∑∞ n Pn = 1−ρρ ;
=0
• средняя продолжительность пребывания клиента в системе:
W |
= |
LS |
= |
|
1 |
|
; |
S |
|
λ |
|
[µ (1− ρ)] |
|
||
• среднее число клиентов в очереди на обслуживании:
Lq = LS − λµ = (1ρ−2ρ) ;
• средняя продолжительность пребывания клиента в очереди:
Wq = Lλq = [µ (1ρ− ρ)].
(7.13)
(7.14)
(7.15)
(7.16)
7.2. Многоканальная модель с пуассоновским входным потоком
сэкспоненциальным распределением длительности обслуживания
Вподавляющем большинстве случаев на практике системы массового обслуживания являются многоканальными и, следовательно, модели с п обслуживающими каналами (где п>1) представляют несомненный интерес.
Процесс массового обслуживания, описываемый данной моделью, характеризуется интенсивностью входного потока λ, при этом параллельно может обслуживаться не более п клиентов (заявок).
Средняя продолжительность обслуживания одной заявки равняется 1/μ. Входной и выходной потоки являются пуассоновскими.
Режим функционирования того или иного обслуживающего канала не влияет на режим функционирования других обслуживающих каналов системы, причем длительность процедуры обслуживания каждым из каналов является случайной величиной, подчиненной экспоненциальному закону распределения.
Конечная цель использования п параллельно включенных обслуживающих каналов заключается в повышении (по сравнению с одноканальной системой) скорости обслуживания требований за счет обслуживания одновременно п клиентов.
Граф состояний многоканальной системы массового обслуживания с отказами имеет вид, показанный на рис. 7.3.
|
|
λ |
|
|
λ |
λ |
|
|
λ |
|
|
|
λ |
λ |
|||||||||||
S0 |
|
|
|
S1 |
|
|
|
S2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sn(k |
|
|
|
|
|
|
SN |
||||||
μ |
|
2 μ |
|
|
3 μ |
k μ |
|
+1)μ |
|
n μ |
|
|
|||||||||||||
Рис. 7.3. Граф состояний многоканальной СМО с отказами
120