Классификация систем массового обслуживания

      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). 

       Следует отметить, что на практике СМО  описывается, как правило, путем определения совокупности параметров {l, n_a} и {m, n}, считая, что ДО по умолчанию является дисциплина FIFO. Более того, если интервалы поступления или длительности обслуживания распределены по экспоненциальному закону, то нет необходимости задать и соответствующий КВ, т.к. в таком случае он равен 1 (n_a º1 или n = 1). Графическое представление СМО, для которой определены параметры, имеет вид: 
 
 

      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) — усредненное время обслуживания заявок объединенного потока, где — доля заявок класса k в суммарном потоке ( );

      3) — из этого выражения определяется КВ 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 – СМО с простейшим потоком на входе, длительностью обслуживания, распределенная по закону произвольного вида, и двумя обслуживающими приборами.

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

      2. Характеристики функционирования  СМО 

                2.1. Характеристики одноканальной СМО с однородной нагрузкой.

      Предположим, что задана ОК СМО общего вида (типа G/G/1), для которой определены параметры нагрузки, а, именно, интенсивность l и КВ n_а интервалов поступления, интенсивность обслуживания m и КВ n длительности обслуживания:

      

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

1. вероятности состояний системы;
2. загрузка или коэффициент использования системы;
3. время ожидания заявок в системе;
4. время пребывания в системе;
5. число заявок в очереди системы или длина очереди;
6. число заявок в системе.

      Следует отметить, что все перечисленные  характеристики имеют смысл только в том случае, когда система функционирует в установившемся режиме (без перегрузок), что и предполагается далее. Кроме того, последние четыре характеристики являются случайными величинами ("3" и "4" – непрерывные, "5" и "6" – дискретные) и полный анализ этих характеристик предполагает определение соответствующих функций распределения. Однако в большинстве практических приложений достаточно анализировать данные характеристики на уровне их средних значений, что и делается далее.

      Остановимся на перечисленных характеристиках более подробно.

      1) Вероятности состояний системы — это наиболее полная характеристика системы в том смысле, что, зная вероятности состояний, можно определить все остальные характеристики. При этом под состоянием СМО понимается число заявок, находящихся в системе. Вероятность состояния системы, когда в ней находится k заявок, обозначим далее через Р_k, k=0, 1, 2, ...