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

При решении различных задач часто приходится сталкиваться с анализом эффективности работы систем массового обслуживания (СМО). Примеры СМО: телефонная станция, ремонтные мастерские, билетные кассы, автомобильные заправочные станции, железнодорожные сортировочные станции и т. п. Заявки поступают в СМО случайно, образуя поток заявок. Обслуживание заявок также выполняется в течение случайного времени. Это приводит к тому, что в некоторые моменты времени в СМО скапливается большое количество заявок, а в другие моменты заявок мало или они вообще отсутствуют. Обычно предполагается, что известен вероятностный закон, управляющий поступлением заявок. Впервые такая задача была решена датским математиком А.К. Эрлангом в начале ХХ века для анализа работы телефонной станции. В теории массового обслуживания понятие очереди является одним из основных.

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

Все СМО характеризуются следующими основными элементами:

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

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

Дисциплина очереди или правила поведения в очереди,

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

− «живая очередь» − первый пришел и первым обслужи-ваешься;

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

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

− обслуживание по приоритетам. Например, обслуживание ветеранов или ликвидация аварий;

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

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

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

Эффективность работы СМО определяется следующими параметрами:

– среднее число обслуживаемых заявок СМО в единицу времени;

– среднее число заявок в единицу времени, покидающих СМО необслуженными;

– среднее время ожидания в очереди и т. п.

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

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

При изучении СМО можно выделить три класса рассматриваемых задач: задачи анализа систем, статические задачи и операционные задачи.

Задачи анализа поведения системы заключаются в том, чтобы на основе математических моделей, адекватно отражающих свойства СМО, выявить основные операционные характеристики, определяющие поведение этих систем в процессе их функционирования. К таким характеристикам относятся:

1) – число требований, находящихся в очереди в момент времени ;

2) – продолжительность ожидания в очереди требования, поступившего в СМО в момент времени ;

3) – продолжительность n-го периода простоя системы.

На практике часто используется показатель, который называется степенью загруженности обслуживающего прибора или коэффициентом нагрузки:

.

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

Операционные задачи возникают при проектировании СМО, управлении системами и для оценки их эффективности. Некоторые из этих задач по своей природе относятся к разряду статистических.

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

Используются следующие обозначения:

– пуассоновское, или экспоненциальное распределение;

– постоянная величина;

– распределение Эрланга;

– произвольное распределение;

– распределение в случае независимых событий.

Например, обозначение M /D /s – означает, что имеется СМО с приборами, обслуживающая поступающие требования за строго определенный интервал времени, входной поток - пуассоновский.

Замечание. Введенная классификация не учитывает правил формирования очереди, которые должны дополнять модель СМО.