Читайте также:
|
|
1.1 Общие понятия теории массового обслуживания
Основной задачей теории массового обслуживания является установление количественных зависимостей между числом приборов обслуживания, характеристиками входящего потока требований (заявок) и качеством обслуживания. При этом под качеством обслуживания понимается, насколько своевременно проведено обслуживание поступивших в систему требований, насколько полно загружены обслуживающие приборы, не велик ли уход из системы не обслуженных требований, не создается ли большая очередь.
Каждая система массового обслуживания (СМО) состоит из какого-то количества обслуживающих единиц, которые называются каналами обслуживания (это станки, транспортные тележки, роботы, линии связи, кассиры, продавцы и т.д.). Всякая СМО предназначена для обслуживания какого-то потока заявок (требований), поступающих в какие-то случайные моменты времени.
Обслуживание заявки занимает случайное время, после чего канал освобождается и готов к приему следующей заявки. Случайный характер потока заявок и времени обслуживания может привести к тому, что в какие – то периоды времени на входе СМО скапливается излишне большое количество заявок (они либо становятся в очередь, либо покидают СМО необслуженными). В другие же периоды СМО будет работать с недогрузкой или вообще простаивать.
Предмет теории массового обслуживания – построение математических моделей, связывающих заданные условия работы СМО (число каналов, их производительность, правила работы, характер потока заявок) с показателями эффективности СМО. Эти показатели описывают способность СМО справляться с потоком заявок. Ими могут быть: среднее число заявок, обслуживаемых СМО в единицу времени; среднее число занятых каналов; среднее число заявок в очереди; среднее время ожидания обслуживания и т.д.
По своему составу СМО делятся на системы с одним обслуживающим прибором (каналом) и многими приборами обслуживания, называющимися соответственно одноканальными и многоканальными.
Многоканальные системы могут состоять из однотипных или разнотипных приборов.
По времени пребывания требований в системе до начала обслуживания СМО делятся на:
- системы с отказами;
- системы с неограниченным временем ожидания;
- системы смешанного типа (с ограниченным временем ожидания).
В системах с отказами всякое поступившее требование, застав все приборы занятыми, покидает систему.
В системах с неограниченным временем ожидания поступившее в систему требование и обнаружившее все приборы занятыми вынуждено ожидать своей очереди до момента освобождения какого-нибудь (или определенного) прибора.
В системах смешанного типа поступившие требования, застав все приборы занятыми, становятся в очередь. Но в ней они находятся ограниченное время, по истечении которого покидают систему. К смешанным системам относятся также системы с ограниченной длиной очереди.
Поток событий – последовательность однородных или неоднородных событий, которые наступают через случайные промежутки времени. Случайные временные интервалы между наступлениями событий в потоке могут подчиняться различным законам распределения. В большинстве работ по теории массового обслуживания, особенно прикладного характера, рассматривается пуассоновский (простейший) поток, в котором вероятность поступления в промежуток времени t ровно k требований задается формулой Пуассона:
,
где λ – плотность потока требований.
Простейший поток теории массового обслуживания играет такую же роль, как нормальный закон распределения случайных величин в теории вероятностей.
Простейший поток обладает тремя основными свойствами: стационарностью, отсутствием последействия и ординарностью.
Случайный поток называется стационарным, если вероятность поступления определенного количества требований в течение определенного отрезка времени зависит от его (отрезка) величины и не зависит от начала его отсчета на оси времени, то есть зависит от величины времени τ и не зависит от положения этого интервала на временной оси.
Отсутствие последействия означает, что события, образующие поток, появляются в те или иные моменты времени независимо друг от другаи вызваны каждое своими собственными причинами.
Ординарность потока требований означает практическую невозможность появления двух и более требований в один и тот же момент времени.
Важной характеристикой потока является его интенсивность, которая определяется как математическое ожидание числа требований, поступающих за единицу времени. Интенсивность потока событий – это среднее число событий, приходящееся на единицу времени.
Математическое ожидание числа требований, поступающих за время (0, t) равно
Для нестационарных простейших потоков вероятность появления k требований за время Δ t зависит не только от величины Δ t но и от момента t0, который является началом этого промежутка.
Кроме характеристик потока событий, поступающих в систему обслуживания, режим работы системы зависит от времени обслуживания прибором одного требования. Время обслуживания является важнейшей характеристикой каждого канала и определяет его пропускную способность. Оно представляет собой случайную величину в силу нестабильности работы обслуживающих приборов и неидентичности поступающих в систему требований. Полной характеристикой времени обслуживания является закон распределения:
.
Для большого количества СМО принимается показательный закон распределения времени обслуживания, то есть
,
плотность вероятности для которого определяется по формуле:
,
где μ – математическое ожидание числа требований, обслуженных прибором за единицу времени.
Выходящий поток играет существенную роль в том случае, если он сам образует входящий поток для других приборов, расположенных последовательно с первым. Поток, проходя через каждую группу приборов, искажается и становится все более сложным.
Показатели эффективности зависят от 3 групп факторов: характеристик качества и надежности системы; экономических показателей (стоимости системы, трудовых затрат обслуживающего персонала, убытков, связанных с несвоевременным обслуживанием и т.д.); особенностей ситуации, в которой обслуживается система (параметров потока требований, ограничений на длину очереди и т.д.).
В зависимости от условий эксплуатации системы и принятого показателя эффективности выбирается математическая модель процесса.
Наиболее часто применяемые показатели:
- вероятность потери требования (pn);
- вероятность того, что обслуживанием занято k приборов (pk):
,
где n – число приборов.
- среднее число занятых приборов, характеризующая степень загрузки СМО:
;
- среднее число свободных приборов:
;
- коэффициент простоя приборов
;
- коэффициент занятости оборудования:
;
- среднее время ожидания требований в очереди до начала обслуживания:
,
где
,
где Pk(tож>t) – условная вероятность того, что время ожидания больше t, при условии, что в момент поступления требования в ней обслуживались k требований;
pk – вероятность того, что в системе находится k требований.
- вероятность того, что время ожидания в очереди не продлится больше определенной величины:
;
- средняя длина очереди:
,
где pk – вероятность того, что в системе находится k требований.
Кроме указанных, могут использоваться стоимостные показатели, такие как: стоимость обслуживания каждого требования, стоимость потерь, связанных с простаиванием требований в очереди в единицу времени, стоимость убытков, связанных с уходом требований из очереди и др.
В качестве экономического показателя качества используется стоимость потерь для систем с ожиданием:
,
где qож – стоимость потерь, связанных с ожиданием в очереди в единицу времени;
qпр – стоимость единицы времени простоя прибора;
qbusy – стоимость эксплуатации прибора в единицу времени.
Для системы с отказами:
.
Для смешанной системы:
2.2 Смешанная СМО с одним прибором
СМО состоит из одного прибора и очереди; в системе может одновременно находиться не более чем n требований; очередь упорядоченная. Обозначим через X(t) число требований, находящихся в системе в момент t. Функция X(t) принимает (n+1) значение: x0 – в системе нет требований, x1 – в системе одно требование, …, xn – в системе n требований.
Определим вектор вероятности p(t) = [p0(t), p1(t), …, pn(t)] состояний системы для любого момента времени t, где pq(t) – вероятность того, что функция X(t) в момент времени t принимает значения xq, q = 0, 1, …, n. Заменим непрерывное время t прерывным, меняющимся скачкообразно через интервал Δt и сведем, тем самым, X(t) к простой цепи Маркова. Составим матрицу вероятностей перехода pij (t, t+Δt) из состояния xi в момент t в состояние xi, в момент (t+Δt) при условии, что Δt мало.
Вследствие ординарности входящего потока и показательного закона распределения времени обслуживания за малый интервал Δt не может произойти соответственно более одного поступления и более одного окончания обслуживания. Поэтому в интервале (t, t+Δt) могут произойти следующие переходы:
.
Определим вероятности следующих событий:
1) за интервал (t, t+Δt) в систему не поступит ни одного требования;
2) за интервал (t, t+Δt) прибор не закончит обслуживания.
Вероятность первого события:
.
Вероятность второго события:
Тогда вероятность поступления в систему ровно одного требования за интервал (t, t+Δt) и вероятность того, что за интервал (t, t+Δt) прибор обслужит ровно одно требование равны: 1-(1-λΔt)=λΔt и 1-(1-µΔt)=µΔt, как вероятности событий, противоположных рассмотренным.
Вычислим вероятность pqq(t, t+Δt), где n>q>0. Если в момент t в системе находилось q требований, то событие, состоящее в том, что в момент t+Δt в системе по-прежнему будет находиться q требований, можно рассматривать как сумму следующих несовместных событий:
события А – за интервал (t+Δt) ни одно требование не поступило в систему и ни одно требование не было обслужено Р(А)≈ (1-λΔt)(1-µΔt);
события B – за интервал (t+Δt) в систему поступило ровно одно требование и за это же время прибор закончил обслуживание одного требования и оно покинуло систему. P(B)≈λ∆t*μ∆t.
Таким образом,
так как 2λµΔt2 является величиной бесконечно малой более высокого порядка, чем Δt.
Рассуждая аналогично, можно определить и другие вероятности перехода pij (t, t+Δt).
Переход | Вероятность |
Учитывая то, что вектор вероятностей простой цепи Маркова в момент времени ti равен произведению вектора вероятностей в момент времени t(i-1) на матрицу переходов, путем нескольких преобразований можно получить следующую формулу вероятности pq:
,
где .
Вычислим основные вероятностные характеристики системы:
1. Математическое ожидание числа требований в системе.
2. Математическое ожидание числа требований в узле обслуживания.
s – число приборов;
qmax – максимальное число требований в системе.
3. Математическое ожидание числа требований в очереди
4. Математическое ожидание числа свободных приборов
5. Вероятность отказа
Пример.
Перед обслуживающим прибором расположен накопитель, в который поступают заявки. Интенсивность потока заявок – 2 заявки в минуту, среднее время обслуживания – 20с, максимальное число заявок в системе – 3. Вычислить основные вероятностные характеристики системы.
Решение.
Варианты исходных данных
Вариант 1
Дежурный по администрации города имеет один телефон. Телефонные звонки поступают с интенсивностью 90 заявок в час, средняя продолжительность разговора составляет 2 мин. Вычислить основные вероятностные характеристики системы.
Вариант 2
СМО представляет собой АЗС с одной колонкой. Площадка возле АЗС позволяет ожидание в очереди не более 2 машин. Поток автомашин на заправку простейший с интенсивностью 35 машин в час. Среднее время заправки составляет 3 мин. Вычислить основные вероятностные характеристики системы.
Вариант 3
В магазине самообслуживания установлено, что поток покупателей является простейшим с интенсивностью 2 покупателя в минуту. Среднее время ожидания составляет 1.5 мин. Максимальное количество покупателей 5. Вычислить основные вероятностные характеристики системы.
Вариант 4
Пункт по ремонту квартир состоит из двух бригад. Интенсивность потока заявок 30, производительность пункта 20. Вычислить основные вероятностные характеристики системы.
Вариант 5
Стол заказов магазина «Продукты» принимает заказы по двум телефонам. Среднее число поступающих заказов в течение часа – 80, среднее время оформления заказа – 3 минуты. Вычислить основные вероятностные характеристики системы.
Вариант 6
СМО представляет собой одну кассу для продажи билетов. В среднем через кассу проходят 100 человек в час, среднее время выписки билета – 5 минут. Определить основные вероятностные характеристики СМО, если максимальная длина очереди – 10 человек.
Содержание отчета
Отчет должен содержать:
– основные положения теории массового обслуживания;
– листинг сессии вычисления вероятностных характеристик;
– полученные результаты.
Дата добавления: 2014-12-20; просмотров: 35 | Поможем написать вашу работу | Нарушение авторских прав |