Введение в теорию комплектов

Классификация систем массового обслуживания

Задачи теории массового обслуживания

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

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

Процесс работы СМО – случайный процесс с дискретными состояниями и непрерывным временем.

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

Классификация СМО по наличию очередей:

- с отказами;

- с очередью.

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

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

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

Рассматриваются следующие СМО:

- СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);

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

Кроме этого СМО делятся на открытые СМО и замкнутые СМО.

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

Классификация СМО далеко не ограничивается приведенными разновидностями.

5. Сетевые модели (N -схемы). Сети Петри

5.1. Теоретические основы сетей Петри: принципы построения, алгоритмы поведения

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

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

Основным понятием теории комплектов является функция числа экземпляров: #(x, B) – число x в B, т.е. число экземпляров элемента x в B.

Элемент х является членом комплекта B, если #(x, B) > 0. Аналогично, если #(x, B) = 0, то х не принадлежит B. Æ – пустой комплект, не имеющий членов (для всех х: #(x, 0) = 0). Если ограничить число элементов в комплекте так, что 0 £ #(x, B) £ 1, то получим теорию множеств.

Под мощностью | B | комплекта B понимается общее число экземпляров в комплекте | B | = S _x #(x, B).

Комплект A является подкомплектом комплекта B, если каждый элемент A является элементом B, по крайней мере, не большее число раз, т.е. A Í B тогда и только тогда, когда #(x, A) £ #(x, B) для всех х.

Два комплекта равны (А = В), если #(x, A) = #(x, B).

Комплект A строго включен в комплект B (A Ì B), если A Í B и A ¹ B. Над комплектами определены 4 операции:

объединение A È B: #(x, A È B) = max(#(x, A), #(x, B));

пересечение A Ç B: #(x, A Ç B) = min(#(x, A), #(x, B));

сумма A + B: #(x, A + B) = #(x, A) + #(x, B);

разность A – B: #(x, A – B) = #(x, A) – #(x, B);

Назовем множество элементов, из которых составляются комплекты, областью D. Пространство комплектов Dⁿ есть множество всех таких комплектов, что элементы их принадлежат D и ни один из элементов не входит в комплект более n раз. Иначе говоря, для любого B Î Dⁿ:

а) из x Î B следует х Î D;

б) для любого х #(x, B) £ n.

Множество D ^¥ есть множество всех комплектов над областью D без какого-либо ограничения на число экземпляров элемента в комплекте.