Теория массового обслуживания (стр. 1 )

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ВОЗДУШНОГО ТРАНСПОРТА

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ

ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ГРАЖДАНСКОЙ АВИАЦИИ»

Кафедра прикладной математики

ТЕОРИЯ МАССОВОГО ОБСЛУЖИВАНИЯ

Тексты лекций

Москва-2007

ББК 517.8

М 77

Печатается по решению редакционно-издательского совета Московского государственного технического университета ГА

Рецензенты: д-р физ.-мат. наук, доц. Г. Калмыков;

канд. тех. наук, с. н.с. А. Скрынников

М 77 Теория массового обслуживания: Тексты лекций. – М.: МГТУ ГА, 2007. – 64 с. 1 табл., 34 ил., лит. 6 наим.

ISBN -613-6

Данные тексты лекций издаются в соответствии с рабочей программой учебной дисциплины «Теория массового обслуживания» по Учебному плану специальности 230401 для студентов V курса дневного обучения.

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

Рассмотрены и одобрены на заседаниях кафедры 19.04.07г. и методического совета 19.04.07г.

М

-039

Ц33(03)-07 Св. план 2007 г.

поз.39

МОНСИК Владислав Борисович

ТЕОРИЯ МАССОВОГО ОБСЛУЖИВАНИЯ

Тексты лекций

Редактор

Подписано в печать 08.06.07 г.

Печать офсетная Формат 60х84/16 уч.-изд. л.

усл. печ. л. Заказ № 000/ Тираж 250 экз.

 

Московский государственный технический университет ГА

125993 Москва, Кронштадтский бульвар, д. 20

Редакционно-издательский отдел

125493 Москва, ул. Пулковская, д.6а

ISBN 1-613-6

© Московский государственный

технический университет ГА, 2007

ПРЕДИСЛОВИЕ

Первые задачи теории массового обслуживания (ТМО) были рассмотрены сотрудником Копенгагенской телефонной компании датским ученым (1878 – 1929) в период между 1908 и 1922 годами. Эти задачи были стимулированы стремлением упорядочить работу телефонной сети и разработать методы, позволяющие заранее оценивать качество обслуживания потребителей в зависимости от числа используемых устройств.

Уже в ту пору Эрланг обратил внимание на тот факт, что системы массового обслуживания (СМО) могут быть разделены на системы с ожиданием и системы с потерями (отказами). В первом случае вызов, пришедший на станцию, когда нужная линия уже занята, остается ждать соединения и дальнейшего разговора. Во втором случае вызов, заставший систему занятой, получает отказ в обслуживании и покидает систему. Классификация, использованная Эрлангом, сохраняет свое значение и в настоящее время, хотя следует отметить, что с тех пор появились и другие разновидности СМО.

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

С тех пор много воды утекло, а ТМО охватила большое число практических задач, связанных с ее успешным применением в различных областях техники и народного хозяйства.

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

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

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

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

Глава 1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ

МАССОВОГО ОБСЛУЖИВАНИЯ

Теория массового обслуживания (ТМО) является в некотором смысле частью теории вероятностей и использует её математический аппарат [1].

В последние десятилетия ТМО стала самостоятельной наукой, поскольку решаемые с её помощью практические задачи имеют важное значение в народном хозяйстве.

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

Общим моментом для всех этих задач является необходимость количественного анализа процесса “обслуживания” различных “заявок”: самолетов, требующих посадки, обслуживания, ремонта; абонентов телефонных и компьютерных систем и т. д. Заявки поступают на обслуживание в случайные моменты времени, образуя так называемый “поток заявок”. В ТМО принимается допущение о том, что все потоки заявок, поступающие в системы массового обслуживания (СМО), являются пуассоновскими, следовательно, процесс функционирования СМО представляет собой марковский случайный процесс с дискретными состояниями и непрерывным временем. Поэтому СМО рассматриваются как пуассоновские системы массового обслуживания.

Пуассоновским потоком событий называется поток, обладающий двумя свойствами – ординарностью и отсутствием последействия [1].

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

. (1.1)

Рис. 1.1

Здесь – случайное число событий, попавшее на участок , примыкающий к моменту .

Так как для любого интервала справедливо выражение

, (1.2)

как сумма вероятностей несовместных событий, образующих полную группу, то для ординарного потока событий имеют место следующие соотношения:

, (1.3)

а , (1.4)

где – величина, порядок малости которой выше, чем

. (1.5)

Примерами ординарных потоков событий являются:

–  поток заявок на телефонный узел;

–  поток самолетов, производящих посадку на аэродроме;

–  поток самолетов, требующих ремонта, поступающих в ремонтный орган и т. п.

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

Среднее число событий (математическое ожидание) на интервале времени в ординарном потоке событий, очевидно, равно

. (1.6)

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

. (1.7)

Предел выражения (1.7), если он существует, при называется интенсивностью (плотностью) ординарного потока событий и обозначается и равен:

. (1.8)

Интенсивность имеет размерность, обратную размеренности времени .

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

. (1.9)

Поток событий называется потоком без последействия, если для любых двух неперекрывающихся участков и (рис. 1.2) число событий , попавших на участок , следующий за участком , не зависит от числа событий , попавших на предшествующий ему участок ,

Рис. 1.2

. (1.10)

Из теории вероятностей [1] известно, что число событий в пуассоновском потоке, попадающих на любой интервал (рис. 1.2), распределено по закону Пуассона [1]:

, (1.11)

где – среднее число событий, поступающих на интервал . Поэтому такой поток событий и называется пуассоновским потоком.

Среднее число событий, поступающих в единицу времени, для любого ординарного потока равно интенсивности потока (1.8). Следовательно, среднее число событий, поступающих на интервал , будет равно

. (1.12)

Если пуассоновский поток является стационарным (1.9), то величина не будет зависеть от

. (1.13)

В этом случае вероятность (1.11) того, что на произвольно выбранный участок времени продолжительностью поступит ровно событий, определяется по формуле

. (1.14)

Стационарный пуассоновский поток событий называется простейшим потоком. Так он назван потому, что применение простейших потоков при анализе различных СМО приводит к наиболее простым решениям.

В простейшем потоке событий случайный интервал времени между двумя соседними событиями распределен по показательному закону [1] с параметром. Действительно, вероятность того, что на участке времени , следующим за одним из событий простейшего потока (рис. 1.3), не появится ни одного события, равна (1.14)

.

Рис. 1.3

С другой стороны, эта вероятность есть вероятность того, что случайная величина , связанная с появлением очередного события после появления события в момент (рис. 1.3), будет больше

.

Отсюда следует, что функция распределения случайной величины – расстояния между соседними событиями в простейшем потоке событий – равна:

. (1.15)

Дифференцируя (1.15) по , получим известную плотность вероятности показательного распределения

, (1.16)

в то время как формула (1.15) определяет функцию распределения показательного распределения. Параметр показательного распределения связан с математическим ожиданием случайной величины соотношением

, (1.17)

из которого следует

. (1.18)

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

- канал телефонной связи на АТС;

- линия ремонта агрегатов самолетов и двигателей;

- группа технического обслуживания и подготовки воздушного судна (ВС) к полету;

- группа регламентных работ;

- авиадиспетчер, осуществляющий с помощью технических средств (обзорная РЛС, экран локатора, компьютер) посадку воздушного судна на ВПП аэродрома и т. п.

Число каналов обслуживания – один из основных параметров любой СМО.

Качество процесса функционирования канала обслуживания характеризуется временем обслуживания одной заявки, которое является в общем случае случайным. Так как СМО рассматривается как пуассоновская система, то время обслуживания одной заявки должно быть распределено по показательному закону с параметром , который равен

. (1.19)

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

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

Системы массового обслуживания делятся на “разомкнутые” и “замкнутые”.

СМО называется разомкнутой, если источник заявок не входит в состав системы, например, АТС, на которую поступают вызовы для соединения с абонентом, счетчик Гейгера, регистрирующий поток космических излучений.

СМО называется замкнутой, если источник заявок входит в состав системы.

Всевозможные системы массового обслуживания делятся на два основных класса:

1.Системы с отказами, в которых заявка, поступившая в СМО в тот момент, когда все каналы заняты обслуживанием, получает отказ и немедленно покидает систему. Например, одноканальный телефон, где заявка, заставшая телефонную линию занятой, получает отбой.

2. Системы с ожиданием (очередью), в которых заявка, поступившая в СМО в тот момент, когда все каналы заняты обслуживанием, становится в очередь и ждет, пока не освободится один из каналов обслуживания. Обслуживание заявок в таких системах может быть “упорядоченным” – заявки обслуживаются в том порядке, в каком они встали в очередь; “неупорядоченным” – заявки обслуживаются случайным образом; “с приоритетом”– некоторые заявки имеют преимущество перед другими и обслуживаются вне очереди.

СМО с ожиданием делятся на системы с неограниченным ожиданием (системы “чистого” типа) и системы с ограниченным ожиданием (системы “смешанного” типа). В чистой СМО с ожиданием число мест в очереди и время ожидания неограничено – каждая заявка рано или поздно будет обслужена. В системе с ожиданием смешанного типа возможны как отказы, так и ожидание заявки в очереди. Отказы в обслуживании могут быть связаны или с ограничением числа мест в очереди, или с ограничением времени ожидания заявки в очереди или времени её пребывания в системе.

ГЛАВА 2. ВЕРОЯТНОСТНЫЕ ХАРАКТЕРИСТИКИ

СЛУЧАЙНЫХ ПРОЦЕССОВ

2.1. Определение случайного процесса

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

При изучении процессов функционирования авиационных комплексов (АК) и других сложных систем приходится иметь дело с величинами, значения которых в каждом опыте изменяются в зависимости от времени или других аргументов. Например, высота, скорость полета, расход топлива, углы атаки и скольжения – функции времени; давление атмосферы, плотность воздуха – функции высоты полета воздушного судна (ВС) и т. п. В результате измерения непрерывно изменяющейся величины мы получим функцию времени, которая для каждого определенного значения времени имеет одно определенное значение в интервале времени измерения. Многократно повторяя измерение в неизменных условиях, мы будем получать вследствие случайных ошибок измерений и других случайных причин различные (случайные) функции. Таким образом, результат измерения непрерывно изменяющейся величины является такой случайной величиной, которая в данном опыте представляет собой определенную функцию времени, а в различных опытах, воспроизводимых в одинаковых условиях, - различные между собой функции времени, называемые реализациями случайной функции. Следовательно, реализация случайной функции - это конкретный вид, который принимает случайная функция в результате опыта.

Условимся обозначать случайные функции прописными (большими) буквами латинского алфавита , а их реализации – строчными (малыми) буквами: . Аргумент (множество аргументов) случайной функции в общем случае будем обозначать буквой и писать в скобках за обозначением самой функции: , а её реализации соответственно . Если аргумент случайной функции представляет собой совокупность скалярных переменных, то его следует рассматривать как - мерный вектор.

В технических приложениях, связанных, в частности, с анализом процессов функционирования и эксплуатации АК, рассматривают случайные функции времени и их реализации . Случайные функции времени называются случайными (стохастическими) процессами. Соответственно теория случайных функций одной независимой переменной называется теорией случайных (стохастических) процессов. В дальнейшем изложении мы будем рассматривать, в основном, случайные процессы.

Рассмотрим несколько примеров реализаций случайных процессов:

- параметры полета ВС – высота , скорость , угол пикирования , угол кабрирования , угол крена (рис. 2.1);

- ошибка измерения угловой координаты объекта радиолокатором (рис. 2.2).

а б

в

г

д

Рис. 2.1. Реализации параметров полета летательных аппаратов:

а - высота полета ЛА; б - скорость полета ЛА; в - угол пикирования в установившемся режиме; г - угол кабрирования ЛА в установившемся режиме; д - угол крена ЛА

Рис. 2.2. Ошибка измерения угловой координаты цели бортовой РЛС

 

2.2. Закон распределения и моменты случайного процесса

При фиксированном значении аргумента случайного процесса этот процесс является скалярной случайной величиной. Значение случайного процесса при каждом данном (фиксированном) значении его аргумента называется сечением случайного процесса. Иначе говоря, в каждом сечении случайного процесса мы имеем дело со случайной величиной. Если рассмотреть последовательность значений аргумента случайного процесса , то им соответствует последовательность случайных величин .

Рассмотрим семейство реализаций , случайного процесса (рис. 2.3). Зафиксируем значение аргумента . В сечении получим случайную величину . Полной её вероятностной характеристикой является закон распределения, который называется одномерным законом распределения случайного процесса и зависит от как от параметра.

Рис. 2.3. Семейство реализаций случайного процесса

Одномерный закон распределения случайного процесса может задаваться одномерной плотностью вероятности и является достаточной характеристикой для вычисления начальных и центральных моментов случайных величин – сечений случайного процесса

, (2.1)

(2.2)

В частном случае, по формулам (2.1), (2.2) вычисляются математическое ожидание, второй начальный момент, дисперсия случайного процесса

, (2.3)

, (2.4)

(2.5)

или

. (2.6)

Поясним смысл понятий математического ожидания и дисперсии случайного процесса более подробно.

Математическим ожиданием случайного процесса называется неслучайная функция аргумента , значение которой при каждом данном (фиксированном) значении аргумента (сечении) равно математическому ожиданию соответствующей случайной величины

. (2.7)

Если для сечений случайного процесса определить их математические ожидания , то они представляют собой средние значения случайных величин (сечений) . Соединив эти средние значения (точки) между собой, получим среднюю реализацию (рис. 2.3), около которой группируются и относительно которой колеблются все возможные реализации случайного процесса .

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

Дисперсией случайного процесса называется такая неслучайная функция , значение которой при каждом данном (фиксированном) значении аргумента (сечении) равно дисперсии соответствующей случайной величины

. (2.8)

Разность называется центрированным случайным процессом. С учетом этого

. (2.9)

Мерой линейного рассеивания значений случайного процесса в сечениях является среднее квадратическое отклонение (с. к. о.)

. (2.10)

В предположении о нормальном распределении случайной величины в сечении можно, вспомнив правило трех средних квадратических отклонений

, (2.11)

построить границы коридора (рис. 2.4)

, (2.12)

внутри которого будут находиться практически все реализации случайного процесса .

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

Рис. 2.4. Средняя и граничные реализации случайного процесса

Покажем это на примере (рис. 2.5, 2.6). Возьмем два случайных процесса и , заданных семейством своих реализаций, имеющих одинаковые математические ожидания и дисперсии. Структура случайных процессов, как видно из рис. 2.5 и 2.6, может быть различна: реализации изменяются достаточно плавно, а - резко. Очевидно, что для описания структуры случайного процесса необходимо ввести характеристику, отражающую степень зависимости между сечениями случайных процессов.