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

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

1. Элементы системы массового обслуживания.

2. Дисциплины буферизации и диспетчеризации.

3. Особенности имитационного моделирования.

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

Рассмотрим основные элементы и общие принципы имитационного моделирования на примере системы информационно-вычислительного обслуживания. Каждая СМО в общем случае состоит из следующих основных элементов:

· блок обслуживания;

· поток заявок на обслуживание;

· очередь в ожидании обслуживания.

Рекомендуемые материалы

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

Поток заявок, как правило, описывается вероятностным законом их поступления в СМО, определяющим длительности интервалов между двумя последовательно поступающими заявками. Эти длительности часто являются статистически независимыми, и их распределение не изменяется в течение некоторого достаточно продолжительного промежутка времени.

Очередь возникает в момент поступления в систему очередной заявки, если канал занят обслуживанием ранее поступившего требования.

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

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

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

Например, выбор исключаемой заявки может быть осуществлен по критерию времени ожидания в очереди: исключается самая «старая» или самая «свежая» заявка.

Правила выбора заявок из очереди для обслуживания называют дисциплинами диспетчеризации. Дисциплины диспетчеризации подразделяются на бесприоритетные и приоритетные. К бесприоритетным дисциплинам относятся:

• обслуживание в порядке поступления заявок: «первый пришел — первым обслужен»;

• обслуживание заявок в инверсном порядке: «последним пришел — первым обслужен»;

• обслуживание со случайным выбором из очереди.

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

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

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

Каждая система поддержки принятия решения носит сугубо индивидуальный характер, поскольку определяется конкретным содержанием решаемой управленческой проблемы и особенностями процедуры принятия решений в той или иной организации. Если процедуры принятия решений регулярны, устойчивы, то состав и последовательность функционирования рассматриваемой системы закрепляются в качестве нормативных методик, использующих преимущественно формальные модели и методы при незначительном использовании диалоговых процедур. Например, периодическое планирование производственной деятельности. Системы поддержки принятия решений эффективны при решении периодически возникающих проблемных ситуаций с высокой степенью неопределенности и, как правило, не имеющих полных аналогов в прошлом. Системы поддержки приятия решений разрабатываются индивидуально под каждую проблему. В их состав включают преимущественно логико-эвристические и экспертные методы и модели, а главную роль начинают играть диалоговые процедуры. В этих условиях, для оценки последствий принимаемых в условиях неопределенности и используются имитационные модели.

Первый признак имитационной модели — ориентированность на такую схему. В ходе экспериментов с имитационной моделью эксперты задают ей вопросы, модель доставляет ответы, эксперты их анализируют и формируют знания, суждения, решения.

Вторая особенность имитационной модели — более подробное, чем в классических моделях, отображение структуры прототипа в структуру модели, использующее богатые и гибкие возможности современных средств организации и обработки данных. В этом отличие современных имитационных моделей от дескриптивных эконометрических моделей, хотя последние можно рассматривать как частный случай имитационной модели. Эконометрическая модель устроена как «черный ящик» и не отображает внутренних связей в прототипе. Ее параметры оцениваются в результате статистической обработки наблюдений за действительностью. Может показаться, что эти оценки верны только в условиях действующего экономического механизма. Модель становится непригодной для проектируемого экономического механизма, более или менее существенно отличающегося от действующего. Особенно актуально изучение свойств экономических механизмов, радикально отличных от прежних. Если конструктор модели вынужден по такой причине отказаться от моделирования «в лоб», он пытается понять и отобразить внутренние причинно-следственные связи и механизмы. Для этого модель представляется в виде совокупности компонентов. Для каждого компонента конструктор должен быть способен построить правдоподобную модель, в которой необходимо отобразить все существенные отношения. Такой способ приводит к правдоподобной модели — особенно если в качестве компонентов модели выбирать модели компонентов системы прототипа: предприятия, цеха, банки, регионы, транспортные сети, органы управления, группы населения. Усложнение структуры имитационной модели вызывается стремлением использовать ее в качестве средства доброкачественности решений, формируемых экспертом или нормативной (т.е. более простой) моделью. Для моделирования первичных структурных единиц иногда удается привлекать и классические подходы. Так, для отображения технологических процессов уместно использовать эконометрические промышленные и сельскохозяйственные производственные функции, явно не зависящие от механизма управления производством. Для построения функций спроса могут быть использованы оптимизационные модели, т.к. здесь критерий оптимальности и ограничения можно иногда формулировать обоснованно.

Третья особенность имитационных моделей состоит в том, что модель, как правило, не «картинка» как, скажем, статическая модель межотраслевого баланса. В статической модели межотраслевого баланса разновременные события «склеены» в одномоментные. Имитационную модель скорее можно рассматривать как «фильм», отображающий функционирование прототипа в виде смен состояний модели в последовательные моменты и — в этой связи — появление разных способов моделирования времени. Эта особенность родилась из отмеченной выше потребности не только получить подходящие решения (роль нормативной модели на этом завершается), но и включить в модель компоненты, отображающие отклик системы на принятые решения — в виде показателей ее функционирования. Классическую динамическую балансовую модель и ее разновидности можно рассматривать как частный, «вырожденный» случай имитационной модели. Хотя функционирование и моделируется в этой модели, но моменты производства, распределения и потребления ресурсов сводятся в один. В результате модель слишком жестко описывает важные явления, связанные с разными ритмами производств поставщиков и потребителей, последствия срывов договоров поставки и т. п. В «невырожденных» имитационных моделях получает отражение то реальное обстоятельство, что процессу потребления ресурсов предшествуют процессы производства и распределения.

Четвертая особенность имитационной модели — свободный выбор средств для моделирования процессов. В то время как классические модели используют сравнительно узкий круг математических конструкций: линейные уравнения и неравенства, оптимизация линейных и дробно-линейных функций, регрессионный

анализ, методы теории массового обслуживания. Модели процессов — это компьютерные и человеко-компьютерные алгоритмы.

Они:

· вычисляют значения «модельного» времени;

· изменяют значения переменных, представляющих состояния компонентов модели;

· генерируют по ходу моделирования новые компоненты (например, сдаваемые в эксплуатацию строящиеся промышленные предприятия (жилые кварталы) или выставляемые платежные требования);

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

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

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

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

Приведем несколько примеров, иллюстрирующих возможность представления реальных систем информационно-вычислительного обслуживания

в виде СМО.

Пример 1.

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

Рисунок 1.3 — Однофазная многоканальная СМО

Пример 2

Рассмотрим пример несколько более сложной СМО. Предположим, что анализируется часть вычислительной системы, состоящая из устройств, изображенных на Рисунке 1.4.

Рисунок 1.4 — Фрагмент вычислительной системы

Здесь к процессору с оперативной памятью подсоединены через селекторный канал (СК) и устройства управления (УУ) два накопителя на магнитных лентах и три накопителя на магнитных дисках.

На устройствах внешней памяти располагаются наборы данных — файлы.

Поток запросов от пользователей на решение задач представляется неограниченным источником заявок.

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

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

В этом случае рассматриваемая модель может быть представлена следующим образом (Рисунок  1.5).

Рисунок 1.5 — Модель системы

информационно-вычислительного обслуживания

Модель состоит из двух одноканальных СМО (S₁ — процессор, S₄ —селекторный канал) и двух многоканальных СМО (S₂ — внешняя память на магнитных лентах, S₃ — внешняя память на магнитных дисках).

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

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

Подтвердим данное утверждение, построив имитационную модель для системы массового обслуживания, рассмотренной в первом примере.

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

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

В качестве критерия оптимальности рассматриваемой модели может быть взят следующий функционал:

где    З₀ — текущие затраты, связанные с содержанием оборудования

(компьютеры);

Зп — заработная плата специалистов-ремонтников;

Q — стоимость работ, выполненных на компьютерах;

V — количество ремонтного персонала.

Оптимизация такого функционала аналитическими методами практически невозможна вследствие его нелинейности. В то же самое время, построив имитационную модель (алгоритм) изучаемой системы, можно рассчитать значения функционала для различных значений величины V: (1, 2, 3,...) и выбрать рациональное (здесь в силу дискретности модели — оптимальное) решение (Рисунок 1.6).

Рисунок 1.6 — График целевой функции моделируемой системы

Динамика функционирования рассматриваемой системы характеризуется следующими состояниями обслуживаемого оборудования:

• начало работы компьютера после его обслуживания;

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

• начало обслуживания компьютера.

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

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

Для практического осуществления имитационного эксперимента с рассматриваемой системой должны быть заданы (известны) законы распределения времени работы U_i и времени обслуживания T_i, (ремонта) каждой единицы оборудования. Рассматриваемый аппарат имитационного моделирования позволяет ограничиться получением гистограмм распределения, что значительно упрощает процесс подготовки данных для модели (Рисунок 1.7). За тем по гистограмма строятся кумуляты (Рисунок 1.8).

Рисунок 1.7 — Гистограммы исходных данных для моделирования

Рисунок 1.8 — Кумуляты исходных данных для моделирования

Тогда для определения случайных величин U_i и T_i с помощью датчика случайных чисел в диапазоне 0-1 вырабатываются случайные числа, определяющие случайным образом соответствующие величины U_i и T_i.

Прежде чем приступить к разработке моделирующего работу изучаемой системы алгоритма, рассмотрим рисунок, иллюстрирующий начальный фрагмент моделирования системы обслуживания трех компьютеров (i = 1, 2, 3) одним специалистом-ремонтником (V =1) — рисунок 1.9.

Логика работы моделирующего алгоритма будет следующей.

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

2. Определение ближайшего момента изменения состояния системы.

Формально это реализуется просмотром величин t_i и определением минимальной из них (т. е. min t_i,).

3. Определение типа события: поступление заявки на обслуживание или окончание обслуживания.

4. Выполнение действий, определяемых характером текущего события:

а) действия, связанные с поступлением заявки.

Проверка состояния канала обслуживания (простой или работа по обслуживанию). Если канал обслуживания простаивает, то необходимо начать обслуживание поступившей заявки: сгенерировать время обслуживания компьютера i (U_i), рассчитать время окончания обслуживания (t_i : = t_i + Т_i), изменить состояние компьютера i на рабочее. Если канал обслуживания занят обслуживанием, поставить поступившую заявку в очередь на обслуживание и увеличить длину очереди на 1 (L:=L + 1).

б) действия, связанные с окончанием обслуживания

Проверка состояния очереди (пустая или непустая). Если очередь пуста, объявить простой канала обслуживания. Если очередь не пуста, то в соответствии с принятой дисциплиной  диспетчеризации начать обслуживание конкретного компьютера, стоящего в очереди, уменьшить длину очереди на единицу, рассчитать время простоя оборудования в очереди. Далее необходимо сгенерировать время работы компьютера i (U_i), рассчитать время окончания обслуживания (t_i : = t_i + Т_i), — время поступления очередной заявки на обслуживание компьютера i.

Некоторые пояснения к моделирующему алгоритму.

1. Для того чтобы отличать рабочее состояние компьютера от состояния обслуживания ее, в первом случае величина  записывается t_i в памяти моделирующей ЭВМ со знаком «минус», во втором случае — со знаком «плюс».

2. Ближайший момент изменения состояния системы в этом случае должен определяться следующим образом:  = min | t_i |.

3. У оборудования, ожидающего обслуживания в очереди, состояние может измениться лишь тогда, когда закончится обслуживание какой-нибудь другой единицы оборудования. Поэтому, чтобы при определении  = min | t_i | не рассматривать компьютеры, ожидающие обслуживания, их текущее время (время постановки в очередь) запоминается в памяти моделирующей ЭВМ (t_i,0), а вместо t_i  записывается наибольшее из чисел, с которыми может оперировать моделирующая ЭВМ (математически это ).

4. В результате в памяти ЭВМ (в поле t_i,0 ) будет фиксирована очередь заявок на обслуживание и время их поступления в нее, которое необходимо знать для практической реализации выбранной дисциплины диспетчеризации. В нашем случае возьмем для конкретности дисциплину: «первым пришел — первым обслужен», формально реализуемую в алгоритме по формуле  = min | t_i,0 |.

5. После «изъятия» i-й единицы оборудования из очереди в соответствующую ячейку памяти t_i0 заносится максимально большое для данной моделирующей ЭВМ число (математически —  ). Алгоритм, моделирующий рассматриваемую систему, представлен на рисунке 1.10. Результаты имитационного моделирования целесообразно оформить в виде таблицы, которая может иметь, например, следующий вид (таблица 1.4).

Рисунок 1.9 — Принципиальная схема моделирования СМО

Таблица 1.4 ― Результаты имитационного моделирования

Формула I:

Формула II:

Формула III: Т_m×V (время простоя)

Лекция "136 Сферы общественной жизни" также может быть Вам полезна.

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

Рисунок 1.10 – Моделирующий алгоритм

(Т_м – глубина моделирования, L  - длина очереди на обслуживание)