СМО с ограничением времени ожидания в очереди
В этом разделе рассмотрим СМО типа М/М/n/m< , но, в отличие от предыдущих, наложим ограничение на время ожидания в очереди.
Это ограничение носит принципиальный характер, т.к. при вычислении вероятностей состояний СМО необходимо знание не только текущего состояния (числа требований в системе), но и того, как давно пришли требования, ожидающие обслуживания. Таким образом, процесс К(t) перестает быть марковским.
Время ожидания в очереди может быть ограничено как детерминированной, так и случайной величиной. В обеих случаях процесс К(t), как уже было сказано, характеризуется наличием последействия. Однако, способы формирования на его основе марковской модели СМО существенно различаются.
7.3.1. Время ожидания ограничено случайной величиной τ
В этом случае все зависит от закона распределения ограничения , т.к. именно ограничение вносит в систему последействие. Поэтому вернуть процессу К(t) марковость крайне просто. Достаточно принять для описания случайной величины экспоненциальное распределение. Однако при этом нельзя забывать, что такая операция возможна лишь в том случае, когда реальное распределение или действительно экспоненциальное, или близко к нему. Если это не так, то сформированная математическая модель будет неадекватна реальной СМО.
При экспоненциально распределенном ограничении на время ожидания в очереди, процесс изменения числа требований в СМО по-прежнему будет процессом размножения и гибели с той лишь разницей, что интенсивность гибели увеличится за счет, покидающих очередь требований, у которых время ожидания превысило допустимую величину.
Примем, что распределение времени ожидания имеет вид:
F(t) = 1 - e - функция распределения,
f(t) = e - плотность распределения,
где - интенсивность выхода из очереди за счет превышения допустимого времени ожидания.
Тогда параметры процесса К(t) будут равны:
= const
= k , при к<n ,
= 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<k<n. Напишем вероятность будущего состояния системы:
(7.6)
При составлении этого уравнения учитывалось следующее:
· за время t занятости всех каналов уменьшаются на , и если за это время не подойдет ни одного требования входящего потока, то к моменту t система окажется в нужном состоянии (первое слагаемое правой части);
· второе слагаемое правой части: в момент t был занят к-1 канал, а канал с номером i (из числа персонифицированных) был пустым, и что бы СМО пришла в нужное состояние необходимо: чтобы пришло требование, чтобы время его обслуживания было равно x , и чтобы из (n-к) свободных каналов оно выбрало именно i-ый, причем этим каналом может быть любой из каналов с номерами от 1 до к.
· последнее слагаемое означает, что в момент t был занят (к + 1) канал, но в одном из них (а именно в (к+1)–ом) на интервале обслуживание заканчивалось. Причем таким каналом может быть любой из (n – к).
Теперь рассмотрим случай, когда :
(7.7)
Поясним, как и выше, содержание правой части:
· Первое слагаемое отличается от случая к<n тем, что здесь учитывается то обстоятельство, что, когда все каналы заняты, требования входящего потока влияют на процесс X (t), только, если время занятости наименее загруженного канала меньше, чем допустимое время ожидания в очереди. В противном случае приходящие требования получают отказ и никак не влияют на процесс X (t). Учет этого достигается за счет введения сомножителя с сигнатурой. (напомним, что sign x =1, если x>0, и sign x= - 1, если x<0).
· Второе слагаемое в содержательном плане ничем не отличается от случая к<n, за исключением того, что не надо учитывать вероятность попадания пришедшего требования в нужный канал, т.к.он единственный свободный.
· Третье слагаемое правой части отвечает ситуации, когда все каналы заняты, как это нужно, но один из них «недозанят», например, X (t) = Z < x ; для того, чтобы в момент t+ СМО оказалась в требуемом состоянии надо, чтобы на интервале пришло требование со временем обслуживания (x - z), и стало бы в очередь к i-му каналу, а для этого его занятость z должна быть меньше занятости любого другого канала (z < min x ) т.к. когда все каналы заняты, требование автоматически становится в очередь к тому который раньше освободится; при этом недозанятым может быть любой из n каналов.
Вспоминая определение смешанной частной производной:
,(7.8)
производя группировку членов уравнений, как это делалось выше, и переходя к пределу при , окончательно получим:
для k >n :
(7.9)
для :
(7.10)
Эти уравнения относятся к стационарному режиму, что получило свое выражение в том, что производные плотностей распределения по t приняты равными нулю, а сами плотности записаны в финальной форме, как функции не зависящие от времени. Кроме того, для простоты последующих выкладок, приняты следующие обозначения: f = f и f = f .
Решение этой системы, т.е. отыскание функций f и f , произведем следующим образом. Вначале, исходя из общих соображений содержательного характера, найдем вид этих функций, после чего подставим их в систему уравнений с целью установить, удовлетворяют они им или нет. Если ответ будет положительным, то решение системы уравнений найдено.
Сперва рассмотрим случай 0 . Как говорилось выше, функция f имеет смысл вероятности того, что в СМО занято «к» персонофицированных (перенумерованных) каналов, причем первый освободится через x единиц времени, второй через x , … , к-ый через x . Каналы функционируют независимо, и время обслуживания в каждом распределено экспоненциально. Тогда вероятность рассматриваемого события равна:
(7.11)
где
- вероятность того, что занято k перенумерованных каналов
P - вероятность того, что в СМО занято k каналов
(7.12)
Т.к. мы рассматриваем случай (очереди нет), то можем предположить, что ограничение времени ожидания в очереди на этом участке не действует, и мы имеем марковскую СМО типа М/М/n с неограниченной по длине очередью, и, следовательно, можно использовать полученные ранее выражения вероятностей P . Необходимо заметить что до сих пор наши рассуждения были достаточно строгими, но это предположение требует проверки. Итак:
(7.13)
Теперь рассмотрим случай к>n. В отличие от предыдущего простым рассуждением найти вероятность распределения времени занятости каналов не удается из-за многообразия комбинаций занятости и очередей. Поэтому воспользуемся готовым результатом:
????????????
Теперь необходимо найти P0. Сделаем это, как обычно, исходя из нормирующего условия:
= + = 1 ,(7.14)
где - вероятность того, что все каналы заняты
(7.15)
Входящий в это выражение n-мерный интеграл можно выразить через табличный:
(7.16)
Задача решена, и с помощью полученных распределений можно вычислять характеристики исследуемой СМО.
Вероятность отказа вычисляется по формуле:
(7.17)
Распределение времени обслуживания:
(7.18)
Среднее время ожидания в очереди:
(7.19)