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

Теорія масового обслуговування, або теорія черг (англ. queueing theory), — розділ теорії ймовірностей, метою досліджень якого є раціональний вибір структури системи обслуговування та процесу обслуговування на основі вивчення потоків вимог на обслуговування, що надходять у систему і виходять з неї, тривалості очікування і довжини черг^[1]. У теорії масового обслуговування використовуються методи теорії ймовірностей та математичної статистики.

Історія

Перші задачі теорії масового обслуговування (ТМО) були розглянуті співробітником Копенгагенської телефонної компанії Агнером Ерлангом^[en] у період між 1908 і 1922 роками. Стояло завдання упорядкувати роботу телефонної станції і заздалегідь розрахувати якість обслуговування споживачів залежно від числа використовуваних пристроїв.

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

Потік

Однорідний потік

Потік заявок однорідний, якщо:

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

Потік без післядії

Потік без післядії, якщо число подій за будь-який інтервал часу (${\displaystyle t}$, ${\displaystyle t+x}$) не залежить від числа подій на будь-якому іншому (${\displaystyle t}$, ${\displaystyle t+x}$) інтервалі часу.

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

Потік заявок стаціонарний , якщо ймовірність появи n подій на інтервалі часу (${\displaystyle t}$, ${\displaystyle t+x}$) не залежить від часу ${\displaystyle t}$, а залежить тільки від довжини цієї ділянки.

Найпростіший потік

Однорідний стаціонарний потік без післядії є найпростішим або пуассонівським потоком.

Число ${\displaystyle n\,}$ подій такого потоку, що випадають на інтервал ${\displaystyle x}$, розподілено за законом Пуассона:

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

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

Миттєва щільність

Миттєва щільність (інтенсивність) потоку дорівнює границі відношення середнього числа подій, що припадають на елементарний інтервал часу (${\displaystyle t}$, ${\displaystyle t+x}$) до довжини інтервалу часу (${\displaystyle x}$), коли останній прямує до нуля.

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

або, для найпростішого потоку,

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

де ${\displaystyle M(x)}$ дорівнює математичному очікуванню числа подій на інтервалі ${\displaystyle x}$.

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

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

${\displaystyle ~N^{*}=\lambda T}$

У 1961 році професор Массачусетського Технологічного Інституту Джон Літтл довів, що це твердження, відоме як закон Літтла діє у кожній системі черг, якщо досліджувати її достатньо довго.

Література

1. Теория массового обслуживания // Математический энциклопедический словарь. М., «Советская энциклопедия», 1988, стр. 327-328

Бібліографія

1. Ивченко Г.И., Каштанов В.А., Коваленко И.Н. Теория массового обслуживания / Рецензенты: кафедра математической статистики, теории надёжности и массового обслуживания факультета прикладной математики — процессов управления ЛГУ им. А.А. Жданова и д.т. н., профессор Р.Я. Судаков. — Учебное пособие для вузов. — М. : Высшая школа, 1982. — 256 с. — 20 000 прим.
2. Клейнрок Л. Теория массового обслуживания
3. Матвеев В. Ф., Ушаков В. Г. Системы массового обслуживания
4. Математический энциклопедический словарь, М., «Советская энциклопедия», 1988
5. Лифшиц А. Л., Мальц Э. А. Статистическое моделирование систем массового обслуживания
6. Вентцель Е. С., Овчаров Л. А. Теория вероятностей. Глава 10. Теория массового обслуживания. М., 1969, 368 стр. с илл.

Див. також

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