Основная модель расчета среднего времени ожидания. Расчетное время ожидания в очереди

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

Сообщениям типа Z 1 ,…,Z n присвоены относительные приоритеты 1,…,n соответственно. Сообщение Z p , поступившее в систему, и ожидающее передачи, заносится в очередь О р, в которой хранятся сообщения приоритета Р. В очереди О р сообщения упорядочены по времени их поступления. Когда процессор Пр заканчивает передачу ранее обслуживаемого сообщения, то управление передается программе "ДИСПЕТЧЕР”. Программа выбирает для очередной передачи сообщение с наивысшим приоритетом - сообщение Z i , если очереди более старших приоритетов О 1 ,..,О i-1 не содержат сообщений (т.е. оказываются пустыми). Выбранное для передачи сообщение захватывает исходящий канал на все время передачи. Если в систему поступает n простейших потоков сообщений с интенсивностями, а длительность передачи сообщений каждого типа имеют средние значения и вторые начальные моменты, соответственно, то среднее время ожидания сообщений, имеющих приоритет k, определится соотношением

Используя понятие коэффициента вариации

где - среднеквадратическое отклонение времен передачи сообщений i-го типа, получим соотношение:

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

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

Для сообщений первого приоритета

Для сообщений второго приоритета

Следовательно, для интерактивных блоков:

Для почтовых блоков:

Для вычисления значений коэффициентов вариации длин блоков необходимо учесть следующее:

При каждом успешном опросе, ЦДП передает абоненту случайное число N исходящих блоков. Будем считать, что случайная величина N распределена по экспоненциальному закону.

Это означает, что коэффициент вариации (34)

Поскольку почтовые сообщения имеют постоянную длину, (35)

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

Время ожидания в очередях в узлах коммутации

Блоки сообщений, попадающие в центры коммутации, анализируются и направляются в соответствии с указанным в них адресом получателя через другие центры коммутации к абоненту или к ЭВМ. Прежде, чем центр коммутации (ЦК) прочтет адрес для направления блока, необходимо, чтобы вся управляющая часть блока (в у = 19 байт), содержащая адресную информацию, была полностью принята УК. Затрачиваемое на это время

Затем, спустя некоторое время реакции УК (рцк =1 мс), если очередь сообщений в УК отсутствует, рассматриваемый блок направится дальше к следующему центру коммутации.

Одновременно с приемом блоков УК ведет передачу выходящих из него блоков.

(37)

является полным временем, необходимым дня обслуживания передачи блока сообщений в УК.

Интерактивные и почтовые блоки сообщений поступают в УК вперемешку. При этом в него попадают как исходящие от ЭВМ ЦДП, так и предназначенные для нее блоки. Поэтому при рассмотрении времени ожидания очереди на передачу сообщения УК- необходимо учитывать полную загрузку сети

Учитывая, что является величиной постоянной (= 0), для определения значения времени tцк следует воспользоваться соотношением

Ввиду малой нагрузки эта величина получилась весьма незначительной, однако, при возрастании суммарной загрузки в 2 раза значение увеличивается, а при дальнейшем повышении нагрузки центры коммутации могут оказаться «узким местом» сети.

Значение эквивалентного времени ожидания в очередях центров коммутации определяется соотношением

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

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

Рассмотрим СМО с п каналами. На вход системы поступает простейший поток заявок с плотностью l . Время ожидания заявки в очереди Т ож распределено по показательному закону со средним значением . Время обслуживания показательное со средним значением . Параметр n полностью аналогичен параметрам l и m . Его можно интерпретировать, как плотность «потока уходов» заявки, стоящей в очереди.

Пусть максимальное число мест в очереди ограничено и равно т .

В этом случае система имеет т + n + 1 состояние. Размеченный граф состояний выглядит так:

Можно составить уравнения, аналогичные уравнениям Эрланга для предельного стационарного режима при t ® ¥ вероятности состояний, полученные из этих уравнений запишутся так:

, (6.1)

, (6.2)

где .

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

(6.3)

(6.4)

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

Средне число занятых каналов определяем по формуле:

(6.5)

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

Если число мест в очереди не ограничено (т ® ¥), то формулы упрощаются с учетом того, то .

Если заявки, попавшие в очередь, не покидают ее, а терпеливо дожидаются обслуживания (n = 0, а значит, и b = 0), то формулы (6.1) и (6.2) превращаются в формулы (5.1), (5.2), которые мы рассматривали в § 5).

Если при этом длина очереди не ограничена (т ® ¥), то получим формулы (4.1), (4.2), мак как система превращается в чистую систему с ожиданием (см. § 4).

Задача 1 . В магазине обслуживают покупателей четыре продавца. Среднее время обслуживания одного покупателя 4 мин. Плотность потока покупателей около двух человек в минуту. В очереди могут ожидать одновременно не более 20 человек. В среднем покупатель, вставший в очередь, ожидает 10 мин., после чего он покидает магазин.

Определить: 1) среднее число занятых продавцов;

2) среднее число покупателей, ожидающих в очереди;

3) вероятность того, что все места в очереди будут заняты;

4) вероятность того, что покупатель будет обслужен;

5) среднее время пребывания в очереди;

6) среднее время, затачиваемое на всю процедуру (ожидание в очереди и обслуживание).

Решение . Работа магазина может быть представлена как работа СМО смешанного типа. Параметры этой системы следующие:

п = 4 – число каналов обслуживания;

т = 20 – максимальное число мест в очереди;

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

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

– среднее время ожидания покупателя в очереди. После чего он покидает магазин ;

; ; – целое число.

1) Среднее число занятых продавцов:

то есть практически все продавцы будут заняты.

2) Среднее число покупателей, ожидающих в очереди:

3) Вероятность того, что все места в очереди будут заняты:

то есть все места в очереди будут заняты с вероятностью менее 1 %.

4) Вероятность обслуживания:

6) Среднее время, затачиваемое на всю процедуру:

Задача 2 . С целью увеличения дальности беспосадочного полета производится дозаправка самолетов горючим в воздухе. В районе дозаправки постоянно дежурят четыре самолета-дозаправщика. Если дозаправка началась, то она осуществляется до конца и длится в среднем 10 минут. Если все дозаправщики заняты, то самолет, нуждающийся в дозаправке, может некоторое время «ожидать» (совершать полет по кругу в районе дозаправки); среднее время ожидании 20 минут. Если самолет не дождался дозаправки в воздухе, он садится на запасной аэродром. Интенсивность полетов такова, что в среднем за час в район дозаправки прибывает 24 самолета. Число самолетов, ожидающих дозаправки в воздухе, не ограничено.

Определить: 1) вероятность Р об с того, что самолет будет дозаправлен;

2) среднее число занятых дозаправщиков;

3) вероятность того, что произвольно взятый дозаправщик будет занят;

4) среднее время простоя дозаправщика.

Решение . Рассматриваемая система может быть рассмотрена как СМО смешанного типа с параметрами:

число каналов обслуживания п = 4;

число мест в очереди не ограничено (т ® ¥);

плотность потока заявок ;

плотность потока обслуживаний ;

плотность потока уходов из очереди .

Отсюда – целое число.

По формуле (6.5) находим среднее число дозаправщиков, занятых обслуживанием самолетов:

где R (¥;8) = 1.

Вероятность тог, что самолет будет дозаправлен:

Среднее время простоя дозаправщика:

Задачи .

1. Гарантийная мастерская принимает заказы на ремонт по одному телефону. Среднее число заказов за 1 час – 2п . Среднее время оформления заявки т мин. Считается, что если клиент позвонил, а телефон занят, то он обратится в другую мастерскую (система без очереди). Найти основные характеристики СМО: 1) р 0 , р 1 ; 2) р обс ; 3) ; 4) . Проанализировать, как изменятся соответствующие показатели, если подключить второй телефон. С какой интенсивностью должны работать два работника, чтобы доля потерь заявок была менее 10 %? , менее 5 %?

2. В мастерской по ремонту холодильников имеются 3 мастера. Мастер в среднем может отремонтировать 1 холодильник за 80 минут. Рабочий день составляет 8 часов. В мастерскую в среднем поступает 40 заявок на ремонт за рабочий день. В случае, если все мастера заняты, холодильник в ремонт не принимается (СМО с отказом). Заработная плата мастеров почасовая,

150 рублей в час. Клиент в среднем платит за ремонт 300 рублей (запчасти оплачиваются отдельно). Определить чистую прибыль мастерской за смену. Как изменится прибыль, если пригласить в мастерскую 4-го мастера? Определить количество мастеров, при котором прибыль мастерской максимальна.

3. В платной справочной телефонной службе имеется четыре телефонные линии. В справочную поступает простейший поток заявок со средней интенсивностью 1 заявка в 2 минуты. Ответ на каждый вопрос длится в среднем 6 минут. За ответ на каждый вопрос клиент платит 10 руб.. Эксплуатация одного канала обслуживания составляет 30 руб./час, создание канала обслуживания требует расхода 8000 руб. Определить чистый доход за один час. Через сколько часов произойдет окупаемость системы?

4. Гарантийная мастерская принимает заказы на ремонт по одному телефону. Среднее число поступающих в течение часа заказов – 20, среднее время оформления заказа – 4 минуты. Определить показатели СМО:

1) вероятности состояний системы р 0 , р 1 ; 2) вероятность обслуживания заявки р обс ; 3) среднее число занятых каналов ; 4) вероятность занятости канала; 5) среднее время простоя канала. Проанализировать, как они изменятся, если подключить второй телефон.

5. Средний интервал между поступающими в прокатный пункт заявками и запросами на наличие определенных предметов составляет 5 мин. Принимают заявки два работника, каждый с интенсивностью 12 заявок в час. С какой интенсивностью должен работать один работник, выполняя работу двух, чтобы доля потерянных требований осталась на прежнем уровне? На сколько требуется повысить интенсивность обслуживания двум работникам, чтобы доля потерянных заявок была менее 10 %?

6. На диспетчерском пункте дежурят 4 приемщика заявок на ремонт телерадиоаппаратуры. Заявки принимаются по телефону. В диспетчерский пункт поступает простейший поток заявок с плотностью l = 3 (заявки в минуту). Вызов, поступивший в момент, когда все приемщики заняты, получает отказ. Средняя длительность оформления заявки 2 минуты. Найти все характеристики СМО: 1) вероятности состояний системы р 0 , р 1 ;

2) вероятность обслуживания заявки р обс ; 3)среднее число занятых каналов ; 4) вероятность занятости канала; 5) среднее время простоя канала.

С какой интенсивностью должны работать 2 работника, выполняя работу четырех, чтобы доля потерянных требований осталась на прежнем уровне?

7. Библиотека принимает заявки на книги по одному телефону. Среднее число поступающих в течение часа заявок – 70, среднее время оформления заявки – 2 минуты. Определить показатели СМО (задача 6). Найти, как изменятся параметры системы, если заявки будут приниматься по двум телефонам и при этом доля потерянных заявок уменьшится в 2 раза по сравнению с прежним уровнем. Как изменится время пребывания заявки в системе?

8. Пусть в СМО с отказом поступает в среднем 15 заявок в час. Среднее время обслуживания заявки составляет 12 мин. За обслуживание заявки клиент платит 80 рублей. Содержание одного канала обслуживания обходится 100 рублей в час. Определить число каналов обслуживания, при которых прибыль максимальна.

Литература

1. Венцель Е.С. Теория вероятностей. М., 1962.

2. Венцель Е.С., Овчаров Л.А. Теория вероятностей. М., 1969.

3. Гнеденко Б.В. Лекции по теории массового обслуживания. Изд. КВИРТУ, 1960.

4. Н.Ш.Кремер Теория вероятностей и математическая статистика. Учебник. 2-е издание. Москва, 2003, 2006 ЮНИТИ.

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

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

Далее предполагаем, что в данной системе имеется ограничение на длину очереди, под которой понимается максимальное число мест в очереди, а именно, предполагаем, что в очереди могут находиться максимум m ≥1 заявок. Поэтому заявка, пришедшая на вход СМО, в момент, когда в очереди уже стоят m заявок, получает отказ и покидает систему необслуженной.

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

Пронумеруем состояния СМО по числу заявок, находящихся в системе, т.е. под обслуживанием и в очереди:

S 0 – канал свободен (следовательно, очереди нет);

S 1 – канал занят и очереди нет, т.е. в СМО находится (под обслуживанием) одна заявка;

S 2 – канал занят и в очереди стоит одна заявка;

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

S m +1 – канал занят и в очереди m заявок.

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

Рис. 6. Схема состояний в одноканальной системе с очередью

Для описания предельного режима работы СМО можно воспользоваться изложенными правилами и формулами. Запишем сразу выражения, определяющие предельные вероятности состояний:

где ρ = λ/μ – интенсивность нагрузки канала.

Если λ = μ , то получаем .

Пусть теперь
. Выражение дляp 0 можно в данном случае записать проще, пользуясь тем, что в знаменателе стоит сумма m + 2 членов геометрической прогрессии со знаменателем ρ :

.

Заметим, что при m = 0 мы переходим к уже рассмотренной одноканальной СМО с отказами. В этом случае .

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

Поступившая на вход СМО заявка получает отказ тогда и только тогда, когда канал занят и в очереди ожидают m заявок, т.е. когда система находится в состоянии S m +1 . Поэтому вероятность отказа определяется вероятностью появления состояния S m +1 :

Относительная пропускная способность, или доля обслуживаемых заявок, поступающих в единицу времени, определяется выражением:

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

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

.

Среднее число заявок L оч , стоящих в очереди на обслуживание, определяется как математическое ожидание дискретной случайной величины k – числа заявок, стоящих в очереди:

.

Случайная величина k принимает значения 0, 1, 2, … , m , вероятности которых определяются вероятностями состояний системы p k . Таким образом, закон распределения дискретной случайной величины k имеет следующий вид:

Поэтому по определению математического ожидания дискретной случайной величины (с учетом формул для вероятностей состояний) получаем:

(16)

Предположим, что ρ ≠ 1 . Очевидно, имеем:

Но сумма представляет собой сумму первых m членов геометрической прогрессии

. (17)

Подставив выражение (17) в (16), найдем:

или, используя равенство
(полученное приρ ≠ 1 ), имеем

Если же ρ = 1 , то из равенства (16)
а учитывая, что в этом случае
и
(суммаm членов арифметической прогрессии), окончательно получаем

.

Тогда среднее число заявок в очереди

(18)

Важной характеристикой СМО с ожиданием является среднее время ожидания заявки в очереди
. Пусть T оч – непрерывная случайная величина, представляющая собой время ожидания заявки в очереди. Среднее время ожидания заявки в очереди вычислим как математическое ожидание этой случайной величины:

.

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

где M (X | H k ) – условное математическое ожидание величины X при гипотезе H k .

Рассмотрим m + 2 несовместных гипотез H k , k = 0,1,..., m + 1 , состоящих в том, что СМО находится соответственно в состояниях S k , k = 0,1,..., m + 1 . Вероятности этих гипотез p (H k ) = p k , k = 0,1,..., m +1 .

Если заявка поступает в СМО при гипотезе H 0 S 0 , в котором канал свободен, то заявке не придется стоять в очереди и, следовательно, условное математическое ожидание M (
| H 0 ) случайной величины
при гипотезе H 0 ,совпадающее со средним временем ожидания заявки в очереди при гипотезе H 0 , равно нулю.

Для заявки, поступившей в СМО при гипотезе H 1 , т.е. когда СМО находится в состоянии S 1 , в котором канал занят, но очереди нет, условное математическое ожидание M (
| H 1 ) случайной величины
при гипотезе H 1 , совпадающее со средним временем ожидания заявки в очереди при гипотезе H 1 , будет равно среднему времени обслуживания одной заявки
.

Условное математическое ожидание M (
| H 2 ) случайной величины
при гипотезе H 2 , т.е. при условии, что заявка поступила в СМО, находящуюся в состоянии S 2 , в котором канал занят и в очереди уже ждет одна заявка, равно 2/ μ (удвоенному среднему времени обслуживания, поскольку нужно обслужить две заявки: ту, которая находится в канале обслуживания, и ту, которая ждет в очереди). И так далее.

Если заявка поступит в систему при гипотезе H m , т.е. когда канал занят и в очереди ждут m − 1 заявок, то M (
| H m ).

Наконец, заявка, пришедшая в СМО при гипотезе H m +1 , т.е. когда канал занят, m заявок стоят в очереди, и свободных мест в очереди больше нет, получает отказ и покидает систему. Поэтому в этом случае M (
| H m +1 ) = 0.

Следовательно, по формуле полного математического ожидания среднее время ожидания заявки в очереди

Подставляя сюда выражения для вероятностей p k (k =1,2,...,m ), получаем:
(19)

Если интенсивность нагрузки канала ρ ≠ 1 , то из равенства (19) с учетом формул (17), (18), а также выражения для p 0 находим:

Если же ρ = 1 , то, подставляя в равенство (19) выражение p 0 = 1/(m +2), значение суммы
, используя формулу (18) приρ = 1 и учитывая, что в данном случае μ = λ , будем иметь

Итак, для любого ρ получаем формулу для среднего времени пребывания заявки в очереди, которая называется формулой Литтла:
т.е. среднее время ожидания заявки в очереди
равно среднему числу заявок в очереди L оч , деленному на интенсивность λ входящего потока заявок.

Пример. На автозаправочной станции (АЗС) имеется одна колонка. Площадка при станции, на которой машины ожидают заправку, может вместить не более трех машин одновременно, если она занята, то очередная машина, прибывшая к станции, в очередь не становится, а проезжает на соседнюю АЗС. В среднем машины прибывают на станцию каждые 2 мин. Процесс заправки одной машины продолжается в среднем 2,5 мин. Определить основные характеристики системы.

Решение. Математической моделью данной АЗС является одноканальная СМО с ожиданием и ограничением на длину очереди (m = 3). Предполагается, что поток машин, подъезжающих к АЗС для заправки, и поток обслуживаний – простейшие.

Поскольку машины прибывают в среднем через каждые 2 мин, то интенсивность входящего потока равна λ =1/2 = 0,5 (машин в минуту). Среднее время обслуживания одной машины
= 2,5 мин, следовательно, интенсивность потока обслуживаний μ =1/2,5 = 0,4 (машины в минуту).

Определяем интенсивность нагрузки канала: ρ = λ/μ = 0,5/0,4 = 1,25.

Вычисляем вероятность отказа
откуда относительная пропускная способность и абсолютная пропускная способность A = λ Q ≈ 0,5⋅0,703 ≈ 0,352.

Среднее число машин, ожидающих в очереди на заправку

Среднее время ожидания машины в очереди находим по формуле Литтла
= L оч /λ ≈1,559/0,5 = 3,118.

Таким образом, из анализа работы СМО следует, что из каждых 100 подъезжающих машин 30 получают отказ (P отк ≈ 29,7%), т.е. обслуживаются 2/3 заявок. Поэтому необходимо либо сократить время обслуживания одной машины (увеличить интенсивность потока обслуживаний), либо увеличить число колонок, либо увеличить площадку для ожидания.

Будем использовать далее следующие обозначения для среднего значения времени ожидания в очереди требований из приоритетного класса p - W p , и среднего времени пребывания в системе для требований этого класса - T p :

Основное внимание будем уделять системам с относительным приоритетом. Рассмотрим процесс с момента поступления некоторого требования из приоритетного класса p . Будем далее называть это требование меченым. Первая составляющая времени ожидания для меченого требования связана с требованием, которое оно застает в сервере. Эта составляющая равна остаточному времени обслуживания другого требования. Обозначим теперь и будем использовать это обозначение и далее, среднюю задержку меченого требования, связанную с наличием другого требования на обслуживании W 0 . Зная распределение времени между соседними поступлениями входных требований для каждого приоритетного класса, можно всегда вычислить эту величину. В нашем предположении пуассоновского закона для потока заявок каждого класса можно записать

.

Вторая составляющая времени ожидания для меченого требования определяется тем, что перед меченым требованием обслуживаются другие требования, которые меченое требование застало в очереди. Обозначим далее число требований из класса i , которое застало в очереди меченое требование (из класса p ) и которые обслуживаются перед ним N ip . Среднее значение этого числа будет определять величину среднего значения этой составляющей задержки

Третья составляющая задержки связана с требованиями, поступившими после того как пришло меченое требование, однако получившими обслуживание раньше его. Число таких требований обозначим M ip . Среднее значение этой составляющей задержки находится аналогично и составляет

Складывая все три составляющие, получаем, что среднее время ожидания в очереди для меченого требования определяется формулой

Очевидно, что независимо от дисциплины обслуживания число требований, N ip и M ip в системе не может быть произвольным, поэтому существует некоторый набор соотношений, связывающий между собой задержки для каждого из приоритетного класса. Важность этих соотношений для СМО позволяет называть их ЗАКОНАМИ СОХРАНЕНИЯ. Основой законов сохранения для задержек является тот факт, что незаконченная работа в любой СМО в течение любого интервала времени занятости не зависит от порядка обслуживания, если система является консервативной (требования не исчезают внутри системы и сервер не простаивает при непустой очереди).

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

Для СМО типа M/G/1 можно показать, что для любой дисциплины обслуживания должно выполняться следующее важное равенство

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

Для более общей системы с произвольным распределением времени поступления требований G/G/1 закон сохранения может быть записан в виде

.

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

Подставляя его в предыдущее выражение, сразу получается приведенный ранее закон сохранения для СМО типа M/G/1.

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

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

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

Воспользуемся формулой для W p . Исходя из механизма функционирования, можно сразу выписать

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

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

Непосредственно из формулы (*) получаем:

Эта система уравнений может быть решена рекуррентно, начиная с W 1 ,W 2 и т.д.

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

Рисунок 2.Обслуживание в порядке приоритетов в случае относительных приоритетов (Р=5, l Р = l/5, ).

Особую задачу представляет определение законов распределения времени ожидания.

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

.

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

Решим задачу нахождения дисциплины обслуживания с относительными приоритетами для системы M/G/1, которая минимизирует среднюю стоимость задержки C . Пусть имеется P приоритетных классов заявок с заданной интенсивностью поступления и средним временем обслуживания. Перенесем в левую часть постоянную сумму и выразим правую часть через известные параметры

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

Обозначим

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

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

Решение состоит в том, что сначала упорядочим последовательность значений f p : .

А затем выберем для каждого f p свое значение g p , так, чтобы минимизировать сумму их произведений. Интуитивно ясно, что оптимальная стратегия выбора состоит в подборе наименьшего значения g p для наибольшего f p , далее для оставшихся значений следует поступать тем же образом. Поскольку g p =W p r p , то минимизация сводится к минимизации значений средней задержки. Таким образом, решение рассматриваемой задачи оптимизации состоит в том, что из всех возможных дисциплин обслуживания с относительным приоритетом минимум средней стоимости обеспечивает дисциплина с упорядоченными приоритетами в соответствие с неравенствами

.