Игорь викторович системы массового обслуживания с ненадежными и восстанавливающимися приборами
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТНа правах рукописи
УДК 519.21 Руденко Игорь Викторович СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ С НЕНАДЕЖНЫМИ И ВОССТАНАВЛИВАЮЩИМИСЯ ПРИБОРАМИ 01.01.05 — теория вероятностей и математическая статистика
Автореферат диссертации на соискание учёной степени кандидата физико-математических наук
Москва 2012
Работа выполнена на кафедре теории вероятностей механико математического факультета Московского государственного университета имени М. В. Ломоносова.
Научный консультант:
доктор физико-математических наук, профессор Афанасьева Лариса Григорьевна.
Официальные оппоненты:
доктор физико-математических наук, профессор Ушаков Владимир Георгиевич, Московский государственный университет имени М. В. Ломоносова, факультет вычислительной математики и кибернетики, профессор кафедры математической статистики;
доктор физико-математических наук, профессор Хохлов Юрий Степанович, Российский университет дружбы народов, факультет физико-математических и естественных наук, заведующий кафедрой теории вероятностей и математической статистики.
Ведущая организация:
Национальный исследовательский университет ”Высшая школа экономики”.
Защита диссертации состоится 21 декабря 2012 года в 16 часов 45 минут на заседании диссертационного совета Д 501.001.85 при Московском госу дарственном университете имени М. В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, механико математический факультет, аудитория 16-24.
С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М. В. Ломоносова.
Автореферат разослан 20 ноября 2012 г.
Учёный секретарь диссертационного совета Д 501.001.85 при МГУ доктор физико-математических наук, профессор В. Н. Сорокин.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы.
Одной из основных задач теории массового обслуживания является по строение и изучение математических моделей, с достаточной точностью опи сывающих реальные системы. Во многих ситуациях для успешного приме нения полученных результатов необходимо при создании модели учесть воз можность выхода прибора из строя. Именно с этим обстоятельством связан значительный интерес к исследованию систем с ненадежными приборами.
Системы, в которых приборы подвержены случайным отказам, изучают ся уже давно. Одни из первых результатов для систем обслуживания с нена дежными приборами были получены в работах В. М. Золотарева 1 (рассмат ривалась система M |M |n с ожиданием, приборы которой отказывают и вос станавливаются по показательному закону) и Г. П. Башарина 2 (изучались системы с ограниченной очередью и ненадежным прибором с различными дисциплинами обслуживания). Кроме того, были исследованы системы типа M |M |1 со случайной, меняющейся по марковскому закону интенсивностью обслуживания 3, системы типа M |G|1, в которых последовательность пери одов безотказной работы и периодов восстановления приборов представляет собой альтернирующий процесс восстановления 4.
В дальнейшем рассматривались более сложные модели: например, си стемы с нетерпеливыми требованиями, которые в случае занятости прибора могут с некоторой вероятностью покидать систему 5, системы типа M |G|1 с потерями в случае произвольного распределения времени восстановления и ресурса надежности 6.
Несмотря на достаточно долгую историю развития данного направления, системы с ненадежными приборами часто являются предметом современных исследований, поскольку развитие технологий приводит к появлению новых содержательных математических задач. Например, значительный интерес проявляется к системам, в которых требования в различных ситуациях мо Золотарев В.М., “Распределение длины очереди и числа действующих линий в системе типа Эрланга со случайными поломками и восстановлениями линий.”. Тр. Мат. ин-та. АН СССР, 71, 51–61 (1964).
Башарин, Г. П., “Один прибор с конечной очередью и заявки нескольких видов”. Теория вероятно стей и её применения, 10, 2, 282–296 (1965).
Eisen, M. M., “Eects of slowdowns and failure on stochastic service systems”. Technometrics, 11, 6, 922–927 (1963).
Eisen, M. M., Leibowitz, M. “Some remarks on server breakdown”. Operat. Res., 5, 3, 385–392 (1963).
Rao S. Subba, “Queueing models with balking, reneging, and interruptions”. Operat. Res., 13, 4, 596– (1965).
Tomko, J., “Однолинейная система массового обслуживания с учетом ненадежности прибора”. Magyar tud- akad. Mat. kutato int. Kozl., 9, 1–2, 61–72 (1964).
гут уходить на орбиту и возвращаются на прибор для повторного обслужи вания (retrial queues) 7. Результаты, полученные при изучении таких систем, могут применяться в работе с мультимедийными приложениями.
Кроме того, системы с выходящими из строя приборами в том или ином виде появляются в транспортных задачах 8. Системы обслуживания, изучае мые в диссертации, возникли при анализе некоторых транспортных моделей:
автомобильной дороги с двумя последовательно расположенными светофо рами и нерегулируемого перекрестка неравнозначных автомобильных дорог.
Первая модель описывается с помощью двухфазной системы обслужи вания с ненадежными приборами и буфером конечного объема. Если все места в буфере заняты, поступление требований на второй прибор (и, со ответственно, обслуживание требований на первом приборе) прекращается.
Рассматриваются различные режимы функционирования приборов. Инте рес представляет исследование процесса, задающего число требований на первом приборе. Предположение об ограниченности числа мест для ожида ния перед вторым прибором приводит к тому, что задача сводится к изу чению достаточно сложных, вообще говоря, немарковских процессов. Тем не менее, с помощью результатов, полученных для циклических систем об служивания, функционирующих в случайной среде, 9 удается исследовать очередь на первой фазе.
Нерегулируемый перекресток неравнозначных дорог описывается с помо щью одноканальной системы с ненадежным прибором типа M |G|1. Изуча ется процесс, определяющий число автомобилей на второстепенной дороге.
Используются специальные предположения о функционировании системы, свойственные рассматриваемой транспортной модели. Движение автомоби лей по основной трассе задается с помощью двух различных бесконечнока нальных моделей: стандартной системы типа M |G| и модифицированной системы типа GI|G| с идентичным временем обслуживания на периоде за нятости. Модифицированные системы GI|G| позволяют дать более точное описание движения автомобилей, приближающихся к перекрестку. Учиты вается тот факт, что при проезде опасного участка водители снижают ско рость и следуют за идущим впереди автомобилем. Полученные результаты для нерегулируемых перекрестков имеют интересные приложения, напри Djellab, N. V., “On the M |G|1 Retrial Queue Subjected to Breakdowns”. RAIRO Oper. Res., 36, 299– (2002). Sherman, N., Kharoufeh, J., Abramson, M., “An M |G|1 Retrial Queue With Unreliable Server for Streaming Multimedia Applications”. Probability in the Engineering and Informational Sciences, 23, 281– (2009).
Helbing, D., Jiang, R., Treiber, M., “Analytical investigation of oscillations in intersecting ows of pedestrian and vehicle trac”. Phys. Rev. E, 72, 046130 (2005). Caceres, F.C., Ferrari, P.A., Pechersky E.,“A slow-to-start trac model related to a M |M |1 queue”. J. Stat. Mech., P07008 (2007).
Афанасьева, Л. Г., “Системы массового обслуживания с циклическими управляющими процессами”.
Кибернетика и системный анализ, 41, 1, 54–68 (2005).
мер, позволяют решить вопрос о целесообразности установки светофора на таких перекрестках.
Вследствие популярности и активного развития теории массового обслу живания вообще и изучения систем с ненадежными приборами в частности, проблематика диссертации и подходы, предложенные в ней, представляются весьма актуальными.
Цель и задачи исследования.
Целью диссертации является получение новых результатов, касающихся систем обслуживания с ненадежными приборами. Среди задач исследования выделяются следующие.
— Изучение двухфазной системы обслуживания с ненадежными прибо рами и буфером конечного размера между фазами. Система представляет собой две последовательно соединенные одноканальные системы обслужива ния. Рассматриваются три режима работы приборов на фазах: синхронные приборы, независимо функционирующие приборы и приборы, работающие в противофазе.
— Анализ операционных характеристик модифицированных систем типа M |G|1| с ненадежным прибором. Особенность изучаемых систем состоит в специфических предположениях о времени обслуживания требований и способе прерывания обслуживания. Эти особенности характерны для неко торых транспортных моделей.
— Исследование систем типа GI|G| с идентичным временем обслужи вания на периоде занятости.
Научная новизна.
Представленные в диссертации результаты являются новыми, получен ными автором самостоятельно. Основные результаты диссертации следую щие.
— Для двухфазной системы обслуживания с ненадежными приборами установлены условия эргодичности. В модели с синхронными приборами на фазах изучены условия высокой загрузки, приводится алгоритм нахождения параметров предельного распределения числа требований на первой фазе в случае, когда времена безотказной работы и времена восстановления прибо ров постоянны.
— Для систем обслуживания типа M |G|1| с ненадежным прибором получены условия эргодичности, найдено предельное распределение числа требований в системе, приведены выражения для важных операционных ха рактеристик. Кроме того, доказана предельная теорема в условиях высокой загрузки.
— Для модифицированных бесконечноканальных систем обслуживания типа GI|G| с идентичным временем обслуживания на периоде занятости найдены условия существования предельного распределения числа требо ваний в системе, определен вид этого распределения, получены выражения для преобразования Лапласа-Стильтьеса функций распределения периода занятости и свободного периода.
— В качестве приложений приводятся применения полученных резуль татов к анализу функционирования транспортных систем: регулируемых и нерегулируемых перекрестков автомобильных дорог, автомобильных дорог с установленными светофорами.
Методика исследования.
В диссертации используются различные методы и результаты теории ве роятностей и теории случайных процессов: метод вложенных цепей Марко ва, теоремы о регенерирующих процессах 10, результаты, касающиеся цик лических систем массового обслуживания, функционирующих в случайной среде 11, предельные теоремы для случайных блужданий 12.
Теоретическая и практическая значимость.
Диссертация носит теоретический характер. Её результаты могут най ти применение в теории очередей, теории случайных блужданий, а также использоваться при исследовании транспортных систем.
Апробация работы.
По теме диссертации были сделаны доклады на следующих семинарах механико-математического факультета МГУ им. М. В. Ломоносова:
• Большом семинаре кафедры теории вероятностей под руководством действительного члена РАН, профессора А. Н. Ширяева (2012 г.), • Cпецсеминаре кафедры теории вероятностей под руководством д.ф.-м.н., профессора Л. Г. Афанасьевой (2009–2012 гг., неоднократно).
Результаты диссертации докладывались на международной конферен ции "Markov, Semi-Markov Processes and Related Fields" (Porto Carras Grand Resort, Greece, 2011), международной научной конференции студентов, ас пирантов и молодых учёных "Ломоносов-2011" (г. Москва, 2011), между народной научной конференции студентов, аспирантов и молодых учёных "Ломоносов-2012" (г. Москва, 2012), международной конференции "Теория вероятностей и ее приложения", посвященной 100-летию со дня рождения Б. В. Гнеденко (г. Москва, 2012), XXX международном семинаре по пробле мам устойчивости стохастических моделей (г. Светлогорск, 2012).
Smith, W. L., “Regenerative stochastic processes”. Proc. Roy. Soc., A232, 6–31 (1955).
Афанасьева, Л. Г., “Системы массового обслуживания с циклическими управляющими процессами”.
Кибернетика и системный анализ, 41, 1, 54–68 (2005).
Боровков, А. А., Вероятностные процессы в теории массового обслуживания. M.: Наука, 368 с.
(1972).
Публикации.
Результаты диссертации опубликованы в шести работах, из которых три — в журналах из перечня ВАК. Список работ приведён в конце ав тореферата [1-6].
Структура и объём работы.
Диссертация изложена на 106 страницах и состоит из введения, трёх глав и списка литературы, включающего 68 наименований.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении приводится краткий обзор исследований, посвященных си стемам обслуживания с ненадежными приборами. Историческая справка подкрепляется соответствующими ссылками на научные работы. Кроме то го, во введении объясняется актуальность темы и научная новизна предпри нятого автором исследования.
В первой главе изучается двухфазная система массового обслужива ния, состоящая из двух последовательно соединенных одноканальных си стем S1 и S2. В S1 поступает пуассоновский поток требований X(t) интен сивности и число мест для ожидания неограничено. Требования, обслу женные в S1, направляются в S2. Между S1 и S2 имеется буфер объема k, так что если все k мест заняты, то поступление требований в S2 (и, ста ло быть, обслуживание в S1 ) прекращается до тех пор, пока не появится свободное место в буфере.
Используются следующие предположения о функционировании прибо ров на фазах.
1. Приборы работают независимо друг от друга. Время безотказной рабо ты каждого из приборов имеет распределение Эрланга с параметрами (1, d1 ), а время восстановления каждого из приборов — распределение Эрланга с параметрами (2, d2 ). Времена обслуживания требований в системах S1 и S2 независимы и имеют показательное распределение с параметром.
2. Приборы работают синхронно (периоды безотказной работы и перио ды восстановления приборов совпадают). Времена безотказной работы прибора {1 } имеют функцию распределения G1 (x) с конечным (n) n= средним 1, а времена восстановления {2 } — функцию распреде (n) n= ления G2 (x) с конечным средним 2. Времена обслуживания требова ний в системе S1 имеют показательное распределение с параметром 1, а в системе S2 — показательное распределение с параметром 2.
3. Приборы функционируют в противофазе (период безотказной работы первого прибора совпадает с периодом восстановления второго прибо ра и наоборот). Времена безотказной работы и восстановления прибо ров имеют функцию распределения G(x) с конечным средним. Вре мена обслуживания требований на первой фазе имеют показательное распределение с параметром 1, на второй фазе — показательное рас пределение с параметром 2.
Рассматриваются процессы Ai (t) (i = 1, 2), задающие число требований в системе Si в момент t. Задача заключается в нахождении условий эргодич ности процесса A1 (t), который в силу сделанных предположений не является марковским.
Приводятся формулировки результатов для циклических систем обслу живания, функционирующих в случайной среде 13.
Сначала исследуется система с независимо функционирующими прибо рами на фазах. Вводится вспомогательная система S2. Она представляет собой второй прибор, на который поступает дважды стохастический пуас соновский поток требований интенсивности e1 (t) (здесь и далее ei (t) = (i = 1, 2), если в момент времени t в основной системе iый прибор находит ся в рабочем состоянии, ei (t) = 0 в противном случае). Число требований в системе S2 в момент t задается процессом A2 (t). С помощью результатов для циклических систем, функционирующих в случайной среде, устанавли ваются условия эргодичности для процесса A1 (t).
Теорема 2. Положим ( ) d1 1 = 1 p k rk, d2 1 + d1 где pk = lim P {A2 (t) = j, e1 (t) = 1, e2 (t) = 1}, t rk = lim P {A2 (t) = j, e1 (t) = 1, e2 (t) = 0}.
t P Если 1 1, то A1 (t). Если 1 1, то существует j = t lim P {A1 (t) = j} 0 для всех j Z +.
t Рассматривается экспоненциальный случай, когда времена безотказной ра боты и времена восстановления приборов имеют показательное распреде ление с параметрами 1 и 2 соответственно. Выписывается система урав нений для стационарных вероятностей процесса {A2 (t), e1 (t), e2 (t)}. Анализ Афанасьева, Л. Г., “Системы массового обслуживания с циклическими управляющими процессами”.
Кибернетика и системный анализ, 41, 1, 54–68 (2005).
этой системы позволяет получить асимптотическую форму коэффициента загрузки системы 1 при k.
Теорема 3. При k коэффициент загрузки 1 (k) имеет асимптотику:
( ) c (1 + 2 )c c + 1 + 2+ 1+ (1 + 2 ) + 1 (k) = 1+ + (1 + 2 )k 2 k () +o 2, k где c=1+, (1 + 2 ) 2(1 + 2 )2 z2 + 22 z2 (1 z2 ) =, 22 z2 (1 z2 ) + ((22 + 1 ) + 2 2 )(1 z2 ) 2(1 + 2 )2 z1 22 (1 z1 ) =, 2(1 + 2 )2 z1 + ((22 + 1 ) + 2 2 )(1 z1 ) (1 + 2 )2 + (22 + 31 ) + 2 ± z1,2 = 2 2 + (22 + 1 ) 2 (1 + 2 )4 + 2(1 + 2 )2 (22 + 31 ) + 4(31 + 41 2 + 2 ) 2 + 81 ±.
2 2 + (22 + 1 ) Далее рассматривается двухфазная система с синхронно работающими приборами. На основании теорем о циклических системах в случайной среде получены условия эргодичности для процесса A1 (t).
Теорема 4. Обозначим ( ) 1 k · = 1, 1 + 2 1 k+ P где = 1 /2. Если 1, то A1 (t). Если 1, то для всех j Z + t существуют lim P {A1 (t) = j} = pj и {pj } является распределением ве j= t роятностей.
Для изучаемой системы формулируются условия высокой загрузки на осно вании подхода, используемого в монографии А. А. Боровкова 14. Рассматри Боровков, А. А., Вероятностные процессы в теории массового обслуживания. M.: Наука, 368 с.
(1972).
вается семейство систем обслуживания S1 с пуассоновским входящим пото ком интенсивности, определяемой соотношением (1 k ) = (1 )1 (1).
(1 k+1 )(1 + 2 ) Таким образом, коэффициент загрузки системы = 1 и 1 при 0. Поскольку при 0 имеем 1, в соответствии с теоремой существует lim P {A (t) x} = (x), t где (x) — функция распределения, а A (t) — число требований в системе S1 в момент t.
Исследуется асимптотическое поведение функции (x) при 0.
Теорема 5. Пусть для некоторого ( )2+ (n), i = 1, 2, E i а интенсивность задается соотношением (1). Тогда lim (x) = 1 e 2, 2ax где a и 2 — некоторые константы.
Доказательство опирается на теорему А. А. Боровкова и результаты, полу ченные в работе Л. Г. Афанасьевой и Е. Е. Баштовой 15.
Коэффициенты a и 2 выражаются через характеристики сложных вспо могательных систем и их определение представляет, вообще говоря, суще ственные трудности. Приводится алгоритм нахождения параметров a и в случае, когда времена безотказной работы и времена восстановления при боров постоянны.
Далее изучается двухфазная система обслуживания с приборами, рабо тающими в противофазе. Для этой системы установлены условия эргодич ности.
Теорема 7. Пусть — случайная величина, задающая число требований, которые могут быть обслужены в системе S1 за один период безотказной работы. Обозначим = 2.
E P Если 1, то A1 (t). Если 1, то существуют lim P {A1 (t) = t t Афанасьева Л. Г., Баштова Е. Е. “Предельные теоремы для систем обслуживания с дважды стоха стическим пуассоновским потоком (условия высокой загрузки)”. Пробл. передачи информ., 44, 4, 72– (2008).
j} = pj, причем {pj } задает распределение вероятностей.
j= Приводится алгоритм нахождения математического ожидания случайной величины.
Во второй главе исследуются системы обслуживания типа M |G|1| с ненадежными приборами.
Кратко приводятся результаты, полученные в одной из важнейших ра бот, посвященных одноканальным системам с ненадежными приборами 16.
Рассматривается одноканальная система обслуживания типа M |G|1| с ненадежным прибором. В систему поступает пуассоновский поток требова ний интенсивности 2. Длительности периодов безотказной работы прибора {j } — независимые случайные величины с функцией распределения (0) j= U (x) с конечным средним u, длительности периодов восстановления прибо ра {j } — независимые случайные величины с функцией распределения (1) j= G(x) с конечным средним g.
Изучаются четыре модели, отличающиеся друг от друга предположениями о времени обслуживания требований и способе прерывания обслуживания.
1. Модель M1. Времена обслуживания требований — независимые слу чайные величины с функцией распределения F (x). При поломке при бора обслуживание требования немедленно прекращается, требование покидает систему в момент восстановления прибора (остаточное время обслуживания после его возобновления равно нулю).
2. Модель M2. Имеет место эффект ”проскакивания”, то есть время об служивания требования, поступившего в свободную систему при ра ботающем приборе, равно нулю. В остальных случаях времена обслу живания требований — независимые случайные величины с функцией распределения F (x). Предположение о прерванном обслуживании то же, что в модели M1.
3. Модель M3. Имеет место эффект ”проскакивания”. В случае преры вания обслуживания поломкой прибора требование, находящееся на приборе, незамедлительно покидает систему.
4. Модель M4. Обслуживание требований стандартное. Прерванное по ломкой прибора обслуживание продолжается после восстановления прибора, причем время обслуживания после возобновления не зави сит от исходного времени обслуживания и имеет то же распределение.
Gaver, D. P., Jr., “A Waiting Line with Interrupted Service, Including Priorities”. J. Roy. Statist. Soc., 24, 73–90 (1962).
В главе 3 показано, что перечисленные особенности систем важны при описа нии функционирования транспортных моделей (например, регулируемых и нерегулируемых перекрестков автомобильных дорог). Кроме того, эти пред положения отличают рассматриваемые системы от ранее изученных.
Обсуждаются различные подходы к определению функций U (x) и G(x).
Отмечается, что при анализе транспортных систем полезна интерпретация периода восстановления прибора как периода занятости в модифицирован ной бесконечноканальной системе типа GI|G| с идентичным временем об служивания требований на периоде занятости.
Далее устанавливаются условия эргодичности для изучаемых моделей.
(0) (1) Будем говорить, что j = j + j представляет собой j-й цикл. Чтобы опи сать процесс обслуживания, введем последовательность {Yj (t), t 0}, со j= стоящую из независимых одинаково распределенных случайных процессов, имеющих неубывающие непрерывные слева траектории с целочисленными { } (0) значениями и единичными скачками. Процесс Yj (t), t j определяет (0) правило обслуживания при условии, что в течение всего периода [0, j ] в системе были требования. Таким образом, моменты окончаний обслужива ния на j-м цикле — это моменты скачков процесса Yj (t). Введем случайный процесс Yj (t) = Yj (t) · (t (0) ) и положим j n(t) Yj (j ) + Yn(t)+1 (t Tn(t) ), Y (t) = j= где n(t) — число полных циклов до момента t, т.е. n(t) = max{k 0 : Tk t}.
Пусть qi (t) — число требований в модели Mi в момент t (i = 1, 4). При водятся необходимые и достаточные условия эргодичности процесса q4 (t).
Теорема 8. Процесс q4 (t) является эргодическим тогда и только тогда, когда (0) (2) 2 Ej EYj (j ).
Показано, что для модели M1 процесс Yj (t) представляет собой простой про цесс восстановления с условием Yj (0) = 1. Имеем Следствие 4. Процесс q1 (t) является эргодическим тогда и только тогда, когда (3) 2 (u + g) H(t)dU (t), где H(t) — функция восстановления для простого процесса восстановле ния Yj (t).
Устанавливается, что для моделей M2 и M3 условие (3) является достаточ ным для эргодичности процессов q2 (t) и q3 (t) соответственно.
Далее считается, что время безотказной работы прибора имеет пока зательное распределение с параметром 1, т.е. U (x) = 1 e1 x. Пусть sx f (s) = e dF (x). На основании следствия 4 получаем Следствие 7. При U (x) = 1 e1 x процесс q1 (t) является эргодическим тогда и только тогда, когда (4) 2 (1 + 1 g).
1 f (1 ) Также заключаем, что условие (4) является достаточным для эргодичности процессов q2 (t) и q3 (t).
Отмечается, что для модели M4 при показательном распределении вре мени безотказной работы прибора необходимые и достаточные условия эр годичности другие.
Следствие 9. При U (x) = 1 e1 x процесс q4 (t) является эргодическим тогда и только тогда, когда 1 f (1 ) (5) 2 (1 + 1 g).
1 f (1 ) Для моделей M1 и M2 находится предельное распределение числа тре бований в системе при t. Пусть q(t) — число требований в системе в момент t для модели M2. Будем считать, что время безотказной рабо ты прибора имеет показательное распределение с параметром 1 (U (x) = 1 e1 x ), время восстановления прибора имеет функцию распределения G(x) и преобразование Лапласа-Стилтьеса g(s). Входящий в систему по ток — пуассоновский с параметром 2. Вводится производящая функция P (z, t) = Ez q(t), (|z| 1).
Теорема 9. Если выполнено условие эргодичности (4), то zK0 (z) K(z) (6) P (z) = lim P (z, t) = P0, z K(z) t где P0 = (1 K (1))(1 K (1) + K0 (1))1, (7) а функции K(z) и K0 (z) определяются соотношениями K(z) = (2 (1 z)), K0 (z) = 0 (2 (1 z)), (8) (1 f (1 + s)) g(s), (9) (s) = f (1 + s) + 1 + s 1 g(2 ) g(s) · · (s), (10) 0 (s) = + 1 g(2 ) 1 g(2 ) s и = 1 (1 + 2 )1.
Из доказательства теоремы 9 немедленно следуют два важных результа та.
Следствие 11. Для модели M1, не учитывающей эффект “проскакивания”, справедлива теорема 9 с заменой K0 (z) на K(z).
Следствие 12. Условие (4) является необходимым и достаточным для эргодичности процесса, задающего число требований в моделях M1, M2 и M3.
Для математического ожидания числа требований в системе имеем Следствие 13. Если выполнено условие эргодичности (4) и x2 dG(x), то для модели M2 существует lim m(t) = lim Eq(t) = m и t t ( ) K (1)K0 (1) 2K0 (1) + K0 (1) m = P0 +.
2(1 K (1)) 2(1 K (1)) Далее изучаются условия высокой загрузки в соответствии с подходом, использованным в монографии А. А. Боровкова 17. Предполагается, что ин тенсивность 2 входящего в систему пуассоновского потока зависит от пара метра таким образом, что = (1 )1, где = ((1 + 1 g)(1 + f (1 )))1. Процессы и их характеристики в системе с таким входящим потоком помечаются буквой, при этом q — сл. в. с производящей функцией P (z), определенной в теореме 9. Доказывается, что для систем M1, M2 и M3 справедлива Теорема 10. Если x dG(x), то при { } P {q x} exp 2x Боровков, А. А., Вероятностные процессы в теории массового обслуживания. M.: Наука, 368 с.
(1972).
и m, где 2 = 2 (21 f (1 )(1 + 1 g) + (1 f (1 ))(g (0)2 + 21 g + 2)).
В заключительной части главы 2 для модели M2 находятся важные опе рационные характеристики, такие как вероятность “проскакивания” требо вания и вероятность прерывания обслуживания.
В третьей главе приводятся приложения результатов глав 1 и 2 к ис следованию транспортных систем.
Изучается регулируемый перекресток однополосных автомобильных до рог с установленным на нем светофором. Считается, что в одном из направ лений движется пуассоновский поток автомобилей, а времена переключения светофора постоянны. Время, необходимое автомобилю на проезд перекрест ка, имеет произвольное распределение. Рассматриваются три модели, ана логичные моделям M1, M2 и M3, исследованным в главе 2. Объясняется, что эти модели описывают различные типы поведения водителей на дороге.
Формулируются условия эргодичности для процессов qi (t), задающих число автомобилей перед светофором в момент t в модели Mi (i = 1, 2, 3).
Для модели M3 приводится алгоритм нахождения предельного распределе ния вложенной цепи Маркова qn — числа автомобилей перед светофором в момент, когда в n-й раз загорается зеленый свет, — при n.
Исследуется однополосная автомобильная дорога с двумя последователь но расположенными светофорами. Показано, что транспортная модель мо жет быть описана с помощью двухфазной системы, рассмотренной в главе 1. Изучаются две ситуации: 1) светофоры работают синхронно, а времена переключения светофора постоянны, 2) светофоры функционируют неза висимо, а времена переключения случайны и имеют показательное распре деление. Формулируются условия эргодичности. Объясняется, что модель с синхронными светофорами может оставаться эргодичной при более вы соких значениях интенсивности входного потока, чем модель с независимо работающими светофорами.
Изучается функционирование перекрестков, образованных пересечением главной (основной) и второстепенной дорог. Рассматриваются пересечения однополосных и двухполосных дорог. Для модели с однополосными дорога ми считается, что автомобиль со второстепенной дороги может повернуть направо, если на основной трассе на расстоянии J от пересечения дорог нет автомобилей. Для модели с с двухполосными дорогами считается, что ав томобиль с второстепенной дороги может повернуть направо, если свободен участок J1 на ближней к перекрестку полосе основной трассы. Для поворота налево необходимо, чтобы были свободны интервалы J1 и J2 на ближней и дальней полосах главной дороги соответственно. Аналогичная задача для однополосных дорог в простейшей постановке рассматривалась Дж. Танне ром 18. В работе Р. Гидеона и Р. Пайка 19 эта задача обобщена на случай двустороннего движения по основной трассе.
Интерес представляет исследование процесса образования очереди на второстепенной дороге. Показано, что данные модели могут интерпретиро ваться как системы типа M |G|1| с ненадежным прибором. Для получения основных характеристик рассматриваемых систем используются результа ты, полученные в главе 2. Новизна результатов заключается в том, что за дачу удается обобщить на случай более сложных потоков, движущихся по основной трассе, а также учесть некоторые особенности поведения водителей на дороге.
Приводится полное описание модели пересечения однополосных дорог.
Движение автомобилей по основной трассе описывается с помощью 1) бес конечноканальной системы типа M |G|, 2) бесконечноканальной системы типа GI|G| с идентичным временем обслуживания требований на периоде занятости. Для применения результатов главы 2 необходимо найти распре деление периода занятости этих систем. В первом случае (система M |G|) используются результаты, полученные в работе W. Stadje 20. Системы типа GI|G| с идентичным временем обслуживания на периоде занятости иссле дуются в диссертации.
В качестве входящего потока рассматривается общий процесс восстанов ления N (t), т.е. интервалы между поступлениями требований независимые одинаково распределенные случайные величины с функцией распределения A(x) и конечным средним a = xdA(x). Время до поступления первого требования имеет функцию распределения A1 (x). Если требование поступа ет в свободную систему, его время обслуживания — случайная величина с функцией распределения B(x) и оно начинает период занятости. Все дру гие требования, приходящие на данном периоде занятости, имеют то же время обслуживания, что и первое, так что на каждом периоде занятости время обслуживания постоянно. На разных периодах занятости времена об Tanner, J. C., “The Delay to Pedestrians Crossing a Road”. Biometrika, 38, 383–392 (1951).
Gideon, R., Pyke, R., “Markov Renewal Modelling of Poisson Trac at Intersections Having Separate Turn Lanes”. Semi-Markov Models and Applications, 285–310 (1999).
Stadje, W., “The Busy Period of the Queueing System M |G|”. J. Appl.Prob., 3, 22, 657–704 (1985).
служивания — независимые случайные величины с функцией распределе ния B(x). Такие системы будем называть модифицированными системами {} (1) типа GI|G|. Пусть j — последовательность периодов занятости, { } j= (0) (1) (0) — последовательность свободных периодов. Сумму j = j + j j j= будем называть jым циклом, при этом цикл начинается в момент поступ ления требования в свободную систему.
Сначала исследуется система типа GI|D|, в которой время обслужива ния постоянно и равно b. Пусть Q(t) — число требований в системе в момент t. Для общего процесса восстановления N (t) положим pk (t, ) = P {N (t + x ) N (t) = k}. Если A1 (x) = a1 A(y)dy, где A(x) = 1 A(x), то N (t) — однородный процесс восстановления и в таком случае pk (t, ) pk ( ).
Справедлива Теорема 11. Существуют lim P {Q(t) = k} = pk (b).
t Кроме того, b ( )1 ( ) (1) Ej = a A(b), Ej = A(b) A(x)dx, b gb (s) = Eesj = 1 esx dA(x) (1) esb A(b), b ub (s) = Eesj = 1 esx dA(x) esx dA(x).
0 b Доказывается аналогичная теорема для систем GI|G| с идентичным временем обслуживания на периоде занятости.
Теорема 12. Справедливы соотношения esx A(x) (1) sj g(s) = Ee = dB(x), x 1 e sy dA(y) esy dA(y) u(s) = Eesj = x dB(x).
x 1 esy dA(y) (1) Математические ожидания Ej и Ej существуют тогда и только то гда, когда ( ) dB(x).
(11) = A(x) Если (11) выполняется, то x ( ) (1) g= Ej = A(x) A(y)dy dB(x), 0 ( ) d = Ej = a A(x) dB(x).
Кроме того, для модифицированных систем GI|G| найдены условия существования предельного распределения числа требований в системе.
Теорема 13. Если =, то lim P {Q(t) = k} = 0, k = 0, 1, 2,...
t Если и выполняется одно из условий 1. B(x) — функция распределения решетчатого распределения, 2. B(x) абсолютно непрерывна и функция (A(x))1 B (x) непосредствен но интегрируема по Риману на [0, ), то существуют положительные пределы ( ) k = lim P {Q(t) = k} = 1 A(x) pk (x)dB(x).
t Для изучаемых моделей перекрестка однополосных дорог на основании результатов главы 2 формулируются условия эргодичности для процесса q(t), задающего число автомобилей на второстепенной дороге, устанавлива ется предельное распределение процесса q(t), находятся операционные ха рактеристики системы, исследуются условия высокой загрузки.
Приводится описание модели перекрестка неравнозначных двухполос ных дорог. Движение по каждой из полос главной дороги описывается с помощью системы GI|G| с идентичным временем обслуживания на пе риоде занятости. Для того, чтобы исследовать процесс q(t), задающий чис ло автомобилей перед перекрестком, поворачивающих налево, необходимо найти распределение периода, когда хотя бы одна из двух модифицирован ных систем GI|G| занята. Предлагается способ решения этой задачи. Для модели перекрестка устанавливаются условия эргодичности, определяется предельное распределение процесса q(t) при t.
Автор выражает глубокую благодарность и признательность своему на учному руководителю доктору физико-математических наук, профессору Афанасьевой Ларисе Григорьевне за постановку задач и постоянное вни мание к работе. Автор высоко ценит содействие, оказанное работе сотрудни ками кафедры теории вероятностей механико-математического факультета МГУ имени М. В. Ломоносова.
РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ [1] Афанасьева, Л. Г., Руденко, И. В., “Системы обслуживания GI|G| и их приложения к анализу транспортных моделей”. Теория вероятностей и ее применения, 57:3, 427–452 (2012).
Афанасьева Л. Г. поставила задачу и предложила методы решения. Все результаты принадлежат Руденко И. В.
[2] Руденко, И. В., “Двухфазная система обслуживания с ненадежными приборами”. Вестн. Моск. ун-та, Сер. 1. Матем. Механ., 4, 8–14 (2012).
[3] Руденко, И. В., “Двухфазная система обслуживания с ненадежными приборами в условиях высокой загрузки”. Вестн. Моск. ун-та, Сер. 1. Ма тем. Механ., 6, 47–50 (2012).
[4] Rudenko, I. V., “Stochastic Analysis of Trac at Non-regulated Intersections”. XXX International Seminar on Stability Problems for Stochastic Models and VI International Workshop "Applied Problems in Theory of Probabilities and Mathematical Statistics Related to Modeling of Information Systems Book of Abstracts, 66-67. Institute of Informatics Problems, RAS, Moscow, 2012.
[5] Rudenko, I. V., “GI|G| Queues and their Applications to the Analysis of Trac Models”. International Conference "Probability Theory and its Applications"in Commemoration of the Centennial of B.V. Gnedenko, Abstracts, 233. URSS, Moscow, 2012.
[6] Rudenko, I. V., “Two-Phase Queuing System in a Random Environment”. International Conference "Markov and Semi-Markov Processes and Related Fields 2011 Conference Abstracts, 21/09/2011. Aristotel University of Thessaloniki, Porto Carras Grand Resort, 2011.