научная статья по теме АНАЛИЗ МНОГОЛИНЕЙНОЙ МАРКОВСКОЙ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ С НЕОГРАНИЧЕННЫМ НАКОПИТЕЛЕМ И ОТРИЦАТЕЛЬНЫМИ ЗАЯВКАМИ Автоматика. Вычислительная техника

Текст научной статьи на тему «АНАЛИЗ МНОГОЛИНЕЙНОЙ МАРКОВСКОЙ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ С НЕОГРАНИЧЕННЫМ НАКОПИТЕЛЕМ И ОТРИЦАТЕЛЬНЫМИ ЗАЯВКАМИ»

Автоматика и телемеханика, Л- 1, 2007

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

PACS 02.50.-i

© 2007 г.

П.П. БОЧАРОВ

д-р техн. наук

(Российский университет дружбы народов, Москва), Ч. Д'АПИЧЕ, д-р филос. (Университет Салерно, Италия),

Р. МАНДЗО (Университет Салерно, Италия), A.B. ПЕЧИНКИН, д-р физ.-мат. наук (Институт проблем информатики РАН, Москва)

АНАЛИЗ МНОГОЛИНЕЙНОЙ МАРКОВСКОЙ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ С НЕОГРАНИЧЕННЫМ НАКОПИТЕЛЕМ И ОТРИЦАТЕЛЬНЫМИ ЗАЯВКАМИ1

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

1. Введение

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

В качестве аналитических моделей инфотелекоммуникационных систем, учитывающих эффекты такого рода, в последнее время широко используются системы и сети массового обслуживания (СМО и СеМО) с отрицательными заявками. Понятие отрицательной заявки в теории массового обслуживания было введено Е. Ге-ленбе [1,2]. В традиционном смысле эффект, производимый при поступлении отрицательной заявки в СМО или в некоторый узел СеМО. заключается в том. что

1 Работа выполнена ири финансовой поддержке Российского фонда фундаментальных исследований (грант 06-07-89056).

она "убивает" (разрушает) одну обычную (положительную) заявку, ожидающую в очереди, после чего обе заявки мгновенно покидают систему, при этом число ожидающих положительных заявок (если они были в очереди) уменьшается на единицу. В дальнейшем Е. Геленбе распространил понятие отрицательной заявки на случай. когда она может убивать группу заявок из очереди или полностью опустошать очередь (катастрофы) (см.. например. [3]). В СеМО были также введены понятия триггера, выталкивающего положительную заявку из одного узла сети в другой, и сигнала, который с заданной вероятностью может быть либо отрицательной заявкой (в традиционном смысле), либо триггером [3]. Обширная библиография публикаций в области исследования СеМО и CMÜ с отрицательными заявками, или так называемых G-сетей и G-систем, включая известные обобщения понятия отрицательной заявки, содержится в обзорах [4. 5].

Известные исследования в области G-сетей ограничены в основном классом ВСМР-сетей [6] и их модификаций, предполагающих пуассоновскпе потоки как положительных. так и отрицательных заявок и позволяющих получить стационарное распределений вероятностей состояний сети в мультипликативной форме.

Для G-систем предположения о пуассоновости потоков и специальном виде функций распределения времени обслуживания не являются обязательными, поэтому публикации по G-системам посвящены CMÜ с более сложными процессами поступления как положительных, так и отрицательных заявок, а также с достаточно общими процессами обслуживания.

Данная работа посвящена анализу многолинейной G-системы. поэтому ниже ограничимся кратким обзором многолинейных CMÜ с отрицательными заявками.

В [7] рассмотрена CMÜ с одним прибором с накопителем конечной емкости и повторными заявками, на которую поступает поток типа ММАР (Marked Markoviari Arrival Process), а времена обслуживания распределены экспоненциально (заметим, что обслуживание повторных заявок в некотором смысле аналогично обслуживанию в многолинейной системе). С учетом двух типов отрицательных заявок и катастрофических сбоев в [7] получен приближенный метод для расчета стационарного распределения вероятностей состояний системы. В [8] для системы M/M/n/0 с повторными заявками в предположении, что отрицательная заявка убивает случайное число заявок, найдено стационарное распределение вероятностей состояний системы и исследован нестационарный режим в условиях большой нагрузки. В [9] рассмотрена многолинейная CMÜ с накопителем конечной емкости, рекуррентным входящим потоком и марковским процессом обслуживания всех заявок на приборах: при этом число состояний процесса и интенсивности переходов между фазами зависят от числа заявок в системе. Предполагается, что поток отрицательных заявок является марковским: при этом поступившая отрицательная заявка удаляет группу положительных заявок в начале очереди. Для этой CMÜ в [9] разработан рекуррентный матричный алгоритм для расчета стационарных вероятностей состояний.

В настоящей статье исследуется многолинейная CMÜ с неограниченным накопителем. марковским входящим потоком положительных и отрицательных заявок и марковским (общим) процессом обслуживания, аналогичным рассмотренному в [9]. При этом в отличие от [9] поступившая отрицательная заявка убивает одну положительную заявку в конце очереди. Заметим, что при некоторой потере общности по сравнению с [9] при переходе от рекуррентного потока к марковскому для анализа CMÜ можно использовать марковский процесс. Это избавляет от необходимости довольно громоздкого расчета матриц, необходимых при анализе систем с помощью вложенной цепи Маркова, введенной в [9]. В силу этого матричный алгоритм, полученный в данной работе, является существенно более эффективным, чем алгоритм [9].

2. Описание системы

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

В систему поступает марковский поток заявок двух типов с числом состояний (фаз генерации заявок) /. Матрицу иптепсивпостей изменения фаз генерации заявок без поступления заявки первого типа, или положительной заявки (далее также будем называть ее просто заявкой), обозначим через Лг, а матрицу интенсивностей изменения фаз генерации заявок с поступлением заявки второго типа, или отрицательной заявки, - через Ло. Наконец, матрицу интенсивностей изменения фаз

Л

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

Л = Л + Ло +ЛЬ

Вектор п-1п = (п;П1,..., П[п1) стационарных вероятностей состояний процесса изменения фаз генерации марковского потока можно найти из системы уравнений равновесия (СУР)

П1пЛ = 7?1п

с условием нормировки П1п1 = 1.

Здесь и далее через 1 = (1,...,1)т будем обозначать вектор-столбец из единиц, размерность которого определяется из контекста (в данном случае равна I).

Обслуживание положительных заявок происходит следующим образом. Имеется некоторое положительное целое число Е, которое назовем числом обслуживающих приборов. При этом будем считать, что если в системе находится не более Е заявок, то все они обслуживаются на приборах; если же число заявок в системе г > Е, то Е го них обслуживаются на приборах, а остальные г — Е ждут начала обслуживания в очереди. Кроме того, имеется набор положительных целых чисел (чисел фаз обслуживания) .1Г, г = 0,Е.

Если в системе имеется г, г > Е, заявок и процесс обслуживания находится в состоянии г, г = 1, Jд, то за малое время Д с вероятностью Д + о(Д),

] = 1, Л-^, не зависящей от всего процесса функционирования системы, заканчива-

Е

вания изменяется на j-ю, на обслуживание становится первая заявка из очереди, а остальные заявки в очереди сдвигаются с сохранением порядка. Кроме того, с вероятностью 1л0}н+1}1}з А + о(Д), j = 1, j = г, также не зависящей от процесса функционирования системы, фаза обслуживания изменяется на j-ю, но не заканчивается обслуживание ни одной из заявок.

Случай 1 < г < Е отличается от предыдущего только тем, что за малое время А вероятность окончания обслуживания одной из заявок на приборах (а теперь все заявки находятся на приборах) равна Д + о(Д), г = 1, Jr, j = 1, .1г-1, а вероятность просто изменения фазы обслуживания на '-ю равна 10Г^ Д + о(Д), г^ = = j = г ■

г =0 Д

только с вероятностью |l00ij Д + о(Д), г, j = 1^0, j = г, измениться с г-й на j-ю фаза обслуживания.

Кроме того, если в системе находится г 0 < г < Е, заявок и поступает новая (положительная) заявка, то с вероятностью г = 1^г, j = 1^г+1, фаза об-

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

Далее положим JR = . и будем обозначать матрицы из элементов ¡л1тг^ и ц0гг^, г = 1,Д, через М1г и М0г, матрицы из элементов и - через М1 и

М0, а матрицу из элементов ¡л00^ - через М00. Положим также М = М1 + М0.

Через 7т0^ = (поиь • • • ,поии) будем обозначать вектор стационарных вероятностей состояний процесса изменения фаз обслуживания заявок в предположении, что в системе имеется бесконечное число заявок. Тогда он находится из СУР

По^М = Пи с условием нормировки ПошД = 1-

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

Далее будем предполагать, что р < 1, где чнсло р, определяемое формулой

П1пЛ11

Р =----,

7?1пЛ01 + 7То^М11 будем называть нагрузкой на систему.

Цель настоящего исследования определение основных стационарных характеристик функционирования системы.

3. Стационарное распределение очереди

Стационарное распределение числа заявок в рассматриваемой системе совп

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком