Полная версия

Главная arrow Туризм arrow Основы функционирования систем сервиса

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Алгоритм свертки для замкнутых сетей обслуживания

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

Известно, что изображение свертки функций находится как произведение изображений исходных функций. Следовательно, выражение (20.29) для g(N,K,z) принимает вид

Алгоритм реализуется в три этапа [49].

  • 1. Вычисляются из уравнения баланса (20.24) интенсивности потоков клиентов и входная приведенная нагрузка |/ к = ^ /ц для каждой СМО.
  • 2. Рассматриваем каждую СМО как изолированную с входной нагрузкой у к, к = 1,2,..., К, и вычисляем относительную вероятность состоянийрк(пк) СМО0Л.
  • 3. Вычисляем свертку для каждой СМО. Например, для первых двух СМО

где * — обозначение операции свертки. Когда свертка будет проделана для всех СМО, на последней итерации получим р 2 К = Р[2 к- * Рк- Поскольку число клиентов в системе фиксировано и равно N, вероятность р 2 должна быть равна единице. Тогда можно нормировать вероятности всех состояний.

Пример. Рассмотрим замкнутую сеть из двух СМО (рис. 20.22).

Замкнутая сеть обслуживания из двух СМО типов M/M/S и М/М/1

Рис. 20.22. Замкнутая сеть обслуживания из двух СМО типов M/M/S и М/М/1

Первая СМО представляет систему M/M/S, а вторая М/М/1. Интенсивность потока к СМО Х= А,, = Х2, откуда относительная нагрузка на системы i] = А,/ц, и V)/2 = А/ц2.

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

Таблица 20.2. Вероятности состояний сети обслуживания, приведенной на рис. 20.22

Состояние

п

Вероятность состояния СМО 1

рМ)

Вероятность состояния СМО 2 Р2(п)

Вероятность состояния сети Р.2 = Р* Р2

0

1

1

1

VI

V2

VI+V2

2

Vi2

2!

v2

2 V Г V2 + Vl -V2 + ^7

/

Vi

i

V 2

S

vf

5!

9

V 2

P.2(S)

Вероятность занятия всех S элементов обслуживания первой СМО (последняя строка табл. 20.2) вычисляется как

Упрощая, получаем где

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

Это, как известно, есть 5-формула Эрланга, или формула потерь Эрланга.

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

Пример. Пусть сеть состоит из пяти С МО, включенных так, как показано на рис. 20.23, число клиентов N = 4 [47].

Замкнутая сеть обслуживания из пяти СМО типа М/М/1

Рис. 20.23. Замкнутая сеть обслуживания из пяти СМО типа М/М/1

Из схемы сети на рис. 20.23, согласно уравнению баланса (20.24), имеем Х{ = Х2 = Х3 = Х4 = 0,5Х5, р|2 = 2, д3=|д4=)д5 = 1. Пусть

v|/5 = Х5 у, тогда у, = i 2 VJ//4, |/3 = |/4 = у/2. Согласно (20.28),

Операция свертки является довольно сложной, поэтому для определения коэффициента нормализации вычислим его производящую функцию по формуле (20.38):

Для вычисления обратного преобразования разложим выражение на сумму простых дробей:

Используем таблицу преобразований:

При > =4 найдем, что ^(4,5) = 1497. После подстановки в (20.39) получим выражение для совместной вероятности состояний сети:

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

возможных состояний системы.

Алгоритм анализа средних значений (MVA) базируется на законе Литтла и теореме прибытия (§19.3). Алгоритм может использоваться для следующих дисциплин обслуживания: обслуживание с начала очереди, обслуживание с конца очереди, параллельное обслуживание, обслуживание с бесконечным числом элементов обслуживания. Время обслуживания должно быть экспоненциальным. Алгоритм начинает свою работу при отсутствии клиентов в сети (п = 0), постепенно увеличивая число клиентов до N.

Среднее время обслуживания клиентов в С МО (9,

где р^1 — среднее время обслуживания в СМО (9, сети; N* (п) — среднее число клиентов, стоящих впереди клиента, прибывшего в СМО(9, сети.

Согласно теореме прибытия, N*(п) — Nt(n-1), где N, (/7-1) — среднее число клиентов в СМО (9, сети в стационарном состоянии при наличии клиентов в сети на 1 меньше.

Следовательно,

Можно показать, что среднее число клиентов в СМО 0, сети

Используя теорему Литтла, определим интенсивность потока через СМО 0, сети:

Здесь А*? является решением уравнения (20.23).

Таким образом, вычисления могут быть выполнены рекурсивно за несколько этапов.

1. Начальное состояние. Полагаем Nk(0) = 0 для всех СМО,

к = 1 т.е. при отсутствии клиентов в сети число клиентов в

любой СМО равно нулю.

2. Проводим вычисления средних значений для числа клиентов п = 1,2,..., N. На каждом шаге вычисляем среднее время пребывания п клиентов в системе для всех i = 1,..., К:

3. Рассчитываем N, (п) для / = 1,..., А':

4. Используя закон Литтла, находим абсолютную пропускную способность

Пример. Рассмотрим простую замкнутую сеть из К последовательных СМО типа М/М/ (рис. 20.24).

Пустьр, = |д2 =• ?• = цк = ц. Ясно, что А, = а2 =•?•= кк = 1. Так как параметры обслуживания каждой СМО одинаковы, индекс можно опустить. Рекуррентные уравнения для вычисления параметров обслуживания имеют вид:

Замкнутая последовательная сеть обслуживания из А'СМО типа М/М/1

Рис. 20.24. Замкнутая последовательная сеть обслуживания из А'СМО типа М/М/1

Начиная с начального состояния N(0) = 0, рассчитаем характеристики обслуживания, постепенно увеличивая число клиентов в сети:

При N «К получим X(N) = (N / К) р. Полное время цикла обслуживания составляет ЛУц для (V клиентов.

При N » К получим X(N) = ii. Все СМО загружены, и клиенты покидают сеть через интервал ц-1.

Пример. Рассмотрим сеть из двух параллельных СМО (рис. 20.25), обслуживающих трех клиентов (N=3).

Замкнутая параллельная сеть обслуживания из двух СМО типа А//А//1

Рис. 20.25. Замкнутая параллельная сеть обслуживания из двух СМО типа А//А//1

Пусть г, = 2/3, /*2 = 1/3. Согласно уравнению баланса потоков, =2, Х2 1. Начиная с нулевого состояния (V,(0)= N2(0) — 0, рассчитаем характеристики обслуживания, постепенно увеличивая число клиентов в сети:

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>