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

Министерство науки и образования Республики Казахстан

Факультет информационных технологий

Кафедра информационных систем

 

 

 

 

Индивидуальное домашнее задание

 На тему: « Модели массового обслуживания»

 

 

 

Выполнила:	Дациева Р.М., студентка 4 курса, специальности «Информационные системы -5В070300»
Проверил:	Вардиашвили Н.Н., к.э.н., доцент кафедры ИС.

 

 

 

 

 

Костанай, 2015

Содержание

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

При решении задач оптимизации управления производством, информационными сетями, транспортными системами часто возникает ряд однотипных задач:

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

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

 

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

Элементами СМО являются:

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

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

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

Работа СМО — это выполнение поступающего на нее потока заявок (потока требований), которые поступают одна за другой в случайные моменты времени. Канал обслуживает заявку какое-то время (тоже в общем случае случайное) и освобождается.

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

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

Для  классификации  СМО  важное  значение  имеет   дисциплина   обслуживания

(правила  обслуживания) заявок: первая   пришла — первая обслужена, последняя пришла

— первая обслужена, обслуживание с приоритетом и т.п.

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

Введем следующие понятия:

n — число каналов СМО;

pi — вероятность того, что в СМО занято обслуживанием ровно i каналов, например,

p0  — все каналы свободны,

p1 — занят один канал и т.д.,

pn — занято n каналов.

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

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

 

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

Если tk-tk-1=const, то такой поток будем называть регулярным. Для СМО более типичен случайный поток.

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

здесь   - интенсивность потока. 
Название потока - пуассоновский - происходит от того, что для этого потока вероятность   появления   заявок за интервал   определяется законом Пуассона:

Именно такой поток предполагают проектировщики при разработке СМО. Вызвано это тремя причинами.

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

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

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

Простейший (или стационарный пуассоновский поток) обладает следующими свойствами:

1. Стационарность — когда вероятность попадания того или иного числа событий на участок времени τ не зависит от того, где расположен этот участок, а зависит только от его длины.
2. Поток является потоком без последствия, если для двух неперекрывающихся участков времени число событий, попадающих на один из них, не зависит от числа событий другого участка.
3. Поток является ординарным, если вероятность попадания двух и более событий на бесконечно малый интервал Δt бесконечно мала.

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

Второе свойство — заявки поступают независимо друг от друга.

Третье свойство — заявки приходят поодиночке, а не парами, тройками и т.д.

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

Рассмотрим характеристики простейшего потока. Вероятность того, что за время  τ

произойдет ровно m событий, равна (распределение по закону Пуассона)

где λ – интенсивность или плотность потока (среднее число событий за  единицу времени).

Это есть показательный закон распределения с параметром λ. Математическое ожидание M[T] имеет вид:

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

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

одной заявки  

- среднее время обслуживания заявки канал

 2 СМО с отказами. Формулы Эрланга.

 

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

Величина  ρ=λ∕μ  называется  приведенной  интенсивностью  потока  заявок или интенсивностью нагрузки канала. Дадим    конечные    формулы  для  предельных вероятностей в    такой системе

(формулы Эрланга):

1. Вероятность того, что в системе находится 0 требований:

 

 

 

 

1. Вероятность того, что в системе находится k требований:

 

 

 

2. Вероятность отказа СМО

 

 

 

3. Относительная пропускная способность

 

 

 

4. Абсолютная пропускная способность

 

 

 

 

 

 

 

5. Среднее число занятых каналов можно определить как математическое ожидание дискретной случайной величины, принимающей значения 0,1,2,…, n с вероятностями p0, p1, …pn,, т.е.

 

 

Подставляя pi из (1), получим:

 

6.  Коэффициент занятости канала

 

 

 

3 СМО с ожиданием.

 

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

Рассмотрим n-канальную СМО с неограниченной очередью. При ρ∕n<1 предельные вероятности существуют. Если ρ∕n≥1, очередь растет до бесконечности.

Формулы для вычисления вероятностей состояний имеют вид

1. Вероятность того, что в системе находится 0 требований:

 

 

2. Вероятность того, что заявка окажется в очереди

 

 

3. Среднее число заявок в очереди Lоч

 

 

 

 

 

4. Среднее число заявок, находящихся в обслуживании

  

 

5. Среднее число заявок в системе

 

6.Среднее время пребывания заявок  в системе (очереди)

=

 

 

 

7.Среднее  время пребывания заявок в  системе (очереди)

 

 

СМО с бесконечным числом приборов.

Пусть входящий поток требований простейший с интенсивностью l . Обслуживающие   приборы   имеют   одинаковую пропускную способность m и время

обслуживания распределено по показательному закону.

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

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

Выходные параметры:

 

 

1. Вероятность того, что в системе находится k требований

 

 

2. Количество обслуживающих приборов n определяется как наиболее вероятное состояние системы.

 

 

 

 

 

 

 

4 Примеры решения задач

 

Пример    1. (СМО с отказами). Заявки    по    телефону    в    ремонтную    мастерскую    поступают с интенсивностью λ, равной 90 заявок в час, а средняя продолжительность разговора по телефону T об=2 мин. Рассматривая данную СМО, как систему с отказами, определить оптимальное число телефонных номеров, если условием оптимальности считать принятие в среднем из каждых 100 заявок не менее 90.