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

гч

Нз' МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.Ломоносова ^ Механико-математический факультет

ЧГ

На правах рукописи УДК 519.2, 519.872

Лебедев Алексей Викторович Экстремумы некоторых процессов массового обслуживания 01.01.05 — "Теория вероятностей и математическая статистика"

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1997

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

Научный руководитель: кандидат физико-математических наук

доцент Е.В.Булинская.

Официальные оппоненты: доктор физико-математических наук

профессор А.В.Печинкин, доктор физико-математических наук профессор В.В.Рыков.

Ведущая организация: Московский Государственный

Институт Электроники и Математики (технический университет)

Защита диссертации состоится 1997 года

в 16 часов 05 минут на заседании диссертационного совета Д.053.05.04 при Московском Государственном Университете имени М.В.Ломоносова по адресу: 119899, ГСП, Москва, Воробьевы горы, МГУ, механико-математический факультет, аудитория 16-24.

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

Автореферат разослан

1997 года.

Ученый секретарь диссертационного совета Д.053.05.04 при МГУ

профессор Т.П.Лукашенко

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

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

Основополагающей d теории экстремумов является работа Гне-денко (1943), посвященная максимумам независимых одинаково распределенных случайных величин (н.о.р.с.в)). Итоги развития теории экстремумов за несколько десятилетий подведены в монографиях Лидбеттера и др. (1989) и Галамбоша (1984), а также обзоре Галам-боша "О развитии математической теории экстремумов за последние полвека" (1994).

Изучение максимумов случайных процессов общего вида представляет собой практически неразрешимую задачу. Однако она существенно упрощается, когда речь идет о различных процессах массового обслуживания. Коэн (1967) нашел распределение максимума числа заявок на периоде занятости в системах М|С?|1 и G\M\1. Наиболее простым результат оказался для системы М\М\1. На этом примере Андерсон (1970) продемонстрировал применение своих теорем о максимумах случайных величин с дискретным распределением, получив стохастические оценки для максимума числа заявок. Хейде (1971) исследовал максимум длины очереди в системе G\M\\. В монографии Коэна (1982) доказаны теоремы о максимумах числа заявок, виртуального и актуального времени ожидания в системах M\G\l и G\M\l. Более общую задачу решил Иглехарт (1972), исследуя систему GjG|l. В целом вопрос о максимумах процессов обслуживания в однолинейных системах представляется достаточно изученным — в отличие от случая нескольких или бесконечного числа приборов (как в настоящей работе).

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

К сожалению, система M\G\oo и ее различные обобщения, по-видимому, традиционно считались менее заслуживающими внимания, чем системы с конечным числом приборов. Правда, в последние годы наблюдается некоторый интерес к системам M'Y|G|co с неод-

нородными заявками (Конг, 1994) и зависимыми временами обслуживания (Фалин, 1994) .

Справедливости ради следует отметить, что обобщения системы М|С|оо имеют самые разнообразные приложения как в сфере массового обслуживания, так и за ее пределами. Речь, в частности, может идти о моделях телефонной сети (Андронов, 1972), стоянки автомобилей (Фрейер, 1974), дорожного движения (Браун, 1969), систем самообслуживания и выплаты компенсаций (Холман и др., 1983), медицинского обслуживания (Коллингс и Стоунман, 1976), систем с разделением времени (Веретенников, 1977), информационной сети (Андронов, 1994) и др. Следует отметить также возможные интерпретации в терминах теории надежности и теории страхования.

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

Естественным обобщением процессов обслуживания в бесконечно-линейных системах оказываются процессы, являющиеся также обобщением так называемых процессов дробового шума. Экстремумы некоторых видов процессов дробового шума изучались, в частности, в работах Хсинга и Тойгельса (1989), Доуни и О'Брайена (1991), Хом-бла и Маккормика (1995). Был получен ряд предельных теорем для максимумов дробового шума, однако мультипликативный вид слагаемых, а также условия, накладываемые на функции отклика и распределения амплитуд, представляются весьма специфическими. В настоящей работе рассматривается более широкий класс процессов (обобщенного) дробового шума.

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

зуется метод диффузионной аппроксимации, весьма популярный в последнее время.

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

Научная новизна, теоретическая и практическая значимость работы. В работе получены следующие (новые) теоретические результаты:

- получена асимптотика почти наверное для максимумов числа заявок как в системах МХ\С\со с ограниченным размером групп, так и для широкого класса систем этого типа с неограниченным размером групп;

- изучено поведение максимумов в системах типа А/|С|со с параметрами, зависящими от времени или от состояния системы;

- доказаны теоремы монотонности для некоторых обобщений М*|С|оо;

- разработаны методы двустороннего оценивания максимумов для некоторого класса процессов обобщенного дробового шума, с помощью которых получена асимптотика максимума объема работы в системе М|С|оо;

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

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

Работа выполнена в соответствии с планом научных исследований на кафедре теории вероятностей механико-математического факультета МГУ (при поддержке Российского Фонда Фундаментальных Исследований по гранту 96-01-01092).

Апробация работы. Результаты диссертации докладывались на XVII и XIX Конференциях молодых ученых механико-математического факультета МГУ (Москва/1995, 1997), XXVI Всепольской конференции по приложениям математики (Закопане-Кощчелнско, 1997), на семинарах кафедры теории вероятностен.

з

Публикации. Основные результаты диссертации опубликованы в [1Н4].

Структура и объем работы. Общий объем диссертации составляет машинописные страницы. Работа состоит из введения, трех глав, приложения и списка литературы, содержащего 54 наименования.

2. Содержание работы

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

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

В главе 1 изучается асимптотика максимального числа заявок M(t) на отрезке [0,£] при t оо в различных бесконечнолинейных системах. В §1.1 дан основной математический аппарат, используемый далее в главе 1 и отчасти — в главе 2. В §1.2 рассматриваются системы типа Mx\G\oo с ограниченным размером групп.

Теорема 1.2.1. Если L — максимально возможное число заявок в группе, то п.н.

In Inf

Mit)—--> L, t -> oo.

ln£

В §1.3 рассматриваются системы типа Mx\G\oo с неограниченным размером групп. Распределение числа заявок в группе обозначается через А; А(к) = 1 — А(к). По теореме 1.3.2, если - InÄ(k) ~ /(£), к со, где непрерывная возрастающая функция / удовлетворяет некоторым специальным условиям (в частности, полуаддитивности), то п.н.

М-,!, t-oo.

In t

Приведено несколько примеров (геометрический хвост, хвост распределения Вейбула, логнормальный и степенной хвосты распределения А).

Для случая, когда А имеет правильно меняющийся хвост, т.е. А(к) ~ k~bL{k), к —> оо, где 6 > 1 и L{x) — медленно меняющаяся функция, получен более точный результат. По теореме 1.З.З., если взять числовую последовательность {мп} такую, что nÄ(u„) -» 1, п со (пусть, например, ип = inf{fc : Ä(k) < 1 /гг}), то

Р(МШ <х)-> ехр{-аГ*}, t оо, х > О,

U[Ai]

где А — интенсивность входного потока.

В §1.4 рассматривается система А/|С?|оо с нестационарными характеристиками (интенсивность входного потока зависит от времени и распределение времени обслуживания — от момента поступления заявки). Доказаны теоремы, описывающие асимптотику максимумов независимых случайных величин Х„, распределенных по пуассоновскому закону с параметрами \„,п > 1. В зависимости от класса последовательности {А,,} асимптотика оказывается различной. Полученные результаты делают возможным исследование асимптотики M(í) при помощи оценок максимумов на отрезках элементами пуассоновских последовательностей.

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

Теорема 1.4.4. Пусть Л(£) не убывает при достаточно больших t

A(í) A (t + c) л w

-¿i-, оо, '

тогда

limsup -гтЧ^ = ß п.н. Í—юо A(ÍJ

В §1.5 доказаны теоремы монотонности для некоторых обобщений M'v|G|oo (с зависимостью параметров от времени и неоднородными заявками). Показано, что как число заявок, так и его максимум являются монотонно возрастающими характеристиками параметров системы относительно некоторых отношений порядка.

В §1.6 рассмотрена система M\G\oo с интенсивностью входного потока, зависящей от состояния. Предполагается, что если в системе находится к заявок, то интенсивность равна At > 0. Поведение системы зависит от параметра г = /3 lim sup А ¡¡¡к, где ß — среднее

k—юэ

время обслуживания. Условие эргодичности может быть записано как г < 1.

Следствие 1.6.1. Если 0 < г < 1 и в = 1 /г, то п.н.

limsup < 1.

i-foo logn t

Следствие 1.6.2. Если г = 0 и At = 0(ка),к -> оо,а < 1, то п.н.

M^lnlni

limsup 1 - а)—-< 1.

t—Юо In t

Получены также оценки по вероятности. Определена числовая последовательность {Ь„,п > 1} такая, что верно следующее утверждение.

Теорема 1.6.4.

lim ínf PÍM(í) < 6[(1 + m)> exp{-rm/Tñ}, m > 0, 0 < r < 1,

í—>oo

¡где TR —средний период регенерации.

В §1.7 рассматриваются системы МЛ|С|оо с большими группами. Предполагается, что ф.р. AN размера групп удовлетворяет условию AN{Nx) —> A#{x),N оо в точках непрерывности причем А#(0) = 0. Соответственно нормируем процесс числа заявок: QN{t)=Q(t)/N.

Теорема 1.7.1. Q^ S- при N -> оо на любом отрезке [0, í]. Здесь через Д~ обозначена D-сходимость.

Следствие 1.7.1. Пусть MN{t) = sup{QN(u) : и € [0,í]} и M*(t) = sup{Q#(u) : и G [0,f]}, тогда MN{t) 4 M*(t) для любого t > 0.

В главе 2 рассматриваются процессы обобщенного дробового шума согласно следующему определению.

Определение 2.1. Процесс t] называется процессом типа (*), если он представим в виде

оо

v{t) = teR+

к=1

где Tt,k > 1 образуют пуассоновский поток на R+ (интенсивности A), a £k{t),k >1 — независимые случайные процессы с одинаковыми конечномерными распределениями (не зависящие от {Тк, к > 1}), удовлетворяющие условиям:

1. &(t) =0 при t < 0,

2. &(t) > 0 при t > О,

3. £t(í) не возрастает при t > 0 п.н.,

4. Jü+coM^k{t)dt < оо.

В §2.1 приведены соответствующие примеры из теории массового обслуживания и изложен основной математический аппарат. В частности, получены различные двусторонние оценки, позволяющие исследовать асимптотику бегущего максимума M(t) процесса типа (*) на отрезке [0,í] при t оо.

В §2.2 доказаны теоремы об асимптотике, обобщающие соответствующие теоремы §1.2-3.

В §2.3-4 демонстрируется применение методов §2.1 для изучения асимптотики максимумов объема работы в системах М\М\со н iVí|G|oo. Под объемом работы понимается сумма остатков времен

обслуживания всех заявок, находящихся в системе. Распределение времени обслуживания обозначается через В.

Теорема 2.3.1. Для системы М\М\оо с В(х) = 1 - е~ах и интенсивностью входного потока А верно

,. Mit) - a-1 Ini 0 (Т

hm — .—--= 2\ п.н.

s vin t N as

Для В, представляющих собой смесь распределений с главной показательной компонентой, т.е. В(х) = qe~az 4- (1 - q)G(x), q G (0,1), G(x) = o(e~ax), x -> со также имеет место аналогичный предел

,. Mit) -a~l In i n

lim-7=-= 2»

v/lnf *

AÎ

, П.Н.

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

Для максимума объема работы в системе М\М\оо в §2.4 получены стохастические оценки. Далее обозначаем р = А/а.

Теорема 2.4.1. МИР(М(<) < ыр + х) > ехр{-е~а1}, где

Щ

u = -(lni + 2\/^hïf - ilnlni + ln^

,3/4

пР

а \ v 4 2л/7Г

Теорема 2.4.2. limsupP(M(f) < uf + x) < ехр{-е~аг}, где

I-4CO

Л/4

и} = - 11п« + 2у/рШ - ? 1п 1п I - 1п 1п v/hГг + 1п

а [ 4 2л/7г

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

В §3.1 дается определение и доказываются некоторые леммы. Определение 3.1. Процесс т] называется процессом типа (**), если он представим в виде

со

»7(0 = Е&е-Зк), teR+

где > 1 образуют пуассоновский поток на (интенсивности А), а >1 — независимые случайные процессы с одинаковыми

конечномерными распределениями (не зависящие от {Т^, к > 1}), удовлетворяющие условиям: 1. = 0 при I < 0,

2. не убывает при t > 0 п.н.,

3. M$k(t) fi € (О, оо) при t сю,

4. M£*(f)2 ст2 € (О,оо) при £ —> оо.

Лемма 3.1.1. Пусть процесс £ удовлетворяет условиям 1-4, тогда

а) £ представляет собой неотрицательный равномерно интегрируемый субмартингал без разрывов 2-го рода;

б) существует случайная величина £ такая, что

£(t)/* f П.Н., l i= ц, М|2 = а2;

в) если для некоторой неубывающей функции </(x) существует Мз(|) < оо, то МдШ) / Мд{0, t оо.

Приведены примеры из теории массового обслуживания и теории страхования. Показано, что представляет интерес рассмотрение процессов вида r]c(t) = rj{t) — ct, t > 0, с > 0 и их экстремумов Mc{t) = sup{i7c(u) : u е [о, г]}.

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

В §3.3 проводится диффузионная аппроксимация процессов типа (**) с линейным сдвигом, которая находит свое применение при расчете вероятности превышения уровня.

Процесс г) типа (**) представляется в виде 7/(i) = S(t) — где

то

S(t)=T.b, V*(t)=Zek(t-Tk),

Tk<i к-1

JO, i<0

u*-£*(f). t> о

Лемма 3.3.1. Пусть для некоторого d > 2 выполнено

оо

Medk(0) < оо, J (M(l 4- ek{t))d - l) dt < оо.

о

Тогда на любом отрезке [0,Т] имеет место сходимость

У*Ы) с „

-t-^J- О, п оо. утг

Здесь через обозначена С-сходимость.

Теорема 3.3.1. Если выполнены условия леммы 3.3.1, то на любом отрезке [0,Т] имеет место сходимость

rj{nt) - Xf-int a\f\n

4 w(t),

где — стандартный винеровский процесс.

Далее будем предполагать, что условия леммы 3.3.1 выполняются. Рассмотрим последовательность процессов

»т - ^"И) _ Ф*) ~ с***

П [1)~ фх - у/К

и их бегущих максимумов = 8ир{т/п'(и) : и 6 [0,4]}. Предпо-

ложим, что

(с„ - \ц)^/п а, поо.

Обозначим

Следствие 3.3.1. На любом отрезке [0,Т]

Д _ п _> оо.

Следствие 3.3.2.

Р(М(п)(0 > и) -> Р ( вир {¿»И^я) - 05} > и) = \«е[М 1

. „ /и + аП /-и + аА / 2а 1

где ^ — функция стандартного нормального распределения.

Следствие 3.3.3. Если а > 0, то для М(п) = зирг?("'(5),п > 1

в>0

имеет место асимптотика

Р(М(п) > и) -> ехр|-^«|, п —у оо, и > 0.

В §3.4 получены верхние и нижние оценки вероятности разорения Щи) в модели страхования с постоянной скоростью накопления резервов и выплатой по искам, описываемой процессом типа (**). Прежде всего, имеется очевидная верхняя оценка

Щи) = Р(вир{»7(*) - с£} > и) < Р(зир{5(£) - с«} > и) = Щи), оо оо

где Щи) — вероятность разорения в классической модели риска со скоростью накопления резервов с и страховыми выплатами Теорема 3.4.1

{д СО ч Д 00 _

— ]Bc{v)dv\~ - /Вс{у)йу, и —^ оо,

С и ) С и

где 5%т) = Р(зир{§ь(£) - сЬ} < х). (>0

Пусть выполнено условие Крамера: уравнение

AMexp{z£} = А + cz

имеет единственное положительное решение г, а также выполнено и более общее условие: уравнение

A h

- [ М exp{^(i)} dt = А + cz ho

при любом h > 0 имеет единственное положительное решение r(h).

Теорема 3.4.2 Для любого р > г существует константа Ср S (0,1] такая, что для всех и > 0 верно R(u) > Срехр{—ри].

Следствие 3.4.3 R(u) = exp{-fu(l -f о(1))} при и -> оо. В Приложении рассматривается важный подкласс процессов обобщенного дробового шума: процессы с конечным средним временем эффекта. Под временем эффекта от к-го импульса понимается

efc = 8up{i:&(i)^0}.

Теорема П.1. Процесс rj(t) с конечным средним временем эффекта обладает свойством сильного перемешивания.

Следствие П.1. Последовательности ¡лп = sup{i7(u) : и € [in_i,in]}, tn = nh, п > 1, h > 0 и 77(Т„), п > 1 также обладают свойством сильного перемешивания.

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

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

[1] Лебедев А.В. Асимптотика максимального числа занятых приборов в бесконечнолинейных системах // Вестник МГУ. Сер.1. — 1996. — No.5 — С.95-97

[2] Лебедев А.В. Асимптотика максимумов в бесконечнолинейных системах с ограниченным размером групп // Фундаментальная и прикладная математика. — 1996. — Т.2, No.4 — С.1107-1115

[3] Лебедев А.В. Асимптотика максимумов числа заявок и объема работы в некоторых бесконечнолинейных системах // Деп. ВИНИТИ N 2973-В97

[4] Bulinskaya Е. V., Lebedev A.V. Ruin probabilities and investment // Dwudziesta szosta ogolnopolska konferencici zastosowan matematyki, Zakopane-Koscielisko, 23-30.IX.1997. — S.10-11