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

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

Рис. 3.1. Схема СМО.

Поступающие на вход СМО однородные заявки в зависимости от порождающей причины делятся на типы, интенсивность потока заявок типа i (i=1…M) обозначено li. Совокупность заявок всех типов - входящий поток СМО.

Обслуживание заявок выполняется m каналами. Различают универсальные и специализированные каналы обслуживания. Для универсального канала типа j считается известными функции распределения Fji(t) длительности обслуживания заявок произвольного типа. Для специализированных каналов функции распределения длительности обслуживания каналов заявок некоторых типов являются неопределёнными, назначение этих заявок на данный канал.

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

Q - схемы можно исследовать аналитически и имитационными моделями. Последнее обеспечивает большую универсальность.

Рассмотрим понятие массового обслуживания.

В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и собственно обслуживание заявки. Это можно отобразить в виде некоторого i-ого прибора обслуживания Пi, состоящего из накопителя заявок, в котором может находится одновременно li=0…LiH заявок, где LiH - ёмкость i-ого накопителя, и канала обслуживания заявок, ki.

Рис. 3.2. Схема прибора СМО

На каждый элемент прибора обслуживания Пi поступают потоки событий: в накопитель Hi поток заявок wi , на канал ki - поток обслуживания ui.

Потоком событий (ПС) называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Различают потоки однородных и неоднородных событий. Однородный ПС характеризуется только моментами поступления этих событий (вызывающими моментами) и задаётся последовательностью {tn}={0£t1£t2…£tn£…}, где tn - момент поступления n- ого события - неотрицательное вещественное число. ОПС может быть также задан в виде последовательности промежутков времени между n-ым и n-1-ым событиями {tn}.

Неоднородным ПС называется последовательность {tn, fn} , где tn- вызывающие моменты; fn- набор признаков события. Например, может быть задана принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала и т.п.

Рассмотрим ОПС, для которого tiÎ{tn}- случайные величины, независимые между собой. Тогда ПС называется потоком с ограниченным последействием.

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

Если для любого интервала Dt событие P0(t, Dt) + P1(t, Dt) + Р³1(t, Dt)=1, P1(t, Dt) - вероятность попадания на интервал Dt ровно одного события. Как сумма вероятностей событий, образующих полную группу и несовместных, то для ординарного потока событий P0(t, Dt) + P1(t, Dt) » 1, Р³1(t, Dt)=Q(Dt), где Q(Dt)- величина, порядок малости который выше, чем Dt, т.е. lim(Q(Dt))=0 при Dt®0.

Стационарным ПС называется поток, для которого вероятность появления того или иного числа событий на интервале времени t зависит от длины этого участка и не зависит от того, где на оси времени 0 - t взят этот участок. Для ОПС справедливо 0*P0(t, Dt) + 1*P1(t, Dt)= P1(t, Dt) - среднее число событий на интервале Dt. Среднее число событий, наступающих на участке Dt в единицу времени составляет P1(t, Dt)/Dt. Рассмотрим предел этого выражения при Dt®0

lim P1(t, Dt)/Dt=l(t)*(1/един.вр.).

Если этот предел существует, то он называется интенсивностью (плотностью) ОПС. Для стандартного ПС l(t)=l=const.

Применительно к элементарному каналу обслуживания ki можно считать что поток заявок wiÎW, т.е. интервалы времени между моментами появления заявок на входе ki образуют подмножество неуправляемых переменных, а поток обслуживания uiÎU, т.е. интервалы времени между началом и окончанием обслуживания заявки образуют подмножество управляемых переменных.

Заявки, обслуженные каналом ki и заявки, покинувшие прибор Пi по различным причинам не обслуженными, образуют выходной поток yiÎY.

Процесс функционирования прибора обслуживания Пi можно представить как процесс изменения состояний его элементов во времени Zi(t). Переход в новое состояние для Пi означает изменение кол-ва заявок, которые в нём находятся (в канале ki и накопителе Hi). Т.о. вектор состояний для Пi имеет вид : , где - состояния накопителя, ( =0 - накопитель пуст, =1- в накопителе одна заявка…, = - накопитель занят полностью; - состояние канала ki ( =0 - канал свободен, =1 канал занят).

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

Т.о. для задания Q-схемы необходимо оператор сопряжения R, отражающий взаимосвязь элементов структуры.

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

Собственными (внутренними) параметрами Q-схемы будут являться кол-во фаз LФ, количество каналов в каждой фазе, Lkj, j=1… LФ, количество накопителей каждой фазы Lkj, k=1… LФ, ёмкость i-ого накопителя LiH. Следует отметить, что в теории массового обслуживания в зависимости от ёмкости накопителя применяют следующую терминологию:

- системы с потерями (LiH=0, накопитель отсутствует);

- системы с ожиданием (LiH®¥);

- системы с ограниченной ёмкостью накопителя Нi (смешанные).

Обозначим всю совокупность собственных параметров Q-схемы как подмножество Н.

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

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

В зависимости от динамики приоритетов Q-схемы различают статические и динамические. Статические приоритеты назначаются заранее и не зависят от состояний Q-схемы, т.е. они являются фиксированными в пределах решения конкретной задачи моделирования. Динамические приоритеты возникают при моделировании. Исходя из правил выбора заявок из накопитель Нi на обслуживание каналом ki можно выделить относительные и абсолютные приоритеты. Относительный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Н, ожидает окончания обслуживания представляющей заявки каналом ki и только после этого занимает канал. Абсолютный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель, прерывает обслуживание каналом ki заявки с более низким приоритетом и сами занимает канал (при этом вытесненная из ki заявка может либо покинуть систему, либо может быть снова записана на какое-то место в Нi).

Необходимо также знать набор правил, по которым заявки покидают Нi и ki: для Нi – либо правила переполнения, либо правила ухода, связанные с истечением времени ожидания заявки в Н; для ki – правила выбора маршрутов или направлений ухода. Кроме того, для заявок необходимо задать правила, по которым они остаются в канале ki, т.е. правила блокировок канала. При этом различают блокировки ki по выходу и по входу. Такие блокировки отражают наличие управляющих связей в Q‑схеме, регулирующих поток заявок в зависимости от состояний Q‑схемы. Набор возможных алгоритмов поведения заявок в Q‑схеме можно представить в виде некоторого оператора алгоритмов поведения заявок А.

Т.о. Q‑схема, описывающая процесс функционирования СМО любой сложности однозначно задаётся в виде набора множеств: Q = <W, U, H, Z, R, A> .








Дата добавления: 2017-02-20; просмотров: 914;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.009 сек.