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

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

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

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

Все системы массового обслуживания имеют следующие основные элементы:

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

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

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

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

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

в) Дисциплина очереди или правила поведения очереди. Это правила, в соответствии с которыми обслуживающий механизм принимает поступившую заявку на обслуживание. Например, “первым пришел – первым обслуживается”, “последним пришел – первым обслуживается”, “случайный отбор заявок” и т.п.

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

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

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

Характеристики эффективности СМО:

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

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

3) Среднее время ожидания в очереди и т.п.

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

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

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

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

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

W(t) – продолжительность ожидания обслуживания относительно требования, которое поступило в момент времени t;

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

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

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

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

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

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

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

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

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

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

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

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

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

Одноканальная СМО с отказами

Рассмотрим СМО, которая состоит из одного канала (одного обслуживающего прибора). На нее поступает стационарный пуассоновский поток заявок с интенсивностью

l = l(t). Заявка, заставшая канал занятым, получает отказ и покидает систему. Обслуживание заявки продолжается в течение случайного времени T_обсл., имеющему экспоненциальную плотность вероятности:

f(t) = me^-^m^t.

Из сказанного следует, что мы имеем дело с системой типа М/М/1. Ее размеченный граф имеет вид:

Возможно два состояния:

Q₀ – канал свободен;

Q₁ – канал занят.

Из Q₁ в Q₀ систему переводит поток заявок, а из Q₁ в Q₀ поток обслуживаний. Обозначим вероятности состояний p₀(t) и p₁(t) и составим для них дифференциальные уравнения Колмогорова. Получим:

Если учесть, что p₁+p₀ = 1, то получим одно уравнение:

Можно показать, что при начальных условиях p₀(0) = 1, p₁(0) = 0, решение имеет вид:

Начальное условие p₀(0) = 1 означает, что в начальный момент канал заведомо свободен. Зависимости p₀(t) и p₁(t) показаны на рисунке.

Важной характеристикой СМО с отказами является относительная пропускная способность q, которая равна доли обслуженных требований от общего числа поступивших в систему

q = 1 – P_отк.,

P_отк. – вероятность отказа в обслуживании поступившему требованию. В нашем случае:

P_отк. = p₁ и y = m/(l + m).

Абсолютная пропускная способность А – это среднее число требований, обслуживаемых системой в единицу времени:

Пример: АЗС имеет одну заправочную колонку. Заявка (требование) – автомобиль, пришедший на заправку. АЗС не имеет места для ожидания, поэтому автомобиль, пришедший на заправку в момент, когда колонка занята, покидает АЗС. Средняя продолжительность заправки мин, средняя интенсивность потока автомобилей l = 0,3 (авт. в минуту). Все потоки событий простейшие. Определить предельные величины:

1) относительной пропускной способности q;

2) абсолютной пропускной способности А;

3) вероятность отказа.

Решение: Имеем одноканальную СМО с отказами. Т.к. время обслуживания имеет экспоненциальное распределение, то

Относительная пропускная способность:

т.е. в установившемся режиме будет обслуживаться около 42,5% машины.

Абсолютная пропускная способность:

A = l * q = 0,425 * 0,3 = 0,127,

т.е. в среднем заправляется 0,127 машин/мин.

Вероятность отказа: P_отк. = 1 – q = 0,575.

Определим номинальную пропускную способность АЗС как

что почти вдвое больше, чем фактическая пропускная способность. Это объясняется стохастической природой входного потока и время обслуживания.

Многоканальная СМО с ожиданием (тип СМО – М/М/n)

Схема СМО показана на рисунке

Поток поступающих требований – пуассоновский со средней интенсивностью l. Число мест для ожидания равно m. Время обслуживания имеет экспоненциальное распределение с параметром m.

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

Максимально в СМО одновременно может находиться n + m требований. Состояние системы будем нумеровать по числу находящихся в ней требований: Q₀ – все каналы свободны; Q₁ – занят один канал; Q_n – заняты все каналы; Q_n₊₁ – одно требование стоит в очереди;

Q_n₊_m – все каналы заняты, все места в очереди заняты. Граф состояний имеет вид:

Если очереди нет, то систему из состояния Q_k в Q_k_-1 переводит поток, интенсивность которого равна km.

Граф представляет рассмотренную схему “гибели и размножения”. Используя полученные результаты можно записать выражение для финальных вероятностей. Обозначим r = l/m.

;

Основные характеристики системы

1) Вероятность того, что все обслуживающие устройства свободны p₀. (1)

2) Вероятность того, что занято k обслуживающих устройств p_k. (2)

3) Вероятность того, что все обслуживающие устройства заняты и l требований в очереди (l£m) (из 3)

Вероятность отказа в обслуживании:

4) Среднее число устройств, занятых обслуживанием требований:

Если выполнить суммирование:

5) Среднее число простаивающих устройств:

6) Коэффициенты прочности и занятости:

7) Относительная пропускная способность:

8) Абсолютная пропускная способность:

A = l q;

9) Среднее число требований, находящихся в очереди. Очередь существует тогда, когда все обслуживающие устройства заняты:

10) Среднее число требований в системе:

11) Среднее время ожидания в очереди. Если заявка застанет занятыми не все каналы, ей вообще не придется ждать облуживания. Если заявка придет в момент, когда заняты все n каналов, а очереди нет, ей придется ждать среднее время 1/nm (nm - интенсивность потока освобождения n каналов). Если заявка придет в СМО и застанет в очереди одну заявку, то она будет ждать 2/nm и т.д. Если заявка застанет в очереди m заявок, то она ждать не будет.

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

12) Среднее время пребывания заявки в СМО. Время пребывания заявки в СМО:

t_сис = t_ож + t, t_ож – время ожидания в очереди;

<t_сис> = <t_ож> + <t>;

<t> = (1-q)0 + q<t_обсл> = q /m; <t_обсл> = 1/m;

<t_сис> = W + q/m;

Прежде чем рассмотреть пример, рассмотрим n-канальную СМО с неограниченной очередью (m®¥). Можно показать, что условием существования финальных вероятностей является r/n < 1. Если r/n ³ 1, то очередь растет до бесконечности. Для системы с неограниченной очередью:

Напоминаем выражение для СМО с ограниченной очередью:

- формула Литтла.

Пример. Касса по продаже железнодорожных билетов с двумя окошками представляет собой двухканальную СМО с неограниченной очередью, которая устанавливается сразу к двум окошкам. Касса продает билеты сразу в два пункта А и В. Интенсивность потока заявок для обоих пунктов одинакова и равна l_А = l_B = 0,45. Интенсивность результирующего потока

l = l_A + l_B = 0,9. Касса в среднем тратит на обслуживание одного пассажира две минуты (время обслуживания имеет экспоненциальное распределение). Пассажиры не довольны большой очередью у кассы. Поступило предложение создать две специализированные кассы, продающие билеты одна только в пункт А, другая в пункт В. Оценить эффективность такого предложения при условии, что поток пассажиров – простейший.

Найдем среднюю длину очереди L_оч и среднее время ожидания в очереди.

Вариант1.

Двухканальная СМО. l = 0,9. m = 0,5. r = l/m = 1,8. r/2 = 0,9 < 1 – условие существования финальных вероятностей выполняется.

P₀» 0,0525 (вероятность присутствия заявок в системе)

L_оч = 7,68чел W_оч = 8,54 мин.

Вариант2.

Две одноканальные СМО. l = 0,9. i =1,2. m = 0,5. r = 0,9.

L_оч = 8,1чел; W_оч = 18 мин.

Второй вариант значительно хуже первого. Это можно объяснить тем, в первом варианте меньше средняя доля времени, которую простаивает каждый из двух пассажиров. Если он не занят обслуживанием пассажира, покупающего билет в А он может заняться обслуживанием пассажира, покупающего билет в В и наоборот. Во втором варианте незанятый кассир сидит. Следует также отметить, что обе СМО работают на пределе своих возможностей. Если немного увеличить время обслуживания, то r станет больше 1 и очередь начнет неограниченно возрастать.