что такое теория массового обслуживания

Три основы теории массового обслуживания

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

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

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

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

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

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

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

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

В качестве характеристик СМО рассматриваются:

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

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

Каждую СМО может характеризовать выражением: ( a / b / c ) : ( d / e / f ), где

a — распределение входного потока заявок;

b — распределение выходного потока заявок;

c – конфигурация обслуживающего механизма;

d – дисциплина очереди;

e – блок ожидания;

f – емкость источника.

Теперь рассмотрим подробнее каждую характеристику.

Входной поток заявок – количество поступивших в систему заявок. Характеризуется интенсивностью входного потока l.

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

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

Таким образом, можно выделить одно- и многоканальные СМО.

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

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

Дисциплина очереди – это правило обслуживания заявок из очереди. К основным типам очереди можно отнести следующие:

Длина очереди может быть

Примером СМО с чистым ожиданием можно считать погрузочно-разгру­зочное депо. В основном же ограничение на длину очереди накладывает размер места для размещения очереди (например, автостоянки или помещения).

Блок ожидания – «вместимость» системы – общее число заявок, находящихся в системе (в очереди и на обслуживании). Таким образом, е=с+d.

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

Количество моделей СМО соответствует числу всевозможных сочетаний этих компонент.

3.2 Входной поток требований.

С каждым отрезком времени [a,a+T ], свяжем случайную величину Х, равную числу требований, поступивших в систему за время Т.

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

Поток называется ординарным, если за очень короткий промежуток времени в систему может поступить не более одного требования. Например, поток в парикмахерскую – ординарный, а в ЗАГС – нет. Но, если в качестве случайной величины Х рассматривать пары заявок, поступающих в ЗАГС, то такой поток будет ординарным (т.е. иногда неординарный поток можно свести к ординарному).

Основная теорема. Если поток – простейший, то с.в. Х_[a.a+T] распределена по закону Пуассона, т.е. .

Следствие 1. Простейший поток также называется пуассоновским.

В ателье поступает в среднем 3 заявки в день. Считая поток простейшим, найти вероятность того, что в течение двух ближайших дней число заявок будет не менее 5.

По условию задачи, l=3, Т=2 дня, входной поток пуассоновский, n ³5. при решении удобно ввести противоположное событие, состоящее в том, что за время Т поступит меньше 5 заявок. Следовательно, по формуле Пуассона, получим
^

3.3 Состояние системы. Матрица и граф переходов.

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

Аналогичная система с отказами может находиться в состояниях E₀ – E_n.

Для СМО с чистым ожиданием существует бесконечное множество состояний. Таким образом, состояниеE_n СМО в момент времени t – это количество n заявок (требований), находящихся в системе в данный момент времени, т.е. n=n(t) – случайная величина, E_n(t) – исходы этой случайной величины, а P_n(t) – вероятность пребывания системы в состоянии E_n.

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

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

Рисунок 3.1 – граф переходов

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

Так как система обязательно перейдет из одного

состояния в другое, то сумма вероятностей в каждой строке всегда равна единице.

3.4 Одноканальные СМО.

3.4.1 Одноканальные СМО с отказами.

Будем рассматривать системы, удовлетворяющие требованиям:

Для такой системы возможно два состояния: Е₀ – система свободна и Е₁ – система занята. Составим матрицу переходов. Возьмем Dt – бесконечно малый промежуток времени. Пусть событие А состоит в том, что в систему за время Dt поступило одно требование. Событие В состоит в том, что за время Dt обслужено одно требование. Событие А_i,k – за время Dt система перейдет из состояния E_i в состояние E_k. Так как l – интенсивность входного потока, то за время Dt в систему в среднем поступает l*Dt требований. То есть, вероятность поступления одного требования Р(А)= l* Dt, а вероятность противоположного событияР(Ā)=1-l*Dt. Р(В)=F(Dt)=P(b — m D t =m Dt – вероятность обслуживания заявки за время Dt. Тогда А₀₀ – заявка не поступит или поступит, но будет обслужена. А₀₀=Ā+А*В. Р₀₀=1—l*Dt. (мы учли, что(Dt) 2 – бесконечно малая величина)

А₀₁ – заявка поступит, но не будет обслужена. А₀₁=А*. Р₀₁=l*Dt.

А₁₁ – заявка не будет обслужена или поступит новая, которая еще не обслужена. А₁₁=+В*А. Р₀₁=1-m*Dt.

Таким образом, получим матрицу переходов:

Вероятность простоя и отказа системы.

Найдем теперь вероятность нахождения системы в состоянии Е₀ в любой момент времени t (т.е. р ₀ ( t ) ). График функции изображен на рисунке 3.2.

Асимптотой графика является прямая .

Очевидно, начиная с некоторого момента t,

1

Окончательно получим, что и , где р₁(t) – вероятность того, что в момент времени t система занята (т.е. находится в состоянии Е₁).

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

Стационарный режим работы и коэффициент загрузки системы.

Если вероятность нахождения системы в состоянии Е_k, т.е. Р_k(t), не зависит от времени t, то говорят, что в СМО установился стационарный режим работы. При этом величина называется коэффициентом загрузки системы (или приведенной плотностью потока заявок). Тогда для вероятностейр₀(t) и р₁(t) получаем следующие формулы: , . Можно также сделать вывод:чем больше коэффициент загрузки системы, тем больше вероятность отказа системы (т.е. вероятность того, что система занята).

На автомойке один блок для обслуживания. Автомобили прибывают по пуассоновскому распределению с интенсивностью 5 авто/час. Среднее время обслуживания одной машины – 10 минут. Найти вероятность того, что подъехавший автомобиль найдет систему занятой, если СМО работает в стационарном режиме.

Решение. По условию задачи, l=5, m =60мин/10мин = 6. Коэффициент загрузки y =5/6. Надо найти вероятность р₁ – вероятность отказа системы. .

3.4.2 Одноканальные СМО с неограниченной длиной очереди.

Будем рассматривать системы, удовлетворяющие требованиям: (Р/Е/1):(d/¥/¥). Система может находиться в одном из состояний E₀, …, E_k, … Анализ показывает, что через некоторое время такая система начинает работать в стационарном режиме, если интенсивность выходного потока превышает интенсивность входного потока (т.е. коэффициент загрузки системы меньше единицы). Учитывая это условие, получим систему уравнений

решая которую найдем, что . Таким образом, при условии, что y средние характеристики (т.е. берем математическое ожидание от рассматриваемых случайных величин, и помним, что y формулы Эрлáнга ) для вероятности нахождения системы в состоянии Е_k в случайный момент времени:

, k=0, 1, …

Функция стоимости.

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

Для поиска оптимального варианта надо найти (и это можно сделать) минимальное значение функции стоимости: С(s) = с_1*l_*p_s+с_2*, график которой представлен на рисунке 3.3:

Поиск минимального значения функции стоимости состоит в том, что мы находим ее значения сначала дляs =1, затем для s =2, потом для s =3, и т.д. до тех пор, пока на каком-то шаге значение функции С(s) не станет больше предыдущего. Это и означает, что функция достигла своего минимума и начала расти. Ответом будет то число каналов обслуживания (значение s), для которого функция стоимости минимальна.

ПРИМЕР.

Сколько линий обслуживания должна содержать СМО с отказами, если l=2треб/час, m =1треб/час, штраф за каждый отказ составляет 7 тыс.руб., стоимость простоя одной линии – 2 тыс.руб. в час?

Предположим, что СМО имеет два канала обслуживания, т.е. s =2. Тогда . Следовательно, С(2) = с₁*l*p₂+с₂*(2-y*(1-р₂))= =7*2*0.4+2*(2-2*0.6)=7.2.

Предположим, что s =3. Тогда , С(3) = с₁*l*p₃+с₂*=5.79.

Предположим, что имеется четыре канала, т.е. s =4. Тогда , , С(4) = с₁*l*p₄+с₂*=5.71.

Предположим, что СМО имеет пять каналов обслуживания, т.е. s =5. Тогда , С(5) =6.7 – больше предыдущего значения. Следовательно, оптимальное число каналов обслуживания – четыре.

3.5.2 Многоканальные СМО с очередью.

Будем рассматривать системы (Р/Е/s):(d/d+s/¥) в предположении, что время обслуживания не зависит от входного потока и все линии работают независимо. Будем говорить, что в системе установилсястационарный режим работы, если среднее число поступающих требований меньше среднего числа требований, обслуженных на всех линиях системы, т.е. l 0) – вероятность ожидания начала обслуживания, .

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

ПРИМЕР.

СМО – станция скорой помощи небольшого микрорайона. l=3 вызова в час, а m = 4 вызова в час для одной бригады. Сколько бригад необходимо иметь на станции, чтобы вероятность ожидания выезда была меньше 0.01?

Решение. Коэффициент загрузки системы y =0.75. Предположим, что в наличие имеется две бригады. Найдем вероятность ожидания начала обслуживания при s =2. , .

Предположим наличие трех бригад, т.е. s =3. По формулам получим, что р₀=8/17, Р(w>0)=0.04>0.01.

Источник

Теория массового обслуживания

Содержание

История

Теорию потока однородных событий, которая легла в основу теории массового обслуживания, разработал советский математик А. Я. Хинчин. [2]

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

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

Поток

Однородный поток

Поток заявок однороден, если:

Поток без последействия

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

Стационарный поток

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

Простейший поток

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

Число событий такого потока, выпадающих на интервал , распределено по Закону Пуассона:

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

Мгновенная плотность

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

или, для простейшего потока,

где равно математическому ожиданию числа событий на интервале .

Формула Литтла

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

Литература

Библиография

См. также

Полезное

Смотреть что такое «Теория массового обслуживания» в других словарях:

теория массового обслуживания — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] теория массового обслуживания Раздел исследования операций, который рассматривает разнообразные процессы в экономике, а также в телефонной связи, здравоохранении и других… … Справочник технического переводчика

Теория массового обслуживания — [theory of waiting lines, queueing theory] раздел исследования операций, который рассматривает разнообразные процессы в экономике, а также в телефонной связи, здравоохранении и других областях как процессы обслуживания, т.е. удовлетворения каких… … Экономико-математический словарь

Теория массового обслуживания — [theory of waiting lines, queueing theory] раздел исследования операций, который рассматривает разнообразные процессы в экономике, а также в телефонной связи, здравоохранении и других областях как процессы обслуживания, т.е. удовлетворения каких… … Экономико-математический словарь

ТЕОРИЯ МАССОВОГО ОБСЛУЖИВАНИЯ — раздел прикладной математики, применяющийся в качестве метода в экономических исследованиях. Эта теория изучает статистические закономерности в массовых операциях, состоящих из большого числа однородных элементарных операций. К ним относятся,… … Большой экономический словарь

ТЕОРИЯ МАССОВОГО ОБСЛУЖИВАНИЯ — раздел теории вероятностей, изучающей потоки требований на обслуживание, поступающие в системы обслуживания и выходящие из них, длительности ожидания и длины очередей и т. п. Целью исследований в Т. м. о. является рациональный выбор структуры… … Энциклопедический словарь по психологии и педагогике

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

МАССОВОГО ОБСЛУЖИВАНИЯ ТЕОРИЯ — теория очередей, раздел теории вероятностей, изучающий математич. модели разного рода реальных массового обслуживания систем. Эти модели представляют собой случайные процессы специального вида, к рые наз. иногда процессами обслуживания. Чаще… … Математическая энциклопедия

МАССОВОГО ОБСЛУЖИВАНИЯ ТЕОРИЯ — раздел математики, изучающий системы, предназначенные для обслуживания массового потока требований случайного характера. Типичный пример такой системы автоматическая телефонная станция, где случайным образом поступают требования вызовы абонентов … Большой Энциклопедический словарь

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

Источник