Системы массового обслуживания при наличии входного и выходного потоков

Автор работы: Пользователь скрыл имя, 15 Сентября 2014 в 15:38, реферат

Описание работы

В окружающей нас действительности много реально протекающих процессов обслуживания на транспорте, в торговле, в медицине, в связи и т.д. Все они могут быть изучены, исходя из соответствующих им моделей систем обслуживания. Создание систем телефонной связи и необходимость расчета их пропускной способности послужили в 20-х годах ХХ века стимулом раз¬вития теории массового обслуживания. Первые исследования группы Operations research британских ВВС была посвящена решению задач этой же тема¬тики (очередь самолетов противника, которая обслуживается снарядами зе¬нитных батарей)~ С 1970-х годов интенсивно разрабатываются методы анали¬за и оптимизации процессов обслуживания требований на вычисления с ис¬пользованием одного или нескольких компьютеров (системы разделенного времени).

Содержание работы

1.Модели массового обслуживания
1.1.Задачи, связанные с обслуживанием очередей -3
1.2.Функционирование моделей систем массового обслуживания -4
1.3.Описание математической модели -5
2.Система обслуживания с пуассоновским потоком на входе и выходе.
2.1.Система массового обслуживания со специальными свойствами -7
2.2.Входной поток -8
2.3.Выходной поток -10
2.4.Верификация пуассоновского закона распределения при анализе реальных систем -12
3.Системы массового обслуживания при наличии входного и выходного потоков.
3.1.Типы структур систем массового обслуживания -12
3.2.Операцинные характеристики систем массового обслуживания -14
3.3. Модель(M/M/1):(GD/¥/¥) -15
3.4. Модель(M/M/1)(GD/N/¥) -16
4.Литература. -18

Файлы: 1 файл

Содержание.docx

— 60.67 Кб (Скачать файл)

= exp(—a.(T+s))Iexp(--a.s) exp(—wT) = Р {t>T}.

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

 

 

2.2. Входной поток

 

 

В предыдущем пункте был рассмотрен случайный процесс с <чистыми поступлением требований, для которого характерно, что поступившее в систему требование присоединяется к очереди и не покидает ее до тех пор, пока не будет обслужено. Такие процессы называют процессами чистого рожде¬ния. Найдем аналитические представления Р~(t) для процесса чистого рожде¬ния с экспоненциальным распределением вероятностей интервалов времени между двумя последовательными поступлениями требований на обслужива¬ние.

Для сколь угодно малого, но не равного нулю интервала h при n>0, имеем

n поступлений в течение t единиц времени и ни 
одного поступления в интервале h 
Рn(t+h) = или 
n-1 поступление в течение t единиц времени и 
одно поступление в интервале h.

Применяя теоремы сложения и умножения вероятностей, получаем Рn(t+h) = Рn(t).Ро(h) + Рn-1(t)*Р1(h), n=1,2,...

Po(t+h) = Р0(t).Р0(h)

Так как Р0(h) = ехр(-l*h), Р1(h) = 1- Р0(h)=1 - ехр(-l*h), то для малых значений h можно написать приближенные равенства 
• Р0(h)= 1 –l*h, Р1(h)=l*h, 
Р0(t+h)= Р0(t)*(1-l*h). 
Последние равенства перепишем в следующем виде: 
[Рn(t+h)- Рn(t)]/h=-l *Рn(t) +l *Pn-1(t) 
• [Р0(t+h)- Po(t)]/h=- l*Ро(t) 
При h®0 эти равенства становятся точными и переходят в разностно--дифференциальные уравнения 
Pn(t)=- l *Pn(t)+ l*Pn-1(t),n>0, 
Р0 (t)==- l*P0(t). 
Решение последнего уравнения нам известно Po(t) = ехр(-l *t). В теории разностно-дифференциальных уравнений с постоянными коэффициентами хорошо изучены полученные уравнения (n>О). Их решениями являются сле-дующие функции 
Pn(t)=[( l*t)n* exp(-l *t)]/n!,n=1,2... 
Убедиться в справедливости написанных представлений функций Рn(t) можно непосредственной подстановкой их в соответствующие уравнения. 
В теории вероятностей распределение вероятностей Рn(t) известно как распределение Пуассона. Среднее значение (математическое ожидание) этого распределения равно l*t. 
Итак, если временные интервалы между моментами двух последовательных событий распределены по экспоненциальному закону с интенсивностьюl, то число поступлений требований на обслуживание в интервале времени t единиц времени характеризуется пуассоновским распределением со средним значением равным l*t. 
Пример 6.1. Найти математическое ожидание и дисперсию для распреде-ления вероятностей (Пуассона) 
Рn(t)=[( l*t)n*ехр(-l*t)]/n!, n=0,1,2,... 
Решение. В начале заметим, что справедливы два равенства 
M[t] =Sп*Pn(t)=S (n-1)*( l*t)n-1 *ехр(l*t)/(n-1)! = l*t 
и S(l*t)n-1*exp(-l*t)/(п-1)! = ехр(-l*t)*ехр(l*t) = 1. 
Чтобы установить справедливость этих равенств, достаточно вспомнить разложение функции ехр(l*t) в ряд Тейлора-Маклорена

ехр(l*t)=1 + (l*t)/1! + (l*t)2/2! + ...+ (l*t)n/n! +.... 
Первое приведенное равенство — математическое ожидание распределе¬ния Пуассона. Найдем дисперсию D[t]. Известно, что величину дисперсии можно найти по формуле 
D[tI=а2—М2[t], 
где а2 — второй начальный момент. Найдем а2.

а2 =Sn2(l*t)*ехр(-l*t)/n! = (l*t )Sn(l*t)n-1ехр(-l*t)/(n-1)! =(l*t)S[(n-1)+1]* (l*t)n-1*exp(-l*t)/(n-1)!= 
=( l*t)*[S(n-1)*( l*t)n-1*exp(l*t)/(n-1)!+S( l*t)n-1 *exp(l*t)/(n-1)!] 
Первая сумма в квадратных скобках равна l*t, а вторая — равна 1, поэтому D[t]= (l*t)2+(l*t)-( l*t)2=(l*t).

Следслвие. Дисперсия дискретной случайной величины, распределенной по закону Пуассона, равна математическому ожиданию этой величины, то есть D[t] = M[t] =(l*t). Отметим, что это уникальное свойство распределения Пуассона. Ни одно другое дискретное распределение случайной величины не обладает этим свойством. для предварительного суждения о том, является ли данное распределение пуассоновским, по эмпирическим данным достаточно 
вычислить математическое ожидание и дисперсию. Если с удовлетворитель¬ной точностью математическое ожидание и дисперсия при этом совпадают, то можно быть уверенным в том, что оно пуассоновское.

 

 

2.3. Выходные потоки

 

 

Процесс на выходе системы массового обслуживания рассматривают в предположении, что система начинает функционировать при наличии ,в ней N клиентов, которые после обслуживания выбывают из системы с интенсив-ностью m (экспоненциальное распределение интервалов времени). Процессы такого рода называют процессами "чистой"гибели. 
К категории процессов "чистой" гибели относится, например, изъятие из склада хранимых в нем запасов. В этом случае предполагается, что на складе имеется N единиц запасов, которые изымаются с интенсивностью m (единиц запасов в единицу времени). 
При условии абсолютной случайности исходов для малого интервала h можно записать (так же как и в случае <чистого~ рождения) 
Q0(h) = exp(-m*h)=1-m*h, Q1(h) = 1 - Q0(h)- m*h=1-m*h для величин Qn(t+h) имеют место следующие соотношения: 
Qn(t+h)=Qn(t)*1 + Qn-1(t)( m*h), 
Qn(t+h)= Qn(t)(1-m*h) + Qn-1(t)*( m*h), n = N-1, N—2,. ..,1, 
Qo(t+h)= Q0(t)*(1- m*h). 
Написанные приближенные равенства можно переписать в следующемвиде:

[QN(t+h)-QN(t)]/h=m*QN-1(t), 
[Qn(t+h) –Qn(t)]/h=-m*Qn-1(t), n=N-l, N-2,...,1, 
[Qo(t+h)- Qo(t)]/h =-m*Qo(t). 
Перейдя к пределу при h®0, получаем систему разностно-дифференциальных уравнений 
QN(t)= m*QN-1(t), 
Qn(t) =-m*Qn(t)+ m*Qn-1(t), n=N-1,N-2,...,1, 
Q0(t) =-m*Qo(t). 
Второе и третье разностно-дифференциальные уравнения имеют единст-венные решения 
Qn(t)=[ (m*t)n*exp(-m*t)]/n!, n=0,1,2,..,N-1 
Решение первого уравнения задается формулой 
QN(t)=1-SQn(t). 
Чтобы убедиться, что написанные формулы действительно являются ре-шениями приведенных разностно-дифференциальных уравнений, достаточно продифференцировать их и подставить в соответствующее уравнение.

Напомним, что Qn(t) — это вероятность n единиц выбывания в течение t единиц времени. Часто интерес представляет вероятность того, что по исте-чении t единиц времени в системе остается n заявок на обслуживание (n кли-ентов). Обозначим эту вероятность Rn(t). Тогда, если предположить, что в начальный момент времени число находящихся в системе клиентов (заявок на обслуживание) равнялось N, то будем иметь 
Rn(t) =QN-n(t) 
Откуда следует, что

Rn(t) = [(m*t)N-n*exp(-m*t)]/(N-n)!, n = 1,2,..,N. 
Ro(t) = 1S Rn(t).

Пример. В начале каждой недели складируется 15 единиц запасов, ко¬торые в течение недели расходуются. Изъятия запасов из складского поме¬щёния происходят лишь в первые шесть дней каждой недели и осуществляется в соответствии с пуассоновским распределением со средней интенсив¬ностью m= 3 (единиц запасов в 1 рабочий день). Как только уровень запасов снижается до пяти единиц, делается новый заказ на поставку в конце недели пятнадцати единиц запасов. Запасы по своей природе таковы, что все неис¬пользованные до конца недели предыдущие запасы приходят в негодность исписываются (ликвидируются).

Исследование ситуации. Учтем, что средняя интенсивность потребления m=3 (единиц в 1 день). 
Вычислим вероятность того, что уровень запасов понизится до пяти еди¬ниц в t-й день. Вероятность такого события вычисляется по формуле 
R5(t)= [(3t)15-5*ехр(-3t)]/(15—5)! = [(3t)10*exp(-3t)]/10! t=1,2,...,6. 
Результаты для определенных значений t сведены в таблицу

t(дни)

1

2

3

4

5

6

m*t

3

6

9

12

15

18

R5(t)

0.0008

0.0413

0.1186

0.1048

0.0486

0.0150


 

По условиям примера R5(t) есть вероятность возникновения необходимо¬сти формирования в t-й день нового заказа на пополнение склада пятнадца¬тью единицами запасов. Эта' вероятность достигает наибольшего значения при t =3, а затем постепенно падает по мере возрастания t (от t=4 до t=6).

Если нужно знать вероятность, с которой новый заказ на накопление за-пасов придется оформлять не позднее чем в t-й день, то нужно вычислить ве-роятность того, что в t-й день уровень запасов окажется равным или будет меньше пяти единиц. В этом случае имеем

Rn<=5(t) = R0(t) + R1(t) +.. + R5(t)=1-[R1(t)+R2(t)+..+R15(t)]+R1(t)+..+R5(t)=1-[R6(t)+R7(t)+..+R15(t)]= 
=1-S15n=6(3t)15-n*exp(-3t)/(15-n)!.

Вычисления, проведенные по последней формуле, сведены в таблицу

t(дни)

1

2

3

4

5

6

m*t

3

6

9

12

15

18

Rn<=5(t)

0.0012

0.0839

0.4126

0.7576

0.9303

0.9847


 

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

М{n | t=h} = Sn*Rn(6) = 0.5537 (единиц).

Это означает, что в конце недели в среднем обесценивается (идет на вы¬брос) меньше одной единицы запасов.

 

 

2.4. Верификация  пуассоновского закона распределения  при анали¬зе реальных систем.

 

 

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

1.. Организуется наблюдение за уже функционирующей сис¬темой массового обслуживания в течение некоторого времени с це¬лью выяснения являются ли поступления требований (или акты выбытия обслуженных клиентов) действительно случайными собы¬тиями. Если входной (или выходной) поток оказывается случайным, то это уже позволяет выдвинуть гипотезу о пуассоновском характе¬ре поступления требований на обслуживание (или выбывания об¬служенных клиентов из рассматриваемой системы). 
2. Собирается информация о количестве заявок на обслужи¬вание, поступивших в систему в течение первого часа, второго часа и т.д. Аналогичная процедура, может осуществляться и на выходе системы массового обслуживания. Затем вычисляется среднее зна¬чение интервала времени между двумя последовательными поступ¬лениями требований (математическое ожидание) или соответст¬вующие характеристики на выходе. Кроме математического ожида¬ния вычисляется дисперсия соответствующей случайной величины. Если вычисленные две характеристики случайной величины оказы¬ваются приблизительно одинаковыми, то с уверенностью можно считать, что мы имеем дело с распределением Пуассона.

 

 

3. Системы массового  обслуживания при наличии входного  и вы-ходного потоков.

3.1. Типы структур  систем массового обслуживания.

 

 

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

 
Заметим, что в любой произвольный момент времени всех находящихся клиентов можно разбить на тех. Кто находится в очереди (ждёт когда его начнут обслуживать) и тех, кто уже обслуживается. 
В настоящее время для характеристики любой системы массового обслу-живания приняты стандартные обозначения. восходящие к Д.Г. Кендаллу(1953 г). Они имеют следующую структуру: 
(а / b / с): (d / е / f ), 
где символы а, b, c, d, e, f характеризуют некоторые существенные элементы модельного представления процессов массового обслуживания.

а — тип распределения моментов поступлений заявок на обслуживание;

b— распределение времени обслуживания (или выбывания обслуженных клиентов);

с — число параллельно функционирующих узлов обслуживания(с=1,2,...,¥);

d — дисциплина очереди;

е — максимальное число допускаемых в систему требований (Число требо-ваний в очереди + число требований, принятых на обслуживание);

f— емкость источника, генерирующего заявки на обслуживание.

для конкретизации а и Ь приняты следующие стандартныё обозначения:

М — пуассоновское распределение моментов поступлений заявок на об-служивание или выбывания из системы, обслуженных клиентов (или экспо-ненциальное распределение интервалов времени между моментами последо-вательных поступлений требований или Продолжительностей обслуживания клиентов);

D — фиксированный (детерминированный) интервал времени  обслужива-ния одного клиента.

Например, структура (М /D/10): (GD/N/¥) означает, что речь идет о системе массового обслуживания с пуассоновским входным потоком, фикси¬рованным временем обслуживания и десятью параллельно функционирующими узлами обслуживания. дисциплина очереди не регламентирована Что подчеркивается парой символов GD. Кроме того, независимо от того, сколь¬ко требований поступает на вход обслуживающей системы, данная система(очередь + обслуживаемые клиенту) не может вместить более N требований(клиентов), то есть клиенты, не попавшие в блок ожидания, вынуждены об¬служиваться в другом месте. Наконец, источник, порождающий заявки на обслуживание, имеет неограниченную емкость.

Информация о работе Системы массового обслуживания при наличии входного и выходного потоков