Многоканальные системы с ограниченной очередью

Пусть в системе имеется m каналов обслуживания и n мест в очереди. Если свободных мест в очереди нет, заявка получает отказ. Граф состояний такой системы имеет вид (рис. 2.8):

l

l

l

l

l

l

Sm+n

Sm

Sm+1

mm

mm

mm

mm

2m

m

...

...

S0

S1

S2

Рис. 2.8. Граф многоканальной системы с очередью

Граф динамики многоканальной системы такого вида состоит из двух частей: до состояния S_m – все m каналов занято, очереди нет, и после от S_m+1 – все m заняты, одна заявка в очереди до S_m+n – все каналы заняты, n заявок в очереди. Общее количество состояний в графе конечно и равно m + n + 1, включая нулевое состояние, где n – величина, ограничивающая длину очереди (в другой терминологии – n – количество мест в накопителе очереди), m – количество каналов обслуживания.

Построим систему уравнений Эрланга для этой СМО и разрешим её. Обозначим , тогда формулы вероятностей состояний имеют вид:

Основные характеристики системы M/M/m/n:

вероятность отказа P_отк = Р_m+n = 1/m! ρ^m+n / mⁿ P₀;

вероятность обслуживания Q = Р_обс = 1– P_отк;

абсолютная пропускная способность А = λQ;

среднее количество занятых каналов К = A/µ;

средняя длина очереди L = M[L] = 1P_m+1 + 2P_m+2 +…nP_m+n;

среднее время ожидания Т = L/λ.

Пример. На станцию техобслуживания с двумя подъёмниками для текущего ремонта поступает простейший поток заявок с плотностью λ = 1,5 маш./час. Во дворе могут находиться, дожидаясь обслуживания не более 3-х машин. Среднее время ремонта Т_обс = 2 час. Найти основные характеристики работы станции.

Решение. Имееммарковскую СМО M/M/2/3 с параметрами:
m = 2, n = 3, λ = 1,5, µ = 1/T = 1/2, значит ρ = λ/µ = 3.

Граф состояний имеет 6 вершин: S₀ – все свободны; S₁ – один подъёмник занят; S₂ – два занято, очереди нет; S₃ – подъёмники заняты, одна машина в очереди, S₄ – подъёмники заняты, две машина в очереди, S₅ – три в очереди.

S5

S3

S4

2m

2m

2m

2m

m

S0

S1

S2

l

l

l

l

Находим P₀:

= = 0,0246

P₁ = ρP₀ = = = 0,0738

P₂ = ρ/2 Р₁ = 3/2 = = 0,1107

P₃ = ρ/2 P₂ = 1,5 = =0,16605×

P₄ = ρ/2 P₃ = 1,5 = = 0,249075

P₅ = ρ/2 P₄ = 1,5 = = 0,3736125

Проверка: .

P_отк = Р₅ = 0,37 = 37%, Q = Р_обс = 1 – P_отк = 0,63;

абсолютная пропускная способность А = λQ = 1,5 0,63 = 0,945 (маш.в час);

средняя длина очереди L = M[L] = 1P₃+2P₄+3P₅ = (маш.);

среднее время ожидания Т = L/λ = 1,79/1,5 =1,19 (час).

Выводы

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

Контрольные вопросы и задания

1. Какой процесс называется марковским, стационарным, ординарным?

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

s1 – полностью исправно; s2 – частично исправно, необходима наладка;

s3 – серьёзная неисправность, требует ремонта; s4 – непригодно.

Постройте граф состояний для системы.

3. Магазин продаёт две марки автомобилей А и В, для каждой своя матрица переходных вероятностей, соответствующая состояниям: «исправен», «требует гарантийного ремонта». Для А Р_А = , для В Р_В = . Требуется найти вероятности состояний через два года после эксплуатации, если в начальном состоянии автомобиль исправен и определить марку автомобиля наиболее предпочтительную.

4. В городе работают три мобильных оператора: Билайн, МТС и Мегафон и предположим каждый пользуется услугами одного, но может поменять его или нет на другого каждые полгода. Причём результаты опроса показали, что в среднем 15 % Билайн переходят на МТС, 10 % на Мегафон; 20 % МТС переходят на Билайн, 5 % на Мегафон; 5 % Мегафон уходят на МТС и 10 % на Билайн. Постройте матрицу переходных вероятностей. Предположив, что изначально клиенты были распределены равномерно, найти распределение через полтора года, определить какой оператор будет пользоваться наибольшим спросом.

S0

S1

S2

S4

5. Пусть имеется система с состояниями:
S₀ – оба узла работают исправно;
S₁ – первый работает, второй сломан;

S₂ – второй работает, первый сломан;
S₃ – оба неисправны.
Возможные переходы из одного состояния в другое изображены на графе. Пусть исправность первого узла приносит доход 10 у. е., а второго – 6 у. е., а их ремонт требует расходов 4 у. е. и 2 у. е. соответственно. Оценить экономический эффект возможности уменьшения вдвое времени на ремонт, если придётся вдвое увеличить затраты.

6. На вход горячей линии, имеющей 9 каналов, поступает в среднем

120 заявок в час. Заявка получает отказ, если все каналы заняты. Среднее время обслуживания в канале равно 4 мин. Все потоки простейшие. Определить вероятность отказа и среднее число занятых каналов.

7. В ремонтную мастерскую с 4 мастерами принимают не более 7 заявок в день, известно среднее число поступающих в час заявок (λ) и среднее время обслуживания (Т_обс). Найти основные показатели эффективности.

№ вар.
λ
Тобс		0,5	0,5		0,5	0,5

8. При проектировании СМО с ограниченной очередью n, число каналов обслуживания m, производительность обслуживания µ заявок в час было рассчитано на характерную для района интенсивность потока заявок λ. Но плотность заявок по некоторым причинам удвоилась (2λ в час). Что целесообразнее для минимизации отказов: удвоить количество каналов или удвоить производительность канала.
Рассмотрите случаи:
a) m = 1, n = 3, λ = 1,5, µ = 0,5;
b) m = 1, n = 3, λ = 4, µ=2.

9. На мойке машин имеется три места для мойки и еще не более трёх для стоянки ожидающих машин. Если все эти места заняты, машина уезжает. В среднем за час прибывает 2 машины, среднее время мойки одной машины 1 час. Найти вероятность отказа и среднюю длину очереди.

10. Входной поток покупателей в магазин – простейший с плотностью 3 покупателя в мин. Среднее время обслуживания 2 мин. Работает 8 продавцов, доступ неограничен. Будет ли магазин справляться с потоком? Найти характеристики системы.

11. Диспетчерский пункт принимает заявки на ремонт по нескольким телефонам. Известно среднее число заявок, поступающих в час (λ) и среднее время оформления Т_об. Требуется определить минимальное количество телефонов, при котором вероятность отказа будет менее 10 %. При найденном значении m определить абсолютную пропускную способность и среднее количество занятых каналов (см. таблицы).

№ вар.

λ

Тобс.

№ вар.

λ

Тобс.

Указание. Поскольку явно из общей формулы для нахождения вероятностей выразить m нельзя, то нужно организовать (удобно на листе Excel) пошаговую процедуру определения Р_n для каждогозначения m (см. формулы на стр. 32). При этом нужно найти все промежуточные вероятности от Р₀ до Р_n. Убедиться, что их сумма равна 1 и последняя вероятность меньше 0,1.

ГЛАВА 3. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ

В СРЕДЕ GPSS

Технологии имитационного моделирования и различные подходы к моделированию начали бурно развиваться в прошлом столетии, сначала для систем массового обслуживания, затем для технических систем и сетей. Существуют разные среды моделирования, отличающиеся подходами, средствами, функциональными возможностями. Некоторые из них имеют хороший графический интерфейс, позволяющий наблюдать за процессом моделирования. Из наиболее известных в настоящее время GPSS, Micro Saint, Arena, Anylogic и др. Рассмотрим наиболее распространённую и относительно несложную в освоении среду GPSS [2,5,7].

3.1. Общие сведения о языке GPSS

Язык моделирования GPSS/PC(General Purpose Simulation System – общецелевая система моделирования) был разработан компанией Minuteman (США) в 1962 году изначально для моделирования дискретных систем и был предназначен для работы в операционной среде DOS. Язык получил широкое распространение и был включён в учебные курсы по моделированию систем у нас в стране и во многих университетах США и других стран. В последнее десятилетие появилась новая версия языка Gpss World, разработанная под Windows, в которой можно моделировать не только дискретные, но и непрерывные процессы. Эти возможности обеспечиваются как новыми объектами языка, так и включением в состав Gpss World языка PLUS – языка программирования низкого уровня, позволяющего взаимодействовать с другими приложениями и создавать собственные библиотеки процедур. Также эта среда обеспечивает высокую интерактивность и визуальное представление информации.

Студенческая версия GPSS/World бесплатная, имеет ограничения лишь на количество используемых в программе блоков (не более 170). Учебную версию можно получить бесплатно на портале www/minutemansoftware.com/download. Не требует установки, для запуска программы достаточно запустить на выполнение файл GPSSW.exe. После этого откроется среда моделирования GPSS/World. Далее необходимо выбрать пункт меню File/Open и в открывшемся диалоговом окне Новый документ – Создать Model. В результате будет открыто окно Untitled Model1, в котором необходимо набрать текст программы. Файл с программой можно сохранить в файле с расширением.gps (пункты меню File/Save; File/Save As).

Для запуска программы на выполнение необходимо выбрать пункт меню Command/Create Simulation.

В среде моделирования различают объекты: модель – разрабатывается на языке GPSS, состоит из блоков, создаётся при помощи встроенного текстового редактора; процесс моделирования – результат трансляции модели, получаемый после команды Create Simulation, при наличии ошибок транслятор выдаёт список сообщений об ошибках в окне JOURNAL; отчёт по моделированию – автоматически создаваемый файл, содержащий статистическую информацию об объектах, накопленную в процессе моделирования.

3.2. Основные объекты языка GPSS

Язык основан на схеме транзактов. Транзакт – это объект, который «путешествует» по системе, перемещаясь от блока к блоку, согласно логике передвижений, предписанной в модели. По пути он может задерживаться на определённое время вследствие своей обработки или занятости того или иного оборудования, создавать очереди, пропускать вперёд другие транзакты, согласно их приоритету и т. д. Транзакты имеют прямую аналогию с заявками в СМО. Каждый транзакт может обладать параметрами (до 100), которые могут меняться в соответствии с логикой модели. Параметры нумеруются или им даются имена. Транзактам может присваиваться приоритет, определяющий предпочтение, который может меняться в программе.

Язык GPSSсвязан с пошаговым выполнением операторов, называемых блоками (фактически, каждый блок – это отдельная подпрограмма). Каждое продвижение транзакта является событием в модели. Комплекс программ, обеспечивающих выполнение событий, называется симулятором (планировщиком). Его функции:

- обеспечить продвижение транзактов по заданным маршрутам;

- регистрировать время наступления каждого события и выполнение их в нарастающей временной последовательности;

- регистрировать статистическую информацию о функционировании модели;

- продвигать модельное время в процессе моделирования.

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

Условно все объекты можно разделить на 7 категорий (табл. 3.1).

Таблица 3.1

Объекты языка GPSS

Категории	Типы объектов
Динамическая	Транзакты
Операционная	Блоки
Аппаратная	Одноканальные устройства, многоканальные устройства (памяти), логические ключи
Вычислительная	Функции, переменные, СЧА, генераторы случайных чисел
Статистическая	Очереди, таблицы
Запоминающая	Сохраняемые ячейки, матрицы ячеек
Группирующая	Списки, группы транзактов

Операционные объекты – блоки задают логику функционирования модели системы и определяют пути продвижения транзактов между объектами других категорий. В блоках происходят события четырёх основных типов:

- создание и уничтожение транзактов;

- задержка транзакта на определённое время;

- изменение маршрута движения транзакта, группировка транзактов;

- изменение числового атрибута (параметра) транзакта.

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

Одноканальное устройство (ОКУ) – оборудование, которое может быть занято только одним транзактом. Например, один узел связи, один мастер, один пункт приёма услуг.

Многоканальные устройства (МКУ) – памяти предназначены для имитации оборудования, осуществляющего параллельную обработку, либо моделирования устройств ограниченной ёмкости (буферы, стоянки транспорта, складские помещения, конвейеры).

Логический ключ – объект, имеющий два состояния «включён» или «выключен», в зависимости от которых другие транзакты определяют пути их дальнейшего следования.

К статистическим объектам относятся очереди и таблицы. В любой системе движение потока заявок может быть задержано из-за недоступности устройства. В этом случае транзакты становятся в очередь. Учёт очередей составляет одну из основных функций планировщика, который автоматически накапливает статистику относительно устройств и очередей. Пользователь может собирать эту информацию в определённых точках модели. Для облегчения табулирования статистической информации предусмотрен объект – таблица, которая используется для получения выборочных распределений, в неё заносится число попаданий конкретного СЧА в некоторый диапазон, а также вычисляется автоматически математическое ожидание и среднеквадратичное отклонение, распределение может быть представлено графически гистограммой.

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

Переменные представляют собой сложные арифметические выражения, которые включают константы, системные числовые атрибуты (СЧА), библиотечные арифметические функции, арифметические и логические операции.

Каждому объекту в GPSS соответствуют атрибуты, описывающие его состояние в данный момент. Они автоматически регистрируются и доступны для использования в течение всего процесса моделирования, называются системными числовыми атрибутами (СЧА). Всего существует более 50 СЧА, наиболее часто используемые приведены в табл. 3.2.

Таблица 3.2

Таблица основных СЧА

Объект	СЧА	Назначение
Генераторы случайных чисел	RNi	Случайное число в диапазоне 0-999, при использовании в качестве аргумента функции в диапазоне [0;0.999]
Транзакт	Рi PR M1 MPi	Значение i-го параметра, Значение приоритета Время пребывания в модели активного транзакта (от MARK до текущего времени) Время прохождения транзактом некоторого участка модели (вычисляется как разность текущего абсолютного времени и значения i-ого параметра транзакта, определяемого блоком MARK i)
Очередь	Qi, Q$имя	Текущая длина i-ой очереди
Переменные	V$имя	Значение арифметической переменной
Сохраняемые ячейки	X$имя	Значение ячейки памяти
Функции	FN$имя	Значение функции
Памяти	S$имя	Количество занятых каналов в МКУ

Окончание таблицы 3.2

Объект	СЧА	Назначение
	R$имя SF$имя	Количество свободных каналов в МКУ Занятость МКУ: 1– заполнена, 0 – нет
Одноканальные устройства	F$имя	Занятость МКУ: 1– занято, 0 – нет
Логический ключ	LS$имя	Состояние ключа: 1– установлен, 0 – нет

Например, Р1 – СЧА, обозначающий значение первого параметра транзакта; Q$och – СЧА, обозначающий длину очереди с именем och. Если используется символьное имя, то между СЧА и именем ставится знак $.

К группирующей категории относятся группы транзактов и списки. Существует 5 видов списков: текущих событий, будущих событий, задержки ОКУ или МКУ, отложенных прерываний и пользователя.

3.3. Основные блоки языка GPSS

В отличие от PLUS-операторов, которые могут содержать несколько строк, операторы GPSS записываются в отдельной строке и имеют следующий вид:

[метка] имя блока[операнды];комментарии

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

Приведём основные операторы, которые используются в программе.

3.3.1. Поступление транзактов в модель

GENERATE (генерировать) – блок, в котором «рождаются» транзакты (заявки на обслуживание) и входят в процесс моделирования. В любой блок GENERATE не могут входить транзакты. Поэтому в простых программах это первый блок. Имеет формат:

GENERATE [A],[B],[C],[D],[E]

Скобки [ ] означают, что данный операнд является необязательным.

Операнд A задаёт средний интервал времени между моментами поступления последовательных транзактов в модель. Если этот интервал постоянен, то операнд B не используется. Если же интервал поступления является случайной величиной, то в операнде B указывается модификатор среднего значения, который может быть задан в виде модификатора-интервала или модификатора-функции. Модификатор-интервал позволяет задать равномерный закон распределения поступления транзактов. Запись GENERATE A,B означает, что время поступления транзактов будет распределено равномерно на отрезке [A–B, A+B]. Ясно, что В<А.

Например, блок GENERATE 100,40 создаёт транзакты через случайные интервалы времени, равномерно распределённые на отрезке [60;140]. Разыгрывается случайное число в этом интервале, например 78, рождается первый транзакт. Затем, разыгрывается новое случайное число в интервале [60;140], например 132, и второй транзакт попадает в модель в момент времени 78 + 132 = 210 и т. д.

Модификатор-функция используется, если закон распределения интервала поступления отличен от равномерного. В этом случае в операнде B должна быть записана ссылка на функцию (её СЧА), описывающую этот закон, и случайный интервал поступления определяется как целая часть произведения поля A (среднего значения) на вычисленное значение функции.

В операнде C задаётся момент поступления в модель первого транзакта. Если это поле пусто или равно 0, то момент появления первого транзакта определяется операндами A и B.

Операнд D задаёт общее число транзактов, которое должно быть создано блоком GENERATE. Если это поле пусто, то блок генерирует неограниченное число транзактов до завершения моделирования.

Операнд E задаёт приоритет, присваиваемый генерируемым транзактам. Число уровней приоритетов неограниченно, причём самый низкий приоритет – нулевой. Если поле E пусто, то генерируемые транзакты имеют нулевой приоритет.

Операнд F задаёт число параметров транзакта, по умолчанию 12.

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