Реферат: Теория массового обслуживания с ожиданием

содержание

TOCo «1-1» «Тема;1; Подзаголовок 1;1»

Введение в теориюмассового обслуживания с ожиданием_________________ GOTOBUTTON _Toc374500017 PAGEREF _Toc374500017 2

1. Постановка задачи.____________________________________________________

GOTOBUTTON _Toc374500019 PAGEREF _Toc374500019 3

2. Составление уравнений._______________________________________________ 4

3. Определение стационарного решения.__________________________________ 5

4. Некоторые подготовительные результаты.______________________________ 6

5. определение функции распределениядлительности ожидания.___________ 7

6. Средняя длительность ожидания.______________________________________ 8

Заключение. Приложение теории к движениювоздушного транспорта______ 10

Список используемой литературы_______________________________________ 13

Введение

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

Системы с ожиданием — возможно ожиданиедля любого числа требований, которые не могут быть обслужены сразу. Онисоставляют очередь, и с помощью некоторой дисциплиныобслуживания определяются, в каком порядке ожидающие требования выбираютсяиз очереди для обслуживания.[1]

Изобразимданную систему графически (рис. 1). Здесь кружочек 1 — обслуживающий прибор,треугольник — накопитель, кружочек О — источник требований. Требование,возникающее в источнике в момент окончания фиктивной операции “ожидания требований”,поступает в накопитель. Если в этот момент прибор 1 свободен, то требованиенемедленно поступает на обслуживание. Если же прибор занят, то требованиеостается в накопителе, становясь в конец имеющейся очереди

Как только прибор 1 заканчивает производимую им операцию,немедленно принимается к обслуживанию требование из очереди т.е. из накопителя,и начинается новая операция обслуживания. Если требований в накопителе нет, тоновая операция не начинается, стрелкой а показанпоток требований от источника к накопителю, стрелкой b — поток обслуженных требований.[2]

Система массового обслуживания сожиданием

1. Постановка задачи.

Мы изучим здесь классическую задачу теории массовогообслуживания в тех условиях, в каких она была рассмотрена и решена Эрлангом. Наm одинаковых приборов поступает простейший поток требований интенсивности l. Еслив момент поступления требования имеется хотя бы один свободный прибор, ононемедленно начинает обслуживаться. Если же все приборы заняты, то вновьпоступившее требование становится в очередь за всеми теми требованиями, которыепоступили раньше и еще не начали обслуживаться. Освободившийся приборнемедленно приступает к обслуживания очередного требования, если только имеетсяочередь. Каждое требование обслуживается только одним прибором, и каждый приборобслуживает в каждый момент не более одного требования. Длительностьобслуживания представляет собой случайную величину с одним и тем жераспределением вероятностей F(x). Предполагается, что при

x

³ 0

F(x) = 1 — e-

mx, (1)

где

m > 0 — постоянная.

Эрланг решилэту задачу, имея в виду постановки вопросов возникших к тому времени втелефонном деле.

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

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

Действительно,пусть fa(t) означает вероятность того, что обслуживание, которое ужепродолжается время a, продлится еще не менее чем t. В предположении, чтодлительность обслуживания распределена показательно, f0(t)=e-

mt. Далее ясно, что f0(a)= e-ma и f0(a+t)= e-m(a+1). А так как всегда f0(a+t)=f0(a)fa(t), то e-m(a+t)= e-ma f0(t) и, следовательно,

fa(t) = e-

mt= fo(t).

Требуемое доказано.

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

где,

m > 0, а k — целое положительноечисло.

РаспределениеЭрланга представляет собой распределение суммы k независимых слагаемых, каждоеиз которых имеет распределение (1).

Обозначим дляслучая распределения (1) через

h время обслуживания требования. Тогдасредняя длительность обслуживания равна

Это равенстводает нам способ оценки параметра

m по опытным данным. Как легковычислить, дисперсия длительности обслуживания равна

при t£0,

при t>0,

2. Составлениеуравнений.

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

Найдём теуравнения, которым удовлетворяют вероятности Pk(t). Одно изуравнений очевидно, а именно для каждого t

. (2)

Найдем сначалавероятность того, что в момент t+h все приборы свободны. Это может произойтиследующими способами:

в момент t всеприборы были свободны и за время h новых требований не поступало;

в момент t одинприбор был занят обслуживанием требования, все остальные приборы свободны; завремя h обслуживание требования было завершено и новых требований не поступило.

Остальныевозможности, как-то: были заняты два или три прибора и за время h работа на нихбыла закончена — имеют вероятность o(h), как легко в этом убедится.

Вероятностьпервого из указанных событий равна

вероятностьвторого события

Таким образом,

Отсюда очевидным образом приходим куравнению

<img src="/cache/referats/6138/image016.gif" v:shapes="_x0000_i1032"> (3)

Перейдемтеперь к составлению уравнений для Pk(t) при k

³1. Рассмотрим отдельно два различных случая: 1 £ k < m и k ³ m. Пусть вначале 1 £k < m. Перечислим только существенные состояния, из которыхможно прийти в состояние Ek в момент t+h. Эти состояния таковы:

В момент tсистема находилась в состоянии Ek, за время h новых требований непоступило и ни один прибор не окончил обслуживания. Вероятность этого событияравна

В момент tсистема находилась в состоянии Ek-1, за время h поступило новоетребование, но ни одно ранее находившееся требование не было законченообслуживанием. Вероятность этого события равна

В момент tсистема находилась в состоянии Ek+1, за время h новых требований непоступило, но одно требование было обслужено. Вероятность этого равна

Все остальныемыслимые возможности перехода в состояние Ek за промежуток времени hимеют вероятность, равную 0(h).

Собрав воединонайденные вероятности, получаем следующее равенство:

Несложныепреобразования приводят нас к такому уравнению для 1

£k < m:

<img src="/cache/referats/6138/image026.gif" v:shapes="_x0000_i1037"> (4)

Подобные жерассуждения для k

³ m приводят к уравнению

<img src="/cache/referats/6138/image028.gif" v:shapes="_x0000_i1038">` (5)

Для определения вероятностей Pk(t) мы получили бесконечнуюсистему дифференциальных уравнений (2)-(5). Ее решение представляет несомненныетехнические трудности.

3. Определение стационарного решения.

В теориимассового обслуживания обычно изучают лишь установившееся решение для t

® ¥. Существование таких решений устанавливаетсятак называемыми эргодическимитеоремами, некоторые из них позднеебудут нами установлены. В рассматриваемой задаче оказывается, что предельныеили, как говорят обычно, стационарные вероятности существуют. Введем для нихобозначения Pk. Заметим дополнительно, (этого мы также сейчас не станем доказывать),что <img src="/cache/referats/6138/image030.gif" v:shapes="_x0000_i1039"> при t®¥.

Сказанноепозволяет заключить, что уравнения (3), (4) и (5) для стационарных вероятностейпринимают следующий вид:

<img src="/cache/referats/6138/image032.gif" v:shapes="_x0000_i1040"> (6)

при 1

£k < m

<img src="/cache/referats/6138/image034.gif" v:shapes="_x0000_i1041"> (7)

при k

³m

<img src="/cache/referats/6138/image036.gif" v:shapes="_x0000_i1042"> (8)

К этим уравнениям добавляется нормирующее условие

<img src="/cache/referats/6138/image038.gif" v:shapes="_x0000_i1043"> (9)

Для решенияполученной бесконечной алгебраической системы введем обозначения: при 1

£k<m

при k

³m <img src="/cache/referats/6138/image042.gif" v:shapes="_x0000_i1045">

Системауравнений (6)-(8) в этих обозначенияхпринемает такой вид:

z1=0, zk-zk+1=0 при k

³1

Отсюда заключается, что при всех k

³1 zk =0

т.е. при 1

£k < m

k

mPk=lPk-1 (10)

и приk

³ m mmPk=lPk-1 (11)

Введем для удобства записи обозначение

r=

l/m.

Уравнение (10)позволяет заключить, что при 1

£ k < m

<img src="/cache/referats/6138/image044.gif" v:shapes="_x0000_i1046"> (12)

При k

³ m из уравнения (11) находим, что

иследовательно, при k

³m

<img src="/cache/referats/6138/image048.gif" v:shapes="_x0000_i1048"> (13)

Остается найтиP0. Для этого в (9) подставляем выражения Pk из (12) и(13). В результате

Такбесконечная сумма, стоящая в квадратных скобках, находится только при условии,что

r

<m (14)

то приэтом положении находим равенство

<img src="/cache/referats/6138/image052.gif" v:shapes="_x0000_i1050"> (15)

Если условие(14) не выполнено, т.е. если

r ³m, то ряд, стоящий в квадратной скобкеуравнения для определения P0, расходится и, значит, P0 должнобыть равно 0. Но при этом, как следует из (12) и (13), при всех k ³1 оказывается Pk =0.

Методы теориицепей Маркова позволяют заключить, что при

r ³ m с течением времени очередь стремитсяк ¥ по вероятности.

4. Некоторые подготовительныерезультаты.

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

g. Рассмотрим сейчас только задачу определения распределениявероятностей длительности ожидания в уже установившемся процессе обслуживания.Обозначим далее через P{g >t} вероятность того, что длительность ожидания превзойдет t, и через Pk{g > t} вероятность неравенства, указанного вскобке, при условии, что в момент поступления требования, в очереди уженаходится k требований. В силу формулы полной вероятности имеем равенство

P

{g >t}=<img src="/cache/referats/6138/image054.gif" v:shapes="_x0000_i1051"> (16)

Прежде чемпреобразовать эту формулу к виду, удобному для пользования, приготовимнекоторые необходимые нам для дальнейшего сведения. Прежде всего для случаев m=1 и m=2 найдем простые формулыдля P0. несложные преобразования приводят к таким равенствам: приm=1

P0=1-

r, (17)

а приm=2

<img src="/cache/referats/6138/image056.gif" v:shapes="_x0000_i1052"> (18)

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

<img src="/cache/referats/6138/image058.gif" v:shapes="_x0000_i1053"> (19)

Эта формула для m=1 принимает особеннопростой вид:

p=

r, (20)

приm=2

<img src="/cache/referats/6138/image060.gif" v:shapes="_x0000_i1054"> (21)

Напомним, чтов формуле (19)

r может принимать любое значение от 0 до m (включительно).Так что в формуле (20) r < 1, а в (21) r <2.

5. определениефункции распределения длительности ожидания.

Если в моментпоступления требования в очереди уже находились k-m требований, то поскольку обслуживание происходит впорядке очередности, вновь поступившее требование должно ожидать, когда будут обслужены k-m+1 требований. Пусть qs(t)означает вероятность того, что за промежуток времени длительности t послепоступления интересующего нас требования закончилось обслуживание ровнотребований. Ясно, что k

³m имеет место равенство

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

Если всеприборы заняты обслуживанием и еще имеется достаточная очередь требований,которые ожидают обслуживания, то поток обслуженных требований будет простейшим.Действительно, в этом случае все триусловия — стационарность, отсутствиепоследействия и ординарность — выполнены. Вероятность освобождения запромежуток времени t ровно s приборов равна (это можно показать и простымподсчетом)

Итак,

и,следовательно,

Новероятности Pk известны:

поэтому

очевиднымипреобразованиями приводим правую часть последнего равенства к виду

Из формул (13) и (19) следует, что <img src="/cache/referats/6138/image077.gif" v:shapes="_x0000_i1063">

<img src="/cache/referats/6138/image079.gif" v:shapes="_x0000_i1064"> (22)

Самособой разумеется, что при t<0 <img src="/cache/referats/6138/image081.gif" v:shapes="_x0000_i1065">

Функция <img src="/cache/referats/6138/image083.gif" v:shapes="_x0000_i1066"> равный вероятности застать все приборызанятыми.

6. Средняя длительность ожидания.

Формула (22)позволяет находить все интересующие нас числовые характеристики длительностиожидания. В частности, математическое ожидание длительности ожидания началаобслуживания или, как предпочитают говорить, средняя длительность ожиданияравна

Несложныевычисления приводят к формуле

<img src="/cache/referats/6138/image087.gif" v:shapes="_x0000_i1068"> (23)

Дисперсия величины

g равна

Формула (23)дает среднюю длительность ожидания одного требования. Найдем среднюю потерю времени требованиями, пришедшимив систему обслуживания в течение промежутка времени T. За время T в системупоступает

lT требований в среднем; общая потеря ими времени на ожиданиев среднем равна

<img src="/cache/referats/6138/image091.gif" v:shapes="_x0000_i1070"> (24)

Приведемнебольшие арифметические подсчеты, которые продемонстрируют нам, как быстровозрастают суммарные потери времени на ожидание с изменением величины

r. Приэтом мы ограничиваемся случаем T=1 и рассматриваем лишь самые малые значения m:m=1 и m=2.

При m=1 в силу (20)

При

r=0.1;0.3; 0.5; 0.9; значение alприблизительно равно 0.011; 0.267; 0.500; 1.633; 8.100.

При m=2 в силу(21)

При

r=0.1;1.0; 1.5; 1.9 значение alприблизительно равно 0.0003; 0.333; 1.350; 17.587.

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

Приложение теории к движению воздушноготранспорта

С некоторымипонятиями, связанными с управлением движением воздушного транспорта, мыпознакомились в иллюстративном приложении первой главы. Пирси рассмотрелприложения некоторых идей теории массового обслуживания к организации посадкисамолетов. В данном случае обычнопредставляет интерес сокращение времени посадки. Вычислим вначале вероятностьтого, что один за другим n-1 самолетов ожидают приземления.

Допустим, чтосамолеты приближаются к зоне управления со случайных направлений черезслучайные промежутки времени, распределенные по экспоненциальному закону, спостоянной интенсивностью прибытия, которая принимается равной одной единице.Следовательно, e-t — распределение промежутков времени междумоментами прибытия. Самолет, которыйприбывает через промежуток времени, меньший минимального времени, необходимо для безопасного предыдущегосамолета, задерживается на минимальное время. Отношение минимального времени,необходимого для безопасной посадки, к средней длительности промежутка временимежду прибывающими самолетами обозначается T (для простоты будем считать, чтодля данного аэропорта эта величина постоянна). Обычно представляет интересслучай T<1. Вероятность того, чтоприбывший самолет не задерживается, равна

<img src="/cache/referats/6138/image097.gif" v:shapes="_x0000_i1073"> (14.54)

Вероятность того, чтобудет задержан один самолет, найдем, рассмотрев все задержки одиночныхсамолетов между двумя незадерживаемыми самолетами. Самолет, который будетзадержан, должен прибыть через промежуток времени t1<T послеприбытия незадерживаемого самолета, непосредственно предшествующего ему, анезадерживаемый самолет, непосредственно следующий за ним, должен прибыть черезпромежуток времени t>2T-t1. Таким образом, искомая вероятностьсовместного появления этих двух событий равна

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

еще рефераты

Еще работы по экономико-математическому моделированию

Реферат по экономико-математическому моделированию

Финансирование с ЕБРР

29 Августа 2013

Реферат по экономико-математическому моделированию

Экономико-математическое моделирование

29 Августа 2013

Реферат по экономико-математическому моделированию

Экономико-математическое моделирование. Коммерческие банки. Анализ деятельности с точки зрения ЭММ

29 Августа 2013

Реферат по экономико-математическому моделированию

Основные методы и содержание профориентационной работы

29 Августа 2013