СМО с ограничением времени ожидания в очереди

⇐ Назад

В этом разделе рассмотрим СМО типа М/М/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. В отличие от предыдущего простым рассуждением найти вероятность распределения времени занятости каналов не удается из-за многообразия комбинаций занятости и очередей. Поэтому воспользуемся готовым результатом:

????????????

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

= + = 1 ,(7.14)