1. Каковы основные составляющие систем массового обслуживания? Каковы могут быть устройства блоков обслуживания?
2. Каковы могут быть порядки обслуживания очередей?
3. Какими показателями характеризуются системы массового обслуживания?
4. Как определяются основные показатели, характеризующие СМО, для случая экспоненциальных распределений вероятностей поступления заявок и вероятностей времени их обслуживания?
5. Приведите примеры систем, в которых появление заявки на обслуживание является случайной величиной.
6. Приведите примеры систем, в которых время обслуживания (продолжительность обслуживания) заявки является случайной величиной.
3.2 Имитационное моделирование
Имитационное моделирование (ИМ) определяет в моделировании такую область, в которой экспериментальная информация о сложном объекте может быть получена только путем экспериментов с его моделью на ЭВМ.
Имитационное моделирование широко используется на различных этапах жизненного цикла сложных систем: при проектировании – для осуществления многовариантного анализа; при вводе в действие – для поиска "узких" мест; при эксплуатации – для прогнозирования эффекта от возможных модернизаций состава и структуры сложной системы. Сложная система, для которой предполагается создать имитационную модель, должна иметь вероятностный характер функционирования. Поэтому определяющей особенностью имитационного моделирования является требование повторяемости. Выводы, получаемые в результате имитационного моделирования, носят характер статистических показателей, в которых исследуемым параметрам ставятся в соответствие определенные средние значения с набором характеристик их распределения (например, ожидаемое значение с возможными отклонениями), без получения зависимости в аналитическом виде. Особенностью имитационного моделирования является снятие требования единственности критерия, выраженного целевой функцией, так как возможно присоединение к главной цели (например, достижению наименьшей себестоимости или максимума выпуска продукции) дополнительных требований, которые обязательно будут учитываться при поиске оптимального плана управления производством, такие как надежность этого плана.
3.2.1 Общие сведения о GPSSW (язык имитационного моделирования GPSS в среде ОС WINDOWS).
Для моделирования сложных систем, формализуемых в виде систем массового обслуживания, наиболее широко применяется специальный язык программирования GPSS (GeneralPurposeSimulationSystem). В качестве объектов языка используются аналоги таких стандартных компонентов СМО, как заявки, обслуживающие приборы, очереди, что позволяет конструировать сложные имитационные модели, сохраняя привычную терминологию СМО.
Имитационная модель отображает стохастический процесс смены дискретных состояний СМО в непрерывном времени в форме моделирующего алгоритма. Для имитации потоков случайных чисел предусмотрен встроенный датчик случайных чисел, заданный закон распределения получается программным способом. При реализации на ЭВМ имитационной модели производится накопление статистических данных по тем атрибутам модели, характеристики которых являются предметом исследований. По окончании моделирования накопленная статистика обрабатывается, и результаты моделирования получаются в виде выборочных распределений исследуемых величин. Таким образом, при имитационном моделировании систем массового обслуживания речь всегда идет о статистическом моделировании.
Программа, составленная на языке GPSSW, близка к описаниям моделируемых систем на естественном языке, что позволяет конструировать сложные имитационные модели пользователям, не являющимся профессиональными программистами.
Основной модуль пакета представляет собой интегрированную среду, включающую помимо транслятора с входного языка средства ввода и редактирования текста модели, ее отладки и наблюдения за процессом моделирования, а также средства накопления результатов моделирования в базе данных и их статистической обработки. Кроме основного модуля в состав пакета входит модуль создания стандартного отчета GPSS. Этапы моделирования представлены на рис.3.3:
Рисунок 3.3 Процесс моделирования в GPSSW.
Ввод текста исходной программы осуществляется в режиме полноэкранного редактирования, он подвергается трансляции (перевод исходного текста программы во внутренний цифровой код), и в памяти ПК создается так называемая текущая модель, готовая к выполнению.
Текущая модель подвергается "прогону", т.е. непосредственно процессу моделирования. Испытание модели происходит в течение определенного периода, задаваемого пользователем. По результатам прогона создается отчет со стандартными терминами. Процесс моделирования носит циклический характер: в случае необходимости по результатам моделирования вносятся исправления в исходный текст программы, и весь процесс повторяется по вышеприведенной схеме.
Текущая модель, созданная в результате трансляции исходного текста, является совокупностью разного типа объектов, каждый из которых представляет собой некоторый набор чисел в памяти ПК, описывающих свойства и текущее состояние объекта. Объекты GPSSW можно разделить на семь классов: динамические, операционные, аппаратные, статистические, вычислительные, запоминающие и группирующие.
· Динамические объекты, соответствующие заявкам в системах массового обслуживания, называются в GPSSW транзактами. Они «создаются» и «уничтожаются» так, как это необходимо по логике модели в процессе моделирования. С каждым транзактом может быть связано произвольное число параметров, несущих в себе необходимую информацию об этом транзакте. Кроме того, транзакты могут иметь различные приоритеты.
· Операционные объекты GPSSW, называемые блоками, соответствуют операторам-блокам исходной программы. Они формируют логику модели, давая транзактам указания: куда идти и что делать дальше. Модель системы на GPSSW можно представить совокупностью блоков, объединенных в соответствии с логикой работы реальной системы.
· Аппаратные объекты GPSSW — соответствуют обслуживающим приборам (устройствам) в СМО. К ним относятся одноканальные и многоканальные устройства. Одноканальное устройство, которое для краткости далее будем называть просто устройством, может обслуживать одновременно только один транзакт. Многоканальное устройство (МКУ) может обслуживать одновременно несколько транзактов. Многоканальное устройство иногда называют памятью.
· Статистические объекты GPSSW служат для сбора и обработки статистических данных о функционировании модели. К ним относятся очереди и таблицы. Каждая очередь обеспечивает сбор и обработку данных о транзактах, задержанных в какой-либо точке модели, например перед одноканальным устройством.
· К вычислительным объектам GPSSW относятся переменные (например, арифметические) и функции. Они используются для вычисления некоторых величин, заданных арифметическими или логическими выражениями либо табличными зависимостями.
· Запоминающие объекты GPSS/PC обеспечивают хранение в памяти ПК отдельных величин, используемых в модели, а также массивов таких величин. К ним относятся так называемые сохраняемые величины и матрицы сохраняемых величин.
Каждому объекту того или иного класса соответствуют числовые атрибуты, описывающие его состояние в данный момент модельного времени. Кроме того, имеются системные атрибуты, относящиеся не к отдельным объектам, а к модели в целом. Значения атрибутов всех объектов модели по окончании моделирования выводятся в стандартный отчет GPSSW.
3.2.2 Управление последовательностью выполнения программы GPSS: понятие симулятора и таймера модельного времени.
Прогон текущей модели выполняется с помощью специальной управляющей программы, которую называют симулятором (от английского SIMULATE —моделировать, имитировать). Работа GPSS-модели под управлением симулятора заключается в перемещении транзактов от одних блоков к другим аналогично тому, как в моделируемой СМО перемещаются заявки.
В начальный момент времени в GPSS-модели нет ни одного транзакта. В процессе моделирования симулятор генерирует транзакты в определенные моменты времени в соответствии с теми логическими потребностями, которые возникают в моделируемой системе. Подобным же образом транзакты покидают модель в определенные моменты времени в зависимости от специфики моделируемой системы. В общем случае в модели одновременно существует большое число транзактов, однако в каждый момент времени симулятор осуществляет продвижение только какого-либо одного транзакта. Центральной задачей, выполняемой симулятором, является определение того, какой транзакт надо выбрать следующим для продвижения в модели, когда его предшественник прекратил свое продвижение. Продвижение транзактов на обслуживание организуется в порядке убывания приоритетов транзактов, а в пределах каждого уровня приоритета — в порядке поступления транзактов.
Если транзакт начал свое движение, он перемещается от блока к блоку по пути, предписанному блок-схемой. В тот 'момент, когда транзакт входит в некоторый блок, на исполнение вызывается подпрограмма симулятора, соответствующая типу этого блока, а после ее выполнения, при котором реализуется функция данного блока, транзакт «пытается» войти в следующий блок. Такое продвижение транзакта продолжается до тех пор, пока не произойдет одно из следующих возможных событий:
1) транзакт входит в блок, функцией которого является удаление транзакта из модели;
2) транзакт входит в блок, функцией которого является задержка транзакта на некоторое определенное в модели время;
3) транзакт «пытается» войти в следующий блок, однако блок «отказывается» принять его. В этом случае транзакт остается в том блоке, где находился, и позднее будет повторять свою попытку войти в следующий блок. Когда условия в модели изменятся, такая попытка может оказаться успешной, и транзакт сможет продолжить свое перемещение по блок-схеме.
Если возникло одно из описанных выше условий, обработка данного транзакта прекращается, и начинается перемещение другого транзакта. Таким образом, выполнение моделирования симулятором продолжается постоянно.
Каждое продвижение транзакта в модели является событием, которое должно произойти в определенный момент модельного времени. Для того чтобы поддерживать правильную временную последовательность событий, симулятор имеет таймер модельного времени, который автоматически корректируется в соответствии с логикой, предписанной моделью.
Таймер GPSS/PC имеет следующие особенности:
1) регистрируются только целые значения (все временные интервалы в модели изображаются целыми числами);
2) единица модельного времени определяется разработчиком модели, который задает все временные интервалы в одних и тех же, выбранных им единицах;
3) симулятор не анализирует состояние модели в каждый следующий момент модельного времени (отстоящий от текущего на единицу модельного времени), а продвигает таймер к моменту времени, когда происходит ближайшее следующее событие.
Центральной задачей, выполняемой симулятором, является определение того, какой транзакт надо выбрать следующим для продвижения в модели, когда его предшественник прекратил свое продвижение. С этой целью симулятор рассматривает каждый транзакт как элемент некоторого списка. В относительно простых моделях используются лишь два основных списка: список текущих событий и список будущих событий.
Список текущих событий включает в себя те транзакты, планируемое время продвижения которых равно или меньше текущего модельного времени (к последним относятся транзакты, движение которых было заблокировано ранее). Он организуется в порядке убывания приоритетов транзактов, а в пределах каждого уровня приоритета — в порядке поступления транзактов.
Список будущих событий включает в себя транзакты, планируемое время продвижения которых больше текущего времени, т.е. события, связанные с продвижением этих транзактов, должны произойти в будущем. Этот список организуется в порядке возрастания планируемого времени продвижения транзактов.
Симулятор GPSS/PC помещает транзакты в зависимости от условий в модели в тот или иной список и переносит транзакты из списка в список, просматривает списки, выбирая следующий транзакт для обработки, корректирует таймер модельного времени после обработки всех транзактов в списке текущих событий.
3.2.3 Основные операторы GPSSW и связанные с ними объекты.
Исходная программа на языке GPSSW, как и программа на любом языке программирования, представляет собой последовательность операторов. Операторы исходного текста GPSSW записываются и вводятся в ПК в следующем формате (в скобках указаны необязательные части):
[ имя ] операция операнды[; комментарии]
Отдельные операторы могут иметь имя для ссылки на эти операторы в других операторах. Если такие ссылки отсутствуют, то этот элемент оператора не является обязательным.
В поле операции записывается ключевое слово (название оператора), указывающее конкретную функцию, выполняемую данным оператором. Это поле оператора является обязательным.
В полях операндов записывается информация, уточняющая и конкретизирующая выполнение функции, определенной в поле операции. Эти поля в зависимости от типа операции содержат до семи операндов, расположенных в определенной последовательности и обозначаемых обычно первыми буквами латинского алфавита от А до G. В некоторых операторах операнды могут быть опущены, при этом устанавливаются их стандартные значения (по умолчанию). При записи операндов используется позиционный принцип: пропуск операнда отмечается запятой.
Необязательные комментарии в случае их присутствия отделяются от поля операндов точкой с запятой. Комментарии не могут содержать букв русского алфавита.
Ниже рассматриваются операторы, необходимые для начального ознакомления с основами моделирования в GPSSW.
1) Операторы связанные с транзактами.
С транзактами связаны операторы создания, уничтожения и задержки транзактов.
Для создания транзактов, входящих в модель, служит оператор GENERATE (генерировать), имеющий следующий формат:
имяGENERATE A,B,C,D,E
В поле А задается среднее значение интервала времени между моментами поступления в модель двух последовательных транзактов. Поле В показывает отклонение от среднего значения интервала. Если этот интервал постоянен, то поле В не используется. Если интервал поступления транзактов является случайной величиной с равномерным законом распределения вероятностей, то диапазон изменения интервала поступления имеет границы А-В, А+В.
Например,оператор GENERATE 100,40
создает транзакты через случайные интервалы времени, равномерно распределенные на отрезке [60;140].
В поле С задается момент поступления в модель первого транзакта. Если это поле пусто или равно 0, то момент появления первого транзакта определяется операндами А и В.
Поле D задает общее число транзактов, которое должно быть создано оператором GENERATE. Если это поле пусто, то блок генерирует неограниченное число транзактов до завершения моделирования.
В поле Е задается приоритет, присваиваемый генерируемым транзактам. Число уровней приоритетов неограничено, причем самый низкий приоритет — нулевой. Если поле Е пусто, то генерируемые транзакты имеют нулевой приоритет.
Для удаления транзактов из модели служит блок TERMINATE (завершить), имеющий следующий формат:
имяTERMINATE A
Значение поля А указывает, на сколько единиц уменьшается содержимое так называемого счетчика завершений при входе транзакта в данный оператор TERMINATE. Если поле А не определено, то оно считается равным 0, и транзакты, проходящие через такой блок, не уменьшают содержимого счетчика завершений.
Блок TERMINATE A с ненулевым полем А используется для управления временем моделирования (см. рис.3.4):
Рисунок 3.4 Управление временем моделирования в GPSSW.
Начальное значение счетчика завершений устанавливается управляющим оператором START А (начать), предназначенным для запуска прогона модели. Поле А этого оператора содержит начальное значение счетчика завершений. Прогон модели заканчивается, когда содержимое счетчика завершений обращается в 0. Таким образом, в модели должен быть хотя бы один блок TERMINATE с непустым полем А, иначе процесс моделирования никогда не завершится.
Для задержки транзактов на определенный отрезок модельного времени служит блок ADVANCE (задержать), имеющий следующий формат:
имя ADVANCE А,В
Операнды в полях А и В имеют тот же смысл, что и в соответствующих полях блока GENERATE. Следует отметить, что транзакты, входящие в блок ADVANCE, по истечении вычисленного времени задержки продолжают продвижение по блок-схеме. Если вычисленное время задержки равно 0, то транзакт в тот же момент модельного времени переходит в следующий блок.
