Ниже будут рассмотрены примеры простейших систем массового обслуживания (СМО). Понятие «простейшие» не означает «элементарные». Математические модели этих систем применимы и успешно используются в практических расчетах.
Одноканальная смо с отказами
Дано : система имеет один канал обслуживания, на который поступает простейший поток заявок с интенсивностью. Поток обслуживаний имеет интенсивность. Заявка, заставшая систему занятой, сразу же покидает ее.
Найти : абсолютную и относительную пропускную способность СМО и вероятность того, что заявка, пришедшая в момент времени t, получит отказ.
Система при любом t > 0 может находиться в двух состояниях:S 0 – канал свободен;S 1 – канал занят. Переход изS 0 вS 1 связан с появлением заявки и немедленным началом ее обслуживания. Переход изS 1 вS 0 осуществляется, как только очередное обслуживание завершится (рис.4).
Рис.4. Граф состояний одноканальной СМО с отказами
Выходные характеристики (характеристики эффективности) этой и других СМО будут даваться без выводов и доказательств.
Абсолютная пропускная способность (среднее число заявок, обслуживаемых в единицу времени):
где – интенсивность потока заявок (величина, обратная среднему промежутку времени между поступающими заявками -);
–интенсивность потока обслуживаний (величина, обратная среднему времени обслуживания )
Относительная пропускная способность (средняя доля заявок, обслуживаемых системой):
Вероятность отказа (вероятность того, что заявка покинет СМО необслуженной):
Очевидны следующие соотношения: и.
Пример . Технологическая система состоит из одного станка. На станок поступают заявки на изготовление деталей в среднем через 0,5 часа. Среднее время изготовления одной детали равно. Если при поступлении заявки на изготовление детали станок занят, то она (деталь) направляется на другой станок. Найти абсолютную и относительную пропускную способности системы и вероятность отказа по изготовлению детали.
Т.е. в среднем примерно 46 % деталей обрабатываются на этом станке.
.
Т.е. в среднем примерно 54 % деталей направляются на обработку на другие станки.
N – канальная смо с отказами (задача Эрланга)
Это одна из первых задач теории массового обслуживания. Она возникла из практических нужд телефонии и была решена в начале 20 века датским математиком Эрлангом.
Дано : в системе имеетсяn – каналов, на которые поступает поток заявок с интенсивностью. Поток обслуживаний имеет интенсивность. Заявка, заставшая систему занятой, сразу же покидает ее.
Найти : абсолютную и относительную пропускную способность СМО; вероятность того, что заявка, пришедшая в момент времениt , получит отказ; среднее число заявок, обслуживаемых одновременно (или, другими словам, среднее число занятых каналов).
Решение . Состояние системыS (СМО) нумеруется по максимальному числу заявок, находящихся в системе (оно совпадает с числом занятых каналов):
S 0 – в СМО нет ни одной заявки;
S 1 – в СМО находится одна заявка (один канал занят, остальные свободны);
S 2 – в СМО находится две заявки (два канала заняты, остальные свободны);
S n – в СМО находитсяn – заявок (всеn – каналов заняты).
Граф состояний СМО представлен на рис. 5
Рис.5 Граф состояний для n – канальной СМО с отказами
Почему граф состояний размечен именно так? Из состояния S 0 в состояниеS 1 систему переводит поток заявок с интенсивностью(как только приходит заявка, система переходит изS 0 вS 1). Если система находилась в состоянииS 1 и пришла еще одна заявка, то она переходит в состояниеS 2 и т.д.
Почему такие интенсивности у нижних стрелок (дуг графа)? Пусть система находится в состоянии S 1 (работает один канал). Он производитобслуживаний в единицу времени. Поэтому дуга перехода из состоянияS 1 в состояниеS 0 нагружена интенсивностью. Пусть теперь система находится в состоянииS 2 (работают два канала). Чтобы ей перейти вS 1 , нужно, чтобы закончил обслуживание первый канал, либо второй. Суммарная интенсивность их потоков равнаи т.д.
Выходные характеристики (характеристики эффективности) данной СМО определяются следующим образом.
Абсолютная пропускная способность :
где n – количество каналов СМО;
–вероятность нахождения СМО в начальном состоянии, когда все каналы свободны (финальная вероятность нахождения СМО в состоянии S 0);
Рис.6. Граф состояний для схемы «гибели и размножения»
Для того, чтобы написать формулу для определения , рассмотрим рис.6
Граф, представленный на этом рисунке, называют еще графом состояний для схемы «гибели и размножения». Напишем сначала для общую формулу (без доказательства):
Кстати, остальные финальные вероятности состояний СМО запишутся следующим образом.
S 1 , когда один канал занят:
Вероятность того, что СМО находится в состоянии S 2 , т.е. когда два канала заняты:
Вероятность того, что СМО находится в состоянии S n , т.е. когда все каналы заняты.
Теперь для n – канальной СМО с отказами
Относительная пропускная способность:
Напомним, что это средняя доля заявок, обслуживаемых системой. При этом
Вероятность отказа :
Напомним, что это вероятность того, что заявка покинет СМО необслуженной. Очевидно, что .
Среднее число занятых каналов (среднее число заявок, обслуживаемых одновременно):
Классификация, основные понятия, элементы модели, расчет основных характеристик.
При решении задач рациональной организации торговли, бытового обслуживания, складского хозяйства и т.д. весьма полезной бывает интерпретация деятельности производственной структуры как системы массового обслуживания , т.е. системы в которой, с одной стороны, постоянно возникают запросы на выполнение каких-либо работ, а с другой - происходит постоянное удовлетворение этих запросов.
Всякая СМО включает четыре элемента : входящий поток, очередь, обслуживающее устройство, выходящий поток.
Требованием (клиентом, заявкой) в СМО называется каждый отдельный запрос на выполнение какой-либо работы.
Обслуживание - это выполнение работы по удовлетворению поступившего требования. Объект, выполняющий обслуживание требований, называется обслуживающим устройством (прибором) или каналом обслуживания.
Временем обслуживания называется период, в течение которого удовлетворяется требование на обслуживание, т.е. период от начала обслуживания и до его завершения. Период от момента поступления требования в систему и до начала обслуживания называется временем ожидания обслуживания. Время ожидания обслуживания в совокупности с временем обслуживания составляет время пребывания требования в системе.
СМО классифицируются по разным признакам .
1. По числу каналов обслуживания СМО делятся на одноканальные и многоканальные.
2. В зависимости от условий ожидания требованием начала обслуживания различают СМО с потерями (отказами) и СМО с ожиданием.
В СМО с потерями требования , поступившие в момент, когда все приборы заняты обслуживанием, получают отказ, они теряются для данной системы и никакого влияния на дальнейший процесс обслуживания не оказывают. Классическим примером системы с отказами является телефонная станция - требование на соединение получает отказ, если вызываемый абонент занят.
Для системы с отказами основной характеристикой эффективности функционирования является вероятность отказа или средняя доля заявок, оставшихся необслуженными.
В СМО с ожиданием требования , поступившее в момент, когда все приборы заняты обслуживанием, не покидает систему, а становится в очередь и ожидает пока не освободится один из каналов. При освобождении очередного прибора одна из заявок, стоящих в очереди, немедленно принимается на обслуживание.
Для СМО с ожиданием основными характеристиками являются математические ожидания длины очереди и времени ожидания.
Примером системы с ожиданием может служить процесс восстановления телевизоров в ремонтной мастерской.
Встречаются системы, лежащие между указанными двумя группами (смешанные СМО ). Для них характерно наличие некоторых промежуточных условий: ограничениями могут быть ограничения по времени ожидания начала обслуживания, по длине очереди и т.п.
В качестве характеристик эффективности может применяться вероятность отказа как в системах с потерями (или характеристики времени ожидания) и в системах с ожиданием.
3. По дисциплине обслуживания СМО делятся на системы с приоритетом в обслуживании и на системы без приоритета в обслуживании.
Требования могут обслуживаться в порядке их поступления либо случайным образом, либо в зависимости от установленных приоритетов.
4. СМО могут быть однофазными и многофазными.
В однофазных системах требования обслуживаются каналами одного типа (например рабочими одной профессии) без передачи их от одного канала к другому, в многофазных системах такие передачи возможны.
5. По месту нахождения источника требований СМО делятся на разомкнутые (когда источник требования находится вне системы) и замкнутые (когда источник находится в самой системе).
К замкнутым относятся системы, в которых поступающий поток требований ограничен. Например, мастер, задачей которого является наладка станков в цехе, должен периодически их обслуживать. Каждый налаженный станок становится в будущем потенциальным источником требований на наладку. В подобных системах общее число циркулирующих требований конечно и чаще всего постоянно.
Если питающий источник обладает бесконечным числом требований, то системы называются разомкнутыми . Примерами подобных систем могут служить магазины, кассы вокзалов, портов и т.п. Для этих систем поступающий поток требований можно считать неограниченным.
Методы и модели исследования СМО можно условно разбить на аналитические и статистические (имитационного моделирования процессов массового обслуживания).
Аналитические методы позволяют получить характеристики системы как некоторые функции от параметров ее функционирования. Благодаря этому появляется возможность проводить качественный анализ влияния отдельных факторов на эффективность работы СМО.
К сожалению, аналитическому решению поддается лишь довольно ограниченный круг задач теории массового обслуживания. Несмотря на постоянно ведущуюся разработку аналитических методов, во многих реальных случаях аналитическое решение либо невозможно получить, либо итоговые зависимости оказываются настолько сложными, что их анализ становится самостоятельной трудной задачей. Поэтому ради возможности применения аналитических методов решения приходится прибегать к различным упрощающим предположениям, что в некоторой степени компенсируется возможностью применения качественного анализа итоговых зависимостей (при этом, разумеется, необходимо, чтобы принятые допущения не искажали реальной картины процесса).
В настоящее время теоретически наиболее разработаны и удобны в практических приложениях методы решения таких задач массового обслуживания, в которых поток требований является простейшим (пуассоновским ).
Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона, то есть вероятность поступления за время t, равное k требований задается формулой:
где λ - параметр потока (см. ниже).
Простейший поток обладает тремя основными свойствами: ординарностью, стационарностью и отсутствием последействия.
Ординарность потока означает практическую невозможность одновременного поступления двух и более требований. Например, достаточно малой является вероятность того, что из группы станков, обслуживаемых бригадой ремонтников, одновременно выйдут из строя несколько станков.
Стационарным называется поток , для которого математическое ожидание числа требований, поступающих в систему в единицу времени (обозначим через λ), не меняется во времени. Таким образом, вероятность поступления в систему определенного количества требований в течение заданного промежутка времени Δt зависит от его величины и не зависит от начала его отсчета на оси времени.
Отсутствие последействия означает, что число требований, поступивших в систему до момента t, не определяет того, сколько требований поступит в систему за время t + Δt.
Например, если на ткацком станке в данный момент произошел обрыв нити, и он устранен ткачихой, то это не определяет того, произойдет новый обрыв на данном станке в следующий момент или нет, тем более это не влияет на вероятность возникновения обрыва на других станках.
Важной характеристикой СМО является время обслуживания требований в системе. Время обслуживания является, как правило, случайной величиной и, следовательно, может быть описано законом распределения. Наибольшее распространение в теории и, особенно в практических приложениях, получил экспоненциальный закон. Для этого закона функция распределения вероятностей имеет вид:
F(t) = 1 – e -μt ,
т.е. вероятность того, что время обслуживания не превосходит некоторой величины t, определяется формулой (1 – e -μt), где μ -параметр экспоненциального закона времени обслуживания требований в системе - величина, обратная среднему времени обслуживания, т.е. .
Рассмотрим аналитические модели СМО с ожиданием (наиболее распространенные СМО, в которых требования, поступившие в момент, когда все обслуживающие единицы заняты, становятся в очередь и обслуживаются по мере освобождения обслуживающих единиц).
Задачи с очередями являются типичными в производственных условиях, например при организации наладочных и ремонтных работ, при многостаночном обслуживании и т.д.
Постановка задачи в общем виде выглядит следующим образом.
Система состоит из n обслуживающих каналов. Каждый из них может одновременно обслуживать только одно требование. В систему поступает простейший (пуассоновский) поток требований с параметром λ. Если в момент поступления очередного требования в системе на обслуживании уже находится не меньше n требований (т.е. все каналы заняты), то это требование становится в очередь и ждет начала обслуживания.
Время обслуживания каждого требования t об является случайной величиной, которая подчиняется экспоненциальному закону распределения с параметром μ.
Как отмечалось выше, СМО с ожиданием можно разбить на две большие группы: замкнутые и разомкнутые.
Особенности функционирования каждой из этих двух видов систем накладывают свой оттенок на используемый математический аппарат. Расчет характеристик работы СМО различного вида может быть проведен на основе расчета вероятностей состояний СМО (формулы Эрланга).
Поскольку система замкнутая, то к постановке задачи следует добавить условие: поток поступающих требований ограничен, т.е. в системе обслуживания одновременно не может находиться больше m требований (m - число обслуживаемых объектов).
В качестве основных критериев, характеризующих качество функционирования рассматриваемой системы, выберем: 1) отношение средней длины очереди к наибольшему числу требований, находящихся одновременно в обслуживающей системе -коэффициент простоя обслуживаемого объекта; 2) отношение среднего числа незанятых обслуживающих каналов к их общему числу - коэффициент простоя обслуживаемого канала.
Рассмотрим расчет необходимых вероятностных характеристик (показателей качества функционирования) замкнутой СМО.
1. Вероятность того, что в системе находится k требований при условии, когда их число не превышает числа обслуживающих аппаратов n:
P k = α k P 0 , (1 ≤ k ≤ n),
где 
λ - частота (интенсивность) поступления требований в систему от одного источника;
Средняя продолжительность обслуживания одного требования;
m - наибольшее возможное число требований, находящихся в обслуживающей системе одновременно;
n - число обслуживающих аппаратов;
Р 0 - вероятность того, что все обслуживающие аппараты свободны.
2. Вероятность того, что в системе находится k требований при условии, когда их число больше числа обслуживающих аппаратов:
P k = α k P 0 , (n ≤ k ≤ m),
где 
3. Вероятность того, что все обслуживающие аппараты свободны, определяется из условия
следовательно,
4. Среднее число требований, ожидающих начала обслуживания (средняя длина очереди):
5. Коэффициент простоя требования в ожидании обслуживания:
6. Вероятность того, что все обслуживающие аппараты заняты:
7. Среднее число требований, находящихся в обслуживающей системе (обслуживаемых и ожидающих обслуживания):
8. Коэффициент полного простоя требований на обслуживании и в ожидании обслуживания:
9. Среднее время простоя требования в очереди на обслуживание:
10. Среднее число свободных обслуживающих аппаратов:
11. Коэффициент простоя обслуживающих аппаратов:
12. Вероятность того, что число требований, ожидающих обслуживания, больше некоторого числа В (вероятность того, что в очереди на обслуживание находится более В требований):
Во многих областях экономики, финансов, производства и быта важную роль играют системы, реализующие многократное выполнение однотипных задач. Такие системы называются системами массового обслуживания (СМО). Примерами СМО являются: банки различных типов, страховые организации, налоговые инспекции, аудиторские службы, различные системы связи, погрузочно-разгрузочные комплексы, автозаправочные станции, различные предприятия и организации сферы обслуживания.
3.1.1 Общие сведения о системах массового обслуживания
Каждая СМО предназначена для обслуживания (выполнения) некоторого потока заявок (требований), поступающих на вход системы большей частью не регулярно, а в случайные моменты времени. Обслуживание заявок также длится не постоянное, заранее известное время, а случайное, которое зависит от многих случайных, порой неизвестных нам, причин. После обслуживания заявки канал освобождается и готов к приёму следующей заявки. Случайный характер потока заявок и времени их обслуживания приводит к неравномерной загруженности СМО. В некоторые промежутки времени на входе СМО могут скапливаться заявки, что приводит к перегрузке СМО, в некоторые же другие интервалы времени при свободных каналах (устройствах обслуживания) на входе СМО заявок не будет, что приводит к недогрузке СМО, т.е. к простаиванию её каналов. Заявки, скапливающиеся на входе СМО, либо «становятся» в очередь, либо по какой-то причине невозможности дальнейшего пребывания в очереди покидают СМО необслуженными.
На рис 3.1 изображена схема СМО.
Основными элементами (признаками) систем массового обслуживания являются:
Обслуживающий узел (блок),
Поток заявок,
Очередь в ожидании обслуживания (дисциплина очереди).
Обслуживающий блок предназначен для осуществления действий согласно требованиям поступающих в систему заявок.
Рис. 3.1 Схема системы массового обслуживания
Вторая составляющая систем массового обслуживания - входной поток заявок. Заявки поступают в систему случайным образом. Обычно предполагают, что входной поток подчиняется некоторому вероятностному закону для длительности интервалов между двумя последовательно поступающими заявками, причем закон распределения считается не изменяющимся в течение некоторого достаточно продолжительного времени. Источник заявок - неограничен.
Третья составляющая - дисциплина очереди . Эта характеристика описывает порядок обслуживания заявок, поступающих на вход системы. Поскольку обслуживающий блок, как правило, имеет ограниченную пропускную способность, а заявки поступают нерегулярно, то периодически создается очередь заявок в ожидании обслуживания, а иногда обслуживающая система простаивает в ожидании заявок.
Главная особенность процессов массового обслуживания – случайность. При этом имеются две взаимодействующие стороны: обслуживаемая и обслуживающая. Случайное поведение хотя бы одной из сторон приводит к случайному характеру протекания процесса обслуживания в целом. Источниками случайности взаимодействия этих двух сторон являются случайные события двух типов.
1. Появление заявки (требования) на обслуживание. Причиной случайности данного события часто является массовый характер потребности в обслуживании.
2. Окончание обслуживания очередной заявки. Причинами случайности этого события является как случайность начала обслуживания, так и случайная продолжительность самого обслуживания.
Указанные случайные события составляют систему двух потоков в СМО: входного потока заявок на обслуживание и выходного потока обслуженных заявок.
Результатом взаимодействия указанных потоков случайных событий является число находящихся в СМО заявок в данный момент, которое принято называть состоянием системы.
Каждая СМО в зависимости от своих параметров характера потока заявок, числа каналов обслуживания и их производительности, от правил организации работы, обладает определенной эффективностью функционирования (пропускной способностью), позволяющей ей успешно справляться с потоком заявок.
Специальная область прикладной математики теория массового обслуживания (ТМО) – занимается анализом процессов в системах массового обслуживания. Предметом изучения теории массового обслуживания является СМО.
Цель теории массового обслуживания выработка рекомендаций по рациональному построению СМО, рациональной организации их работы и регулированию потока заявок для обеспечения высокой эффективности функционирования СМО. Для достижения этой цели ставятся задачи теории массового обслуживания, состоящие в установлении зависимостей эффективности функционирования СМО от её организации.
Задачи теории массового обслуживания носят оптимизационный характер и в конечном счете направлены на определение такого варианта системы, при котором будет обеспечен минимум суммарных затрат от ожидания обслуживания, потерь времени и ресурсов на обслуживание и от простоя обслуживающего блока. Знание таких характеристик дает менеджеру информацию для выработки направленного воздействия на эти характеристики для управления эффективностью процессов массового обслуживания.
В качестве характеристик эффективности функционирования СМО обычно выбираются три следующие основные группы (обычно средних) показателей:
Показатели эффективности использования СМО:
Абсолютная пропускная способность СМО - среднее число заявок, которое сможет обслужить СМО в единицу времени.
Относительная пропускная способность СМО - отношение среднего числа заявок, обслуживаемых СМО в единицу времени, к среднему числу заявок поступивших за это же время.
Средняя продолжительность периода занятости СМО.
Коэффициент использования СМО - средняя доля времени, в течении которого СМО занята обслуживанием заявок, и т.п.
Показатели качества обслуживания заявок:
Среднее время ожидания заявки в очереди.
Среднее время пребывания заявки в СМО.
Вероятность отказа заявке в обслуживании без ожидания.
Вероятность того, что поступившая заявка немедленно будет принята к обслуживанию.
Закон распределения времени пребывания заявки в очереди.
Закон распределения времени пребывания заявки в СМО.
Среднее число заявок, пребывающих в очереди.
Среднее число заявок, находящихся в СМО, и т.п.
Показатели эффективности функционирования пары «СМО − потребитель», где под «потребителем» понимают всю совокупность заявок или некий их
Рассмотренный в предыдущей лекции марковский случайный процесс с дискретными состояниями и непрерывным временем имеет место в системах массового обслуживания (СМО).
Системы массового обслуживания – это такие системы, в которые в случайные моменты времени поступают заявки на обслуживание, при этом поступившие заявки обслуживаются с помощью имеющихся в распоряжении системы каналов обслуживания.
Примерами систем массового обслуживания могут служить:
- расчетно-кассовые узлы в банках, на предприятиях;
- персональные компьютеры, обслуживающие поступающие заявки или требования на решение тех или иных задач;
- станции технического обслуживания автомобилей; АЗС;
- аудиторские фирмы;
- отделы налоговых инспекций, занимающиеся приёмкой и проверкой текущей отчетности предприятий;
- телефонные станции и т. д.
Узлы |
Требования |
|
Больница |
Санитары |
Пациенты |
Производство |
||
Аэропорт |
Выходы на взлетно-посадочные полосы Пункты регистрации |
Пассажиры |
Рассмотрим схему работы СМО (рис. 1). Система состоит из генератора заявок, диспетчера и узла обслуживания, узла учета отказов (терминатора, уничтожителя заявок). Узел обслуживания в общем случае может иметь несколько каналов обслуживания.
Рис. 1
- Генератор заявок – объект, порождающий заявки: улица, цех с установленными агрегатами. На вход поступает поток заявок (поток покупателей в магазин, поток сломавшихся агрегатов (машин, станков) на ремонт, поток посетителей в гардероб, поток машин на АЗС и т. д.).
- Диспетчер – человек или устройство, которое знает, что делать с заявкой. Узел, регулирующий и направляющий заявки к каналам обслуживания. Диспетчер:
- принимает заявки;
- формирует очередь, если все каналы заняты;
- направляет их к каналам обслуживания, если есть свободные;
- дает заявкам отказ (по различным причинам);
- принимает информацию от узла обслуживания о свободных каналах;
- следит за временем работы системы.
- Очередь – накопитель заявок. Очередь может отсутствовать.
- Узел обслуживания состоит из конечного числа каналов обслуживания. Каждый канал имеет 3 состояния: свободен, занят, не работает. Если все каналы заняты, то можно придумать стратегию, кому передавать заявку.
- Отказ от обслуживания наступает, если все каналы заняты (некоторые в том числе могут не работать).
Кроме этих основных элементов в СМО в некоторых источниках выделяются также следующие составляющие:
терминатор – уничтожитель трансактов;
склад – накопитель ресурсов и готовой продукции;
счет бухгалтерского учета – для выполнения операций типа «проводка»;
менеджер – распорядитель ресурсов;
Классификация СМО
Первое деление (по наличию очередей):
- СМО с отказами;
- СМО с очередью.
В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не обслуживается.
В СМО с очередью заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает возможности быть обслуженной.
СМО с очередями подразделяются на разные виды в зависимости от того, как организована очередь, – ограничена или не ограничена . Ограничения могут касаться как длины очереди, так и времени ожидания, «дисциплины обслуживания».
Итак, например, рассматриваются следующие СМО:
- СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);
- СМО с обслуживанием с приоритетом, т. е. некоторые заявки обслуживаются вне очереди и т. д.
Типы ограничения очереди могут быть комбинированными.
Другая классификация делит СМО по источнику заявок. Порождать заявки (требования) может сама система или некая внешняя среда, существующая независимо от системы.
Естественно, поток заявок, порожденный самой системой, будет зависеть от системы и ее состояния.
Кроме этого СМО делятся на открытые СМО и замкнутые СМО.
В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии сама СМО (сколько каналов занято). В замкнутой СМО – зависят. Например, если один рабочий обслуживает группу станков, время от времени требующих наладки, то интенсивность потока «требований» со стороны станков зависит от того, сколько их уже исправно и ждет наладки.
Пример замкнутой системы: выдача кассиром зарплаты на предприятии.
По количеству каналов СМО делятся на:
- одноканальные;
- многоканальные.
Характеристики системы массового обслуживания
Основными характеристиками системы массового обслуживания любого вида являются:
- входной поток поступающих требований или заявок на обслуживание;
- дисциплина очереди;
- механизм обслуживания.
Входной поток требований
Для описания входного потока требуется задать вероятностный закон, определяющий последовательность моментов поступления требований на обслуживание, и указать количество таких требований в каждом очередном поступлении. При этом, как правило, оперируют понятием «вероятностное распределение моментов поступления требований». Здесь могут поступать как единичные, так и групповые требования (количество таких требований в каждом очередном поступлении ). В последнем случае обычно речь идет о системе обслуживания с параллельно-групповым обслуживанием.
А i – время поступления между требованиями – независимые одинаково распределенные случайные величины;
E(A) – среднее (МО) время поступления;
λ=1/E(A) – интенсивность поступления требований;
Характеристики входного потока:
- Вероятностный закон, определяющий последовательность моментов поступления требований на обслуживание.
- Количество требований в каждом очередном поступлении для групповых потоков.
Дисциплина очереди
Очередь – совокупность требований, ожидающих обслуживания.
Очередь имеет имя.
Дисциплина очереди определяет принцип, в соответствии с которым поступающие на вход обслуживающей системы требования подключаются из очереди к процедуре обслуживания. Чаще всего используются дисциплины очереди, определяемые следующими правилами:
- первым пришел – первый обслуживаешься;
first in first out (FIFO)
самый распространенный тип очереди.
Какая структура данных подойдет для описания такой очереди? Массив плох (ограничен). Можно использовать структуру типа СПИСОК.
Список имеет начало и конец. Список состоит из записей. Запись – это ячейка списка. Заявка поступает в конец списка, а выбирается на обслуживание из начала списка. Запись состоит из характеристики заявки и ссылки (указатель, за кем стоит). Кроме этого, если очередь с ограничением на время ожидания, то еще должно быть указано предельное время ожидания.
Вы как программисты должны уметь делать списки двусторонние, односторонние.
Действия со списком:
- вставить в хвост;
- взять из начала;
- удалить из списка по истечении времени ожидания.
- пришел последним - обслуживаешься первым LIFO (обойма для патронов, тупик на железнодорожной станции, зашел в набитый вагон).
Структура, известная как СТЕК. Может быть описан структурой массив или список;
- случайный отбор заявок;
- отбор заявок по критерию приоритетности.
Каждая заявка характеризуется помимо прочего уровнем приоритета и при поступлении помещается не в хвост очереди, а в конец своей приоритетной группы. Диспетчер осуществляет сортировку по приоритету.
Характеристики очереди
- ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая длина очереди»);
- длина очереди.
Механизм обслуживания
Механизм обслуживания определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. К характеристикам процедуры обслуживания относятся:
- количество каналов обслуживания (N );
- продолжительность процедуры обслуживания (вероятностное распределение времени обслуживания требований);
- количество требований, удовлетворяемых в результате выполнения каждой такой процедуры (для групповых заявок);
- вероятность выхода из строя обслуживающего канала;
- структура обслуживающей системы.
Для аналитического описания характеристик процедуры обслуживания оперируют понятием «вероятностное распределение времени обслуживания требований».
S i – время обслуживания i -го требования;
E(S) – среднее время обслуживания;
μ=1/E(S) – скорость обслуживания требований.
Следует отметить, что время обслуживания заявки зависит от характера самой заявки или требований клиента и от состояния и возможностей обслуживающей системы. В ряде случаев приходится также учитывать вероятность выхода из строя обслуживающего канала по истечении некоторого ограниченного интервала времени. Эту характеристику можно моделировать как поток отказов, поступающий в СМО и имеющий приоритет перед всеми другими заявками.
Коэффициент использования СМО
N ·μ – скорость обслуживания в системе, когда заняты все устройства обслуживания.
ρ=λ/(N μ) – называется коэффициентом использования СМО , показывает, насколько задействованы ресурсы системы.
Структура обслуживающей системы
Структура обслуживающей системы определяется количеством и взаимным расположением каналов обслуживания (механизмов, приборов и т. п.). Прежде всего следует подчеркнуть, что система обслуживания может иметь не один канал обслуживания, а несколько; система такого рода способна обслуживать одновременно несколько требований. В этом случае все каналы обслуживания предлагают одни и те же услуги, и, следовательно, можно утверждать, что имеет место параллельное обслуживани .
Пример. Кассы в магазине.
Система обслуживания может состоять из нескольких разнотипных каналов обслуживания, через которые должно пройти каждое обслуживаемое требование, т. е. в обслуживающей системе процедуры обслуживания требований реализуются последовательно . Механизм обслуживания определяет характеристики выходящего (обслуженного) потока требований.
Пример. Медицинская комиссия.
Комбинированное обслуживание – обслуживание вкладов в сберкассе: сначала контролер, потом кассир. Как правило, 2 контролера на одного кассира.
Итак, функциональные возможности любой системы массового обслуживания определяются следующими основными факторами :
- вероятностным распределением моментов поступлений заявок на обслуживание (единичных или групповых);
- мощностью источника требований;
- вероятностным распределением времени продолжительности обслуживания;
- конфигурацией обслуживающей системы (параллельное, последовательное или параллельно-последовательное обслуживание);
- количеством и производительностью обслуживающих каналов;
- дисциплиной очереди.
Основные критерии эффективности функционирования СМО
В качестве основных критериев эффективности функционирования систем массового обслуживания в зависимости от характера решаемой задачи могут выступать:
- вероятность немедленного обслуживания поступившей заявки (Р обсл =К обс /К пост);
- вероятность отказа в обслуживании поступившей заявки (P отк =К отк /К пост);
Очевидно, что Р обсл + 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 ) будет большей; чего и следовало ожидать. По формуле можно обнаружить и менее очевидный факт: перегрузка также увеличивается, когда изменчивость распределения времени обслуживания возрастает, даже если среднее время обслуживания остается прежним. Интуитивно это можно объяснить так: дисперсия случайной величины времени обслуживания может принять большое значение (поскольку она должна быть положительной), т. е. единственное устройство обслуживания будет занято длительное время, что приведет к увеличению очереди.
Предметом теории массового обслуживания является установление зависимости между факторами, определяющими функциональные возможности системы массового обслуживания, и эффективностью ее функционирования. В большинстве случаев все параметры, описывающие системы массового обслуживания, являются случайными величинами или функциями, поэтому эти системы относятся к стохастическим системам.
Случайный характер потока заявок (требований), а также, в общем случае, и длительности обслуживания приводит к тому, что в системе массового обслуживания происходит случайный процесс. По характеру случайного процесса , происходящего в системе массового обслуживания (СМО), различают системы марковские и немарковские . В марковских системах входящий поток требований и выходящий поток обслуженных требований (заявок) являются пуассоновскими. Пуассоновские потоки позволяют легко описать и построить математическую модель системы массового обслуживания. Данные модели имеют достаточно простые решения, поэтому большинство известных приложений теории массового обслуживания используют марковскую схему. В случае немарковских процессов задачи исследования систем массового обслуживания значительно усложняются и требуют применения статистического моделирования, численных методов с использованием ЭВМ.
