Теория массового обслуживания с ожиданием
Введение
Судьбу требований, которые при поступлении в систему обслуживания застают все приборы занятыми, определяют с помощью задания типа системы обслуживания. Один из типов систем является система с ожиданием.
Системы с ожиданием - возможно ожидание для любого числа требований, которые не могут быть обслужены сразу. Они составляют очередь, и с помощью некоторой дисциплины обслуживания определяются, в каком порядке ожидающие требования выбираются из очереди для обслуживания.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 по опытным данным. Как легко вычислить, дисперсия длительности обслуживания равна
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
Список литературы
Д.Кениг, Д.Штойян. Методы теории массового обслуживания: Пер. с нем. /Под. ред. Г.П.Климова. М., 1981.
Г.И.Ивченко, В.А.Каштанов, И.Н.Коваленко. Теория массового обслуживания. М., 1982.
Б.В.Гнеденко, И.Н.Коваленко. Введение в теорию массового обслуживания. М., 1987.
Т.Л.Саати. Элементы теории массового обслуживания и ее приложения: Пер. с англ. /Под. ред. И.Н. Коваленко, изд-ие 2. М., 1971.
Для подготовки данной работы были использованы материалы с сайта http://referatovbank.ru/
topref.ru
СОДЕРЖАНИЕ
ВВЕДЕНИЕ____________________________________________________3
ЗАКЛЮЧЕНИЕ_________________________________________________13
СПИСОК ЛИТЕРАТУРЫ_________________________________________14
ВВЕДЕНИЕ
При исследовании операций часто приходится сталкиваться с системами, предназначенными для многоразового использования при решении однотипных задач. Возникающие при этом процессы получили название процессов обслуживания, а системы – систем массового обслуживания (СМО). Примерами таких систем являются телефонные системы, ремонтные мастерские, вычислительные комплексы, билетные кассы, магазины, парикмахерские.
Под системой массового обслуживания (СМО) понимают динамическую систему, предназначенную для эффективного обслуживания потока заявок (требований на обслуживание) при ограничениях на ресурсы системы. Совокупность взаимосвязанных СМО называется сетью массового обслуживания (стохастической сетью).
Модели СМО удобны для описания отдельных подсистем современных систем, в том числе и вычислительных, таких как подсистема - процессор - основная память, канал ввода-вывода и т. д. Система в целом представляет собой совокупность взаимосвязанных подсистем, взаимодействие которых носит вероятностный характер. Заявка на решение некоторой задачи, поступающая в систему, проходит последовательность этапов счета, обращения. После выполнения некоторой последовательности таких этапов, заявка считается обслуженной и покидает систему. Таким образом, систему в целом можно представлять совокупностью СМО, каждая из которых отображает процесс функционирования отдельного устройства или группы однотипных устройств, входящих в состав системы. Этим обусловлена актуальность темы реферата.
Теория массового обслуживания – область прикладной математики, занимающаяся анализом процессов в системах производства, обслуживания, управления, в которых однородные события повторяются многократно. Возникающие при этом процессы получили название процессов обслуживания, а системы – систем массового обслуживания (СМО). Примерами таких систем являются телефонные системы, ремонтные мастерские, вычислительные комплексы, билетные кассы, магазины, парикмахерские.
Предметом теории массового обслуживания является установление зависимостей между характером потока заявок, числом каналов обслуживания, производительностью отдельного канала и эффективным обслуживанием с целью нахождения наилучших путей управления этими процессами.
Задача теории массового обслуживания – установить зависимость результирующих показателей работы системы массового обслуживания (вероятности того, что заявка будет обслужена; математического ожидания числа обслуженных заявок и т.д.) от входных показателей (количества каналов в системе, параметров входящего потока заявок и т.д.). Результирующими показателями или интересующими характеристиками СМО являются – показатели эффективности СМО, которые описывают способна ли данная система справляться с потоком заявок.
Задачи теории массового обслуживания носят оптимизационный характер и в конечном итоге включают экономический аспект по определению такого варианта системы, при котором будет обеспечен минимум суммарных затрат от ожидания обслуживания, потерь времени и ресурсов на обслуживание и простоев каналов обслуживания. [1]
1.2. Система массового обслуживания.
Каждая СМО (рис.1) включает в свою структуру некоторое число обслуживающих устройств, называемых каналами обслуживания (к их числу можно отнести лиц, выполняющих те или иные операции, - кассиров, операторов, менеджеров и т.п.), обслуживающих некоторый поток заявок (требований), поступающих на ее вход в случайные моменты времени. Обслуживание заявок происходит за неизвестное, обычно случайное время и зависит от множества самых разнообразных факторов. После обслуживания заявки канал освобождается и готов к приему следующей заявки. Случайный характер потока заявок и времени их обслуживания приводит к неравномерности загрузки СМО – перегрузке с образованием очередей заявок или недогрузке – с простаиванием каналов. [2]
Таким образом, в СМО имеются: входящий поток заявок, дисциплина очереди, поток необслуженных (покинувших очередь) заявок, каналы обслуживания с механизмом обслуживания и выходящий поток обслуженных заявок.
Рис.1. Структура СМО.
Для облегчения процесса моделирования используют классификацию СМО по различным признакам, для которых пригодны определенные группы методов и моделей теории массового обслуживания, упрощающие подбор адекватных математических моделей к решению задач обслуживания в коммерческой деятельности.(см. рис.2)
Рис. 2 Классификация СМО
Перечень характеристик систем массового обслуживания можно представить следующим образом:
Процесс работы СМО представляет собой случайный процесс.
Под случайным процессом понимается процесс изменения состояния некоторой системы с течение времени заранее неизвестным, случайным образом.
Процесс называется процессом с дискретными состояниями, если его возможные состояния S1, S2, S3… можно заранее перечислить, а переход системы из состояния в состояние происходит мгновенно (скачком). Процесс называется процессом с непрерывным временем, если моменты возможных переходов системы из состояния в состояние не фиксированы заранее, а случайны.
Процесс работы СМО представляет собой случайный процесс c дискретными состояниями и непрерывным временем. Это означает, что состояние СМО меняется скачком в случайные моменты появления каких-то событий (например, прихода новой заявки, окончания обслуживания и т.п.).
Математический анализ работы СМО существенно упрощается, если процесс этой работы — марковский. Случайный процесс называется марковским или случайным процессом без последствия, если для любого момента времени t0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t0 и не зависят от того, когда и как система пришла в это состояние.
Например, показание S счетчика в такси в какой-либо момент времени t зависят только от показаний S0 счетчика в начальный момент времени t0 и от пути, пройденного такси после этого момента, что является случайной величиной, и не зависит от того, как изменялись показания счетчика до момента t0. [3]
Марковские процессы важны, так как более просты для изучения. В ряде случаев предысторией рассматриваемых процессов можно пренебречь и приближенно считать их марковскими.
Например, процесс игры в шахматы; система S — группа шахматных фигур. Состояние системы характеризуется числом фигур противника, сохранившихся на доске в момент t0. Вероятность того, что в момент t > t0 материальный перевес будет на стороне одного из противников, зависят в первую очередь от того, в каком состоянии находится система в данный момент t0, а не того, когда и в какой последовательности исчезли фигуры с доски до момента t0.
При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой — так называемым графом состоянии. Обычно состояния системы изображаются прямоугольниками (кружками), а возможные переходы из состояния в состояние — стрелками (ориентированными дугами), соединяющими состояния.
Для примера построим граф состояний технической системы S, состоящей из двух узлов, каждый из которых в случайный момент времени может выйти из строя, после чего мгновенно начинается ремонт узла, продолжающийся заранее неизвестное случайное время. [3]
Возможные состояния системы:
S0 — оба узла исправны;
S1 — первый узел ремонтируется, второй исправен;
S2 — второй узел ремонтируется, первый исправен;
S3 — оба узла ремонтируются.
Граф системы приведен на рис.3.
Рис.3. Граф состояний системы из двух узлов
Стрелка, направленная, например, из S0 в S1 означает переход системы в момент отказа первого узла, из S1 в S0 — переход в момент окончания ремонта этого узла.
На графе отсутствуют стрелки из S0, в S3 и из S1 в S2. Это объясняется тем, что выходы узлов из строя предполагаются независимыми друг от друга и, например, вероятностью одновременного выхода из строя двух узлов (переход из S0 в S3) или одновременного окончания ремонтов двух узлов (переход из S3 в S0) можно пренебречь.
Для математического описания марковского случайного процесса с дискретными состояниями и непрерывным временем, протекающего в СМО, одним из важных понятий теории вероятностей является понятие потока событий. [2]
Под потоком событий понимается последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени (например, поток вызовов на телефонной станции, поток отказов ЭВМ, поток покупателей и т.п.).
Поток характеризуется интенсивностью λ — частотой появления событий или средним числом событий, поступающих в СМО в единицу времени.
Поток событий называется регулярным, если события следуют одно за другим через определенные равные промежутки времени. Например, поток изделий на конвейере сборочного цеха (с постоянной скоростью движения) является регулярным.
Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени. В частности, интенсивность стационарного потока есть величина постоянная: λ(t)=λ. Например, поток автомобилей на городском проспекте не является стационарным в течение суток, но этот поток можно считать стационарным в течение суток, скажем, в часы пик.
Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени t1 и t 2— число событий, попадающих на один из них, не зависит от числа событий, попадающих на другие. Например, поток пассажиров, входящих в метро, практически не имеет последействия. А, скажем, поток покупателей, отходящих с покупками от прилавка, уже имеет последействие (хотя бы потому, что интервал времени между отдельными покупателями не может быть меньше, чем минимальное время обслуживания каждого из них).
Поток событий называется ординарным, если события в нем проявляются поодиночке, а не группами. Например, поток поездов, подходящих к станции ординарен, а поток вагонов нет. Если поток ординарен, то вероятность попадания на малый промежуток времени ∆t двух или более событий можно пренебречь. [2]
Поток событий называется простейшим (или стационарным пуассоновским), если он одновременно стационарен, ординарен и не имеет последействия. Простейшие потоки возникают при наложении достаточного большого числа независимых, стационарных и ординарных потоков. Регулярный поток не является простейшим, так как в равные отрезки времени происходит равное число событий, следовательно, в таком потоке есть последействие.
Выделим на оси времени Ot промежуток t, рис.4, и рассмотрим случайную величину m – число событий, которое происходит за этот промежуток.
Рис. 4 Ось времени случайного процесса
Для простейшего потока событий вероятность того, что в течение промежутка времени t произойдет ровно m событий, находится по формуле:
myunivercity.ru
Реферат на тему:
Теория массового обслуживания (теория очередей) — раздел теории вероятностей, целью исследований которого является рациональный выбор структуры системы обслуживания и процесса обслуживания на основе изучения потоков требований на обслуживание, поступающих в систему и выходящие из неё, длительности ожидания и длины очередей [1]. В теории массового обслуживания используются методы теории вероятностей и математической статистики.
Теорию потока однородных событий, которая легла в основу теории массового обслуживания, разработал советский математик А. Я. Хинчин.[2]
Первые задачи ТМО (Теории Массового Обслуживания) были рассмотрены сотрудником Копенгагенской телефонной компании, ученым Агнером Эрлангом, в период между 1908 и 1922 годами. Стояла задача упорядочить работу телефонной станции и заранее рассчитать качество обслуживания потребителей в зависимости от числа используемых устройств.
Имеется телефонный узел (обслуживающий прибор), на котором телефонистки время от времени соединяют отдельные номера телефонов друг с другом. Системы массового обслуживания (СМО) могут быть двух видов: с ожиданием и без ожидания (то есть с потерями). В первом случае вызов (требование, заявка), пришедший на станцию в момент, когда занята нужная линия, остается ждать момента соединения. Во втором случае он «покидает систему» и не требует забот СМО.
Поток заявок однороден, если:
Поток без последействия, если число событий любого интервала времени (t, t + x) не зависит от числа событий на любом другом непересекающемся с нашим (t, t + x) интервале времени.
Поток заявок стационарен, если вероятность появления n событий на интервале времени (t, t + x) не зависит от времени t, а зависит только от длины этого участка.
Однородный стационарный поток без последействий является простейшим, потоком Пуассона.
Число n событий такого потока, выпадающих на интервал x, распределено по Закону Пуассона:
Пуассоновский поток заявок удобен при решении задач ТМО. Строго говоря простейшие потоки редки на практике, однако многие моделируемые потоки допустимо рассматривать как простейшие.
Мгновенная плотность (интенсивность) потока равна пределу отношения среднего числа событий, приходящихся на элементарный интервал времени (t, t + x) к длине интервала (x), когда последний стремится к нулю.
или, для простейшего потока,
где M(x) равно математическому ожиданию числа событий на интервале x.
Среднее число заявок в системе равно произведению интенсивности входного потока на среднее время пребывания заявки в системе.
wreferat.baza-referat.ru
