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

Белорусов, Тимофей Николаевич

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

Белорусов, Тимофей Николаевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2011 ГОД ЗАЩИТЫ

01.01.05 КОД ВАК РФ

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

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

Московский Государственный Университет имени М. В. Ломоносова

механико-математический факультет

На правах рукописи 4В4ЭЭ3 1

Белорусов Тимофей Николаевич

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

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

Автореферат

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

1 2 МАИ 2011

Москва 2011

4845931

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

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

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

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

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

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

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

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

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

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

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

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

Общая характеристика работы

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

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

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

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

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

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

1 Rolski, Т., "Queues with nonstationary inputs". Queueing systems, 5, 1-3, 113-129 (1989). Asmussen, S., "Ladder heights and the Markov-modulated M\G\\ queue". Stochastic Processes and Their Applications, 37, 313-326 (1991).

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

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

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

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

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

Несмотря на достаточно долгую историю развития данного направления интерес к вопросам эргодичности велик и в настоящее время. Этой проблеме посвящены работы Г. Ш. Цициашвили, М. А. Осиповой 6, А. Mandelbaum, S. Zeltyn7, Л. Г. Афанасьевой 8.

Отличительная черта ранее изучаемых систем состоит в том, что в них либо входной поток пуассоновский, либо время обслуживания имеет экспо-

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

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

'Cohen, J. W., "Single server queue with uniformely bounded virtual waiting time". J. Appl. Probab. 5, 1, 93-122 (1968). Афанасьева, Л. Г., Мартынов, А. В., "Об эргодических свойствах систем массового обслуживания с ограничением". Теория вероятностей « её применения, 14,1,105-114 (1969).

'Цициашвили, Г. Ш., Осипова, М. А., "Предельные распределения в сетях массового обслуживания с непадежными элементами". Пробл. передачи информ., 44, 4, 109-119 (2008).

7Mandelbaum, A., Zeltyn S., "Staffing many-server queues with impatient customers: constraint satisfaction in call centers". Working Paper, Technion-Israel Institute of Technology (2007).

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

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

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

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

9Natvig, В., "On the transient state probabilities for a queueing model where potentia] customers are discouraged by queue lenght". J. Appl. Probah., 11,345-354 (1974); Doom, V., "The transient state probabilities for a queueing model where potential customers are discouraged by queue lenght". J. Appl. Probab., 18, 499-506 (1981).

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

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

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

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

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

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

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

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

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

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

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

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

— Для систем с возможностью неприсоединения к очереди с регенерирующим входным потоком и убывающей последовательностью {/_,} выведены условия сходимости стационарных распределений нормированных процессов виртуального времени ожидания и количества требований к экспоненциаль-

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

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

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

Теоретическая и практическая значимость.

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

Апробация работы.

Результаты диссертации докладывались в 2010 г. на Большом семинаре кафедры теории вероятностей механико-математического факультета МГУ им. М. В. Ломоносова под руководством член-корр. РАН, проф. А. Н. Ширяева, неоднократно на спецсеминаре кафедры теории вероятностей механико-математического факультета МГУ им. М. В. Ломоносова под руководством д.ф.-м.н., проф. Л. Г. Афанасьевой (2007-2011 гг.), на XVII Международной конференции студентов, аспирантов и молодых учёных "Ломоносов" (Москва, 2010 г.), на международной конференции по методам стохастического моделирования и анализа данных в г. Ханья (Греция, 2010 г.)

Публикации.

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

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

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

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

"Smith, W. L., 'Regenerative stochastic processes". Proc. Roy. Sac., A 232, &-31 (1935).

Краткое содержание работы

На протяжении всей работы основное внимание уделяется исследованию процесса виртуального времени ожидания (workload process) W(t) и процесса количества требований Q(t) в системе с возможностью неприсоединения к очереди. Заявка, поступающая в систему, в которой уже находятся j требований, присоединяется к очереди с вероятностью fj и уходит с вероятностью 1-/,,/;£ [ОД]-

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

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

h • = тк - Тк-ь 0о '•— то, хк(t,w) : = (X(u-i(uj)+t,u) - Х(гА_ьа;))/[0АМ](^, x0{t, w) : = X(t, u>)I[0Mu)\, (1)

Xfc(w) : = {xk(t,w),ek(ш)),

Cfc: = xk(0k).

Определение. Случайный поток {X(t),t > 0} называется регенерирующим, если существует неубывающая последовательность случайных величин {тк, к ^ 0}, такая что последовательность {xt, к ^ 1} состоит из независимых одинаково распределённых случайных элементов и не зависит от хо-

Предполагается, что Р(#о < оо) = 1 и существуют а := E£i < со, ¡j, := = E^i < оо. Вводится интенсивность потока Л limt-mx,-X"(i)/i = а/ц п.н.

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

15Кокс, Д., Смит, В., Теория восстановления. Изд-во "Советское радио 299 с. (1967)

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

Приводится подробное описание системы с возможностью неприсоединения к очереди. Для получения необходимых и достаточных условий эргодичности такой системы применяется метод мажорирования, который состоит в следующем. Пусть имеются две г-канальные системы S и S с вероятностями присоединения {fj} и соответственно, причём для некоторого к ^ О

j ■ _ jai, если j<k\ 3 1 «2, если j ^ к,

Процессы количества требований в системах S и S обозначаются Q(t) и Q(t) соответственно. Доказана следующая лемма.

Лемма. Пусть Q(0) = Q(0) = 0. Если fj fj при всех j > 0, то стохастически

Q(i) <Q(i)+r, i> 0. Если fj > fj при всех j ^ 0, то стохастически

Q{t) < Q{t) + r,t> 0.

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

г. Р(7„ < г0п) > 0, где п ^ 0, — суммарное время обслуживания требований, поступивших на n-м периоде регенерации входного потока. п. Распределение в\ имеет абсолютно непрерывную компоненту.

Теорема 1. Пусть fj > 0, j > 0, тогда система S эргодична, если

XbJ < г,

где / = limsupj^+oo/j. Система S неэргодична, если

Xbf > г,

где / = lim infj-++00 fj ■

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

Следствие 1. Пусть существует предел / = Мт_,_>+00/,-. Если АЬ/ < г, то система 5 эргодична. Если ЛЬ/ > г, то система 5 неэргодична.

Установлено, что если А6/ = г, то существуют примеры как эргодичных, так и не эргодичных систем в зависимости от последовательности {/¿}. В случае убывающей последовательности вероятностей присоединения справедливо следующие утверждение, которое используется в третьей главе при определении ситуации высокой загрузки.

Теорема 2. Если последовательность {/3} убывает, то условие

ЛЬ/ < г,

где / = Нт^_>+00 является необходимым и достаточным для эргодичности системы Б.

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

Рассматривается случайное блуждание по целочисленной решётке действительной прямой с отражающей границей в нуле {С3„, п > 0}, а именно

с начальным условием <?о. Относительно целочисленных неотрицательных случайных последовательностей {£„} и {г}п} предположим, что

Р(£п = Я = ^п-х) = Р(£п = 3 I <Эп = г) 9ч п.н., Р(% ~з\<Эп = г,^п-х) = Р(Пп = з\Яп = г) =: Лу п.н.,

где Тп = <г(£п, ??„,..., 6. <Зо), п^О, := о(<30). Доказывается, что С}п является цепью Маркова. __

Рассмотрим последовательность {(5п,п ^ а}, удовлетворяющую рекуррентным соотношениям

<Эп+1 = [Фп + Сп - 5?п]+ с начальным условием £)а. Предположим, что для {£„} и {т}п} выполнено

Р(Сп = 3 IЯп = г,Г)п,?п-\) = Р(Гп = з\Яп = г) 9ц п.н., Р(»7п -3 \<2п = ьЛ-0 = Р(т?п = з\Яп = г) =: Нц п.н..

где Тп := ff(f„, ..., £„, щ, Qa),n > o, .Fa-i := cr(Qa). Считаем, что производящие функции

+00

Gi(z) = Е(/» I Qn = i) = £ |z| < 1,

j=0 +00

Hi{z) = | Qn = t) = £ |z| < 1,

3=0

периодичны по г с периодом т, то есть G¿+m(¿) = G¿(z) и Я;+т(г) = для всех г ^ 0.

Строится вспомогательная цепь Маркова с конечным множеством состояний.

^ _ í I, если Qn = jm +1 > О, j ^ О, 1 ^ 1 ^ т;

" | не определено, если Qn = 0.

В силу сделанных в работе предположений Хп эргодична, а её стационарное распределение обозначим {яj, 1 < j < m}.

Теорема 3. Пусть для введённых выше цепей Маркова {Qn,n ^ 0} и {Qn, n ^ 0} выполнены условия

i- Iза - 9иI о, ^j\hi3 - Áy| о,»+оо. Р{£„ - = f | Qn = г} > О, Р{& - % = 11 Qn = ¿} > О, / = -1,0,1; г > О, n ^ 0.

3. Последовательности случайных величин {£п} и {т]п} являются равномерно интегрируемыми.

4. G'i{ 1) < +оо, H¡( 1) < +оо, 1 < i < т.

Тогда последовательность {Qn} эргодична, если

£(^(1)-дг(1))тт4<о. ¿=i

Если

т í=i

то

~ р

Qn—>-+00, 71 —+оо.

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

В качестве первого приложения теоремы рассматривается система обслуживания 5 типа а\М\1 с возможностью неприсоединения к очереди. Входной поток задаётся неубывающей последовательностью {ип,п ^ 1}, щ = 0. Интервалы между последовательными поступлениями требований ап = ип+1 — ип представляют собой независимые одинаково распределённые случайные величины с функцией распределения А{Ь) и средним а. Времена обслуживания {&„} — независимые случайные величины, имеющие показательное распределение с параметром ц. Последовательность вероятностей присоединения > 0}, € (0,1], имеет период т. Пусть (¿(^ — количество требований в системе в момент а <3П = (¿(ип — 0) — количество требований в системе в момент поступления п-го требования.

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

Теорема 4. Система 5 типа С/|М|1 с периодической последовательностью {/¿} эргодична, если

В качестве примера рассматривается случай т = 2.

Следствие 2. Пусть последовательность {/,} имеет период т — 2. Тогда процесс эргодичен, если

(2)

Если С > 0, то <5П —>■ +00, п +оо.

с =

(1-а*)(/1 + /а) + 4/1/аа'

2(1 - а* + (Л + /2)а*)

— ца < 0,

(3)

где а* :=/о+а0е-2^сМ(£).

Следующее уравнение соответствует неравенству (3)

а* (тРр ~р~2)х) = \ ~

-р-рх,

(4)

где х := /2//1, р '•= (ра)-1. В случае р < 1 система эргодична, поэтому далее рассматривается случай р > 1. Применяя теорему 4 и решая уравнение (4) относительно х, получим

Следствие 3. Пусть последовательность {/¿} имеет период тп = 2 и Л > Н> Р/г < 1 < р/ь Процесс (}({) эргодичен, если

где 7(р, Д) — положительный корень уравнения (4) относительно х.

В качестве второго приложения теоремы 3 рассматривается система обслуживания й типа М\а\1 с возможностью неприсоединения к очереди. Пуассоновский входной поток имеет интенсивность Л. Времена обслуживания {6П} ~ независимые одинаково распределённые случайные величины с функцией распределения В(Ь) и средним 6. Пусть тп — момент завершения п-го обслуживания требования, то = 0. Положим С}„ = С2(тп + 0), случайная величина равна количеству присоединившихся на интервале [г„, тп+1) требований. На данном интервале обслуживается ровно одно требование, поэтому т]п = 1 для любого га.

Теорема 5. Система Б типа М\а\1 с периодической последовательностью {/;} эргодична, если

В качестве примера рассматривается случай ш = 2.

Следствие 4. Пусть последовательность {/-,} имеет период т — 2. Тогда процесс эргодичен, если

Л < Л7(Р, Л).

(5)

с =

2ЛЬДЛ , (Д-Щх-У) Л + Л (Л + /2)2(1 + Ь*)

-1 <0,

(6)

где Ь* —

Следующее уравнение соответствует неравенству (6)

Ь'(х) =

2х - р^х - р!\х2

(рЛ-Цх' + р/!®-!'

где х := /2/Л, — /0°° ¿5(4), р := АЬ. В случае р < I си-

стема эргодична, поэтому далее рассматривается случай р > 1. Применяя теорему 5 и решая уравнение (7) относительно х, получим

Следствие 5. Пусть последовательность {/¿} имеет период т — 2, Л > /г, р/г < 1 < р/ь Процесс £){£) эргодичен, если

где 7(р/х) — положительный корень уравнения (7) относительно х.

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

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

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

Времена обслуживания {гц,з ^ 1} являются независимыми одинаково распределёнными случайными величинами с функцией распределения В(х) и конечными моментами Ь = Ег/;-, Ь2 Е 77?, а* := 62 - Ь2.

Поскольку для произвольной сходящейся последовательности $$ —/, 2 +оо условие р := АЬ < 1 не является, вообще говоря, необходимым

/2 < ЛТСРЛ)

а = Е&, р = Ебь А =

:= О := О ть ги := соу(&, п).

для эргодичности, рассматриваются системы с убывающей последователь-костью {/j} (см. теорему 2).

Пусть задано семейство {5£} систем обслуживания указанного типа с входным потоком Xe(t), определяемым соотношениями

Xe(t) = X(a,t), (8)

где

Пусть W£(i) и Qe{t) — процессы виртуального времени ожидания и количества требований для S€ соответственно. Пределы

£ Игп^ Р(We(t) <*) = Ф£(х) и ^m^ ?{QS) <х) = Fe(x)

существуют или не существуют одновременно.

Теорема 6. Пусть fj I f, j +оо, существует 6 > О, такое что

Е т2+5 < +оо, ЕС?"5 < +оо, Е ri+s < +оо

оо

!>-/)<+ 00. (Ю)

j=i

Тогда для системы с возможностью неприсоединения к очереди в асимптотике (8), (9) справедливы соотношения

2 ab 2 ab2

1-expj—J,-®}, e 0, -Pf(j)-> 1-exp|-^-z}, £-+0,

где

,2,2 2 aö2/„

о) = аа2п + а& (1 - /) + Ь2/а| + ^^ - (И)

/х /1

Для систем с нетерпеливыми клиентами на основании результатов третьей главы и теоремы 5 из работы Л. Г. Афанасьевой и Е. Е. Баштовой 16 вытекает следующее утверждение.

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

Теорема 7. Пусть выполнены условия теоремы 6 и We(Q) = 0. Тогда на каждом конечном интервале [0, и] для процесса \Уе{£) — еШ^/е2) имеет место С-сходимость к диффузионному процессу с отражением от нулевой границы и коэффициентами (—1,а^а/Ь), где а^ определяется (11).

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

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

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

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

lrLindvall, Т., "The probabilistic proof of Blackwell's renewal theorem". Ann. Probab., 5, 3, 482-485 (19T7).

Работы автора по теме диссертации

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

[2] Белорусов, Т. Н., "Случайные блуждания с периодической управляющей последовательностью и их приложения в теории очередей". Обозрение прикладной и промышленной математики, 17, 3, 149-158 (2010).

[3] Afanasyeva, L. G., Belorusov, Т. N., "Queueing systems in regenerative random environment". Book of Abstracts of Stochastic modeling techniques and data analysis international conference, 4-5 (2010).

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж (¿С экз. Заказ Кг

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Белорусов, Тимофей Николаевич

Введение

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

1.1 Определение регенерирующего случайного потока.

1.2 Свойства и примеры регенерирующих потоков.

1.2.1 Дважды стохастический пуассоновский поток (ДСПП)

1.2.2 Поток с интенсивностью случайной амплитуды

1.2.3 Поток со случайными периодами.

1.2.4 Поток потерянных требований.

1.2.5 Марковски-модулированный поток (ММП).

1.2.6 Поток Льюиса

1.2.7 Марковский поток поступлений (МПП).

1.2.8 Полумарковский поток (ПМП).

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

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

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

1.5.1 Формулировка теоремы 1.

1.5.2 Формулировки теорем Блекуэлла и Смита.

1.5.3 Доказательство теоремы 1.

1.6 Следствие и примеры.

1.7 Критерий эргодичности для систем с убывающей {/3}

Глава 2. Эргодическая теорема для систем с периодической последовательностью вероятностей присоединения

2.1 Описание случайного блуждания.

2.2 Формулировка и доказательство теоремы 3.

2.3 Система С/|М|1 с нетерпеливыми клиентами.

2.4 Система М|(2/|1 с нетерпеливыми клиентами.

Глава 3. Предельные теоремы для систем с нетерпеливыми клиентами в условиях высокой загрузки

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

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

3.3 Предельная теорема для систем с нетерпеливыми клиентами в условиях высокой загрузки.

3.4 Диффузионная аппроксимация на конечном интервале

3.5 Система М\М\1 с нетерпеливыми клиентами. Несколько примеров.

3.6 Выводы.

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

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

Диссертация посвящена исследованию систем массового обслуживания с нетерпеливыми клиентами (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]).

И наконец, потоки данного класса могут использоваться при построении математических моделей многих реальных объектов, поскольку интенсивность таких потоков может зависеть от времени и, более того, являться случайным процессом. Одна из первых работ, посвящённых системам с входным потоком непостоянной интенсивности принадлежит Кларку (А. В. Clarke, 1953 [52]). Затем Такач (L. Takacs, 1955 [78]) получил иптегро-дифференциальное уравнение для времени ожидания. Из результатов 70-х годов наибольший интерес представляют работы Б. В. Гнеденко и PI. П. Макарова (1971 [22]), где для анализа систем с отказами используются методы теории дифференциальных уравнений; Харрисона и Лемуана (J. М. Harrison, A. J. Lemoine, 1977 [62]), где даются условия существования предельного периодического режима в системе типа М(t)\G\l\oo] и Лемуана (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]) (неравенства для дисперсии времени ожидания).

В качестве базовой модели рассматриваются системы с возможностью неприсоединения к очереди. Заявка, поступающая в систему, в которой уже находятся 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]).

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

Имеется обширная литература, в которой доказываются предельные теоремы для стационарных и нестационарных характеристик систем, находящихся в условиях, близких к критическим. Первыми работами, по-свящёнными применению общих принципов теории случайных процессов к исследованию критических режимов систем обслуживания, были статьи Ю. В. Прохорова (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.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Белорусов, Тимофей Николаевич, Москва

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

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

3. Афанасьева, Л. Г., "О потоке потерянных требований в некоторых системах массового обслуживания с ограничением". Изв. АН СССР Техн. кибернетика, 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. Афанасьева, Л. Г., Булинская, Е. В., Случайные процессы в теории массового обслуживания и управления запасами. М.: Изд-во МГУ (1980).

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

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

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

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

13. Белорусов, Т. Н., "Случайные блуждания с периодической управляющей последовательностью и их приложения в теории очередей". Обозрение прикладной и промышленной математики, 17, 3, 149-158 (2010).

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

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

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

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

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

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

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

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

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

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

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

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

26. Коваленко, И. Н., "Исследование многолинейной системы обслуживания с очередью и ограниченным временем пребывания в системе". Укр. мат. ж., 12, 3, 471-476 (1960).

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

28. Коваленко, И. Н., О системе массового обслуживания с ограничением на время ожидания. Киев: Ин-т матматики АН УССР (1961).

29. Кокс, Д., Смит, В., Теория восстановления. Изд-во "Советское радио", 299 с. (1967)

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

31. Морозов, Е. В., "Исследование некоторых систем обслуживания с ограниченным ожиданием". Автоматизир. системы план, расчётов в рес-публ. план, органах, 9, 48-57 (1977).

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

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

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

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

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

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

38. Шваб, Н. Д., "Виртуальное время ожидания для систем с т-пребыванием". Математические модели сложных систем, 206-211 (1973).

39. Ширяев, А. Н., Вероятность-1. М.: МЦНМО, 520 с. (2004)

40. Ширяев, А. Н., Вероятность-2. М.: МЦНМО, 408 с. (2004)

41. Юркевич, О. М., "К исследованию многолинейных систем массового обслуживания с ограниченным временем ожидания". Изв. АН СССР Техн. кибернетика, 5, 50-58 (1970).

42. Цициашвили, Г. Ш., Осипова, М. А., "Предельные распределения в сетях массового обслуживания с ненадежными элементами". Пробл. передачи информ., 44, 4, 109-119 (2008).

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

44. Afanasyeva, L. G., Bashtova, E. E., Bulinskaya, E. V., "Limit theorems for semi-Markov queues", Proc. Ill Int. Sympos. on Semi-Markov Proc. Theory Appl, Cagliari, Italy, Electronic edition, 1-15 (2009).

45. Afanasyeva, L. G., Belorusov, T. N., "Queueing systems in regenerative random environment". Book of Abstracts of Stochastic modeling techniques and data analysis international conference, 4-5 (2010).

46. Asmussen, S., Applied probability and queues. J. Wiley and Sons, New York (1987).

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

48. Asmussen, S., "Semi-Markov queues with heavy tails". Semi-Markov Models and Applications, J. Janssen and N. Limnios, Kluwer, Dordrecht, 269-284 (1999).

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

50. 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).

51. Cinlar, E., Introduction to stochastic processes. Prentis-Hall, Englewood Cliff, New Jersey (1975).

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

53. Cohen, J. W., "Single server queue with uniforinely bounded virtual waiting time". J. Appl. Probab., 5, 1, 93-122 (1968).

54. Doorn, V., "The transient state probabilities for a queueing model where potential customers are discouraged by queue lenght". J. Appl. Probab., 18, 499-506 (1981).

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

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

57. Garnett, O., Mandelbaum, A., Reiman, M., "Designing a call center with impatient customers". Manufacturing and Service Operations Management, 4, 3, 208-227 (2002).

58. Grandell, J., Doubly Stochastic Poisson Processes. Springer-Verlag (1976).

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

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

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

62. Harrison, J. M., Lemoine, A. J., "Limit theorems for periodic queues". J. Appl. Prob., 14, 566-576 (1977).

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

64. Karlin, S., McGregor, J., "The classification of birth and death processes". Trans. Amer. Math. Soc., 86, 2, 366-400 (1957).

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

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

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

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

69. Lindvall, T., "The probabilistic proof of Blackwell's renewal theorem". Ann. Probab., 5, 3, 482-485 (1977).

70. 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).

71. Mandelbaum, A., Zeltyn S., "Staffing many-server queues with impatient customers: constraint satisfaction in call centers". Working Paper, Technion-Israel Institute of Technology (2007).

72. Natvig, B., "On the transient state probabilities for a queueing model where potential customers are discouraged by queue lenght". J. Appl. Probab., 11, 345-354 (1974).

73. Posner, M., "Single-server queues with service time dependent on waiting time". Operat. Res., 21, 610-616 (1973).

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

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

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

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

78. Takacs, L., "Investigation of waiting time problems by reduction to Markov processes". Acta Math. Acad. Sci. Hung., 6, 101-129 (1955).

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