Содержание к диссертации
Введение
1 Эргодическая теорема для системы обслуживания с ненадежным прибором 21
1.1 Определение и свойства регенерирующего случайного потока 21
1.2 Примеры регенерирующих потоков
1.2.1 Дважды стохастический пуассоновский поток (ДСПП) 27
1.2.2 Поток с интенсивностью случайной амплитуды 29
1.2.3 Поток со случайными периодами 29
1.2.4 Поток потерянных требований 30
1.2.5 Марковски-модулированный поток (ММП) 31
1.2.6 Поток Льюиса 32
1.2.7 Марковский поток поступлений (МПП) 33
1.2.8 Полумарковский поток (ПМП)
1.3 Описание модели и основные понятия 37
1.4 Условия стабильности и нестабильности 41
1.5 Примеры 45
2 Система M/G/1/oo с приоритетным обслуживанием и нена дежным прибором 53
2.1 Предыдущие результаты по теме 53
2.2 Вероятности больших уклонений 56
2.3 Описание модели M\ 60
2.4 Предельное распределение для числа требований в модели M\ 61
2.5 Описание модели M 65
2.6 Предельное распределение для числа требований в модели M 67
3 Вероятности больших уклонений для системы обслуживания с регенерирующим входящим потоком 73
3.1 Описание модели 73
3.2 Основные теоремы 75
3.3 Системы с независимыми временами обслуживания 81
3.4 Примеры 83
3.5 Заключение 88
Заключение 90
Литература 91
- Поток с интенсивностью случайной амплитуды
- Описание модели и основные понятия
- Предельное распределение для числа требований в модели M\
- Системы с независимыми временами обслуживания
Введение к работе
Актуальность темы.
Системы с прерываниями обслуживания изучаются довольно давно. Одной из первых работ по данной тематике является статья Н. White и L. Christie1 в которой рассмотрена система M/M/1/оо с ненадежным прибором, где времена ремонта и рабочего состояния прибора имеют экспоненциальные распределения с разными параметрами. Одной из наиболее частых причин прерывания обслуживания является поступление в систему требования с более высоким приоритетом, статья R. Miller2 посвящена такому виду прерывания. Отдельно стоит отметить работу D. Gaver3, где рассмотрена система M/G/1/oo, прибор в которой может ломаться только во время обслуживания требования, время рабочего состояния распределено экспоненциально, а время ремонта имеет произвольное распределение. В этой работе было введено понятие "полного времени обслуживания "(completion time), которое позволяет свести анализ системы с ненадежным прибором к классической системе M/G/1/oo. Также там было рассмотрено несколько вариантов обслуживания требования после прерывания. Практически аналогичная модель была рассмотрена в книге П.П. Бочарова и А.В. Печинкина4 с той разницей, что поломка прибора может происходить в любое время. Анализу подобных систем посвящено очень много работ, например, В. Doshi5, J. Keilson6. В обзорной статье A. Krishnamoorty и др.7 дано подробное описание имеющихся на данный момент в этом направлении результатов. Одной из последних работ является статья Л.Г. Афанасьевой и Е.Е. Баштовой8, где
1Н. White, L.S. Christie. (1958) Queuing with Preemptive Priorities or with Breakdown. Operations Research. Vol. 6, No. 1 pp. 79-95
2Miller Jr R.G. Priority queues. Ann. Math. Statist. 1960. 31, № 1. 86-103.
3Gaver D.P. (1962) A waiting line with interrupted service including priority. J Rl Stat Soc В 24:73-90
4П.П. Бочаров, А.В. Печинкин. (1995) Теория массового обслуживания. М. : Изд-во Рос. ун-та дружбы народов.
5Doshi В. Т. Queueing systems with vacations — a survey //Queueing systems. - 1986. - 1. - №1. - pp. 29-66.
6Keilson J. (1962) Queues subject to service interruptions. Ann Math Stat 33(4):13Ц-1322
7Krishnamoorthy A., Pramod P.K., Deepak T.G. (2009) On a queue with interruptions and repeat or resumption of service. Nonlinear Anal Theory Methods Appl 71(12):1673-1683
8 Afanaseva L. G., Bashtova E.E. Coupling method for asymptotic analysis of queues with regenerative input and unreliable server. — Queueing Systems, 2014, v. 76, №2, p. 125-147.
рассмотрена система Reg/G/1/oo с ненадежным прибором, времена восстановления и рабочего состояния которого независимы и произвольно распределены.
Определение условий эргодичности процессов, описывающих функционирование систем, является одной из первых задач, которые приходится решать при анализе систем обслуживания. Эти условия представляют собой соотношения между параметрами модели, при которых не образуется бесконечно больших очередей. Доказательства соответствующих теорем приводят к анализу достаточно сложных случайных процессов, вообще говоря, не марковских. Если же удается построить цепь Маркова, описывающую функционирование системы, то доказательства предельных теорем основываются на результатах для марковских процессов. Одними из первых работ в данном направлении являются статьи F. Foster9 и Д.Г. Кендалла10, в которых найдены достаточные условия существования стационарного распределения у цепей Маркова, связанных с очередью в системе. Монография А.А. Боров-кова11 посвящена анализу свойств эргодичности и устойчивости широкого класса случайных процессов (цепей Маркова, стохастически рекурсивных последовательностей и рекурсивных цепей и др.). Анализ систем обслуживания часто сводится к изучению марковских процессов с помощью введения дополнительной переменной. Этот метод использован, например, Б.А. Севастьяновым12 для исследования систем с отказами при произвольном распределении времени обслуживания, а также в И.Н. Коваленко13 для систем с ограничениями. Другой метод доказательства эргодических теорем состоит в построении процессов, стохастически монотонных по времени. В этом случае из монотонности следует существование предела последовательности функций распределения. Условия, при которых этот предел задает распределение вероятностей, могут быть получены с помощью метода, предложенного в R. Loynes14, (см., например, Л.Г. Афанасьева и А.В. Мартынов15).
Естественным и актуальным направлением развития теории является исследование моделей с входными потоками более общего вида. В настоящей работе представлены результаты для систем с регенерирующим входным
9Foster, F. G., "On the stochastic matrices associated with certain queuing processes". Ann. Math. Statist., 24, 2, 355-360 (1953).
10Кендалл, Д. Г./'Стохастические процессы, встречающиеся в теории очередей, и их анализ методом вложенных цепей Маркова". Математика, 3, 6, 97-111 (1959)
пБоровков, А. А., Эргодичность и устойчивость случайных процессов. М.: Едиториал УРСС, 440 с. (1999)
12Севастьянов, Б. А., "Эргодическая теорема для марковских процессов и её приложение к телефонным линиям с отказами". Теория вероятностей и её применения, 2, 1, 106-116 (1957).
13Коваленко, И. Н., "Некоторые задачи массового обслуживания с ограничением". Теория вероятностей и её применения, 6, 2, 222-228 (1961).
liLoynes R.M. The stability of a queue with non-independent inter-arrival and service times. — Proc. Cambridge Philos. Soc, 1962, v. 58, №3, p. 497-520.
15Афанасьева, Л. Г., Мартынов, А. В., "Об эргодических свойствах систем массового обслуживания с ограничением". Теория вероятностей и её применения, 14, 1, 105-114 (1969).
потоком и ненадежным прибором. Причем интервалы рабочего состояния прибора и ремонта определяются некоторым регенерирующим процессом, т.е. в нашей системе данные интервалы могут быть зависимыми, что является обобщением большинства систем с ненадежным прибором. Для такой модели найдено условие эргодичности процесса виртуального времени ожидания.
Если известно, что система стабильна и со временем очередь не растет до бесконечности, то возникает важная проблема связанная с оценкой вероятности образования сколь угодно большой очереди. То есть, если Ф(ж) — функция распределения остаточного времени ожидания в стационарном режиме, то нас интересует асимптотика функции 1 — Ф(ж) при х —> оо. Данному вопросу посвящено большое количество работ. В статье J. Abate и W. Whitt16 данная задача решена для системы M/G/1/oo с приоритетами, в случае "тяжелых хвостов"и "легких". Вариант легких хвостов для системы GI/G/1/oo был рассмотрен в работах P. Glynn и W. Whitt17, A. Ganesh и др.18. В статье Л.Г. Афанасьевой и Е.Е. Баштовой19 этот результат был обобщен на систему Reg/G/1/oo. В диссертации мы будем рассматривать только тяжелые хвосты. Как отмечено в S. Foss и др.20, распределения с тяжелыми хвостами играют существенную роль при моделировании коммуникационных сетей. В силу различия в запросах от разных групп потребителей, часть трафика касается малых объемов работы, но есть запросы весьма большого объема и это приводит к распределениям с тяжелыми хвостами.
Хорошо известно (см. D. Lindley21), что время ожидания начала обслуживания п-го требования (п = 1, 2,...) в система GI/G/1/oo определяется рекуррентным соотношением
wn+1 = max(0, wn + r)n- (п) = max(0, wn + un),
гДе "Цп ~ время обслуживания п-го требования, (п — интервал между моментами поступлений (п + 1)-го и п-го требований, ип = г]п — (п- Если {ип}=1 стационарная последовательность и W\ = 0, то по распределению
wn = max Sk}
16 J. Abate, W. Whitt. (1997) Asymptotics for M/G/l low-priority waiting time tail probabilities. Queueing
Systems, 25:173-233.
17 Glynn P. W., Whitt W. Logarithmic asymptotics for steadystate tail probabilities in a single-server queue.
— Journal of Applied Probability, Special edition, 1994, v. 31A, p. 131—156.
18Ganesh A., O'Connel N., Wischik D. Big Queues. Springer, Verlag Berlin Heidelberg, 2004.
19Л.Г. Афанасьева, Е.Е. Баштова. (2015) Вероятности больших уклонений для системы обслуживания с регенерирующим входящим потоком. Теория вероятностей и ее применения, 60(1):П1-177.
20Foss S., Konstantopoulos Т., Zachary S. Discrete and continuous time modulated random walks with heavy-tailed increments. — Journal of Theoretical Probability, 2007, v. 20, №3, p. 581-612.
21 Lindley D.V. The theory of queues with a single server. — Mathematical Proceedings of the Cambridge Philosophical Society, Cambridge University Press, 1952, v. 48, №2, p. 277-289.
где Sk = X^=i uj и 5*о = 0. Отсюда следует, что существует
F(x) = lim P(wn <ж) = Р ( supSn <ж) (1)
п^оо уте^0 у
и F(ie) — функция распределения, когда Еип < 0 (см. R. Loynes22).
Первые результаты были получены для систем с управляющей последовательностью {un}^=lJ состоящей из независимых одинаково распределенных случайных величин, на основе соотношения (1). Для регулярно меняющихся на +оо функций G(x) = J Р(ип > y)dy асимптотика
Р ( supS; > х ) - —^- (ж^оо) (2)
была установлена в работе J. Cohen23, а затем обобщена на более широкий класс функций (надстепенных) в статье А.А. Боровкова24. Для субэкспоненциальных функций G(x) асимптотика (2) доказана в V. Veraverbeke25. Дальнейшее развитие связано, с так называемыми, модулированными случайными блужданиями, для которых стационарная последовательность {мп}^1 состоит, вообще говоря, из зависимых случайных величин. Предполагается, что распределение приращения случайного блуждания ип = Sn — Sn-i определяется значением некоторого случайного процессаХп. Отметим несколько статей на эту тему. К. Arndt26 рассмотрел приращения с регулярно меняющимися хвостами, модулированные цепью Маркова с конечным множеством состояний. G. Alsmeyer и М. Sbignev27, а также P. Jelenkovic и A. Lazar28, исследовали распределение верхней грани случайного блуждания, модулированного цепью Маркова с конечным множеством состояний, но в предположении, что приращения ип имеют субэкспоненциальный интегральный хвост. В работе S. Asmussen29 рассмотрены случайные блуждания Y(t) регенерирующей структуры. В предположении, что распределение верхней грани приращения Y(t) на периоде регенерации асимптотически (при х —> оо)
22Loynes R.M. The stability of a queue with non-independent inter-arrival and service times. — Proc. Cambridge Philos. Soc, 1962, v. 58, №3, p. 497-520.
23 Cohen J. W. The single server queue. North Holland Publ. Co., Amsterdam, 1969, 657 p.
24Боровков А.А. О факторизационных тождествах и свойствах распределения супремума последовательных сумм. — Теория вероятн. и ее примен., 1970, т. 15, №3, с. 377-418.
25 Veraverbeke N. Asymptotic behaviour of Wiener-Hopf factors of a random walk. — Stochastic Processes
and their Applications, 1977, v. 5, №1, p. 27-37.
26 Arndt K. Asymptotic properties of the distribution of the supremum of a random walk on a Markov chain.
- Th. Prob. Appl., 1980, v. 25, p. 309-324.
27 Alsmeyer G., Sbignev M. On the tail behaviour of the supremum of a random walk defined on a Markov
chain. - Yokohama Math. J., 1999, v. 46, p. 139-159.
28 Jelenkovic P., Lazar A. Subexponential asymptotics of a Markovmodulated random walk with queueing
applications. — J. Appl. Prob., 1998, v. 25, p. 132—141.
29Asmussen, S., Semi-Markov queues with heavy tails. Semi-Markov Models and Applications, J. Janssen and N. Limnios, Kluwer, Dordrecht, 269-284 (1999).
эквивалентно распределению приращения за то же время, для случая субэкспоненциального интегрального хвоста получена асимптотика распределения верхней грани. Результаты применены к анализу системы обслуживания с полумарковским входящим потоком, для которой соответствующее случайное блуждание может рассматриваться как модулированное. В качестве модулирующей среды выступает полумарковский процесс. Установлены условия субэкспоненциальной асимптотики распределения процесса виртуального времени ожидания W(t) в стационарном режиме.
В диссертации найдена асимптотика больших уклонений процесса виртуального времени ожидания в стационарном режиме для системы с регенерирующим входящим потоком, в предположении, что суммарная работа, поступившая в систему за период регенерации, имеет субэкспоненциальный интегральный хвост. Данный результат распространен на вложенные процессы wn и Wn = W(6n), где вп — п-я точка регенерации входного потока. Мы также решили эту задачу в случае, когда прибор ненадежен.
Цель и задачи исследования.
Целью настоящей диссертационной работы являются:
нахождение условий стабильности для системы Reg/G/1/oo с ненадежным прибором, если функционирование прибора определяется регенерирующим процессом, который не зависит от входящего потока;
оценка вероятностей больших уклонений для функции распределения виртуального времени ожидания в стационарном режиме в случае "тя-желых"хвостов. Провести эту оценку для системы Reg/G/1/oo с надежным и ненадежным прибором;
нахождение явного распределения виртуального времени ожидания и количества требований в системе в стационарном режиме для системы M/G/1/oo с ненадежным прибором и наличием приоритетных требований.
Научная новизна.
Все результаты работы являются новыми. В диссертации получены следующие основные результаты.
-
Для системы обслуживания Reg/G/1/oo с ненадежным прибором, в которой процесс, описывающий моменты поломок и восстановления прибора, является регенерирующим, не зависящим от входного потока, установлены условия эргодичности.
-
Для системы обслуживания M/G/1/oo с ненадежным прибором и приоритетными требованиями получены условия эргодичности, найдены предельные распределения процессов виртуального времени ожидания
и числа требований в системе в терминах преобразования Лапласа-Стилтьеса, приведены выражения для важных операционных характеристик. Анализ проведен для двух дисциплин обслуживания требований после прерывания.
3. Найдена асимптотика вероятностей больших уклонений процесса виртуального времени ожидания для системы Reg/G/1/oo в предположении, что суммарное время обслуживания требований, поступивших в течение периода регенерации, имеет "тяжелый хвост". Аналогичный результат получен для системы Reg/G/1/oo с ненадежным прибором.
Методика исследования.
В диссертации используются различные методы и результаты теории вероятностей и теории случайных процессов: теоремы для стационарных процессов, теорема восстановления Блекуэлла, узловая теорема Смита, метод склеивания (coupling), теоремы о регенерирующих процессах, метод полного времени обслуживания.
Теоретическая и практическая значимость.
Диссертация носит теоретический характер. Её результаты могут найти применение в теории очередей, теории надежности, а также использоваться при исследовании телекоммуникационных систем.
Апробация работы.
По теме диссертации были сделаны доклады на следующих семинарах механико-математического факультета МГУ им. М. В. Ломоносова:
Большом семинаре кафедры теории вероятностей под руководством действительного члена РАН, профессора А.Н. Ширяева (2016 г.),
Семинаре «Исследование асимптотического поведения и устойчивости
стохастических моделей» под руководством проф. Л.Г. Афанасьевой,
проф. Е.В. Булинской, проф. Е.Б. Яровой (2013-2016 гг., неоднократ
но).
Результаты диссертации докладывались на:
Международной конференции "XXXII International Seminar on Stability Problems for Stochastic Models" в Норвегии (Тронхейм, 2014 г.);
Международной конференции "16th Applied Stochastic Models and Data Analysis International Conference (ASMDA2015)" в Греции (Пирей, 2015
г.);
Международной конференции студентов, аспирантов и молодых учё
ных «Ломоносов» в МГУ (Москва, 2013-2016 гг.);
Международной конференции по стохастическим методам (г. Новороссийск, пос. Абрау-Дюрсо, 2016 г.);
Международной конференции по исследованию операций (ORM2016) в России (Москва, 2016г.).
Публикации.
Основные результаты диссертации содержатся в работах [1-4]. Все четыре статьи опубликованы в журналах из перечня ВАК. Также результаты диссертации содержатся в трудах международных конференций [5-12].
Структура и объём работы.
Диссертация состоит из введения, трех глав, заключения и списка литературы из 85 наименований. Общий объем диссертации составляет 97 страниц.
Поток с интенсивностью случайной амплитуды
Случайные амплитуды возникают, когда известен общий закон изменения интенсивности входного потока в течение некоторого периода, но на амплитуду изменения оказывают влияние дополнительные случайные факторы. Строгое определение выглядит следующим образом. Пусть v(t) — периодическая интегрируемая неотрицательная функция с периодомТ, {г]п, п 0} — последовательность независимых одинаково распределенных случайных величин (г]п 0 п.н.). Случайную интенсивность ДСПП определим равенством Х(пТ + t,u) := v(t)rjn(uj), п 0. При таком определении величины г]п можно интерпретировать как случайные амплитуды, которые постоянны нап-м периоде. Моменты регенерации неслучайны и задаются последовательностью {пТ,п 0}, приращение ДСПП за
Пусть, как и раньше, v(t) — периодическая интегрируемая неотрицательная функция с периодом Т, {г)п,п 1} — последовательность независимых одинаково распределенных случайных величин (г]п 0 п.н.). Случайную интенсивность определим следующим образом где 7t недоскок процесса восстановления, образованного последовательностью {г)п,п 1}, до момента t. Моментами регенерации ДСПП являются моменты восстановлений процесса {Sn,n 0}, Sn = Y =i Ші приращение за п-й период регенерации равно JVn v( t) dt, интенсивность потока
Рассмотрим r-канальную систему, в которую поступает пуассоновский поток требований интенсивности А. Время обслуживания каждого требования имеет показательное распределение с параметром v. Заявка, поступающая в систему, в которой уже находятся j требований, присоединяется к очереди с вероятностью fj и теряется с вероятностью 1 — /j, fj Є [0,1]. Считаем, что fj = 1, 0 j г, то есть требование поступает на обслуживание с вероятностью 1, если есть свободный прибор. Пусть Q{t) — число требований в системе в момент t, a L{t) - число потерянных требований за [0, t]. Покажем, что L{t) является ДСПП со случайной интенсивностью А(1 — /g(t)).
Проверим определение 11. Зафиксируем траекториюQ(t}uJo) = Qo(t). Возьмём п непересекающихся полуинтервалов ($«,«], 1 і п. Без ограничения общности можно считать, что (si,ti\ — участки постоянства зафиксированной траектории Qo(t). Пусть длина интервала (SJ,J] равна Aj, a Qo(t) принимает на нём значение к{. Введём события
Моменты регенерации потока потерянных требований 0к = mf{tn, n l:tn вк-1, Q(tn) = 0}, 6 0 = 0, где tn — момент n-го скачка входного потока. С другой стороны, в работе Л. Г. Афанасвевой [2] (Афанасьева, 1966) показано, что в такой системе поток потерянных требований является полумарковским процессом. Таким образом, ДСПП в некоторых случаях является полумарковским процессом.
Если же fk = 0, к г, то согласно теореме Хинчина [26](Хинчин, 1963) поток потерянных требований образует процесс восстановления. Следовательно, в этом случае ДСПП будет являться процессом восстановления.
Эти потоки рассматривались в [31](Asmussen, 1991) и они образуют важный подкласс ДСПП. Пусть {Y(t),t 0} — эргодическая цепь Маркова с конечным или счётным множеством состояний, а {\к,\к С, к 1} — совокупность неотрицательных чисел.
Определение 12. ДСПП называется марковски-модулированным потоком (Markov-modulated flow) с управляющим процессом Y(t): если его случайная интенсивность имеет вид +оо \(t) = J2 kI{Y(t) = k}. k=1
Цепь Маркова Y{t) является регенерирующим процессом, а точки регенерации определяются моментами достижения некоторого фиксированного состояния, скажем состояния 1. Другими словами, если {tn,n 1} — последовательность моментов изменения состояний цепи Маркова Y(t), то 0k = mf{tn,n l:tn 0k.1Y(tn) = 1}, 00 = 0. (1.5) Из утверждений 1 и 2 следует, что X{t) также будет регенерирующим с моментами регенерации {вк}. Интенсивность потока +оо А = y Afc7rfc, (1.6) к=1 где {7Г/;} — стационарное распределение цепи Y(t). В силу сделанных предположений Л +оо. Среднее значение периода регенерации /І находится из соотношения 7Гі = («іЕт )-1, то есть [i = Етк = (аі7Гі)_1. (1.7)
Здесь (і\ — параметр экспоненциального распределения, задающего время пребывания управляющей цепи Маркова Y(t) в состоянии 1. Заметим также, что если Р(У(0) = 1) = 1, то {9k\ образует простой процесс восстановления, а если Р(У(0) = j) = 7Tj, j 0, то этот процесс стационарный. Среднее число требований, поступивших за период регенерации, определяется соотношением Е& = АЕт, = —. (1.8) Заметим, что потоки из разделов 1.2.2 и 1.2.3 не являются ММП. Потоки этого рода часто возникают в приложениях. Предположим, что в бес-консчноканальную систему S поступает регенерирующий поток с моментами регенерации {#n} Li- Времена обслуживания — независимые одинаково распределённые случайные величины. В течение времени пребывания в системе каждое требование независимо от других порождает пуассоновский поток интенсивности v. Суммарный поток, генерируемый требованиями, находящимися на обслуживании в S: называется потоком, Льюиса. Если Q{t) — процесс числа требований в системе S: то поток Льюиса является ДСПП со случайной интенсивностью X(t) = vQ(t). Точки регенерации потока Тк = Ы{вП1п 1:вп TA_i,Q(0n) = 0}, То = 0. Интенсивность A = z/EQ, (1.9) где Q — случайная величина, которая имеет распределение процесса Q{t) в стационарном режиме. Поток Льюиса, вообще говоря, не является ММП. Он будет таковым, если входной поток — пуассоновский, а времена обслуживания имеют показательное распределение. В качестве примера возможного приложения рассмотрим модель работы авиадиспетчера. Пусть Q{t) — число воздушных судов в зоне наблюдения. Времена обслуживания интерпретируются, как времена нахождения судна в этой зоне. Пребывая в зоне наблюдения, каждое воздушное судно посылает запросы авиадиспетчеру на обслуживание. Эти запросы образуют входной поток, который и будет потоком Льюиса.
Рассмотрим эргодическую цепь Маркова {Y(t),t 0}, принимающую значения в Z+ с непрерывными справа траекториями. Обозначим {tj,j 0}, to = 0, неубывающую последовательность моментов скачков процесса Y(t). Случайные величины У,- := Y(tj): j 0, образуют вложенную цепь Маркова с дискретным временем. Пусть N(t) := max{j 0: tj t]. На исходном вероятностном пространстве зададим семейство я := {{ },п Є Z;i, j 0} независимых последовательностей (при фиксированных i, j последовательность по п), состоящих из независимых одинаково распределенных случайных величин, принимающих значения в Z+. Математические ожидания равномерно ограничены Ея]- С +оо. Предполагается также, что семейство я не зависит от Y{t).
Описание модели и основные понятия
Приведем некоторые результаты из [18](Бочаров, Печинкин, 1995) и [47](Gaver, 1962), которые будут использованы в дальнейшем.
Одной из первых работ, где изучались системы типаМ/G/l/oo с выходами прибора из строя и последующими восстановлениями, является статья [47] (Gaver, 1962). В этой работе рассматривается вариант, когда поломка прибора может происходит только во время обслуживания требования. Можно сделать различные предположения о том, что происходит, когда прибор выходит из строя в процессе обслуживания требования. Выделили следующие две наиболее распространенные дисциплины (см. [47]): Dl (Preemptive-resume interruptions). Прерывание обслуживания интерпретируется как поломка прибора и, соответственно, имеет немедленный эффект. Прерванное обслуживание продолжается после восстановления прибора, причем время обслуживания требования после восстановления прибора совпадает с остаточным временем обслуживания этого требования в момент поломки. D2 (Preemptive-repeat-different interruptions). Обслуживание требования пре рывается немедленно, а время обслуживания требования после восстановления прибора имеет то же распределение, что и начальное время обслуживания, и не зависит от него.
Две эти дисциплины были введены в работе [47](Gaver, 1962), там же можно найти описание и других дисциплин обслуживания требования после поломки прибора. Также в [47] было введено понятие полного времени обслуживания (completion time).
Определение 17. Полное время обслуживания требования - это время, которое требование находится на приборе вне зависимости от того, исправен прибор или нет.
Приведем описание системы и некоторые результаты, полученные в [18, Глава 7] (Бочаров, Печинкин, 1995). В этой книге рассмотрена система, где предполагается, что прибор может выходить из строя не только во время обслуживания требования, но и когда требований в системе нет, что является обобщением системы из [47].
Рассматривается система массового обслуживания M/G/1/oo с ненадежным прибором. Вероятность выхода прибора из строя на интервале времени (t,t + А) зависит только от состояния системы в момент t и, если система в момент t свободна, то равна //А + о(А), а если на приборе находится требование, то равна цА + о(Д). Параметры // и /І — интенсивности отказов в свободном и занятом состояниях соответственно.
Если в момент отказа прибора система свободна, то прибор ремонтируется случайное время, имеющее функцию распределения G (x) с преобразованием Лапласа-Стилтьеса (ПЛС) ( (s) и средним д . При этом первое требование, поступившее в свободную систему в момент ремонта прибора, становится на прибор, но его обслуживание начинается только после окончания ремонта. Остальные поступающие требования скапливаются в очереди.
Если же в момент отказа прибора на нем находится требование, то обслуживание прекращается, а прибор ремонтируется случайное время с функцией распределения G(x), ПЛС ((s) и средним д. В течение этого времени требование продолжает находиться на приборе, причем после восстановления прибора требование дообслуживается остаточное время.
Время обслуживания требования имеет функцию распределения В (ж), математическое ожидание Ь и ПЛС /3(s).
Пусть a(s) и a (s) — ПЛС времени пребывания требования на приборе (полное время обслуживания), пришедшего в занятую систему и свободную соответственно. В [47] получены формулы, позволяющие выразитьa(s) через исходные данные для дисциплин D1 и D2 /3(s + /i-/i((s)), a(s Dl a(s D2 1 - C(s) (l - (3(s + ,,)) 2.i; 2.2 где Л — интенсивность поступления требований в систему. Формулу дляа (й] можно найти в [18], она имеет следующий вид a [s, А А + /І - ц С(\) + /І X-s a[s). 2.3) Зная a(s) и a (s), получаем соответствующие им математические ожидания: D1 D2 а а а -a,(0) = b(l+fig): м, м А + /І - ц ( (\) 1-С (А) А + а. 2.4) 2.5) 2.6) Введем процесс q{t) — число требований в системе в момент t. Для определенности будем считать, что в начальный момент 0 система свободна и прибор находится в исправном состоянии. Тогда q(0) = 0.
Пусть го = 0, а {тп} 1 — последовательность моментов ухода требований из системы. Так как после каждого ухода требования прибор обязательно находится в исправном состоянии, то {qn = q{rn + 0),n 0} — однородная цепь Маркова. Для этой цепи Маркова в [18] доказана следующая теорема. Теорема (Бочаров, Печинкин). Если р = Ха 1, то существуют предельные (стационарные) вероятности состояний рІ = lira P(qn = і), і = П—т 00 0,1,..., и для функции P(z) = Y iLoPiZ1 справедливо следующее соотношение: ґ . a(X — Xz) — za (X — Xz) P(z) = - — po, z a(X — Xz) где po = x_ Aa ; функции a(s) и a (s) определены формулами (2.1); (2.2) и 2.3); а и а — математические ожидания, определенные формулами (2.4); 2.5) и (2.6). Пусть W(t) — время, через которое после момента t прибор будет способен приступить к обслуживанию нового требования, т.е. он освободится от обслуживания всех требований, находившихся в системе в момент t, и будет в рабочем состоянии.
Если р = Ха 1, то существует lim P(W(t) х) = Ф(ж), где Ф(ж) — t— со функция распределения. Из [18, Глава 7] известно, что для функции w(s) = j0 е зхо!Ф(х) справедлива следующая формула = s + f-Ws) 1-р J s - X + Xa(s) 1 + /І # v 2.2 Вероятности больших уклонений В данном разделе мы оценим вероятность образования очень большой очереди для системы, описанной в разделе 2.1. Предполагаем, что обслуживание после поломки соответствует дисциплине D1. Задача больших уклонений с дисциплиной D2 будет рассмотрена как пример в следующей главе для более общей модели. Наша цель — исследовать асимптотику 1 — Ф(ж) при х — оо, в предположении, что время обслуживания и время ремонта имеют "тяжелые хвосты".
Предельное распределение для числа требований в модели M\
Рассматривается одноканальная система массового обслуживания с неограниченной очередью и регенерирующим входящим потоком X{t) (определение см. на стр. 22), определенным на вероятностном пространстве (Г2,#", P) с фильтрацией { tit 0}, к которой он адаптирован. Процесс X{t) имеет непрерывные справа неубывающие кусочно-постоянные траектории (Х(0) = 0).
Случайные величины 9j и Tj = 9j — 0j-\{j = 1,2,...) называются соответственно моментами и периодами регенерации. В теории очередей X{t) представляет собой либо суммарное время обслуживания требований, либо число требований, поступивших в систему за время (0,]. Здесь мы считаем, что X{t) — суммарное время обслуживания поступивших требований, и обозначаем 7п = Х{вп) — Х{вп-\) и п — число скачков X(t) на n-ом периоде регенерации. Если в систему поступает ординарный поток требований, то п — это число пришедших требований, а величина каждого скачка — время обслу живания. Ввиду того что X{t) регенерирующий поток, последовательности iri}? 25 {7j}? 2 и \Лз\ =2 состоят из независимых одинаково распределенных случайных величин. Предположим, что Е72 оо и Ет2 оо, и обозначим G(y) = Р(72 У), д(х) = Jx(l - G(y))dy, GT(x) = Я1 " G(y))dy. 1 о Введем процесс виртуального времени ожидания W(t): а также два вложенных процесса Wn = W(9n — 0) и wn = W(tn — 0). Здесь tn — момент n-го скачка процесса X{t). Для сходимости последовательности функций limn .00 P(wn х) = F(x) при п — оо достаточно потребовать выполнение условия апериодичности. Условие 6. Наибольшийобщий делитель {к : Р( 2 = к) 0} = 1. В работе [28] (Афанасьева, Баштова, 2014) даны достаточные условия, при которых существуют пределы Ф(х) = lim P(Wn ж), П—т 00 Ф(ж) = lim P(W(t) ж). t—7 00 Более того, Ф(ж), Ф(ж) и F(:r) являются функциями распределения тогда и только тогда, когда коэффициент загрузки Е72 1 р= — 1. Ег2 Далее везде предполагаем, что предельные распределения существуют ир 1.
Наша основная задача — найти асимптотическое поведение функцийФ(ж), Ф(ж) и F(:r) при х — оо. Будем считать, что случайный вектор (г, 7, ) имеет такое же распределение, как и вектор (т2,72, 2) Следуя [44](Фосс и др. 2011 ), дадим определения классов функций распределения. Определение 18. Функция распределения F(x) называется асимптотически локально постоянной (принадлежит классу ), если при х — оо F(x + y) F(x) для любого фиксированного у. Для краткости такие функции будем называть просто локально постоянными. Определение 19. Функция распределения F(x) неотрицательной случайной величины принадлежит классу 5? субэкспоненциальных, если lim F 2\x)/F{x) = 2, X—7 00 где F (x) = J0ooF(x- y)dF(y). Функция распределения F(x) = Р( х) на всей вещественной прямой называется субэкспоненциальной, если условное распределение Р( х\ 0) является субэкспоненциальным.
Известно [56](Kluppelberg, 1988), что любое субэкспоненциальное распределение является локально постоянным, т.е. 5? С «5?. В свою очередь, любое локально постоянное распределение имеет тяжелый хвост. Напомним, что случайная величина имеет распределение с тяжелым хвостом, если Ееє = оо для всех є 0.
Определение 20. Функция распределения F(x) принадлежит классу У сильно субэкспоненциальных, если х F{x — y)F{y)dy 2mF(x), . где т = J0 F(y)dy. Отметим, что одно из ключевых свойств сильно субэкспоненциального распределения является то, что само это распределение является субэкспоненциальным (т.е. У С У) и его интегральный хвост принадлежит классу 5? [56](Kluppelberg, 1988). 3.2 Основные теоремы Далее, мы рассматриваем одноканальную систему обслуживания с регенерирующим входящим потоком X(t). Теорема 3. Пусть GT(x) Є 6? и при у — оо Р{ч у + т) 0(у). (3.1) Тогда при х — оо Ф(х) а_1 (ж), (3.2) где а = Ет — Е7. Доказательство. Из соотношения (3.1) следует, что интегральные хвосты оо _ оо g(x) = J G(y)dy и J Р(7 т + y)dy асимптотически эквивалентны (см., например, следствие 3.26 из [44](Фосс и др. 2011)). Для доказательства (3.2) надо установить, что для любого є 0 найдется достаточно большое х такое, что для всех х х (1 - е)д(х)а 1 Ф(х) (1 + є)д{х)а 1. (3.3) Оценка снизу. Введем вспомогательный процесс Wn с помощью рекуррентного соотношения ИС = [ИС-і+7п-тп] + , W0 = 0 где [х}+ = тах(ж,0). Очевидно, что если Wo = 0 с вероятностью 1, то при всех п = 1,2,... справедливо неравенство W Wn. Обозначим Ф (х) = limn .oo Р(И/„ х). Из [71](Veraverbeke, 1977) известно, что если функция f Р(7 у + т)(іу субэкспоненциальна, то при х — оо имеет место асимптотика
Для доказательства теоремы нам понадобится вспомогательная система ST, которая зависит от параметра Т. Периоды регенерации {TJ} CL1 входящего потока Хт{р) определяются соотношением rj = min(rn,T), а моменты регенерации QTn = YTj=i TJі @о = 0- При этом, если тп Т, то Хт{Ь) на своем п-ом периоде регенерации совпадает cX(t), то есть Ху( _1+/:) = X{9n-\+i) для t Є (0, тп]. Если же тп Т, то Ху() до момента Т копирует процесс X(t), а все требования, что придут в основную систему за время (9п-\ + Т, #п], поступят в в момент 0п-\ + Т. Таким образом, для любого t Т имеем Хт{вІ_х + t) = Х(вп-і + t), а при t = T получаем Хт(вІ_1 + Т) = Хт(0%) Х{вп). Выразим вышесказанное формулой
Системы с независимыми временами обслуживания
Времена обслуживания требований описываются последовательностью случайных величин {?7n} Li, которые независимы, имеют общую функцию распределения В(х)} среднее 6, В(х) = 1 — В(х). Последовательность {?7n} Li не зависит от процесса A(t).
Пусть \(t, w) — регенерирующий процесс с точками регенерации {вп}{$о = 0), тп = 6п — Вп-\ — длина n-го периода регенерации, Ет оо. Тогда A(t) регенерирующий поток с теми же точками регенерации {#n} Ll, п = А{9п — 0) — А{6п-\) — количество требований, поступивших за n-ый период регенерации. Положим Hindoo Y = ЁТ = А. Выпишем функцию распределения случайной величины РК=n) = Еш:е-АМ. Полагаем, что коэффициент загрузки р = ХЬ 1. Функции Ф(ж), Ф(ж) и F(x) имеют тот же смысл, что и в предыдущих разделах. Следствие 12. Пусть В(х) Є У и 1) X(t,w) X оо с вероятностью 1; 2) существует число с Ь такое, что Р(т х/сХе2 ) = о(В(х)) при х — оо. Тогда для функций Ф(ж), Ф(ж), F(IE) им,еет м,есто (3.10). Доказательство. Как и ранее, введем случайную величину такую, что Р( = ) = Ё ( = ) Для всех = {1? 2,... }. В силу пункта (гг) теоремы 5, нам достаточно показать, что Р(с х) = о(В(х)). Имеем Г (\ii)k Р(С х/с) / rV Р(г !/) = / ж/(сАе2) / оо / + / = Ji(z) + J2(z). JO Jx/(c\e2) Очевидно, что (ж) Р(г х/(сХе2)) = о{В(х)) в силу условия 2). Перейдем к оценке J\(x) /г=[ж/с]+1 Sfe_Sm(l) = Aro(i)P(C (a:)), где т(х) = - + 1, к(х) = [ж/с], а ( имеет пуассоновское распределение с параметром Хт(х). Пусть {C«} i последовательность независимых одинаково распределенных случайных величин, имеющих пуассоновское распределение с параметром Л. Тогда Р(С к(х)) = P(Ci + + Cm(x) к(х)) = Р( Ci -I 1- Cm(x) &(жі mm m ж Применим лемму 1.2 из [46](Ganesh et. al. 2004), в которой утверждается, что для последовательности независимых одинаково распределенных случайных величин {C«} i при любых х и п выполнено неравенство — In Р ( х ) — sup(s:c — (p(s))} (3.16) где ip(s) = lnEe 1. В нашем случае ip(s) = X(es — 1). Несложно установить, что sup(s:c — (p(s)) = х(\п(х/Х) — 1) + Л. s Далее, из (3.16) получаем П х ) ехр(—п(х(\п(х/Х) — 1) — Л)). Теперь применим этот результат к нашей ситуации. Подставив вместоп :-т(х) и х := к(х)/т(х), находим т(х)Х, P Л1 + + ") Ш exp ( -ОД fin f- l") - 1V Ат(ЖЛ V т(ж) т(ж) / V V ч л к{х) Учитывая, что т(х) больших ж, имеем сАе2 + 1 (1+( )у2 при любом 6 0 и достаточно ехр ( v 7 ( ( т(х)Х. ln(l+J) Таким образом, вероятность P( &(ж)) асимптотически убывает быстрее чем некоторая экспоненциальная функция, так что J1{x) = о{В{х)) и мы можем применить теорему 5.
Если входящий поток является марковски модулированным и управляющий процесс имеет конечное число состояний, то можно не накладывать условия на интенсивность и на распределение длины периода регенерации, так как эти условия автоматически выполняются. Нужно лишь потребовать сильную субэкспоненциальность функции распределения времени обслуживания.
Пример 8 (Система с марковски модулированным полумарковским входящим потоком). Здесь рассмотрим систему с марковски модулированным полумарковским входящим потоком (см., например, [29](Афанасьева и др. 2012)). Это ДСПП со случайной интенсивностью N \{t)w) = YJ {U{t) г=1 где ХІ 0, і = 1,...,7V, a U{t) — полумарковский процесс. Он задается матрицей переходных вероятностей Р = {Piji i,j = 1, V} и матрицей {Cij, i,j = 1,N} функций распределений времен пребывания в состояний і при условии, что следующим состоянием будет j(i,j = 1, V). Если Р — эргодическая матрица, то процесс U{t) имеет предельное распределение N ТГІ = lim P(U(t) = і), а его интенсивность Л = 2 ХІПІ. Времена обслужива ния требований {т]п} =1 не зависят от входного потока и В(х) = Р(т]п %). В предположении, что В{х) Є S из следствия 12 несложно получить условие субэкспоненциальности функции Ф(ж). Положим С(ж) = min Су(ж).
Так как Р — эргодическая матрица, то для некоторого 1 m оо имеем Pij(m) 0 для всех i,j = 1,7V. Здесь {Р -(т)} = Рт. Не ограничивая общности, считаем m = 1. В качестве моментов регенерации входного потока рассмотрим моменты попадания управляющего полумарковского процесса U{t) в некоторое фиксированное состояние, скажем, в первое. Тогда число переходов /І процесса U{t) до возвращения в {1} оценивается геометрически распределенной случайной величиной с параметром а = miiijj Р . Период регенерации г стохастически удовлетворяет неравенству где {Cjljl1 независимые одинаково распределенные случайные величины с функцией распределения С(х)7 которые не зависят от /І. Если С(х) имеет легкий хвост, то (3.10) имеет место. Если С(х) субэкспоненциальна, то в силу Р(т х) Р(С1 + + См х) оТ ж), для (3.10) надо С(х/с\е2) = о(В(х)) (3.17) для некоторого О Ь. Таким образом, получено Следствие 13. Для системы с марковски модулированным полумарковским входящим потоком в предположениях (3.17) и В(х) Є У для функций Ф(ж), Ф(х) и F(x) имеет место (3.10).
Замечание 5. Утверждение следствия 13 остается верным, если в моменты изменения состояния управляющего полумарковского процесса в систему поступают требования. Это почти очевидно, поскольку число таких требований на периоде регенерации оценивается сверху геометрически распределенной случайной величиной. 3.5 Заключение Здесь мы обсудим влияние структуры входящего регенерирующего потока на асимптотическое поведение стационарного распределения Ф (х) виртуального времени ожидания. Рассмотрим систему с временами обслуживания, не зависящими от входного потока. В случае легкого хвоста распределения В(х) в [7] (Афанасьева, Баштова, 2015) установлено, что Піп — 1пФ(ж) = —q, где q — единственное положительное решение уравнения U(b(-qU) = l, где b(s) = Ee sri, U(z,s) = Ez e ST, a 77, т, соответственно время обслуживания, длина периода регенерации входного потока, число требований, поступивших за этот период. Мы видим, что асимптотическое поведение Ф(ж) определяется совместным распределением и г и не зависит от того, как требования поступают в систему в течение периода регенерации. Ещё меньше асимптотика Ф(ж) зависит от структуры входного потока в условиях теоремы 5, где она полностью определяется интенсивностью входного потока и интегральным хвостом функции распределения В(х). Это происходит из-за предположения, что распределение имеет более легкий хвост, чем распределение времени обслуживания. Если это не так, то, по-видимому, распределение будет играть существенную роль. Продемонстрируем это следующим примером. Предположим, что длина периода регенерации имеет конечный носитель, то есть Р(т Т) = 1 для некоторого Т оо, а функция распределения С{х) = Р( х) регулярно меняющаяся. Как показано в [39](Денисов и др. 2010), если В{х) = 0(С(х)), то при х