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

Многие процессы, описывающие функционирование экономических, организационных, технических и тому подобных систем, представляются как последовательность операций, производимых над материальными, информационными или какими-либо иными потоками. Типичными примерами могут служить процессы соединения телефонных абонентов, передачи и обработки информации, обслуживания в магазинах, поликлиниках, билетных кассах и т. д. Процессы подобного рода носят название процессов обслуживания. Для описания подобных процессов служат модели — системы массового обслуживания (СМО), изучаемые теорией массового обслуживания или теорией очередей.

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

Таким образом, системы массового обслуживания описываются заданием:

• • входящего потока требований (заявок);
• • совместного распределения времен обслуживания требований (заявок);
• • числа обслуживающих приборов (линий);
• • дисциплины обслуживания, организации очереди и процесса обслуживания.

Существуют следующие основные типы СМО: системы с потерями и системы с ожиданием. В системах с потерями заявки, которые при поступлении не находят ни одного свободного прибора, теряются. Для СМО с ожиданием возможно ожидание любого числа заявок, которые не могут быть обслужены сразу. Кроме этого рассматриваются еще СМО с ограниченным числом мест для ожидания, в которых ожидать может только число заявок, меньше некоторого фиксированного числа N. Если заявка, поступающая в СМО, застает очередь из N заявок, она теряется для системы.

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

FIFO {first in — first out) — заявки обслуживаются в порядке поступления;

LIFO (last in — first out) — инверсионный порядок обслуживания, при котором в первую очередь обслуживается заявка, поступившая последней;

PS (processor sharing) — разделение процессора; она характерна тем, что если в очереди СМ О находятся М заявок, то каждая из них обслуживается за 1 с в течение времени с;

SIRO (service in random order) — очередная заявка выбирается из очереди наудачу.

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

Для представления систем обслуживания используются обозначения, предложенные М. Кендаллом: AB N.

Буква А характеризует поток заявок:

А = G или А = GI — рекуррентный поток (промежутки времени между заявками — взаимно независимые СВ, каждая из которых имеет одну и ту же произвольную ФР);

А = М — пуассоновский поток;

А = E_k — поток Эрланга к-го порядка (поток Эрланга k-ro порядка образуется путем просеивания простейшего потока при сохранении каждого (к + 1)-й заявки и отбрасывании всех остальных заявок);

AD — регулярный или детерминированный поток (с постоянным интервалом между моментами поступления заявок).

Буква В характеризует случайные последовательности длительности обслуживания на отдельных приборах:

В = G или В = GI — рекуррентное обслуживание с одной и той же функцией распределения B (t) для разных приборов;

В = М — экспоненциальное обслуживание с одинаковой интенсивностью для разных приборов;

В = Е_к — эрлангово обслуживание k-YO порядка с одинаковой интенсивностью для разных приборов;

В = D — регулярное обслуживание, идентичное для разных приборов.

Буква п означает количество обслуживающих приборов, буква N — количество мест для ожидания заявок в очереди.

Если п = 1, то СМО называется однолинейной (одноканалъной) если 1 < п < оо, то система называется многолинейной (многоканальной).

Значение N= 0 характеризует СМО с потерями, значение 0 < JV< оо — систему с ограниченным числом мест для ожидания, значение N = оо — СМО с ожиданием. В последнем случае часть «|оо» опускается, так что Л|В|/?|со и А Вп означают одно и то же.

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