Пять способов сделать ожидание в очереди менее утомительным. Время ожидания в очередях

В этом разделе рассмотрим СМО типа М/М/n/m< , но, в отличие от предыдущих, наложим ограничение на время ожидания в очереди.
Это ограничение носит принципиальный характер, т.к. при вычислении вероятностей состояний СМО необходимо знание не только текущего состояния (числа требований в системе), но и того, как давно пришли требования, ожидающие обслуживания. Таким образом, процесс К(t) перестает быть марковским.

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

7.3.1. Время ожидания ограничено случайной величиной τ

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

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

Примем, что распределение времени ожидания имеет вид:

F(t) = 1 - e - функция распределения,

f(t) = e - плотность распределения,

где - интенсивность выхода из очереди за счет превышения допустимого времени ожидания.

Тогда параметры процесса К(t) будут равны:

K , при к

N + (k - n) , при к>n .

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

7.3.2. Время ожидания ограничено неслучайной величиной τ

В этом случае для описания СМО с помощью марковской модели целесообразно использовать второй из приведенных в 7.1. способов, а именно, расширение понятия состояния. Для того, чтобы прогнозировать распределения состояний в будущем, необходимо знать как давно пришли в систему требования, которые в настоящее время находятся в очереди. Это можно сделать, включив в число обобщенных координат, описывающих состояние СМО, давность прихода каждого ожидающего требования, или, что то же самое, время, которое осталось у него до окончания срока ожидания. В рамках процесса К(t), которым мы пользовались во всех предыдущих задачах, это сделать нельзя, и в рассматриваемом случае модель функционирования СМО строится на основании векторного случайного процесса X , характеризующего состояние системы через состояния каждого из n ее каналов:

X = { X (t), X (t),…. X (t)} = { X (t)}

X (t) – это время, которое осталось до освобождения j-ого канала. Таким образом, для каждого момента времени t, мы можем прогнозировать будущие состояния каналов: j-ый канал освободится через х j (t), если за это время не поступят требования из внешнего потока. А так как входящий поток простейший, это значит, что в процессе X последействие отсутствует, т.е. процесс марковский. Найдем распределение этого процесса.

(7.3)

Это функция и плотность n-мерного распределения вектора X (t) в случае, когда все каналы заняты. Занятые (и только они) каналы персонифицированы, т.е. перенумерованы.

То же, что и выше, но в случае, когда занято лишь «к» каналов, а остальные свободны.

(7.4)

В дальнейшем, для простоты, будем трактовать плотность f (t; x …x ) как вероятность того, в СМО занято к каналов, которым присвоены номера от 1 до к., опуская при этом формальное умножение на . Знание этих распределений позволит вычислять вероятности состояний рассматриваемой системы.

Для вывода необходимых уравнений используем марковское свойство процесса X(t), а именно: будем выражать вероятность состояния процесса в момент t+ t (будущее) через его состояние в момент t (настоящее). Предварительно заметим, что - вероятность того, что в системе нет требований.

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

(7.5)

Второе слагаемое означает, что в момент t в одном из каналов системы было требование, обслуживание которого заканчивалось на интервале t , и этим каналом мог быть любой из n.

Преобразуя и переходя к пределу при t 0, получим:

(7.6)

Рассмотрим случай, когда 0

(7.6)

При составлении этого уравнения учитывалось следующее:

· за время t занятости всех каналов уменьшаются на , и если за это время не подойдет ни одного требования входящего потока, то к моменту t система окажется в нужном состоянии (первое слагаемое правой части);

· второе слагаемое правой части: в момент t был занят к-1 канал, а канал с номером i (из числа персонифицированных) был пустым, и что бы СМО пришла в нужное состояние необходимо: чтобы пришло требование, чтобы время его обслуживания было равно x , и чтобы из (n-к) свободных каналов оно выбрало именно i-ый, причем этим каналом может быть любой из каналов с номерами от 1 до к.

· последнее слагаемое означает, что в момент t был занят (к + 1) канал, но в одном из них (а именно в (к+1)–ом) на интервале обслуживание заканчивалось. Причем таким каналом может быть любой из (n – к).

Теперь рассмотрим случай, когда :

(7.7)

Поясним, как и выше, содержание правой части:

· Первое слагаемое отличается от случая кsign x =1, если x>0, и sign x= - 1, если x<0 ).

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

· Третье слагаемое правой части отвечает ситуации, когда все каналы заняты, как это нужно, но один из них «недозанят», например, X (t) = Z < x ; для того, чтобы в момент t+ СМО оказалась в требуемом состоянии надо, чтобы на интервале пришло требование со временем обслуживания (x - z), и стало бы в очередь к i-му каналу, а для этого его занятость z должна быть меньше занятости любого другого канала (z < min x ) т.к. когда все каналы заняты, требование автоматически становится в очередь к тому который раньше освободится; при этом недозанятым может быть любой из n каналов.

Вспоминая определение смешанной частной производной:

,(7.8)

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

(7.9)

(7.10)

Эти уравнения относятся к стационарному режиму, что получило свое выражение в том, что производные плотностей распределения по t приняты равными нулю, а сами плотности записаны в финальной форме, как функции не зависящие от времени. Кроме того, для простоты последующих выкладок, приняты следующие обозначения: f = f и f = f .

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

Сперва рассмотрим случай 0 . Как говорилось выше, функция f имеет смысл вероятности того, что в СМО занято «к» персонофицированных (перенумерованных) каналов, причем первый освободится через x единиц времени, второй через x , … , к-ый через x . Каналы функционируют независимо, и время обслуживания в каждом распределено экспоненциально. Тогда вероятность рассматриваемого события равна:

(7.11)

Вероятность того, что занято k перенумерованных каналов

P - вероятность того, что в СМО занято k каналов

Исчисляем показатели обслуживания многоканальной СМО (онлайн):
Интенсивность потока обслуживания:

1. Интенсивность нагрузки .
ρ = λ t обс = 120 1/60 = 2
Интенсивность нагрузки ρ=2 показывает степень согласованности входного и выходного потоков заявок канала обслуживания и определяет устойчивость системы массового обслуживания.
3. Вероятность, что канал свободен (доля времени простоя каналов).

Следовательно, 12% в течение часа канал будет не занят, время простоя равно t пр = 7.1 мин.
Вероятность того, что обслуживанием:
занят 1 канал:
p 1 = ρ 1 /1! p 0 = 2 1 /1! 0.12 = 0.24
заняты 2 канала:
p 2 = ρ 2 /2! p 0 = 2 2 /2! 0.12 = 0.24
заняты 3 канала:
p 3 = ρ 3 /3! p 0 = 2 3 /3! 0.12 = 0.16
4. Доля заявок, получивших отказ .

Значит, 3% из числа поступивших заявок не принимаются к обслуживанию.
5. Вероятность обслуживания поступающих заявок .
В системах с отказами события отказа и обслуживания составляют полную группу событий, поэтому:
p отк + p обс = 1
Относительная пропускная способность: Q = p обс.
p обс = 1 - p отк = 1 - 0.0311 = 0.97
Следовательно, 97% из числа поступивших заявок будут обслужены. Приемлемый уровень обслуживания должен быть выше 90%.
6. Среднее число каналов, занятых обслуживанием .
n з = ρ p обс = 2 0.97 = 1.9 каналов
Среднее число простаивающих каналов .
n пр = n - n з = 3 - 1.9 = 1.1 каналов
7. Коэффициент занятости каналов обслуживанием .

Следовательно, система на 60% занята обслуживанием.
8. Абсолютная пропускная способность .
A = p обс λ = 0.97 120 = 116.3 заявок/час.
.
t пр = p отк t обс = 0.0311 0.0166 = 0 час.
10. Среднее число заявок, находящихся в очереди .

ед.
(среднее время ожидания обслуживания заявки в очереди).
час.
12. Среднее число обслуживаемых заявок .
L обс = ρ Q = 2 0.97 = 1.94 ед.
13. Среднее число заявок в системе .
L CMO = L оч + L обс = 0.51 + 1.94 = 2.45 ед.
13. Среднее время пребывания заявки в СМО .
час.
Число заявок, получивших отказ в течение часа: λ p 1 = 4 заявок в час.
Номинальная производительность СМО: 3 / 0.0166 = 181 заявок в час.
Фактическая производительность СМО: 116.3 / 181 = 64% от номинальной производительности.

Будем использовать далее следующие обозначения для среднего значения времени ожидания в очереди требований из приоритетного класса 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 , то минимизация сводится к минимизации значений средней задержки. Таким образом, решение рассматриваемой задачи оптимизации состоит в том, что из всех возможных дисциплин обслуживания с относительным приоритетом минимум средней стоимости обеспечивает дисциплина с упорядоченными приоритетами в соответствие с неравенствами

.

Изучим работу n-канальной (n > 1) СМО с ожиданием, на вход которой поступает простейший поток заявок П вх с интенсивностью. Поток обслуживании каждым каналом также предполагается простейшим с интенсивностью µ. На длину очереди никаких ограничений не налагается, но время ожидания каждой заявки в очереди ограничено случайным сроком Т ож со средним значением, после которого заявка покидает систему необслуженной. Временной интервал Т ож является непрерывной случайной величиной, которая может принимать любое положительное значение и математическое ожидание которой.

Если этот поток пуассоновский, то процесс, протекающий в СМО, будет Марковским.

Такие системы часто встречаются на практике. Их иногда называют системами с «нетерпеливыми» заявками.

Занумеруем состояния СМО по числу заявок, находящихся в системе, как под обслуживанием, так и стоящих в очереди: S k (k = 0,1,…n) - k заявок под обслуживанием (k каналов заняты, очереди нет), S n+r (r = 1,2,…) - п заявок под обслуживанием (все п каналов заняты) и r заявок в очереди.

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

Размеченный граф состояний указан на рис. 1.

Рис. 1.

Из состояния в состояние слева направо СМО переходит под воздействием одного и того же входящего потока заявок П вх с интенсивностью. Следовательно, плотности вероятностей этих переходов

k-1,k = , k = 1,2,… (1)

Переход СМО из состояния без очереди S k , k = 1,…,n , в соседнее слева состояние S k-1 , (k = 1,…,n) (в котором также не будет очереди) происходит под действием суммарного потока, слагающегося из к потоков обслуживания занятых каналов, интенсивность которого, представляющая собой сумму интенсивностей слагаемых потоков обслуживании, равна kµ . Поэтому под стрелками налево от состояния s n до состояния s 0 проставлены плотности вероятностей переходов

k,k-1 =kµ, k = 1,…,n (2)

На систему в состоянии с очередью S n+r , r = 1,2,… , действует суммарный поток - результат наложения n потоков обслуживании и r потоков уходов. Поэтому интенсивность суммарного потока равна сумме интенсивностей слагаемых потоков nµ+rщ . Этот суммарный поток порождает переход СМО справа налево из состояния S n+r ,(r = 1,2,…) в среднее S n+r-1 ,(r = 1,2,…) и, таким образом,

k,k-1 =nµ+(k-n)щ, k =n+1,n+2,… (3)

Итак, плотности вероятностей переходов системы справа налево, учитывая (2) и (3), можно записать в объединённой форме

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

Подставим (1) и (4) для k=1,…,n+m в формулу

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

Так как в рассматриваемой СМО нет ограничений на длину очереди, то заявка, поступившая во входящем потоке, будет принят; в систему, т.е. отказ со стороны системы заявка не получает. Поэтому для СМО с «нетерпеливыми» заявками вероятность принятия в систему p сист =1, а вероятность отказа принятия в систему p отк =0 . Понятие «отказа принятия в систему» не следует смешивать с понятием «отказа в обслуживании», поскольку, в силу «нетерпеливости», не каждая поступившая (принятая) в систему заявка, будет обслужена. Таким образом, имеет смысл говорить о вероятности ухода заявки из очереди p ху и вероятности того, что заявка будет обслужена, p об . При этом, вероятность p об представляет собой относительную пропускную способность Q и p ху =1- p об .

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

N оч
		p n+1	p n+2		p n+r

где p= p 0 + p 1 +…+ p n . Следовательно,

или подставляя сюда (7), получим

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

Тогда по определению относительной пропускной способности,

Q = A/ = (-)/ = 1 - (щ/),

где щ/ = показывает среднее число уходов из очереди не обслуженных заявок за среднее время между поступлениями двух соседних заявок во входящем потоке П вх .

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

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

	p 0	p 1	p 2		p n-1

где p = p n + p n+1 +…+ p n+1 + …. Но так как событие, состоящее в том, что все n каналов заняты, противоположно событию, состоящему в том, что не все n каналов заняты, а вероятность последнего события равна

p 0 + p 1 + p 2 +…+ p n-1 , то p = 1 - (p 0 + p 1 + p 2 +…+ p n-1) .

Но тогда из (11) получим:

Используя формулы (11) и (13), получим формулу для среднего числа заявок, находящихся в системе:

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

либо найдется натуральное число i > 2 такое, что

Умножая неравенства (14) и (15) на, получим соответственно неравенства

Рассмотрим случай (14) и несовместные гипотезы состоящие в том, что система находится в состоянии. Вероятности этих гипотез

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

Если заявка поступит в систему при гипотезет.е. когда СМО находится в одном из состоянийв котором все п к-п заявок (при к = п в очереди заявок нет), то среднее время освобождения одного из п занятых каналов равно, а среднее время обслуживания к-п заявок, стоящих в очереди перед поступившей в систему заявкой, равно Поэтому среднее время, необходимое для того, чтобы подошла очередь на обслуживание поступившей заявки, равно.Так как, то в силу правого неравенства (14),

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

Теперь рассмотрим те же гипотезыв случае (15). В этом случае также справедливы равенства (16).

Если заявка поступит в систему при одной из гипотез т.е., когда СМО находится в одном из состояний в котором все п каналов заняты и в очереди перед поступившей заявкой уже стоят к-п заявок (при к - n в очереди заявок нет), то так же, как и в случае (14), среднее время, необходимое для того, чтобы подошла очередь этой заявки на обслуживание, равно ограничивающим пребывание заявки. Так както, в силу левого неравенства (15),

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

Пусть теперь заявка поступила в систему при одной из гипотез Н ю к = n+i- т.е., когда СМО находилась в одном из состояний..., в котором все п каналов заняты и в очереди уже стоят к-п заявок. Так как то из неравенства (15):

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

По формуле полного математического ожидания получим:

В случае (15) поступившая заявка будет принята к обслуживанию, если только в момент её поступления СМО находится в одном из состояний тогда вероятность того, что заявка будет обслужена

При / = 1 формула (25) превращается в (24), поэтому для вероятности обслуживания можно записать одну формулу:

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

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

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

6. Построение и анализ модели систем массового обслуживания

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

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

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

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

Среднее число самолетов в очереди.

Среднее число самолетов под обслуживанием.

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

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

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

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

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

Критерии эффективности функционирования СМО:

• · Вероятность простоя системы;
• · Вероятность отказа системы;
• · Относительная пропускная способность.
• · Среднее время пребывания заявки в очереди.

Данная система моделируется многоканальной СМО с «нетерпеливыми» заявками.

Параметры системы:

число каналов обслуживания n = 2 ;

интенсивность входящего поток заявок = 12 (самолетов в час);

интенсивность потока обслуживания µ = 6 (самолетов в час);

среднее время, ограничивающее пребывание заявки в очереди, следовательно, интенсивность потока уходов щ = 1/= 3 (самолета) в час.

Расчеты произведены с помощью разработанной в Turbo Pascal программе. Язык Turbo-Pascal - один из самых распространенных языков программирования компьютеров. К важным достоинствам языка Turbo-Pascal относится небольшой размер компилятора, высокая скорость трансляции программ, компиляции и их компоновки. Кроме того, удобство и высокое качество дизайна диалоговой оболочки, делают написание и отладку программ наиболее удобным в сравнении с альтернативными языками нового поколения.

Для анализа работы СМО необходимо исследовать поведение данной системы при различных входных параметрах.

В первом варианте л=12, µ=6, щ=3, число каналов n=2.

Во втором варианте л=12, µ=6, щ=3, число каналов n=3.

В третьем варианте л=12, µ=6, щ=4, число каналов n=2.

Все результаты расчетов приведены в Приложение 2.

В результате анализа полученных данных (Приложение 2), были сделаны следующие выводы.

С увеличением числа каналов увеличивается вероятность простоя системы и вероятность дозаправки на 50%.

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

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

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

Рассмотрим n - канальную систему массового обслуживания с ожиданием.

Интенсивность потока обслуживания равна μ. Длительность обслуживания – случайная величина, подчиненная показательному закону распределения. Поток обслуживаний является простейшим пуассоновским потоком событий.

Размер очереди допускает нахождение в ней m заявок.

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

(0‑1)

где.

Вероятность отказа в обслуживании заявки (отказ произойдет в случае, если все каналы заняты и в очереди находятся m заявок):

(0‑2)

Относительная пропускная способность .

(0‑3)

Абсолютная пропускная способность .

(0‑4)

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

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

Обозначим среднее число занятых каналов. Каждый занятый канал обслуживает в среднем μ заявок в единицу времени, а СМО в целом – А заявок в единицу времени. Разделив А на μ получим

(0‑5)

Среднее число находящихся в очереди заявок.

Для нахождения среднего числа ожидающих в очереди заявок в случае, если χ≠1, можно использовать выражение:

(0‑6)

(0‑7)

где = .

Среднее число находящихся в системе заявок.

(0‑8)

Среднее время ожидания заявки в очереди .

Среднее время ожидания заявки в очереди можно найти из выражения (χ≠1).

(0‑9)

Среднее время пребывания заявки в системе.

Так же как и в случае с одноканальной СМО имеем:

(0‑10)

Содержание работы .

Подготовка инструментария эксперимента .

Выполняется в соответствии с общими правилами.

Расчет на аналитической модели .

1. В приложение Microsoft Excel подготовьте таблицу следующего вида.

Параметры СМО

Аналитическая модель

Имитационная модель

n

m

T a

Ts

ρ

χ

P0

P1

p2

Pотк

W

nож

q

A

Pотк

W

q

A

2. В столбцах для параметров СМО таблицы запишите свои исходные данные, которые определяются по правилу:

n =1,2,3

m=1,3,5

Для каждой комбинации { n ,m} необходимо найти теоретические и экспериментальные значения показателей СМО для таких пар значений:

= <порядковый номер в списке группы>

3. В столбцы с показателями аналитической модели впишите соответствующие формулы.

Эксперимент на имитационной модели .

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

2. Для каждой комбинации n, m, и осуществите запуск модели.

Результаты запусков внесите в таблицу.

3. Внесите в соответствующие столбцы таблицы формулы для расчета среднего значения показателя Pотк, q и А.

Анализ результатов .

1. Проанализируйте результаты, полученные теоретическим и экспериментальным способами, сравнив результаты между собой.

2. Для одной из комбинаций {n,m} постройте на одной диаграмме графики зависимости Pотк от на теоретически и экспериментально полученных данных.

Оптимизация параметров СМО .

Решите задачу оптимизации размера числа мест в очереди m для двух приборов со средним временем обслуживания = с точки зрения получения максимальной прибыли. В качестве условий задачи возьмите:

- доход от обслуживания одной заявки равным 80у.е./час,

- стоимость содержания одного прибора - 1у.е./час,

- стоимость содержания одного места в очереди – 0.2у.е./час.

1. Для расчетов целесообразно создать таблицу:

Первый столбец заполняется значениями числа приборов n =1.

Второй столбец заполняется значениями чисел натурального ряда (1,2,3…).

Все клетки третьего и четвертого столбцов заполняются значениями.

В клетки столбцов с пятого по четырнадцатый переносятся формулы для столбцов таблицы раздела 0.

В столбцы с исходными данными разделов Доход, Расход, Прибыль внесите значения (см. выше).

В столбцах с вычисляемыми значениями разделов Доход, Расход, Прибыль запишите расчетные формулы:

- число заявок в единицу времени

N r =A

- суммарный доход в единицу времени

I S = I r *N r

- суммарный расход в единицу времени

E S =E s *n + E q *m

- прибыль в единицу времени

P = I S - E S

где

I r - доход от одной заявки ,

E s - расход на один прибор ,

E q - расход на одно место в очереди

2. Заполните строки таблицы для n=2 и n=3.

Найдите m опт для n =1 ,2,3.

3. Постройте на одной диаграмме графики зависимости C(m) для n=1,2,3.

Отчет по работе :

Отчет по работе должен включать:

- исходные данные,

- результаты расчетов и экспериментов с программной моделью,

Графики для P отк ,

- таблицу с данными для нахождения наилучшего m и значение m опт,

- графики зависимости прибыли в единицу времени от m для n=1,2,3.

Контрольные вопросы :

1) Дайте краткое описание многоканальной модели СМО с ограниченной очередью.

2) Какими показателями характеризуется функционирование многоканальной СМО с ограниченной очередью?

3) Как рассчитываются предельные вероятности многоканальной СМО с ограниченной очередью?

4) Как найти вероятность отказа обслуживания заявки?

5) Как найти относительную пропускную способность?

6) Чему равна абсолютная пропускная способность?

7) Как подсчитывается среднее число заявок в системе?

8) Приведите примеры многоканальной СМО с ограниченной очередью.

Задачи .

1) На автозаправочной станции установлены 3 колонки и площадка на 3 автомобиля для ожидания заправки. В среднем на станцию прибывает одна машина каждые 4 минуты. Среднее время обслуживания одной машины - 2,8 мин. Определить характеристики работы автозаправочной станции.

2) На станцию технического осмотра автомобилей, имеющего 3 смотровых поста, в среднем поступает 1 автомобиль за 0,4 часа. Стоянка во дворе вмещает 3 машины. Среднее время работы одного поста - 0,5 часа. Определить характеристики работы СТО.

3) В магазин осуществляется завоз товаров автомобилями. В течение дня прибывают в среднем 6 машин. Подсобные помещения для подготовки товаров к продаже позволяют обрабатывать и хранить товар, привезенный двумя машинами. В магазине работают посменно три фасовщика товаров, каждый из которых в среднем может обрабатывать товар одной машины в течение 5 часов. Продолжительность рабочего дня фасовщиков составляет 12 часов. Определить характеристики работы магазина, а также, какова должна быть емкость подсобных помещений, чтобы вероятность полной обработки товаров была больше 0,96.

4) В магазине работают три кассы. Среднее время обслуживания одного покупателя - 3 мин. Интенсивность потока покупателей - 7 человек в минуту. Число покупателей, стоящих в очереди к кассе, не может превышать 5 человек. Покупатель, пришедший в магазин, в котором в каждой очереди в кассу 5 человек, не ждет, а уходит из магазина. Определить характеристики работы магазина.

5) Оптовый склад производит отпуск товаров клиентам. Погрузку автомашины осуществляют три бригады грузчиков, каждая из которых состоит из 4 человек. Склад одновременно вмещает 5 автомашин и, если в это время прибывает новая автомашина, то она не обслуживается. Интенсивность входящего потока составляет 5 автомашин в час. Интенсивность по грузки составляет 2 автомашины в час. Дайте оценку работы склада и вариант его реорганизации.

6) Таможня располагает тремя терминалами. Интенсивность потока автомашин, перевозящих грузы и подлежащих прохождению таможенного контроля, составляет 30 шт. в сутки. Среднее время таможенной обработки на терминале одной автомашины составляет 3 часа. Если в очереди на прохождение таможенного контроля стоят 5 автомашин, то приезжающие автомашины уезжают на другую таможню. Найти показатели эффективности работы таможни.

7) На строительную площадку в среднем через 40 мин прибывают автомашины со строительным материалом. Среднее время разгрузки одной автомашины составляет 1,8 часа. В разгрузке принимают участие две бригады грузчиков. На территории строительной площадки может находиться в очереди на разгрузку не более 5 автомашин. Определить показатели эффективности работы строительной площадки.

8) На мойку, имеющую три рабочих места, в среднем в час приезжает 12 автомашин. Если в очереди уже находится 6 автомашин, вновь приезжающие автомобили не встают в очередь, а покидают мойку. Среднее время мойки автомашины составляет 20 мин, средняя стоимость услуг мойки - 150 руб. Определить показатели эффективности работы мойки и среднюю величину потери выручки в течение рабочего дня (с 9 до 19 часов).

9) Интенсивность потока автомашин, перевозящих грузы и подлежащих прохождению таможенного контроля, составляет 50 шт. в сутки. Среднее время таможенной обработки на терминале одной автомашины составляет 2,8 часа. Максимальная очередь на прохождение таможенного контроля должна быть не более 8 автомашин. Определить, какое количество терминалов надо открыть на таможне, чтобы вероятность простоя автомашин была минимальна.