Модели массового обслуживания поликомпонентных потоков с ограниченной очередью
ВВЕДЕНИЕ
Настоящая монография посвящена разработке и исследованию комбинированных моделей систем массового обслуживания (СМО) с поликомпонентным потоком требований, произвольным количеством источников и ограничений по длине очереди. Под поликомпонентным потоком понимается суперпозиция потоков заявок разных типов, поступающих из различных источников. Различаются заявки по тому, сколько места они занимают в накопителе или какие ограничения для них действуют.
В последнее десятилетие задача квотирования различного рода ресурсов при ограниченном их количестве приобрела особую остроту в различных предметных областях: телекоммуникации, транспорт, логистика, сфера обслуживания населения и т.п. К подобным техническим объектам можно отнести различные системы телефонной связи, компьютерные сети глобальных и локальных масштабов, системы спутниковой связи. Другими объектами такого рода являются управляющие вычислительные системы и комплексы, в особенности, системы реального времени, где актуальна
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ 6
ГЛАВА 1 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ КОМБИНИРОВАННОЙ МНОГОКАНАЛЬНОЙ СМО С ТРЕХКОМПОНЕНТНЫМ ПОТОКОМ ТРЕБОВАНИЙ 13
1.1. Вывод вспомогательных формул 13
1.2. Вероятности состояний СМО в стационарном режиме 15
1.3. Вероятностные характеристики СМО 17
1.4. Числовые характеристики СМО 19
1.5. Временные характеристики СМО 20
1.6. Резюме 25
ГЛАВА 2 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ОТКРЫТОЙ МНОГОКАНАЛЬНОЙ СМО ПОЛИКОМПОНЕНТНЫХ ПОТОКОВ С ПРОИЗВОЛЬНЫМ КОЛИЧЕСТВОМ ИСТОЧНИКОВ И ОГРАНИЧЕНИЙ ПО ДЛИНЕ ОЧЕРЕДИ 26
2.1. Вероятности состояний СМО в стационарном режиме 26
2.2. Вероятностные характеристики СМО 29
2.3. Числовые характеристики СМО 30
2.4. Временные характеристики СМО 32
2.5. Резюме 39
ГЛАВА 3 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ОТКРЫТОЙ МНОГОКАНАЛЬНОЙ СМО ПОЛИКОМПОНЕНТНЫХ ПОТОКОВ С ПРОИЗВОЛЬНЫМ КОЛИЧЕСТВОМ ИСТОЧНИКОВ И ЕДИНИЧНЫМ ШАГОМ МЕЖДУ ОГРАНИЧЕНИЯМИ НА ДЛИНУ ОЧЕРЕДИ 40
3.1. Вероятности состояний СМО в стационарном режиме 40
3.2. Вероятностные характеристики СМО 41
3.3. Числовые характеристики СМО 42
3.4. Временные характеристики СМО 43
3.5. Резюме 45
ГЛАВА 4 ЧИСЛЕННОЕ ИССЛЕДОВАНИЕ СТАБИЛЬНЫХ РЕЖИМОВ РАБОТЫ СМО ПОЛИКОМПОНЕНТНЫХ ПОТОКОВ ПО ДЛИНЕ ОЧЕРЕДИ И ВРЕМЕНИ ОЖИДАНИЯ 47
4.1. Постановка задачи 47
4.2. Исследование однокомпонентной модели массового обслуживания с ограниченной очередью (М/М/m/Е по Кендаллу) 49
4.3. Исследование двухкомпонентной модели массового обслуживания с двумя ограничениями на длину очереди для каждой компоненты 53
4.4. Исследование трехкомпонентной модели массового обслуживания с тремя ограничениями на длину очереди для каждой компоненты 59
4.5. Исследование влияния эрланговской компоненты на стабильность работы комбинированной модели массового обслуживания с ограниченной очередью (М/М/m/Е & М/М/m/0) 66
4.6. Исследование влияния классической компоненты на стабильность работы комбинированной модели массового обслуживания (М/М/m/Е & М/М/m) 68
4.7. Резюме 73
ГЛАВА 5 ЧИСЛЕННОЕ ИССЛЕДОВАНИЕ СТАБИЛЬНЫХ РЕЖИМОВ РАБОТЫ СМО ПОЛИКОМПОНЕНТНЫХ ПОТОКОВ ПО ЧИСЛУ ЗАЯВОК, НАХОДЯЩИХСЯ ПОД ОБСЛУЖИВАНИЕМ И В СИСТЕМЕ В ЦЕЛОМ 74
5.1. Постановка задачи 74
5.2. Исследование однокомпонентной модели массового обслуживания с ограниченной очередью (М/М/m/Е по Кендаллу) 74
5.3. Исследование двухкомпонентной модели массового обслуживания с двумя ограничениями на длину очереди для каждой компоненты 77
5.4. Исследование трехкомпонентной модели массового обслуживания с тремя ограничениями на длину очереди для каждой компоненты 79
5.5. Исследование влияния эрланговской компоненты на стабильность работы комбинированной модели массового обслуживания с ограниченной очередью (М/М/m/Е & М/М/m/0) 81
5.6. Исследование влияния классической компоненты на стабильность работы комбинированной модели массового обслуживания (М/М/m/Е & М/М/m) 83
5.7. Резюме 86
ГЛАВА 6 КОНЦЕПЦИЯ ОЧЕРЕДЕЙ ВЫСШИХ ПОРЯДКОВ В СМО ПОЛИКОМПОНЕНТНЫХ ПОТОКОВ 87
6.1. Основные определения 87
6.2. О моментах времени ожидания в физической и реальной очередях в СМО с неограниченной очередью 87
6.3. Вероятностные характеристики и моменты длин физической и реальной очередей 90
6.4. Время ожидания обслуживания заявкой в физической очереди 93
6.5. Время ожидания обслуживания заявкой в реальной очереди 94
6.6. Очереди высших порядков 95
6.7. Обобщенные формулы Литтла и классификация очередей высших порядков 96
6.8. Резюме 98
ГЛАВА 7 ЧИСЛЕННОЕ ИССЛЕДОВАНИЕ СТАБИЛЬНЫХ РЕЖИМОВ РАБОТЫ СМО ПОЛИКОМПОНЕНТНЫХ ПОТОКОВ ПО ДЛИНЕ ФИЗИЧЕСКОЙ И РЕАЛЬНОЙ ОЧЕРЕДЕЙ 99
7.1. Постановка задачи 99
7.2. Исследование однокомпонентной модели массового обслуживания с ограниченной очередью (М/М/m/Е по Кендаллу) 101
7.3. Исследование двухкомпонентной модели массового обслуживания с двумя ограничениями на длину очереди для каждой компоненты 104
7.4. Исследование трехкомпонентной модели массового обслуживания с тремя ограничениями на длину очереди для каждой компоненты 108
7.5. Резюме 115
СПИСОК ЛИТЕРАТУРЫ 116
СПИСОК ЛИТЕРАТУРЫ
1. Липаев В.В. Тестирование программ. М.: Радио и связь, 1986. 296 с.
2. Липаев В.В. Надежность программного обеспечения АСУ. М: Энергоиздат, 1981. 240 с.
3. Липаев В.В. Управление разработкой программных средств: Методы, стандарты, технология. М.: Финансы и статистика, 1993. 160 с.
4. Основы теории и проектирования вычислительных приборов и машин управления / Л.Н. Преснухин [и др.]; под ред. проф. Л.Н. Преснухина. – М.: Высшая школа, 1970. 632 c.
5. Технология проектирования комплексов программ АСУ / В.В. Липаев [и др.]; под ред. Ю.В. Астафьева, В.В. Липаева. – М.: Радио и связь, 1983. 264 с.
6. Отладка систем управляющих алгоритмов ЦВМ реального времени / В.В. Липаев [и др.]; под ред. проф. В.В. Липаева. – М.: Советское радио, 1974. 328 с.
7. Липаев В.В. Проектирование математического обеспечения АСУ (системотехника, архитектура, технология). М.: Советское радио, 1977. 400 с.
8. Евсюков К.Н., Колин К.К. Основы проектирования информационно-вычислительных систем. М.: Статистика, 1977. 216 с.
9. Липаев В.В. Распределение ресурсов в вычислительных системах. М.: Статистика, 1979. 247 с.
10. Липаев В.В., Яшков С.Ф. Эффективность методов организации вычислительного процесса в АСУ. М.: Статистика, 1975. 255 с.
11. Колин К.К., Липаев В.В. Проектирование алгоритмов управляющих ЦВМ. М.: Советское радио, 1970. 344 с.
12. Математическое обеспечение управляющих ЦВМ / В.В. Липаев [и др.]. – М.: Советское радио, 1972. 528 с.
13. Романенко В.А. Оптимизация управления технологическими процессами узлового аэропорта как системы массового обслуживания с нестационарными потоками и частичной взаимопомощью каналов // Управление большими системами: сборник трудов. 2012. № 36. С. 209 – 247.
14. Романенко В.А. Математические модели функционирования узловых аэропортов в условиях современного авиатранспортного рынка. Самара: Ас Гард, 2010. 224 с.
15. Андронов А.М. Теория массового обслуживания и научная организация труда в гражданской авиации. М.: РИО МГА СССР, 1969. 118 с.
16. Романенко В.А. Оптимизация параметров системы трансферных авиаперевозок с учетом нечеткой и стохастической неопределенностей // Управление большими системами: сборник трудов. 2013. № 41. С. 285 – 313.
17. Романенко В.А. Нечеткая оптимизация параметров трансферной системы авиаперевозок // Вестник Самарского государственного технического университета. Серия: Технические науки. 2012. №4 (36). С. 73 – 80.
18. Романенко В.А. Оптимизация параметров трансферной системы авиаперевозок в условиях неопределенности // Вестник Самарского государственного аэрокосмического университета им. академика С.П. Королёва (национального исследовательского университета). 2012. № 4 (35). С. 218–228.
19. Романенко В.А. Нечеткая оптимизация сети пассажирских авиалиний на базе системы узловых аэропортов // Вестник Самарского государственного аэрокосмического университета им. академика С.П. Королёва (национального исследовательского университета). 2012. № 5-1 (36). С. 328–334.
20. Романенко В.А. Математическая модель
В большинстве задач прикладного характера замена непуассоновских потоков событий пуассоновскими с теми же интенсивностями приводит к получению решения, которое мало отличается от истинного, а иногда и вовсе не отличается. При этом погрешность решения, как правило, находится в пределах точности исходных данных, которые зачастую известны весьма приближённо. Специальное моделирование различных задач, проведенное методом Монте-Карло [129], показало, что в большинстве случаев эта погрешность ограничена 3 5% и лишь в редких случаях доходит до 10–12%, что вполне приемлемо при решении прикладных задач. Данное положение объясняется тем, что потоки событий, протекающие в реальных системах, в силу предельных теорем теории потоков по своей структуре весьма близки к пуассоновским. Достаточные условия близости суммарного потока, слагаемые которого независимы и равномерно малы, к простейшему потоку были изложены А.Я. Хинчиным [130]. Его ученик Г.А. Ососков выяснил, что эти условия являются и необходимыми. Однако, как показал А.Д. Соловьёв, имеются особые условия, когда погрешность может достигать значительных величин. Согласно знаменитой теореме Б.А. Севастьянова [71], для моделей СМО с отказами стационарное распределение вероятностей состояний системы нечувствительно к распределению обслуживания. Для СМО смешанного типа автором был проведен ряд исследований для случаев, когда экспоненциально распределенное время обслуживания аппроксимируется различными законами распределения. Результаты этих исследований приводятся в приложении 3. В отдельных случаях погрешность