Реферат: Теория массового обслуживанияс ожиданием.
содержаниеВведение в теорию массового обслуживания с ожиданием_________________ 2
1. Постановка задачи.____________________________________________________ 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), как легко в этом убедится.
Вероятность первого из указанныхсобытий равна
/>
вероятностьвторого события
/>
Такимобразом,
/>
Отсюдаочевидным образом приходим к уравнению
/> (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:
/> (4)
Подобные же рассуждения для k ³ m приводят куравнению
/>` (5)
Дляопределения вероятностей Pk(t) мы получили бесконечную системудифференциальных уравнений (2)-(5). Ее решение представляет несомненныетехнические трудности.
3.Определение стационарного решения.
В теории массового обслуживанияобычно изучают лишь установившееся решение для t ® ¥.Существование таких решений устанавливается так называемыми эргодическимитеоремами, некоторые из них позднее будут нами установлены. В рассматриваемойзадаче оказывается, что предельные или, как говорят обычно, стационарныевероятности существуют. Введем для них обозначения Pk. Заметимдополнительно, (этого мы также сейчас не станем доказывать), что /> при t®¥.
Сказанное позволяет заключить, чтоуравнения (3), (4) и (5) для стационарных вероятностей принимают следующий вид:
/> (6)
при1 £ k < m
/> (7)
приk ³ m
/> (8)
К этим уравнениям добавляется нормирующее условие
/> (9)
Для решения полученной бесконечнойалгебраической системы введем обозначения: при 1£ k<m
/>
приk ³ m />
Система уравнений (6)-(8) в этихобозначениях принемает такой вид:
z1=0, zk-zk+1=0при k ³ 1
Отсюда заключается, что при всех k ³ 1 zk =0
т.е. при 1 £ k <m
kmPk=lPk-1 (10)
ипри k ³m mmPk=lPk-1 (11)
Введем для удобства записи обозначение
r=l/m.
Уравнение (10) позволяет заключить, что при 1 £ k < m
/> (12)
При k ³ m из уравнения (11) находим, что
/>
иследовательно, при k ³ m
/> (13)
Остается найти P0. Дляэтого в (9) подставляем выражения Pk из (12) и (13). В результате
/>
Так бесконечная сумма, стоящая вквадратных скобках, находится только при условии, что
r <m (14)
топри этом положении находим равенство
/> (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}=/>. (16)
Прежде чем преобразовать эту формулук виду, удобному для пользования, приготовим некоторые необходимые нам длядальнейшего сведения. Прежде всего для случаев m=1 и m=2 найдем простые формулыдля P0. несложные преобразования приводят к таким равенствам: приm=1
P0=1-r, (17)
апри m=2
/> (18)
Вычислим теперь вероятность того,что все приборы будут заняты в какой-то наудачу взятый момент. Очевидно, чтоэта вероятность равна
/> (19)
Этаформула для m=1 принимает особенно простой вид:
p=r, (20)
приm=2
/> (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) следует, что />, поэтому при t>0
/> (22)
Самособой разумеется, что при t<0 />.
Функция />имеетв точке t=0 разрыв непрерывности, равный вероятности застать все приборызанятыми.
6.Средняя длительность ожидания.
Формула (22) позволяет находить всеинтересующие нас числовые характеристики длительности ожидания. В частности,математическое ожидание длительности ожидания начала обслуживания или, какпредпочитают говорить, средняя длительность ожидания равна
/>
Несложныевычисления приводят к формуле
/> (23)
Дисперсиявеличины g равна
/>.
Формула (23) дает среднююдлительность ожидания одного требования. Найдем среднюю потерю временитребованиями, пришедшими в систему обслуживания в течение промежутка времениT. За время T в систему поступает lTтребований в среднем; общая потеря ими времени на ожидание в среднем равна
/> (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. Вероятность того, что прибывшийсамолет не задерживается, равна
/> (14.54)
Вероятность того, что будет задержан одинсамолет, найдем, рассмотрев все задержки одиночных самолетов между двумянезадерживаемыми самолетами. Самолет, который будет задержан, должен прибытьчерез промежуток времени t1<T после прибытия незадерживаемогосамолета, непосредственно предшествующего ему, а незадерживаемый самолет,непосредственно следующий за ним, должен прибыть через промежуток времениt>2T-t1. Таким образом, искомая вероятность совместногопоявления этих двух событий равна
/>
Вероятность того, что будет задержано двасамолета, находится аналогично (рассматривается два задерживаемых самолета между двумя незадерживаемыми) путем вычисления вероятности совместногопоявления событий:
t1 < T — для первогозадерживаемого самолета, следующего за незадерживаемым;
t2 < 2T- t1 — для второго задерживаемого самолета, следующего за первым задерживаемым;
t < 3T- t1 — t2- длянезадерживаемого самолета, следующего непосредственно за двумя задерживаемыми.
В результате для двух задерживаемых самолетов получаем
/>. (14.55)
Общее выражение для вероятноститого, что задерживается n-1 самолетов, имеет вид an Tn-1 e-nT , где an — коэффициент,зависящий только от n. Очевидно, что должно выполняться соотношение
/> (14.56)
или
/> (14.57)
где величина UºTe-T для малых T определяетсяоднозначно, следовательно, T можно выразить как функцию от U:
/> (14.58)
Используято обстоятельство, что начало координат — кратный полюс, имеем
/> (14.59)
Следовательно, разложивподынтегральное выражение в ряд и выбрав коэффициент при T-1, можнонайти вычет.
Вероятность того, что один за другимзадерживаются n-1 самолетов, равна
/> (14.60)
Используя формулу Стирлинга для n!, Пирси приводит ряд кривых для этогораспределения.
Среднее число самолетов, находящихсяв системе (с учетом первого самолета, совершающего посадку без ожидания),равно
/> (14.61)
Это выражение можно легко найти,дифференцируя выражение (14.56) по T и производя упрощения. (Заметим, что приT=1 задерживаются все самолеты). Аналогично находим второй начальный момент,он равен />.
Доля задерживаемых самолетовопределяется как отношение среднего числа самолетов, находящихся в системе, безучета самолета, совершающего посадку, к среднему числу самолетов:
/>.
Распределение длительности посадкинайдем путем следующих рассуждений. Все промежутки времени длительностьюt<T имеют нулевую частоту; промежутки времени длительностью t=T появляютсяс частотой t; доля задерживаемых самолетов, т.е. доля промежутков временидлительностью t>T, появляется с частотой 1-T появления незадерживаемыхсамолетов, умноженной на вероятность их прибытия, т.е. на e-(t+T).Используем единичную функцию H(T- t) (которая равна единице для положительныхзначений аргумента и равна нулю для отрицательных; ее производная являетсядельта-функцией) и дельта-функцию d(T-t),чтобы представить это распределение в виде
/>
Теперь, используя интегральноеуравнение Линдли, можно получить распределение времени ожидания. Путемдетального анализа Пирси находит выражение для распределения в промежуткевремени t, mT < t < (m+1)T:
/>
откуда после интегрирования по t (0 £ t £ ¥) он определяет T как долюзадерживаемых самолетов. Заметим, что при суммировании по m необходиморассматривать интервалы (mT,(m+1)T). Отсюда находим также среднее времяожидания
/>.
Заметим, что время ожиданияувеличивается с ростом T. Приведенное выше распределение дает критерии дляопределения необходимой пропускной способности аэропорта.[4]
/>/>Список литературы
1. Д.Кениг, Д.Штойян.Методы теории массового обслуживания: Пер. с нем. /Под. ред. Г.П.Климова. М.,1981.
2. Г.И.Ивченко,В.А.Каштанов, И.Н.Коваленко. Теория массового обслуживания. М., 1982.
3. Б.В.Гнеденко,И.Н.Коваленко. Введение в теорию массового обслуживания. М., 1987.
4. Т.Л.Саати. Элементытеории массового обслуживания и ее приложения: Пер. с англ. /Под. ред. И.Н.Коваленко, изд-ие 2. М., 1971.