Системы массового обслуживания при наличии входного и выходного потоков
Автор работы: Пользователь скрыл имя, 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
Это свойство обычно
называют отсутствием памяти, оно является
еще одним доказательством того, что описанный
процесс является совершенно случайным.
2.2. Входной поток
В предыдущем пункте
был рассмотрен случайный процесс с <чистыми
поступлением требований, для которого
характерно, что поступившее в систему
требование присоединяется к очереди
и не покидает ее до тех пор, пока не будет
обслужено. Такие процессы называют процессами
чистого рожде¬ния. Найдем аналитические
представления Р~(t) для процесса чистого
рожде¬ния с экспоненциальным распределением
вероятностей интервалов времени между
двумя последовательными поступлениями
требований на обслужива¬ние.
Для сколь угодно малого,
но не равного нулю интервала h при n>0,
имеем
n поступлений в течение
t единиц времени и ни
одного поступления в интервале h
Рn(t+h) = или
n-1 поступление в течение t единиц времени
и
одно поступление в интервале 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-й день уровень запасов окажется
равным или будет меньше пяти единиц. В
этом случае имеем
Вычисления, проведенные
по последней формуле, сведены в таблицу
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 требований(клиентов),
то есть клиенты, не попавшие в блок ожидания,
вынуждены об¬служиваться в другом месте.
Наконец, источник, порождающий заявки
на обслуживание, имеет неограниченную
емкость.