Моделирование систем массового обслуживания
1.3.1. Компоненты и классификация моделей массового обслуживания
Системы массового обслуживания ЁC это такие системы, в которые в случайные моменты времени поступают заявки на обслуживание, при этом поступившие заявки обслуживаются с помощью имеющихся в распоряжении системы каналов обслуживания.
С позиции моделирования процесса массового обслуживания ситуации, когда образуются очереди заявок (требований) на обслуживание, возникают следующим образом. Поступив в обслуживающую систему, требование присоединяется к очереди других (ранее поступивших) требований. Канал обслуживание выбирает требование из находящихся в очереди, с тем чтобы приступить к его обслуживанию. После завершения процедуры обслуживания очередного требования канал обслуживании приступает к обслуживанию следующего требования, если таковое имеется в блоке ожидания.
Цикл функционирования системы массового обслуживания подобного рода повторяется многократно в течение всего периода работы обслуживающей системы. При этом предполагается, что переход системы на обслуживание очередного требования после завершения обслуживания предыдущего требования происходит мгновенно, в случайные моменты времени.
Примерами систем массового обслуживания могут служить: посты технического обслуживания автомобилей; посты ремонта автомобилей; персональные компьютеры, обслуживающие поступающие заявки или требования на решение тех или иных задач; станции технического обслуживания автомобилей; аудиторские фирмы; отделы налоговых инспекций, занимающиеся приемкой и проверкой текущей отчетности предприятий; телефонные станции и т. д.
Основными компонентами системы массового обслуживания любого вида являются: входной поток поступающих требований или заявок на обслуживание; дисциплина очереди; механизм обслуживания.
Входной поток требований. Для описания входного потока требуется задать вероятностный закон, определяющий последовательность моментов поступления требований на обслуживание и указать количество таких требований в каждом очередном поступлении.
Дисциплина очереди определяет принцип, в соответствии с которым поступающие на вход обслуживающей системы требования подключаются из очереди к процедуре обслуживания. Чаще всего используются дисциплины очереди, определяемые следующими правилами: первым пришел ЁC первый обслуживаешься; пришел последним ЁC обслуживаешься первым; случайный отбор заявок; отбор заявок по критерию приоритетности; ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая длина очереди»).
Механизм обслуживания определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. К характеристикам процедуры обслуживания относятся: продолжительность процедуры обслуживания; количество требований, удовлетворяемых в результате выполнения каждой такой процедуры; вероятность выхода обслуживающего прибора по истечении некоторого ограниченного интервала времени.
Структура обслуживающей системы определяется количеством и взаимным расположением каналов обслуживания (механизмов, приборов и т. п.). Прежде всего следует подчеркнуть, что система обслуживания может иметь не один канал обслуживания, а несколько. Система такого рода способна обслуживать одновременно несколько требований. В этом случае все каналы обслуживания предлагают одни и те же услуги, и, следовательно, можно утверждать, что имеет место параллельное обслуживание.
Система обслуживания может состоять из нескольких разнотипных каналов обслуживания, через которые должно пройти каждое обслуживаемое требование, т. е. в обслуживающей системе процедуры обслуживания требований реализуются последовательно. Механизм обслуживания определяет характеристики выходящего (обслуженного) потока требований.
Рассмотрев основные компоненты систем обслуживания, можно констатировать, что функциональные возможности любой системы массового обслуживания определяются следующими основными факторами:
вероятностным распределением моментов поступлений заявок на обслуживание (единичных или групповых);
вероятностным распределением времени продолжительности обслуживания;
конфигурацией обслуживающей системы (параллельное, последовательное или параллельно-последовательное обслуживание);
количеством и производительностью обслуживающих каналов;
дисциплиной очереди;
мощностью источника требований.
В качестве основных критериев эффективности функционирования систем массового обслуживания в зависимости от характера решаемой задачи могут выступать:
вероятность немедленного обслуживания поступившей заявки;
вероятность отказа в обслуживании поступившей заявки;
относительная и абсолютная пропускная способность системы;
средний процент заявок, получивших отказ в обслуживании;
среднее время ожидания в очереди;
средняя длина очереди;
средний доход от функционирования системы в единицу времени и т.п.
Предметом теории массового обслуживания является установление зависимости между факторами, определяющими функциональные возможности системы массового обслуживания, и эффективностью ее функционирования. В большинстве случаев все параметры, описывающие системы массового обслуживания, являются случайными величинами или функциями, поэтому эти системы относятся к стохастическим системам.
Случайный характер потока заявок (требований), а также, в общем случае, и длительности обслуживания приводит к тому, что в системе массового обслуживания происходит случайный процесс. По характеру случайного процесса, происходящего в системе массового обслуживания (СМО), различают системы марковские и немарковские. В марковских системах входящий поток требований и выходящий поток обслуженных требований (заявок) являются пуассоновскими. Пуассоновские потоки позволяют легко описать и построить математическую модель системы массового обслуживания. Данные модели имеют достаточно простые решения, поэтому большинство известных приложений теории массового обслуживания используют марковскую схему. В случае немарковских процессов задачи исследования систем массового обслуживания значительно усложняются и требуют применения статистического моделирования, численных методов с использованием ЭВМ.
Независимо от характера процесса, протекающего в системе массового обслуживания, различают два основных вида СМО:
системы с отказами, в которых заявка, поступившая в систему в момент, когда все каналы заняты, получает отказ и сразу же покидает очередь;
системы с ожиданием (очередью), в которых заявка, поступившая в момент, когда все каналы обслуживания заняты, становится в очередь и ждет, пока не освободится один из каналов.
Системы массового обслуживания с ожиданием делятся на системы с ограниченным ожиданием и системы с неограниченным ожиданием.
В системах с ограниченным ожиданием может ограничиваться: длина очереди; время пребывания в очереди.
В системах с неограниченным ожиданием заявка, стоящая в очереди, ждет обслуживание неограниченно долго, т.е. пока не подойдет очередь.
Все системы массового обслуживания различают по числу каналов обслуживания: одноканальные системы; многоканальные системы.
Приведенная классификация СМО является условной. На практике чаще всего системы массового обслуживания выступают в качестве смешанных систем. Например, заявки ожидают начала обслуживания до определенного момента, после чего система начинает работать как система с отказами.
Определение характеристик систем массового обслуживания
Простейшей одноканальной моделью с вероятностными входным потоком и процедурой обслуживания является модель, характеризуемая показательным распределением как длительностей интервалов между поступлениями требований, так и длительностей обслуживания. При этом плотность распределения длительностей интервалов между поступлениями требований имеет вид:
µ §
гдеµ § - интенсивность поступления заявок в систему.
Плотность распределения длительностей обслуживания:
µ §
где µ §- интенсивность обслуживания.
Потоки заявок и обслуживаний простейшие. Система работает с отказами.
Данная система массового обслуживания может быть представлена в виде графа (рис. 1.13), у которого имеются два состояния:
S0 - канал свободен (ожидание);
S1 - канал занят (идет обслуживание заявки).
µ §
µ §µ §
µ §
Рис. 1.13. Граф состояний одноканальной СМО с отказами
Обозначим вероятности состояний:
P0(t) ЎЄ вероятность состояния «канал свободен»;
P1(t) ЎЄ вероятность состояния «канал занят».
P0(t) + P1(t) = 1
µ §
µ §
µ §Для одноканальной СМО с отказами вероятность P0(t) есть не что иное, как относительная пропускная способность системы q. Действительно, P0ЎЄ вероятность того, что в момент t канал свободен и заявка, пришедшая к моменту t, будет обслужена, а следовательно, для данного момента времени t среднее отношение числа обслуженных заявок к числу поступивших также равно P0(t), т.е.
µ §По истечении большого интервала времени (при µ §) достигается стационарный (установившийся) режим:
µ §Зная относительную пропускную способность, можно найти абсолютную. Абсолютная пропускная способность (А) ЁC среднее число заявок, которое может обслужить система массового обслуживания в единицу времени:
Вероятность отказа в обслуживании заявки будет равна вероятности состояния «канал занят»:
µ §
Данная величина Pотк может быть интерпретирована как средняя доля необслуженных заявок среди поданных.
Пример 1.9. Пусть одноканальная СМО с отказами представляет собой один пост ежедневного обслуживания (ЕО) для мойки автомобилей. Заявка ЁC автомобиль, прибывший в момент, когда пост занят ЁC получает отказ в обслуживании. Интенсивность потока автомобилей µ § (автомобиль в час). Средняя продолжительность обслуживания - 1,8 часа. Поток автомобилей и поток обслуживаний являются простейшими.
Требуется определить в установившемся режиме предельные значения: относительной пропускной способности q; абсолютной пропускной способности А; вероятности отказа Pотк.
Необходимо сравнить фактическую пропускную способность СМО с номинальной, которая была бы, если бы каждый автомобиль обслуживался точно 1,8 часа и автомобили следовали один за другим без перерыва.
Решение
1. Определим интенсивность потока обслуживания:
µ §
2. Вычислим относительную пропускную способность:
µ §
Величина q означает, что в установившемся режиме система будет обслуживать примерно 35% прибывающих на пост ЕО автомобилей.
3. Абсолютную пропускную способность определим по формуле:
µ §
Это означает, что система (пост ЕО) способна осуществить в среднем 0,356 обслуживания автомобилей в час.
3. Вероятность отказа:
µ §
Это означает, что около 65% прибывших автомобилей на пост EO получат отказ в обслуживании.
4. Определим номинальную пропускную способность системы (автомобилей в час):
µ §
Оказывается, что в Аном в 1,5 разаµ § больше, чем фактическая пропускная способность, вычисленная с учетом случайного характера потока заявок и времени обслуживания.
Рассмотрим одноканальную СМО с ожиданием.
Система массового обслуживания имеет один канал. Входящий поток заявок - простейший поток с интенсивностью µ §. Интенсивность потока обслуживания равна µ § (т. е. в среднем непрерывно занятый канал будет выдавать µ § обслуженных заявок). Длительность обслуживания ЁC случайная величина, подчиненная показательному закону распределения. Поток обслуживаний является простейшим пуассоновским потоком событий. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.
Предположим, что независимо от того, сколько требований подступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более N-требований (заявок), т. е. клиенты, не попавшие в ожидание, вынуждены обслуживаться в другом месте. Источник, порождающий заявки на обслуживание, имеет неограниченную (бесконечно большую) емкость.
Граф состояний СМО в этом случае имеет вид, показанный на рис 1.14.
µ §µ §µ §µ §µ §µ §
µ §µ §µ §µ §µ §µ §µ §
µ §µ §µ §µ §µ §µ §
Рис. 1.14. Граф состояний одноканальной СМО с ожиданием (схема гибели и размножения)
Состояния СМО имеют следующую интерпретацию:
S0 ЎЄ «канал свободен»;
S1ЎЄ «канал занят» (очереди нет);
S2 ЎЄ «канал занят» (одна заявка стоит в очереди);
ЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK
SnЎЄ «канал занят» (n ЎЄ 1 заявок стоит в очереди);
ЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK
SN ЎЄ «канал занят» (N ЎЄ 1 заявок стоит в очереди).
Стационарный процесс в системе будет описываться системой алгебраических уравнений, решение которой для модели СМО имеет вид:
µ §
µ §
где
Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N- 1):
вероятность отказа в обслуживании заявки:
µ §
относительная пропускная способность системы:
µ §
µ §абсолютная пропускная способность:
среднее число находящихся в системе заявок:
µ §
µ §среднее время пребывания заявки в системе:
µ §средняя продолжительность пребывания клиента (заявки) в очереди:
µ §среднее число заявок (клиентов) в очереди (длина очереди)
Рассмотрим пример одноканальной СМО с ожиданием.
Пример 1.10. Специализированный пост диагностики представляет собой одноканальную СМО. Число стоянок для автомобилей, ожидающих проведения диагностики, ограниченно и равно 3 [(N-1) = 3]. Если все стоянки заняты, т. е. в очереди уже находится три автомобиля, то очередной автомобиль, прибывший на диагностику, в очередь на обслуживание не становится. Поток автомобилей, прибывающих на диагностику, распределен по закону Пуассона и имеет интенсивность µ § = 0,85 (автомобиля в час). Время диагностики автомобиля распределено по показательному закону и в среднем равно 1,05 час.
Требуется определить вероятностные характеристики поста диагностики, работающего в стацио
нарном режиме.
Решение
Параметр потока обслуживаний автомобилей:
µ §
2. Приведенная интенсивность потока автомобилей определяется как отношение интенсивностей µ §иµ §, т. е.
µ §
3. Вычислим финальные вероятности системы:
µ §
µ §
4. Вероятность отказа в обслуживании автомобиля:
µ §
5. Относительная пропускная способность поста диагностики:
µ §
Абсолютная пропускная способность поста диагностики (автомобиля в час)
µ §
7. Среднее число автомобилей, находящихся на обслуживании и в очереди (т.е. в системе массового обслуживания):
µ §
8. Среднее время пребывания автомобиля в системе (час):
µ §
Средняя продолжительность пребывания заявки в очереди на обслуживание (час):
µ §
10. Среднее число заявок в очереди (длина очереди):
µ §
Работу рассмотренного поста диагностики можно считать удовлетворительной, так как пост диагностики не обслуживает автомобили в среднем в 15,8% случаев (µ §).
Рассмотрим одноканальную СМО с ожиданием без ограничения на вместимость блока ожидания (т. е. µ §). Остальные условия функционирования СМО остаются без изменений.
Характеристики одноканальной СМО с ожиданием, без ограничения на длину очереди, следующие:
µ §среднее число находящихся в системе клиентов (заявок) на обслуживание:
|
