WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи

УДК 519.21 Руденко

Игорь Викторович СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ С НЕНАДЕЖНЫМИ И ВОССТАНАВЛИВАЮЩИМИСЯ ПРИБОРАМИ

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

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

Москва 2012

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

Научный консультант:

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

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

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

доктор физико-математических наук, профессор Хохлов Юрий Степанович, Российский университет дружбы народов, факультет физико-математических и естественных наук, заведующий кафедрой теории вероятностей и математической статистики.

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

Национальный исследовательский университет ”Высшая школа экономики”.

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

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М. В. Ломоносова.

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

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Системы, в которых приборы подвержены случайным отказам, изучаются уже давно. Одни из первых результатов для систем обслуживания с ненадежными приборами были получены в работах В. М. Золотарева (рассматривалась система M|M|n с ожиданием, приборы которой отказывают и восстанавливаются по показательному закону) и Г. П. Башарина (изучались системы с ограниченной очередью и ненадежным прибором с различными дисциплинами обслуживания). Кроме того, были исследованы системы типа M|M|1 со случайной, меняющейся по марковскому закону интенсивностью обслуживания, системы типа M|G|1, в которых последовательность периодов безотказной работы и периодов восстановления приборов представляет собой альтернирующий процесс восстановления.

В дальнейшем рассматривались более сложные модели: например, системы с нетерпеливыми требованиями, которые в случае занятости прибора могут с некоторой вероятностью покидать систему, системы типа M|G|1 с потерями в случае произвольного распределения времени восстановления и ресурса надежности.

Несмотря на достаточно долгую историю развития данного направления, системы с ненадежными приборами часто являются предметом современных исследований, поскольку развитие технологий приводит к появлению новых содержательных математических задач. Например, значительный интерес проявляется к системам, в которых требования в различных ситуациях моЗолотарев В.М., “Распределение длины очереди и числа действующих линий в системе типа Эрланга со случайными поломками и восстановлениями линий.”. Тр. Мат. ин-та. АН СССР, 71, 51–61 (1964).

Башарин, Г. П., “Один прибор с конечной очередью и заявки нескольких видов”. Теория вероятностей и её применения, 10, 2, 282–296 (1965).

Eisen, M. M., “Effects 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–6(1965).

Tomko, J., “Однолинейная система массового обслуживания с учетом ненадежности прибора”. Magyar tud- akad. Mat. kutato int. Kozl., 9, 1–2, 61–72 (1964).

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

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

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

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

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

Нерегулируемый перекресток неравнозначных дорог описывается с помощью одноканальной системы с ненадежным прибором типа 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–3(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–3(2009).

Helbing, D., Jiang, R., Treiber, M., “Analytical investigation of oscillations in intersecting flows of pedestrian and vehicle traffic”. Phys. Rev. E, 72, 046130 (2005). Caceres, F.C., Ferrari, P.A., Pechersky E.,“A slow-to-start traffic 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| с идентичным временем обслуживания на периоде занятости найдены условия существования предельного распределения числа требований в системе, определен вид этого распределения, получены выражения для преобразования Лапласа-Стильтьеса функций распределения периода занятости и свободного периода.

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

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

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

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

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

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

По теме диссертации были сделаны доклады на следующих семинарах механико-математического факультета МГУ им. М. В. Ломоносова:

• Большом семинаре кафедры теории вероятностей под руководством действительного члена РАН, профессора А. Н. Ширяева (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. Приборы работают синхронно (периоды безотказной работы и периоды восстановления приборов совпадают). Времена безотказной работы (n) прибора {1 } имеют функцию распределения G1(x) с конечным n=(n) средним 1, а времена восстановления {2 } — функцию распредеn=ления G2(x) с конечным средним 2. Времена обслуживания требований в системе S1 имеют показательное распределение с параметром 1, а в системе S2 — показательное распределение с параметром 2.

3. Приборы функционируют в противофазе (период безотказной работы первого прибора совпадает с периодом восстановления второго прибора и наоборот). Времена безотказной работы и восстановления приборов имеют функцию распределения G(x) с конечным средним . Времена обслуживания требований на первой фазе имеют показательное распределение с параметром 1, на второй фазе — показательное распределение с параметром 2.

Рассматриваются процессы Ai(t) (i = 1, 2), задающие число требований в системе Si в момент t. Задача заключается в нахождении условий эргодичности процесса A1(t), который в силу сделанных предположений не является марковским.

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

Сначала исследуется система с независимо функционирующими приборами на фазах. Вводится вспомогательная система S2. Она представляет собой второй прибор, на который поступает дважды стохастический пуассоновский поток требований интенсивности e1(t) (здесь и далее ei(t) = (i = 1, 2), если в момент времени t в основной системе i-ый прибор находится в рабочем состоянии, ei(t) = 0 в противном случае). Число требований в системе S2 в момент t задается процессом A2(t). С помощью результатов для циклических систем, функционирующих в случайной среде, устанавливаются условия эргодичности для процесса A1(t).

Теорема 2. Положим ( )-d11 = -1 - pk - rk, d21 + 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 Если 1 > 1, то A1(t) -P . Если 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) имеет асимптотику:

( ) 2+ (1 + 2)c2 - c + 1 + 2 - (1 + 2) 1+ 1 + c + 1(k) = + 2 k (1 + 2)k( ) + , kгде 22 c = 1 +, (1 + 2)2(1 + 2)2z2 + 22z2(1 - z2) =, 22z2(1 - z2) + ((22 + 1) + 22)(1 - z2)2(1 + 2)2z1 - 22(1 - z1) =, -2(1 + 2)2z1 + ((22 + 1) + 22)(1 - z1)(1 + 2)2 + (22 + 31) + 2z1,2 = ± 22 + (22 + 1) 2 (1 + 2)4 + 2(1 + 2)2(22 + 31) + 4(31 + 412 + 2)2 + 81±.

22 + (22 + 1) Далее рассматривается двухфазная система с синхронно работающими приборами. На основании теорем о циклических системах в случайной среде получены условия эргодичности для процесса A1(t).

Теорема 4. Обозначим ( )-1 1 - k = 1 ·, 1 + 2 1 - k+где = 1/2. Если > 1, то A1(t) -P . Если < 1, то для всех j Z+ -t существуют lim P {A1(t) = j} = pj и {pj} является распределением веj=t роятностей.

Для изучаемой системы формулируются условия высокой загрузки на основании подхода, используемого в монографии А. А. Боровкова. РассматриБоровков, А. А., Вероятностные процессы в теории массового обслуживания. 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+ E i(n) < , i = 1, 2, а интенсивность задается соотношением (1). Тогда 2ax lim (x) = 1 - e-, где a и 2 — некоторые константы.

Доказательство опирается на теорему А. А. Боровкова и результаты, полученные в работе Л. Г. Афанасьевой и Е. Е. Баштовой.

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

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

Теорема 7. Пусть — случайная величина, задающая число требований, которые могут быть обслужены в системе S1 за один период безотказной 2 работы. Обозначим =.

E Если > 1, то A1(t) -P . Если < 1, то существуют lim P {A1(t) = -t t Афанасьева Л. Г., Баштова Е. Е. “Предельные теоремы для систем обслуживания с дважды стохастическим пуассоновским потоком (условия высокой загрузки)”. Пробл. передачи информ., 44, 4, 72–(2008).

j} = pj, причем {pj} задает распределение вероятностей.

j=Приводится алгоритм нахождения математического ожидания случайной величины .

Во второй главе исследуются системы обслуживания типа M|G|1| с ненадежными приборами.

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

Рассматривается одноканальная система обслуживания типа M|G|1| с ненадежным прибором. В систему поступает пуассоновский поток требований интенсивности 2. Длительности периодов безотказной работы прибора (0) {j } — независимые случайные величины с функцией распределения j=U(x) с конечным средним u, длительности периодов восстановления прибо(1) ра {j } — независимые случайные величины с функцией распределения 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) Y (t) = Yj(j) + Yn(t)+1(t - Tn(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) 2Ej < EYj(j ). (2) Показано, что для модели M1 процесс Yj(t) представляет собой простой процесс восстановления с условием Yj(0) = 1. Имеем Следствие 4. Процесс q1(t) является эргодическим тогда и только тогда, когда 2(u + g) < H(t)dU(t), (3) где H(t) — функция восстановления для простого процесса восстановления Yj(t).

Устанавливается, что для моделей M2 и M3 условие (3) является достаточным для эргодичности процессов q2(t) и q3(t) соответственно.

Далее считается, что время безотказной работы прибора имеет показательное распределение с параметром 1, т.е. U(x) = 1 - e- x. Пусть f(s) = e-sxdF (x). На основании следствия 4 получаем Следствие 7. При U(x) = 1 - e- x процесс q1(t) является эргодическим тогда и только тогда, когда 2(1 + 1g) <. (4) 1 - f(1) Также заключаем, что условие (4) является достаточным для эргодичности процессов q2(t) и q3(t).

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

Следствие 9. При U(x) = 1 - e- x процесс q4(t) является эргодическим тогда и только тогда, когда 1f(1) 2(1 + 1g) <. (5) 1 - f(1) Для моделей M1 и M2 находится предельное распределение числа требований в системе при t . Пусть q(t) — число требований в системе в момент t для модели M2. Будем считать, что время безотказной работы прибора имеет показательное распределение с параметром 1 (U(x) = 1 - e- x), время восстановления прибора имеет функцию распределения G(x) и преобразование Лапласа-Стилтьеса g(s). Входящий в систему поток — пуассоновский с параметром 2. Вводится производящая функция P (z, t) = Ezq(t), (|z| < 1).

Теорема 9. Если выполнено условие эргодичности (4), то zK0(z) - K(z) P (z) = lim P (z, t) = P0, (6) t z - K(z) где 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) (s) = f(1 + s) + (1 - f(1 + s)) g(s), (9) 1 + s 1 - 2 g(2) - g(s) 0(s) = + · · (s), (10) 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) и x2dG(x) < , то для модели M2 существует lim m(t) = lim Eq(t) = m < и t t ( ) 2K0(1) + K0 (1) K(1)K0(1) m = P0 +.

2(1 - K(1)) 2(1 - K(1))Далее изучаются условия высокой загрузки в соответствии с подходом, использованным в монографии А. А. Боровкова. Предполагается, что интенсивность 2 входящего в систему пуассоновского потока зависит от параметра таким образом, что = (1 - )1, где = ((1 + 1g)(1 + f(1)))-1. Процессы и их характеристики в системе с таким входящим потоком помечаются буквой , при этом q — сл. в. с производящей функцией P(z), определенной в теореме 9. Доказывается, что для систем M1, M2 и M3 справедлива Теорема 10. Если x3dG(x) < , то при { } P {q > x} exp -2x-Боровков, А. А., Вероятностные процессы в теории массового обслуживания. M.: Наука, 368 с.

(1972).

и m , где 2 = 2(21f(1)(1 + 1g) + (1 - f(1))(g(0)2 + 21g + 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 ром. В работе Р. Гидеона и Р. Пайка эта задача обобщена на случай двустороннего движения по основной трассе.

Интерес представляет исследование процесса образования очереди на второстепенной дороге. Показано, что данные модели могут интерпретироваться как системы типа M|G|1| с ненадежным прибором. Для получения основных характеристик рассматриваемых систем используются результаты, полученные в главе 2. Новизна результатов заключается в том, что задачу удается обобщить на случай более сложных потоков, движущихся по основной трассе, а также учесть некоторые особенности поведения водителей на дороге.

Приводится полное описание модели пересечения однополосных дорог.

Движение автомобилей по основной трассе описывается с помощью 1) бесконечноканальной системы типа M|G|, 2) бесконечноканальной системы типа GI|G| с идентичным временем обслуживания требований на периоде занятости. Для применения результатов главы 2 необходимо найти распределение периода занятости этих систем. В первом случае (система M|G|) используются результаты, полученные в работе W. Stadje. Системы типа 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 Traffic 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) = a-1 (y)dy, где (x) = 1 - A(x), то N(t) — однородный процесс восстановления и в таком случае pk(t, ) pk().

Справедлива Теорема 11. Существуют lim P {Q(t) = k} = pk(b).

t Кроме того, ( )-1 (1) ( )-1 b Ej = a (b), Ej = (b) (x)dx, -b (1) j gb(s) = Ee-s = - e-sxdA(x) e-sb(b), -b j ub(s) = Ee-s = - e-sxdA(x) e-sxdA(x).

0 b Доказывается аналогичная теорема для систем GI|G| с идентичным временем обслуживания на периоде занятости.

Теорема 12. Справедливы соотношения (1) e-sx(x) j g(s) = Ee-s = dB(x), x 1 - e-sydA(y) e-sydA(y) x j u(s) = Ee-s = dB(x).

x 1 - e-sydA(y) (1) Математические ожидания Ej и Ej существуют тогда и только тогда, когда ( )- = (x) dB(x) < . (11) Если (11) выполняется, то ( )-1 x (1) g = Ej = (x) (y)dy dB(x), 0 ( )-d = Ej = 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))-1B(x) непосредственно интегрируема по Риману на [0, ), то существуют положительные пределы ( )-k = lim P {Q(t) = k} = -1 (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 Traffic 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 Traffic 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.







© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.