Системы обслуживания с возможностью неприсоединения к очереди

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

Диссертация посвящена исследованию систем массового обслуживания с нетерпеливыми клиентами (queueing systems with impatient customers), в которых поступающее требование с некоторой вероятностью, зависящей от числа требований в системе, отказывается от обслуживания и покидает систему. Системы с такого рода ограничением именуют системами с возможностью неприсоединения к очереди (queueing systems with balking). В работе основное внимание уделяется отысканию необходимых и достаточных условий эргодичности процессов, описывающих функционирование системы.

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

Одними из первых работ в этом направлении были статьи Кендал-ла (1959 [25]) и Фостера (1953 [56]), в которых приведены достаточные условия существования стационарных распределений цепей Маркова, связанных с очередью. Изучению свойств эргодичности и устойчивости широкого класса случайных процессов посвящена монография А. А. Боров-кова (1999 [18]). В ней рассматриваются цепи Маркова, стохастически рекурсивные последовательности, цепи Маркова в случайной среде, а также континуальные относительно времени аналоги этих процессов. Изучены переходные явления для условий высокой загрузки и получены аппроксимации для стационарных распределений цепи. Значительная часть исследований в теории массового обслуживания посвящена марковским процессам, возникающим в результате введения дополнительных переменных. Этот подход использован Б. А. Севастьяновым (1957 [35]) при анализе систем с отказами и произвольным распределением времени обслуживания, И. Н. Коваленко (1961 [27]) для исследования систем с ограничением, а также многими другими авторами. Ещё один метод доказательства эрго-днческих теорем состоит в построении процессов стохастически монотонных по времени. В такой ситуации из монотонности следует существование предела функций распределения, а условия, при которых этот предел задаёт распределение вероятностей, могут быть получены с помощью метода, предложенного Лойнсом (1962 [70]), что и сделано Л. Г. Афанасьевой (1965 [2], 1969 [10]). Более общая постановка рассмотрена в книге А. А. Бо-ровкова (1980 [16]), что позволило наряду с эргодическими теремами получать теоремы устойчивости.

Несмотря на достаточно долгую историю развития данного направления интерес к вопросам эргодичности велик и в настоящее время. Этой проблеме посвящены работы Г. Ш. Цициашвили, М. А. Осиповой (2008 [42]), А. Мапс1е1Ьаит, Б. геНуп (2007 [71]), Л. Г. Афанасьевой (1992 [43], 2005 [5]), О. Сагпеи et а1. (2002 [57]) и многих других авторов.

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

Во-первых, регенерирующими являются большинство потоков, обычно используемых в теории массового обслуживания в качестве входных потоков. Среди них дважды стохастический пуассоновский поток со случайной интенсивностью, являющейся регенерирующим процессом (J. Grandell, 1976 [58]), марковски-модулированный поток (S. Asmussen, 1991 [47]), марковский поток поступлений (V. Klimenok et al., 2005 [67]), полумарковский поток (S. Asmussen, 1996 [48], Л. Г. Афанасьева, Е. Е. Баштова, Е. В. Бу-линская, 2009 [44]).

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

И наконец, потоки данного класса могут использоваться при построении математических моделей многих реальных объектов, поскольку интенсивность таких потоков может зависеть от времени и, более того, являться случайным процессом. Одна из первых работ, посвящённых системам с входным потоком непостоянной интенсивности принадлежит Кларку (А. В. Clarke, 1953 [52]). Затем Такач (L. Takacs, 1955 [78]) получил иптегро-дифференциальное уравнение для времени ожидания. Из результатов 70-х годов наибольший интерес представляют работы Б. В. Гнеденко и PI. П. Макарова (1971 [22]), где для анализа систем с отказами используются методы теории дифференциальных уравненийХаррисона и Лемуана (J. М. Harrison, A. J. Lemoine, 1977 [62]), где даются условия существования предельного периодического режима в системе типа М (t)Gloo] и Лемуана (A. J. Lemoine, 1981 [68]), который установил связь между предельным распределением времени ожидания в периодической системе и вероятностью выхода сложного пуассоновского процесса за криволинейную границу. Это представление оказалось полезным при решении задач устойчивости для систем с потоками, интенсивность которых зависит от времени (Л. Г. Афанасьева, А. А. Лустина, 1984 [9]). Изучению процессов рождения и гибели с нестационарными параметрами посвящены исследования А. И. Зейфмана (2003 [23], 2007 [24]).

Ряд статей, касающихся периодических систем, имеется у Рольски (Т. Rolski, 1986 [75], 1989 [76]). Интересны также результаты В. Ф. Матвеева и В. Г. Ушакова (1984 [30]) (приоритетные системы обслуживания), Асмуссена (S. Asmussen, 1991 [47]) (теоремы переноса), Чанга и Хао (С. Chang, X. Chao, 1991 [50]) (неравенства для дисперсии времени ожидания).

Заметим, что входные потоки в упомянутых работах относятся к классу регенерирующих, так что в диссертации исследуются системы обслуживания, обобщающие модели, изучаемые в последние годы (Е. Е. Ва-штова, 2004 [11], 2006 [12]).

В качестве базовой модели рассматриваются системы с возможностью неприсоединения к очереди. Заявка, поступающая в систему, в которой уже находятся j требований, присоединяется к очереди с вероятностью fj и уходит с вероятностью 1 — fj, fj? [0,1]. Такие системы относятся к классу систем с ограничениями, активно изучавшимся с середины прошлого века. Невозможно перечислить все результаты, касающиеся систем с различными ограничениями, поскольку интерес к моделям подобного рода до сих пор чрезвычайно высок. В работах Коэна (J. W. Cohen, 1968 [53]), О. М. Юркевича (1970 [41]), Е. В. Морозова (1977 [31]) были рассмотрены системы с ограничением на время ожидания. Системы с ограничением на время пребывания изучались в работах JI. Г Афанасьевой и А. В. Мартынова (1969 [10]), Н. Д. Шваба (1973 [38]). Впоследствии была предложена смешанная модель, учитывающая оба упомянутых типа ограничений (Б. В. Гнеденко, И. Н. Коваленко, [21, Глава 4,§ 7]). Отличительная черта ранее изучаемых систем состоит в том, что в них либо входной поток пуассоновский, либо время обслуживания имеет экспоненциальное распределение. В дополнение накладываются условия на сами ограничения, такие как экспоненциальное распределение величины, ограничивающей время ожидания (пребывания) (И. Н. Коваленко, 1960 [26], 1961 [27], [28]), монотонность последовательности вероятностей присоединения {fj} (В. Natvig, 1974 [72], V. Doom, 1981 [54]). Это позволяет использовать традиционные для теории массового обслуживания методы (вложенные цепи Маркова, введение дополнительных переменных) при получении стационарных характеристик таких систем. Например, в самых простейших предпосылках число требований в системе является процессом рождения и гибели, так что стационарное распределение находится по известным формулам (Т. JI. Са-ати [34]).

Можно выделить два типа систем с нетерпеливыми клиентами — системы с возможностью неприсоединения к очереди (Т. Homma, 1955 [63], F. A. Haight, 1957 [59], 1959 [60], 1960 [61], P. Finch, 1959 [55]) и системы с ограниченным временем ожидания (пребывания, смешанного типа) (Л. Г. Афанасьева, 1965 [2], JI. Г. Афанасьева, А. В. Мартынов, 1969 [10]). Во втором случае поступившее требование присоединяется к очереди, но находится в ней не более некоторого времени, после чего покидает систему, если его обслуживание ещё не началось.

Модели с возможностью неприсоединения к очереди можно рассматривать как модификацию систем с ограничением времени ожидания. Пусть требование имеет некий лимит времени. Придя в систему и застав в ней некоторое количество требований, оно оценивает шансы попасть на обслуживание раньше, чем этот лимит будет исчерпан. Затем оно либо покидает систему (с вероятностью, зависящей от длины очереди), либо остаётся в ней и ждёт обслуживания. С другой стороны, классическую систему с ограничением времени ожидания можно считать системой с возможностью неприсоединения к очереди, только факт присоединения к очереди зависит не от числа требований, а от процесса виртуального времени ожидания (Л. Г. Афанасьева, 1964 [1]). Оба описанных подхода широко используются на практике и на эту тему имеется значительное количество работ (М. Posner, 1973 [73]).

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

Имеется обширная литература, в которой доказываются предельные теоремы для стационарных и нестационарных характеристик систем, находящихся в условиях, близких к критическим. Первыми работами, по-свящёнными применению общих принципов теории случайных процессов к исследованию критических режимов систем обслуживания, были статьи Ю. В. Прохорова (1963 [32]), Ю. В. Прохорова и О. В. Вискова (1964 [33]), О. В. Вискова (1964 [20]). В несколько более ранних работах Кингмена (J. F. С. Kingman, 1962 [66]) и Райса (О. Rise, 1962 [74]) предельные теоремы доказывались посредством исследования аналитических выражений для характеристик систем обслуживания. В монографии А. А. Боровкова (1980 [16]) развита общая теория предельного поведения процессов массового обслуживания при слабых условиях относительно потока требований, длительности обслуживания и структуры самой системы. Доказаны предельные теоремы для систем с ожиданием и с потерями, в частности, при неограниченно увеличивающемся числе приборов и стремящейся к бесконечности интенсивности входного потока. Предельные процессы оказались весьма сложного характера, они сводятся к диффузионным процессам лишь в частных случаях.

В диссертации задача о высокой загрузке исследована в двух вариантах. В одной постановке рассматривается поведение предельного распределения нормированных процессов виртуального времени ожидания и количества требований в условиях высокой загрузки, а в другой — диффузионная аппроксимация данных процессов на конечном интервале. Доказательства опираются на общую теорему Боровкова (А. А. Боровков, 1980 [16, § 24]) и результаты, касающиеся диффузионной аппроксимации систем с неограниченным временем ожидания (JI. Г. Афанасьева, Е. Е. Ба-штова, 2009 [7]).

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

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

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

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

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

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

Получены необходимые и достаточные условия эргодичности случайного блуждания по целочисленной решётке действительной прямой с отражающей границей в нуле в случае, когда управляющая последовательность близка к периодической. На основе этих результатов найдены необходимые и достаточные условия эргодичности систем типа (7/|М|1 и М|(?/|1 с периодической последовательностью вероятностей присоединения. Данный случай рассмотрен отдельно, так как применение уже полученных выводов к системам с осциллирующей на бесконечности не приводит к точным ответам.

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

Результаты диссертации опубликованы в работах [13], [14], [45].

Содержание работы. Па протяжении всей работы основное внимание уделяется исследованию процессов виртуального времени ожидания (workload process) W (t) и количества требований Q (t) в системе S с возможностью неприсоединения к очереди. В главах 1 и 2 находятся условия существования у данных процессов собственного предельного распределения. В главе 3 исследуются поведения указанных процессов в ситуации высокой загрузки.

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

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

Основным результатом данной главы является теорема 1, устанавливающая достаточные условия эргодичности и стохастической неограни-• ченности для r-каналыгай системы обслуживания с вероятностями присоединения {fj} с регенерирующим входным потоком интенсивности Л и произвольным распределением времени обслуживания со средним Ь.

В качестве следствия получены достаточные условия эргодичности и стохастической неограниченности для системы с последовательностью вероятностей присоединения {/-}, имеющей предел / при j —" +оо. Установлено, что если ХЬ/ — г, то существуют примеры как эргодичных, так и неэргодичных систем. Критерий эргодичности для случая убывающей формулируется в виде теоремы 2. Доказано, что система с убывающей последовательностью вероятностей присоединения эргодична тогда и только тогда, когда ЛЬ/ < г. Данный результат существенно используется при рассмотрении ситуации высокой загрузки в третьей главе.

2. Во второй главе доказывается эргодическая теорема для случайного блуждания с отражением в нуле и управляющей последовательностью, которая в определённом смысле близка к периодической. Результаты, полученные в начале данной главы, применяются к анализу систем обслуживания с периодической последовательностью вероятностей присоединения. Доказано, что для систем С?/|М|1 и Ма1 условия эргодичности, вообще говоря, нельзя выразить лишь в терминах среднего времени обслуживания и интенсивности входного потока.

3. В третьей главе для систем с возможностью неприсоединения к очереди с регенерирующим входным потоком изучается поведение операционных характеристик (виртуальное время ожидания, число требований в системе) в ситуации высокой загрузки. Находятся условия сходимости стационарных распределений этих процессов к экспоненциальному. Доказательства опираются на построение мажорирующих процессов и результаты для систем без ограничений (А. А. Боровков [15]). Этот же подход позволяет установить при определённой нормировке С-сходимость на конечном интервале указанных процессов к диффузионному. Приводятся примеры, в которых при нарушении условий доказанных теорем имеет место сходимость к другим распределениям.

4. В приложении 1 приводится доказательство теоремы Блекуэлла для дрхскретных и непрерывных процессов восстановления в случае бесконечного математического ожидания интервалов между восстановлениями, поскольку в диссертации существенно используется данный случай, а в специальной литературе доказательство для него имеется лишь в схематическом виде (T. Lindvall, 1977 [69]).

5. В приложении 2 содержатся численные расчёты характеристик систем, рассмотренных во второй главе.

Обозначения и сокращения. Если не оговорено иначе, за исходное вероятностное пространство принято (Г2, JF", Р), и все случайные элементы предполагаются заданными на этом пространстве. Для случаев, рассмотренных в диссертации, доказательство существования единого вероятностного пространства для нескольких случайных элементов опирается на теорему Колмогорова (А. В. Булинский, А. Н. Ширяев, 2003 [19, Глава I]) и опускается в тексте диссертации в силу очевидности. Функции распределения случайных величин полагаются непрерывными справа, таким образом для случайной величины? её функция распределения равна F&) = Р (£ < ж).

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

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

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

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

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

Z+ = {0,1,2,.} — множество целых неотрицательных чисел. ij — символ Кронекера. т (Д) — наименьшая сигма-алгебра, порождённая системой множеств Л.

7(£а, а 6 X) — наименьшая сигма-алгебра, относительно которой измеримы все случайные элементы, а Е X. В этом случае говорят, что сигма-алгебра порождена случайными элементами a EX.

J-^xt = 0″ (X (s), 0 ^ s ^ t) — сигма-алгебра, порождённая случайным процессом {Х (в), 0 ^ й ^.

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

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

1, если х е АО, если х? А.

5.3. Выводы.

Как следует из таблиц, 7 для различных распределений отличается не слишком сильно (в сотых долях). Наибольшие различия в обеих таблицах наблюдаются между 7е, подсчитанных для экспоненциального распределения, и 7с, подсчитанных для константы. Максимальное различие в таблице 5.2: 7^(2- 1) — 7с (2- 1) = 0,0381- в таблице 5.3: ^(2,4) — 7с (2,4) = 0,0827.

Заметим, что при всех рассмотренных значениях параметров р и /1 соответствующие значения 7 больше в таблице 5.2.