Материал: Имитационное и статистическое моделирование — копия

ЧАСТЬ3. ПРАКТИКУМПОИМИТАЦИОННОМУМОДЕЛИРОВАНИЮ

Лабораторная работа 1 МОДЕЛИРОВАНИЕ ОДНОКАНАЛЬНЫХ СМО

Цель работы. Имитационное моделирование одноканальной системы массового обслуживания (СМО).

Содержание работы:

1.Изучение объекта моделирования (одноканальной СМО).

2.Предварительное аналитическое исследование СМО с применением Ms

Excel.

3.Разработка и отладка имитационной модели СМО на GPSS World.

4.Выполнение имитационных экспериментов и анализ результатов.

Краткая теория и методические указания

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

Одноканальная экспоненциальная СМО

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

Таким образом, в экспоненциальной СМО функции распределения вероятностей (ф. р. в.) случайных величин τ и x имеют следующий вид:

где λ – параметр, называемый интенсивностью поступления заявок на вход СМО; μ – интенсивность обслуживания заявок каналом СМО.

Параметр «интенсивность» для экспоненциально распределённой с. в. обратен её математическому ожиданию (м. о.). Обозначая м. о. случайной величины

надчёркиванием, можно записать: λ = 1τ и μ = 1x . Интенсивность λ поступле-

91

ния заявок в СМО – это среднее число заявок, поступающих в единицу времени. Если средний интервал поступления заявок τ измеряется в секундах (с), то интенсивность λ = 1τ измеряется в секундах в минус первой степени (с–1).

Аналогично интенсивность обслуживания заявок μ = 1x – это среднее число заявок, обслуживаемых каналом в единицу времени. Здесь имеется в виду, что канал обслуживает заявки с интенсивностью μ, когда он занят, не простаивает. Когда заявок в системе нет, интенсивность их обслуживания равна нулю.

Параметры λ и μ полностью задают одноканальную экспоненциальную СМО и тем самым однозначно определяют следующие показатели (характеристики) эффективности её функционирования:

ρ – коэффициент загрузки; L – средняя длина очереди;

N – среднее число заявок в СМО;

W – среднее время ожидания заявкой обслуживания; U – среднее время пребывания заявки в СМО.

Приведём без вывода хорошо известные формулы для расчёта этих показателей.

Коэффициент загрузки ρ рассчитывается по формуле

то существует стационарный режим функционирования СМО, в котором средняя длина очереди L не зависит от времени. Как видно из определения коэффициента загрузки (3.2), в случае (3.3) имеем λ ≤ μ, т. е. среднее число заявок λ, поступающих в систему за единицу времени, не превосходит среднего числа заявок μ, которые за единицу времени обслуживаются каналом. Следовательно, канал справляется с поступающей работой. Интенсивность потока заявок на выходе СМО равна интенсивности λ входного потока.

Наряду с ρ и L в стационарном режиме также не зависят от времени, т. е. являются постоянными величинами, и вероятностные характеристики N, W, U. Сами происходящие в СМО процессы, средними значениями которых являются

в случайно выбранный момент времени t в стационарном режиме, wi, ui – время ожидания в очереди и, соответственно, время прохождения через всю систему (через очередь и канал) заявки со случайно выбранным номером i, поступающей в систему в стационарном режиме.

При ρ > 1, наоборот, стационарного режима не существует. Действительно, если ρ > 1, то λ > μ и работа поступает в СМО в среднем быстрее, чем выполняется. Поэтому длина очереди возрастает каждую единицу времени в среднем на (λ – μ). Очередь с ходом времени неограниченно растёт, и стационарной средней длины очереди не существует. Также не существует стационарных показателей N, W, U.

92

В стационарном режиме среднее число N заявок в СМО постоянно. Поэтому среднее число заявок, поступающих в СМО в единицу времени, равно среднему числу заявок, в единицу времени из СМО уходящих. Следовательно, в стационарном режиме интенсивность потока уходящих заявок равна λ. Эта величина меньше, чем интенсивность обслуживания μ, так как канал в стационарном режиме определённую долю времени простаивает. Эта доля времени равна (1–ρ) – коэффициенту простоя СМО. Интенсивность выходного потока заявок равна интенсивности обслуживания, когда канал занят, и равна нулю, когда канал свободен. В среднем же она равна интенсивности поступления заявок. Поэтому среднее число заявок в СМО в стационарном режиме со временем не изменяется, т. е. остаётся постоянным.

Требование (3.3) является условием стационарности не только для экспоненциальных СМО, но и для любых других. «Физический смысл» этого требования состоит в том, чтобы «скорость поступления работы» в систему не превышала «скорости её выполнения» системой.

Коэффициент загрузки ρ в стационарном режиме можно интерпретировать следующими тремя способами:

–как среднюю долю единицы времени, в течение которой канал занят;

–как вероятность застать в случайный момент времени канал занятым;

–как среднее число заявок в канале.

Примечание 1 . Если речь идет об экспоненциальной СМО, то коэффициент загрузки ρ равен также вероятности того, что заявка, приходящая в СМО в стационарном режиме, застанет канал занятым. Этот способ интерпретации показателя ρ для не экспоненциальных СМО в общем случае не имеет места. Например, если интервал τ поступления заявок и интервал x их обслуживания имеют такое распределение, при котором они мало отклоняются от своих средних значений, то, как легко видеть, даже при больших ρ (ρ < 1) вероятность того, что приходящая заявка застанет канал занятым, может быть равна нулю.

Далее в данном цикле лабораторных работ речь будет идти только о стационарных значениях характеристик, определяемых при ρ ≤ 1.

Средняя длина очереди (среднее число заявок в очереди) в одноканальной экспоненциальной СМО L рассчитывается по формуле

93

и числа заявок в канале. Отсюда, поскольку среднее значение суммы чисел равно сумме их средних, вытекает соотношение (3.5).

Зная среднее число заявок в какой-либо части системы, можно легко определить и среднее время пребывания заявок в этой части. Названные две средние величины связаны знаменитой формулой Литтла, которая представляет собой своеобразный «закон природы» для систем массового обслуживания любого вида, не обязательно только экспоненциальных. Эта формула достаточно проста:

nср = λвх tср ,

где λвх – интенсивность поступления заявок в выделенную часть системы; tср – среднее время пребывания заявки в этой части, nср – среднее число заявок в ней.

Формула Литтла справедлива для стационарного режима. Её универсальность можно понять с помощью следующего рассуждения. Поскольку в стационарном режиме среднее число заявок nср в выделенной области системы постоянно, то среднее число заявок, поступающих в неё в единицу времени, т. е. λвх, равно λвых – среднему числу заявок, выходящих из неё в единицу времени. При этом интенсивность выхода заявок λвых складывается из интенсивностей

выхода каждой из nср заявок, т. е. λвых = nср·(1/tср). Отсюда получаем λвх = nср·(1/tср), т. е. формулу Литтла.

Применяя формулу Литтла к очереди в СМО, находим среднее время ожи-

Аналогично вычисляется среднее время пребывания заявки во всей СМО:

Среднее время пребывания можно вычислить и через средние его слагаемых:

U = W + x .

Характеристики (3.2)–(3.7) дают ценную информацию о системе, моделируемой в виде СМО.

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

Обозначения Кендалла – Башарина

Для указания типа СМО используются условные обозначения Кендалла – Башарина, в которых тип системы указывается её основными структурными параметрами в формате:

A|B|K|m.

К основным структурным параметрам, определяющим тип СМО, относятся:

–вид закона распределения интервалов поступления заявок (A);

–вид закона распределения времени обслуживания заявок (B);

–число каналов (K),

–число мест в очереди (m).

94

Первая позиция (A) содержит буквенное обозначение вида закона распределенияFτ (t) для времени τ между поступлениями заявок. Вторая позиция (B) указывает вид закона распределения Fx (t) для времени x обслуживания заявки

каналом. В обозначениях вида закона распределения буква M соответствует экспоненциальному распределению (от слова Марковиан), буква E – распределению Эрланга, R – равномерному распределению и D – детерминированной величине. Порядок эрланговского распределения указывается в виде верхнего индекса при букве E. Равномерное распределение R задаётся на интервале от нуля до двух математических ожиданий. Обозначением RT будем указывать равномерное распределение на интервале от половины м. о. до полутора м. о., обозначением Hr – гиперэкспоненциальное распределение второго порядка с параметром r (r – коэффициент вариации, r2 – квадратичный коэффициент вариации), HBε – ограниченное гиперболическое распределение с параметром ε. Справочная информация по перечисленным распределениям приводится в приложении. Буквой G (general) обозначают распределение произвольного типа.

Третья позиция (K) задаёт число каналов в СМО. Четвёртая позиция (m) определяет число мест в очереди, т. е. её максимальную длину. Заявка, приходящая в систему, когда все места в очереди заняты, теряется.

Рассмотренная выше одноканальная экспоненциальная СМО является системой типа M|M|1. В этом обозначении четвёртая позиция опущена. Это означает, что число мест в очереди бесконечное, т. е. приходящие заявки не теряются.

2. Предварительное аналитическое исследование одноканальной СМО рассмотрим на примере системы R|R|1. Проще всего приближённый расчёт характеристик выполнить с помощью программы Ms Excel. Основной характеристикой СМО является зависимость L(ρ) средней длины очереди от коэффициента загрузки. Для системы M|M|1 эта зависимость, определяемая формулой (3.4), может быть рассчитана точно. Для СМО других типов, за редким исключением, подобных точных аналитических решений не существует. Если исходить из предположения, что систему R|R|1 можно аппроксимировать системой M|M|1, то приближённое представление о характеристике L(ρ) системы R|R|1 можно получить, используя характеристику Lexp(ρ) системы M|M|1:

Погрешность приближения (3.8) нам неизвестна, так как мы не знаем, как сильно на характеристике L(ρ) сказывается переход в СМО от экспоненциальных законов распределения к равномерным.

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

95