Общие понятия систем массового обслуживания

Моделирование систем массового обслуживания

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

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

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

Примерами систем массового обслуживания могут служить:

- посты технического обслуживания автомобилей;

- посты ремонта автомобилей;

- персональные компьютеры, обслуживающие поступающие заявки или требования на решение тех или иных задач;

- станции технического обслуживания автомобилей;

- аудиторские фирмы;

- отделы налоговых инспекций, занимающиеся приемкой и проверкой текущей отчетности предприятий;

- телефонные станции и т. д.

Основными компонентами системы массового обслуживания лю­бого вида являются:

• входной поток поступающих требований или заявок на обслужи­вание;

• дисциплина очереди;

• механизм обслуживания.

Входной поток требований. Для описания входного потока тре­буется задать вероятностный закон, определяющий последователь­ность моментов поступления требований на обслуживание и ука­зать количество таких требований в каждом очередном поступле­нии. При этом, как правило, оперируют понятием «вероятностное распределение моментов поступления требований». Здесь могут поступать как единичные, так и групповые требования (требования поступают группами в систему). В последнем случае обычно речь идет о системе обслуживания с параллельно-групповым обслужи­ванием.

Дисциплина очереди — это важный компонент системы массово­го обслуживания, он определяет принцип, в соответствии с кото­рым поступающие на вход обслуживающей системы требования подключаются из очереди к процедуре обслуживания. Чаще всего используются дисциплины очереди, определяемые следующими правилами:

- первым пришел — первый обслуживаешься;

- пришел последним — обслуживаешься первым;

- случайный отбор заявок;

- отбор заявок по критерию приоритетности;

- ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания
обслуживания, что ассоциируется с понятием «допустимая дли­на очереди»).

Механизм обслуживания определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. К характеристикам процедуры обслуживания относятся: продол­жительность процедуры обслуживания и количество требований, удовлетворяемых в результате выполнения каждой такой процеду­ры. Для аналитического описания характеристик процедуры обслу­живания оперируют понятием «вероятностное распределение вре­мени обслуживания требований».

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

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

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

Рассмотрев основные компоненты систем обслуживания, мож­но констатировать, что функциональные возможности любой систе­мы массового обслуживания определяются следующими основными факторами:

- вероятностным распределением моментов поступлений заявок
на обслуживание (единичных или групповых);

- вероятностным распределением времени продолжительности об­служивания;

- конфигурацией обслуживающей системы (параллельное, после­довательное или параллельно-последовательное обслуживание);

- количеством и производительностью обслуживающих каналов;

- дисциплиной очереди;

- мощностью источника требований.

В качестве основных критериев эффективности функционирова­ния систем массового обслуживания в зависимости от характера ре­шаемой задачи могут выступать:

- вероятность немедленного обслуживания поступившей заявки;

- вероятность отказа в обслуживании поступившей заявки;

- относительная и абсолютная пропускная способность системы;

- средний процент заявок, получивших отказ в обслуживании;

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

- средняя длина очереди;

- средний доход от функционирования системы в единицу времени и т.п.

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

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

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

- системы с отказами, в которых заявка, поступившая в систему в
момент, когда все каналы заняты, получает отказ и сразу же по­кидает очередь;

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

Системы массового обслуживания с ожиданием делятся на си­стемы с ограниченным ожиданием и системы с неограниченным ожиданием.

В системах с ограниченным ожиданием может ограничиваться:

- длина очереди;

- время пребывания в очереди.

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

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

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

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

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

4.2 Одноканальная модель с пуассоновским входным потоком с экспоненциальным распределением длительности обслуживания

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

(1)

где λ. — интенсивность поступления заявок в систему.

Плотность распределения длительностей обслуживания:

(2)

где μ - интенсивность обслуживания.

Потоки заявок и обслуживании простейшие.

Пусть система работает с отказами. Необходимо определить абсолютную и относительную пропускную способность системы.

Представим данную систему массового обслуживания в виде графа (рис. 4.1), у которого имеются два состояния:

S₀ — канал свободен (ожидание);

S₁ — канал занят (идет обслуживание заявки).

Рисунок 4.1 – Граф состояний одноканальной СМО с отказами

Обозначим вероятности состояний:

P₀(t) — вероятность состояния «канал свободен»;

P₁(t) — вероятность состояния «канал занят».

По размеченному графу состояний (рис. 1) составим систему дифференциальных уравнений Колмогорова для вероятностей стояний:

(3)

Система линейных дифференциальных уравнений имеет решение с учетом нормировочного условия P₀(t) + P₁(t) = 1. Реше­ние данной системы называется неустановившимся, поскольку оно непосредственно зависит от t и выглядит следующим образом:

(4) (5)

Нетрудно убедиться, что для одноканальной СМО с отказами вероятность P₀(t) есть не что иное, как относительная пропускная способность системы q.

Действительно, P₀ — вероятность того, что в момент t канал сво­боден и заявка, пришедшая к моменту t, будет обслужена, а следо­вательно, для данного момента времени t среднее отношение числа обслуженных заявок к числу поступивших также равно P₀(t), т. е.

(6)

По истечении большого интервала времени (при t → ∞) дости­гается стационарный (установившийся) режим:

(7)

Зная относительную пропускную способность, легко найти аб­солютную. Абсолютная пропускная способность (А) — среднее чис­ло заявок, которое может обслужить система массового обслужива­ния в единицу времени:

(8)

Вероятность отказа в обслуживании заявки будет равна вероят­ности состояния «канал занят»:

(9)

Данная величина P _отк может быть интерпретирована как сред­няя доля не обслуженных заявок среди поданных.

Пример 1. Пусть одноканальная СМО с отказами представля­ет собой один пост ежедневного обслуживания (ЕО) для мойки ав­томобилей. Заявка — автомобиль, прибывший в момент, когда пост занят, — получает отказ в обслуживании. Интенсивность потока ав­томобилей λ = 1,0 (автомобиль в час). Средняя продолжительность обслуживания — 1,8 часа. Поток автомобилей и поток обслужива­нии являются простейшими.

Требуется определить в установившемся режиме предельные значения:

- относительной пропускной способности q;

- абсолютной пропускной способности А;

- вероятности отказа Pотк;

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

Решение

1. Определим интенсивность потока обслуживания:

2. Вычислим относительную пропускную способность:

Величина q означает, что в установившемся режиме система будет обслуживать примерно 35% прибывающих на пост ЕО авто­мобилей.

3. Абсолютную пропускную способность определим по формуле:

Это означает, что система (пост ЕО) способна осуществить в среднем 0,356 обслуживания автомобилей в час. 3. Вероятность отказа:

Это означает, что около 65% прибывших автомобилей на пост ЕО получат отказ в обслуживании.

4. Определим номинальную пропускную способность системы:

(автомобилей в час).

Оказывается, что А_ном в 1,5 раза больше, чем фактическая пропускная способность, вычисленная с учетом случай­ного характера потока заявок и времени обслуживания.

Дата добавления: 2014-01-04