Замкнутая СМО (СМО с ограниченным потоком требований)

Пусть имеется некий источник, содержащий N требований, каждое из которых может потребовать обслуживание с постоянной интенсивностью l. Обслуживание осуществляет СМО, классифицируемая по Кэндаллу следующим образом: M/M/n/m, где m<N (см. 7.2.1). Состояние СМО будем, как и выше, описывать случайным процессом К(t), принимающим значения на множестве к={0, 1, 2,…..,N}. Обслуженные требования возвращаются в источник, и таким образом интенсивность входящего потока зависит от числа требований находящихся в СМО:

(N-k) - число требований в источнике,

- интенсивность входящего потока

Рассмотрим случай, когда N>n.

Т.к. число состояний системы конечно, и все они не нулевые и не периодические, то в СМО существует стационарный режим. Как и прежде, напишем уравнения размножения и гибели для нестационарного и стационарного режимов:

(6.23)

 

(6.24)

Решим эту систему, сделав :

 

(6.25)

 

Если положить k=1 в первом уравнении для любого k. Отсюда находим:

 

,

,

(6.26)

(6.27)

Если есть распределение вероятностей состояний, можно вычислить все необходимые характеристики. Т,е. задача принципиально решена.

 

Примеры:

1. Организация морского порта

Сравним 3 варианта организации морского порта:

1) Два порта по одному причалу в каждом; поток кораблей делится между портами.

2) Один порт с двумя причалами, принимающий все корабли

3) Один порт с одним причалом двойной производительности.

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

Первому варианту отвечают две СМО, модель каждой M/M/1/m>, интенсивность входящего потока , а времени обслуживания - для каждой

Второму –.модель СМО M/M/2/m>, где интенсивность входящего потока 2 , а времени обслуживания - для каждого канала.

Третьему – одна СМО M/M/1/m>, где интенсивность входящего потока 2 , а времени обслуживания - 2 .

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

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

, где и

Из формул видно, что определяющим фактором является загрузка и отношение .

. В таблице…приведены результаты расчета времени ожидания для рассматриваемых вариантов и трех значений , в том числе близких к критическому. Эти результаты говорят о том, что первый вариант заведомо хуже своих конкурентов и его следует отбросить. второй и третий варианты разнятся между собой не столь значительно, и на этом основании делать окончательный выбор не следует. Надо учесть помимо времени ожидания и другие факторы, например стоимость строительства и эксплуатации, наличие подъездных путей и т.п. Иными словами принимать окончательное решение надо на основе векторного критерия.

2. Организация пункта выдачи инструментов

Рассматривается пункт выдачи инструментов мастерам. Требуется определить сколько нужно поставить «раздатчиков», чтобы минимизировать оплату простоев на пункте (как мастеров, так и раздатчиков). Пункт можно рассматривать как СМО, входящий поток – это обращения мастеров за инструментом, время облуживания - это время выдачи инструмента раздатчиком мастеру, а число каналов – это число раздатчиков. Был проведен хронометраж обращений за инструментами, который показал, что интервал между обращениями распределен по экспоненциальному закону со средним временем 35 сек (l=1/35), и, следовательно, входящий поток требований - простейший. Хронометраж процесса обслуживания одного мастера раздатчиком показал, что время обслуживания тоже распределено по экспоненциальному закону 50 сек. Это объясняется тем, что наиболее часто используемый инструмент раздатчики хранят рядом, с собой. Очередь необходимо допускать любую, и значит, пункт выдачи инструментов можно описать моделью СМО типа M/M/n/m>, в которой n надо найти, исходя из минимизации стоимости простоев.

Средняя стоимость простоя мастеров в очереди в течение рабочего дня вычисляется по формуле:

,

где C_m – оплата простоя мастеров, τ – длительность рабочего дня, S_m –мастера, t - см. предыдущий пример.

Средняя стоимость простоя раздатчиков:

,

где C_k – оплата простоя раздатчиков, (τ ) – время обслуживания мастеров, S_m – стоимость часа работы раздатчика. Примем, что час работы мастера стоит 5 условных единиц, а раздатчика - 2.

l=1/35 сек, n=1/50 сек., r=50/35>1Þn_min=2

 

Табл……

n	Cм	Ck
		8,6	67,6
	7,8	27,6	35,4
	1,45	38,6	40,05

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

СМО с приоритетом

Виды приоритета:

- относительный - требование, обладающее этим видом приоритета, поступает в первый освободившийся канал, минуя очередь (например, участники ВОВ, инвалиды идут без очереди)

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

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

Назначение динамических приоритетов – это элемент управления функционированием СМО.

Рассмотрим систему типа М/М/n /m=0. Напомним, что это означает пуассоновский поток на входе, экспоненциальное распределение времени обслуживания, n каналов и запрет на очередь.

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

1/ поток обычных, неприоритетных, требований интенсивностью

2 / поток приоритетных (с абсолютным приоритетом) требований интенсивностью

Так как оба потока пуассоновские, то и суммарный поток также пуассоновский интенсивностью .

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

- интенсивность обслуживания приоритетных требований,

- интенсивность обслуживания неприоритетных требований.

Случайный процесс К(t), описывающий изменения числа требований в системе, также будет составным:

 

К(t) = K₁(t) + K₂(t), ( 6.28 )

где K₁(t) – число приоритетных требований,

K₂(t) – неприоритетных требований

Соответственно, по аналогии с неприоритетными системами, состояние системы в стационарном режиме (режим статистического равновесия) будем характеризовать вероятностями вида:

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

= 0

( 6.29 )

, если 1< i+j < n

( 6.30 )

, если i+j=n

 

Система, отвечающая приведенным уравнениям, весьма проста. Ниже проиллюстрируем ее решение на частном примере.

Специфическим элементом обслуживания с приоритетом является характер отказов. Кратко рассмотрим это.

 

1. Отказ приоритетному требованию (приоритетное требование подошло и получило отказ). Это может произойти, только если все каналы заняты такими же приоритетными требованиями.

2. Отказ требованию 2-го потока. Здесь возможны варианты.

2.1. Неприоритетное требование подошло, но все каналы заняты. - требование получает чистый отказ.

2.2. Подошло требование 1 потока., но все каналы заняты, и хотя бы в одном из них обслуживается требование 2-ого потока. Оно будет вытеснено (отказ типа «недообслуживание»).

- условная вероятность (условие – подошло требование 1-го потока).

2.3. В полностью занятой системе обслуживается требование 2-ого потока. Оно получит отказ типа «недообслуживание», если в это время подойдет требование 1-го потока.

. - вероятность, что подойдет требование 1-го потока, которое вытолкнет требование 2-го потока - условная вероятность (условие – все каналы заняты, и хотя бы в одном из них обслуживается требование 2-ого потока.)

Представляет интерес распределение числа требований 1-го и 2-го потоков раздельно. Для этой цели вводятся вероятности Р_j. и Р_i

= P{K(t) =i} и = P{K(t) =j}, где

i - приоритетные требования, j- неприоритетные требования.

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

Пример. Одноканальная система M/M/1/m=0, с абсолютным приоритетом.

(2 потока требований: λ₁ – приоритетный, λ₂ – не приоритетный.

Интенсивности обслуживания: ν₁ и ν₂).

Эта система может быть моделью телефонной линии: обычные абоненты – неприоритетные требования (среднее время разговора 1/ ν₂), неисправности – приоритетные (среднее время ремонта 1/ ν ).

 

Множество состояний:

{0;0} – линия исправна и свободна,

{1,0} – линия неисправна,

{0,1} – линия исправна, но занята.

Составим уравнения СМО в стационарном режиме и решим его:

( 6.31 )

- нормирующее условие (сумма вероятностей всех возможных состояний)

( 6.32 )

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

P_отк1=Р_1,0 - вероятность, что все каналы заняты приоритетными требованиями;

P_отк2`=Р_1,0+Р_0,1 – либо неисправность, либо кто-то говорит;

P_отк2``=Р_0,1 – известно, что произошел отказ. Р_0,1 – это вероятность, что отказ прервал разговор.(вероятность занятости канала требованием 2-го потока в момент отказа);

P_отк2``` - вероятность, что канал испортится в течение разговора.

P_{окончания обслуживания} =

Следовательно: ( 6.33 )

 

Многофазное обслуживание

 

 

Структурно многофазная СМО – это последовательное соединение однофазных (см. рис 8). Обслуженные требования в установленном порядке переходят с фазы на фазу. Таким образом, входящий поток на каждой фазе – это выходящий поток предыдущей фазы (за исключением требований, получивших отказ). Например, механическая обработка детали: обдирка > грубая обточка > прецизионная обточка > шлифовка и т.п. Каждая из этих операций выполняется на своем станке, представляющем отдельную СМО.

Как уже говорилось, входящие потоки (кроме 1-ой СМО) являются выходными потоками предыдущей фазы. Поэтому для каждой фазы необходимы алгоритмы, преобразующие входной поток в выходной, и позволяющие описать СМО с помощью вероятностей вида: P(k₁,k₂,...,k_n;t)=P{k₁(t)=k₁,...,k_n(t)=k_n}.

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

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

Тогда общее уравнение для вероятностей будет следующим:

 

( 6.33 )

Вероятностный смысл слагаемых правой части таков:

1)не должно прийти требование из внешнего потока и не должно закончить обслуживание ни одно требование ни в одной фазе кроме последней (иначе, переход внутри фаз);

2) не хватало требования в 1-ой фазе и оно пришло;

3) было лишнее требование на последней фазе и оно ушло

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

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

Теорема Бёрка:

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

Теорема Рейча:

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

Теорема Бёрка позволяет при входящем пуассоновском потоке на входе в СМО считать, что входящие потоки во всех фазах одинаковы, состояния в этих фазах независимы и следовательно

. ( 6.35 )

Проиллюстрируем это простейшим примером: двухфазная СМО, по одному каналу в каждой фазе, простейший поток на входе, и экспоненциальное распределение времени обслуживания.

( 6.36 )

n=1

( 6.37 )

Проверим, удовлетворяет ли это решение уравнению:

( 6.38 )

Проверка допустимости рассмотрения фаз как независимых прошла.

 

 

Стохастические сети

 

 

В этом разделе приведем лишь основные понятия, т.к. детально такие системы будут рассматриваться в специальных курсах.

На рис.9 показаны четыре СМО связанные между собой по принципу «каждая с каждой». Требование, обслуженное в одной из СМО (например в i-ой), может продолжить обслуживание в любой другой (например в j-ой) с вероятностью p . Соответственно интенсивность перехода = p , где - интенсивность выходного потока i-го узла. Таким образом, потоки в сети носят случайный характер, как по направлению, так и по интенсивности.

.Такая сеть описывается с помощью транспортной матрицы.

Эта матрица не симметрична относительно диагонали.

Стохастические сети могут быть как разомкнутыми, так и замкнутыми.

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

Сеть будет разомкнутой, если добавить внешнюю среду, откуда приходят и куда уходят требования.

В такой сети возможны как стационарный, так и нестационарный режимы.

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

Если один из узлов не стационарен, то он становится источником требований, но в такой системе все равно будет стационарный режим. Сеть станет разомкнутой. Перед этим узлом накопится бесконечная очередь.

Исходя из этого условия, можно описать систему в виде алгебраических уравнений λ_k = α_k(λ₀) и найти интенсивности потоков в каждом узле.

Если уравнения линейны, то такая система называется линейной стохастической сетью.

В качестве примера стохастической сети можно привести информационные сети (например, Интернет), развитые транспортные сети (например, сеть ЖД страны) и т.п.