5.3.3. Система массового обслуживания с ожиданием

Как было упомянуто выше СМО с ожиданием подразумевает наличие буфера с очередью из заявок, заставших все каналы занятыми и ждущих освобождения одного из каналов. Если время ожидания заявки в очереди ничем не ограничено, то система называется «чистой системой с ожиданием». Если оно ограничено какими-то условиями, то система называется «системой смешанного типа». Это промежуточный случай между чистой системой с отказами и чистой системой с ожиданием.

Для практики наибольший интерес представляют именно системы смешанного типа. Ограничения, наложенные на ожидание, могут быть различного типа. Часто бывает, что ограничение накладывается на время ожидания заявки в очереди; считается, что оно ограничено сверху каким-то сроком , который может быть как строго определенным, так и случайным. При этом ограничивается только срок ожидания в очереди, а начатое обслуживание доводится до конца, независимо от того, сколько времени продолжалось ожидание (например, в системах с коммутацией каналов после установления соединения между абонентами процесс разговора уже не прерывается). В других задачах естественнее наложить ограничение не на время ожидания в очереди, а на общее время пребывания заявки в системе (например, при передаче SMS-сообщений, если после определенного количества попыток сообщение не доходит до адресата оно аннулируется). Наконец, можно рассмотреть и такую смешанную систему (она ближе всего к типу торговых, предприятий, торгующих предметами не первой необходимости), когда заявка становится в очередь только в том случае, если длина очереди не слишком велика. Здесь ограничение накладывается на число заявок в очереди (или на размер буфера , рис. 5.13).

Рис. 5.13. Логическая схема односерверной СМО

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

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

Рассмотрим смешанную СМО с каналами при следующих условиях [6]. На вход системы поступает простейший поток заявок с плотностью . Время обслуживания одной заявки - показательное, с параметром . Заявка, заставшая все каналы занятыми, становится в очередь и ожидает обслуживания; время ожидания ограничено некоторым сроком ; если до истечения этого срока заявка не будет принята к обслуживанию, то она покидает очередь и остается необслуженной. Срок ожидания будем считать случайным и распределенным по показательному закону

, ,

где параметр - величина, обратная среднему сроку ожидания: .

Параметр полностью аналогичен параметрам и потока заявок и «потока освобождений». Его можно интерпретировать, как плотность «потока уходов» заявки, стоящей в очереди. Действительно, представим себе заявку, которая только и делает, что становится в очередь и ждет в ней, пока не кончится срок ожидания , после чего уходит и сразу же снова становится в очередь. Тогда «поток уходов» такой заявки из очереди будет иметь плотность . Очевидно, при система смешанного типа превращается в чистую систему с отказами; при она превращается в чистую систему с ожиданием.

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

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

Возможные состояния системы будут (рис. 5.14):

- ни один канал не занят, очереди нет;

- занят ровно один канал, очереди нет;

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

- занято ровно каналов, очереди нет;

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

- заняты все каналов, очереди нет;

- заняты все каналов, одна заявка стоит в очереди;

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

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

Рис. 5.14. Диаграмма возможных переходов для СМО с очередью

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

Очевидно, первые ДУ ничем не будут отличаться от соответствующих уравнений Эрланга (5.28):

(5.37)

Отличие новых уравнений от уравнений Эрланга начнется при . Действительно, в состояние система с отказами может перейти только из состояния ; что касается системы с ожиданием, то она может перейти в состояние не только из , но и из (все каналы заняты, одна заявка стоит в очереди).

Составим ДУ для . Зафиксируем момент и найдем - вероятность того, что система в момент будет в состоянии . Эта вероятность вычисляется как вероятность суммы трех событий:

- в момент система уже была в состоянии , а за время не вышла из него (не пришло ни одной заявки и ни один из каналов не освободился);

- в момент система была в состоянии , а за время перешла в состояние (пришла одна заявка);

- в момент система была в состоянии (все каналы заняты, одна заявка стоит в очереди); а за время перешла в (либо освободился один канал и стоящая в очереди заявка заняла его, либо стоящая в очереди заявка ушла в связи с окончанием срока ожидания).

В итоге имеем:

откуда ДУ для состояния имеет вид

. (5.38)

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

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

- в момент система была в состоянии , а за время перешла в состояние (пришла одна заявка);

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

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

откуда ДУ для состояния имеет вид

(5.39)

Таким образом, мы получили для вероятностей состояний систему бесконечного числа ДУ:

(5.40)

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

Выведем, формулы, аналогичные формулам Эрланга, для вероятностей состояний системы в установившемся режиме обслуживания (при ). Из уравнений (5.40), полагая все постоянными, а все производные - равными нулю, получим систему алгебраических уравнений:

(5.41)

К ним необходимо добавить условие

. (5.42)

Найдем решение системы (5.41), для чего применим тот же прием, которым мы пользовались в случае системы с отказами; разрешим первое уравнение относительно , подставим во второе, и т. д. Для любого , как и в случае системы с отказами, получим:

(5.43)

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

и вообще при любом

. (5.44)

В обе формулы (5.43) и (5.44) в качестве сомножителя входит вероятность . Определим ее из условия (5.42). Подставляя в него выражения (5.43) и (5.44) для и , получим

откуда имеем

. (5.45)

Преобразуем выражения (5.43), (5.44) и (5.45), вводя в них вместо плотностей и «приведенные» плотности:

(5.46)

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

В новых обозначениях формулы (5.43), (5.44) и (5.45) примут вид:

, (5.47)

, (5.48)

. (5.49)

Подставляя (5.49) в (5.47) и (5.48), получим окончательные выражения для вероятностей состояний системы:

, (5.50)

. (5.51)

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

. (5.52)

Чтобы получить , нужно умножить на среднюю «плотность уходов» одной заявки и разделить на среднюю плотность заявок , т. е. умножить на коэффициент

Получим:

. (5.53)

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

Очевидно, что пропускная способность системы с ожиданием, при тех же и , будет всегда выше, чем пропускная способность системы с отказами: в случае наличия ожидания необслуженными уходят не все заявки, заставшие каналов занятыми, а только некоторые. Пропускная способность увеличивается при увеличении среднего времени ожидания . Непосредственное использование формул (5.50), (5.51) и (5.53) несколько затруднено тем, что в них входят бесконечные суммы. Однако члены этих сумм быстро убывают.

Посмотрим, во что превратятся формулы (5.50) и (5.51) при и . Очевидно, что при система с ожиданием должна превратиться в систему с отказами (заявка мгновенно уходит из очереди). Действительно, при формулы (5.51) дадут нули, а формулы (5.50) превратятся в формулы Эрланга для системы с отказами (5.29).

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

Предположим, что , и найдем предельные вероятности для чистой системы с ожиданием. Для этого, положив в формулах (5.49), (5.50) и (5.51) , получим

или, суммируя прогрессию (что возможно только при ), получим

. (5.54)

Отсюда, пользуясь формулами (5.47) и (5.48), найдем

, (5.55)

и аналогично для

. (5.56)

Среднее число заявок, находящихся в очереди; определяется из формулы (5.52) при :

(5.57)

Пример 5.2. На вход трехканальной системы с неограниченным временем ожидания поступает простейший поток заявок с плотностью [заявки/час]. Среднее время обслуживания одной заявки мин. Определить, существует ли установившийся режим обслуживания; если да, то найти вероятности , вероятность наличия очереди и среднюю длину очереди

Решение. Имеем ; . Так как , установившийся режим существует. По формуле (5.55) находим

Вероятность наличия очереди .

Средняя длина очереди по формуле (5.57) будет равна 0.89 [заявки].