Введение в теорию комплектов
Классификация систем массового обслуживания
Задачи теории массового обслуживания
Каждая система массового обслуживания (СМО) состоит из какого-то количества обслуживающих единиц, которые называются каналами обслуживания (станки, транспортные тележки, роботы, линии связи, кассиры, продавцы и т.д.). Всякая СМО предназначена для обслуживания потока заявок (требований), поступающих в какие-то случайные моменты времени.
Примеры СМО: телефонные станции, ремонтные мастерские, билетные кассы, справочные бюро, станочные и другие технологические системы, системы управления гибких производственных систем и т.д.
Процесс работы СМО – случайный процесс с дискретными состояниями и непрерывным временем.
Предмет теории массового обслуживания – построение математических моделей, связывающих заданные условия работы СМО (число каналов, их производительность, правила работы, характер потока заявок) с показателями эффективности СМО. Эти показатели описывают способность СМО справляться с потоком заявок. Ими могут быть: среднее число заявок, обслуживаемых СМО в единицу времени; среднее число занятых каналов; среднее число заявок в очереди; среднее время ожидания обслуживания и т.д.
Классификация СМО по наличию очередей:
- с отказами;
- с очередью.
В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не обслуживается.
В СМО с очередью заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает возможности быть обслуженной.
СМО с очередями подразделяются на разные виды в зависимости от того, как организована очередь – ограничена или не ограничена. Ограничения могут касаться как длины очереди, так и времени ожидания или дисциплины обслуживания.
Рассматриваются следующие СМО:
- СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);
- СМО с обслуживанием с приоритетом, т.е. некоторые заявки обслуживаются вне очереди и т.д.
Кроме этого СМО делятся на открытые СМО и замкнутые СМО.
В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии сама СМО (сколько каналов занято). В замкнутой СМО – зависят. Например, если один инженер обслуживает группу приборов, время от времени требующих наладки, то интенсивность потока требований со стороны приборов зависит от того, сколько их уже исправно и ждет наладки.
Классификация СМО далеко не ограничивается приведенными разновидностями.
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| = Sx#(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. Пространство комплектов Dn есть множество всех таких комплектов, что элементы их принадлежат D и ни один из элементов не входит в комплект более n раз. Иначе говоря, для любого B Î Dn:
а) из x Î B следует х Î D;
б) для любого х #(x, B) £ n.
Множество D¥ есть множество всех комплектов над областью D без какого-либо ограничения на число экземпляров элемента в комплекте.