Размещено на http://www.allbest.ru/

Пермский национально исследовательский политехнический университет

Аэрокосмический факультет

Кафедра "Инновационные технологии в машиностроении"

Направление 151000 "Конструкторско-технологическое обеспечение машиностроительных производств"

Профиль магистратуры: "Технология обеспечения качества изделий компьютеризированного производства"

Аналитический обзор на тему:

"Моделирование работы систем массового обслуживания с ожиданием и очередями с ограниченной длиной"

Пермь, 2016

Содержание

• 1. Теория массового обслуживания. Основные положения
• 1.1 Предмет и задачи теории массового обслуживания
• 1.2 Характеристики СМО
• 2. Параметры СМО
• 2.1 Общие положения
• 2.2 Процесс поступления заявок
• 3. Модели систем массового обслуживания с ограниченной очередью
• 3.1 Многоканальная СМО с ограниченной длиной очереди
• 3.2 Одноканальная СМО с ожиданием и ограниченной очередью
• Заключение
• Список используемой литературы
• 1. Теория массового обслуживания. Основные положения

1.1 Предмет и задачи теории массового обслуживания

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

На первичное развитие теории массового обслуживания оказали особое влияние работы датского ученого А.К. Эрланга (1878-1929).

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

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

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

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

1.2 Характеристики СМО

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

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

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

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

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

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

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

Перечень характеристик систем массового обслуживания можно представить следующим образом:

· среднее время обслуживания;

· среднее время ожидания в очереди;

· среднее время пребывания в СМО;

· средняя длина очереди;

· среднее число заявок в СМО;

· количество каналов обслуживания;

· интенсивность входного потока заявок;

· интенсивность обслуживания;

· интенсивность нагрузки;

· коэффициент нагрузки;

· относительная пропускная способность;

· абсолютная пропускная способность;

· доля времени простоя СМО;

· доля обслуженных заявок;

· доля потерянных заявок;

· среднее число занятых каналов;

· среднее число свободных каналов;

· коэффициент загрузки каналов;

· среднее время простоя каналов.

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

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

· ординарность потока означает, что невозможно одновременное поступление двух и более заявок;

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

2. Параметры СМО

2.1 Общие положения

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

Рис. 1 Вид СМО

Процесс функционирования СМО включает в общем случае следующие этапы:

приход (поступление) требования;

ожидание (при необходимости) в очереди;

обслуживание в приборе;

уход требования из системы.

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

Для формализации любой СМО необходимо описать:

процесс поступления заявок в систему;

процесс обслуживания заявок в системе;

дисциплину обслуживания.

2.2 Процесс поступления заявок

Прежде чем описать процесс поступления заявок (Рис. 2) приведем необходимые обозначения и определения.

Пусть t₁, t₂, t₃, t_k, - моменты поступления в систему 1-го, 2-го, 3-го, ... k-го, требований:

Рис. 2. Процесс поступления заявок.

Обозначим через

t_k = t_{k -} t_k-1

промежуток времени между моментами прихода (k-1)-го и k-го требований, который называется интервалом прихода k-го требования (k = 1, 2, 3, ...).

Если интервалы прихода всех заявок являются постоянными, т.е.

- const, то такой поток называется детерминированным или регулярным. Однако, как правило, интервалы прихода k являются случайными величинами, и соответствующий поток заявок называется стохастическим или случайным. Очевидно, что регулярный поток является частным случаем случайного потока.

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

(1)

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

(2)

Другими словами, для рекуррентного потока интервалы прихода всех заявок распределены по одному и тому же закону.

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

Величина, обратная интенсивности (а=1/), определяет среднее значение интервалов прихода или средний интервал поступления заявок.

Если в каждый момент времени t₁, t₂, t₃, ... поступает только одна заявка, то такой поток называется ординарным, в противном случае - групповым (могут приходить одновременно две или более заявок). В дальнейшем рассматриваются только рекуррентные, стационарные и ординарные потоки.

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

При анализе СМО важное место занимает так называемый простейший поток. Простейшим называется поток, в котором интервалы поступления заявок распределены по экспоненциальному закону:

 (3)

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

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

Простейший поток обладает следующими свойствами.

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

2. Если из простейшего потока интенсивности исключить каждую заявку с вероятностью р (а с вероятностью 1-р оставить), то как поток исключенных, так и поток оставшихся заявок, окажутся простейшими с интенсивностями р и (1-р) соответственно (Рис. 3):

Рис. 3 Интенсивность потока

3. Число заявок N(t) простейшего потока, поступающих в СМО за время t, будучи случайной целочисленной дискретной величиной, распределено по закону Пуассона:

(4)

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

Таким образом, для описания рекуррентного, стационарного и ординарного процесса поступления заявок необходимо в общем случае задать функцию распределения интервалов их поступления. Однако не всегда бывает известной функция распределения. В таких случаях вместо неизвестной функции распределения для описания входного потока задаются интенсивность (или средний интервал а=1/) и коэффициент вариации (КВ) _а интервалов поступления, что оказывается достаточным для многих теоретических и практических приложений. Более того, в большинстве аналитических исследований в качестве входного потока заявок рассматривается простейший поток, ибо только в этом случае удается получать сколько-нибудь содержательные результаты анализа СМО. А для описания простейшего потока достаточно задать интенсивность , т.к. при этом КВ _а1 в силу экспоненциального характера распределения интервалов поступления заявок. Выделение используемых при анализе СМО потоков схематически представлено на рис. 4.

Рис. 4 Виды потоков.

3. Модели систем массового обслуживания с ограниченной очередью

3.1 Многоканальная СМО с ограниченной длиной очереди

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

- все каналы свободны;

- занят только один канал (любой);

- заняты только два канала (любых);

- заняты все каналов.

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

3.2 Одноканальная СМО с ожиданием и ограниченной очередью

Рассмотрим теперь одноканальную СМО с ожиданием.

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

Рассмотрим систему с ограниченной очередью. Предположим, что независимо оттого, сколько требований поступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более N-требований (заявок), из которых одна обслуживается, а (N-1) ожидают, Клиенты, не попавшие в ожидание, вынуждены обслуживаться в другом месте и такие заявки теряются. Наконец, источник, порождающий заявки на обслуживание, имеет неограниченную (бесконечно большую) емкость.

Обозначим - вероятность того, что в системе находится n заявок. Эта величина вычисляется по формуле:

(5)

Здесь

- приведенная интенсивность потока. Тогда вероятность того, что канал обслуживания свободен и в системе нет ни одного клиента, равна:

.

С учетом этого можно обозначить

 (6)

Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N-1):

вероятность отказа в обслуживании заявки:

P_отк=Р_N= (7)

относительная пропускная способность системы:

(8)

абсолютная пропускная способность:

А=q•л;

среднее число находящихся в системе заявок:

среднее время пребывания заявки в системе:

;

средняя продолжительность пребывания клиента (заявки) в очереди:

W_q=W_s- 1/м;

среднее число заявок (клиентов) в очереди (длина очереди):

L_q=л(1-P_N)W_q.

Рассмотрим пример одноканальной СМО с ожиданием.

Пример. Специализированный пост диагностики представляет собой одноканальную СМО. Число стоянок для автомобилей, ожидающих проведения диагностики, ограниченно и равно 3, то есть (N-1)=3. Если все стоянки заняты, т. е. в очереди уже находится три автомобиля, то очередной автомобиль, прибывший на диагностику, в очередь на обслуживание не становится. Поток автомобилей, прибывающих на диагностику имеет интенсивность л=0,85 (автомобиля в час). Время диагностики автомобиля распределено по показательному закону и в среднем равно =1,05 час.

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

Решение

Интенсивность потока обслуживаний автомобилей:

Приведенная интенсивность потока автомобилей определяется как отношение интенсивностей л и м, т.е.

Вычислим вероятности нахождения п заявок в системе:

P₁=r•P₀=0,893•0,248=0,221;

P₂=r²•P₀=0,893²•0,248=0,198;

P₃=r³•P₀=0,893³•0,248=0,177;

P₄=r⁴•P₀=0,893⁴•0,248=0,158.

Вероятность отказа в обслуживании автомобиля:

P_отк=Р ₄=r⁴•P₀?0,158.

Относительная пропускная способность поста диагностики:

q=1-P_отк=1-0,158=0,842.

Абсолютная пропускная способность поста диагностики

А=л•q=0,85•0,842=0,716 (автомобиля в час).

Среднее число автомобилей, находящихся на обслуживании и в очереди (т.е. в системе массового обслуживания):

Среднее время пребывания автомобиля в системе:

часа.

Средняя продолжительность пребывания заявки в очереди на обслуживание:

W_q=W_s-1/м=2,473-1/0,952=1,423 часа.

Среднее число заявок в очереди (длина очереди):

L_q=л•(1-P_N)•W_q=0,85•(1-0,158)•1,423=1,02.

Работу рассмотренного поста диагностики можно считать удовлетворительной, так как пост диагностики не обнаруживает автомобили в среднем в 15,8% случаев (Р_отк=0,158).

Заключение

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

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

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

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

1. Количество заявок в системе (которая рассматривается как СМО) должно быть достаточно велико (массово).

2. Все заявки, поступающие на вход СМО, должны быть однотипными.

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

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

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

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

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

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

Список используемой литературы

1. Электронный ресурс: http://www.studmed.ru/docs/document12590/content дата обращения (08.03.2016г.)

2. Моделирование: учебное пособие для вузов /В.С. Зарубин. - Москва: Академия, 2013. - 336 С.

Размещено на Allbest.ru

...