Механики
 Скачать 4.29 Mb.
|
|
5.4.1. Одноканальная СМО без накопителя (M/M/1/0) Рассмотрим простейшую одноканальную систему массового обслуживания (СМО) с отказами, в которую поступает случайный поток заявок, задерживаемых в приборе на случайное время (рис.5.3,а). Посколь- Раздел 5. Численное моделирование 191 ку перед обслуживающим прибором нет накопителя, то заявка, поступив- шая в систему и заставшая прибор занятым, получает отказ в обслужива- нии и теряется. Таким образом, в системе, кроме входящего потока заявок с интенсивностью λ , образуются еще два потока: выходящий поток обслу- женных в приборе заявок с интенсивностью ' λ и поток необслуженных заявок (получивших отказ в обслуживании) с интенсивностью " λ Очевидно, что λ λ λ = + " ' 1. Описание системы . 1.1. Система содержит один обслуживающий прибор (П), то есть является одноканальной 1.2. В систему поступает один класс заявок, то есть поток заявок однородный . 1.3. В приборе происходит задержка (обслуживание) поступающих в систему заявок на некоторое случайное время. 1.4. Перед прибором не предусмотрены места для ожидания заявок, то есть в системе отсутствует накопитель. 2. Предположения и допущения . 2.1. Поступающие в систему заявки образуют простейший поток с интенсивностью λ 2.2. Длительность обслуживания заявок в приборе распределена по экспоненциальному закону с интенсивностью b / 1 = µ , где b – средняя длительность обслуживания. 2.3. Дисциплина буферизации – с отказами : заявка, поступившая в систему и заставшая прибор занятым обслуживанием другой заявки, теряется. 2.4. Дисциплина обслуживания – в естественном порядке : заявка, поступившая в систему и заставшая прибор свободным, принимается на обслуживание. Очевидно, что в СМО с отказами всегда будет существовать устано- вившийся режим, поскольку даже при больших значениях нагрузки ( 1 >> y ) число заявок в системе не может вырасти до бесконечности. Это обусловлено тем, что с ростом нагрузки увеличивается доля заявок, получающих отказ в обслуживании. 3. Кодирование состояний случайного процесса . В качестве параметра, описывающего состояние случайного процесса, будем рассматривать количество заявок k, находящихся в СМО. Очевидно, что система в любой момент времени может находиться в П µ λ ' λ λ E 0 E 1 µ Рис . 5.3. СМО с отказами ( а ) и её граф переходов ( б ) а) б) " λ 192 Раздел 5. Численное моделирование одном из двух состояний: E 0 : 0 = k – в системе нет заявок (прибор простаивает); E 1 : 1 = k – в системе (на обслуживании в приборе) находится 1 заявка (прибор работает). 4. Размеченный граф переходов случайного процесса (рис.5.3,б). В процессе функционирования рассматриваемой системы в один и тот же момент времени может наступить только одно из двух возможных событий, которые приводят к изменению состояния случайного процесса, протекающего в системе. 1. Поступление заявки в систему с интенсивностью λ . При этом: • если случайный процесс находится в состоянии E 0 (прибор простаи- вает), то произойдет переход в состояние E 1 (начнется обслуживание поступившей заявки), причем интенсивность перехода совпадает с интенсивностью поступления заявок в систему λ ; • если же случайный процесс находится в состоянии E 1 (прибор работает), то состояние E 1 случайного процесса не изменится, что будет соответствовать отказу в обслуживании поступившей заявке. Таким образом, переход из состояния E 0 в состояние E 1 происходит с интенсивностью λ 2. Завершение обслуживания заявки , находящейся в приборе. Это событие может наступить только в том случае, если в приборе на обслу- живании находится заявка, то есть случайный процесс находится в состо- янии E 1 . При этом происходит переход в состояние E 0 , причем интенсив - ность перехода совпадает с интенсивностью обслуживания заявки в приборе µ 5. Диаграммы функционирования системы . Рассмотрим диаграммы функционирования системы и покажем, что случайный процесс, протекающий в системе, при сформулированных выше предположениях является марковским. На рис.5.4 показаны диаграммы следующих процессов: а) поступления в СМО заявок, интервалы между которыми в случае простейшего потока распределены по экспоненциальному закону; б) перехода из состояния E 0 в состояние E 1 и обратно, в которых может находиться система, при этом время нахождения случайного процесса в состоянии E 1 равно длительности обслуживания заявки в приборе, которая представляет собой случайную величину, распределен- ную по экспоненциальному закону; в) выхода из системы обслуженных заявок в моменты времени ' 7 ' 4 ' 3 ' 1 , , , t t t t ; г) выхода из системы необслуженных заявок, получивших отказ из- за занятости прибора в моменты времени ' 8 ' 6 ' 5 ' 2 , , , t t t t ; д) формирования интервалов времени между соседними переходами случайного процесса. Раздел 5. Численное моделирование 193 Как показано в п. 5.1.2, дискретный случайный процесс с непрерыв- ным временем будет марковским, если интервалы между соседними переходами распределены по экспоненциальному закону. В нашем случае, интервал 1 τ представляет собой интервал между поступающими заявками, который для простейшего потока имеет экспоненциальное распределение. Интервалы 8 6 4 2 , , , τ τ τ τ , как видно из диаграммы, представляют собой время нахождения случайного процесса в состоянии E 1 , равное длительности обслуживания заявки в приборе, которая распределена по экспоненциальному закону. Таким образом, интервалы 8 6 4 2 1 , , , , τ τ τ τ τ распределены по экспоненциальному закону и, следовательно, удовлетворяют сформулированному выше условию. Рассмотрим теперь выделенные интервалы 7 5 3 , , τ τ τ . Каждый из этих интервалов представляет собой промежуток времени от момента заверше- ния обслуживания некоторой заявки до момента поступления новой заявки, принимаемой на обслуживание в приборе. В п.5.1.2 сформулиро- вано замечательное свойство экспоненциального распределения , которое гласит, что в случае экспоненциального распределения интервалов времени между двумя событиями интервал времени от любого случайного момента до момента наступления очередного события имеет такое же экспоненциальное распределение с тем же параметром . В соответствии с этим свойством интервалы 7 5 3 , , τ τ τ имеют экспоненциальное распределе - ние с параметром λ и, следовательно, также удовлетворяют сформулиро- ванному выше условию для марковского процесса. Таким образом, случайный процесс, протекающий в системе с простейшим потоком заявок и экспоненциальным обслуживанием, является марковским. 6. Матрица интенсивностей переходов . Графу переходов (рис.5.3) соответствует матрица интенсивностей переходов: 8 7 6 5 4 3 2 1 τ τ τ τ τ τ τ τ " 8 " 6 " 5 " 2 t t t t ' 7 ' 4 ' 3 ' 1 t t t t 8 7 6 5 4 3 2 1 t t t t t t t t E 1 E 0 а) б) в) г) д) t t t t t Рис .5.4. Диаграммы процессов в СМО с отказами 194 Раздел 5. Численное моделирование µ µ λ λ − − = 1 0 1 0 i E G Действительно, переход из состояния E 0 в состояние E 1 соответствует поступлению заявки в систему с интенсивностью λ , а переход из состояния E 1 в состояние E 0 соответствует завершению обслуживания заявки в приборе с интенсивностью µ Диагональные элементы матрицы определяются из условия (5.4) – сумма элементов каждой строки должна быть равна нулю. 7. Система уравнений . Система уравнений для определения стационарных вероятностей, составленная по графу переходов с применением правила 1, имеет вид: = + = = 1 1 0 0 1 1 0 p p p p p p λ µ µ λ , где последнее уравнение представляет собой нормировочное условие (5.10). Учитывая, что первое и второе уравнение одинаковы (или, как говорят математики, линейно зависимы) и удаляя одно из них, окончательно получим: = + = 1 1 0 1 0 p p p p µ λ Решая эту систему , получим следующие значения стационарных вероятностей состояний марковского процесса : y y p y p + = + = + = + = 1 ; 1 1 1 0 µ λ λ µ λ µ , где µ λ / = y - нагрузка системы. 8. Расчет характеристик СМО . Для расчета характеристик СМО можно воспользоваться следующими математическими зависимостями, вытекающими из зависимостей (3.6) – (3.18): 1) нагрузка: b y λ µ λ = = / (по определению); 2) загрузка определяется как вероятность работы прибора : 1 p = ρ и не совпадает с нагрузкой даже в случае 1 < y , что характерно для систем с отказами и потерями заявок, причём всегда y < ρ ; 3) коэффициент простоя системы определяется как вероятность отсутствия заявок в системе или, по определению, через загрузку системы: ρ η − = = 1 0 p ; 4) среднее число заявок в системе: ρ = = 1 p m , определяемое как математическое ожидание случайной величины: в системе может Раздел 5. Численное моделирование 195 p 1 π ρ , , , 1 m p ) 1 ( , , 0 π η − p y ) ( 1 µ λ = = y 0 Рис .5.5. Характеристики СМО находиться либо ноль заявок с вероятностью 0 p , либо одна заявка с вероятностью 1 p , тогда среднее число заявок равно 1 1 0 1 0 p p p m = ⋅ + ⋅ = ; 5) вероятность потери заявок в результате отказа в обслуживании из- за занятости прибора в соответствии с (3.18) совпадает с вероятностью того, что система занята обслуживанием заявок: 1 1 1 1 1 p y y y p K y n = + = − = − = = ρ π π , где учтено, что для рассматриваемой СМО без накопителя y y p + = 1 1 ; 6) производительность системы: λ π λ ) 1 ( ' − = , определяемая как интенсивность потока обслуженных заявок на выходе системы; 7) интенсивность потока не обслуженных заявок, то есть получивших отказ: λ π λ = '' ; 8) среднее время пребывания заявок в системе: b m u = = ' / λ (определяется по формуле Литтла (3.15) и, как следовало ожидать, равно средней длительности обслуживания заявок; отметим, что в формуле Литтла используется интенсивность ' λ потока обслуженны х заявок, а не входящего потока λ ). 9. Анализ свойств системы . Анализ полученных зависимо-стей (рис.5.5) показывает, что с рос- том нагрузки коэффициент простоя системы, равный 0 p , уменьшается, а загрузка системы, определяемая как вероятность 1 p того, что прибор ра- ботает, (а также среднее число зая-вок в системе и вероятность отказа) увеличивается, причем их сумма всегда равна единице. При ∞ → y коэф- фициент простоя 0 → η , в то время как загрузка 1 → ρ . Заметим также, что нагрузка системы определяется через стационарные вероятности как отношение вероятности работы системы к вероятности простоя: 0 1 / p p y = (что легко может быть получено из выражений для 0 p и 1 p ) или, что то же самое, через загрузку и коэффициент простоя: η ρ / = y 5.4.2. Многоканальная СМО без накопителя (M/M/N/0) 196 Раздел 5. Численное моделирование Рассмотрим многоканальную систему массового обслуживания (СМО) с отказами, в которую поступает случайный поток заявок, задержи- ваемых в приборе на случайное время (рис.5.6). Заявка, поступившая в систему и заставшая прибор занятым, получает отказ в обслуживании и теряется. Таким образом, в системе, кроме входящего потока заявок с интенсивностью λ , образуются еще два потока: выходящий поток обслу- женных в приборе заявок с интенсив-ностью ' λ и поток необслуженных заявок (получивших отказ в обслу-живании) с интенсивностью " λ Очевидно, что λ λ λ = + " ' 1. Описание системы . 1.1. Система содержит N обслуживающих приборов П 1 ,…,П N , то есть является многоканальной 1.2. В систему поступает один класс заявок (поток однородный ). 1.3. Все приборы идентичны, то есть любая заявка может быть обслужена любым прибором за одно и то же случайное время. 1.4. В системе отсутствует накопитель. 2. Предположения и допущения . 2.1. Поступающие в систему заявки образуют простейший поток с интенсивностью λ 2.2. Длительность обслуживания заявок в любом приборе распреде- лена по экспоненциальному закону с интенсивностью b / 1 = µ , где b – средняя длительность обслуживания заявок в приборе. 2.3. Дисциплина буферизации – с отказами : заявка, поступившая в систему и заставшая все приборы занятыми обслуживанием других заявок, теряется. 2.4. Дисциплина обслуживания – в естественном порядке : заявка, поступившая в систему принимается на обслуживание, если есть хотя бы один свободный прибор. Если заявка застала свободными несколько приборов, то она направляется в один из них случайным образом. 3. Кодирование состояний случайного процесса . В качестве параметра, описывающего состояние случайного процесс- са, как и ранее, будем рассматривать количество заявок k, находящихся в СМО. При этом система в любой момент времени может находиться в одном из ) 1 ( + N состояний: E 0 : 0 = k – в системе нет заявок (система простаивает); E 1 : 1 = k – в системе находится 1 заявка (один прибор работает, остальные – простаивают); E 2 : 2 = k – в системе находится 2 заявки (два прибора работают, П 1 µ Рис . 5.6. Многоканальная СМО с отказами " λ П N ' λ λ … Раздел 5. Численное моделирование 197 остальные – простаивают); … E N : N k = – в системе находится N заявок (все приборы работают). 4. Размеченный граф переходов случайного процесса представлен на рис.5.7. В один и тот же момент времени в системе может произойти только одно из двух событий, которые приводят к изменению состояния случай- ного процесса. 1. Поступление заявки в систему с интенсивностью λ . При этом: • если случайный процесс находится в состоянии |