Моделирование нестационарных потоков событий

В ряде случаев интенсивность потока может меняться со временем λ (t). Такой поток называется нестационарным. Например, среднее количество за час машин скорой помощи, покидающих станцию по вызовам населения большого города, в течение суток может быть различным. Известно, например, что наибольшее количество вызовов падает на интервалы с 23 до 01 часа ночи и с 05 до 07 утра, тогда как в остальные часы оно вдвое меньше (см. рис. 28.11).

Рис. 28.11. Диаграмма изменения интенсивности потока случайных событий со временем

В этом случае распределение λ (t) может быть задано либо графиком, либо формулой, либо таблицей. А в алгоритме, показанном на рис. 28.6, в место, помеченное (**), нужно будет вставить фрагмент, показанный на рис. 28.12.

Рис. 28.12. Фрагмент алгоритма, реализующий генерацию случайных событий в случае нестационарного потока

Потоки с последействием
(потоки Эрланга)

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

Допустим, события в потоке следуют точно одно за другим каждые 12 минут без отклонений. Интенсивность такого потока будет равна 5 событий в час. Но если события будут идти случайно, например, 12 ± 2 минуты, то и они в среднем дадут также 5 событий в час. Например, за 200 часов произойдет 1000 событий, величина интенсивности 1000/200 = 5 событий в час. Поэтому по данной характеристике потоки нельзя отличить друг от друга. Но очевидно, что второй поток все-таки будет более случайным, чем первый. Тем более, если в потоке события будут следовать друг за другом 12 ± 10 минут.

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

Рис. 29.1. Иллюстрация регулярного и случайного потоков

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

Поток Эрланга k -го порядка — это поток случайных событий, получающийся, если в простейшем (см. лекцию 28) случайном потоке сохранить каждое k -е событие, а остальные отбросить (см. рис. 29.2). Порядок потока — мера последействия потока. То есть обратной величиной к мере случайности потока является его порядок.

Рис. 29.2. Иллюстрация метода получения потоков Эрланга

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

Основано это на том простом и ранее изученном нами факте, что сумма случайных величин есть величина неслучайная (центральная предельная теорема — см. лекцию 25). Чем больше мы сложим случайных величин, тем предсказуемее будет результат (их сумма).

Очевидно, что

— интервал между событиями в потоке Эрланга k -го порядка.

Плотность вероятности распределения интервалов между случайными событиями в потоке Эрланга k -го порядка:

λ_k = λ / k — интенсивность потока Эрланга k -го порядка, где λ — интенсивность простейшего потока Пуассона, а λ_k интенсивность просеянного k раз потока, то есть в k раз меньше.

Параметры закона Эрланга вычисляются по формулам: M_k = 1/ λ_k, σ_k = 1/sqrt(k)/ λ_k,

Обратите внимание, что в потоке Эрланга M ≠ σ, то есть в потоках с последействием равенство M и σ невозможно.

Более того, при k –> ∞ событие происходит строго в размеренное время, так как σ –> 0.

Сравните:
Поток Эрланга 1-го порядка: m = σ ₁ — поток без последействия;
Поток Эрланга i -го порядка: m ≠ σ ₂, при этом (σ ₂ > 0) и (σ ₁ > σ ₂) разброс уменьшается, последействие увеличивается;
Поток Эрланга ∞-го порядка: m ≠ σ = 0 — регулярный поток.

Из этого следует, что порядок потока Эрланга — есть мера последействия потока.

Пример. Рассмотрим пример выхода из строя лампочек на опоре уличного освещения. Примем время наблюдения 100 лет. Из паспортных данных на эти изделия известно, что среднее время работы изделия на отказ составляет 1.5 года; среднеквадратическое отклонение — 0.5 года.

То есть, задано: M_k = 1.5, σ_k = 0.5.

Поскольку M_k ≠ σ_k, то k ≠ 1, то есть мы имеем дело с потоком с последействием. Интенсивность этого потока λ_k = 1/ M_k = 1/1.5 = 0.67. Вычисленная интенсивность потока говорит нам о том, что в течение года в среднем перегорает 0.67 лампочки или 67 лампочек за 100 лет.

Так как σ_k = 1/sqrt(k)/ λ_k, и равна 0.5, то вычислим порядок потока Эрланга: k = 1/ σ ²/ λ_k ² = 1/0.5²/0.67² ≈ 9.

Вычислим интенсивность порождающего потока Пуассона λ = λ_k · k = 0.67 · 9 = 6.

На рис. 29.3 представлен пример алгоритма, реализующего моделирование описанного процесса. Обратите внимание, что берется каждое девятое событие, это обеспечивает достаточно высокую детерминированность потока (то есть малую дисперсию σ_k = 0.5).

Рис. 29.3. Блок-схема алгоритма моделирования появления случайных событий в виде потока Эрланга

Моделирование систем
массового обслуживания

Большой класс систем, которые сложно изучить аналитическими способами, но которые хорошо изучаются методами статистического моделирования, сводится к системам массового обслуживания (СМО).

В СМО подразумевается, что есть типовые пути (каналы обслуживания), через которые в процессе обработки проходят заявки. Принято говорить, что заявки обслуживаются каналами. Каналы могут быть разными по назначению, характеристикам, они могут сочетаться в разных комбинациях; заявки могут находиться в очередях и ожидать обслуживания. Часть заявок может быть обслужена каналами, а части могут отказать в этом. Важно, что заявки, с точки зрения системы, абстрактны: это то, что желает обслужиться, то есть пройти определенный путь в системе. Каналы являются также абстракцией: это то, что обслуживает заявки.

Заявки могут приходить неравномерно, каналы могут обслуживать разные заявки за разное время и так далее, количество заявок всегда весьма велико. Все это делает такие системы сложными для изучения и управления, и проследить все причинно-следственные связи в них не представляется возможным. Поэтому принято представление о том, что обслуживание в сложных системах носит случайный характер.

Примерами СМО (см. табл. 30.1) могут служить: автобусный маршрут и перевозка пассажиров; производственный конвейер по обработке деталей; влетающая на чужую территорию эскадрилья самолетов, которая «обслуживается» зенитками ПВО; ствол и рожок автомата, которые «обслуживают» патроны; электрические заряды, перемещающиеся в некотором устройстве и т. д.

Таблица 30.1. Примеры систем массового обслуживания

СМО Заявки Каналы Автобусный маршрут и перевозка пассажиров Пассажиры Автобусы Производственный конвейер по обработке деталей Детали, узлы Станки, склады Влетающая на чужую территорию эскадрилья самолетов, которая «обслуживается» зенитками ПВО Самолеты Зенитные орудия, радары, стрелки, снаряды Ствол и рожок автомата, которые «обслуживают» патроны Патроны Ствол, рожок Электрические заряды, перемещающиеся в некотором устройстве Заряды Каскады технического устройства

Но все эти системы объединены в один класс СМО, поскольку подход к их изучению един. Он состоит в том, что, во-первых, с помощью генератора случайных чисел разыгрываются случайные числа, которые имитируют СЛУЧАЙНЫЕ моменты появления заявок и время их обслуживания в каналах. Но в совокупности эти случайные числа, конечно, подчинены статистическим закономерностям.

К примеру, пусть сказано: «заявки в среднем приходят в количестве 5 штук в час». Это означает, что времена между приходом двух соседних заявок случайны, например: 0.1; 0.3; 0.1; 0.4; 0.2, как это показано на рис. 30.1, но в сумме они дают в среднем 1 (обратите внимание, что в примере это не точно 1, а 1.1 — но зато в другой час эта сумма, например, может быть равной 0.9); и только за достаточно большое время среднее этих чисел станет близким к одному часу.

Рис. 30.1. Случайный процесс прихода заявок в СМО

Результат (например, пропускная способность системы), конечно, тоже будет случайной величиной на отдельных промежутках времени. Но измеренная на большом промежутке времени, эта величина будет уже, в среднем, соответствовать точному решению. То есть для характеристики СМО интересуются ответами в статистическом смысле.

Итак, систему испытывают случайными входными сигналами, подчиненными заданному статистическому закону, а в качестве результата принимают статистические показатели, усредненные по времени рассмотрения или по количеству опытов. Ранее, в лекции 21 (см. рис. 21.1), мы уже разработали схему для такого статистического эксперимента (см. рис. 30.2).

Рис. 30.2. Схема статистического эксперимента для изучения систем массового обслуживания

Во-вторых, все модели СМО собираются типовым образом из небольшого набора элементов (канал, источник заявок, очередь, заявка, дисциплина обслуживания, стек, кольцо и так далее), что позволяет имитировать эти задачи типовым образом. Для этого модель системы собирают из конструктора таких элементов. Неважно, какая конкретно система изучается, важно, что схема системы собирается из одних и тех же элементов. Разумеется, структура схемы будет всегда различной.

Перечислим некоторые основные понятия СМО.

Каналы — то, что обслуживает; бывают горячие (начинают обслуживать заявку в момент ее поступления в канал) и холодные (каналу для начала обслуживания требуется время на подготовку). Источники заявок — порождают заявки в случайные моменты времени, согласно заданному пользователем статистическому закону. Заявки, они же клиенты, входят в систему (порождаются источниками заявок), проходят через ее элементы (обслуживаются), покидают ее обслуженными или неудовлетворенными. Бывают нетерпеливые заявки — такие, которым надоело ожидать или находиться в системе и которые покидают по собственной воле СМО. Заявки образуют потоки — поток заявок на входе системы, поток обслуженных заявок, поток отказанных заявок. Поток характеризуется количеством заявок определенного сорта, наблюдаемым в некотором месте СМО за единицу времени (час, сутки, месяц), то есть поток есть величина статистическая.

Очереди характеризуются правилами стояния в очереди (дисциплиной обслуживания), количеством мест в очереди (сколько клиентов максимум может находиться в очереди), структурой очереди (связь между местами в очереди). Бывают ограниченные и неограниченные очереди. Перечислим важнейшие дисциплины обслуживания. FIFO (First In, First Out — первым пришел, первым ушел): если заявка первой пришла в очередь, то она первой уйдет на обслуживание. LIFO (Last In, First Out — последним пришел, первым ушел): если заявка последней пришла в очередь, то она первой уйдет на обслуживание (пример — патроны в рожке автомата). SF (Short Forward — короткие вперед): в первую очередь обслуживаются те заявки из очереди, которые имеют меньшее время обслуживания.

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

Пусть имеется два магазина. В магазине № 1 обслуживание осуществляется в порядке очереди, то есть здесь реализована дисциплина обслуживания FIFO (см. рис. 30.3).

Рис. 30.3. Организация очереди по дисциплине FIFO

Время обслуживания t _{обслуж.} на рис. 30.3 показывает, сколько времени продавец затратит на обслуживание одного покупателя. Понятно, что при покупке штучного товара продавец затратит меньше времени на обслуживание, чем при покупке, скажем, сыпучих продуктов, требующих дополнительных манипуляций (набрать, взвесить, высчитать цену и т. п). Время ожидания t _ожид.показывает, через какое время очередной покупатель будет обслужен продавцом.

В магазине № 2 реализована дисциплина SF (см. рис. 30.4), означающая, что штучный товар можно купить вне очереди, так как время обслуживания t _{обслуж.} такой покупки невелико.

Рис. 30.4. Организация очереди по дисциплине SF

Как видно из обоих рисунков, последний (пятый) покупатель собирается приобрести штучный товар, поэтому время его обслуживания невелико — 0.5 минут. Если этот покупатель придет в магазин № 1, он будет вынужден выстоять в очереди целых 8 минут, в то время как в магазине № 2 его обслужат сразу же, вне очереди. Таким образом, среднее время обслуживания каждого из покупателей в магазине с дисциплиной обслуживания FIFO составит 4 минуты, а в магазине с дисциплиной обслуживания КВ — лишь 2.8 минуты. А общественная польза, экономия времени составит:(1 – 2.8/4) · 100% = 30 процентов! Итак, 30% сэкономленного для общества времени — и это лишь за счет правильного выбора дисциплины обслуживания.

Специалист по системам должен хорошо понимать ресурсы производительности и эффективности проектируемых им систем, скрытые в оптимизации параметров, структур и дисциплинах обслуживания. Моделирование помогает выявить эти скрытые резервы.

При анализе результатов моделирования важно также указать интересы и степень их выполнения. Различают интересы клиента и интересы владельца системы. Заметим, что эти интересы совпадают не всегда.

Судить о результатах работы СМО можно по показателям. Наиболее популярные из них:

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

Судить о качестве полученной системы нужно по совокупности значений показателей. При анализе результатов моделирования (показателей) важно также обращать внимание на интересы клиента и интересы владельца системы, то есть минимизировать или максимизировать надо тот или иной показатель, а также на степень их выполнения. Заметим, что чаще всего интересы клиента и владельца между собой не совпадают или совпадают не всегда. Показатели будем обозначать далее H = { h ₁, h ₂, …}.

Параметрами СМО могут быть: интенсивность потока заявок, интенсивность потока обслуживания, среднее время, в течение которого заявка готова ожидать обслуживания в очереди, количество каналов обслуживания, дисциплина обслуживания и так далее. Параметры — это то, что влияет на показатели системы. Параметры будем обозначать далее как R = { r ₁, r ₂, …}.

Пример. Автозаправочная станция (АЗС).

1. Постановка задачи. На рис. 30.5 приведен план АЗС. Рассмотрим метод моделирования СМО на ее примере и план ее исследования. Водители, проезжая по дороге мимо АЗС по дороге, могут захотеть заправить свой автомобиль. Хотят обслужиться (заправить машину бензином) не все автомобилисты подряд; допустим, что из всего потока машин на заправку в среднем заезжает 5 машин в час.

Рис. 30.5. План моделируемой АЗС

На АЗС две одинаковые колонки, статистическая производительность каждой из которых известна. Первая колонка в среднем обслуживает 1 машину в час, вторая в среднем — 3 машины в час. Владелец АЗС заасфальтировал для машин место, где они могут ожидать обслуживания. Если колонки заняты, то на этом месте могут ожидать обслуживания другие машины, но не более двух одновременно. Очередь будем считать общей. Как только одна из колонок освободится, то первая машина из очереди может занять ее место на колонке (при этом вторая машина продвигается на первое место в очереди). Если появляется третья машина, а все места (их два) в очереди заняты, то ей отказывают в обслуживании, так как стоять на дороге запрещено (см. дорожные знаки около АЗС). Такая машина уезжает прочь из системы навсегда и как потенциальный клиент является потерянной для владельца АЗС. Можно усложнить задачу, рассмотрев кассу (еще один канал обслуживания, куда надо попасть после обслуживания в одной из колонок) и очередь к ней и так далее. Но в простейшем варианте очевидно, что пути движения потоков заявок по СМО можно изобразить в виде эквивалентной схемы, а добавив значения и обозначения характеристик каждого элемента СМО, получаем окончательно схему, изображенную на рис. 30.6.

Рис. 30.6. Эквивалентная схема объекта моделирования

2. Метод исследования СМО. Применим в нашем примере принцип последовательной проводки заявок (подробно о принципах моделирования см. лекцию 32). Его идея заключается в том, что заявку проводят через всю систему от входа до выхода, и только после этого берутся за моделирование следующей заявки.

Для наглядности построим временную диаграмму работы СМО, отражая на каждой линейке (ось времени t) состояние отдельного элемента системы. Временных линеек проводится столько, сколько имеется различных мест в СМО, потоков. В нашем примере их 7 (поток заявок, поток ожидания на первом месте в очереди, поток ожидания на втором месте в очереди, поток обслуживания в канале 1, поток обслуживания в канале 2, поток обслуженных системой заявок, поток отказанных заявок).

Для генерации времени прихода заявок используем формулу вычисления интервала между моментами прихода двух случайных событий (см. лекцию 28):

В этой формуле величина потока λ должна быть задана (до этого она должна быть определена экспериментально на объекте как статистическое среднее), r — случайное равномерно распределенное число от 0 до 1 из ГСЧ или таблицы, в которой случайные числа нужно брать подряд (не выбирая специально).

Задача. Сгенерируйте поток из 10 случайных событий с интенсивностью появления событий 5 шт/час.

Решение задачи. Возьмем случайные числа, равномерно распределенные в интервале от 0 до 1 (см. таблицу), и вычислим их натуральные логарифмы (см. табл. 30.2).

Таблица 30.2. Фрагмент таблицы случайных чисел и их логарифмов

rрр[0; 1] ln(rрр[0; 1]) 0.0333 –3.4022 0.3557 –1.0337 0.2172 –1.5269 0.5370 –0.6218

Формула пуассоновского потока определяет расстояние между двумя случайными событиями следующим образом: t = –Ln(r_рр)/ λ. Тогда, учитывая, что λ = 5, имеем расстояния между двумя случайными соседними событиями: 0.68, 0.21, 0.31, 0.12 часа. То есть события наступают: первое — в момент времени t = 0, второе — в момент времени t = 0.68, третье — в момент времени t = 0.89, четвертое — в момент времени t = 1.20, пятое — в момент времени t = 1.32 и так далее. События — приход заявок отразим на первой линейке (см. рис. 30.7).

Рис. 30.7. Временная диаграмма работы СМО

Берется первая заявка и, так как в этот момент каналы свободны, устанавливается на обслуживание в первый канал. Заявка 1 переносится на линейку «1 канал».

Время обслуживания в канале тоже случайное и вычисляется по аналогичной формуле:

где роль интенсивности играет величина потока обслуживания μ ₁ или μ ₂, в зависимости от того, какой канал обслуживает заявку. Находим на диаграмме момент окончания обслуживания, откладывая сгенерированное время обслуживания от момента начала обслуживания, и опускаем заявку на линейку «Обслуженные».

Заявка прошла в СМО весь путь. Теперь можно, согласно принципу последовательной проводки заявок, также проимитировать путь второй заявки.

Если в некоторый момент окажется, что оба канала заняты, то следует установить заявку в очередь. На рис. 30.7 это заявка с номером 3. Заметим, что по условиям задачи в очереди в отличие от каналов заявки находятся не случайное время, а ожидают, когда освободится какой-то из каналов. После освобождения канала заявка поднимается на линейку соответствующего канала и там организуется ее обслуживание.

Если все места в очереди в момент, когда придет очередная заявка, будут заняты, то заявку следует отправить на линейку «Отказанные». На рис. 30.7 это заявка с номером 6.

Процедуру имитации обслуживания заявок продолжают некоторое время наблюдения T _н. Чем больше это время, тем точнее в дальнейшем будут результаты моделирования. Реально для простых систем выбирают T _н, равное 50—100 и более часов, хотя иногда лучше мерить эту величину количеством рассмотренных заявок.

⇐ Предыдущая16171819202122232425Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: