Теория массового обслуживания (стр. 4 )

Воспользуемся мнемоническим правилом для составления уравнений для вероятностей других состояний и

, (4.29)

. (4.30)

Вместо одного из дифференциальных уравнений можно использовать нормирующее условие

. (4.31)

Дифференциальные уравнения решаются при следующих, например, начальных условиях:

при .

Для составления дифференциальных уравнений для вероятностей состояний пуассоновской системы можно использовать более простое в использовании мнемоническое правило – II, основанное на понятии “поток вероятности” [3].

Рис. 4.8. Поток вероятности

“Потоком вероятности”, переводящим пуассоновскую систему из состояния в состояние (рис. 4.8), назовем произведение вероятности состояния , из которого выходит стрелка на размеченном графе состояний (рис. 4.8), на интенсивность потока событий , переводящего систему по этой стрелке в состояние

. (4.32)

Мнемоническое правило – II составления дифференциальных уравнений для вероятностей состояний формулируется следующим образом: производная вероятности любого состояния пуассоновской системы равна сумме потоков вероятности, входящих в это состояние, минус сумма потоков вероятности, выходящих из этого состояния (см. пример, рассмотренный выше, с графом состояний рис. 4.7) [3].

При возможен стационарный режим функционирования пуассоновской системы при следующих условиях:

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

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

- система не должна иметь циклических подмножеств состояний.

При соблюдении этих условий при система дифференциальных уравнений Колмогорова (4.26) вырождается в систему следующих линейных уравнений

. (4.33)

Нормирующее условие (4.27) имеет вид

. (4.34)

Вероятности в установившемся режиме называются предельными вероятностями.

Пример 4.2. Техническая система (ТС) может находиться в одном из трех возможных состояний:

– система функционирует нормально;

– произошел отказ и система находится в ремонте;

– система проходит проверку, регулировку и настройку перед началом эксплуатации.

Граф состояний системы представлен на рис. 4.9

Рис. 4.9

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

Решение. Пользуясь мнемоническим правилом, составим по графу состояний систему линейных уравнений вида (4.32):

(4.35)

Добавим к уравнениям (4.35) нормирующее условие (4.34):

. (4.36)

Выразим вероятности и через и подставим в (4.36):

; (4.37)

. (4.38)

Подставляя (4.38) в формулы для и (4.37), окончательно получим

, (4.39)

. (4.40)

ГЛАВА 5. СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ С ОТКАЗАМИ

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

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

Рассмотрим – канальную разомкнутую СМО, на вход которой подается простейший поток заявок с интенсивностью (рис. 5.1). Поток обслуживаний каждого канала – простейший с интенсивностью .

Рис. 5.1. Схема функционирования СМО с отказами

Если заявка застает все каналы занятыми, то она покидает систему необслуженной (получает отказ).

На выходе такой системы в стационарном режиме (если он существует) будут наблюдаться два потока:

- поток обслуженных заявок с интенсивностью ;

- поток необслуженных заявок с интенсивностью .

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

. (5.1)

Разделим обе части равенства (5.1) на величину

. (5.2)

Очевидно, отношение есть не что иное, как вероятность обслуживания заявки

, (5.3)

а отношение – вероятность необслуживания заявки

. (5.4)

Вероятность обслуживания заявки называют относительной пропускной способностью СМО, а интенсивность потока обслуживания заявок – абсолютной пропускной способностью СМО, которую обозначают (5.3):

. (5.5)

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

Будем рассматривать следующее множество возможных состояний системы:

– все каналы свободны (ноль занятых каналов), – ни одна заявка не обслуживается;

– занят обслуживанием один (любой) канал – обслуживается одна заявка;

………..………………………………………………………………

– занято обслуживанием каналов – обслуживается заявок;

.……………………………………………………………………….

– все каналов системы заняты обслуживанием.

Граф состояний СМО с отказами представлен на рис. 5.2. Возможность перескока системы через состояния не рассматривается в силу ординарности потоков заявок и обслуживания.

Рис. 5.2. Размеченный граф состояний СМО с отказами

Поясним порядок определения потоков событий на рис. 5.2. На систему в состоянии действует поток заявок с интенсивностью , переводящий её в состояние (занят один канал). На систему в состоянии действуют два потока событий: поток заявок с интенсивностью , который стремится перевести систему в состояние , и поток освобождений канала (поток “обслуживания”), который стремится перевести систему в состояние . Поток обслуживания имеет интенсивность . В общем случае, когда система находится в состоянии , на нее действуют опять два потока событий: поток заявок с интенсивностью , стремящийся перевести систему в состояние (слева – направо) и поток обслуживания с интенсивностью , который стремится перевести систему в состояние (справа – налево). Когда система находится в состоянии , то на неё действует только один поток событий (обслуживания), переводящий систему в состояние (справа – налево).

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

В соответствии с мнемоническим правилом составления системы дифференциальных уравнений для вероятностей состояний и графом состояний (рис. 5.2) получим

(5.6)

Полученные уравнения называются уравнениями Эрланга. Они интегрируются при начальных условиях:

при . (5.7)

Начальные условия (5.7) соответствуют случаю, когда в момент все каналов СМО свободны. Система уравнений (5.6) достаточна для определения неизвестных величин . При решении системы (5.6) обычно добавляют ещё одно избыточное уравнение для вероятностей состояний:

, (5.8)

называемое “нормирующим условием”, которое может использоваться вместо одного (любого) дифференциального уравнения. Решение системы уравнений (5.6) с нормирующим условием (5.8) при начальных условиях (5.7) дает в результате искомые вероятности .

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

Решение. Рассмотрим единственный канал обслуживания СМО как систему , которая может находиться в одном из двух возможных состояний:

– канал свободен;

– канал занят обслуживанием.

Граф состояний системы представлен на рис. 5.3

Рис. 5.3

Обозначим и – вероятности состояний, сумма которых, очевидно, для любого равна единице

.

Дифференциальные уравнения Колмогорова для вероятностей состояний согласно мнемоническому правилу составления дифференциальных уравнений для вероятностей состояний пуассоновских систем имеют следующий вид

.

Подставим в первое уравнение вместо его выражение через

и отбросим второе уравнение

.

Это уравнение решается при начальных условиях

.

Решение уравнения для имеет следующий вид:

.

Графики функций и приведены на рис. 5.4.

Рис. 5.4

При вероятность стремится к величине , а вероятность – к величине .

Рассмотрим стационарный режим работы СМО с отказами при. Такой режим, очевидно, существует, так как рассматриваемая система эргодична: в ней нет групп состояний без выхода или без входа и все потоки событий – простейшие.

При и система дифференциальных уравнений (5.6) вырождается в систему алгебраических уравнений с неизвестными

. (5.9)

Эти уравнения нужно решать совместно с нормирующим условием (5.8)

. (5.10)

Последовательно решая уравнения системы (5.9), получим

и вообще

. (5.11)

Для нахождения вероятности воспользуемся нормирующим условием (5.10)

. (5.12)

Введем обозначение

. (5.13)

Здесь – отношение интенсивностей потоков заявок и обслуживания, имеющее смысл среднего числа заявок, поступающего в СМО за среднее время обслуживания одной заявки в одном канале. Если , то система справляется с обслуживанием; если , то часть заявок остается необслуженной; если , то система загружена неполностью. С учетом (5.13) получим следующие формулы для вероятностей состояний:

, (5.14)

. (5.15)

Формулы (5.14) и (5.15) называются формулами Эрланга.

Для оперативных расчетов вероятностей состояний используют табличные функции пуассоновского распределения – таблицы пуассоновских сумм (приложение)

, (5.16)

, (5.17)

где – пуассоновская вероятность [1]

. (5.18)

Очевидно соотношение между (5.17) и (5.16)

, (5.19)

. (5.20)

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

, (5.21)

где , (5.22)

или с помощью пуассоновских сумм (5.17)

, (5.23)

где . (5.24)

Перечислим вероятностные характеристики процесса функционирования классической СМО с отказами.

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

(5.25)

или

. (5.26)

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

(5.27)

или

(5.28)

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

3. Абсолютная пропускная способность СМО с отказами определяется выражением (5.5)

. (5.29)

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

. (5.30)

В соответствии с (5.3) интенсивность обслуживания заявок равна

Среднее число занятых каналов из (5.30) определяется выражением

. (5.31)

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

, (5.32)

откуда . (5.33)

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

Для эргодического дискретного марковского случайного процесса с непрерывным временем вероятность занятости канала определяется выражением

, (5.34)

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

– среднее время простоя канала, определяемое как средний промежуток от момента освобождения канала до его занятия новой заявкой.

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

. (5.35)

С другой стороны, из (5.34) следует

. (5.36)

7. Среднее время простоя канала, как следует из (5.34), определяется формулой

. (5.37)

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

Пример 5.2. Рассматривается 3-канальная СМО с отказами. Интенсивность пуассоновского потока заявок . Время обслуживания – случайная величина, распределенная по экспоненциальному закону, .

Требуется определить относительную и абсолютную пропускную способности СМО и другие характеристики эффективности функционирования системы.

Решение.

Интенсивность обслуживания заявок равна

.

Приведенная интенсивность потока заявок равна

.

Вероятность обслуживания – относительная пропускная способность системы – равна (5.28)

.

Таблицы пуассоновских сумм даны в приложении. Следовательно, 55% всех заявок, поступающих в СМО, будет обслужено, а 45% - нет.

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

.

Среднее число занятых каналов равно (канала).

Вероятность занятости канала обслуживания равно среднему времени обслуживания заявки .

Среднее время простоя канала равно

.

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

, (5.38)

где параметр – интенсивность ухода заявок из системы в процессе обслуживания, равный

, (5.39)

где – среднее время пребывания заявки в системе, если она принята к обслуживанию.

Приведенная интенсивность потока заявок заменяется на величину

. (5.40)

Исправленные формулы, где вместо , подставлены (5.38), (5.40), можно использовать для расчетов характеристик эффективности СМО с отказами и ограниченным временем пребывания заявки в системе после начала её обслуживания.

ГЛАВА 6. СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ С ОЖИДАНИЕМ

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

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

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

“Поведение” заявок в очереди также входит в понятие “дисциплина очереди”. “Терпеливые” заявки ждут начала обслуживания терпеливо, а “нетерпеливые” – могут уходить из очереди и из системы, не дождавшись обслуживания по окончании своего запаса времени.