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

Первое деление (по наличию очередей):

- СМО с отказами;

- СМО с очередью (с ожиданием);

- смешанного типа.

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

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

СМО с очередью подразделяются на разные виды, в зависимости от того, как организована очередь — ограничена она или не ограничена. Ограничения могут касаться как длины очереди, так и времени ожидания (так называемые «СМО с нетерпеливыми заявками»). При анализе СМО должна учитываться также и «дисциплина обслуживания» — заявки могут обслуживаться либо в порядке поступления (раньше пришла, раньше обслуживается), либо в случайном порядке. Нередко встречается так называемое обслуживание с приоритетом — некоторые заявки обслуживаются вне очереди. Приоритет может быть как абсолютным — когда заявка с более высоким приоритетом «вытесняет» из-под обслуживания заявку с низшим, так и относительным — когда начатое обслуживание доводится до конца, а заявка с более высоким приоритетом имеет лишь право на лучшее место в очереди.

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

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

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

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

- одноканальные системы;

- многоканальные системы.

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

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

1.5 Функционирование системы массового обслуживания

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

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

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

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

3. время обслуживания требования каждым прибором;

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

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

6. дисциплина очереди, т.е. совокупность правил, в соответствии, с которыми требование отдает предпочтение той или иной очереди (если их несколько) и располагается в выбранной очереди. Например, поступившее требование может занять место в самой короткой очереди; в этой очереди оно может расположиться последним (такая очередь называется упорядоченной), а может пойти на обслуживание вне очереди. Возможны и другие варианты.

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

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

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

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

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

Рисунок 2 – Структура СМО

Поступающие на вход СМО однородные заявки в зависимости от порождающей причины делятся на типы, интенсивность потока заявок типа i (i=1…M) обозначено _i. Совокупность заявок всех типов - входящий поток СМО.

Обслуживание заявок выполняется m каналами. Различают универсальные и специализированные каналы обслуживания. Для универсального канала типа j считается известными функции распределения F_ji() длительности обслуживания заявок произвольного типа. Для специализированных каналов функции распределения длительности обслуживания каналов заявок некоторых типов являются неопределёнными, назначение этих заявок на данный канал.

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

Таким образом процесс функционирования системы массового обслуживания можно представить в виде Q-схемы (Рисунок 3).

Рисунок 3 – Q - схема

П_i – некоторый i-й прибор обслуживания, который состоит из накопителя заявок H_i, в котором может находиться одновременно l_i=0…L_i^H заявок, где L_i^H - ёмкость i-ого накопителя, и канала обслуживания заявок, k_i. На каждый элемент прибора обслуживания П_i поступают потоки событий: в накопитель H_i поток заявок w_i , на канал k_i - поток обслуживания u_i.

Потоком событий (ПС) называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Различают потоки однородных и неоднородных событий. Однородный ПС характеризуется только моментами поступления этих событий (вызывающими моментами) и задаётся последовательностью {t_n}={0t₁t₂…t_n…}, где t_n - момент поступления n- ого события - неотрицательное вещественное число. ОПС может быть также задан в виде последовательности промежутков времени между n-ым и n-1-ым событиями {_n}.

Неоднородным ПС называется последовательность {t_n, f_n} , где t_n- вызывающие моменты; f_n- набор признаков события. Например, может быть задана принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала и т.п.

Применительно к элементарному каналу обслуживания k_i можно считать что поток заявок w_iW, т.е. интервалы времени между моментами появления заявок на входе k_i образуют подмножество неуправляемых переменных, а поток обслуживания u_iU, т.е. интервалы времени между началом и окончанием обслуживания заявки образуют подмножество управляемых переменных.

Заявки, обслуженные каналом k_i и заявки, покинувшие прибор П_i по различным причинам не обслуженными, образуют выходной поток y_iY.

Процесс функционирования прибора обслуживания П_i можно представить как процесс изменения состояний его элементов во времени Z_i(t). Переход в новое состояние для П_i означает изменение кол-ва заявок, которые в нём находятся (в канале k_i и накопителе H_i). Т.о. вектор состояний для П_i имеет вид : , где - состояния накопителя, (=0 - накопитель пуст, =1- в накопителе одна заявка…, =- накопитель занят полностью; - состояние канала k_i (=0 - канал свободен, =1 канал занят).

Q-схемы реальных объектов образуются композицией многих элементарных приборов обслуживания П_i. Если k_i различных приборов обслуживания соединены параллельно, то имеет место многоканальное обслуживание (многоканальная Q-схема), а если приборы П_i и их параллельные композиции соединены последовательно, то имеет место многофазное обслуживание (многофазная Q-схема).

Связи в Q-схеме изображают в виде стрелок (линий потока, отражающих направление движения заявок). Различают разомкнутые и замкнутые Q-схемы. В разомкнутой выходной поток не может снова поступить на какой-либо элемент, т.е. обратная связь отсутствует.

• Собственными (внутренними) параметрами Q-схемы будут являться кол-во фаз L_Ф, количество каналов в каждой фазе, L_kj, j=1… L_Ф, количество накопителей каждой фазы L_kj, k=1… L_Ф, ёмкость i-ого накопителя L_i^H.

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

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

В зависимости от динамики приоритетов Q-схемы различают статические и динамические. Статические приоритеты назначаются заранее и не зависят от состояний Q-схемы, т.е. они являются фиксированными в пределах решения конкретной задачи моделирования. Динамические приоритеты возникают при моделировании. Исходя из правил выбора заявок из накопителя Н_i на обслуживание каналом k_i можно выделить относительные и абсолютные приоритеты. Относительный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Н, ожидает окончания обслуживания представляющей заявки каналом k_i и только после этого занимает канал. Абсолютный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель, прерывает обслуживание каналом k_i заявки с более низким приоритетом и сам занимает канал (при этом вытесненная из k_i заявка может либо покинуть систему, либо может быть снова записана на какое-то место в Н_i).

Необходимо также знать набор правил, по которым заявки покидают Н_i и k_i: для Н_i – либо правила переполнения, либо правила ухода, связанные с истечением времени ожидания заявки в Н_i­; для k_i – правила выбора маршрутов или направлений ухода. Кроме того, для заявок необходимо задать правила, по которым они остаются в канале k_i, т.е. правила блокировок канала. При этом различают блокировки k_i по выходу и по входу. Такие блокировки отражают наличие управляющих связей в Q‑схеме, регулирующих поток заявок в зависимости от состояний Q‑схемы.

Таким образом Q‑схема, описывающая процесс функционирования СМО любой сложности однозначно задаётся в виде набора множеств: Q = {W, U, H, Z, R, А}, где А – оператор алгоритмов обслуживания заявок (оператор поведения заявок).