- •Набережные Челны 1999
- •2. Теория массового обслуживания
- •2.1 Задачи теории массового обслуживания
- •2.2. Классификация систем массового обслуживания и их основные характеристики
- •2.4. Многоканальная смо с отказами
- •2.5. Одноканальная смо с ожиданием
- •2.8. Многоканальная смо с ожиданием
- •2.9. Смо с ограниченным временем ожидания
- •2.10. Замкнутые системы массового обслуживания
- •2.11. Системы массового обслуживния с не пуассоновскими потоками событий
- •3.3. Оценка количества испытаний,
- •3.4. Генерирование, равномерно
- •3.6. Имитация случайных величин
- •3.7. Имитация случайных потоков
- •3.8. Имитация процессов функционирования
3.7. Имитация случайных потоков
Как правило, потоки событий имитируются с использованием распределений случайного времени между двумя соседними событиями. Если рассматриваемый поток является стационарным и известна плотность или функция распределения времени между событиями, то методами имитации случайных величин вычисляются значения Δt1, Δt2, случайного времени между событиями. Тогда момент наступления i -го события вычисляется по формуле
При этом t0 должно быть задано. Если поток является нестационарным, то для формирования каждого Δti используется свой закон распределения.
Если поток событий является многомерным, то процедура имитации осуществляется методами имитации случайных векторов. При этом, получив случайный вектор и определив моменты наступления событий
следует упорядочить события потока по времени наступления.
Е сли многомерный поток является стационарным и ординарным с многомерной интенсивностью ,то его можно имитировать следующим образом. Моделируется одномерный поток событий с интенсивностью а принадлежность события i - й составляющей потока определяется по жребию с вероятностью
При этом λi есть величина, обратная среднему времени между заявками.
3.8. Имитация процессов функционирования
СМО
Имитацию процессов функционирования СМО будем рассматривать на примере простейшей одноканальной СМО.
Пусть в одноканальную СМО входит одномерный поток, закон распределения которого известен. Длительность обслуживания τ есть случайная величина с заданным законом распределения. Заявки в системе обслуживаются, в порядке очереди, т.е. в том порядке, в котором они поступают в систему. Если поступившая заявка застанет канал занятым, то она встает в очередь и ожидает освобождения канала. Как только
очередь достигнет величины к*, заявки в очередь не встают, а получают отказ. В результате моделирования нужно получить следующие характеристики качества обслуживания: вероятность отказа, среднее время ожидания в очереди, среднее время пребывания заявки в системе.
Процесс функционирования СМО будем рассматривать в интервале времени [0, Т], где Т - заданное время моделирования. Это означает, что заявки, пришедшие в момент времени t >Т, в систему не попадают и не обслуживаются. Если же время поступления заявки t < Т, но время окончания обслуживания (время освобождения канала) toce > Т, то такая заявка считается получившей отказ.
В качестве исходных данных для решения задачи должны быть заданы значения времени моделирования Т, законы распределения потока заявок и времени обслуживания, а также количество реализаций N* , обеспечивающие заданную точность.
Перед началом моделирования задаются начальные условия:
- время поступления "нулевой" заявки t = 0;
время освобождения канала toce = 0;
число обслуженных заявок m = 0;
число заявок, получивших отказ, = 0;
- длина очереди к = 0;
- суммарное время пребывания заявок в системе tnp =0;
суммарное время ожидания заявок в системе tож = 0;
выполненное число имитаций N =0;
Блок-схема имитации данной СМО приведена нарис.31.
Остановимся кратко на работе алгоритма и его основных операторов. Оператор 1 вводит исходную информацию и устанавливает начальные условия. Оператор 2 формирует поступления очередной заявки t. Оператор 3 проверяет выполнение условия t <T . Если это условие выполняется, то заявка попадает в систему, в противном случае она в системе не рассматривается. В блоке 4 проверяется, свободен ли канал. Если канал занят (ω= 1), то в блоке 5 проверяется, есть ли место в очереди. Если есть (ω=0) , то в блоке 6 длина очереди увеличивается, а на последнее место в буфере записывается время поступления заявки (блок 7). Если места в очереди нет (ω= 0 блоке 5), заявка получает отказ и в блоке 8 число отказов увеличивается на единицу.
Если ω = 0 в блоке 4, т.е. канал свободен, в блоке 9 проверяется, есть ли в системе очередь. Если ω= 0 в блоке 9, это означает, что очереди в системе нет, а поскольку канал свободен, то с блока 10 начинается обслуживание вновь поступившей заявки. При этом в блоке 10 за начало обслуживания tH принимается t - время поступления данной заявки. В блоке 11 формируется случайная длительность обслуживания τ. Оператор 12 определяет время освобождения канала от обслуживания данной заявки. В блоке 13 проверяется условие t Т, Если это условие выполнено (ω= 0), то заявка считается обслуженной. Оператор 14 увеличивает число обслуженных заявок m на единицу. В блоке 15 накапливается время пребывания всех заявок в системе, а в 16 - время ожидания в очереди.
Если ω = 0 в блоке 13, то обслуживание заявки не укладывается во время моделирования Т и заявка получает отказ (блок 17). Поскольку в этом случае заявка покидает систему не в момент tосв, а в момент времени Т, то для подсчета tnp и tож в блоках 15,16 необходимо сделать присвоения tосв = T (блок 18).
Если ω = 1 в блоке 9, то в системе свободен канал, и есть очередь. Вновь пришедшую заявку, время которой еще не наступило, так как t > tосв, нужно запомнить в специально отведенной ячейке памяти. Это запоминание имитирует оператор 22, а в 23 вырабатывается признак а — 1 (сформировано время поступления заявки, которое пока не использовано). В блоке 24 имитируется выбор из очереди первой заявки; в блоках 25-29 происходит сдвиг значения в буфере с занулением последнего элемента. В блоке 30 очередь уменьшается, а в 31 за начало обслуживания выбранной заявки принимается момент освобождения канала. Затем имитируется обслуживание заявки в блоках 11-16. После завершения обслуживания в блоке 19 проверяется, есть ли в памяти уже сформированное, но не использованное время поступления заявки. Если нет (ω= 0), то управление передается блоку 2 для формирования времени поступления очередной заявки. Если ω= 1 в блоке 19, то из памяти забирается записанное там t и управление передается блоку 4.
Если ω = 0 в блоке 3, то момент поступления заявки вышел за время моделирования Т. В этом случае за время от toce по T можно обслужить заявку из очереди, если она есть. Поэтому оператор 32 проверяет, есть ли очередь. Если есть ω=0 в (32) , управление передается оператору 24, в котором имитируется выбор заявки из очереди. Если ω= 0 в (32), и это означает конец реализации. В блоке 33 число реализаций имитации увеличивается на единицу, а в блоке 34 оно сравнивается с максимальным. В зависимости от результатов сравнения следует передача управления либо на блок 35, где установка начальных условий для новой реализации t = 0 , toce = 0, к = 0, либо на блок 36 для обработки и выдачи результатов.
Рис.31
Обработка результатов заключается здесь в определении вероятности отказа
среднего времени ожидания заявки в очереди
среднего времени пребывания заявки в системе
Замечание. Аналогично можно разработать блок-схему имитации процессов функционирования других систем массового обслуживания. Широкое применение, благодаря простоте освоения в самых различных областях науки и промышленности, получил язык моделирования CPSS.
ЛИТЕРАТУРА
Анисимов В.В.., Закусило O.K., Донченко B.C. Элементы теории массового обслуживания и асимптотического анализа систем. Киев; Вица школа,1987.
Бронштейн О.И., Духовный И.М. Приоритетное обслуживание в информационных системах. М: Наука, 1976.
Бусленко Н.П. Моделирование сложных систем. М: Наука, 1978.
Вентцель Е.С. Исследование операций. М: Советское радио, 1972.
Гиеденко Б.В., Коваленко И.Н. Введение в теорию
массового обслуживания. М: Наука, 1987.
Ермаков СМ., Михайлов Г.А. Курс статистического моделирования. М: Наука, 1976.
Лившиц А.Л., Мальц Э.А. Статистическое моделирование систем массового обслуживания. М: Советское радио,
1978.
8. Мова В.В., Пономаренко Л.А., Калиновский A.M. Организация приоритетного обслуживания в АСУ. Киев: Техника, 1977.
9. Овчаров Л.А. Прикладные задачи теории массового обслуживания. М: Машиностроение, 1969.
10. Советов Б.Я., Яковлев С.А. Моделирование систем. М: Высшая школа, 1985.
СОДЕРЖАНИЕ
1. Моделирование операций по схеме марковских случайных процессов...........................................................3
1.1. Марковский случайный процесс с дискретными состояниями................................................................3
1.2. Марковский процесс с дискретными состояниями и непрерывным временем. Уравнения Колмогорова для вероятностей состояний................................................................................................6
Поток событий. Простейший поток и его свойства.................................................................................16
Пуассоновские потоки событий и непрерывные марковские цепи........................................................22
Предельные вероятности состояний..........................................................................................................26
Процесс "гибели и размножения"..............................................................................................................31
Циклический процесс..................................................................................................................................37
2. Теория массового обслуживания.......................................................................................................................41
Задачи теории массового обслуживания....................................................................................................41
Классификация систем массового обслуживания и их основные характеристики................................43
Одноканальная СМО с отказами................................................................................................................46
Многоканальная СМО с отказами..............................................................................................................51
Одноканальная СМО с ожиданием (число мест в очереди ограничено).................................................56
2.6. Одноканальная СМО с ожиданием (число мест в очереди не ограничено)...........................................64
Многоканальная СМО с ожиданием (число мест в очереди ограничено).............................................69
Многоканальная СМО с ожиданием (число мест в очереди не ограничено) .........................................74
СМО с ограниченным временем ожидания..............................................................................................77
Замкнутые системы массового обслуживания.........................................................................................81
Системы массового обслуживания с непуассоновскими потоками событий.......................................87
3. Имитационное моделирование систем массового обслуживания..................................................................88
Метод имитационного моделирования....................................................................................................88
Фиксация и обработка результатов имитационного эксперимента.......................................................89
Оценка количества испытаний, необходимого для обеспечения заданной точности ..........................91
Генерирование равномерно распределенной в интервале (0,1) случайной величины.........................94
Имитация случайных событий.............................................................................................................97
Имитация случайных величин...........................................................................................................100
Имитация случайных потоков............................................................................................................105
Имитация процессов функционирования СМО.......................................................................................107
Набор и верстка Ф. С Хасанова
ЛРN 020342 от 7.02.97 г. Подписано в печать 27.12.99 г.
Формат 60x84/16 Бумага газетная Печать офсетная Уч.-изд.л. 7,2 Усл.-печ.л. 7,2 Тираж 300 экз. Заказ 1170/595 Издательство Камского политехнического института
Участок оперативной полиграфии КамПИ, 423810, г. Набережные Челны, Новый город, проспект Мира, 13