автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Математические методы и алгоритмы расчета некоторых немарковских моделей массового обслуживания

На правах рукописи

Чаплыгин Василий Васильевич

МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РАСЧЕТА НЕКОТОРЫХ НЕМАРКОВСКИХ МОДЕЛЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ

05.13.17 — теоретические основы информатики

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2005

Работа выполнена в Московском государственном техническом университете имени Н.Э. Баумана

Научный руководитель: доктор физико-математических наук,

профессор А.В. Печинкин

Официальные оппоненты: доктор технических наук,

профессор П.П. Бочаров кандидат физико-математических наук, доцент П.В. Шнурков

Ведущая организация: Факультет «Вычислительная математика

и кибернетика» Московского государственного университета им. М.В. Ломоносова

Защита состоится «_» 2005 г. в мин. на заседании

Диссертационного совета Д 002.077.01 при Институте проблем передачи информации РАН по адресу: 127994, г. Москва, ГСП-4, Б. Каретный пер., 19.

С диссертацией можно ознакомится в библиотеке Института проблем передачи информации РАН.

Автореферат разослан ^Ш^Лть г.

Ученый секретарь Диссертационного совета Д 002.077.01

доктор физико-математических наук / , И.И. Цитович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Исследованию математических моделей очередей в различных технических устройствах, особенно в современных инфо-телекоммуникационных системах, уделяется большое внимание. В области аналитического и имитационного расчета систем массового обслуживания (СМО) опубликовано значительное число работ. Существенный вклад в разработку и анализ классических моделей теории массового обслуживания внесли А.Я. Хинчин, Б.В. Гнеденко, A.A. Боровков, Г.П. Башарин, Д. Кендалл, Д. Литтл, Д. Кокс, В. Смит, JI. Такач, Ф. Поллачек. Но на практике до недавнего времени аналитические расчеты велись по формулам, предложенным А.К. Эрлангом в начале прошлого века.

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

1 Бочаров П.П., Печинкин A.B. Теория массового обслуживания. — М.: Изд-во РУДН, 1995. - 529 с. ~ • • - ——.

»'•^•s-'Лй «!.С. А

С

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

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

Цель работы. Диссертационная работа направлена на решение следующих задач:

1. Разработка математических методов расчета стационарных характеристик моделей СМО:

— многолинейной СМО с полумарковским входящим потоком, марковским обслуживанием и накопителем конечной и бесконечной емкости;

— однолинейной СМО с рекуррентным входящим потоком и групповым марковским обслуживанием;

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

2. Разработка алгоритмов для вычисления основных стационарных характеристик рассмотренных систем по полученным математическим соотношениям.

3. Создание прикладного программного комплекса для расчета стационарных характеристик по предложенным численным алгоритмам.

Научная новизна и основные результаты диссертации. Все основные результаты диссертации являются новыми. На защиту выносятся следующие результаты:

1. Предложен математический метод расчета основных стационарных

характеристик модели СМО БМ/МБР/п/г с накопителем конечной и бесконечной емкости.

2. Разработаны алгоритмы расчета стационарных характеристик модели СМО БМ/МБР/п/г по полученным математическим соотношениям. На основе базовой модели предложены упрощенные алгоритмы расчета стационарных характеристик моделей СМО в/МБР/п/г и БМ/МБР/1/г.

3. Разработаны математический метод и алгоритмы расчета стационарных характеристик для модели СМО О/ВМБР/1/г с групповым марковским обслуживанием и накопителем конечной и бесконечной емкости.

4. Предложены математический метод и алгоритмы расчета стационарных характеристик для модели СМО в/МБР/п/г с марковским потоком отрицательных заявок.

5. Созданы вошедшие в единый программный комплекс модули расчета стационарных характеристик по предложенным алгоритмам для моделей СМО БМ/МБР/п/г, БМ/МБР/п/оо и их частных случаев, которые допускают расчет по упрощенным алгоритмам.

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

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

Реализация результатов работы. На основе теоретических результатов диссертации написаны программные модули расчета моделей СМО БМ/МБР/п/г, БМ/МБР/п/оо, вошедшие в единый прикладной программный комплекс для расчета стационарных характеристик многолинейных моделей СМО, зарегистрированный в Реестре программ для ЭВМ Российского агентства по патентам и товарным знакам

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

— Аппаратно-программные средства для построения информационно-телекоммуникационных компьютерных систем на базе технологий высокоскоростной передачи и коммутации данных;

— Новые математические методы, алгоритмы и программные средства расчета и оптимизации современных инфотелекоммуникационных систем и сетей;

— Математические и компьютерные модели информационных, телекоммуникационных и управляющих систем;

— Исследование общемировых тенденций развития систем управления и разработка комплекса математических моделей для оценки основных оперативно-технических показателей АСУ ВС РФ с учетом ее развития па основе поэтапного внедрения новых информационных технологий.

Апробация работы. Результаты, полученные в ходе выполнения диссертационной работы, докладывались на

— международном семинаре «Распределенные компьютерные и телекоммуникационные сети (ВСС1\Т-2003)» в Институте проблем передачи информации Российской Академии наук (Москва, июль 2003 года);

— на XXIII семинаре по стационарным проблемам в стохастических моделях в Памплоне (Испания, май 2003 года);

— на XXIV международном семинаре по стационарным проблемам в стохастических моделях в Юрмале (Латвия, 7-10 сентября 2004 года);

— на научных семинарах МГТУ им. Н. Э. Баумана.

Публикации. По теме диссертации опубликовано 9 работ, список которых приводится в конце автореферата.

V

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, разделенных на пункты, заключения и списка литературы. Текст изложен на 99 страницах, включая 12 рисунков и 4 таблицы. Список литературы содержит 54 наименования.

СОДЕРЖАНИЕ РАБОТЫ

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

Глава 1 посвящена исследованию системы массового обслуживания БМ/МБР/п/г с полумарковским входящим потоком, марковским обслуживанием, конечным и бесконечным накопителем.

В пункте 1.1 описывается модель п-линейная СМО БМ/МвР/п/г с накопителем емкости т (см. рис. 1).

Рис. 1.

Полумарковский процесс генерации заявок определяется следующим образом. Имеется полумарковский процесс, функционирующий на конечном множестве фаз {1,...,т}, т < оо, и управляемый стохастической матрицей переходных вероятностей М = (Му), г,;' = 1,гос полумарковским ядром А(х) = (Лу(ж)), 1,з = 1 ,т. Предполагается, что матрица

00

М неразложима и непериодична, а йу = / хйА^{х) < оо для любых

_ _ о

г,; = 1 ,го, где Ац(х) = х).

Марковский процесс обслуживания заявок определяется следующим образом. Если в системе находится к, 0 < к ^ п+г, заявок, то процесс обслуживания может находиться на одной из 1к, 1к < 00 > Ф^ обслуживания.

Тогда, если в некоторый момент в системе находится к, к = 1, п + г, заявок и фаза обслуживания равна г, г = 1, то за «малое» время Д (Д —> 0) с вероятностью Л-^Д + о(Д) фаза изменится на j, j = 1, lk, и все заявки будут продолжать обслуживаться, а с вероятностью п® Д + о(Д) фаза изменится на j, j = 1, lh-ъ но обслуживание одной из заявок закончится и она покинет систему. Матрицы из элементов A¡f и Пу обозначены через Л/; и iVjt, к = 1,71 +г. Предполагается, что — I при к = п,п + г, матрицы Ak = А совпадают при к = n,n + r, а матрицы Nk = N совпадают при к = п + 1,п + г. На свободном периоде фаза обслуживания i, i — 1, Iq, не изменяется. При к = 0, п — 1 предполагается, что если в момент поступления очередной заявки в системе имеется к других заявок и фаза обслуживания равна i, г = 1, h, то после поступления новой заявки она с вероятностью изменится на j, j — 1, h+ь Матрица из элементов обозначена через

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

В пункте 1.2 рассмотрена система SM/MSP/n/r с конечным накопителем (г < оо). Пусть r)(t) и — фазы генерации и обслуживания заявок в момент времени t, a vit) — число заявок в системе в этот момент. Случайные величины щ = rj(rn + 0), £п = £(т„ + 0) и vn = и(тп + 0) задают соответственно фазы генерации и обслуживания и число заявок в системе непосредственно после момента поступления гг-й заявки. По последовательным моментам т„, п ^ 0, поступления заявок в систему строится однородная вложенная цепь Маркова = {т]п, и„), п ^ 0} с множеством состояний

X = {{h3,k), г = Ï7m, j = ÏJk, k = l,n + r},

где индексы i,jvik указывают соответственно фазы генерации и обслуживания и число заявок в системе непосредственно после момента поступления заявки.

Через р*к, г = lk{u — 1) + v, и = 1, m, v = 1, h, к = 1, и + г, обозначена

стационарная по вложенной цепи Маркова вероятность того, что в системе имеется к заявок и фазы генерации и обслуживания равны и и и, и положим Pi- = (pi,i> • • • 'Pmh,k)> Р* = (Ри ■ ■ -.Pn+r)- Для построения матрицы переходных вероятностей введены вспомогательные матрицы Fk(x) и Fjm(x) и матрицы экспоненциальных моментов Ак и Акт. Для р* справедлива система уравнений равновесия

п+г

р! = Е р£А о»

Ш=1

п+г _

Р*к= Е P*wK,k-\, к-2,п,

w=k-1

п+г _

Р*к= Е PwAw~k+1, fc = n+l,n + r-l,

Рп+г = Pn+r-Ио + P;+r(^0 + ^l),

с условием нормировки р*1 = 1. Эта система имеет единственное решение, которое находится методом исключения состояний вложенной цепи Маркова2.

Векторы pi = (plk,...,р~1Ш1к), к = 0, п + г, где рГк, i = lk+1(u-l) +v, и = 1,т, v = 1, lk+i — стационарная вероятность того, что поступающая в систему заявка застанет в ней к других заявок и процессы генерации и обслуживания после ее поступления окажутся на фазах и и v, определяются соотношениями

Рк=Рк+ъ к = 0,п + г-2,

п+г

Рк = Ylp*}Ai-k> к = п + г-1,п + г. j=k

Векторы рк = (р1,ь • • • ,PiM,k), к = 0, п + г, гдер^, i = 1, lk+i - стационарная вероятность того, что поступающая в систему заявка застанет в ней к других заявок и процесс обслуживания после ее поступления окажется на фазе i (без учета фазы генерации), определяются соотношением

Рк = Pfc (lm ® k = Q,n + r,

где ® — символ кронекерова произведения матриц.

2 Печинкин А.В. Об одной инвариантной системе массового обслуживания // Math. Operationsforsch. und Statist. Ser. Optimization. — 1983. — Vol. 14, №3. — S. 433-444.

Стационарная вероятность 7г потери заявки из-за заполненности накопителя в момент ее прихода в систему определяется формулой

я- = Pn+r^ol-

Для модели СМО SM/MSP/n/r найдены стационарное распределение числа заявок в системе в произвольные моменты времени, среднее время ожидания начала обслуживания и функция распределения времени ожидания начала обслуживания, которая представлена в виде

=1 - тггЕ ( Е ¿WiW)i-

В пункте 1.3 рассмотрена система SM/MSP/n/oo с бесконечным накопителем. Векторы стационарных вероятностей р\ по моментам поступления, начиная с номера к — п -f-1, ищутся в виде р\ = p*nGk~n, где матрица G находится из матричного функционального уравнения

00

fc=о

Первые п векторов р\ находятся из приведенной системы уравнений равновесия. Для модели СМО SM/MSP/n/oo получены соотношения для среднего значения

00

w = -p*G(I - G)~l £; &(1т ® (—Л-1) 1 j=о

и функции распределения W(x) времени ожидания начала обслуживания в стационарном режиме

W(x) = l-p*nG(I-G)-1R(x)l,

где

00 > {=0

В пункте 1.4 рассмотрена модель СМО G/MSP/n/r, являющаяся частным случаем модели системы SM/MSP/n/r. Для G/MSP/n/r найдены распределение числа заявок в системе по моментам поступления и в

произвольные моменты времени, вероятность потери заявки (для системы с накопителем конечной емкости), среднее значение и функция распределения времени ожидания начала обслуживания.

В пункте 1.5 рассмотрена модель системы 5М/М5Р/1/т, для которой получены упрощенные расчетные формулы стационарных характеристик. Эта система рассматривается с марковским обслуживанием на приборе. Она является обобщением модели однолинейной СМО с рекуррентным входящим потоком в/МБР/!/г. Для модели СМО БМ/М8Р/1/г с накопителем конечной и бесконечной емкости получены стационарное распределение числа заявок в системе по моментам поступления и по времени, вероятность потери заявки (для системы с конечным накопителем), расчетные формулы для средних значений и функций распределений времен ожидания начала обслуживания и пребывания произвольной заявки в системе,

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

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

00

распределения А(х). Предполагается, что среднее время а = / хИА{х)

о

между поступлениями заявок конечно.

Групповое марковское обслуживание заявок определяется следующим образом. Пусть в некоторый момент в системе на обслуживании находятся т ^ 1 заявок и фаза обслуживания равна г, г = 1,1. Тогда за «малое» время Д с вероятностью А^-Д + о(Д) фаза изменится на з, $ = 1,1, и все заявки продолжат обслуживание. Кроме того, за это же время с вероятностью А^Д + о(Д), 1 < к < т, фаза изменится на з и обслужится ровно к заявок. Матрицы из элементов Л^, т ^ 0, = 1,1 обозначены через Лт. С вероятностью А^*Д + о(Д) фаза изменится на з и обслужатся

все находящиеся в системе заявки. Матрицы из элементов Щ*, т > О,

_ 00

1,3 — 1,1, обозначены через Л^, причем Л^ = ^ Л*,. Предполагается, что

к—т

оо

матрица Л* = ^ неразложима. На свободном периоде фаза процесса

к=О

обслуживания не меняется. Для рассмотренной в этой главе модели СМО найдены распределение

числа заявок в системе по моментам поступления в систему и по времени, вероятность потери заявки (для системы с конечным накопителем). Получены формулы для среднего значения и функции распределения времени пребывания заявки в системе для модели СМО с конечным и бесконечным накопителем.

В главе 3 рассмотрена модель многолинейной СМО в/МвР/п/т с рекуррентным потоком заявок, марковским обслуживанием (см. рис. 2) и потоком отрицательных заявок.

Марковский процесс обслуживания определяется таким же образом, как и для базовой системы ЗМ/МБР/п/т в пункте 1.1.

Процесс поступления отрицательных заявок определяется следующим образом. Пусть в случайные моменты времени в систему поступают отрицательные заявки, которые убивают заявки в накопителе. Убитые заявки на обслуживание не принимаются и покидают систему. Предполагается, что процесс поступления отрицательных заявок является марковским процессом с непрерывным временем и конечным числом д состояний, который описывается следующим образом. За «малое» время Д с вероятностью 7,°Д + о(Д), = 1,д, фаза процесса изменится на з, и ни одной заявки в накопителе убито не будет при условии, что в начальный момент процесс находился на фазе г, и с вероятностью 7,™Д + о(Д), 1,з = фаза процесса изменится на з, и ровно то заявок в накопителе будут убиты и покинут систему при условии, что в начальный момент процесс находился на фазе г и в накопителе находилось более то заявок. Матрицы из элементов 7??, г, з = 1, то = 0,1,2,..., обозначены через Гт. Если в некоторый момент времени в накопителе находилось то, то > 0, заявок, то за «малое» время Д с вероятностью *Д + о(Д), г, j = 17?, фаза процесса изменится на j и все т заявок будут убиты и покинут систему при условии, что в начальный момент процесс находился на фазе г. Матрицы из элементов 7у*> ЬЗ = 1, <?, то = 0,1,2,..., обозначены через Г^, причем

оо

г; = £г*, то = 0,1,2,..., Г* = Гц.

к=т

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

дают те заявки из накопителя, которые пришли в систему раньше других. Предполагается, что матрица Г* является неразложимой, а матрица Г| ненулевой. Предполагается, что на периоде, когда в накопителе отсутствуют заявки, фаза процесса поступления отрицательных заявок не меняется.

Рис. 2.

Для рассматриваемой модели СМО с конечным и бесконечным накопителем найдены стационарные распределения числа заявок в системе по моментам поступления и в произвольные моменты времени и получены формулы для следующих стационарных характеристик: вероятность того, что заявка обслужится, вероятность потери заявки из-за полного накопителя (для системы с накопителем конечной емкости), вероятность 6 потери произвольной заявки (с учетом возможного ее убийства). Показано, что функция распределения \¥(х) времени ожидания начала обслуживания произвольной заявки при условии того, что заявка попадет на прибор, имеет вид: для модели СМО с конечным накопителем

1 /п-1 п+г-1 \

ИЧ*) = ТТ7 ЕР'Г + Е РьГ^-п(х) ,

\й=0 к=п /

где

х

Ок(х) = I Рк(у)(1®Н)с1у, о

для модели СМО с бесконечным накопителем где

X

D(x) = JR{y){I ® N)dy, о

00

R(x) =

1=0

В главе 4 рассматриваются алгоритмы расчета основных стационарных характеристик моделей СМО, рассмотренных в трех первых главах диссертации.

Расчет вспомогательных матриц основан на возможности их представления в экспоненциальной форме. Для модели СМО SM/MSP/n/r в пункте 4.1 получены рекуррентные формулы расчета коэффициентов суммы ряда, которые содержит экспоненциальная форма представления вспомогательных матриц Fk(x), Fi-m(x), R(x), матриц экспоненциальных моментов А}:> А\.т и других вспомогательных матриц.

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

Обслуживание каждым прибором имеет фазовый тип с параметрами:

М — квадратной матрицей порядка s с элементами /¿у;

Ъ — вектором размерности s с координатами

Положим также

s 3=1

Состояние марковского процесса обслуживания при к заявках характеризуется мультииндексом i = (ii,... ,is), где ij — число заявок на приборах, обслуживаемых на фазе j. Предполагается, что i\ +... + is = к.

Для любого вектора г с координатой ij > 1 положим:

ц — вектор, все координаты которого, кроме ^'-й, совпадают с координатами вектора г, а ]-я координата равна ц - 1;

г™ — вектор, все координаты которого, кроме и и/-й, совпадают с координатами вектора г, а ]-я и ги-я координаты равны ^ - 1 и гш + 1 соответственно.

Кроме того, для любого вектора г обозначим через гю — вектор, все координаты которого, кроме ги-й, совпадают с координатами вектора г, а ии-я координата равна гш + 1.

Теперь матрицы Лfc, Л, Л^, N и £2*, общей СМО БМ/МБР/п/г определим следующим образом:

= у > 1, з ф ги, к = 1, п - 1;

8

/в = — 1;

= ЭД, у >1, к = = ¿»ш, А = 1, та — 1;

Агг^ = УЩт, Ъ' > 1, .?' ^

8

ХЦ = ^ ^ Ц/лц)

3=1

пну = ущЬу,, у ^ 1-

Остальные элементы матриц Л*, Л, Л^, N и С1к равны нулю.

Для численных расчетов производится линейная нумерация состояний. При наличии & заявок на приборах состоянию, характеризуемому мульти-индексом г = (¿1,..., гя), соответствует состояние с линейным номером

8-1 к-»1—1 и = Е Е +

ш=1 ¿=о

В пункте 4.1 получены формулы расчета стационарного распределения У(х) времени пребывания заявки СМО БМ/РН/п/г с конечным и бесконечным накопителем.

В пункте 4.2 для модели СМО С/МБР/п/г указаны расчетные формулы для коэффициентов ряда экспоненциальных форм вспомогательных матриц Рк(х), Ркт(х), В.(х), матриц экспоненциальных моментов Ак, Акт.

В пунктах 4.3 и 4.4 получены расчетные формулы для матричной функции К(х) для моделей СМО ЯМ/МБР/!/оо и С/В МБР/1/оо.

Для модели СМО О/МБР/п/г с потоком отрицательных заявок в пункте 4.5 получены расчетные формулы для вспомогательных матриц ^(ж), Ркт{х), матриц экспоненциальных моментов Акт, матричных функций £>&(х), входящих в соотношения для функции распределения \У(х) времени ожидания начала обслуживания.

На основе теоретических результатов диссертации написаны модули расчета стационарных характеристик моделей СМО вида БМ/РН/п/г и БМ/РН/п/оо, вошедшие в единый программный комплекс. Описанию этого программного комплекса посвящена глава 5. В этой главе рассмотрены результаты расчетов стационарных характеристик нескольких моделей СМО, произведенных с помощью этого комплекса. Программный комплекс позволяет рассчитывать стационарные характеристики следующих СМО:

1. Однолинейные системы с рекуррентным потоком, обслуживанием фазового типа и накопителем конечной (М/РН/1/г, НЕ/РН/1/г, В/РЕ/1/т) и бесконечной (М/РН/1/оо, НЕ/РН/1/оо, О/РН/1/оо) емкости;

2. Однолинейные системы с рекуррентным потоком, марковским обслуживанием и накопителем конечной (М/МБР/1/г, НЕ/МБР/1/г, В/МБР/1/г) и бесконечной (М/МБР/1/оо, НЕ/МБР/1/оо, И/МБРД/оо) емкости;

3. Однолинейные системы с полумарковским потоком генерации заявок, обслуживанием фазового типа на каждом приборе и накопителем конечной (БМ/РН/1/г) и бесконечной (БМ/РН/1/оо) емкости;

4. Однолинейные системы с полумарковским потоком генерации заявок, общим марковским обслуживанием на приборе и накопителем конечной (БМ/МАР/1/г) и бесконечной {БМ/МАР/1/оо) емкости;

5. Многолинейные системы с рекуррентным потоком, обслуживанием

фазового типа на каждом приборе и накопителем конечной (М/РН/п/г, НЕ/РН/п/т, D/PH/n/r) и бесконечной {М/РН/п/оо, НЕ/РН/п/оо, D/PH/n/oo) емкости;

6. Многолинейные системы с полумарковским потоком генерации заявок, обслуживанием фазового типа на каждом приборе и накопителем конечной (SM/PH/n/r) и бесконечной (SM/PH/п/оо) емкости.

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Чаплыгин В.В. Система массового обслуживания G/BMSP/1/r // Информационные процессы. 2003. Т. 3. № 2. С. 97-108.

2. Печинкин A.B., Чаплыгин В.В. Исследование системы массового обслуживания SM/MSP/n/r // Труды международного семинара «Распределенные компьютерные и телекоммуникационные сети. Теория и приложения (DCCN-2003)». Москва. 2003. С. 58-65.

3. Печинкин A.B., Чаплыгин В.В. Стационарные характеристики системы массового обслуживания G/MSP/n/r // Вестник РУДН. Сер. «Прикладная математика и информатика». 2003. № 1. С. 119-143.

4. Pechinkin A., Chaplygin V. The Stationary Characteristics of an SM/MSP/n/r Queueing System // XXIII Seminar on Stability Problems for Stochastic Models. Pamplona. Spain. 2003. P. 32.

5. Чаплыгин B.B. Система массового обслуживания SM/MSP/1/r // Вестник МГТУ им. Н.Э. Баумана. Сер. «Естественные науки». 2004.

№ 2. С. 60-74.

6. Печинтн А.В., Чаплыгин В.В. Стационарные характеристики системы массового обслуживания SM/MSP/n/r // Автоматика и телемеханика. 2004. № 9. С. 85-100.

7. Pechinkin A., Chaplygin V. The mathematical methods and the algorithms for a multichannel queues calculation I I Transactions of XXIV International Seminar on Stability Problems for Stochastic Models. Jurmala. Latvia. 2004. P. 1-10.

8. Чаплыгин В.В. Система массового обслуживания G/MSP/n/r с потоком отрицательных заявок // Информационные процессы. 2005. Т. 5. № 1.

9. Печинкин A.B., Чаплыгин В.В. Математическая модель для расчета многолинейных СМО // Тезисы докладов II научной сессии Института проблем информатики Российской академии наук. Москва. 2005. Р. 94-96.

С. 1-19.

Принято к исполнению 08/09/2005 Исполнено 12/09/2005

Заказ №1031 Тираж: 100 экз

ООО «11-й ФОРМАТ» ИНН 7726330900 Москва, Варшавское ш., 36 (095) 975-78-56 (095)747-64-70 www.autoreferat.ru

РНБ Русский фонд

2007-4 11175

Введение

1 Стационарные характеристики системы массового обслуживания SM/MSP/n/r

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

1.2. Система SM/MSP/n/r с конечным накопителем.

1.3. Система SM/MSP/п/оо с бесконечным накопителем

1.4. Система G/MSP/n/r

1.4.1. Система G/MSP/n/r с конечным накопителем

1.4.2. Система G/MSP/п/оо с бесконечным накопителем

1.5. Система массового обслуживания SM/MSP/1/r.

1.5.1. Система SM/MSP/1/r с конечным накопителем

1.5.2. Система SM/MSP/1/r с бесконечным накопителем

2 Стационарные характеристики системы массового обслуживания G/BMSP/1/r

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

2.2. Конечный накопитель.

2.3. Бесконечный накопитель

3 Стационарные характеристики СМО G/MSP/n/r с потоком отрицательных заявок

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

3.2. Конечный накопитель.

3.3. Бесконечный накопитель

4 Алгоритмы расчета СМО

4.1. Алгоритмы расчета системы SM/MSP/n/r.

4.2. Алгоритмы расчета системы G/MSP/n/r.

4.3. Алгоритмы расчета системы SM/MSP/1/r.

4.4. Алгоритмы расчета системы G/BMSP/1/r.

4.5. Алгоритмы расчета системы G/MSP/n/r с потоком отрицательных заявок.

5 Описание программного комплекса. Примеры расчета моделей систем массового обслуживания

С момента появления первых телефонных сетей возникла необходимость решения задач расчета вероятностно-временных характеристик, среди которых основными являются стационарное распределение числа заявок в системе (для телефонных сетей важнейшей характеристикой является вероятность потери заявки), стационарные распределения времени ожидания начала обслуживания и времени пребывания заявки в системе. Эти задачи впервые поставлены известным датским ученым А.К. Эрлангом [42], который и является родоначальником теории массового обслуживания (ТМО). Внимание многих математиков привлекли возможности применения этой теории к важнейшим практическим задачам в самых различных сферах: при эксплуатации различных транспортных систем, в медицинском обслуживании, в страховом деле, при профилактическом обслуживании технических устройств. Значительный вклад в разработку и анализ классических моделей ТМО внесли А.Я. Хинчин, Б.В. Гнеденко, А.А. Боровков, Г.П. Башарин, Д. Кендалл, Д. Литтл, Д. Кокс, В. Смит, JI. Такач, Ф. Поллачек. Бурное развитие информационно-телекоммуникационных технологий и сетей различного назначения направило методы ТМО, в первую очередь, на решение задач именно в этой области.

Модели, рассмотренные Эрлангом, имели пуассоновский входящий поток и экспоненциальное обслуживание. Но еще при анализе телефонных сетей было замечено, что во многих случаях требование экспоненциальное™ времени обслуживания не выполнено. Первой попыткой более адекватного описания обслуживания в реальных системах стало использование моделей с рекуррентным обслуживанием. Большое число работ посвящено модели однолинейной системы массового обслуживания (СМО) M/G/1/оо1 с накопителем бесконечной емкости. Для исследования указанной модели СМО разработаны различные методы исследования: построение вложенной цепи Маркова по момендальнейшем будем придерживаться классификации СМО, которую ввел Д. Кендалл [47]. Заметим, что существует другая классификация СМО, с которой подобно можно ознакомится в работе А.А. Боровкова [4]. там обслуживания заявок, исследование с помощью виртуального времени ожидания, введение дополнительной переменной, исследование с использованием процессов восстановления. Метод построения вложенной цепи, впервые предложенный А.Я. Хинчиным [25], позволил вычислить для СМО M/G/1/оо лишь некоторые характеристики, связанные с числом заявок в системе только в специальные моменты времени. Применение метода исследования с помощью виртуального времени ожидания приводит к интегро-дифференциальному уравнению Такача [54], которое разрешается с помощью преобразований Лапласа-Стилтьеса (ПЛС). Недостаток этого метода заключается в невозможности использования его для вычисления характеристик очереди. При использовании метода введении дополнительной переменной, как правило, в качестве дополнительной переменной рассматривается прошедшее или остаточное время обслуживания. С полным обоснованием этого метода можно ознакомится в работе Ю.К. Беляева [31]. Метод исследования с помощью процессов восстановления позволяет найти совместное нестационарное распределение практически любых характеристик обслуживания. Методы, разработанные для расчета модели однолинейной СМО M/G/1/r, позволили получить стационарные характеристики для однолинейных моделей СМО, обобщающих входящий поток и процесс обслуживания. В частности, в последнее время для описания СМО было предложено использовать марковский входящий поток. Тем не менее, несмотря на то, что созданы определенные методы расчета с марковским входящим потоком [6, 11, 15, 17, 18, 40, 41, 48, 50], в этом направлении остается немало нерешенных проблем, связанных с вычислительными сложностями.

К настоящему времени не создано методов исследования многолинейной СМО M/G/n/oo, которые позволяли бы находить для нее стационарные показатели в сколько-нибудь пригодном для анализа виде (Тем более это касается СМО G/G/n/oo. Даже для однолинейной СМО G/G/1/оо полученные на сегодняшний день результаты ориентированы на решение лишь качественных задач ТМО. При этом подавляющее число работ посвящено рассмотрению характеристик, связанных с временем пребывания заявок в системе, и так или иначе опирается на уравнение Линдли [49]. Еще более глубокие качественные результаты относительно СМО GI/GI/1/оо с зависимыми временами между поступлениями заявок и временами обслуживания можно найти в монографиях А.А. Боровкова [4, 5]). Исключением такого положения вещей являются системы с немногими частными случаями рекуррентного потока (например, СМО M/D/n/oo, для которой получены соотношения для расчета стационарного распределения числа заявок в системе). Еще хуже обстоит дело с многолинейными СМО M/G/n/r с конечным накопителем. Они остаются практически неизученными (исключением является телефонная система M/G/n/О с потерями, для которой Б.А. Севастьяновым [32] получены стационарные вероятности состояний, которые фактически совпадают с формулами Эрланга).

Шагом вперед стало появление в начале 80-х годов прошлого века алгоритмических методов (см. работы [10, 38]), предложенных впервые М.Ф. Ньютсом [51] и позволивших на основе современных высокопроизводительных вычислительных устройств производить расчеты стационарного распределения очереди для модели СМО с марковским входящим потоком и фазовым распределением времени обслуживания, гораздо более адекватно описывающих функционирование ин-фотелекоммуникационных систем. Однако, предложенные там математические методы расчета, основанные на матричной модификации метода прогонки для решения систем уравнений равновесия, оказались неустойчивыми к погрешностям вычислений, что не позволило вычислить пользовательские показатели СМО с большим числом фаз входящего потока и обслуживания и большими емкостями накопителей. В настоящее время на основе этого подхода разработаны методы для расчета многолинейных СМО вида РН/РН/n/r и МАР/РН/п/г с накопителем конечной и бесконечной емкости (см., например, работу [37]).

Пуассоновский входящий поток заявок, в отличие от экспоненциального времени обслуживания, долгое время вполне удовлетворял исследователей. Однако, по мере развития инфотелекоммуникационных технологий появились системы, для которых использование моделей с пуассоновским, и даже с обобщающим его марковским входящим потоком является неприемлемым. Это привело к изучению модели СМО G/M/n/r с рекуррентным входящим потоком вида и экспоненциальным обслуживанием. Для модели СМО G/M/n/r удалось получить как стационарные вероятности состояний, которые представимы в геометрическом виде, так и стационарное распределение времени ожидания начала обслуживания и времени пребывания заявки в системе. Наконец, совсем недавно появились работы, позволяющие рассчитывать стационарные характеристики однолинейной СМО вида G/MSP/1/r с марковским процессом обслуживания и накопителем конечной и бесконечной очереди [7, 9]. В [7] для системы G/MSP/1/r в случае конечного числа мест ожидания, т. е. г < оо, было получено стационарное распределение длины очереди. Однако предложенная там вычислительная процедура хорошо работала только для относительно небольших значений г. В [9] предложен другой способ исследования системы G/MSP/1/r, основанный на методе последовательного исключения состояний вложенной цепи Маркова. Метод исследования СМО с помощью построения вложенной цепи Маркова дал возможность получить стационарные распределения времени ожидания начала обслуживания и времени пребывания произвольной, принятой к обслуживанию заявки. В работах Албореса с соавтором [31, 32] была рассмотрена многолинейная система с рекуррентным потоком, марковским обслуживанием и накопителем конечной емкости. Но полученные там алгоритмы расчета стационарных вероятностей применимы лишь к системам с малым числом приборов, фаз обслуживания и мест ожидания.

Среди новейших инфотелекоммуникационных систем встречаются системы, требующие применение моделей СМО с полумарковским потоком, обобщающим рекуррентный и марковский потоки (полумарковский поток в большинстве случаев, когда использование рекуррентного или марковского процесса является неадекватным, весьма точно позволяет отразить свойства описываемой реальной системы). Однолинейная система с полумарковским входящим потоком, двумя типами заявок, марковским обслуживанием была рассмотрена в работе А.В. Печинкина и С.И. Тришечкина [19]. До настоящего времени не было работ, посвященных моделям многолинейных СМО с полумарковским входящим потоком и марковским обслуживанием.

В диссертации также рассмотрена модель СМО с отрицательными заявками. Модели СМО с отрицательными заявками тесно связаны с G-сетями [8, 1] и являются предметом интенсивных исследований. Первая работа, в которой была исследована однолинейная СМО с неограниченным накопителем с отрицательными заявками, принадлежит Е. Геленбе с соавторами [43]. В дальнейшем системы с отрицательными заявками рассматривались в работах П. Харрисона [44], П.Харрисона с соавторами [45, 46, 39], Н.Байера и О.Боксмы [36], И.Атенсиа с соавторами [33, 34, 35], Д.Албореса, П.П.Бочарова и Д. Ю.Любина [29, 30]. Хотя понятие отрицательной заявки было введено Е. Геленбе сравнительно недавно, однако в ТМО уже давно известны СМО с ограниченным временем пребывания или, что то же самое, СМО с нетерпеливыми заявками (см., например, Б.В. Гнеденко [13]), которые по своей сущности практически ничем не отличаются от отрицательных заявок.

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

Кратко остановимся на содержании диссертации.

Выход

Время между поступлениями заявок | Ш\

Рис. 12. Задание условной ФР для элемента (1,1) ядра полу Маркове кого процесса генерации заявок из примера 36.

1пгмгнт 1) w пппумпркоагного npoucrca Экспоненциальный пра^асс 'J | Сохранить | быход

Параметр I э~М|

Рис. 13. Задание условной ФР для элемента (2.1) ядра пол у Маркове кого процесса генерации заявок из примера 36.

Заключение

В диссертационной работе решены следующие задачи:

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

2. Разработаны алгоритмы для вычисления основных стационарных характеристик рассмотренных систем по полученным математическим соотношениям.

3. Для моделей многолинейных СМО с полумарковским входящим потоком на основе предложенных численных алгоритмов создан прикладной программный комплекс для расчета следующих стационарных характеристик: стационарного распределения числа заявок в системе по времени и по моментам поступления заявок в систему; стационарной вероятности потери заявки; средней длина очереди; среднего числа занятых приборов; среднего числа заявок в системе; стационарного распределения времени ожидания начала обслуживания и времени пребывания заявки в системе и их средних значений.

1. Башарин Г. П., Бочаров П. П., Коган А. Я. Анализ очередей в вычислительных сетях. Теория и методы расчета. Москва, Наука, 1989. 336 с.

2. Беллман Р. Введение в теорию матриц. Москва, Физматгиз, 1969. 367 с.

3. Боровков А.А. Вероятносные процессы в теории массового обслуживания. Москва, Наука, 1972. 368 с.

4. Боровков А.А. Асимптотические методы в теории массового обслуживания. Москва, Наука, 1980. 367 с.

5. Бочаров П.П. Анализ системы массового обслуживания MAP/G/1/r конечной емкости. // Вестник РУДН. Сер. «Прикладная математика и информатика». 1995. № 1. С. 52-67.

6. Бочаров П. П. Стационарное распределение конечной очереди с рекуррентным потоком и марковским обслуживанием // Автоматика и телемеханика. 1996. № 9. С. 66-78.

7. Бочаров П.П., Вишневский В. М. G-сети: развитие теории мультипликативных сетей. // Автоматика и телемеханика. 2003. № 5. С. 4674.

8. Бочаров П. П., ДАпиче Ч., А. В. Печинкин, Салерно С. Система массового обслуживания G/MSP/1/r // Автоматика и телемеханика. 2003. JVs 2. С. 127-143.

9. Бочаров П.П., Печинкин А.В. Теория массового обслуживания. Москва, Изд-во РУДН, 1995. 529 с.

10. Бочаров П.П., Печинкин А.В., Д'Апиче Ч., Фонг Н.Х. Однолинейная система обслуживания конечной емкости с групповым марковским потоком и полумарковским обслуживанием // Вестник РУДН. Сер. «Прикладная математика и информатика». 2001. № 1. С. 64-79.

11. Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. Москва, Наука, 1984. 320 с.

12. Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. Москва, Наука, 1987. 336 с.

13. Королюк В. СТурбин А. Ф. Полумарковские процессы и их приложения. Киев, Наукова думка, 1976. 184 с.

14. Наумов В.А. Марковские модели потоков требований // Системы массового обслуживания и информатика. 1987. № 1. С. 67-73.

15. Печинкин А.В. Об одной инвариантной системе массового обслуживания // Math. Operationsforsch. und Statist. Ser. Optimization. 1983. Vol. 14, № 3. S. 433-444.

16. Печинкин А.В. Однолинейная система обслуживания с марковским входящим потоком требований // Автоматика и телемеханика. 1996. № 4. С. 100-110.

17. Печинкин А.В. Ветвящийся процесс, управляемый цепью Маркова. // Вестник РУДН. Сер. «Прикладная математика и информатика». 1999. № 1. С. 115-127.

18. Печинкин А.В., Тришечкин С.И. Система SM2/MSP/l/r с дисциплиной случайного выбора заявки на обслуживание и общим накопителем // Системы и средства информатики: спец. выпуск. Москва, Изд-во института проблем инфоматики РАН, 2002. С. 160-180.

19. Печинкин А.В., Чаплыгин В.В. Исследование системы массового обслуживания SM/MSP/n/r // Труды международного семинара «Распределенные компьютерные и телекоммуникационные сети. Теория и приложения (DCCN-2003)». Москва, 2003. С. 58-65.

20. Печинкин А.В., Чаплыгин В. В. Стационарные характеристики системы массового обслуживания G/MSP/n/r // Вестник РУДН. Сер. «Прикладная математика и информатика». 2003. № 1. С. 119-143.

21. Печинкин А.В., Чаплыгин В.В. Стационарные характеристики системы массового обслуживания SM/MSP/n/r // Автоматика и телемеханика. 2004. № 9. С. 85-100.

22. Печинкин А.В., Чаплыгин В.В. Математическая модель для расчета многолинейных СМО // Тезисы докладов II научной сессии Института проблем информатики Российской академии наук. Москва, 2005. Р. 94-96.

23. Севастьянов Б. А. Эргодическая теоремадля марковских процессов и ее приложение к телефонным линиям с отказами // Теория вероятностей и ее прим. 1957. Т. 2, Вып. 1. С. 106-116.

24. Хинчин А.Я. Работы по математической теории массового обслуживания. Москва, Физматгиз, 1963. 236 с.

25. Чаплыгин В.В. Система массового обслуживания G/BMSP/1/r // Информационные процессы. 2003. Т. 3, № 2. С. 97-108.

26. Чаплыгин В.В. Система массового обслуживания SM/MSP/1/r // Вестник МГТУ им. Н.Э. Баумана. Сер. «Естественные науки».2004. № 2. С. 60-74.

27. Чаплыгин В.В. Система массового обслуживания G/MSP/n/r с потоком отрицательных заявок // Информационные процессы. 2005. Т. 5, № 1. С. 1-19.

28. Albores J.F., Bocharov P.P., Luybin D.Yu. Two-stage exponential queueing system with internal losses, feedback and negative arrivals // Вестник РУДН. Сер. «Прикладная математика и информатика». 2003. № 1. С. 70-84.

29. Albores J.F., Bocharov P.P., Luybin D.Yu. On two-stage exponential system with losses, feedback and negative customers // Proc. of Internal Conference «Distributed Computer and Communication Networks.

30. Stochastic Modelling and Optimization (DCCN-2003)». Moscow, 2003. P. 100-105.

31. Albores J.F., Tajonar S.F. The multi-server GI/MSP/c/r queue // Transactions of XXIV International Seminar on Stability Problems for Stochastic Models. Jurmala, Latvia, 2004. P. 110.

32. Albores J.F., Tajonar S.F. Analysis of the GI/MSP/c/r Queueing System // Информационные процессы. 2004. Т. 4, № 1. С. 46-57.

33. Atencia I., Aguillera G., Bocharov P. P. On the M/G/1/0 queueing system under LCFS PR discipline with repeated and negative customers with batch arrivals // Proc. Oper. Res. 42 Annual Conf. University of Swamsea. 2000. P. 30-34.

34. Atencia I., Bocharov P. P. On the M/G/1/0 queueing system under LCFS PR discipline with repeated and negative customers with batch arrivals // Proc. 3-rd Europ. Cong. Math. Barcelona, 2000. P. 133.

35. Atencia I., DApiche C., Manzo R., Salerno S. Retrial queueing system with several input flows and negative customers and LCFS PR discipline // Proc. Fourth Int. Workshop on Queueing Networks with Finite Capacity. Ilkley, U. K., 2000. P. 1-9.

36. Bayer N., Boxma O. J. Wiener-Hopf analysys of an M/G/l queue with negative customers and of related class of random walk // Queueing Systems. 1996. V. 23. P. 301-316.

37. Bocharov P.P., DApice C., Pechinkin A.V., Salerno S. Queueing Theory. Utrecht, Boston: VSP, 2004. 446 p.

38. Bocharov P.P., Naumov V.A. Matrix-geometric stationary distribution for the PH/PH/l/r queue // Electron. Informmationsverarb. Kyb. 1986. Vol. 22, № 4. P. 179-186.

39. Chakka R., Harrison P. G. A Markov modulated multi-server queue with negative customers — The MM CPP/GE/c/L G-queue // Acta Informatika. 2001. V. 37. P. 881-919.

40. Dudin A.N., Klimenok V.I. BMAP/SM/1 queue with Markov modulated retrials // TOP. 1999. V. 7. P. 267-278.

41. Dudin A.N., Klimenok V.I. Alternative algorithm for characteristics calculation of BMAP/SM/1 system with the multi-threshold control // Queues: Flows, Systems, Networks. Minsk, BSU, 2001. V. 16. P. 81-86.

42. Erlang A.K. Solution of some problemsin the theory of probabilities of significance in automatic telephone exchanges // The Post Office Electrical Engineers Journal. 1917. Vol. 10. P. 189-197.

43. Gelenbe E., Glynn P., Sigman K. Queues with negative arrivals. // J. Appl. Prob. 1991. V. 28. P. 245-250.

44. Harrison P. G. The MM CPP/GE/c G-queue: sojourn time distribution // Queueing Sytems. 2002. V. 41. P. 271-298.

45. Harrison P. G., Pitel E. Sojourn times in single server queues with negative customers // Queueing systems. 2002. V 41. P. 943-963.

46. Harrison P. G., Pitel E. The M/G/l queue with negative customers // Adv. Appl. Prob. 1996. V. 28. P. 540-566.

47. Kendall D.J. Stochastic processes ocurring in the theory of queues and their analysys by the method of the embedded Markov chains // Ann. Math. Stat. 1953. № 24. P. 338-354.

48. Klimenok V.I. The Controlled BMAP/SM/1 Retrial Queue with Markov Modulated Retrials. // Proc. of Internat. Conference «Distributed Computer and Communication Networks. Stochastic Modelling and Optimization (DCCN-2003)». Moscow, 2003. C. 81-88.

49. Lindley D. V The theory of queueswith a single server // Proc. Camb. Phil. Soc. 1962. Vol. 58, № 3. P. 497-520.

50. Lucantoni D.M., Neuts M.F. Simpler proofs of some properties of the fundamental period of the MAP/G/1 queue // J. Appl. Prob. 1994. V. 31. P. 235-243.

51. Neuts M.F. Matrix-geometric solutions in stochastic models. An algorithmic approach. Baltimore and London, The Johns Hopkins Univ. Press, 1981. 332 p.

52. Pechinkin A., Chaplygin V. The Stationary Characteristics of an SM/MSP/n/r Queueing System // XXIII Seminar on Stability Problems for Stochastic Models. Pamplona, Spain, 2003. P. 32.

53. Pechinkin A., Chaplygin V. The mathematical methods and the algorithms for a multichannel queues calculation // Transactions of XXIV International Seminar on Stability Problems for Stochastic Models. Ju-rmala, Latvia, 2004. P. 110.

54. Takacs L. Introduction to the theory of queues. New York, Oxford University Press, 1962. 268 p.