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

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

ИССЛЕДОВАНИЕ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

С ОТРИЦАТЕЛЬНЫМИ ЗАЯВКАМИ

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

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

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

Москва 2011

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

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

Официальные оппоненты: доктор физико-математических наук, професссор Каштанов Виктор Алексеевич доктор физико-математических наук, професссор Ушаков Владимир Георгиевич

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

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

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

Автореферат разослан 2011 г.

Ученый секретарь Диссертационного совета Д 212.133. к.ф.-м.н., доцент П.В. Шнурков

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

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

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

Значительное внимание уделяется и изучению систем с отрицательными заявками в 1 Gelenbe E., Glynn P., Sigman K. Queues with negative arrivals // Journal of Applied Probability. 1991. V. 28. P. 245–250.

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

3 Artalejo J.R. G-networks: A versatile approach for work removal in queueing networks. Eur.

J. Oper. Res., 2000, vol. 126, pp. 233–249.

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

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

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

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

Классическая отрицательная заявка предполагает “удаление“ работы из системы или сети.

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

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

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

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

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

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

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

6Li Ma A Class of Geom/Geom/1 Discrete-time Queueing System with Negative Customers.

Int.J.NonlinearSci., V. 5, No. 3, 2008. P.275–280.

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

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

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

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

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

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

Личное участие автора. Научному руководителю диссертации Печинкину А.В.

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

Реализация результатов работы. Результаты исследований вошли в программу “WEBориентированный программный комплекс удаленного расчёта стационарных характеристик программные модули расчета моделей одноканальной системы массового обслуживания с отрицательными заявками и бункером для вытесненных заявок полностью конечной емкости и одноканальной системы массового обслуживания с отрицательными заявками и бункером для вытесненных заявок полностью неограниченной емкости, которые зарегистрированы в Реестре программ для ЭВМ Российского агентства по патентам и товарным знакам9.

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

9 Свидетельство № 2011610585 и № 2011610589 соответственно.

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

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

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

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

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

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

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

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

международная конференция “International Conference on Ultra Modern Telecommunications“ ICUMT 2010 (18-20 October 2010, Moscow, Russia);

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

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

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

информационных систем и процессов“ МНТОРЭС им. А.С. Попова, декабрь 2010;

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

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

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

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

11 Свидетельство № 01200807411.

том числе 8 рисунков и 18 таблиц. Список литературы включает в себя 71 наименование, в том числе и публикации соискателя по теме исследования. Каждая глава разбита на параграфы, параграфы, в свою очередь, разбиты на пункты, имеющие порядковую нумерацию. Формулы внутри каждого пункта имеют двойную нумерацию с указанием главы и порядкового номера формулы в данной главе.

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

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

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

В параграфе 1.1 приводится описание модели. Рассматривается СМО с одним обслуживающим прибором в которую поступает пуассоновский поток заявок интенсивности.

Назовем эти заявки положительными. Для положительных заявок имеется накопитель неограниченной емкости.

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

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

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

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

Т е о р е м а 1.1. Стационарное распределение общего числа заявок в системе {pn, n 0} имеет вид где = /µ загрузка системы.

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

Пусть pk,m стационарная вероятность того, что в накопителе и на приборе находятся k заявок, а в бункере ожидают m заявок, вытесненных из накопителя. Введем производящую функцию (ПФ) Т е о р е м а 1.2. ПФ P (u, v) совместного стационарного распределения числа заявок в накопителе и бункере {pk,m, k, m 0} имеет вид где Обозначим через pk,· стационарную вероятность того, что в накопителе и на пиборе находится k заявок, а через p·,m вероятность того, что в бункере находится m заявок.

Тогда для данных маргинальных распределений имеют место следующие два следствия из теоремы 1.2.

С л е д с т в и е 1.1. Стационарное распределение общего числа заявок в накопителе и на приборе {pk,·, k 0} имеет вид Таким образом, маргинальное распределение числа заявок в накопителе и на приборе определяется (начиная с k = 1) геометрической прогрессией, что позволяет без труда находить моменты любых порядков.

С л е д с т в и е 1.2. Стационарное маргинальное распределение числа заявок в бункере {p·,m, m 0} рассчитывается по формулам где стационарные вероятности p1m задаются формулой Используя результаты теоремы 1.2, возможно последовательно вычислить вероятности pkm. Однако этот путь опирается на трудоемкие вычисления, в процессе которых, в зависимости от начальных данных, быстро накапливаются ошибки вычислений. Поэтому в конце параграфа 1.2 для нахождения совместного стационарного распределения приводится алгоритм, который также опирается на обращение ПФ, сопутствующих получению P (u, v), однако дает более точные результаты вычислений.

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

вытесняется первая заявка из очереди в накопителе, на обслуживание выбирается первая заявка из очереди в накопителе, и последняя заявка из очереди в бункере (обозначается, как F IRST -F IF O-LIF O);

вытесняется последняя заявка из очереди в накопителе, на обслуживание выбираются последние заявки из очередей в накопителе и и бункере (LAST -LIF O-LIF O);

вытесняется первая заявка из очереди в накопителе, на обслуживание выбираются первые заявки из очередей в накопителе и бункере, (F IRST -F IF O-F IF O);

вытесняется последняя заявка из очереди в накопителе, на обслуживание выбирается последняя заявка из очереди в накопителе и первая заявка из очереди в бункере (LAST -LIF OF IF O);

вытесняется последняя заявка из очереди в накопителе, на обслуживание выбирается первая заявка из очереди в накопителе и последняя заявка из очереди в бункере (LAST F IF O-LIF O);

вытесняется первая заявка из очереди в накопителе, на обслуживание выбираются последние заявки из очередей в накопителе и бункере (F IRST -LIF O-LIF O);

вытесняется последняя заявка из очереди в накопителе, на обслуживание выбираются первые заявки из очередей в накопителе и бункере (LAST -F IF O-F IF O);

вытесняется первая заявка из очереди в накопителе, на обслуживание выбирается последняя заявка из очереди в накопителе и первая заявка из очереди в бункере (F IRST LIF O-F IF O).

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

Т е о р е м а 1.3. ПЛС (s) стационарного распределения V (x) времени ожидания начала обслуживания поступившей в систему заявки при дисциплине F IRST -F IF O-LIF O имеет вид где Т е о р е м а 1.4. ПЛС (s) стационарного распределения V (x) времени ожидания начала обслуживания поступившей в систему заявки при дисциплине LAST -LIF O-LIF O имеет вид где Т е о р е м а 1.5. ПЛС (s) стационарного распределения V (x) времени ожидания начала обслуживания поступившей в систему заявки при дисциплине F IRST -F IF O-F IF O имеет вид где Т е о р е м а 1.6. ПЛС (s) стационарного распределения V (x) времени ожидания начала обслуживания поступившей в систему заявки при дисциплине LAST -LIF O-F IF O имеет вид где Результаты теорем позволяют находить моменты любого порядка стационарных распределений времени ожидания начала обслуживания для указанной дисциплины. В частности, среднее время ожидания начала обслуживания равно Как положено в силу формулы Литтла и, как показано в диссертационной работе, стационарные средние значения времен ожидания начала обслуживания для всех дисциплин совпадают и равны w. Однако стационарные дисперсии времени ожидания для всех дисциплин различны.

Для большого числа рассчитанных примеров, как показано в приложении, минимальной дисперсией обладает дисциплина LAST -F IF O-F IF O.

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

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

В параграфах 2.1 и 2.2 рассматриваются однолинейные СМО с отрицательными заявками и бункером для вытесненных заявок как в главе 1, только в первом случае с бункером емкости r (r < ), а во втором случае с накопителем емкости r. Для этих двух систем доказаны теоремы, которые следуют из монографии M.F. Neuts12, определяющие совместное стационарное распределение числа заявок в накопителе и бункере и условие его существования.

Приведем результат для системы из параграфа 2.1.

Инфинитезимальная матрица переходов Q однородного неприводимого марковского процесса {X(t), t 0}, описывающего стохастическое поведение рассматриваемой СМО, является блочной трехдиагональной вида 12Neuts M.F. Matrix-geometric solutions in stochastic models. An algorithmic approach. Baltimore and London, The Johns Hopkins Univ. Press, 1981. 332 p.

где, N, M, N1 квадратные матрицы размерности (r + 1) (r + 1) имеют следующий вид:

элементы равны нулю, кроме элемента на i-м месте.

Обозначим через p T = (p0, p0,...) вектор стационарных вероятностей МП {X(t), t 0}, где piT = (pi0, pi1,..., pir ), а pij стационарная вероятность того, что в накопителе i, а в тогда и только тогда, когда минимальное неотрицательное решение R уравнения имеет спектральный радиус (R) < 1, и если существует положительный вектор (p0, p0 ) такой, что выполняется где I единичная матрица размерности (r + 1) (r + 1).

Для системы в параграфе 2.1 стационарное распределение существует тогда и только тогда, когда /0 < 1, где 0 – единственный действительный положительный корень уравнения (относительно ) Для системы из параграфа 2.2 необходимым и достаточным условием существования стационарного режима является условие /(µ + ) < 1.

В параграфе 2.3 исследуется одноканальная СМО с отрицательными заявками и бункером для вытесненных заявок как в главе 1, с той разницей, что теперь накопитель и бункер имеют одинаковую конечную емкость r (r < ).

Двумерный процесс {X(t) = ((t), (t)), t 0}, описывающий стохастическое поведение рассматриваемой СМО во времени, является эргодическим, с конечным множеством состояний и блочной трехдиагональной инфинитезимальной матрицей переходов. Этот процесс относится к обобщенным процессам рождения и гибели и для нахождения его стационарного распределения, как и в п.2.1 2.2, можно воспользоваться соответствующими разработанными методами13.

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

В параграфе 2.4 показано как результаты, касающиеся совместного стационарного распределения числа заявок в накопителе и бункере, полученные для однолинейных СМО из главы 1 и 2, переносятся на случай, когда в этих же системах имеется не один, а несколько приборов. Обозначим через {p00, pk,m, k 0, m 0} совместное стационарное распределение вероятностей состояний однолинейной СМО из главы 1, в которой прибор обслуживает заявки с интенсивностью nµ. А через {i0, 0 i n 1, n+k1,m, k 1, m 0} стационарное распределение вероятностей состояний соответствующей n-линейной СМО, в которой каждый прибор обслуживает заявки с интенсивностью µ. Как показано в диссертационной работе, стационарные распределения {n1,0, n+k1,m, k 1, m 0} и {p00, pk,m, k 1, m 0} совпадают с точностью до некоторой постоянной, зависящей только от n, т.е.

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

14 Данный метод применялся в работе Avrachenkov K.E., Vilchevsky N.O., Shevljakov G.L.

Priority queueing with nite buer size and randomized push-out mechanism // Proceedings of the ACM international conference on measurement and modeling of computer (SIGMETRIC 2003).

San Diego, 2003. P. 324–335.

Постоянная c(n) определяется с помощью условия нормировки для n-линейной СМО и равна а остальные вероятности i0, 0 i n 2 определяются из СУР для n-линейной СМО и имеют вид Поскольку стационарное распределение {p00, pk,m, k 1, m 0} для СМО из главы 1 уже найдено в терминах вычислительных алгоритмов, то, воспользовавшись вышеприведенными формулами, можно рассчитать совместное стационарное распределение в соответствующей n-линейной СМО.

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

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

В параграфе 3.1 приводится описание системы. В СМО с накопителем неограниченной емкости, поступает геометрический поток обычных (вероятность поступления на такте равна a) и отрицательных (вероятность поступления на такте равна c) заявок; распределение времени обслуживания геометрическое (вероятность окончания обслуживания на такте равна b).

Дискретное время измеряется в фиксированных интервалах (тактах). Величина такта равна h, h > 0, единиц времени. Все возможные измерения в системе происходят в моменты времени nh, n = 1, 2,... Величина такта h в диссертации, для простоты, принята равной 1.

Все изменения состояния СМО происходят в конце такта в следующем порядке: если на этом такте завершилось обслуживание заявки на приборе (с вероятностью b), то она покидает систему и на прибор из накопителя или если накопитель пуст, то из бункера сразу же поступает следующая заявка; затем (с вероятностью a) поступает обычная заявка и если прибор занят, то помещается в накопитель, а если прибор свободен, то сразу же начинает обслуживаться;

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

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

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

Т е о р е м а 3.1. Стационарное распределение общего числа заявок в системе по моментам поступления {pe, n 0} имеет вид С точки зрения общего числа заявок в системе рассматриваемая СМО совпадает с обычной СМО Geom/Geom/1/ без отрицательных заявок. Необходимым и достаточным условием для существования стационарного режима функционирования рассматриваемой СМО является условие = a/b < 1.

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

Т е о р е м а 3.3. ПФ P (u, v) совместного стационарного распределения числа заявок в накопителе и бункере {pe, k, m 0} имеет вид ее решение единственно, а 1 < u1 (v) < 0 < u2 (v) 1 < u3 (v) корни уравнения r(u, v) = abcu3 + abcv (ab + ab + abc + bac) u2 + В качестве следствия из теоремы 3.3 доказано, что стационарное маргинальное распределение {pe, k 0} числа заявок в накопителе, начиная с pe, является геометрическим где что дает возможность легко определять моменты любых порядков.

Также были найдены выражения для Q0 (1) и Q1 (1), что позволяет с помощью теоремы 3.3, определять смешанные факториальные моменты. Учитывая, что P (u, v) трудно использовать для вычисления стационарных вероятностей pe, в параграфе 3.2 сформулирована и доказана теорема, определяющая рекуррентный алгоритм вычисления двумерного стационарного распределения pe. Ввиду громоздкости формулировка этой теоремы в автореферате не предkm ставлена.

В параграфе 3.3 исследуется стационарное распределение времени ожидания начала обслуживания заявки в рассматриваемой СМО для одной дисциплины выбивания и выбора заявок на обслуживание из очереди в накопителе и бункере, а именно дисциплины F IRST -F IF OF IF O. Стационарное распределение времени ожидания начала обслуживания определяется следующей теоремой.

Т е о р е м а 3.4. Стационарное распределение времени ожидания начала обслуживания заявки при дисциплине F IRST -F IF O-F IF O в терминах ПФ (z) имеет вид где = c1 c1 (a1 z + az, h(z))1 (a1 z + az, h(z)) + c2 c1 (a2 z + az, h(z))1 (a2 z + az, h(z)), = c1 c2 (a1 z + az, h(z))2 (a1 z + az, h(z)) + c2 c2 (a2 z + az, h(z))2 (a2 z + az, h(z)), c2 (z) = bz u1 + bz 2 (bac2 + (bac + bac + bac)1 + ba + bac + bac) Дифференцируя (z) можно найти моменты любых порядков стационарного распределения времени ожидания начала обслуживания. В частности, среднее значение определяется выражением которое не зависит от вероятности c поступления отрицательной заявки и совпадает с аналогичной характеристикой для обычной СМО Geo/Geo/1/ без отрицательных заявок.

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

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

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

ВЫНОСИМЫЕ НА ЗАЩИТУ

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

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

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

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

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

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

Изд-во РУДН, 2006.

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

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

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

Изд-во РУДН, 2008. C. 55.

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

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

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

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

8. Разумчик Р.В. Cистема массового обслуживания с отрицательными заявками, конечным накопителем и бесконечным бункером для вытесненных заявок. Proceedings of the International Conference on Distributed computer and communication networks. Moscow, Russia, October 26-28, 2010. P. 216–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. Печинкин А.В., Разумчик Р.В. О времени ожидания при некоторых дисциплинах обслуживания в системе с отрицательными заявками и бункером. Proceedings of the International Conference “Modern Probabilistic Methods for Analysis and Optimization of Information and Telecommunication Networks“, Minsk, 2011. C. 207–212.

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