Пусть задана одноканальная разомкнутая СМО с обслуживающим устройством и бесконечной очередью, для которой время поступления заявок распределено по экспоненциальному закону с интенсивностью lп=6,66, а время обслуживания – по экспоненциальному закону с интенсивностью lо=10. Математическое ожидание для этого типа распределения есть величина обратная интенсивности, следовательно заявки в СМО поступают в среднем через МОп=0,15 секунд, а на обслуживание тратиться в среднем МОо=0,1 секунда, т. е. заявки обслуживаются быстрее, чем поступают. Следовательно, в данной СМО лимитирующим является процесс поступления заявок.
Требуется экспериментально установить число реализаций (прогонов) случайного процесса генерации времени обслуживания в устройстве, гарантирующее имитационной модели 95%-ю точность по математическому ожиданию. В нашем случае при МО=0,15 это означает, что нужно установить с какой реализации случайного процесса МО случайной величины гарантированно не выходит за пределы диапазона 0,1425…0,1575, т. е. отклонение рассчитываемого по экспериментальным реализациям случайного процесса значения МО от заданного значения не превышает 5%.
Для произвольного числа реализаций N случайного процесса МО вычисляется по формуле:
.
При программной реализации следует с использованием метода Монте-Карло реализовать генератор случайных чисел по заданному закону распределения с расчетом МО после каждой генерации случайного числа и определением порядкового номера генерации, начиная с которой расчетное значение МО больше не выходит за пределы 5%-го отклонения. Реализация расчета с использованием других математических пакетов выполняется аналогично.
Для заданного примера фрагмент рабочего листа с реализованными формулами в MS Excel имеет вид, представленный на рис. 60-а (в ячейке В3 содержится значение интенсивности), а результат расчета для 1000 реализаций случайного процесса показан на рис. 60-б.
Графическое представление двух экспериментов по 3000 прогонов случайной величины приведено на рис. 61 и 62 (нижний и верхний предел 5%-го отклонения МО от заданного значения показан жирными линиями). Видно, что в первом эксперименте экспериментальное значение числа прогонов Nэ, начиная с которого МО больше не выходило за пределы диапазона допустимого отклонения, составило порядка 1050 генераций, а во втором эксперименте – ровно 1000. Для гарантированного обеспечения 95%-ной точности по МО при испытаниях имитационной модели число прогонов следует выбрать бóльшим, например 1500.
Выполним приближенный детерминированный анализ заданной СМО. Так как в данном случае лимитирующим является процесс поступления и для него выбрано количество прогонов, равное 1500, в СМО поступит 1500 заявок, а время моделирования составит tм=1500´МОп= =1500´0,15=225 секунд. За это время устройство обслуживания смогло бы обслужить tм/МОо=225/0,1=2250 заявок, т. е. все заявки, поступившие в СМО за время моделирования будут обслужены. Коэффициент использования устройства составит КИ=МОо/МОп=0,66[6]. Средняя длина очереди рассчитывается по формуле [27]:
=1,28 заявки.
Среднее время ожидания обслуживания в очереди составит tож= =1,28´0,15=0,192 секунды.
GPSS World.
Базовые понятия GPSS. Модель GPSS состоит из блоков-операторов, которые задают логику функционирования системы и определяют пути движения заявок между элементами системы. В операторах могут происходить события следующих типов:
- создание или уничтожение заявок;
- изменение числовых атрибутов объекта (заявки, устройства, очереди, списка и т. д.);
- задержка заявки на определенный период времени;
- изменение маршрута движения заявки.
Заявки перемещаются в системном времени и пространстве, переходя от одного оператора модели к другому и воздействуя на них. Входя в оператор, заявка вызывает определяемую типом оператора подпрограмму, которая обрабатывает соответствующее событие. Далее заявка в общем случае пытается войти в следующий оператор. Продвижение продолжается до тех пор, пока не окажется, что очередной оператор должен выполнить одну из следующих функций:
- удалить заявку из модели;
- задержать заявку в предыдущем операторе до выполнения некоторых условий;
- задержать заявку на определяемое моделью время.
Тогда начинается продвижение другой заявки и т. д. – до завершения моделирования. За один шаг работы управляющей программы производится поочередный просмотр всех имеющихся процессов и имитация тех, которые могут быть запущены. При этом может освободиться ранее занятый ресурс или оказаться порожденным процесс более высокого приоритета, и просмотр списка процессов можно начать сначала. При описании этих процессов и в сборе итоговой статистики используются таймер модельного времени, стандартные числовые атрибуты (СЧА) и параметры заявок, а также определяемые пользователем переменные, выражения и таблично задаваемые функции. Наиболее сложные аспекты модели – планирование предстоящих событий и очередности их обработки – автоматически реализует планировщик событий (интерпретатор) GPSS.
Работа начинается с составления GPSS-программы. Компиляция организуется по команде Command/Create Simulation. Синтаксический контроль достаточно развит (в частности, контролируется парность скобок). При обнаружении ошибок создается их список. Каждый выбор элемента списка вызывает сообщение о типе ошибки в статусную строку и помещает точку вставки точно перед ошибочным элементом, например «Line 10, Col 20, Invalid Delimiter. Expecting a GPSS Verb».
Операторы языка GPSS. Оператор – это специальное обозначение для определенного действия над операндами (данными). Оператор модели GPSS может быть собственно оператором GPSS, либо PLUS-оператором. В отличие от PLUS-операторов, которые могут содержать несколько строк, операторы GPSS записываются одной строкой и состоят из полей, разделенных пробелами или ограничителями. В общем случае оператор состоит из следующих полей:
- метка (необязательно);
- глагол (обязательно);
- операнды (в зависимости от глагола);
- комментарий (обязательно).
Для вставки оператора GPSS в модельную реализацию можно использовать меню Edit/Insert GPSS Blocks.
Реализация потока заявок с заданным распределением интервалов времени между поступлениями и задержки заявки в обслуживающем устройстве на время обслуживания с заданным законом распределения осуществляется в GPSS World с использованием операторов GENERATE и ADVANCE соответственно. Способы здания типа и параметров распределения приведены в таблице 21.
p1 – параметр равномерного распределения, обычно p1=1; p2 – смещение распределения, обычно p2=0; p3 – величина равная 1/l; p4 – целочисленный параметр b. МО для этого типа распределения равно b/l
p1 – параметр равномерного распределения, обычно p1=1; p2 – МО (m); p3 – стандартное отклонение s
Рассмотрим моделирование в GPSS World заданной одноканальной разомкнутой СМО. Моделирование потока требований выполняется с помощью оператора GENERATE:
GENERATE (Exponential(1,0,0.15))
Очередь задается с помощью операторов QUEUE и DEPART. Оператор QUEUE записывается в виде (в поле операнда дается символьное или числовое имя очереди):
QUEUE OCH1
Заявка будет находиться в очереди до тех пор, пока не поступит сообщение об освобождении устройства обслуживания. Для этого используется оператор SEIZE, который определяет занятость устройства обслуживания, и при освобождении последнего отправляет заявку на обслуживание (в поле операнда дается символьное или числовое имя устройства обслуживания):
SEIZE U1
Выход заявки из очереди фиксируется оператором DEPART (в поле операнда дается символьное или числовое имя очереди):
DEPART OCH1
Далее должно быть задано время пребывания заявки в устройстве обслуживания. Для этого используется оператор ADVANCE:
ADVANCE (Exponential(1,0,0.1))
После обслуживания заявка должна освободить устройство:
RELEASE U1
Парные операторы QUEUE и DEPART для каждой очереди должны иметь одно и то же уникальное имя или номер. Это же относится и к операторам SEIZE и RELEASE.
Выход заявки из системы моделируется следующим оператором (в поле операнда задается число удаляемых из системы заявок):
TERMINATE 1
В реализации модели можно жестко задать число прогонов с использованием оператора START (в поле операнда задается количество заявок, после удаления которых из системы процесс моделирования будет прекращен):
START 1500
Таким образом, имитационная модель заданной одноканальной разомкнутой СМО в среде GPSS World имеет вид, показанный на рис. 63.
Перед началом моделирования нужно установить вывод в стандартном отчете GPSS World тех параметров, которые необходимо получить в процессе моделирования, в меню Edit/Settings. В нашем случае выбору подлежат опции Facilities (устройства обслуживания) и Queues (очереди).
После создания имитационную модель необходимо оттранслировать и запустить на выполнение. Для этого:
- щелкните по пункту Command главного меню системы или нажмите комбинацию клавиш Alt+C;
- щелкните по пункту Create Simulation (создать выполняемую модель) выпадающего меню.
Так как в модели имеется управляющая команда START, то исходная имитационная модель будет выполняться после транслирования, если в ней нет ошибок, а после завершения моделирования будет автоматически сформирован стандартный отчет GPSS World, показанный на рис. 64.
Сравнение результатов имитационного моделирования СМО, выведенных в параметрах отчета, с результатами приближенного детерминированного анализа характеристик СМО, приведено в таблице 22 (расшифровку полей полного стандартного отчета GPSS – см. Приложение 1).
Удовлетворительное совпадение результатов приближенного анализа характеристик СМО с характеристиками, полученными по результатам статистического эксперимента в GPSS World, подтверждает корректность реализации имитационной модели.
Результаты моделирования для устройства обслуживания (FACILITY)
ENTRIES (Число входов)
UTIL. (Коэффициент использования)
0,684
0,66[6]
AVE. TIME (Среднее время обслуживания)
0,103
0,1
Результаты моделирования очередей (QUEUE)
МАХ (Максимальное длина очереди)
–
CONT. (Текущее содержание)
–
ENTRY (Число входов)
ENTRY(0) (Число входов без ожидания в очереди)
–
AVE.CONT. (Средняя длина очереди)
1,312
1,28
AVE.TIME (Среднее время ожидания заявки в очереди)
0,197
0,192
AVE. (-0) (Среднее время ожидания заявки в очереди, рассчитанное для заявок, обслуженных с ожиданием)
0,3
–
КИ очереди устройства СМО равен доле заявок, ожидавших обслуживания в очереди, от общего числа заявок, поступивших в очередь:
где NQj – общее количество заявок, поступивших в очередь j; N0Qj – количество заявок с нулевым временем ожидания в очереди j. Для заданной СМО:
0,656.
Для построения гистограммы времени ожидания заявок в очереди устройства обслуживания в программную реализацию модели следует добавить команду QTABLE формата:
метка QTABLE p1,p2,p3,p4
Метка при построении выводится как заголовок гистограммы; значения параметров: р1 – имя очереди; р2, р3 и р4 – начало координат (левая граница первого интервала), шаг (ширина интервала) и максимальное значение по оси х (количество интервалов).
Гистограмма времени ожидания заявок в очереди устройства, полученная путем табулирования данных с использованием статистической Q-таблицы GIS имеет следующий вид, представленный на рис. 65.
Для вывода табличной формы в стандартном отчете необходимо в меню Edit/Settings выбрать дополнительно опцию Tables (таблицы). Фрагмент стандартного отчета GPSS World – раздел информации о статистических таблицах – для построенной гистограмм имеет вид, показанный на рис. 66.
Варианты индивидуальных заданий
Варианты индивидуальных заданий представлены в таблице 23.
Таблица 23
№
Входной поток
заявок
Обслуживание
в устройстве
Задача оптимизации (модификации)
закон
распределения
параметры
закон
распределения
параметры
эксп.
l=0,01
равн.
10±2
Определить максимально возможную интенсивность поступления, при которой коэффициент использования устройства составит 65%.
равн.
10±2
эксп.
l=0,33
Определить максимально возможное значение параметра поступления А для интервала поступления А±0,2×А, при котором коэффициент использования устройства не превышает 65%.
эксп.
l=6,2
эксп.
l=7,1
Определить максимально возможную интенсивность входного потока, обеспечивающую безочередное обслуживание для 28% заявок.
эксп.
l=0,35
эксп.
l=80
Определить предельную интенсивность, при которой становится невозможным безочередное обслуживание.
эксп.
l=0,035
гамма
l=0,033 b=3
Определить максимальную интенсивность входного потока, при которой очередь можно ограничить 4 заявками.
эксп.
l=0,15
равн.
2±0,2
Определить максимально возможную интенсивность входного потока, обеспечивающую безочередное обслуживание для 20% заявок.
эксп.
l=0,72
эксп.
l=5
Определить интенсивность входного потока, при которой коэффициент использования очереди будет меньше начального значения 10%.
эксп.
l=0,27
гамма
l=0,93 b=3
Определить максимально возможную интенсивность входного потока, обеспечивающую безочередное обслуживание.
гамма
l=0,014 b=2
эксп.
l=0,27
Определить минимально возможную интенсивность обслуживания, при которой возможны потери при условии ограничения очереди 15-ю заявками.
эксп.
l=0,05
эксп.
l=0,045
Определить коэффициент использования очереди, являющийся необходимым условием для обеспечения коэффициента использования устройства равного 80%.
Продолжение таблицы 23
№
Входной поток
заявок
Обслуживание
в устройстве
Задача оптимизации (модификации)
закон
распределения
параметры
закон
распределения
параметры
эксп.
l=0,2
норм.
m=4,8 s=0,5
Определить минимально возможное значение интервала времени между поступлениями заявок для обеспечения коэффициента использования очереди равного 12%.
норм.
m=2,2, s=0,1
эксп.
l=1,1
Определить интенсивность обслуживания, при которой коэффициент использования очереди будет в два раза меньше начального значения.
гамма
l=0,5; b=2
гамма
l=0,5 b=4
Определить максимально возможную интенсивность поступления, при которой процент заявок, ожидающих обслуживания в очереди, составит не более 25%
гамма
l=0,5; b=2
норм.
m=2,2 s=0,1
Определить максимально возможную интенсивность поступления, при которой коэффициент использования устройства составит 45%.
норм.
m=0,5 s=0,05
гамма
l=4,5 b=3
Определить минимально возможное значение интервала времени между поступлениями заявок для обеспечения коэффициента использования устройства равного 30%.
норм.
m=4 s=0,21
равн.
3,5±0,5
Определить значение параметра обслуживания А для распределения времени обслуживания А±0.2А, при котором суммарное время использования очереди в процессе обслуживания будет составлять не более 25% от общего времени эксплуатации системы.
равн.
3,5±0,5
гамма
l=0,5 b=2
Определить, при какой интенсивности обслуживания коэффициент использования очереди составит 50%.
гамма
l=2,5
b=2
равн.
0,5±0,2
Определить, при какой интенсивности поступления очередь обслуживания можно ограничить 4-мя заявками.
норм.
m=3 s=0,09
норм.
m=2 s=0,04
Определить при каком минимальном среднем интервале между поступлениями заявок обслуживание будет безочередным.
гамма
l=0,2
b=2
гамма
l=0,25 b=3
Определить, при каком коэффициенте использования устройства очередь можно ограничить 3-мя заявками.
Продолжение таблицы 23
№
Входной поток
заявок
Обслуживание
в устройстве
Задача оптимизации (модификации)
закон
распределения
параметры
закон
распределения
параметры
гамма
l=0,25; b=2
эксп.
l=0,25
Определить, при каком коэффициенте использования очереди коэффициент использования устройства составит 25%.
равн.
3±1
норм.
m=3 s=1
Определить, при каком параметре s распределения времени обслуживания коэффициент использования очереди не будет превышать 10%.
эксп.
l=0,8
гамма
l=0,62 b=2
Определить, при какой интенсивности обслуживания коэффициент использования очереди будет в два раза меньше начального значения.
эксп.
l=0,72
эксп.
l=5
Определить максимально возможную интенсивность поступления, при которой коэффициент использования устройства составит 15%.
эксп.
l=0,5
норм.
m=20,8 s=2
Определить, при какой интенсивности входного потока средняя длина очереди в процессе обслуживания не будет превышать 25 заявок.
эксп.
l=0,25
гамма
l=0,5 b=2
Определить, при какой интенсивности входного потока среднее время ожидания обслуживания составит 1 секунду.
эксп.
l=0,1
эксп.
l=0,25
Определить, при какой интенсивности входного потока среднее время пребывания заявки в системе составит 15 секунд.
гамма
l=0,5
b=3
равн.
4±0,5
Определить значение параметра обслуживания А для распределения времени обслуживания А±0,1А, при котором только 50% заявок от числа поступивших в систему будут обслужены с ожиданием.
Лабораторная работа №4. Статистическое моделирование многоканальных СМО безприоритетного обслуживания неоднородного потока заявок с ограничением очередей обслуживания
Цель: Моделирование многоканальной многофазной СМО безприоритетного обслуживания с ограничением очередей обслуживания. Модификация СМО заданным способом по условию гарантии безочередного обслуживания для заданного процента заявок входного потока.
Программное обеспечение моделирования: GPSS World.
Теория
СМО бывают одно- и многоканальными в зависимости от числа устройств, параллельно обрабатывающих входной поток заявок; одно- и многофазными в зависимости от числа последовательно включенных устройств. Параметры поступления и обслуживания заявок в СМО, как правило, являются случайными величинами, распределенными по заданному закону.
Основные сведения об имитационных моделях СМО – см. раздел 3.4. конспекта лекций.
.
=1,28 заявки.
=1,28´0,15=0,192 секунды.
0,656.
