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

• Ткаченко, Андрей Викторович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Ткаченко, Андрей Викторович

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

Введение диссертации (часть автореферата) на тему «Многоканальные системы обслуживания с неидентичными приборами»

Введение

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

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

Многоканальные системы обслуживания давно и интенсивно изучаются многими авторами. В значительной мере это связано с широким кругом применений в самых различных областях: компьютерные системы, коммуникационные сети, супермаркеты, аэропорты и т.д. (см. например [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. Удается также получить вычислительные алгоритмы для систем с марковски-модулированным потоком. Говоря об аппроксимации, необходимо исследовать ее точность, доказав соответствующие теоремы устойчивости. Что касается статистического моделирования, то его осуществление при высокой загрузке представляет существенные трудности. Имеется обширная литература, в которой доказываются предельные теоремы для стационарных и нестационарных характеристик систем, находящихся в условиях, близких к критическим. Первыми работами, посвященными применению общих принципов теории случайных процессов к исследованию критических режимов систем обслуживания, были статьи [39] (Прохоров, 1963), [40] (Прохоров, Висков, 1964), [27] (Висков, 1964). В несколько более раиних работах Кинг-мена [92] (Kingman, 1962) и Райса [110] (Rise, 1962) предельные теоремы доказывались посредством исследования аналитических выражений для характеристик систем обслуживания. В монографии А. А. Боровкова [23] (Боровков, 1980) развита общая теория предельного поведения процессов массового обслуживания при слабых условиях относительно потока требований, длительности обслуживания и структуры самой системы. Доказаны

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

Обзор широкого круга задач, связанных с поведением системы в условиях высокой загрузки, представлен в работах [121] (Whitt, 1974), [93] (Kimura, 1993). Несмотря на долгую историю исследования проблемы высокой загрузки для различных систем актуальны и до настоящего времени [68] (Dantzer, 2001), [89] (Jelenkovich et al., 2004), [123] (Whitt, 2004), [87] (Ibrahim, Whitt, 2009). При этом значительная часть работ посвящена рассмотрению систем с рекуррентным входящим потоком. В работах [7] (Афанасьева, Баштова, 2009), [8] (Афанасьева, Белорусов, 2011), для различных одноканальных систем с регенерирующим входящим потоком устанавливается сходимость предельного стационарного распределения нормированного времени ожидания и числа требований к экспоненциальному. В схеме серий доказана С-сходимость процесса времени ожидания к диффузионному с постоянными коэффициентами и отражением от нулевой границы.

В диссертации задача о высокой загрузке для многоканальной системы обслуживания с регенерирующим входящим потоком и различными приборами изучается в двух вариантах. В одной постановке рассматривается поведение нормированного процесса, определяющего количество требований в системе, в условиях перегруженной системы, а в другой — в условиях стабильной системы, но близкой к критической. Доказательства опираются на свойство сходимости нормированного регенерирующего потока к винеровскому процессу и соответствующие результаты для систем с рекуррентным потоком [86] (Iglehart, Whitt, 1970), [122] (Whitt, 2002).

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

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

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

Прежде всего, на основе теоремы восстановления Блекуэлла [61] (Blackwell, 1948) и узловой теоремы Смита [115] (Smith, 1955) для регенерирующих процессов, устанавливается общая теорема об эквивалентности эргодичности и стохастической ограниченности при некоторых дополнительных условиях. Эта теорема представляет самостоятельный интерес и может быть применима для анализа стабильности различных систем обслуживания. Опираясь на эту теорему мы находим необходимое и достаточное условие эргодичности рассматриваемой системы, что обобщает результаты [108] (Sadowsky, Szpankowski, 1995) и [101] (Morozov, 1997) на случай более общего регенерирующего входящего потока. Поскольку свойство регенерации потока сохраняется при прохождении через систему обслуживания, то теоремы эргодичности для многоканальных систем могут быть обобщены на иерархические сети, где каждый узел — многоканальная система обслуживания. Соответствующая теорема также доказана в этой главе. Далее устанавливается сходимость нормированного процесса числа требований в системе к диффузионному в условиях высокой и сверхвысокой загрузках, обобщающая результаты [86] (Iglehart, Whitt, 1970) и [122] (Wliitt, 2002) для случая регенерирующего входящего потока. Центральном шагом при доказательстве соответствующих теорем, является построение модифицированной системы, предложенной в [21] (Боровков, 1965). Поведение этой системы асимптотически эквивалентно поведению стандартной многоканальной системы, однако вычислять различные характеристики гораздо проще именно для модифицированной системы.

2. Вторая глава посвящена анализу систем типа -Re(7|G|r|oo, функционирующих в случайной среде, и системам с ненадежными приборами. Случайная среда функционирует по своим законам и имеет непосред-

ственное влияние на всю систему в целом. В пашем случае эта среда может выводить из строя все приборы, которые затем восстанавливаются и начинают функционировать одновременно. Время до поломки системы случайно и распределено по показательному закону. Время восстановления системы имеет произвольное распределение. Для доказательства эргодичности процесса, описывающего эволюцию системы, используется метод склеивания (coupling) [98] (Lindval, 2002), т.е. строится другой процесс в которых периоды восстановления системы исключены, и система, описываемая им, работает бесперебойно. Далее удастся показать, что разность между первоначальным и новым процессами стохастически ограничена. Более того, для нового процесса применима эргодическая теорема из 1-й главы, что позволяет установить условия эргодичности первоначальной системы.

Во второй главе также изучаются системы типа Reg\G\r\oo с ненадежными приборами, которые выходят из строя независимо друг от друга и других процессов системы. По аналогии с [77] (Gaver, 1962) рассматриваются три различных варианта поведения требования, обслуживание которого было прервано выходом прибора из строя

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

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

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

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

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

3. В третьей главе рассматриваются системы типа Яед\С\г с возможностью неприсоединения к очереди. Заявка, поступающая в систему, в которой уже находятся J требований, присоединяется к очереди с вероятностью и уходит с вероятностью 1 — /3. Мы предполагаем, что —> / и / > 0. Эргодичность подобной системы с одинаковыми приборами исследовалась в [19] (Белорусов, 2011). В диссертационной работе эти результаты обобщаются на системы с различными приборами. Для доказательства эргодпческой теоремы и выяснения предельного поведения процесса, определяющего число требований в системе, вводится новая система. В ней те требования, которые могли бы не присоединиться, если бы очередь была очень большой, но все же присоединились к очереди, не обслуживаются и находятся в системе бесконечно долго. Далее доказывается лемма, устанавливающая что число требований в новой системе стохастически больше числа требований в первоначальной. При этом, новая система может рассматриваться как стандартная многоканальная система с разреженным регенерирующим входящим потоком, и для нее справедливы результаты первой главы. Таким образом, для системы с возможностью неприсоединения к очереди доказывается эргодическая теорема и устанавливаются функциональные предельные теоремы в условиях высокой и сверхвысокой загрузки.

Результаты диссертации опубликованы в работах [15] (Афанасьева, Ткаченко, 2013), [48] (Ткаченко, 2013а), [49] (Ткаченко, 2013Ь), [50]

(Ткаченко, 2013с), [118] (Tkachenko, 2013а), [119] (Tkachenko, 2013b), [57] (Afanasyeva, Tkachenko, 2012), [46] (Ткаченко, 2012a), [47] (Ткаченко, 2012b).

Обозначения и сокращения. Если не оговорено иначе, за исходное вероятностное пространство принято (Q.,J-,P), и все случайные элементы предполагаются заданными на этом пространстве. Для случаев, рассмотренных в диссертации, доказательство существования единого вероятностного пространства для нескольких случайных элементов опирается на теорему Колмогорова (см. [26] (Булинский, Ширяев, 2003)) и опускается в тексте диссертации. Функции распределения случайных величин полагаются непрерывными слева, таким образом, для случайной величины £ её функция распределения равна F^(x) = < х).

Сумма по пустому множеству индексов полагается равной нулю, а произведение — единице.

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

:= — положить по определению.

п.н. — почти наверное (по мере Р исходного вероятностного пространства, если не оговорено иначе).

=>■ — сходимость по вероятности (по мере Р исходного вероятностного

пространства, если не оговорено иначе).

d

= — равенство распределении.

К = (—оо,+оо) — множество действительных чисел.

М+ = [0, +оо) — множество неотрицательных действительных чисел.

Z = {0, ±1, ±2,...} — множество целых чисел.

Z+ = {0,1,2,...} — множество неотрицательных целых чисел.

Ю>[0, v\ — пространством функций, непрерывных справа и имеющих предел слева на отрезке [0, г*]

öij — символ Кронекера.

а (Л) — наименьшая сигма-алгебра, порождённая системой множеств Л.

Gl) - наименьшая сигма-алгебра, относительно которой измеримы все случайные элементы а £ X. В этом случае говорят, что сигма-алгебра порождена случайными элементами а £ Т.

= сг(Х(з),0 ^ я ^ — сигма-алгебра, порождённая случайным

процессом {Х(з),0 ^ й ^ ¿}.

В(Е) — сигма.-алгебра борелевских множеств пространства Е. 1а (ж) — индикатор множества А, то есть

(.х)+ = тах( 0, х).

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

Список литературы диссертационного исследования кандидат наук Ткаченко, Андрей Викторович, 2013 год

Литература

1. Афанасьева, Л. Г., "О некоторых задачах ТМО с ограниченным временем ожидания". Техн. киберн., 6, 27-37 (1964).

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

3. Афанасьева, Л. Г., "О потоке потерянных требований в некоторых системах массового обслуживания с ограничением". Изв. AFI СССР Техн. кибернетика, 3, 57-65 (1966).

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

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

6. Афанасьева Л. Г., Баштова Е. Е. "Предельные теоремы для систем обслуживания с дважды стохастическим пуассоновским потоком (условия высокой загрузки)". Пробл. передачи информ., 44, 4, 72-91 (2008).

7. Афанасьева, Л. Г., Баштова, Е. Е., "Предельные теоремы для систем массового обслуживания в условиях высокой загрузки". Современные проблемы математики и механики, М.: Изд-во МГУ, 4, 3, 40-54 (2009).

8. Афанасьева, Л. Г., Белорусов, Т. Н., "Предельные теоремы для систем с нетерпеливыми клиентами в условиях высокой загрузки". Теория вероятностей и ее применения, 56, 4, 788-796 (2011).

9. Афанасьева, Л. Г., Булинская, Е. В., Случайные процессы в теории массового обслуэюивания и управления запасами. М.: Изд-во МГУ, 110 с. (1980).

10. Афанасьева, Л. Г., Булинская, Е. В., "Некоторые задачи для потоков взаимодействующих частиц". Современные проблемы математики и механики, IV, 55-67 (2009).

11. Афанасьева, Л. Г., Булинская, Е. В., "Математические модели транспортных систем, основанные на теории очередей". Труды МФТИ, 4, 2, 6-21 (2010).

12. Афанасьева, Л. Г., Лустина, А. А., "О периодическом решении уравнения Такача". Пробл. уст. стох. моделей. Труды семинара ВНИИСИ (1984).

13. Афанасьева, Л. Г., Мартынов, А. В., "Об эргодических свойствах систем массового обслуживания с ограничением". Теория вероятностей и её применения, 14, 1, 105-114 (1969).

14. Афанасьева, Л. Г., Руденко, И. В., "Системы обслуживания (?/|С|оо и их приложения к анализу транспортных моделей". Теория вероятностей и её применения, 57, 3, 427-452 (2012).

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

16. Башарин, Г. П., "Один прибор с конечной очередью и заявки нескольких видов". Теория вероятностей и её применения, 10, 2, 282-296 (1965).

17. Баштова, Е. Е., "Виртуальное время ожидания в одной системе с марковски-модулированным входным потоком". Матем. заметки, 76, 6, 945-948 (2004).

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

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

20. Биллингсли, П Сходимость вероятностных мер. М.: Наука, 351 с. (1977)

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

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

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

24. Боровков, А. А., Теория вероятностей. М.: Наука, 432 с. (1986).

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

26. Булинский, А. В., Ширяев, А. Н., Теория случайных процессов. М.: ФИЗМАТЛИТ, 400 с. (2003).

27. Висков, О. В., "Две асимптотические формулы теории массового обслуживания". Теория вероятностей и её применения, 9, 4, 104-112 (1964).

28. Гнеденко, Б. В., Коваленко, И. Н., Введение в теорию массового обслуживания. М.: Изд-во ЛКИ, 400 с. (2011).

29. Гнеденко, Б. В., Макаров, И. П., "Свойства решений для систем с потерями в случае периодической интенсивности". Дифференциальные уравнения, 7, 1696-1698 (1971).

30. Елесин, М., Зейфман, А., Кузнецов, А. "Об эргодичности некоторых марковских цепей с непрерывным временем". Стат. методы оценивания и проверки гипотез, Пермь, ПГУ, 57-66 (2003).

31. Зейфман, А. И., Сатин, Я. А., "Средние характеристики марковских систем обслуживания". Автомат, и телемех., 9, 122-133 (2007).

32. Золотарев В.М., "Распределение длины очереди и числа действующих линий в системе типа Эрланга со случайными поломками и восстановлениями линий.". Тр. Мат. ип-та. АН СССР, 71, 51-61 (1964).

33. Кендалл, Д. Г., "Стохастические процессы, встречающиеся в теории очередей, и их анализ методом вложенных цепей Маркова". Математика, 3, 6, 97-111 (1959).

34. Коваленко, И. Н., "Некоторые задачи массовго обслуживания с ограничением". Теория вероятностей и её применения, 6, 2, 222-228 (1961).

35. Кокс, Д., Смит, В., Теория восстановления. М.: Сов. радио, 299 с. (1967).

36. Матвеев, В. Ф., Ушаков, В. Г., Системы массового обслуэюивапия. М.: Изд-во МГУ, 240 с. (1984)

37. Микадзе, 3. И., Микадзе, И. С., Хочолава, В. В. "Об одной многоканальной смешанной системе массового обслуживания с ограниченным временем ожидания". Автомат и телемех., 7, 44-51 (2007).

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

39. Прохоров, Ю. В., "Переходные явления в процессах массового обслуживания". Литое, мат. сб., 3, 1, 199-206 (1963).

40. Прохоров, Ю. В., Висков, О. В., "Вероятность потери вызова при большой интенсивности потока". Теория вероятностей и её применения, 9, 1, 99-104 (1964).

41. Руденко, И. В., "Двухфазная система обслуживания с ненадежными приборами". Вестн. Моск. ун-та. Сер. 1. Матем. Механ., 4, 8-14 (2012).

42. Руденко, И. В., "Двухфазная система обслуживания с ненадежными приборами в условиях высокой загрузки". Вести. Моск. ун-та. Сер. 1 Матем. Механ., 6, 47-50 (2012).

43. Саати, Т. Л., Элементы теории массового обслуживания и ее приложения. М.: Либроком, 520 с. (2010)

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

45. Султанова, Д. X., "Некоторые асимптотические задачи для системы обслуживания с профилактикой и восстановлением". УзССР Фанлар Акад. ахбороти. Физ.-магг. фанлари сер., Изв. АН УзССР., 1, 20-25 (1968).

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

47. Ткаченко, А. В., "Система М|С|1|оо с ненадежным прибором и различными временами обслуживания." XIX Международная молодеэю-ная научная конференции студентов, аспирантов и молодых учёных "ЛомоносовТезисы докладов, МАКС Пресс, Москва, 1 (2012).

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

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

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

51. Феллер, В., Введение в теорию вероятностей и её приложения, т. 1. М.: Либроком, 528 с. (2010)

52. Фосс, С.Г. "Об условиях эргодичности в многоканальных системах массового обслуживания с ожиданием". Сибир. Мат. Журнал, 24, 6, 168— 175 (1983).

53. Хинчин, А. Я., Работы по математической теории массового обслу-оюивания. М.: Физматгиз, 240 с. (1963).

54. Afanas'eva, L. G., "Stochastic boundedness of cyclic queueing systems". IMS, 59, 4, 869-875 (1992).

55. Afanasyeva, L. G., Bashtova, E. E., Bulinskaya, E. V., "Limit theorems for semi-Markov queues and their applications". Communications in Statistics - Simulation and Computation, 41, 6, 688-709 (2012).

56. Afanasyeva, L. G., Bashtova, E. E., "Coupling method for asymptotic analysis of queues with Rregenerative input and unreliable Sserver". Queueing Syst, Electr. Edt. (2013).

57. Afanasyeva, L. G., Tkachenko, A. 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, Institute of Informatics Problems, RAS, Moscow, 9-10 (2012).

58. Asmussen, S., Applied probability and queues. N.Y.: J. Wiley and Sons, 352 p. (1987).

59. Asmussen, S., "Ladder heights and the Markov-modulated M\G\1 queue". Stochastic Processes and Their Applications, 37, 313-326 (1991).

60. Asmussen, S., Semi-Markov queues with heavy tails. In Semi-Markov Models and Application. D.: Kluwer Academic Publishers, 432 p. (1999).

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

62. Chang, C., Chao, X., Pinedo, M., "Monotonicity result for queues with doubly stochastic Poisson arrivals: Ross's conjecture". Adv. Appl. Probab., 23, 210-228 (1991).

63. Caceres, F.C., Ferrari, P.A., Pechersky, E., "A slow-to-start traffic model related to a M\M\1 queue". J. Stat. Mech., P07008 (2007).

64. Cinlar, E., Introduction to stochastic processes. N.J.: Prentis-Hall, 402 p. (1975).

65. Clarke, A. B., "The time dependent waiting line problem". Univ. Michigan Rept., M720-1R39 (1953).

66. Dai, J. G., "On positive Harris recurrence of multiclass queueing networks: a unifed approach via fluid limit models." Ann. Appl. Proba. 5, 49-77 (1995).

67. Dai, J. G., "A fluid-limit model criterion for instability of multiclass queueing networks". Ann. Appl. Proba., 6, 751-757 (1996).

68. Dantzer, J., Mitrani, I., Robert, P., "Large scale and heavy traffic asymptotics for systems with unreliable servers." Queueing Syst. Theory Appl., 38, 1, 5-24 (2001).

69. Djellab, N. V., "On the M\G\1 retrial queue subjected to breakdowns". RAIRO Oper. Res., 36, 299-310 (2002).

70. Eisen, M. M., "Effects of slowdowns and failure on stochastic service systems". Technometrics, 11, 6, 922-927 (1963).

71. Eisen, M. M., Leibowitz, M. "Some remarks on server breakdown". Oper. Res., 5, 3, 385-392 (1963).

72. Finch, P., "Balking in the queueing system GI\M\V\ Acta Mathematica Hungarica, 10, 1, 2, 241-247 (1959).

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

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

75. Foss, S., Kovalevskii, A., "A stability criterion via fluid limits and its application to a polling model." Queueing Syst., 32, 1, 131-168 (1999).

76. Garnett, O., Mandelbaum, A., Reiman, M., "Designing a call center with impatient customers". Manufacturing and Service Oper. Manag., 4, 3, 208227 (2002).

77. Gaver, D., "A waiting line with interrupted service, including priorities". J. Roy. Statist. Soc., 24, 73-90 (1962).

78. Gideon, R., Pyke, R., "Markov renewal modelling of Poisson traffic at intersections having separate turn lanes". Semi-Markov Models and Applications, 285-310 (1999).

79. Grandell, J., Doubly stochastic Poisson processes. Springer-Verlag (1976).

80. Haight, F. A., "Queueing with balking". Biometrika, 44, 3, 4, 360-369 (1957).

81. Haight, F. A., "Queueing with reneging". Metrika, 2, 1, 186-197 (1959).

82. Haight, F. A., "Queueing with balking. II". Biometrika, 47, 3, 4, 285-296 (1960).

83. Harrison, J. M., Lcmoine, A. J., "Limit theorems for periodic queues". J. Appl. Probab., 14, 566-576 (1977).

84. Helbing, D., Jiang, R., Treiber, M., "Analytical investigation of oscillations in intersecting flows of pedestrian and vehicle traffic". Phys. Rev. E, 72, 046130 (2005).

85. Homma, T., "On a certain queuing process". Rep. Statist. Appl. Res. Un. Jap. Sci. Engrs., 4, 1, 14-32 (1955).

86. Iglehart, D. L., Whitt, W., "Multiple channel queues in heavy traffic, I". Adv. Appl. Probab., 2, 2, 150-177 (1970).

87. Ibrahim, R., Whitt, W., "Real-time delay estimation in overloaded multiserver queues with abandonments." Manag. Sei., 55, 10, 1729-1742 (2009).

88. Ito, K., McKean, H., Diffusion processes and their Sample Paths. B.: Springer-Verlag, 329 p. (1965).

89. Jelenkovich, P., Mandelbaum, A., Momcilovich, P., "Heavy traffic limits for queues with many deterministic servers." Queueing Syst., 47, 1, 53-69 (2004).

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

91. Kiefer, J., Wolfowitz, J., "On the theory of queues with many servers". Trans. Amer. Math. Soc., 78, 1-18 (1955).

92. Kingman, J. F. C., "On queues in heavy traffic". J. Roy. Statist. Soc., 24, 381-392 (1962).

93. Kimura, T., "A bibliography of research on heavy traffic limit theorems for queues." Economic J. Hokkaido University, 22, 167-179 (1993).

94. Klimenok, V., Kim, C. S., Orlovsky, D., Dudin, A., "Lack of invariant property of Erlang loss model in case of the MAP input". Queueing Syst., 49, 187-213 (2005).

95. Koole, G., Mandelbaum, A., "Queueing models of call centers: An introduction." Ann. Oper. Res., 113, 41-59 (2002).

96. Krishnamoorthy, A., Pramod, P., Chakravarthy, S., "Queues with interruptions: a survey." TOP, 1-31 (2012).

97. Lemoine, A. J., "On queues with periodic Poisson input". J. Appl. Probab., 18, 889-900 (1981).

98. Lindvall, T., Lectures on the coupling method. N.Y.: Dover Publications, 257 p. (2002).

99. Liu, Y., Whitt, W., "A many-server fluid limit for the Gt\GI\st + GI queueing model experiencing periods of overloading". Oper. Res. Let., 40, 307-312 (2012).

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

101. Morozov, E. "The stability of a non-homogeneous queueing system with * regenerative input". J Math Sci, 83, 3, 407-421 (1997).

102. Morozov, E. "The tightness in the ergodic analysis of regenerative queueing processes." Queueing Syst., 27, 1, 179-203 (1997).

103. Morozov, E., Delgado, R., "Stability analysis of regenerative queueing systems" Autom. Remote Control, 70, 2, 1977-1991 (2009).

104. Morozov, E., "Weak regeneration in modeling of queueing processes." Queueing Syst., 46, 3, 295-315 (2004).

105. Pakes, A. G., "Some conditions for ergodicity and recurrence of Markov chains." Oper. Res., 17, 6, 1058-1061 (1969).

106. Pang, G., Talreja, R., Whitt, W. "Martingale proofs of many-server heavy-traffic limits for Markovian queues". Probability Surveys, 4, 193-267 (2007).

107. Pukhal'skii, A., Rybko, A. "Nonergodicity of a queueing network under nonstability of its fluid model". Probl. Peredachi Inf., 36, 1, 26-47 (2000).

108. Sadowsky, J.S., Szpankowski, W., "The probability of large queue lengths and waiting times in a heterogeneous multiservcr queue part I: tight limits", Adv. Appl. Probab., 27, 2, 1-41 (1995).

109. Sennott, L. I., Humblet, P. A., Twccdie, R. L. "Technical note—mean drifts and the non-ergodicity of Markov chains". Oper. Res., 31, 4, 783-789 (1983).

110. Rise, O., "Single server systems". Bell Syst. Technical J., 1, 269-278 (1962).

111. Rolski, T., "Upper bounds for single server queues with doubly stochastic Poisson arrivals". Math. Oper. Res., 11, 3, 442-450 (1986).

112. Rolski, T., "Queues with nonstationary inputs". Queueing syst., 5, 1-3, 113-129 (1989).

113. Rybko, A. N., Stolyar, A. L., "Ergodicity of stochastic processes describing the operations of open queueing networks". Probl. Peredachi Inf., 28, 3-26 (1992).

114. Sherman, N., Kharoufeh, J., Abramson, M., "An M\G\1 retrial queue with unreliable server for streaming multimedia applications". Probab. Engin. Inf. Sci., 23, 281-304 (2009).

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

116. Thorisson, H., "The coupling of regenerative processes". Adv. Appl. Probab., 15, 531-561 (1983).

117. Thorisson, H., "A complete coupling proof of Blackwell's renewal theorem". Stock. Proc. Appl, 26, 87-97 (1987).

118. Tkachenko, A. "Multichannel queuing systems in a random environment". Seventh International Workshop on Simulation, Book of Abstract, Rimini, University of Bologna, 347-348 (2013).

119. Tkachenko, A. "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 Abstract, Institute of Informatics Problems, RAS, Moscow, 123-124 (2013).

120. Whitt, W., "Embedded renewal processes in the GI\G\s queue". J. Appl. Probab., 9, 650-658 (1972).

121. Whitt, W., "Heavy traffic limit theorems for queues: a survey". Lect. Notes in Economics and Math. Syst., 98, 307-350 (1974).

limits and their application to queues. N.Y.: Springer, 727 p. (2002).

123. Whitt, W., "A diffusion approximation for the G\GI\n\m queue." Oper. Res., 52, 6, 922-941 (2004).

124. Whitt, W., "Engineering solution of a basic call-center model." Manag. Sci., 51, 2, 221-235 (2005).

125. Whitt, W., "Fluid models for multiserver queues with abandonments." Oper. Res., 54, 1, 37-54 (2006).