-2-
СОДЕРЖАНИЕ
стр.
ВВЕДЕНИЕ..........................................................3
Г Л А В А 1. ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ ДЛЯ ДИСКРЕТНЫХ ХАРАКТЕ-
РИСТИК МОДЕЛИ M|G|l|oo ПРИ ФИКСИРОВАННЫХ ЗАГРУЗКАХ
§ 1.1. Основное уравнение...................................13
§ 1.2. Асимптотический анализ...............................18
§ 1.3. Информация об устойчивых законах.....................26
§ 1.4. Сходимость к устойчивым законам......................36
§ 1.5. Свойства траекторий..................................38
§ 1.6. Представления для времен ожидания....................49
Г Л А В А 2. ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ ДЛЯ НЕПРЕРЫВНЫХ ХАРАКТЕРИСТИК МОДЕЛИ M|G|l|oo ПРИ ФИКСИРОВАННЫХ ЗАГРУЗКАХ
§ 2.1. Основное уравнение...................................55
§ 2.2. Асимптотический анализ...............................58
§ 2.3. Сходимость к устойчивым законам......................67
§ 2.4. Усиленный закон больших чисел........................78
§ 2.5. Представления для времен ожидания....................79
§ 2.6. Основные формулы для стационарных времен ожидания....85
Г Л А В А 3. ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ В МОДЕЛИ M|G|1 |оо В УСЛОВИЯХ КРИТИЧЕСКОЙ ЗАГРУЗКИ
§3.1. Одномерные и многомерные интегральные представления для
виртуальных времён ожидания.......................................92
§3.2. Предельные теоремы для времён ожидания при критической
загрузке.........................................................94
§3.3. Представления на языке медленно меняющихся функций...101
ЛИТЕРАТУРА......................................................104
-3-
ВВЕДЕНИЕ
Модели массового обслуживания образуют специальный класс математических моделей, описывающих поведение огромного множества разнообразных сложных систем. Их теоретический анализ необходим на этапе проектирования таких сложных систем, как информационные сети, в частности, интернет-сети, автоматизированные вычислительные системы, системы снабжения, транспортные комплексы, медицинское обслуживание и т.д.
Модели массового обслуживания возникают всюду, где мы имеем дело с клиентами, требованиями, вызовами, которые выстраиваются в очередь с целью приобретения услуг (получения обслуживания) в пунктах, узлах, их предоставляющих. Обслуживанием очередей занимаются так называемые приборы, осуществляющие последовательную "массовую” обработку (обслуживание) вызовов при учете влияния сопутствующих случайных факторов.
Известный специалист по вычислительным системам Л. Клейнрок определяет модели массового обслуживания (очередей) как широкий класс систем, в которых клиенты конкурируют друг с другом за доступ к ограниченным ресурсам. По его мнению " применение теории очередей (теории массового обслуживания) для анализа распределения ресурсов и решения задач о потоках данных в вычислительных системах является, по-видимому, единственным, доступным специалистам по вычислительной технике методом, позволяющим понять сложные связи в таких системах" [14].
По своей сути, практические задачи, приводящие к моделям массового обслуживания, являются оптимизационными. Особенно отчетливо эта особенность проявилась на этапе первичного развития теории, на который большое влияние оказал известный датский ученый А.К. Эрланг (1878-1929) -многолетний сотрудник Копенгагенской телефонной компании.
-4-
Функционирование телефонной станции того времени привело к возникновению следующей практической задачи. На телефонную станцию с конечным числом свободных линий (приборов) приходят клиенты (поступают вызовы). Если в момент прихода клиента находится свободная линия, то происходит подключение и начинается разговор (происходит обслуживание вызова). В противном случае клиенту приходится ждать освобождения линий (вызов становится в очередь и ждет освобождения прибора).
В связи с конкуренцией с другими телефонными станциями, слишком долгое ожидание начала обслуживания может заставить клиента обратиться к услугам другой телефонной станции.
С одной стороны, телефонная компания заинтересована в уменьшении числа телефонных линий, требующих на свое приобретение, содержание и эксплуатацию определенных затрат. С другой стороны, уменьшение числа телефонных линий может привести к потенциальным потерям клиентов, что отражается на доходах телефонной компании.
Возникает задача расчета оптимального числа телефонных линий на станции на основе статистически выверенного критерия потерь.
С рассматриваемой точки зрения теория массового обслуживания включается в широкое направление исследований - исследование операций.
При удовлетворении критериям потерь, при которых клиент предпочитает остаться в очереди и ждать начала обслуживания, мы имеем дело с моделями массового обслуживания с ожиданием.
Далее, учет влияния случайных факторов при изучении практических задач, приводящих к моделям массового обслуживания, обуславливает применение методов теории вероятностей для решения этих задач, относит модели массового обслуживания к стохастическим моделям - специальному разделу теории вероятностей.
-5-
Исключительная роль теории вероятностей при анализе моделей массового обслуживания, в сравнении с некоторыми другими разделами исследования операций (теория игр, теория информации и кодирования и т.д.), вызвана многими обстоятельствами.
В моделях массового обслуживания прежде, чем дойти до возможности непосредственного решения оптимизационной задачи, следует пройти несколько этапов.
Оптимизационные задачи здесь, как правило, формируются в условиях стационарного режима работы модели. Они заключаются в минимизации так называемых критериев потерь либо в широких классах дисциплин обслуживания (правил выбора вызовов из очереди на обслуживание), либо по типу обслуживания (вида функции распределения времен обслуживания) и т.д.
Сами критерии потерь записываются в терминах основных характеристик модели (времен ожидания, длин очередей, простоев приборов и т.д.).
Таким образом, решение оптимизационной задачи в моделях массового обслуживания предполагает предварительное получение, по крайней мере:
1. Условий существования стационарных характеристик;
2. Расчетных формул для нестационарных характеристик;
3. Расчетных формул для стационарных характеристик из формул для соответствующих нестационарных характеристик при неограниченном росте времени (дискретного или непрерывного).
Теория массового обслуживания за короткий промежуток времени из области исследований инженерных задач телефонной связи превратилась в широкое инженерно-математическое направление с применениями в разных сферах человеческой деятельности. Вплоть до 50-х годов под единым названием «теория массового обслуживания» публиковались много статей, изучающих по сути дела задачи массового обслуживания, но разнообразные по терминологии и сферам применения.
-6-
Возникла необходимость четко осознать предмет теории массового обслуживания, создать её терминологию, освободиться от многочисленных дублирований исследований в дальнейшем.
С выходом в свет монографий Б.В.Гнеденко и И.Н.Ковалснко [6], Дж.Коэна [36] окончательно оформилась теория массового обслуживания на математическую теорию и инженерную теорию телетрафика.
У многих исследователей возникло естественное желание ограничить предмет математической теории массового обслуживания сравнительно простыми по структуре, но тем не менее достаточно общими моделями, для которых возможно подобрать единый математический аппарат их исследования. Примерами такого подхода служат работы А.А.Боровкова [1,2].
В теории массового обслуживания намечается тенденция выделения математической теории путем подбора сравнительно несложных одноканальных моделей (моделей с одним обслуживающим прибором), поддающихся исследованию известными математическими методами [7, 13, 14].
На практике часто предполагается, что входящий поток (поток поступающих в модель вызовов) является пуассоновским. Предположение о пуассоновости входящего потока не является сильным ограничением, поскольку, как показали интересные исследования Г.А.Ососкова [18] и Б.Григелиониса [8], наложение многих «малых» потоков при достаточно широких условиях приводит к суммарному пуассоновскому.
Предположение о пуассоновости входящих потоков в структурно сложных моделях массового обслуживания (приоритетные модели, динамические модели и т.д.) и сейчас, как правило, является необходимым атрибутом формализации, не вызывая протеста в среде инженеров, применяющих полученные результаты. Более того, результаты по
- 7 -
приоритетным и динамическим моделям при таком предположении характеризуют современный уровень, выше которого затруднено понимание результатов инженерами-проекгировщиками реальных систем.
Предположение пуассоновости, из-за свойства отсутствия последействия показательного закона, который служит распределением промежутка между соседними моментами поступлений вызовов в пуассоновском потоке, позволяет разработать специфические методы анализа.
В то же время использование предположения об экспоненциальном распределении длительностей обслуживания вызовов менее оправдано. Случаи экспоненциального распределения обслуживания на практике редки.
Слишком ограничительные требования одновременной показательной распределенности времен обслуживания и пуассоновости входящих потоков кардинально сужают возможность применения результатов к реальным системам. К настоящему времени данный этап развития завершен, исчерпал себя. Интерес математиков к таким задачам невелик.
Математическая теория одноканальных моделей с пуассоновским входящим потоком оформилась усилиями А .Я. Хинчина [34], Б.В. Гнеденко и И.Н. Коваленко [6], Г.П. Климова [15]. Их работы привели к систематизации результатов, относящихся к одноканальным моделям, и посвящены получению точных, неасимптотических результатов на языке преобразования Лапласа-Стилтьеса, которые во многих случаях громоздки на вид.
Объективная закономерность развития теории массового обслуживания заключается в применении асимптотического анализа. Следует отметить, что использование асимптотических методов в теории одноканальных систем оправдано: во-первых, наличием большого числа точных результатов, на базе которых асимптотический анализ приводит к качественным результатам; во-вторых, тем, что часто предельные теоремы раскрывают структурные
-8-
особенности моделей; в-третьих, асимптотические результаты менее громоздкие и более удобные для применения.
В становлении асимптотических методов в теории массового обслуживания важна роль Ю.В. Прохорова [22], A.A. Боровкова [2], Э.А. Даниеляна [11].
Основополагающую роль в становлении асимптотических методов теории массового обслуживания сыграла работа Ю.В. Прохорова [22].
Дадим описание исследуемой модели.
Пусть в одноканальную систему обслуживания с ожиданием вызовы поступают в случайные моменты времени {^}лг1, где 0^/,</2<.... Время обслуживания п - того вызова (п > 1) обозначим ул и пусть ип = tn /0 = 0.
Последовательности {wn} и {vn} неотрицательных случайных величин (СВ) определены на одном и том же вероятностном пространстве (£2,3,/*). Последовательности {мл} и {ул} независимы (друг от друга) и образуют последовательности независимых одинаково распределенных (НОР) СВ с функциями распределения (ФР) Л(/)= 1 - e~at и B(t) на R+ соответственно.
Далее, предполагаем 0 < а, = — = Mw, < +со' и ()</?,= Mv, < +со 9 где М -
а
знак математического ожидания, а также В(+ 0) = 0, что означает, что вероятность «мгновенного» обслуживания равна нулю.
По классификации Кендалла-Башарина данный класс систем обозначается M|G| 1 |оо.
Первый символ характеризует структуру входящего потока вызовов. Второй указывает ФР времени обслуживания. Третий означает число обслуживающих приборов. Четвертый символ говорит о том, что число мест для ожидания неограниченно.
Дисциплина обслуживания — правило выбора вызовов из очереди на обслуживание.
- Київ+380960830922