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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 519.21

Ткаченко Андрей Викторович

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

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

Автореферат

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

005539258

г 1 ноя 2013

Москва 2013

005539258

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

Научный руководитель:

доктор физико-математических наук, профессор Афанасьева Лариса Григорьевна.

Официальные оппоненты:

доктор физико-математических наук, профессор Королёв Виктор Юрьевич, Московский государственный университет имени М. В. Ломоносова,

факультет вычислительной математики и кибернетики, профессор кафедры математической статистики;

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

Ведущая организация:

Вологодский государственный педагогический университет

Защита диссертации состоится 13 декабря 2013 года в 16 часов 45 минут на заседании диссертационного совета Д 501.001.85 при Московском государственном университете имени М. В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, механико-математический факультет, аудитория 16-24.

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М. В. Ломоносова.

Автореферат разослан 12 ноября 2013 г.

Учёный секретарь диссертационного совета Д 501.001.85 при МГУ доктор физико-математических наук, профессор

В. Н. Сорокин.

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

Актуальность темы.

Многоканальные системы обслуживания давно и интенсивно изучаются многими авторами. В значительной мере это связано с широким кругом применений в самых различных областях: компьютерные системы, коммуникационные сети, супермаркеты, аэропорты и т.д.. Одна из первых проблем, возникающих при анализе этих моделей, — выяснение условий существования собственных предельных распределений (условий стабильности) у процессов, описывающих функционирование систем. Проблема условий эргодичности систем достаточно традиционна для теории массового обслуживания. Эти условия представляют значительный интерес для приложений, поскольку они определяют соотношения между параметрами модели, при которых не образуется бесконечно больших очередей. С другой стороны, доказательства соответствующих предельных теорем приводят к анализу сложных случайных процессов, вообще говоря, немарковских, что способствует разработке новых подходов и методов. Если удается построить цепь Маркова, связанную с функционированием системы, то доказательства опираются на соответствующие результаты для марковских цепей. Одними из первых работ, в которых были найдены достаточные условия существования стационарного распределения у цепей Маркова, связанных с очередью в системе, являются работы Ф. Фостера1 и Д. Кендалла2. Некоторые необходимые условия эргодичности установлены в работе М. Каплана3. Анализ свойств эргодичности широкого класса случайных процессов проведен в монографии A.A. Боровкова4, в которой рассматриваются как цепи Маркова, так и стохастические рекурсивные последовательности и цепи.

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

1 Foster, F. G., "On the stochastic matrices associated with certain queuing processes". Ann. Math. Statist., 24, 2, 355-360 (1953).

2Kendall, D. G., "Stochastic processes occuring in the theory of queues and their analysis by the method of the imbedded Markov chain". Ann. Math. Statist., 24, 3, 338-354 (1953)

3Kaplan, M.,"A sufficient condition of nonergodicity of a Markov chain". IEEE Transactions on Information Theory, 25, 4, 470-471 (1979).

4Боровков, А. А., Эргодичность и устойчивость случайных процессов. M.: Едиториал УРСС, 440 с.

(1999)

sDai, J. G., "On positive Harris recurrence of multiclass queueing networks: a unifed approach via uid limit

models." Ann. Appl. Proba. 5, 49-77 (1995).

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

Для многоканальных систем обслуживания в работе Р.Лойнеса6 установлено, что процессы, описывающие функционирование системы, стабильны, если интенсивность поступления новых требований меньше суммарной интенсивности обслуживания, когда все имеющиеся приборы заняты. При этом предполагается, что интервалы между поступлениями требований и времена обслуживания образуют стационарную метрически транзитивную двумерную последовательность и все приборы одинаковы. В такой ситуации, введенный в работе Ж.Кифера и Ж.Вольфовица7 r-мерный случайный процесс Wn, обладает свойством стохастической монотонности, т.е. если Й^х = 0, то Fn+i(x) = P{Wn+x} < = Fn(x). Отсюда следует сходимость по-

следовательности Fn(x) при нулевых начальных условиях. Доказательство условий стабильности следует из ряда оценок или опирается на метод Фо-стера8. Подобный подход можно применить и к системам с ограничениями, обладающими указанными свойствами монотонности9. Однако для доказательства стабильности при общих начальных условиях требуются дополнительные предположения10.

Несмотря на достаточно долгую историю развития данного направления, интерес к вопросам эргодичности велик и в настоящее время. Этой проблеме посвящены работы Садовски и Спанковски11, Афанасьевой12, Фосса и Константопулуса13, Морозова и Дельгадо14 и многих других авторов.

В связи с интенсивным развитием телекоммуникационных систем, акту-

eLoynes, R. М„ "The stability of a queue with non-independent inter-arrival and service times" Proc Cambr. Phil. Soc., 58, 3, 494-520 (1962).

(1955)efer' J ' W°IfoWitZ' J'' "0n the theory of 4ueues with many servers". Trans. Amer. Math. Soc., 78, 1-18

'Foster, F. G., "On the stochastic matrices associated with certain queuing processes". Ann. Math. Statist., 24, 2, 355—360 (1953). '

9Афанасьева, Л. Г., "О существовании предельного распределения в системах массового обслуживания с ограниченным временем пребывания". Теория вероятностей и её применения, 10, 3 570-578 (1965). '

(1980)°РОВКОВ' А А'' Асимптотические методы в теории массового обслуживания. М.: Наука, 381 с.

"Sadowsky, J.S., Szpankowski, W., "The Probability of Large Queue Lengths and Waiting Times in a Heterogeneous Multiserver Queue Part I: Tight Limits", Advances in Applied Probability, 27, 2, 1-11 (1995).

"Афанасьева, Л. Г., "Системы массового обслуживания с циклическими управляющими процессами" Кибернетика и системный анализ, 41, 1, 54-68 (2005).

13Foss, S., Konstantopoulos, Т., "An overview of some stochastic stability methods". Journal of the Operations Research Society of Japan-Keiei Kagaku, 47, 275-303 (2004).

7n14f7-v, E„ Delgado, R,, "Stability analysis of regenerative queueing systems" Autom. Remote Contml, 70« 2) 197T~1991 (2009)*

альными направлениями исследований в теории очередей является анализ моделей с входными потоками более общего вида15, а также изучение систем с ненадежными приборами10 и различными ограничениями17. В работе исследуются как обычные многоканальные системы с общей очередью и неидентичными приборами, где каждый прибор имеет свою функцию распределения времени обслуживания, так и многоканальные системы обслуживания с ненадежными приборами, системы, функционирующие в случайной среде и системы с возможностью неприсоединения требований к очереди. Для всех рассматриваемых систем входящий поток предполагается регенерирующим. Отметим, что класс регенерирующих потоков весьма широк. Регенерирующими являются большинство процессов, обычно используемых в теории массового обслуживания в качестве входных потоков. Кроме того, при довольно общих условиях свойство регенерации сохраняется при прохождении через систему обслуживания. Таким образом, опираясь на результаты, касающиеся отдельных узлов, мы исследуем иерархическую сеть многоканальных систем обслуживания, подобно тому, как это сделано в работах Афанасьевой Л.Г. 18 и Морозова Е.19. И наконец, потоки данного класса могут использоваться при построении математических моделей многих реальных объектов, поскольку интенсивность таких потоков может зависеть от времени и, более того, являться случайным процессом.

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

"Баштова, Е. Е., "Режим малой загрузки для системы обслуживания со случайной нестационарной интенсивностью". Матем. заметки, 80, 3, 339-349 (2006).

1бПечинкин, А. В., Соколов, И. А., Чаплыгин, В. В., "Многолинейная система массового обслуживания с групповым отказом приборов". Информатика и её применения, 3, 3, 4-15 (2009).

17Ibrahim, R., Whitt, W., "Real-Time Delay Estimation in Overloaded Multiserrer Queues with Abandonments." Management Science, 55, 10, 1729-1742 (2009).

18Афанасьева, Л. Г., "Об эргодичности открытой сети обслуживания". Теория вероятностей и её применения, 32, 4, 777-781 (1987).

19Morozov, Е., "Weak Regeneraron in Modeling of Queueing Processes." Queueing Systems, 46, 3 295-315 (2004).

20Whitt, W., "Heavy T^affic Limit Theorems for Queues: A Survev". Lecture Notes in Economics and Math Systems, 98, 307-350 (1974).

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

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

Цель и задачи исследования.

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

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

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

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

Научная новизна.

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

— Для многоканальной системы с регенерирующим входящим потоком

(2004)hÍtt' W'' "А DÍffUSÍOn APProximati™ for the G/GI/n/m Queue." Operations Research, 52, 6, 922-941

"Iglehaxt, D. L., Whitt, W., "Multiple Channel Queues in Heavy Traffic, Г. Advances Appl Prob 2 2 150-177 (1970). ' '

"Whitt, W., Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Anvlication to Queues. N.Y.rSpringer, 727 с (2002).

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

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

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

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

Методика исследования.

В диссертации используются как классические методы теории вероятностей и теории случайных процессов, такие как предельные теоремы для стационарных процессов25, теорема восстановления Блекуэлла26, узловая теорема Смита27, метод склеивания (coupling)28, так и специальные методы теории очередей: метод полного времени обслуживания29, метод одного вероятностного пространства, метод жидкостных аппроксимаций30. Теоретическая и практическая значимость.

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

По теме диссертации были сделаны доклады на следующих семинарах механико-математического факультета МГУ им. М. В. Ломоносова:

• Большом семинаре кафедры теории вероятностей под руководством действительного члена РАН, профессора А. Н. Ширяева (2013 г.),

• Семинаре «Исследование асимптотического поведения и устойчивости стохастических моделей» под руководством проф. Л.Г. Афанасьевой, проф. Е.В. Булинской, доц. Е.Б. Яровой (2011-2013 гг., неоднократно).

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

26Blackwell, D., "A renewal theorem". Duke Math. J., 15, 145-150 (1948).

"Smith, W. L., "Regenerative stochastic processes". Proc. Roy. Soc., A 232, 6-31 (1955).

2sLindvall, T., Lectures on the coupling method. N.Y.:Dover Publications, 257 c. (2002).

29Gaver, D. P., Jr., "A Waiting Line with Interrupted Service, Including Priorities". J. Roy. Statist. Soc., 24, 73-90 (1962). '

30Whitt, W., Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Application to Queues. N.Y.iSpringer, 727 с (2002).

Доклад на семинаре «Теория риска и смежные вопросы» под руководством проф. В.Ю. Королёва факультета вычислительной математики и кибернетики МГУ им. М. В. Ломоносова (2013 г.).

Результаты диссертации докладывались на:

• Международной конференции "Теория вероятностей и ее приложения" в МГУ, посвященной столетию со дня рождения Б.В.Гнеденко (Москва, 2012 г.);

• Международной конференции "XXX International Seminar on Stability Problems for Stochastic Models" (Светлогорск, 2012 г.);

• Международной конференции студентов, аспирантов и молодых учёных «Ломоносов» в МГУ (Москва, 2012-2013 гг.);

• Международной конференции "XXXI International Seminar on Stability Problems for Stochastic Models" (Москва, 2013 г.);

• Международной конференции "Seventh International Workshop on Simulation" в Италии (Римини, 2013 г.);

Публикации.

Результаты диссертации опубликованы в девяти работах, из которых две — в журналах из перечня ВАК, одна депонирована в ВИНИТИ. Список работ приведён в конце автореферата [1-9].

Структура и объём работы.

Диссертация изложена на 108 страницах и состоит из введения, трёх глав и списка литературы, включающего 125 наименований.

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

Во введении приводится краткий обзор исследований, посвящённых вопросам эргодичности различных систем и анализу их поведению в условиях высокой и сверхвысокой загрузки. Историческая справка подкрепляется соответствующими ссылками на научные работы. Кроме того, во введении объясняется актуальность темы и научная новизна предпринятого автором исследования.

В первой главе изучается многоканальная система обслуживания с г неидентичными приборами, время обслуживания требований на которых, для г'-го прибора, задается произвольной функцией распределения В{(х) с конечным средним ßr1, регенерирующим входящим потоком X(t) интенсивность которого равна lim^ Щр- = Л и общей очередью. Мы также допускаем тривиальный случай ßr1 = 0 и, тогда, полагаем & = оо. Дисциплина обслуживания консервативная, т.е. приборы не могут простаивать, если в

очереди находятся требования. В этой главе мы предполагаем, что приборы являются надежными и не происходит прерывания обслуживания. Такую систему далее будем называть стандартной. Для входящего потока X(t) заданы следующие последовательности: [Oi - вг_1 = т,}«^^ = 0) — независимые одинаково распределенные (за исключением ti) времена между наступлениями моментов регенерации входящего потока, — независимые одинаково распределенные (за исключением £i) случайные величины, задающие число требований, поступивших за соответствующие периоды регенерации. Каждый прибор характеризуется последовательностью независимых времен обслуживания г)® = {т^}^, (г = T7F) с функцией распределения Bi(x).

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

Вводится r-мерный случайный процесс W(t) = (Wi(t),..., Wr{t)) с неотрицательными координатами, характеризующий функционирование системы. Предполагается, что W(t) при t !> 0 определяется соотношением

= Ф(й*(0), t, {X(s), а <t},tъ.. • (1)

где Ф(-) — некоторая функция в соответствующем пространстве со значениями в R+. Более того, функция Ф(-) такова, что процесс W(t) — регенерирующий и его точки регенерации совпадают с теми моментами регенерации входного потока {(^H^i, для которых W(9{ - 0) = 0.

Для процесса Jv(i), определенного соотношением (1), вводится вложенный процесс Wn = W(9n - 0) = (W„i,..., Wnr) и суммы координат w(t) = 2j=iWj(i), wn — Ej=i W„j. Предполагается, что входящий поток X(t), последовательность {jfn}^=i и функция Ф(-) таковы, что выполнены следующие условия.

Условие 1. Р{и>п+1 = 0|щп = 0} > 0.

Будем говорить, что точка V € Ж+ достижима из нуля процессом если для любого е > 0 существуют е-окрестность, = {1? : —

t)\ < г} и te > 0 такие, что P{f(te) е Д£(^)|^(0) = 0} > 0. Обозначим Bo(V^(-)) множество точек, достижимых из нуля процессом 5^(t). Условие 2. Для любого äf < оо, £ Мг найдутся целое и 5(lt) >

0, такие что при всех е Во и 1/ < ^ выполняется равенство

P{wn+m(-i) = 0|Й>„ = f}> Ö&).

3lBlackwell, D., "А renewal theorem". Duke Math. J., 15, 145-150 (1948).

32Smith, W. L., "Regenerative stochastic processes". Proc. Roy. Soc., А 232, 6-31 (1955).

Здесь и далее < означаетпокоординатное неравенство. Будем говорить, что процесс Шп асимптотически стохастически непрерывен, если выполнено следующее условие.

Условие 3. Для произвольных е > 0 и <= существуют (5 > 0 и целое щ, такие что |р{й^п < = - < -¿00 = < £) если п >

по,

Следующее предположение технического характера касается входящего потока и оно позволяет устанавливать условие эргодичности для процесса с непрерывным временем IV

Условие 4. Распределение т2 содержит абсолютно непрерывную компоненту.

Заметим, что если один из процессов стохастически ограни-

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

Условие 5. Последовательность случайных величин ип = тах1<у<г -Жу!) п = 1,2,... стохастически ограничена при тг -»■ оо.

Теорема 1 (1). Пусть выполнены условия 1 и 2. Тогда

1. Если для некоторого начального состояния 6 В0(\$п) процесс стохастически ограничен, то при условии 3 он эргодичен.

2. Если процесс^ гип стохастически неограничен при любом начальном состоянии И^о = € В0(1У„), то он сильно стохастически неограничен.

3. При условии 5 эти утверждения имеют место для процесса 4- Данные утверждения верны для процесса при условии 4-

Рассмотрим теперь стандартную систему типа Кед\С\г\оо, где сокращение Лед обозначает регенерирующий входящий поток. Положим = №(')|-"Дгй)| гДе УУ^) — время от момента Ь до момента, когда г-й прибор освободится от обслуживания требований, пришедших раньше и Ч(Ъ) — • • •) Ог(*)), где (¿{(Ь) — количество требований из числа имеющихся в системе в момент которые будут обслуживаться (или уже об-

г

служиваются) на г-м приборе. Тогда процесс <3(£) = С}^) задает число

требований в системе в момент времени Установлено, что для рассматриваемых процессов условие 5 выполнено, а условие 3 оказывается излишним.

Вместо условий 1 и 2 достаточно потребовать выполнение следующего нераг венства:

= 0} + Р{6 = 1, 1-2 - «х > 4} > 0. (2)

для некоторого прибора г (г = Т~г). Имеет место эргодическая теорема. Теорема 2 (2). 1. Если выполнено (2) и

р = Шкк1' (3)

то процессы ЙК эргодичны. Если, кроме того, выполнено условие 4, то процессы и 0 (¿) эргодичны.

2. При р > 1, а также при р = 1 и дополнительных условиях

Ет1+6<ю, Е$+*<оо, Е(т,{)2<ОО, ¿ = 17? (4)

для некоторого 5 > 0, все эти процессы сильно стохастически неогра-ничены.

Далее рассматривается иерархическая сеть многоканальных систем обслуживания, и на основании теоремы 2 находится необходимое и достаточное условие ее эргодичности. Итак, мы рассматриваем сеть с N узлам. Она называется иерархической, если наличие маршрута из узла А в узел В предполагает, что отсутствует маршрут из В в А. В такой ситуации множество узлов сети можно разбить на т классов (уровней) таким образом, что отсутствуют маршруты между узлами одного уровня, а перемещение требований из узлов уровня г возможно только в узлы уровня г+1. Перенумеруем уровни и узлы каждого уровня так, что символ (г,з) обозначает ¿-й узел г-го уровня и г = 1, ш, ^ = 1, щ, щ = N (щ — число узлов на уровне г). Обозначим множество всех узлов N = {(г, ¿), j = 1, щ, г = 1, т}. В качестве маршрута рассматривается набор I = , определяющий последовательность

узлов, проходимых требованием, так что зк — номер посещаемого на к-м уровне узла. При этом поступление требований извне происходит лишь в узлы первого уровня, уход из сети — через узлы последнего (т-го) уровня и каждое требование проходит все уровни. Эти, на первый взгляд, ограничительные предположения легко устраняются введением фиктивных узлов с нулевым временем обслуживания. На множестве Л всех маршрутов задана вероятностная мера {Р(1), /е^и требования, поступающие в сеть, выбирают свои маршруты в соответствии с этой мерой независимо друг от друга. Каждый узел сети является многоканальной системой обслуживания с различными приборами и г(г,з) — число приборов в узле (1,3), —

функция распределения, а (/З^)-1 — математическое ожидание времени обслуживания на к-м приборе узла (г,3). Предполагается, что поступающий в

сеть поток X(t) — регенерирующий с интенсивностью А. Выпишем условие, аналогичное (2), обеспечивающее регенерацию описывающих сеть процессов. Пусть rj^jj — случайная величина с функцией распределения В^^(х),

к = l,r(¿,¿), = тах{?7^, к = 1 ,r(i,j)}. Предположим, что найдется маршрут I0 = (j?,..., j^) и Р(/0) > 0 такой, что

т

Р{?2 = о} + P{¿2 = i, г2 - h > £ тя) > о. (5)

¿=i

По-сути это условие означает возможность освобождения всей системы с ненулевой вероятностью. Пусть — случайный процесс для

узла (i,j), a_W(í) = (i,j) e N}. Определим также вложен-

ный процесс Wn = - 0) = {Wíi>, (i,j) e N} и суммы координат,

так что wn(i,j) — сумма координат вектора Й^', wn{i) = YJjU ™n{i,j), wn = Y^(i,j)eNwn(hj)- Коэффициентом загрузки узла (i,j) является величина p(i,j) = (^21=1 ßi,j) > гДе интенсивности A¿¿ определяются соотношениями Xijc = AПоложим р = max{p(i,j)\(i,j) е N}. Следствие 1 (1). Пусть выполнено условие (5).

1. Если р < 1, то процесс П эргодичен. При условии 4 эргодическим является и процесс W(t).

2. Если р> 1, то wn-+ со п.н..

3. Если р — 1 и выполнены дополнительные предположения (4) для входящего в сеть потока и времен обслуживания всех узлов, то wn сильно стохастически неограничен.

В заключительной части первой главы, на основании предельных теорем для жидкостной модели33 и некоторых результатов для модифицированной многоканальной системы обслуживания34, доказываются функциональные предельны теоремы в условиях высокой и сверхвысокой загрузки. Сначала рассматривается случай сверхвысокой загрузки, т.е. ситуация, когда р> 1. Пусть Q(t)

— число требований в стандартной системе обслуживания в момент t. Введем нормированный процесс Qn(t) = ЗдеСь (а>)+ = тах(0, х) и нормирующий параметр а определяется соотношениями

г /*оо

= 4+<7% > о, 4 = Y14м 4 = ß!°h 4 = (х-ß-'fdBiix), (6)

JO

33Whitt, W., Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Application to Queues. N.Y.rSpringer, 727 с (2002).

34Боровков, А. А., "Некоторые предельные теоремы теории массового обслуживания. II (многоканальные системы)". Теория вероятностей и её применения, 10, 3, 409-437 (1965).

2 ae a2 al 2areT , „

a = M = Ет^. Имеет место функциональная предельная теорема.

Теорема 3 (5). Пусть случайная величина Q(0) конечна почти наверно и для некоторого 6 > 0 выполнены условия (4), тогда при п оо справедливы утверждения.

1. Если р > 1, то процесс Q„(t) слабо сходится к стандартному вине-ровскому процессу на любом конечном интервале [0, г>].

2. Если р — 1, то процесс Q„{t) слабо сходится к модулю стандартного винеровского процесса на любом конечном интервале [0,г>].

Здесь коэффициент загрузки р задается соотношением (3).

Далее изучается случай высокой загрузки, т.е. когда коэффициент загрузки р < 1, но близок к 1. Для этого рассмотрим последовательность стандартных систем Sn с входящим потоком Xn(t), заданным соотношением

где X(t) — регенерирующий процесс. Мы предполагаем, что последовательности времен обслуживания {r]l}f=1>i = 1 ,г одинаковы для всех систем Sn. Пусть Qn(t) — число требований в системе Sn. Введем процесс Qn(t) = Тогда имеет место следующая функциональная предельная теорема.

Теорема 4 (6). Пусть последовательность (Q^O)}^ равномерно ограничена почти наверно и^для некоторого ô > 0 выполнены условия (4). Тогда при п -»• оо процесс Qn(t) слабо сходится на конечном интервале [0, и] к диффузионному процессу с отражением в нуле и параметрами (-у?,52).

Здесь (3 = 2 Pi и а1 = <т| + а параметры crs и определяются соот-1=1

ношениями (6) и (7) соответственно.

Во второй главе изучается система типа Reg\G\r|оо с неидентичными приборами, функционирующая в случайной среде. Мы предполагаем, что случайная среда может выводить из строя все приборы. Требования, обслуживание которых было прервано выходом системы из строя, не покидают систему, дожидаются ее восстановления и продолжают обслуживание на тех же приборах. Время до поломки системы случайно и распределено по показательному закону со средним сц. Время восстановления системы имеет произвольное распределение с конечным средним <22. Для доказательства

эргодичности процесса, определяющего, число требований в системе, используется метод склеивания (coupling)35, т.е. строится другой процесс в котором периоды ремонта приборов исключены, и система, описываемая им, работает бесперебойно. Тогда для нового процесса применимы эргодические теоремы 1 и 2. Далее устанавливается, что процесс, равный модулю разности между первоначальным и новым процессами, стохастически ограничен. Таким образом, условия эргодичности обоих процессов совпадают. Пусть Q(t) — число требований в многоканальной системе обслуживания с неидентичными приборами и регенерирующим входящим потоком, функционирующей в случайной среде. Тогда имеет место следующая теорема.

Теорема 5 (10). 1, Если выполнено условие (2), распределение т2 содержит абсолютно непрерывную компоненту и р = ^ < 1, где А = то процесс Q(t) эргодичен.

2. Прир > 1, а также прир — 1 и дополнительных условиях (4), выполненных для некоторого S > 0, этот процесс сильно стохастически неограничен.

Во второй главе также изучаются системы типа iîepjG|rjoo с ненадежными приборами, которые выходят из строя независимо друг от друга и других процессов системы. Здесь предполагается, что поломка г-го прибора (г = 1, г) возможна только тогда, когда он занят обслуживанием требования. При этом, время до выхода г-го прибора из строя имеет показательное распределение со средним 7Г1 и не зависит от времени бесперебойной работы других приборов. Ремонт прибора начинается немедленно после его поломки и продолжается случайное время с функцией распределения А (ж) и средним di для г-го прибора. Введем также преобразования Лапласа-Стильтьеса bi{s) и Ai(s) функций Bi{x) и Д(ж) (г = 1,г) соответственно. По аналогии с работой Д. Гайвера36 рассматриваются три различных варианта поведения требования, обслуживание которого было прервано выходом прибора из строя.

• Требование покидает систему сразу после восстановления прибора (модель Mi).

• После восстановления прибора обслуживание начинается сначала на том же приборе, и это новое время обслуживания не зависит от предыдущего (модель Мг).

• После восстановления прибора обслуживание продолжается на том же приборе с тем же временем обслуживания (модель Мз).

35LmdvaU, Т., Lectures on the coupling method. N.Y.:Dover Publications, 257 c. (2002).

36Gaver, D. P., Jr., "A Waiting Line with Interrupted Service, Including Priorities". J. Roy. Statist. Soc., 24 73-90 (1962).

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

УСх =

'(й + тГ1)!!-^)] для Ми

(*+тГ1)Р-»Ы1 япя м

¡>((7() ДЛЯ

[¡З^^ + ^ъ) для М3.

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

Теорема 6 (7). Пусть выполнено (2) и распределение т2 содержит абсолютно непрерывную компоненту. Тогда при

Р = < 1 (9)

процессы, описывающие функционирование системы, эргодичны. При р > 1, а также при р = 1, дополнительных условиях (4) и /0°°я:2сШ{(х) < оо (г = 1,г), эти процессы сильно стохастически неограничены.

На основе понятия полного времени обслуживания также устанавливаг-ются функциональные предельные теоремы в условиях высокой и сверхвысокой загрузки. Пусть С}Ц) - число требований в рассматриваемой системе. Введем нормированные процессы ф„(г) = *г')+п* где

= 4 + 4 > о, 4 = е■ 4 =

'Од. + с?)(1 - М70) + 2 (7Г1 + <к) (7-41 ~ и7)) + Ш)) --№+7Г1)2(1-Ь4(70)2 для М\,

— 6-Ы* для М2,

7;/?Г + 4) + (1 + для Мз,

ai = So (x~fii )2dBi(x), a2D. = ¡^(x-d^dD^x) и a\ определяется соотношением (7). Имеет место следующая функциональная предельная теорема в условиях сверхвысокой загрузки.

Теорема 7 (8). Пусть случайная величина Q(0) конечна почти наверно; для некоторого 6 > 0 выполнены условия (4) и параметр загрузки р определяется соотношением (9). Тогда при п -+ оо справедливы следующие утверждения:

1. если р > 1, то процесс Qn(t) слабо сходится к стандартному вине-ровскому процессу на любом конечном интервале [0, г>] /

2. если р = 1, то процесс Qn(t) слабо сходится к модулю стандартного винеровского процесса на любом конечном интервале [0, v).

Далее устанавливается предельная теорема в условиях высокой загрузки. Для этого, так же, как и для стандартной многоканальной системы, введем последовательность входящих потоков Xn{t) задаваемых соотношением (8). Пусть Xn(t) — входящий поток в систему Sn. Мы предполагаем, что последовательности времен обслуживания {>4}^, г = 1/г одинаковы для всех систем Sn. Пусть Q„(t) — число требований в системе Sn. Введем нормированный процесс Qn(t) = ■

Теорема 8 (9). Пусть последовательность {<?„(()) равномерно ограничена почти наверно и для некоторого 5 > 0 выполнены условия (4) и параметр^загрузки р определяется соотношением (9). Тогда при п оо процесс Qn(t) слабо сходится на конечном интервале [0, г>] к диффузионному процессу с отражением в нуле и параметрами а2), где а2 = erf

г ^

и X"1 = xf1-!=1

В третьей главе рассматривается система S типа Reg\G\r с регенерирующим входящим потоком и возможностью неприсоединения к очереди. Заявка, поступающая в систему, в которой уже находятся j требований, присоединяется к очереди с вероятностью fj и уходит с вероятностью 1 — fj. Мы предполагаем, что последовательность /_,• не возрастает, >■/,/> 0 и

оо

£(/,■ - /) < оо. (И)

;=0

Если fj = 1 при j < т для некоторого т> г и = 0 при j > то, мы получаем систему cm —г местами для ожидания в очереди, при тп = г систему с отказами, а при fj = 1 стандартную модель без ограничений. Эргодичность

подобной системы с одинаковыми приборами исследовалась Т. Белорусо-вым37. В диссертационной работе эти результаты обобщаются на системы с различными приборами. Пусть СЦг) - число требований в системе 5 в момент времени Для доказательства эргодической теоремы и выяснения предельного поведения процесса <5(£) вводится новая система 5+. Система 5+ задается входящим потоком и теми же функциями распределения времен обслуживания, что и система 5, но отличается от нее дополнительными правилами обслуживания требований. Будем считать, что требования поступающие в систему разделяются на два типа. Новое требование присоединяется к очереди и считается требованием первого типа с вероятностью /. С вероятностью $$ - / оно присоединяется к системе, но считается требованием второго типа, и не присоединяется к системе с вероятностью 1 - /•. Предположим, что в 5+ требования второго типа не обслуживаются и, являясь элементами очереди, не создают помех для обслуживания требований первого типа. Обозначим (^(Ь) - количество требований г-го типа в момент t в системе (г = 1,2). Тогда имеет место следующая лемма мажорирова-

Лемма 1 (9). Если <3(0) = д+(0) и £+(0) = 0, то при любом I > 0 выполнены стохастические неравенства (^(Ь) - г < (¿(г) < (¿{(г) + + г.

Отметим, что новая система может рассматриваться как стандартная многоканальная система с разреженным регенерирующим входящим потоком, и для нее справедливы результаты теорем 2, 3, 4. Таким образом, опираясь на лемму 1, для системы с возможностью неприсоединения к очереди мы доказываем следующую эргодическую теорему.

Теорема 9 (12). 1. Если выполнены условие 4, соотношения (И), (2) и

где Р = то процесс (¿(г) эргодичен.

2. При р > 1, а также при р = 1 и дополнительных условиях (4) для некоторого 6 > 0, эти процессы сильно стохастически неограничепы.

Далее, на основе леммы 1 мы устанавливаем функциональные предельные теоремы в условиях высокой и сверхвысокой загрузки. Введем нормированный процесс <2п(г) = Здесь

ния.

р = /А/г1 < 1,

(12)

/(1 ~ Ла + | (/о) У? 2арсоу{Ъ, т2) р, у? ¿¿2

(13)

"Белорусов, Т. Н., "Эргодичность многоканальной системы обслуживания с возможностью неприсоединения к очереди". Теория вероятностей и её применения, 56, 1, 145-152 (2011).

Теорема 10 (13). Если р > 1 (р = 1), для некоторого 5 > 0 выполнены условия (4) и случайная величина Q(0) конечна почти наверно, то нормированный процесс Qn{t) слабо сходится на конечном интервале [0, w] к стандартному винеровскому процессу (модулю стандартного винеровского процесса) при п —> оо.

Для выяснения поведения процесса Q(t) в условиях высокой загрузки задается последовательность систем обслуживания. Введем последовательность потоков Xn(t) = X (V1 (l - tj , где р задается соотношением

(12). Пусть Xn(t) — входящий поток в систему Sn. Мы предполагаем, что последовательности вероятностей присоединения {fj}fLi и времен обслуживания {rfk}f=1J, = 1,7- одинаковы для всех систем Sn. Введем нормированный процесс Qn{t) = Тогда имеет место теорема.

Теорема 11 (14). Пусть последовательность {Qn(0)}^=1 равномерно ограничена почти наверно и для некоторого 5 > 0 выполнены условия (4), тогда нормированный процесс Qn(t) слабо сходится на конечном интервале [0, и] к диффузионному процессу с отражением в нуле и параметрами (—/3, а2) при п оо. Здесь а2 = + а параметры и а2х определяются соотношениями (6) и (13) соответственно.

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

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

[1] Афанасьева, Л. Г., Ткаченко А. В., "Многоканальные системы обслуживания с регенерирующим входящим потоком". Теория вероятностей и ее применения, 58, 2, 210-234 (2013).

Афанасьева Л. Г. поставила задачу и предложила методы решения. Все результаты принадлежат Ткаченко А. В.

[2] Ткаченко, А. В., "Одноканальная система с ненадежным прибором и различными временами обслуживания". Вестн. Моск. ун-та, Сер. 1. Ма-тем. Механ., 2, 10-17 (2013).

[3] Ткаченко, А. В., "Многоканальные системы обслуживания с возможностью неприсоединения к очереди и регенерирующим входящим потоком". Деп. в ВИНИТИ 03.07.2013, 195-В2013, 19 (2013).

[4] Afanasyeva, L. G., Tkachenko, А. V., "Queueing Systems with Regenerative Input Flow and Heterogeneous Servers". XXX International

Seminar on Stability Problems for Stochastic Models and VI International Workshop "Applied Problems in Theory of Probabilities and Mathematical Statistics Related to Modeling of Information Systems Book of Abstracts, 9-10. Institute of Informatics Problems, RAS, Moscow, 2012.

Афанасьева Л. Г. поставила задачу и предложила методы решения. Все результаты принадлежат Ткаченко А. В.

[5] Ткаченко, А. В., "Многоканальные системы обслуживания с регенерирующим входящим потоком и неидентичными приборами". Международная конференция "Теория Вероятностей и ее Приложения"посвященной 100-летию со дня рождения Б.В. Гнеденко, Тезисы докладов, 210-211, Ленанд, Москва, 2012.

[6] Tkachenko, А. V., "Multichannel Queuing Systems in a Random Environment". Seventh International Workshop on Simulation, Book of Abstracts, 347-348, Department of Statistical Sciences, University of Bologna, Rimini, 2013.

[7] Tkachenko, A. V., "Multichannel queuing systems with bounded waiting time and regenerative input flow". XXXI International Seminar on Stability Problems for Stochastic Models and VII International Workshop «Applied Problems in Theory of Probabilities and Mathematical Statistics Related to Modeling of Information Systems» and International Workshop "Applied Probability Theory and Theoretical Informatics", Book of Abstracts, 123-124, Institute of Informatics Problems, RAS, Moscow, 2013.

[8] Ткаченко, А. В., "Система M|G|l|oo с ненадежным прибором и различными временами обслуживания". XIX Международная молодежная научная конференции студентов, аспирантов и молодых учёных «Ломоносов», Тезисы докладов, 1, МАКС Пресс, Москва, 2012.

[9] Ткаченко, А. В., "Многоканальные системы обслуживания с ограничениями и регенерирующим входящим потоком." XX Международная молодежная научная конференции студентов, аспирантов и молодых учёных «Ломоносов», Тезисы докладов, 1-2, МАКС Пресс, Москва, 2013

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж [ (/0экз. Заказ № S£'

. / /

московский государственный университет

имени М. В. ЛОМОНОСОВА

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

04201365399 УДК 519.21

Ткаченко Андрей Викторович

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

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

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

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

Москва 2013

Оглавление

Введение 4

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

1.1 Регенерирующие потоки..........................................18

1.1.1 Определение регенерирующих потоков..................18

1.1.2 Свойства регенерирующих потоков......................23

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

1.2.1 Описание процессов и основные определения..........25

1.2.2 Эргодичность и стохастическая ограниченность процессов ......................................................30

1.3 Эргодическая теорема для многоканальной системы обслуживания с неидентичными приборами..........................32

1.3.1 Описание модели..........................................32

1.3.2 Эргодическая теорема....................................33

1.4 Условие эргодичности иерархических сетей обслуживания с регенерирующим входящим потоком............................44

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

1.5.1 Жидкостные системы обслуживания....................49

1.5.2 Модифицированная система обслуживания............51

1.5.3 Стандартная многоканальная система обслуживания 56

Глава 2. Системы Яед\С\г\оо с ненадежными приборами 60

2.1 Система обслуживания с ненадежными и восстанавливающимися приборами....................................................60

2.1.1 Эргодичность системы обслуживания с ненадежными приборами......................... 62

2.1.2 Предельные теоремы для многоканальной системы обслуживания с ненадежными приборами........ 65

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

2.3 Система с различными временами обслуживания, зависящими от состояния системы .................... 74

Глава 3. Системы Дед|С|г с нетерпеливыми требованиями 82

3.1 Описание модели..................................................82

3.2 Лемма о мажорировании ........................................85

3.3 Эргодическая теорема для системы обслуживания с нетерпеливыми требованиями............................................92

3.4 Предельные теоремы для системы обслуживания с нетерпеливыми клиентами................................................94

Литература 97

Введение

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

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

Многоканальные системы обслуживания давно и интенсивно изучаются многими авторами. В значительной мере это связано с широким кругом применений в самых различных областях: компьютерные системы, коммуникационные сети, супермаркеты, аэропорты и т.д. (см. например [108]) (Sadowsky, Szpankowski, 1995). Одна из первых проблем, возникающих при анализе этих моделей, — выяснение условий существования собственных предельных распределений (условий стабильности) у процессов, описывающих функционирование систем. Проблема условий эргодичности систем достаточно традиционна для теории массового обслуживания. Эти условия представляют значительный интерес для приложений, поскольку они определяют соотношения .между параметрами модели, при которых не образуется бесконечно больших очередей. С другой стороны, доказательства соответствующих предельных теорем приводят к анализу сложных случайных процессов, вообще говоря, немарковских, что способствует разработке новых подходов и методов. Если удается построить цепь Маркова, связанную с функционированием системы, то доказательства опираются

на соответствующие результаты для марковских цепей. Одними из первых работ, в которых были найдены достаточные условия существования стационарного распределения у цепей Маркова, связанных с очередью в системе, являются [73] (Foster, 1953), [33] (Kendall, 1959) и [105] (Pakes, 1969). Некоторые необходимые условия эргодичности установлены в работах [90] (Kaplan, 1979) и [109] (Sennott et al, 1983). Анализ свойств эргодичности широкого класса случайных процессов проведен в монографии [25] (Боровков, 1999), в которой рассматриваются как цепи Маркова, так и стохастические рекурсивные последовательности и цепи.

Одним из методов анализа стабильности систем обслуживания является сведение исходного, в общем случае, немарковского процесса к марковскому с помощью введения дополнительной переменной. Этот метод использован, например, в [44] (Севастьянов, 1957) для исследования систем с отказами при произвольном распределении времени обслуживания, а также в [34] (Коваленко, 1961) для систем с ограничениями. Другой метод доказательства эргодическнх теорем состоит в построении процессов, стохастически монотонных по времени. В этом случае из монотонности следует существование предела последовательности функций распределения. Условия, при которых этот предел задает распределение вероятностей, могут быть получены с помощью метода, предложенного в [100] (Loynes, 1962), (см., например, [2] (Афанасьева, 1965), [13] (Афанасьева, Мартынов, 1969)).

Заметим также, что начиная с 90-х годов, для анализа стабильности (или нестабильности) систем и сетей обслуживания успешно применяются методы предельных жидкостных моделей (fluid approximation) (см., например, [113] (Rybko, 1992), [66] (Dai, 1995), [67] (Dai, 1996), [75] (Foss, Kovaleskii, 1999), [107] (Pukhal'skii, Rybko, 2000)). По-сути, жидкостная аппроксимация сводится к функциональному закону больших чисел, который выполняется для широкого класса марковских и немарковских систем. Этот подход может оказаться успешным, когда входящий поток принадлежит некоторому подклассу регенерирующих потоков. Например - это марковски-модулированный поток или марковский поток поступлений (см., например, [60] (Asmussen, 1999)). Тогда функционирование системы, вве-

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

Несмотря на достаточно долгую историю развития данного направления, интерес к вопросам эргодичности велик и в настоящее время. Этой проблеме посвящены работы , [54] (Afanas'eva, 1992), [5] (Афанасьева, 2005), [108] (Sadowsky, Szpankowski, 1995), [74] (Foss, Konstantopoulos, 2004), [103] (Morozov, 2009) и многих других авторов.

Для многоканальных систем обслуживания в работах [91] (Kiefer, Wolfowitz, 1955), [100] (Loynes, 1962), [120] (Whitt, 1972), [52] (Фосс, 1983) установлено, что процессы, описывающие функционирование системы, стабильны, если интенсивность поступления новых требований меньше суммарной интенсивности обслуживания, когда все имеющиеся приборы заняты. При этом предполагается, что интервалы между поступлениями требований и времена обслуживания образуют стационарную метрически транзитивную двумерную последовательность и все приборы одинаковы. В такой ситуации введенный в [91] (Kiefer, Wolfowitz, 1955) r-мерный случайный процесс Wn обладает свойством стохастической монотонности, т.е.

—> —> —>

если W1 = 0, то Fn+i(x) = P{Wn+1} < P{Wn] = Fn(x). Отсюда следует сходимость последовательности Fn(x) при нулевых начальных условиях. Доказательство условий стабильности следует из ряда оценок или опирается на метод Фостера [73] (Foster, 1953). Подобный подход можно применить и к системам с ограничениями, обладающим указанными свойствами монотонности [2] (Афанасьева, 1965). Однако для доказательства стабильности при общих начальных условиях требуются дополнительные предположения (см., например. [23, гл. 4 §6] (Боровков, 1980)).

Актуальным направлением развития теории очередей является исследование моделей с входными потоками более общего вида. Одна из первых работ, посвящянных системам с входным потоком непостоянной интенсивности принадлежит Кларку [65] (Clarke, 1953). Из результатов 70-х годов наибольший интерес представляют работы Б. В. Гнеденко и И. П. Макарова [29] (Гнеденко, Макаров, 1971), где для анализа систем с отказами

используются методы теории дифференциальных уравнении; Харрисона и Лемуана [83] (Harrison, Lemoine, 1977), где даются условия существования предельного периодического режима в системе типа M(í)|G|l|oo; и Лемуана [97] (Lemoine, 1981), который установил связь между предельным распределением времени ожидания в периодической системе и вероятностью выхода сложного пуассоновского процесса за криволинейную границу. Это представление оказалось полезным при решении задач устойчивости для систем с потоками, интенсивность которых зависит от времени [12] (Афанасьева, Лустина, 1984). Изучению процессов рождения и гибели с нестационарными параметрами посвящены исследования А. И. Зейфмана [30] (Елесин, Зейфман и др., 2003) и [31] (Зейфман и др., 2007).

Ряд статей, касающихся периодических систем, имеется у Рольски [111] (Rolski, 1986), [112] (Rolski, 1989). Интересны также результаты В. Ф. Матвеева и В. Г. Ушакова [36] (Матвеев, Ушаков, 1984) (приоритетные системы обслуживания), Асмуссепа [59] (Asmussen, 1991) (теоремы переноса), Чанга и Хао [62] (Chang, Chao, 1991) (неравенства для дисперсии времени ожидания). Заметим, что входные потоки в упомянутых работах относятся к классу регенерирующих, так что в диссертации исследуются системы обслуживания, обобщающие модели, изучаемые в последние годы [17] (Баштова, 2004), [18] (Баштова, 2006), [6] (Афанасьева, Баштова, 2008).

В настоящей работе изучается система Reg\G\r с регенерирующим входящим потоком и различными приборами, т.е. каждый прибор имеет свою функцию распределения времени обслуживания. Отметим, что класс регенерирующих потоков весьма широк. Регенерирующими являются большинство потоков, обычно используемых в теории массового обслуживания в качестве входных потоков. Среди них дважды стохастический пуас-соновский поток со случайной интенсивностью, являющейся регенерирующим процессом [79] (Grandell, 1976), марковски-модулировапный поток [59] (Asmussen, 1991), марковский поток поступлении [94] (Klimenok et al., 2005), полумарковский поток [60] (Asmussen, 1999), [55] (Afanas'eva et al., 2009). Регенерирующие потоки обладают рядом замечательных свойств. В частности, имеет место слабая сходимость последовательности, состоящей из временных интервалов между поступлениями требовании, к стационар-

ной. Таким образом, опираясь на упомянутые выше результаты для систем со стационарной последовательностью, определяющей входящий поток, можно доказать условия стабильности при регенерирующем потоке, когда все приборы идентичны [52] (Фосс, 1983). При неидентичных приборах это сделать не удается, поскольку г-мерный процесс, описывающий функционирование системы, даже при нулевых начальных условиях не обладает свойством стохастической монотонности. В такой ситуации анализ стабильности системы требует других подходов (см. например [23, гл. 4 §4] (Боровков, 1980)). Отметим также, что при довольно общих условиях свойство регенерации сохраняется при прохождении через систему обслуживания. Это позволяет исследовать последовательно соединенные системы обслуживания и иерархические сети, опираясь на результаты, касающиеся отдельных узлов, подобно тому, как это сделано в [4] (Афанасьева, 1987), [104] (Могогоу, 2004), [15] (Афанасьева, Ткаченко, 2013). И наконец, потоки данного класса могут использоваться при построении математических моделей многих реальных объектов, поскольку интенсивность таких потоков может зависеть от времени и, более того, являться случайным процессом.

В диссертации также рассматриваются многоканальные системы обслуживания с ненадежными приборами, системы, функционирующие в случайной среде и системы с нетерпеливыми клиентами. Системы обслуживания с ненадежными приборами изучаются уже давно. В статье [32] (Золотарев, 1964) исследована система М|М|п с ожиданием, приборы которой отказывают и восстанавливаются по показательному закону, причем интенсивность отказа одинакова в свободном и занятом состоянии. Система М\М\п с профилактикой и ремонтом обслуживающих приборов рассмотрена в [45] (Султанова, 1968) (все определяющие процесс случайные величины обладают экспоненциальным распределением). В работе [16] (Баша-рин, 1965) изучены системы с ограниченной очередью и ненадежным прибором. Входящий поток представляет собой сумму конечного числа простейших потоков, каждый из которых имеет различную интенсивность. Рассмотрены три различные дисциплины обслуживания: прямой, обратный и случайный выбор требований. Система М|М|1 со случайной, меняющейся по марковскому закону интенсивностью обслуживания, исследована

в [70] (Eisen, 1963). Система M|G|1, в которой последовательность периодов безотказной работы и периодов восстановления прибора представляет собой альтернирующий процесс восстановления, исследована в [71] (Eisen, Leibowitz, 1963). Одной из важнейших работ по системам с ненадежными приборами является статья [77] (Gaver, 1962), где для системы M|G|1 с ненадежным прибором рассматривались четыре различных типа прерывания обслуживания. Системы с ненадежными приборами часто являются предметом современных исследований. В качестве примера приведем статьи [69] (Djcllab, 2002), [114] (Sherman et al., 2009), где рассматривались системы с уходом требований на орбиту и повторным обслуживанием (retrial queues). Результаты могут применяться в работе с мультимедийными приложениями. Кроме того, модели с выходящими из строя приборами в том или ином виде часто появлякнсн при анализе транспортных систем. Примером могут послужить работы [78] (Gideon, Руке, 1999), [10] (Афанасьева, Булинская, 2009), [11] (Афанасьева, Булпнская, 2010), [84] (Helbing, Jiang, Treiber, 2005), [63] (Caceres, Ferrari, Pechersky, 2007), [14] (Афанасьева, Руденко, 2012), [41, 42] (Руденко, 2012a, 2012b). Достаточно полный обзор работ по системам с ненадежными приборами можно найти в [96] (Krishnamoorthy et al., 2012) и [38] (Печинкин, Соколов и др., 2009).

Системы с возможностью неприсоединения к очереди являются традиционными в теории очередей. Их изучение началось уже с середины прошлого столетия [85] (Ilomma, 1955) , [80, 81, 82] (Haight, 1957, 1959, 1960), [72] (Finch, 1959). Однако, в настоящее время, в связи с широким развитием телекоммуникационных сетей, системы с нетерпеливыми клиентами особенно привлекли внимание исследователей и стали интенсивно применяться для анализа эффективности работы колл-центров, ориентированных на обслуживание, (см., например, [125] (Whitt, 2006)). Важной чертой моделирования таких систем является нетерпеливый характер поведения клиентов. Такое поведение, как правило, может проявляться как отказ от присоединения к очереди, если ее длина больше некоторого значения с априори заданной вероятностью или уход из очереди клиента, если его время ожидания обслуживания превысило характерную для него величину (см, например, [95] (Koole, Mandelbaum, 2002), [76] (Garnett, 2002)).

Как правило, модели с нетерпеливыми клиентами являются стабильными при любых начальных условиях [87] (Ibrahim, Whitt, 2009), однако, при чрезмерной загрузке системы, здесь возникает проблема высоких потерь пеобслуженных требований [124] (Whitt, 2005), [99] (Liu, Whitt, 2012). В работах [1] (Афанасьева, 1964), [3] (Афанасьева, 1966), [8] (Афанасьева, Белорусов, 2011), [19] (Белорусов, 2011) предложено обобщение моделей с нетерпеливыми клиентами, так что система может быть неэргодичной.

Главная трудность в изучении систем с достаточно общими входными потоками и произвольным распределением времени обслуживания состоит в том, что за редким исключением не удается получить явные выражения для основных характеристик системы. И здесь есть три пути — построение вычислительных алгоритмов, статистическое моделирование или исследование крайних случаев (ситуации большой и малой загрузки). Заметим, что первый путь не всегда осуществим, поскольку требует дополнительных предположений. Можно построить алгоритм для системы типа Ek\Em\r, а затем использовать его как аппроксимацию для систем типа GI\GI\r. Удается также получить вычислительные алгоритмы для систем с марковски-модулированным потоком. Говоря об аппроксимации, необходимо исследовать ее точность, доказав соответствующие теоремы устойчивости. Что касается статистического моделирования, то его осуществление при высокой загрузке представляет существенные трудности. Имеется обширная литература, в которой доказываются предельные теоремы для стационарных и нестационарных характеристик систем, находящихся в условиях, бли�