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

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

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

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

Такие системы можно описать, если задать:

1) входящий поток требований или заявок, которые поступают на обслуживание;

2) дисциплину постановки в очередь и выбор из нее;

3) правило, по которому осуществляется обслуживание;

4) выходящий поток требований;

5) режимы работы.

1) Входящий поток. Для задания входящего потока требований необходимо описать моменты времени их поступления в систему (закон поступления) и количество требований, которое поступило одновременно. Закон поступления может быть детерминированный )например, одно требование поступает каждые 10 мин) или стохастический (требования могут появляться с равной вероятностью в интервале 10± 3 ми). В общем случае входящий поток требований описывается распределением вероятностей интервалов времени между соседними требованиями.

Классическая теория массового обслуживания рассматривает так называемый пуассоновский (простейший) поток требований (событий). Для этого потока число требований k для любого интервала времени распределено по закону Пуассона:

где λ – интенсивность потока событий. Интенсивность потока это среднее число событий, которые появляются в единицу времени. Среднее число событий, наступающих на интервале ∆t в единицу времени, составляет Р₁(t; ∆t)/∆t. Рассмотрим предел этого выражения при ∆t→0:

Если этот предел существует, то он называется интенсивностью (плотностью) потока событий. Для стационарного потока событий λ(t) =λ = const.

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

· «раньше поступил – раньше обслужился» РПРО (FIFO;

· «последний поступил – первый обслужился» ПППО (LIFO). Это правило также называется «стеком» или «магазином».

Дисциплина обслуживанияопределяет:

· при каких условиях прекращается обслуживание требований;

· как выбирается для обслуживания следующее требование;

· что делать с частично обслуженным требованием.

На очереди могут накладываться ограничения по длине очереди или по времени пребывания в ней. Очередь может также быть с ограниченным количеством мест ожидания – это так называемый буфер.

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

Обслуживание может организовываться с помощью одного устройства – это так называемые системы с одним устройством (каналом) обслуживания – или с несколькими – многоканальные системы.

Устройства обслуживания могут быть объединены в последовательную цепочку – это многофазные системы обслуживания.

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

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

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

N = λT.

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

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

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

Каждая такая система может содержать конечное число элементов обслуживания, называемых каналами обслуживания. Примерами таких систем могут быть телефонные, радиолокационные станции, ЭВМ, вычислительные центры, информационные системы различных видов.

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

Процесс продвижения заявок в СМО осуществляется по некоторому закону управления, который задается дисциплинами ожидания D1 и обслуживания D2. Дисциплина ожидания определяет порядок приема заявок в систему и размещения их в очереди, а дисциплина обслуживания – порядок выбора заявок из очереди для назначения на обслуживание.

Поступающие на вход СМО однородные заявки в зависимости от порождающей причины делятся на типы. Совокупность заявок всех типов образует входящий поток СМО. Интенсивность потока заявок типа i (i = 1,…, m) обозначим λ_i. Обслуживание заявок выполняется m каналами (К). Различают универсальные и специализированные каналы обслуживания. Для универсального канала типа j считаются известными функции распределения F_ij(τ) длительности обслуживания заявок произвольного типа. Для специализированных каналов функции распределения обслуживания заявок некоторых типов являются неопределенными.

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

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

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

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

Для характеристики СМО обычно применяют следующие показатели:

· среднее число заявок, которые система может обслужить за единицу времени;

· средний процент необслуженных заявок;

· вероятность того, что поступившая заявка будет принята к выполнению;

· среднее время ожидания в очереди;

· закон распределения времени ожидания;

· среднее число заявок в очереди;

· закон распределения числа заявок в очереди;

· средний доход системы в единицу времени.

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

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

· ожидание обслуживания заявки;

· обслуживание заявки.

Это можно отобразить в виде некоторого i-го прибора обслуживания П_i , состоящего из накопителя заявок Н_i и канала обслуживания заявок К_i (рис. 2.4).

Рис. 2.4. Схема прибора СМО

В накопителе может находиться одновременно заявок

l_i =,…, L_i^Н,

где L_i^Н – емкость i-го накопителя. На каждый элемент прибора обслуживания П_i поступают потоки событий: поток заявок w_i в накопитель Н_i, на канал K_i – поток обслуживания u_i.

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

Суммируя сказанное, можно выделить следующие разновидности СМО:

1) по числу каналов обслуживания – одноканальные и многоканальные;

2) по числу фаз (последовательно соединенных агрегатов) – однофазные и многофазные

З) по наличию обратной связи – разомкнутые (с бесконечным числом заявок) и замкнутые (с конечным числом заявок);

4) по наличию очереди – системы без очередей (с потерями заявок), системы с неограниченным ожиданием (по времени или длине очереди) и системы с ограниченным ожиданием (по времени или длине очереди);

5) по принципу формирования очередей – системы с общей очередью и системы с несколькими очередями;

6) по наличию отказов – системы с отказами и системы без отказов;

7) по виду приоритета – системы со статическим приоритетом и системы с динамическим приоритетом.

Не нашли, что искали? Воспользуйтесь поиском по сайту: