Система массового обслуживания (СМО) - система, которая производит обслуживание поступающих в неё требований. Обслуживание требований в СМО производится обслуживающими приборами. Классическая СМО содержит от одного до бесконечного числа приборов. В зависимости от наличия возможности ожидания поступающими требованиями начала обслуживания СМО подразделяются на
Выбор требования из очереди на обслуживание производится с помощью так называемой дисциплины обслуживания. Их примерами являются FCFS/FIFO (пришедший первым обслуживается первым), LCFS/LIFO (пришедший последним обслуживается первым), random (англ.) (случайный выбор). В системах с ожиданием накопитель в общем случае может иметь сложную структуру.
Требование (заявка) - запрос на обслуживание.
Входящий поток требований - совокупность требований, поступающих в СМО.
Время обслуживания - период времени, в течение которого обслуживается требование.
Математическая модель СМО - это совокупность математических выражений, описывающих входящий поток требований, процесс обслуживания и их взаимосвязь.
Wikimedia Foundation . 2010 .
система массового обслуживания - СМО Система, предназначенная для обслуживания случайных потоков вызовов абонентов в сетях связи (рис. Q 3). Общепринятое условное обозначение, используемое для описания систем массового обслуживания, состоит из трех символов A/S/m, где символ А… …
Система массового обслуживания - совокупность пунктов (каналов, станций, приборов), на которые в случайные или неслучайные моменты времени поступают заявки на обслуживание (требования), подлежащие удовлетворению. Примеров таких систем можно привести очень много …
СИСТЕМА МАССОВОГО ОБСЛУЖИВАНИЯ - математическая модель, созданная для изучения качества работы реальных систем, в которых реализуются последовательности однородных элементарных операций обслуживания. С.м.о. – основной предмет исследования теории массового обслуживания. С.м.о.… … Большой экономический словарь
Многофазная система массового обслуживания - система, в которой поступившее требование проходит последовательно несколько этапов обработки. Для анализа таких систем необходимо знать не только длину очереди, время ожидания обслуживания, нагрузку каждого… … Экономико-математический словарь
многофазная система массового обслуживания - Система, в которой поступившее требование проходит последовательно несколько этапов обработки. Для анализа таких систем необходимо знать не только длину очереди, время ожидания обслуживания, нагрузку каждого последовательного звена системы, но и… … Справочник технического переводчика
Многоканальная система массового обслуживания - система, в которой поступившее требование может быть обслужено одним из нескольких каналов, входящих в блок обслуживания … Экономико-математический словарь
многоканальная система массового обслуживания - Система, в которой поступившее требование может быть обслужено одним из нескольких каналов, входящих в блок обслуживания. Тематики экономика EN multichannel system … Справочник технического переводчика
С ожиданием многоканальная система массового обслуживания, алгоритм к рой предусматривает накапливание вызовов в очереди, если в момент их прихода система оказалась занятой; при этом обслуживание вызовов ведется в нескольких каналах одновременно … Математическая энциклопедия
МАССОВОГО ОБСЛУЖИВАНИЯ СИСТЕМА - с отказами система массового обслуживания, алгоритм к рой предусматривает выбывание вызовов, в момент прихода к рых все каналы оказались занятыми. Основные определения и обозначения см. в ст. Массового обслуживания система. 1) Естественными… … Математическая энциклопедия
МАССОВОГО ОБСЛУЖИВАНИЯ СИСТЕМА - с ожиданнем и одним каналом обслуживания система массового обслуживания, алгоритм к рой предусматривает, что вызовы, не принятые немедленно к обслуживанию (заставшие систему занятой), накапливаются в очереди; при этом обслуживание следующего… … Математическая энциклопедия
Пользователи Интернет ресурсов еще не успели осмыслить и свыкнуться с тем, значит Веб 2. 0, как возникли еще два новых названия, являющиеся прямым результатом развития данного Веб 2.0 .
Не многие различают SMO и SMM , для большинства — это одно и тоже. Вместе с тем, вопрос разделения этих понятий на различные определения является довольно спорным. Можно выразиться так, что SMO представляет собой определенную часть SMM .
Лабораторией Сарафанное Радио – признанного эксперта по социальным сетям, эти два термина условно разделены с целью большего восприятия на тему достижения благополучного продвижения в социальных сетях.
Согласно определению экспертов, SMO (Social media optimization) – это общественная медио оптимизация или оптимизация под социальные медиа.
Согласно определению тех же экспертов, SMM (Social media marketing) – представляет собой социальный медиа маркетинг или маркетинг в социальных медиа.
Статья по материалам: лаборатории Сарафанное радио
В зависимости от того, как поступают с заявкой в случае, если все каналы оказались занятыми, различают:
СМО с отказом в обслуживании заявки и СМО с ожиданием.
Для СМО с отказом характерно, что заявка, заставшая все каналы занятыми, немедленно покидает систему.
В СМО с ожиданием заявка, заставшая все каналы занятыми, не покидает систему, а ставится в очередь и при освобождении одного из каналов обслуживается. В СМО с ожиданием на процесс ожидания заявок в очереди могут накладываться или не накладываться какие-либо ограничения. В последнем случае говорят, что имеют дело с "чистой" СМО с ожиданием. Если же на процесс ожидания накладываются ограничения, то СМО называют "системой смешанного типа". В таких системах из-за наложенных ограничений возможны случаи, когда заявка получит отказ в обслуживании, т.е. СМО смешанного типа проявляет также признаки СМО с отказом.
В системах смешанного типа могут накладываться следующие ограничения:
а) на количество заявок, стоящих в очереди;
б) на время пребывания заявки в очереди;
в) на общее время нахождения заявки в СМО.
В технологии РЭУ чаще всего встречаются СМО смешанного типа.
Математическое описание СМО с отказом
Рассмотрим систему массового обслуживания с отказом, имеющую п каналов. Предположим, что поток заявок, поступающих в СМО, простейший и имеет плотность l. Кроме того, будем считать, что время обслуживания заявок распределено по экспоненциальному закону с параметром
где М(Тоб) - математическое ожидание времени обслуживания заявки.
Следовательно, плотность распределения времени обслуживания
Для рассматриваемой системы возможны следующие состояния:
x 0 - свободны все каналы;
x 1 - занят один канал;
x k -- занято k каналов;
x n -- заняты все п каналов.
Данные состояния системы обслуживания могут быть описаны дифференциальными уравнениями Эрланга. их решение позволяет получить формулы для расчета вероятностей, которые для установившегося режима постоянны. Такой режим наступает при времени t® ¥ .
Коэффициент определяют как
где М(Тоб) - математическое ожидание времени обслуживания одной заявки.
Формулы Эрланга получены для случая экспоненциального распределения времени обслуживания, но справедливы и при любом другом законе, лишь бы поток заявок был простейшим.
Вероятность необслуживания заявки определяется как
q
Среднюю долю времени, которое система обслуживания будет простаивать, можно определить вероятностью состояния x 0 , т.е.
Р простоя = р(х 0) = р 0
Пример. Пусть на участок ремонта технологического оборудования поступают приборы со средней плотностью l = 2 ед/ч. Среднее время обслуживания одной единицы оборудования равно 24 мин (0,4 ч.). Заявка, заставшая все каналы занятыми получает отказ в обслуживании.
Требуется определить характеристики СМО в предположении наличия одного рабочего места. Кроме того, требуется установить, как меняются характеристики СМО при введении второго рабочего места.
Решение. По условию задачи имеем СМО с отказом. Будем предполагать, что поток заявок, поступающих в СМО, простейший со средней плотностью l.
1. Подсчитаем коэффициент загрузки канала или приведенную плотность заявок
2. Найдем характеристики СМО при числе каналов n= 1. Вероятность необслуживания заявок:
Относительная пропускная способность q определится, как
q=1- Р необ = 1 – 0,44 = 0,56.
Следовательно, примерно 56% заявок, поступивших в СМО, будут обслужены.
Вероятность простоя канала р 0
Рассмотренный в предыдущей лекции марковский случайный процесс с дискретными состояниями и непрерывным временем имеет место в системах массового обслуживания (СМО).
Системы массового обслуживания – это такие системы, в которые в случайные моменты времени поступают заявки на обслуживание, при этом поступившие заявки обслуживаются с помощью имеющихся в распоряжении системы каналов обслуживания.
Примерами систем массового обслуживания могут служить:
Узлы |
Требования |
|
Больница |
Санитары |
Пациенты |
Производство |
||
Аэропорт |
Выходы на взлетно-посадочные полосы Пункты регистрации |
Пассажиры |
Рассмотрим схему работы СМО (рис. 1). Система состоит из генератора заявок, диспетчера и узла обслуживания, узла учета отказов (терминатора, уничтожителя заявок). Узел обслуживания в общем случае может иметь несколько каналов обслуживания.
Кроме этих основных элементов в СМО в некоторых источниках выделяются также следующие составляющие:
терминатор – уничтожитель трансактов;
склад – накопитель ресурсов и готовой продукции;
счет бухгалтерского учета – для выполнения операций типа «проводка»;
менеджер – распорядитель ресурсов;
Первое деление (по наличию очередей):
В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не обслуживается.
В СМО с очередью заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает возможности быть обслуженной.
СМО с очередями подразделяются на разные виды в зависимости от того, как организована очередь, – ограничена или не ограничена . Ограничения могут касаться как длины очереди, так и времени ожидания, «дисциплины обслуживания».
Итак, например, рассматриваются следующие СМО:
Типы ограничения очереди могут быть комбинированными.
Другая классификация делит СМО по источнику заявок. Порождать заявки (требования) может сама система или некая внешняя среда, существующая независимо от системы.
Естественно, поток заявок, порожденный самой системой, будет зависеть от системы и ее состояния.
Кроме этого СМО делятся на открытые СМО и замкнутые СМО.
В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии сама СМО (сколько каналов занято). В замкнутой СМО – зависят. Например, если один рабочий обслуживает группу станков, время от времени требующих наладки, то интенсивность потока «требований» со стороны станков зависит от того, сколько их уже исправно и ждет наладки.
Пример замкнутой системы: выдача кассиром зарплаты на предприятии.
По количеству каналов СМО делятся на:
Основными характеристиками системы массового обслуживания любого вида являются:
Для описания входного потока требуется задать вероятностный закон, определяющий последовательность моментов поступления требований на обслуживание, и указать количество таких требований в каждом очередном поступлении. При этом, как правило, оперируют понятием «вероятностное распределение моментов поступления требований». Здесь могут поступать как единичные, так и групповые требования (количество таких требований в каждом очередном поступлении ). В последнем случае обычно речь идет о системе обслуживания с параллельно-групповым обслуживанием.
А i – время поступления между требованиями – независимые одинаково распределенные случайные величины;
E(A) – среднее (МО) время поступления;
λ=1/E(A) – интенсивность поступления требований;
Характеристики входного потока:
Очередь – совокупность требований, ожидающих обслуживания.
Очередь имеет имя.
Дисциплина очереди определяет принцип, в соответствии с которым поступающие на вход обслуживающей системы требования подключаются из очереди к процедуре обслуживания. Чаще всего используются дисциплины очереди, определяемые следующими правилами:
first in first out (FIFO)
самый распространенный тип очереди.
Какая структура данных подойдет для описания такой очереди? Массив плох (ограничен). Можно использовать структуру типа СПИСОК.
Список имеет начало и конец. Список состоит из записей. Запись – это ячейка списка. Заявка поступает в конец списка, а выбирается на обслуживание из начала списка. Запись состоит из характеристики заявки и ссылки (указатель, за кем стоит). Кроме этого, если очередь с ограничением на время ожидания, то еще должно быть указано предельное время ожидания.
Вы как программисты должны уметь делать списки двусторонние, односторонние.
Действия со списком:
Структура, известная как СТЕК. Может быть описан структурой массив или список;
Каждая заявка характеризуется помимо прочего уровнем приоритета и при поступлении помещается не в хвост очереди, а в конец своей приоритетной группы. Диспетчер осуществляет сортировку по приоритету.
Механизм обслуживания определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. К характеристикам процедуры обслуживания относятся:
Для аналитического описания характеристик процедуры обслуживания оперируют понятием «вероятностное распределение времени обслуживания требований».
S i – время обслуживания i -го требования;
E(S) – среднее время обслуживания;
μ=1/E(S) – скорость обслуживания требований.
Следует отметить, что время обслуживания заявки зависит от характера самой заявки или требований клиента и от состояния и возможностей обслуживающей системы. В ряде случаев приходится также учитывать вероятность выхода из строя обслуживающего канала по истечении некоторого ограниченного интервала времени. Эту характеристику можно моделировать как поток отказов, поступающий в СМО и имеющий приоритет перед всеми другими заявками.
Коэффициент использования СМО
N ·μ – скорость обслуживания в системе, когда заняты все устройства обслуживания.
ρ=λ/(N μ) – называется коэффициентом использования СМО , показывает, насколько задействованы ресурсы системы.
Структура обслуживающей системы определяется количеством и взаимным расположением каналов обслуживания (механизмов, приборов и т. п.). Прежде всего следует подчеркнуть, что система обслуживания может иметь не один канал обслуживания, а несколько; система такого рода способна обслуживать одновременно несколько требований. В этом случае все каналы обслуживания предлагают одни и те же услуги, и, следовательно, можно утверждать, что имеет место параллельное обслуживани .
Пример. Кассы в магазине.
Система обслуживания может состоять из нескольких разнотипных каналов обслуживания, через которые должно пройти каждое обслуживаемое требование, т. е. в обслуживающей системе процедуры обслуживания требований реализуются последовательно . Механизм обслуживания определяет характеристики выходящего (обслуженного) потока требований.
Пример. Медицинская комиссия.
Комбинированное обслуживание – обслуживание вкладов в сберкассе: сначала контролер, потом кассир. Как правило, 2 контролера на одного кассира.
Итак, функциональные возможности любой системы массового обслуживания определяются следующими основными факторами :
В качестве основных критериев эффективности функционирования систем массового обслуживания в зависимости от характера решаемой задачи могут выступать:
Очевидно, что Р обсл + P отк =1.
Задержка – один из критериев обслуживания СМО, время проведенное заявкой в ожидании обслуживания.
D i – задержка в очереди требования i ;
W i =D i +S i – время нахождения в системе требования i .
(с вероятностью 1) – установившаяся средняя задержка требования в очереди;
(с вероятностью 1) – установившееся среднее время нахождения требования в СМО (waiting).
Q(t) – число требований в очереди в момент времени t;
L(t) – число требований в системе в момент времени t (Q(t) плюс число требований, которые находятся на обслуживании в момент времени t.
Тогда показатели (если существуют)
(с вероятностью 1) – установившееся среднее по времени число требований в очереди;
(с вероятностью 1) – установившееся среднее по времени число требований в системе.
Заметим, что ρ<1 – обязательное условие существования d, w, Q и L в системе массового обслуживания.
Если вспомнить, что ρ= λ/(N μ), то видно, что если интенсивность поступления заявок больше, чем N μ, то ρ>1 и естественно, что система не сможет справиться с таким потоком заявок, а следовательно, нельзя говорить о величинах d, w, Q и L.
К наиболее общим и нужным результатам для систем массового обслуживания относятся уравнения сохранения
Следует обратить внимание, что упомянутые выше критерии оценки работы системы могут быть аналитически вычислены для систем массового обслуживания M/M/N (N >1), т. е. систем с Марковскими потоками заявок и обслуживания. Для М/G/ l при любом распределении G и для некоторых других систем. Вообще распределение времени между поступлениями, распределение времени обслуживания или обеих этих величин должно быть экспоненциальным (или разновидностью экспоненциального распределения Эрланга k-го порядка), чтобы аналитическое решение стало возможным.
Кроме этого можно также говорить о таких характеристиках, как:
Еще один интересный (и наглядный) пример аналитического решения – вычисление установившейся средней задержки в очереди для системы массового обслуживания M/G/ 1 по формуле:
.
В России эта формула известна как формула Поллачека– Хинчина, за рубежом эта формула связывается с именем Росса (Ross).
Таким образом, если E(S) имеет большее значение, тогда перегрузка (в данном случае измеряемая как d ) будет большей; чего и следовало ожидать. По формуле можно обнаружить и менее очевидный факт: перегрузка также увеличивается, когда изменчивость распределения времени обслуживания возрастает, даже если среднее время обслуживания остается прежним. Интуитивно это можно объяснить так: дисперсия случайной величины времени обслуживания может принять большое значение (поскольку она должна быть положительной), т. е. единственное устройство обслуживания будет занято длительное время, что приведет к увеличению очереди.
Предметом теории массового обслуживания является установление зависимости между факторами, определяющими функциональные возможности системы массового обслуживания, и эффективностью ее функционирования. В большинстве случаев все параметры, описывающие системы массового обслуживания, являются случайными величинами или функциями, поэтому эти системы относятся к стохастическим системам.
Случайный характер потока заявок (требований), а также, в общем случае, и длительности обслуживания приводит к тому, что в системе массового обслуживания происходит случайный процесс. По характеру случайного процесса , происходящего в системе массового обслуживания (СМО), различают системы марковские и немарковские . В марковских системах входящий поток требований и выходящий поток обслуженных требований (заявок) являются пуассоновскими. Пуассоновские потоки позволяют легко описать и построить математическую модель системы массового обслуживания. Данные модели имеют достаточно простые решения, поэтому большинство известных приложений теории массового обслуживания используют марковскую схему. В случае немарковских процессов задачи исследования систем массового обслуживания значительно усложняются и требуют применения статистического моделирования, численных методов с использованием ЭВМ.