Теория массового обслуживания

Теория массового обслуживания, или теория очередей (англ. queueing theory), — раздел теории вероятностей, целью исследований которого является рациональный выбор структуры системы обслуживания и процесса обслуживания на основе изучения потоков требований на обслуживание, поступающих в систему и выходящих из неё, длительности ожидания и длины очередей. В теории массового обслуживания используются методы теории вероятностей и математической статистики.

История

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

Первые задачи теории массового обслуживания (ТМО) были рассмотрены сотрудником Копенгагенской телефонной компании, ученым Агнером Эрлангом, в период между 1908 и 1922 годами. Стояла задача упорядочить работу телефонной станции и заранее рассчитать качество обслуживания потребителей в зависимости от числа используемых устройств.

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

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

Поток

Однородный поток

Основная статья: Поток однородных событий

Поток заявок однороден, если:

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

Поток без последействия

Поток без последействия, если число событий любого интервала времени ($t$, $t+x$) не зависит от числа событий на любом другом не пересекающемся с нашим ($t$, $t+x$) интервале времени.

Стационарный поток

Поток заявок стационарен, если вероятность появления n событий на интервале времени ($t$, $t+x$) не зависит от времени $t$, а зависит только от длины $x$ этого участка.

Простейший поток

Однородный стационарный поток без последействий является простейшим, потоком Пуассона.

Число $n$ событий такого потока, выпадающих на интервал длины $x$, распределено по Закону Пуассона:

$P(n,x)={\frac {(\lambda x)^{n}e^{-\lambda x}}{n!}}.$

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

Нормальный поток

Cтационарный поток без последействий, для которого интервалы между событиями распределены по нормальному закону, называется нормальным потоком: $f(t)={\frac {1}{{\sqrt {2\pi }}\sigma _{t}}}\exp {-{\frac {1}{2}}\left({\frac {t-m_{t}}{\sigma _{t}}}\right)^{2}}$.

Поток Эрланга

Потоком Эрланга $k$-го порядка называется стационарный поток без последействий, у которого интервалы между событиями представляют собой сумму $k+1$ независимых случайных величин, распределенных одинаково по экспоненциальному закону с параметром $\lambda$. При $k=0$ поток Эрланга является простейшим потоком.

Плотность распределения случайной величины T-интервала между двумя соседними событиями в потоке Эрланга $k$-го порядка равна: $f_{k}(t)={\frac {\lambda (\lambda t)^{k}}{\Gamma (\alpha )}}\exp {-\beta t}$, $t>0,\alpha \geqslant 1$.

Гамма-поток

Гамма-потоком называется стационарный поток без последействий, у которого интервалы между событиями представляют собой случайные величины, подчиненные гамма-распределению с параметрами $\alpha$ и $\beta$: $f(t)={\frac {\beta ^{\alpha }t^{\alpha -1}}{k!}}\exp {-\lambda t}$, $t>0$, где $\Gamma (\alpha )=\int _{0}^{\infty }x^{\alpha -1}\exp {-x}dx$.

При $\alpha =k+1$ гамма-поток является потоком Эрланга $k$-го порядка.

Мгновенная плотность

Мгновенная плотность (интенсивность) потока равна пределу отношения среднего числа событий, приходящихся на элементарный интервал времени ($t$, $t+x$) к длине интервала ($x$), когда последний стремится к нулю.

$\lambda (t)=\lim _{x\to 0}\left({\frac {M(t+x)-M(t)}{x}}\right)$

или, для простейшего потока,

$\lambda ={\frac {M(x)}{x}},$

где $M(x)$ равно математическому ожиданию числа событий на интервале $x$.

Формула Литтла

Основная статья: Закон Литтла

$N^{*}=\lambda T.$

Среднее число заявок в системе равно произведению интенсивности входного потока на среднее время пребывания заявки в системе.

См. также

• Система массового обслуживания
• Исследование операций

Литература

1. Ивченко Г. И., Каштанов В. А., Коваленко И. Н. Теория массового обслуживания. — Учебное пособие для вузов. — М.: Высшая школа, 1982. — 256 с. — 20 000 экз.
2. Клейнрок Л. Теория массового обслуживания. Пер. с англ. / Пер. И. И. Грушко; ред. В. И. Нейман. — М.: Машиностроение, 1979. — 432 с. — 10 000 экз.
3. Матвеев В. Ф., Ушаков В. Г. Системы массового обслуживания. — М.: МГУ, 1984. — 240 с.
4. Математический энциклопедический словарь / Гл. ред. Ю. В. Прохоров. — М.: Советская энциклопедия, 1988. — 847 с.
5. Лифшиц А. Л., Мальц Э. А. Статистическое моделирование систем массового обслуживания / С предисл. член.-корр. АН СССР Н. П. Бусленко. — М.: Сов. радио, 1978. — 248 с.
6. Вентцель Е. С., Овчаров Л. А. Теория вероятностей (глава 10. Марковские процессы. Потоки событий. Теория массового обслуживания). — М.: «Наука». Главное издательство Физико-математической литературы, 1969. — 368 с. — 100 000 экз.
7. Боровков А. А. Вероятностные процессы в теории массового обслуживания. — М.: «Наука». Главное издательство Физико-математической литературы, 1972. — 368 с. — (Теория вероятностей и математическая статистика). — 13 000 экз.
8. Овчаров Л. А. Прикладные задачи теории массового обслуживания. — М.: Машиностроение, 1969. — 323 с. — 7500 экз.
9. Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. — М.: Издательство «Наука», Главная редакция физико-математической литературы, 1966. — 432 с. — 12000 экз.
10. Хемди А. Таха. Глава 17. Системы массового обслуживания // Введение в исследование операций = Operations Research: An Introduction. — 7-е изд. — М.: «Вильямс», 2007. — С. 629—697. — ISBN 0-13-032374-8.