Исследование систем массового обслуживания с отрицательными заявками и бункером для вытесненных заявок тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

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

Разумчик Ростислав Валерьевич

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

01.01.05 — теория вероятностей и математическая статистика

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

Москва - 2011

1 6 НЮН 2011

4849997

Работа выполнена на кафедре теории вероятностей и математической статистики факультета физико - математических и естественных наук Российского университета дружбы народов.

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

Печинкин Александр Владимирович

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

Каштанов Виктор Алексеевич

доктор физико-математических наук, профессор Ушаков Владимир Георгиевич

Ведущая организация: Институт проблем передачи информации имени А.А. Харкевича Российской академии наук

Защита состоится « ШОК^ 2011 г. в ч. &0 мин. на заседании

Диссертационного совета Д 212.133.07 при Московском государственном институте электроники и математики (техническом университете) по адресу: 109028, г. Москва, В. Трехсвятительский пер., д.З.

С диссертацией можно ознакомиться в библиотеке Московского государственного института электроники и математики (технического университета), по адресу: 109028, г. Москва, Б. Трехсвятительский пер., д.З.

Автореферат разослан « Мь ЯГ 2011 г.

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

к.ф.-м.н., доцент ~ТГ, Ыиур-^Ь

П.В. Шнурков

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

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

Для учета подобных факторов Е. Геленбе, П. Глинн, К. Сигман в своей статье1 предложили концепцию отрицательных заявок, и связанных с ними сетей и систем массового обслуживания, которые получили название соответственно G-сети и G-снстемы. Классический принцип действия отрицательных заявок заключается в в том, что при поступлении в СМО или в некоторый узел СеМО она "убивает*1 (разрушает) одну обычную заявку, ожидающую в очереди, после чего обе заявки мгновенно покидают систему. К настоящему времени исследовано большое число различного вида G-сетей и G-систем. Рассматривались случаи, когда отрицательные заявки удаляют группу ожидающих в очереди заявок или полностью опустошают очередь (катастрофы); были введены понятия триггера, выталкивающего заявку из одного узла сети в другой, и сигнала, который с заданной вероятностью может быть либо отрицательной заявкой, либо триггером. Подробное исследование публикаций в области исследования G-систем и G-сетей до 2003 года, включая известные обобщения, приводится, например, в обзорах Бочарова П.П. и Вишневского В.М.2 , и Artalejo J.R..3. В теоретических работах после 2003 года внимание уделялось исследованию различных модификаций G-систем, например, с марковским входящим потоком, марковским обслуживанием, специальными дисциплинами обслуживания и "убийства" заявок. Из недавних прикладных работ в этой области стоит отметить исследования по применению G-систем в телефонии для моделирования работы call-центров, при анализе систем инвентаризации и анализу механизмов балансировки нагрузки в телекоммуникационных сетях4,5.

1Ge!enbe Е., Glynn P., Sigman К. Queues with negative arrivals // Journal of Applied Probability. 1991. V. 28. P. 245-250.

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

3Artalejo J.R. G-networks: A versatile approach for work removal in queueing networks. Eur. J. Oper. Res., 2000, vol. 126, pp. 233-249.

4 Yang Woo S. Multi-server retrial queue with negative customers and disasters // Queueing Syst. 2007. № 55. P. 223-237.

5Manuel Paul, Sivakumar В., and Arivarignan G. Perishable Inventory System with Post-

Значительное внимание уделяется и изучению систем с отрицательными заявками в дискретном времени6,7, поскольку они играют важную роль в оценке производительности систем и сетей связи, позволяя учитывать дискретность функционирования реальных систем.

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

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

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

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

1. Введена новая модель системы массового обслуживания с отрицательными заявками и бункером для вытесненных заявок.

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

poned Demands and Negative Customers // Journal of Applied Mathematics and Decision Sciences. 2007.

eLt Ma A Class of Geom/Geom/l Discrete-time Qucueing System with Negative Customers. Int.J.NonlinearSci., V. 5, No. 3, 2008. P.275-280.

1 Hyun Min Parka, Won Seo к Yangb, Kyung Chul Cham The Geo/G/1 Queue with Negative Customers and Disasters. Stochastic Models. V. 25 Issue 4. 2009.

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

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

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

Разработанные в диссертации математические методы и вычислительные алгоритмы могут применяться для анализа характеристик систем распределенных вычислений и систем распределенных баз данных и ДР-

Исследования проводились в рамках грантов Российского фонда фундаментальных исследований (РФФИ) № 06-07-89056-а "Математические модели, методы, алгоритмы и программное обеспечение, основанное на веб-технологиях, для проведения фундаментальных исследований в области анализа производительности сетевых систем" и № 09-07-12032-офи_м "Разработка математические методов, вычислительных алгоритмов и программных средств для решения задач моделирования информационно-вычислительных и телекоммуникационных систем".

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

Личное участие автора. Научному руководителю диссертации Печинкину A.B. принадлежат постановки задач и помощь в выборе методов исследования. Автору диссертации принадлежат аналитические преобразования и выводы, доказательства теорем, проведение численных расчетов и имитационного моделирования. В работе [4], опубликованной в соавторстве с Мандзо Р. и Касконе Н., соавторам принадлежит участие в постановке задачи и обсуждение методов исследования.

Реализация результатов работы.

Результаты диссертации использовались в научно-исследовательских

5

работах, проводимых Институтом проблем информатики Российской академии наук:

1. Разработка общих базовых математических методов расчёта систем массового обслуживания, функционирующих в дискретном времени (свидетельство № 01200903883).

2. Исследование систем и сетей массового обслуживания специального вида и информационно-управляющих систем с новыми видами обратной связи (свидетельство № 01200807411).

3. Исследование систем и сетей массового обслуживания специального вида с ненадёжными приборами и отрицательными заявками.

Результаты исследований вошли в программу "WEB-ориентированный программный комплекс удаленного расчёта стационарных характеристик систем массового обслуживания"8.

Достоверность и обоснованность.

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

Апробация работы. Результаты работы были представлены на следующих научных конференциях и международных семинарах:

— XLII-XLVI Всероссийские конференции по проблемам математики, информатики, физики и химии. Москва, Российский университет дружбы народов (РУДН), 2006-2010;

— международная конференция "International Conference on Ultra Modem Telecommunication^' — ICUMT 2010 (18-20 October 2010, Moscow, Russia);

— международный семинар "Распределенные компьютерные и телекоммуникационные сети" — DCCN 2010 (26-28 Октября 2010, Москва, Россия);

— V отраслевая научная конференция "Технологии Информационного общества", посвященная 90-летию МТУСИ (9-10 Февраля 2011, Москва, Россия);

Кроме того, результаты работы докладывались на заседаниях следующих научно-исследовательских семинаров:

— научный семинар ФГУП ЦНИИС и секции "Моделирование сетей связи, информационных систем и процессов' МНТОРЭС им. A.C. Попова, декабрь 2010;

— научный семинар кафедры исследования операций Московского государственного института электроники и математики (технический университет), 2011;

— научные семинары по теории массового обслуживания в институте проблем информатики Российской академии наук (ИПИ РАН), 2008-2011.

8Дата регистрации РОСПАТЕНТом 11.01.2010г., свидетельство о регистрации № 2010610026.

Публикации. Результаты диссертации опубликованы в 11 работах соискателя, перечень которых приведен в конце автореферата. Научные работы [4, б, 11] опубликованы в журналах, входящих в утвержденный ВАК перечень ведущих рецензируемых научных изданий, в которых должны быть размещены основные научные результаты диссертации на соискание ученой степени кандидата наук.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения. Объем работы составляет 137 страниц текста, в том числе 8 рисунков и 18 таблиц. Список литературы включает в себя 71 наименование, в том числе и публикации соискателя по теме исследования.

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

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

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

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

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

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

Длительности обслуживания заявок как из накопителя, так и из бункера имеют экспоненциальное распределение с одним и тем же параметром /х.

В параграфе 1.2 доказываются две теоремы с помощью которых находятся стационарные характеристики марковского процесса {X(t) — (v(t),ri(t)), t > 0}, описывающего стохастическое поведение рассматриваемой СМО во времени, где v{t) — общее число заявок, находящихся в накопителе и на обслуживающем приборе в момент времени t, а т}{1) — число заявок в бункере. Приведем их формулировки.

Теорема 1.1. Стационарное распределение общего числа заявок в системе {рп, п > 0} имеет вид

рп=(\-р)рП, 71 >0.

где р = \/(L — загрузка системы.

Физический смысл полученного в теореме 1.1 результата заключается в том, что с точки зрения общего числа заявок в системе рассматриваемая СМО ничем не отличается от СМО M/M/1/oo. Кроме того, учитывая, что период занятости для данной системы совпадает с периодом занятости СМО А//Л//1 /оо, то необходимым и достаточным условием существования стационарного режима функционирования рассматриваемой СМО является условие р = А//х < 1.

Пусть Рк.т — стационарная вероятность того, что в накопителе и на приборе находятся к заявок, а в бункере ожидают m заявок, вытесненных из накопителя. Введем производящую функцию (ПФ)

оо оо

P{u,v)^^2^2pkmukvm, 0 < U < 1, 0 < V < 1.

Ь=0 т=0

Теорема 1.2. ПФ Р(и, v) совместного стационарного распределения числа, заявок в накопителе и бункере {pk,т> к, m > 0} имеет вид

рГ > и /Gfe-0+*-<»-«>

Р(М' "> = (1 - Р)-ХМи-щ)-'

где

, . \ + ц + \~± у/(Х + р+ A-)2-4A(/i+ X-v) Щ,2 = =-—-.

Обозначим через pk,. стационарную вероятность того, что в накопит еле и на пиборе находится к заявок, а через — вероятность того, что в бункере находится m заявок. Тогда для данных маргинальных распределений имеют место следующие два следствия из теоремы 1.2.

Следствие 1.1. Стационарное распределение общего числа заявок в

накопителе и на приборе {ptА: > 0} умеет вид

Ро,- = Poo = 1 - Р, Рк,- = - Q)Qk~1, fc > 1-

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

Следствие 1.2. Стационарное маргинальное распределение числа заявок в бункере {р.,т, m > 0} рассчитывается по формулам

11 tl Р-,0 = дТРП + РОО + Р10. P.m = jrPl.m+1 + Plm, Ш > I,

где стационарные вероятности pim задаются формулой?

Рш = (л + Л->-+1 (("1Г(Г )mu2(0) + Amui(°)+ I V2<"v<ffi2r ni l-^MV-r

¿f i! r=l ЧА(Л + А' + А~-2Аиа(0))2<~1

__(A-)'Am-' 1\

(2Aui(0) — A — /x — A")2'"1] /' m~

Используя результаты теоремы 1.2, возможно последовательно вычислять вероятности рьп- Соответствующий алгоритм приводится в конце параграфа.

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

— вытесняется первая заявка из очереди в накопителе, на обслуживание выбирается первая заявка из очереди в накопителе, и последняя заявка из очереди в бункере (обозначается, как FIRST-FIFO-LIFO);

— вытесняется последняя заявка из очереди в накопителе, на обслуживание выбираются последние заявки из очередей в накопителе и и бункере {LAST-LIFO-LIFO)\

— вытесняется первая заявка из очереди в накопителе, на обслуживание выбираются первые заявки из очередей в накопителе и бункере, (FIRST-FIFO-FIFO)\

23десь [Jh = 1, Eti =

- (-1Г-'(А)'(А-Г A(A + /i + A--2Au2(0))2'-

(д-удт-I

(2Aui(0) - A - /х - A")2'"1

— вытесняется последняя заявка из очереди в накопителе, на обслуживание выбирается последняя заявка из очереди в накопителе и первая заявка из очереди в бункере (LAST-LIFO-FIFO);

— вытесняется последняя заявка из очереди в накопителе, на обслуживание выбирается первая заявка из очереди в накопителе и последняя заявка из очереди в бункере {LAST-FIFO-LIFO);

— вытесняется первая заявка из очереди в накопи геле, на обслуживание выбираются последние заявки из очередей в накопителе и бункере (FIRST-LIFO-LIFO);

— вытесняется последняя заявка из очереди в накопителе, на обслуживание выбираются первые заявки из очередей в накопителе и бункере

{LAST-FIFO-FIFO):

— вытесняется первая заявка из очереди в накопителе, на обслуживание выбирается последняя заявка из очереди в накопителе и первая заявка из очереди в бункере (FIRST-LIFO-FIFO).

Для каждой из этих комбинаций была доказана теорема о виде (в терминах ПЛС) стационарного распределения времени ожидания. Приведем только некоторые из них.

Теорема 1.3. ПЛС ^(s) стационарного распределения V(x) времени ожиданья начала обслуживания поступившей в систему заявки при дисциплине FIRST-FIFO-LIFO имеет вид

A A"+/i-A А~р(1 -q)j(s\ ц)

ф) = [ e->4V{x) = 1-Р+-А-. А" + +

^ ; J w Ц+-Х- s + A-4- ц- A s + A" +fi-\-r{s;fiy

о

где.

Теорема 1.4. ПЛС стационарного распределения У(х) времени ожидания начала обслуживания поступившей в систему заявки при дисциплине ЬЛЗТ-Ь1РО-ЫРО имеет вид

^(в) = 1 — р Н---7 8 Д+А Н--:------.-г-.

где

+ ^ + А + ц + А- - ^+ А +ц 4- А~)» - 4А(р + А")^/(2А).

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

указанной дисциплины. Как положено в силу формулы Литтла и, как показано в диссертационной работе, стационарные средние значения времен ожидания начала обслуживания для всех дисциплин совпадают и равны 1и> = -(¿/(0) = р/(ц — А). Однако стационарные дисперсии времени ожидания для всех дисциплин различны. Для большого числа рассчитанных примеров, как показано в приложении, минимальной дисперсией обладает дисциплина ЬАБТ-Р1РО-Р1РО.

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

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

В параграфах 2.1 и 2.2 рассматриваются однолинейные СМО с отрицательными заявками и бункером для вытесненных заявок как в главе 1, только в одном случае - с бункером емкости г (г < оо) (п.2.1), а во втором - с накопителем емкости г (п. 2.2). Для этих двух систем доказаны теоремы, которые следуют из монографии М.Р. Ые^Б9, определяющие совместное стационарное распределение и условие его существования. Приведем результат для системы из параграфа 2.1.

Инфинитезимальная матрица переходов С} однородного неприводимого марковского процесса {Х(£), í ^ 0}, описывающего стохастическое поведение рассматриваемой СМО, является блочной трехдиагональной вида

Q =

(Nq Ai 0 0 0

Л/0 Ni Л 0 0 ..

0 M N Л 0 ..

0 0 M N А ..

\ ; ; ; ; ; ••./

где M, Nh Л, N -следующий вид:

квадратные матрицы размерности (г +1) х (г +1) имеют

M =

h о

0

о о

о о

А-ц + Х~/

, Nt

-(М + Л)

M

0 ... -(/i + A) 0 0 ... p -(/x + A)/

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

Л = XI, N = -(Л + (J. + X~)I, a No = (-Л), Ai = XelT, M0 = fieu где I — единичная матрица, êî — вектор-столбец размерности (r-f 1), у которого все элементы равны нулю, кроме элемента на г'-м месте.

Обозначим через рт = (рп, Pq, ...) вектор стационарных вероятностей МП {X(t), t > 0}, где р[ = (рю,р,и ■ ■ •, Pir), a Pij — стационарная вероятность того, что в накопителе i, а в бункере — j заявок.

Теорема 2.1. Неприводимый МП {^(t), t ^ 0} является положительно возвратным тогда и только тогда, когда минимальное неотрицательное решение R уравнения А -I- RN + R2M = 0 имеет спектральный радиус p(R) < 1, и если существует положительный вектор (ро, Po) такой, что выполняется

poiVo + pjMo = 0, poAi + p£(Ni + RM) = бТ.

Тогда стационарные вероятности МП {X(t), t ^ 0} имеют вид

Ро =---=, рТ = -PöAjWi + RM)~lR, i Z 0,

l-AtiNi + RM^il-Ryn ю u

где I — единичная матрица размерности (г + 1) х (г + 1).

Для системы в параграфе 2.1 стационарное распределение существует тогда и только тогда, когда А/Ао < 1, где А0 - единственный действительный положительный корень уравнения (относительно А)

г

A- Аг-'(/1 + А-)' + X-)r+1 = 0. ¿=о

Для системы из параграфа 2.2 необходимым и достаточным условием существования стационарного режима является условие А/(/х + А") < 1.

В параграфе 2.3 исследуется одноканальная СМО с отрицательными заявками и бункером для вытесненных заявок как в главе 1, с той разницей, что теперь накопитель и бункер имеют одинаковую емкость г (г < оо). Инфинитезимальная матрица переходов марковского процесса, описывающего поведение этой СМО, также является блочной трехдиагональной. Этот процесс относится к обобщенным процессам рождения и гибели и для нахождения его стационарного распределения, как и в п.2.1—2.2, можно воспользоваться стандартными методами10.

Однако для рассматриваемой системы использовался другой метод, который ранее применялся11 для анализа системы с приоритетами,

"Подробное изложение методов приведено, например, в гл. 4, §6 Бочаров П.П., Печинкин A.B. Теория массового обслуживания. М.: РУДН, 1995.

11 Avrachenkov К.Е., Vilchevsky N.O., Shevljakov G.L. Priority queueing with finite buffer size and randomized push-out mechanism // Proceedings of the ACM international conference on measurement and modeling of computer (SIGMETMC 2003). San Diego, 2003. P. 324-335.

ограниченным буфером и вероятностным выталкивающим механизмом. Доказана теорема, позволяющая находить совместное стационарное распределение вероятностей состояний. В силу громоздкости формулировка этого результата в автореферате не приводится. Опишем вкратце идею метода. Сначала для совместного стационарного распределения {Ркт, 0 < к < г, 0 < т < г} числа заявок в накопителе и бункере находится вид двойной ПФ. Затем, используя свойство аналитичности ПФ, а также вид маргинальных распределений чисел заявок в накопителе и бункере, получаются уравнения, в результате решения которых с помощью многочленов Чебышева второго рода и многочленов Гегенбауэра удается выписать формулы для определения вероятности простоя системы, а затем и расчета вероятностей ркт-

В параграфе 2.4 показано как результаты, касающиеся совместного стационарного распределения числа заявок в накопителе и бункере, полученные для однолинейных СМО из главы 1 и 2, переносятся на случай, когда в этих же системах имеется не один, а несколько приборов. Обозначим через {роо, Рк.т, к > 0, m > 0} совместное стационарное распределение вероятностей состояний однолинейной СМО из главы 1, в которой прибор обслуживает заявки с интенсивностью n/i. А через [ж{0, 0 < г < п — 1, ir„+k-i,m, к > 1, то > 0} — стационарное распределение вероятностей состояний соответствующей п-линейной СМО, в которой каждый прибор обслуживает заявки с интенсивностью Как показано в диссертационной работе, стационарные распределения {Тд-ио, Тп+*-1.т, к > 1, т > 0} и {роо, Рк.т, к > 1, m > 0} совпадают с точностью до некоторой постоянной, зависящей только от п, т.е.

ТГп-1,0 = С(п)роо, 7Гп+Ь-1,т = с(п)рь„, к > 1, ТП > 0.

Постоянная с(п) определяется с помощью условия нормировки для п-лииейной СМО и равна

а остальные вероятности тгш, 0 < г < п — 2 определяются из СУР для гг-линейной СМО и имеют вид

то = ^ ~ ty тг„_1,о, 0 < г < п - 2.

Поскольку стационарное распределение {роо, рк,т, к > 1, m > 0} для СМО из главы 1 уже найдено в терминах вычислительных алгоритмов, то, воспользовавшись вышеприведенными формулами, можно рассчитать

совместное стационарное распределение в соответствующей п-линейной СМО.

Для нахождения совместного стационарного распределения в п-линейных СМО, аналогичных рассмотренным в п.2.1—2.3, достаточно воспользоваться полученными результатами для онолинейных СМО и приведенными выше формулами12. Для нахождения условия существования стационарного распределения в п-линейной системе необходимо в уже найденном условии существования для соответствующей однолинейной системы положить пц вместо ¿1.

Глава 3 посвящена нахождению вероятностно-временных стационарных характеристик очередей в той же системе, что и в главе 1, только функционирующей в дискретном времени.

В параграфе 3.1 приводится описание системы. В СМО с накопителем неограниченной емкости, поступает геометрический поток обычных (вероятность поступления на такте равна а) и отрицательных (вероятность поступления на такте равна с) заявок; распределение времени обслуживания — геометрическое (вероятность окончания обслуживания на такте равна Ь). Дискретное время измеряется в фиксированных интервалах (тактах). Величина такта равна к, /г > 0, единиц времени. Все возможные измерения в системе происходят в моменты времени п/г, п = 1,2,... Величина такта И в диссертации, для простоты, принята равной 1. Все изменения состояния СМО происходят в конце такта в следующем порядке: если на этом такте завершилось обслуживание заявки на приборе (с вероятностью Ь), то она покидает систему и на прибор из накопителя или если накопитель пуст, то из бункера сразу же поступает следующая заявка; затем (с вероятностью а) поступает обычная заявка и если прибор занят, то помещается в накопитель, а если прибор свободен, то сразу же начинает обслуживаться; наконец, в систему (с вероятностью с) поступает отрицательная заявка, которая выбивает обычную заявку из накопителя и перемещает ее в бункер. Если отрицательная заявка в момент поступления в СМО застает накопитель пустым, то она тут же покидает систему, не оказывая на нее никакого воздействия.

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

Т е о р е и я 3.1. Стационарное распределение общего числа заявок в системе по маментны поступления {р®, п > 0} имеет вид

?п = (1-6)6», п > 0, 6 = ^.

ПВ СУР, описывающой поведение однолинейной СМО, необходимо предварительно заменить интенсивность обслуживания р на пр..

С точки зрения общего числа заявок в системе рассматриваемая СМО совпадает с обычной СМО Осот¡Ссогп/1 /оо без отрицательных заявок. Необходимым и достаточным условием для существования стационарного режима функционирования рассматриваемой СМ О является условие р = а / Ь < 1.

Пусть рект — стационарная вероятность поступающей заявке застать застать прибор занятым, а в накопителе и в буфере к и т заявок соответственно.

Теорем а 3.3. ПФ Р(и, у) совместного стационарного распределения числа заявок в накопителе и бункере {р^, к, т > 0} имеет вид

Ь=0 ш=0

V)

-Л1"«)"2 « ,

ab-—-J—pfj0+

+ âbc(v — u)uQi (v) + (v — и) ^(abc + abc)u -f ab— 4- abcj Qo(v)

ос оо

причем система уравнений для Qo(v) = Ротут и Qiiv) = X) Р\гпут>

т=О т=0

имеет вид

( - Ui(v) N

(и - щ(1>)) I (аЬс + аЬс)и,(и) 4-аЬ +abc\ Qo(w)+

+ âbc(v - m(«))ui(w)Qi(v) = 0, г = ТД

v

ее решение единственно, а — 1 < tti(f) < 0 < U2(v) < 1 < из (г;) — корни уравнения

г (и, г») = аЬё»3 + [аЬсг — (аВ 4- ab + 5бс 4- bac)] и24-

+ ¡abc -f- (abc + âbcjvju + âbcv — 0.

В качестве следствия из теоремы 3.3 доказано, что стационарное маргинальное распределение к > 0} числа заявок в накопителе,

начиная с pf., является геометрическим

- Т _ аЪ пе - ~ 0 k > 1

где

из(1) = + abc + bac + \J(ab + abc + bac)2 4- Aabcabr^j j(2ahc).

Учитывая, что Р(и, V) трудно использовать для вычисления двумерного стационарного распределения рект, в параграфе 3.2 сформулирована и доказана теорема, определяющая рекуррентный алгоритм для его вычисления. Ввиду громоздкости формулировка этого результата в автореферате не приводится.

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

ртят-р/ро-ргро.

Теорема 3.4. Стационарное распределение времени ожидания начала обслуживания заявки при дисциплине Р1Я5Т-Р1РО-Р1РО в терминах ПФ ш(г) имеет вид

л 5ЫУ-1){Ьс + Ьси3{1)г) Ы1)-и1)(и3(1)-и2)(1-Ьсг)

4- счР^й^ащг + аг, 1г(г)), /1(2)^+0^ ^«гСайг-г + ог, Н{г)), ,

где

= С1С4(ащг+аг,Н(г))щ(ащг+аг, к(г))+С2С{(ай2г+аг,1г(г))щ(ащг+аг,к(г)), «1,2 = «1,2(2) = (сЬг + сЬг ^ ^(сЬ + сЬ)2г2 + 4(1 - ~рг)сЬг)/(2 -

«1.2 = ûlx(z,v) = (cb+cbv Т- \J (cb + cbv)2 + Adbv(\ -zJi))/(2 - 2zJI),

ci,2 = ci,2(2, v) = тс/\J (cb + cbv)2 + 4cbv( 1 - zp),

. ^ _ c2(z)[(6S + bac + bacû2)z - 1] + b - _ (сфас(й2 - щ)г + b)(l - bz) 1 — (bâ + bac + bacûi)z (1 — (bâ + bac -f bacûi)z)bz

c_

X

]2(z) = £ - bzû 1 + bzQ(bacû2 + (bac + bac 4- Ьас)щ + ba + bac + 6ae)j x £(¿2 — «i)([l — z(6a + 5ac)][l — z(bac + bâc + Ъас + Ьас(щ -4-г12))]—

— bacz2[bâ + bac + bac — 6aëû17i2])j , a—l<ûi<0<ti2<l — решения уравнения

bâcz + (bac +bac + bâcjzu + [(bac + bac -f bac)z — 1 \u2 + baczu3 = 0.

Дифференцируя cu(z) можно найти моменты любых порядков стационарного распределения времени ожидания начала обслуживания. В частности, среднее значение определяется выражением и> = a/(l) = ab/(b5 — bb),

16

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

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

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

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

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

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

1. Мандзо Р., Касконе Н., Разумник Р.В. Экспоненциальная система массового обслуживания с отрицательными заявками и бункером для вытесненных заявок. Тезисы ХЫ1 Всероссийской конференции по проблемам математики, информатики, физики и химии. М.: Изд-во РУДН, 2006.

2. Разумник Р.В. Система массового обслуживания с отрицательными заявками и бункером для вытесненных заявок в дискретном времени. Тезисы

17

XL1I1 Всероссийской конференции по проблемам математики, информатики, физики и химии. М.: Изд-во РУДН, 2007. С. 36.

3. Разумник Р.В. О временных характеристиках экспоненциальной системы массового обслуживания с отрицательными заявками и бункером для вытесненных заявок. Тезисы XLIV Всероссийской конференции по проблемам математики, информатики, физики и химии. М.: Изд-во РУДН, 2008. С. 55.

4. Мандзо Р., Касконе Н., Разумчик Р.В. Экспоненциальная система массового обслуживания с отрицательными заявками и бункером для вытесненных заявок // Автоматика и телемеханика. 2008. № 9. С. 103-113.

5. Разумчик Р.В. Стационарные характеристики экспоненциальной системы массового обслуживания полностью конечной емкости с отрицательными заявками и бункером для вытесненных заявок. Тезисы докладов XLV Всероссийской конференции по проблемам математики, информатики, физики и химии. М.: Изд-во РУДН, 2009. С. 125-126.

6. Печинкин A.B., Разумчик Р.В. Система массового обслуживания с отрущательными заявками и бункером для вытесненных заявок в дискретном времени // Автоматика и телемеханика. 2009. № 12. С. 109-120.

7. Разумчик Р.В. Стационарные характеристики экспоненциальной системы массового обслуживания с отрицательными заявками и бункером для вытесненных заявок в случае накопителей различной емкости. Тезисы докладов XLVI Всероссийской конференции по проблемам математики, информатики, физики и химии. М.: Изд-во РУДН, 2010. С. 42.

8. Разумчик Р.В. Система массового обслуживания с отрицательными заявками, конечным накопителем и бесконечным бункером для вытесненных заявок. Proceedings of the International Conference on Distributed computer and communication networks. Moscow, Russia, October 26-28, 2010. P. 21&-223.

9. Pechinkin A.V., Razumchik R. V. Waiting Characteristics of Queueing System Geo\Geo\\ with Negative Claims and a Bunker for Superseded Claims in Discrete Time. International Conference on Ultra Modern Telecommunications 18-20 October 2010, Moscow. P. 1051-1055.

10. Печинкин A.B., Разумчик Р.В. О времени ожидания при некоторых дисциплинах обслуживания в системе с отрицательными заявками и бункером. Proceedings of the International Conference "Modern Probabilistic Methods for Analysis and Optimization of Information and Telecommunication Network^, Minsk, 2011. C. 207-212.

11. Разумчик Р.В. Система массового обслуживания с отрицательными заявками, бесконечным накопителем и конечным бункером для вытесненных заявок в непрерывном времени. Вестник Российского университета дружбы народов. Серия: Математика, информатика, физика. М.: Изд-во РУДН, 2011. № 1. С. 75-81.

Подписано к печати " _23_" мая 2011 г. Отпечатано в отделе оперативной полиграфии МИЭМ.

Москва, ул. М. Пионерская, д. 12. Заказ № 120 . Объем 1,0 п.л. Тираж 100 экз.

Введение

1 Одноканальная экспоненциальная система массового обслуживания с отрицательными заявками и бункером для вытесненных заявок

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

1.2. Стационарное распределение вероятностей состояний

1.3. Стационарное распределение времени ожидания начала обслуживания.

2 Стационарные характеристики в экспоненциальных системах массового обслуживания с различными ограничениями на емкости накопителя и бункера, и на число приборов

2.1. Случай бесконечного накопителя и конечного бункера

2.2. Случай конечного накопителя и бесконечного бункера . 5R

2.3. Случай конечного накопителя и конечного бункера

2.4. Случай нескольких приборов.

3 Одноканальная марковская система массового обслуживания с отрицательными заявками и бункером для вытесненных заявок в дискретном времени

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

3.2. Стационарное распределение вероятностей состояний . 9U

3.3. Стационарное распределение времени ожидания начала обслуживания.

3 ак лючение

Считается, что первой, математической работой по теории массового обслуживания, является работа А.К. Эрланга "Теория вероятностей и телефонные разговоры1' ("The Theory of Probabilities and Telephone Conversations") [1]. Работы А.К. Эрланга и других ученых двадцатых и тридцатых годов были посвящены в основном решению практических проблем, связанных с управлением нагрузкой в телефонных сетях. В течение следующих двадцати лет, в результате того, что все больше ученых проявляли интерес к изучению данных проблем, были разработаны модели, которые позволяли исследовать более сложные явления и системы. Среди ученых того времени, которые уделили значительное внимание развитию теории массового обслуживания, необходимо отметить Г.П. Башарина [2]-[3], А. А. Боровкова [4], Б.В. Гнеденко [о], Д. Кен дал л а [б], А. Колмогорова [7], Д. Кокса [8], К. Д. Кроммелин [9], К. Пальма [10], Ф. Поллачека [10], Ю. Прохорова [22], Т. Саати [12], Б.А. Севастьянова [13], В. Смита [14], JL Такача [15], В. Феллера [16], Ф. Фостера [17], А.Я. Хинчина, [18].

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

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

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

Сейчас С-системы и С-сети остаются актуальным предметом исследований. Среди прикладных и теоретических работ, опубликованных после 2003 года, можно упомянуть [27]—[38]. В работе [29] показано как системы с отрицательными заявками и катастрофами могут применяться в телефонии для моделирования работы call-центров. Работа [36] иллюстрирует использование G-систем при анализе систем инвентаризации. Связь генетических и G-сетей подробно исследуется в [38]. Приложению системы с отрицательными заявками к анализу механизмов балансировки нагрузки в сети MPLS посвящена работа [39].

Отдельно необходимо упомянуть исследования G-систем, функционирующих в дискретном времени. Известно (см. [40, 41]), что СМО в дискретном времени играют важную роль в оценке производительности систем и сетей связи, поскольку позволяют учитывать дискретных характер передаваемой информации и дискретность функционирования реальных систем. Поэтому неудивительно, что исследование G-систем в дискретном времени уделялось и уделяется по прежнему значительное внимание (см, например, [42]-[45]).

Диссертация продолжает работы в области G-систем. В ней вводится новый вид отрицательной заявки. Рассматриваемые в рамках всей диссертационной работы отрицательные заявки не 'убивают" заявки, ожидающие в очереди, а вытесняют их в другую очередь. При этом, переместив заявку из одной очереди в другую, сама отрицательная заявка покидает систему. Системы подобного вида являются актуальным предметом исследований и имеют практическую ценность, поскольку позволяют создавать аналитические модели, применимые для следующих целей: моделирование различных стадий процессов планирования, управления и контроля движения материальных, информационных и финансовых ресурсов в различных областях деятельности (например, системы храпения скоропортящихся товаров или грузов). моделирование случаев отката транзакций в распределенных базах данных. Для обеспечения целостности данных при внесении изменений в базы данных применяются механизмы двухфазной фиксации. На первой фазе происходит уведомление и подготовка всех баз данных, участвующее в транзакции. А на второй выполняется либо фиксация транзакции, либо ее откат, если ее фиксация невозможна в любой из баз данных, вследствие внутренних сбоев сервера на котором установлена база данных или сбоя программного обеспечения. После отката выполнение транзакции не отменяется, а откладывается на некоторое случайное время, по истечению которого предпринимается очередная попытка. В данном случае внесение изменений в базы данных есть процесс обслуживания, тогда как выход из строя сервера или сбои программного обеспечения означают приход отрицательной заявки, которая откладывает (путем перемещения в бункер) выполнение транзакции; моделирование систем с параллельной обработки информации, где необходима синхронизация выполненных заданий для завершения очередного этапа вычислений. В накопитель поступают выполненные задания, которые требуют синхронизации, а поступление отрицательной заявки откладывает синхронизацию задания, фактически означая, что при выполнении задачи на одном из компьютеров произошел случайный сбой, приведший к увеличению времени выполнения задания.

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

Заключение

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

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

2. в главе 2 для экспоненциальных СА40 с различными ограничениями на емкости накопителя, бункера, и на число приборов с помощью теории эргодических процессов, матрично-геометрических методов, методов производящих функций, а также специальных функций (многочленов Чебышева. и Гегенбауэра) найдено совместное стационарное распределение числа заявок в накопителе и бункере; стационарные маргинальные распределения числа заявок в накопителе, бункере;

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

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

1. U. Narayan Bhat An introduction to queueing theory. Birkhauser Boston, 2007.

2. Батарин Г.П., Харкевич, А.Д., Шнепс. A.M. Массовое обслуживание в телефонии. М.: Наука, 1968.

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

4. Borovkov A.A. Asymptotical methods in queueing theory // Proc.of Winter Meeting in Probab. and Statistics. Ushgorod. 1964. P. 3-40.

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

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

7. Колмогоров A.H. Sur le probleme d'attente. Матем. сб. 1931. 38:1-2. С. 101-106.

8. Cox D.R. The analysis of non-Markovian stochastic processes by the inclusion of supplementary variables. Proc. Camb. Phil. Soc. 51. 1955.

9. Crommelin C. D. Delay probability formulae when the holding times are constant. Post Office Electrical Engineer's Journal. 1932. V.25. P. 41-50.

10. Palm C. Palm C., Intensitatsschwankungen im Fernsprechverkehr. Ericsson Technics. 1943. № 44. P. 1-189.

11. Pollaczek, F. Ueber eine Aufgabe der Wahrscheinlichkeitstheorie. Mathematische Zeitschrift. 1930. № 32. P. 64-100.

12. Saaty T. Elements of Queueing Theory. McGraw-Hill, 1961.

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

14. Smith W.L. On the distribution of queueing times. Proc. Camb. Phil. Soc. 49. 1953.

15. Takacs L. Investigations of Waiting Time Problems by Reduction to Markov Processes // Acta Math. Acad. Sci. Hung. 1955 V.6. P. 101129.

16. Feller W. An Introduction to Probability Theory and its Applications, Volume one. John Wiley, 1950.

17. Foster F.G. On stochastic matrices associated with certain queueing processes. Ann. Math. Statist. 24. 1953. P. 355-360.

18. Хинчин А.Я. Математическая теория стационарной очереди. Матем. сб. 1932. 39:4. С. 73-84.

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

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

21. Kleinrock L. Queueing Systems: Volume I Theory. Wiley Interscience, 1975.

22. Prohorov Y. V. Transient phenomena in queueing processes. Liet. Mat. Rink. 1963. № 3. P. 199-206.

23. Gelenbe E., Glynn P., Sigman K. Queues with negative arrivals // Journal of Applied Probability. 1991. V.28. P. 245-250.

24. Gelenbe E. Random neural networks with negative and positive signals and product form solution // Neural Computation. 1989. V.l. № 4. P. 502-510.

25. Gelenbe E. G-nctworks: an unifying model for neural and queueing networks // Annals of Operations Research. 1994. V.48. № 1-4. P. 433-461.

26. Artalejo J.R. G-networks: A versatile approach for work removal in queueing networks. Eur. J. Oper. Res. 2000. V.126. P. 233-249.

27. Krishna Kumar В., Arivudainambi D., Krishnamoorthy A. Some results on a generalized M/G/l feedback queue with negative customers // Ann. Oper. Res. 2006. № 143. P. 277-296.

28. Соколов И.А., Печинкин А.В., Чаплыгин В.В. Стационарные характеристики многолинейной системы массового обслуживания с ненадежными приборами // Обозрение прикладной и промышленной математики. 2007. Т. 14. № 5. С. 27-39.

29. Yang Woo S. Multi-server retrial queue with negative customers and disasters // Queueing Syst. 2007. № 55. P. 223-237.

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

31. Бочаров П., Д'Апиче Ч., Мандзо Р., Печинкин А. В. Анализ многолииейной марковской системы массового обслуживания с неограниченным накопителем и отрицательными заявками // Автоматика и телемеханика. 2007. № 1. С. 93-104.

32. Печинкин А. В. Марковская система обслуживания с конечным накопителем и отрицательными заявками, действующими на конец очереди // Информационные процессы. 2007. Т.7. С. 138-152.

33. Qua,n-Lin L., Yiqiang Q. Z. A MAP/G/1 Queue with Negative Customers // Queueing Systems. 2004. № 47. P. 5-43.

34. Kim C., Klimenok V.I., Orlovsky D.S. Multi-Server Queueing System with a Batch Markovian Arrival Process and Negative Customers // Automation and Remote Control. 2006. № 12. P. 106-122.

35. Manuel Paul, Sivakumar B., and Arivarignan G. Perishable Inventory System with Postponed Demands and Negative Customers // Journal of Applied Mathematics and Decision Sciences. 2007.

36. Gym,ez-Corral A., Martos M. E. Marked Markovia.n Arrivals in a Tandem G-Network with Blocking // Methodol. Comput. Appl. Probab. 2009. P. 621-649.

37. Arnon Arazia, Eshel Ben-Jacobb, Uri Yechialia Bridging genetic networks and queueing theory // Physica. Ser., A. V.232. 2004. P. 585-616.

38. Ram Chakka, Tien Van Do The MMJ2k=oCPPt>-/GE/c/L G-Queue and its Application to the Analysis of the Load Balancing in MPLS Networks // Proceedings of the 27th Annual IEEE Conference on Local Computer Networks (LCN02), 2002.

39. Herwig Bruneel, Byung G. Kim. Discrete-Time Models for Communication Systems Including ATM. Kluwer Academic Publishers, 1992.

40. Woodward M.E. Communication and Computer Networks: Modelling with Discretetime Queues, IEEE Computer Society Press, 1994.

41. Atencia I., Moreno P. The discrete-time Geo/Geo/1 queue with negative customers and disasters. Computers and Operations Research. 2004. V. 31. № 9, P. 1537-1548.

42. Atencia I., Moreno P. A single-server G-queue in discrete-time with geometrical arrival and service process. Performance Evaluation. 2005. V. 59. № 1. P.85-97.

43. Li Ma A Class of Geom/Geom,/1 Discrete-time Queueing System with Negative Customers. Int.J.NonlincarSci. 2008. V. 5. № 3. P.275-280.

44. Hyun Min Parka, Won Seok Yangb, Kyung Chul Chaea The Geo/G/1 Queue with Negative Customers and Disasters. Stochastic Models. 2009. V. 25. Issue 4.

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

46. Latouche G. a,nd Taylor P. G. Level-Phase Independence for GI\M\1 Type Markov Chains // J. Appl. Prob. 2000. V. 37. P. 984-998.

47. Гантмахер Ф. M. Теория матриц. M.: Наука, 1966.

48. Favati P. and Meini B. On Functional Iteration Methods for Solving Nonlinear Matrix Equations Arising in Queueing Problems // IMA J. Numer. Anal. 1999. № 19. P. 39-49.

49. Guo C.-H. On the Numerical Solution of a Nonlinear Matrix Equation in Markov Chains // Linear Algebra Appl. 1999. № 288. P. 175-186.

50. Latouche G. Newton's Iteration for Non-Linear Equations in Markov Chains // IMA J. Numer. Anal. 1994. № 14. P. 583-598.

51. Latouche G. Algorithms for Evaluating the Matrix G in Markov Chains of Ph\G\l Type // Cahiers Centre Etudes Rech. Oper. 1994. № 36. P. 251-258.

52. Meini B. New Convergence Results on Functional Iteration Techniques for the Numerical Solution of M\G\1 Type Markov Chains // Numer. Math. 1997. № 78. P. 39-58.

53. Neuts M. F. Moment Formulas for the Markov Renewal Branching Process // Adv. in Appl. Probab. 1976. № 8. P. 690-711.

54. Ye Q. High Accuracy Algorithms for Solving Nonlinear Matrix Equations in Queueing Models // Advances in Algorithmic Methods for Stochastic Models. 2000. P. 401-415.

55. Latouche G. and Ramaswami V. A Logarithmic Reduction Algorithm for Quasi-Birth-Death Processes // J. Appl. Probab. 1993. № 30. P. 650 -674.

56. Корн Г., Корн Т. Справочник по математике. М.: Наука. 1974.

57. Bocharov P.P. , D'Apice C., Pechinkin A.V., Salerno S. Queueing Theory. Utrecht, Boston: VSP, 2004.

58. Erdelyi A. and Bateman H. Higher transcendental functions. Volume II. Robert E. Krieger Publishing Company, 1985.

59. Мандзо Р., Касконе Н., Разумчик Р.В. Экспоненциальная система массового обслуживания с отрицательными заявками и бункеромдля вытесненных заявок // Автоматика и телемеханика. 2008. № 9. С. 103-113.

60. Печинкин А.В., Разумчик Р.В. Система массового обслуживания с отрицательными заявками и бункером для вытесненных заявок в дискретном времени // Автоматика и телемеханика. 2009. № 12. С. 109-120.