Процессы массового обслуживания. Основные понятия

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

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

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

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

ЗАМЕЧАНИЕ: Часто в научной и учебной литературе используется предложенный Кендаллом Д.(1953г.) символьный способ кодировки СМОразличной структуры – до 5 и более символов, разделенных косой чертой.

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

Второй разряд. Символ означает, что у длительностей обслуживания заявок также отсутствует память (т.е. они распределены экспоненциально!), D (determine) – детерминированный или регулярный поток, E – эрланговский, HE – гиперэрланговский, GI – входной поток рекуррентный, т.е СВ независимы и одинаково распределены, G – произвольное распределение (не сделано предположений).

На третьей позиции указывается число каналов (приборов) обслуживания . Символ означает, что рассматривается сложная система обслуживания.

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

Пятый разряд касается систем с приоритетами.

ПРИМЕР: СМО – пуассоновский входной поток заявок; общее распределение времени обслуживания; один канал (прибор) обслуживания; есть мест в очереди на обслуживание.

ЗАМЕЧАНИЕ: Вероятностные процессы, возникающие в ТМО, являются, вообще говоря, немарковскими и только в системах эти процессы марковские, поскольку для них характерно отсутствие последействия и будущее развитие процесса зависит от текущих состояний и не зависит от того, как происходило их развитие в прошлом.

Простейший поток: 1) вероятность появления того или иного числа заявок на временнóм интервале зависит лишь от его длительности и не зависит от его расположения на временнóй оси (стационарность входного потока), причём заявки поступают поодиночке (ординарность входного потока) и независимо друг от друга (отсутствие последействия во входном потоке); 2) вероятность реализации отдельного случайного события (появление заявки) на временнóм интервале малой длительности пропорциональна с точностью до бесконечно малой более высокого порядка малости по сравнению с , т.е. , , ; 3) вероятность реализации двух или более случайных событий (появление двух и более заявок) на временном интервале малой длительности есть величина .

ЗАМЕЧАНИЕ. Потоком с ограниченным последействием называется поток, у которого случайные интервалы между соседними по времени события представляют собой независимые СВ.

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

ТЕОРЕМА. Дискретная СВ , принимающая значения и характеризующая при простейшем входном потоке число заявок поступающих в систему обслуживания на временнóм интервале длительность , распределена по закону Пуассона с параметрами .

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

Система уравнений Колмогорова имеет вид:

где - вероятность того, что на временнóм интервале длительности в изучаемую систему обслуживания поступит заявок. Из определения простейшего потока следует, что .

Задача Коши для имеет вид: ,

а для функций : , .

Последовательно решая указанные задачи Коши, получим для случая простейшего входного потока , где - число заявок на временном интервале длительности . Это означает, что СВ распределена по закону Пуассона с параметром .►

СЛЕДСТВИЕ. , .

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

ТЕОРЕМА. Для простейшего входного потока с интенсивностью длительность временнóго интервала между двумя последовательными заявками имеет экспоненциальное распределение с параметром .

◄ Вероятность отсутствия заявок на временнóм интервале длительности . Тогда . Очевидно, что при . То есть – СВ, распределённая по экспоненциальному закону с параметром .►

ЗАМЕЧАНИЕ. ,  среднее время и дисперсия времени между соседними заявками. Тогда в качестве оценки можно брать , т.е. есть среднее число заявок в единицу времени. Помимо этого

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

ЗАДАЧА 2. В ремонтную мастерскую поступает в среднем 12 заказов в час. Считая поток заказов простейшим, определить вероятность того, что: а) за 1 минуту не поступит ни одного заказа;

б) за 10 минут поступит не более трёх заказов.

◄ Поскольку поток заказов простейший, то его интенсивность . Тогда и ►

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

ПРОСТЕЙШАЯ ЗАДАЧА ТМО

Рассматривается техническая система (ТС), которая может находиться всего в двух состояниях: - система исправна (нет отказа), - система неисправна. На ТС, находящуюся в состояния , действует поток отказов с интенсивностью , переводящий ТС в состояние . На ТС, находящуюся в состоянии , действует поток восстановлений с интенсивностью . Оба потока пуассоновские, независимые. Размеченный граф состояний ТС имеет вид:
В начальный момент ТС исправна, т.е. . Требуется составить систему уравнений Колмогорова для вероятностей состояний и решить её:

.

Из условия нормировки найдём: . После подстановки этого результата в первое уравнение получим дифференциальное уравнение с одной неизвестной функцией :

, . (1)

Откуда (2)

В частном случае , уравнение (1) приобретает вид:

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

ЗАМЕЧАНИЕ: Следует обратить внимание на то, что даже в случае этой простейшей системы зависимость интенсивностей и от времени приводит к достаточно громоздким вычислениям вероятностей нахождения ТС в состояниях и (см. формулу(2)).

Рис. 1

ЗАДАЧА 3. Транспортная фирма располагает грузовиками, каждый из которых (независимо от других!) может выйти из строя. Интенсивность простейшего потока отказов автомобилей равна . Неисправный грузовик становится на стоянку в ожидании ремонта.

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

◄ Обозначим состояния автомашины: - исправна, - ожидает ремонта, - ремонтируется.

.

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

, , . Получается система ОДУ

, , .

Из второго уравнения системы выразим через и подставим в первое уравнение:

Обозначим , . Если , то, обозначив , , получаем искомые вероятности: , ,

В частном случае [2]: , :

, , (см. Рис.2).

КОММЕНТАРИЙ. 1) По прошествии месяцев система почти «забыла» стартовое положение. 2)Наличие максимума у обусловлено первоначальным состоянием автомобиля – «исправен», а затем «массовый» переход автомобилей в состояние ожидания обслуживания (ремонта). 3) Если поменять начальные условия, то изменяются, но примерно через тоже время система «забывает» первоначальное состояние. 4) ЗАДАНИЕ. Самостоятельно исследовать, что явится решением задачи, если взять начальные условия в виде , , ?

Рис. 2

ОДНОКАНАЛЬНАЯ СИСТЕМА ОБСЛУЖИВАНИЯ С ОТКАЗАМИ

ОПРЕДЕЛЕНИЕ. Регулярным потоком событий называется поток, в котором события следуют одно за другим через строго определённые промежутки времени.

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

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

ЗАДАЧА 4. На вход одноканальной СМО с отказами поступает простейший поток заявок с интенсивностью , а время обслуживания заявки – СВ, распределенная по экспоненциальному закону с параметром . Найти характеристики работы системы обслуживания.
(Условное обозначение рассматриваемой СМО: М/М/1 или М/М/1/0)
◄ У системы обслуживания есть два возможных состояния: - канал обслуживания свободен (ноль заявок на обслуживании); - канал обслуживания занят – одна заявка на обслуживание).

Размеченный граф состояний СМО.

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

Откуда ►

Интерпретация полученных результатов.

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

Для установившегося (стационарного) режима функционирования СМО:

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

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

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

ЗАДАЧА 5 Одноканальная СМО представляет собой телефонную линию с отказами, т.е. заявка на соединение, поступившая в момент времени, когда линия занята, получает отказ. Интенсивность потока заявок 0.8 вызовов/мин. Средняя продолжительность разговора 1.5 минуты. Считая поток заявок простейшим, а время обслуживания распределенным по экспоненциальному закону, определить для стационарного режима функционирования:

1. абсолютную пропускную способность канала связи ;

2. относительную пропускную способность канала связи ;

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

4. оценить, насколько канал загружен.

◄ Результатов, полученных в рамках моделей СМО типа М/М/1/0, достаточно для решения поставленной задачи. Из условия задачи имеем:

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

.

Оценим влияние «случайности» поступления заявок и времени обслуживания. Если бы поток заявок был регулярным, то в единицу времени обслуживалось бы заявок, где . Таким образом, номинальная пропускная способность почти вдвое превышает «реальную» пропускную способность канала . Это означает, что почти половину времени свободный канал простаивает по причине отсутствия заявок на обслуживание (очередь ведь отсутствует!).

ЗАДАЧА 6. Одноканальная СМО представляет собой телефонную линию с отказами. Интенсивность потока заявок 0.4 вызова в минуту, средняя продолжительность разговора 2 минуты. Во сколько раз надо сократить среднее время разговора, чтобы сохранить качество обслуживания заявок (т.е. вероятность отказа в обслуживании не должна увеличиться!) при возрастании интенсивности потока заявок до 0.8 вызовов в минуту?

Дата добавления: 2015-06-25