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

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

2.3 Процесс обслуживания

По аналогии с процессами поступления заявок в систему для описания процессов  обслуживания необходимо задать функцию распределения B_k(t) длительности обслуживания для каждой k-й заявки (k = 1, 2, 3, ...), которая в общем случае является случайной величиной. При этом под длительностью обслуживания t_в понимается промежуток времени, в течение которого заявка находится в обслуживающем приборе. Далее будем считать, что все заявки создают статистически однородную нагрузку, т.е. длительности обслуживания всех заявок распределены по одному и тому же закону:

  (2.4)

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

Величина b, обратная интенсивности m (b=1/m), определяет среднее время обслуживания одной заявки.

Как и в случае интервалов поступления, если функция распределения B(t) неизвестно, то для многих приложений (теоретических и практических) оказывается достаточным определить интенсивность обслуживания m (или среднее время обслуживания b) и КВ n_в длительности обслуживания. Если длительность обслуживания распределено по экспоненциальному закону, то достаточно задать интенсивность обслуживания m (или среднее время обслуживания b). Следует отметить, что, в отличие от интервалов поступления заявок, отказ от экспоненциального характера распределения длительности их обслуживания не столь усложняет задачу аналитического исследования СМО, и многие содержательные результаты получены при произвольном характере распределения времени обслуживания.

2.4 Дисциплина обслуживания

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

1) обслуживание в порядке  поступления или дисциплина FIFO (First Input, First Output — первым пришел, первым ушел);

2) обслуживание в обратном порядке или дисциплина LIFO (Last Input, First Output — последним пришел, первым ушел);

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

В дальнейшем в  качестве ДО будем рассматривать  ДО FIFO.

Таким образом, для описания СМО необходимо задать:

1) функцию распределения A(t) интервалов поступления (общий случай) или интенсивность поступления l (или средний интервал а=1/l) и КВ n_а интервалов поступления;

2) функцию распределения В(t) длительности обслуживания (общий случай) или интенсивность обслуживания m (или среднее время обслуживания b=1/m) и КВ n_вºn времени обслуживания;

3) дисциплина обслуживания (ДО FIFO).

1.5 СМО с неоднородной  нагрузкой

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

Для формализации СМО с неоднородной нагрузкой необходимо описать:

1. процесс поступления заявок каждого класса, т.е. необходимо задать либо функции распределений А₁(t), А₂(t), ..., А_H(t) интервалов поступления (общий случай), либо интенсивности поступления l₁, l₂, ..., l_H (или средние интервалы поступления a₁, a₂, ..., а_H) с КВ n_а1, n_а2, ..., n_аH интервалов поступления, где Н – количество классов заявок, поступающих в систему;
2. процесс обслуживания заявок каждого класса, т.е. необходимо задать либо функции распределения В₁(t), B₂(t), ..., B_H(t) длительностей обслуживания (общий случай), либо интенсивности обслуживания m₁, m₂, ..., m_H (или средние времена обслуживания b₁, b₂, ..., b_H) с КВ n₁, n₂,..., n_H длительностей обслуживания;
3. дисциплину обслуживания, в качестве которой может быть задана:

а) ДО бес приоритетная, когда между заявками разных классов нет приоритетов (приоритет ¾ это преимущественное право на обслуживание);

б) ДО с относительными приоритетами, когда приоритеты заявок учитываются только в моменты выбора их из очереди на обслуживание;

в) ДО с абсолютными приоритетами, когда приоритеты учитываются так же и во время обслуживания – высокоприоритетные заявки прерывают обслуживание низкоприоритетных;

г) ДО со смешанными приоритетами, когда заявки данного  класса имеют к заявкам одних  классов относительный приоритет, к заявкам других – абсолютный, а к заявкам третьих – нет приоритета.

Вопросы математической формализации перечисленных ДО выходят  за рамки курса "Моделирование  дискретных систем".

 Графическое представление  СМО с неоднородной нагрузкой имеет вид

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

1)    (2.5)  — интенсивность объединенного потока (простейшего);

2) (2.6) — усредненное время обслуживания заявок объединенного потока, где — доля заявок класса k в суммарном потоке ( );

3) (2.7)  — из этого выражения определяется КВ n длительности обслуживания заявок объединенного потока.

После преобразований исходная модель примет вид:

1.6 Многоканальные СМО

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

Для описания МК СМО задается та же совокупность параметров, что  и для ОК СМО (см. раздел 1.4). Дополнительно  задается только количество N обслуживающих приборов. Графическое представление МК СМО имеет вид:

1.7  Мнемоническое обозначение СМО

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

А – описывает распределение (или задает характер закона распределения) интервалов поступления заявок;

В – описывает распределение длительностей обслуживания заявок;

N – задает количество обслуживающих приборов в СМО.

Иногда, когда СМО является системой с ограниченной емкостью накопителя (или с ограниченной очередью), приведенное обозначение расширяется до четырех букв А/В/N/К, где последняя буква (на самом деле число, как и N) К задает емкость накопителя (количество мест ожидания).

Приведенные трех или четырех буквенные обозначения  называют обозначениями Кендалла. В этих обозначениях А и В могут принимать значения из следующего набора символов {M, D, E_k, H_k, G, U}. При этом:

а) А или В=M, если распределение интервалов поступления или длительностей обслуживания заявок является экспоненциальным (М – от слова Markovian – Марковский);

б) А или В=D, если интервалы поступления или длительности обслуживания являются детерминированными (D – Determinate);

в) А или В=E_k, если соответствующие распределения являются Эрланговскими порядка k (E – Erlang);

г) А или В=H_k, в случае гиперэкспоненциальных распределений порядка k (H – Hyperexponential);

д) А или В= G, в случае распределений общего (произвольного) вида (G – General – общий, общего вида);

е) А или В= U – при равномерных распределениях соответствующих случайных величин (U – Uniform distribution – равномерное распределение).

Так, например, обозначение  вида:

М/М/1 означает СМО с простейшим потоком на входе и экспоненциально распределенной длительностью обслуживания заявок в приборе (один)

D/Е₂/3/5 – СМО с регулярным потоком на входе, длительностью обслуживания, распределенной по закону Эрланга 2-го порядка, тремя обслуживающими приборами и пятью местами ожидания;

М/G/2 – СМО с простейшим потоком на входе, длительностью обслуживания, распределенная по закону произвольного вида, и двумя обслуживающими приборами.

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

 

3 МОДЕЛИ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С ОГРАНИЧЕННОЙ ОЧЕРЕДЬЮ

3.1 Многоканальная СМО с ограниченной длиной очереди

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

- все каналы свободны, ;

- занят только один канал (любой), ;

- заняты только два канала (любых), ;

- заняты все  каналов, .

 

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

- заняты все  каналов и одна заявка стоит в очереди,

;

- заняты все  каналов и две заявки стоят в очереди,

;

- заняты все  каналов и все мест в очереди,

.

Граф состояний n-канальной СМО с очередью, ограниченной m местами на рис.3.1.

Рисунок 3.1 – Граф состояний n-канальной СМО с ограничением на длину очереди m

 

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

Запишем выражения  для предельных вероятностей состояний:

 

 

.

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

     (3.1)

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

   

(3.2)

 

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

Поэтому вероятность  образования очереди равна:

 

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

1. Вероятность того, что все обслуживающие устройства свободны, определяется с помощью формулы (3.2).
2. Вероятность того, что обслуживанием занято определенное число устройств , определяется с помощью (3.1).
3. Вероятность того, что все обслуживающие устройства заняты и требований ожидают в очереди, с учетом (3.1)

  (3.3)

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

      (3.4)

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

     (3.5)

6. Среднее число простаивающих устройств