Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лекция 6. Моделирование систем на основе теория массового обслуживания
1. Задачи теории массового обслуживания
При исследовании операций часто приходится сталкиваться с работой своеобразных систем, называемых системами массового обслуживания (СМО). Примерами таких систем могут служить: телефонные станции, ремонтные мастерские, билетные кассы, справочные бюро, магазины, парикмахерские и т. п. Каждая СМО состоит из какого-то числа обслуживающих единиц (или «приборов»), которые мы будем называть каналами обслуживания. Каналами могут быть: линии связи, рабочие точки, кассиры, продавцы, лифты, автомашины и др. СМО могут быть одноканальными и многоканальными.
Всякая СМО предназначена для обслуживания какого-то потока заявок (или «требований»), поступающих в какие-то случайные моменты времени. Обслуживание заявки продолжается какое-то, вообще говоря, случайное время Тоб, после чего канал освобождается и готов к приему следующей заявки. Случайный характер потока заявок и времен обслуживания приводит к тому, что в какие-то периоды времени на входе СМО скапливается излишне большое число заявок (они либо становятся в очередь, либо покидают СМО необслуженными); в другие же периоды СМО будет работать с недогрузкой или вообще простаивать.
В СМО происходит какой-то СП с дискретными состояниями и непрерывным временем; состояние СМО меняется скачком в моменты появления каких-то событий (или прихода новой заявки, или окончания обслуживания, или момента, когда заявка, которой надоело ждать, покидает очередь). Чтобы дать рекомендации по рациональной организации этого процесса и предъявить разумные требования к СМО, необходимо изучить СП, описать его математически. Этим и занимается теория МО.
Предмет теории массового обслуживания — построение математических моделей, связывающих заданные условия работы СМО (число каналов, их производительность, правила работы, характер потока заявок) с интересующими нас характеристиками — показателями эффективности СМО, описывающими, с той или другой точки зрения, ее способность справляться с потоком заявок. В качестве таких показателей (в зависимости от обстановки и целей исследования) могут применяться разные величины, например: среднее число заявок, обслуживаемых СМО в единицу времени; среднее число занятых каналов; среднее число заявок в очереди и среднее время ожидания обслуживания; вероятность того, что число заявок в очереди превысит какое-то значение, и т. д. Область применения математических методов теории МО непрерывно расширяется и все больше выходит за пределы задач, связанных с «обслуживающими организациями» в буквальном смысле слова. Как своеобразные СМО могут рассматриваться: ЭВМ, системы сбора и обработки информации, автоматизированные производственные цеха, поточные линии, транспортные системы, системы ПВО и т.п.
Математический анализ работы СМО очень облегчается, если процесс этой работы — марковский. Для этого достаточно, чтобы все потоки событий, переводящие систему из состояния в состояние (потоки заявок, потоки «обслуживаний»), были простейшими. Если это свойство нарушается, то математическое описание процесса становится гораздо сложнее и довести его до явных, аналитических формул удается лишь в редких случаях. Однако все же аппарат простейшей, марковской теории массового обслуживания может пригодиться для приближенного описания работы СМО даже в тех случаях, когда потоки событий — не простейшие. Во многих случаях для принятия разумного решения по организации работы СМО вовсе и не требуется точного знания всех ее характеристик — зачастую достаточно и приближенного, ориентировочного. Причем, чем сложнее СМО, чем больше в ней каналов обслуживания, тем точнее оказываются эти приближенные формулы.
2. Классификация СМО и их основные характеристики
Системы массового обслуживания делятся на типы (или классы) по ряду признаков. Первое деление: СМО с отказами и СМО с очередью. В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем процессе обслуживания не участвует. Примеры СМО с отказами встречаются в телефонии: заявка на разговор, пришедшая в момент, когда все каналы связи заняты, получает отказ и покидает СМО необслуженной. В СМО с очередью заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает возможности быть обслуженной. На практике чаще встречаются (и имеют большее значение) СМО с очередью; недаром теория массового обслуживания имеет второе название: «теория очередей».
СМО с очередью подразделяются на разные виды, в зависимости от того, как организована очередь—ограничена она или не ограничена. Ограничения могут касаться как длины очереди, так и времени ожидания (так называемые «СМО с нетерпеливыми заявками»). При анализе СМО должна учитываться также и «дисциплина обслуживания» — заявки могут обслуживаться либо в порядке поступления (раньше пришла, раньше обслуживается), либо в случайном порядке. Нередко встречается так называемое обслуживание с приоритетом — некоторые заявки обслуживаются вне очереди. Приоритет может быть как абсолютным — когда заявка с более высоким приоритетом «вытесняет» из-под обслуживания заявку с низшим (например, пришедший в парикмахерскую клиент высокого ранга прогоняет с кресла обыкновенного клиента), так и относительным — когда начатое обслуживание доводится до конца, а заявка с более высоким приоритетом имеет лишь право на лучшее место в очереди.
Существуют СМО с так называемым многофазовым обслуживанием, состоящим из нескольких последовательных этапов или «фаз» (например, покупатель, пришедший в магазин, должен сначала выбрать товар, затем оплатить его в кассе, затем получить на контроле).
Кроме этих признаков, СМО делятся на два класса: «открытые» и «замкнутые». В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии сама СМО (сколько каналов занято). В замкнутой СМО — зависят. Например, если один рабочий обслуживает группу станков, время от времени требующих наладки, то интенсивность потока «требований» со стороны станков зависит от того, сколько их уже неисправно и ждет наладки. Это — пример замкнутой СMO.
В зависимости от типа СМО при оценке её эффективности могут применяться те или иные величины (показатели эффективности). Например, для СМО с отказами одной из важнейших характеристик её продуктивности является так называемая абсолютная пропускная способность – среднее число заявок, которое может обслужить система за единицу времени. Наряду с абсолютной, часто рассматривается относительная пропускная способность – средняя доля поступивших заявок, обслуживаемая системой (отношение среднего числа обслуживаемых в единицу времени заявок к среднему числу поступающих заявок за это время). Помимо этого при анализе СМО с отказами могут интересовать ещё среднее число занятых каналов, среднее относительное время простоя системы в целом и отдельного канала и т.д.
Характеристики СМО с ожиданиями. Для СМО с неограниченным ожиданием абсолютные и относительные пропускные способности теряют смысл. Зато важными являются: среднее число заявок в очереди, среднее число заявок в системе (в очереди и под обслуживанием), среднее время ожидания заявки в очереди, среднее время пребывания заявки в системе и другие. Для СМО с ограниченным ожиданием интерес представляют обе группы характеристик.
Для анализа процесса, протекающего в СМО, существенно знать основные параметры системы: число каналов n, интенсивность потока заявок , производительность каждого канала (среднее число заявок , обслуживаемых непрерывно занятым каналом в единицу времени), условия образования очереди (ограничения, если они есть).
Условимся все потоки событий, переводящие СМО из состояния в состояние, считать пуассоновскими.
3. Одноканальная СМО с отказами
Простейшая задача. Пусть СМО состоит только из одного канала (n=1) и на нее поступает пуассоновский поток заявок с интенсивностью , зависящей в общем случае от времени =(t) (9.1). Заявка, заставшая канал занятым, получает отказ и покидает систему. Обслуживание заявки продолжается в течение случайного времени Тоб, распределенного по показательному закону с параметром f(t)= e-t (t0) (9.2).
Из этого следует, что «поток обслуживаний» - простейший, с интенсивностью m. Требуется найти: абсолютную (А) и относительную (q) пропускные способности.
Рассмотрим единственный канал обслуживания как физическую систему S, которая может находиться в одном из двух состояний: S0 – свободен, S1 – занят. Обозначим вероятности состояний p0(t) и p1(t). Очевидно:
t p0(t)+p1(t)=1 (9.3).
Граф состояний системы
По графу состояний системы составим дифференциальные уравнения Колмогорова:
(9.4)
В соответствии с (9.3) одно уравнение в (9.4) лишнее. Отбросим второе уравнение, а первое перепишем с учетом (9.3):
или (9.5).
Это уравнение естественно решать при начальных условиях p0(0)=1; p1(0)=0. Уравнение (9.5) легко может быть решено не только для простейшего потока заявок (=const), но и для случая =(t). Приведем решение (9.5) только для случая =const: .
Для нашего случая вероятность p0 есть не что иное, как q.
Действительно, p0 есть вероятность того, что в момент t канал свободен, иначе вероятность того, что заявка, пришедшая в момент t, будет обслужена. А значит, для данного момента времени t среднее число обслуженных заявок к числу поступивших также равно p0: q= p0.
В пределе, при t, когда процесс обслуживания уже установится, предельное значение q будет равно .
Легко найти и А, зная q. Они связаны очевидным соотношением:. В пределе, при t, А тоже установится и будет равна .
Зная q (вероятность того, что пришедшая в момент t заявка будет обслужена) легко найти вероятность отказа: Pотк =1-q. Pотк есть не что иное, как средняя доля необслуженных заявок среди поданных. В пределе, при t .
4. Многоканальная СМО с отказами
Рассмотрим n-канальную СМО с отказами. Будем нумеровать состояния системы по числу занятых каналов (или, что в данном случае то же, по числу заявок, связанных с системой). Состояния будут:
S0 – все каналы свободны;
S1 – занят ровно один канал, остальные свободны;
……
Sk – заняты ровно k каналов, остальные свободны;
…….
Sn – заняты все n каналов.
Граф состояний имеет следующий вид. Слева направо систему переводит один и тот же поток – поток заявок с интенсивностью .
Очевидно, если обслуживанием занято 2 канала, а не один, поток обслуживаний, переводящий систему по стрелке S2S1, будет вдвое интенсивнее (2), если занято k- каналов – в k раз интенсивнее (k). Процесс такого вида представляет собой частный случай процесса гибели и размножения. Составляем уравнения Колмогорова:
(9.6).
Уравнения (9.6) называются уравнениями Эрланга. Естественными начальными условиями являются:
p0(0)=1; p1(0)=p2(0)=…=pn(0)=0
Интегрировать (6) в аналитическом виде довольно сложно, на практике решают численно с использованием ЭВМ. Такое решение дает нам все вероятности состояний как функции времени: p0(t), p1(t), …, pn(t).
Больше всего интересны предельные вероятности состояний, характеризующие установившийся режим работы СМО (при t). Воспользуемся готовым решением, полученным для схемы гибели и размножения:
(k=1,2,..n) (9.7).
Обозначим и будем называть величину «приведенной интенсивностью» потока заявок. Физический смысл её таков: величина представляет собой среднее число заявок, приходящих в СМО за среднее время обслуживания одной заявки. С учетом этого (9.7) принимает вид:
(9.8). Формулы Эрланга.
Теперь можно найти характеристики эффективности СМО: q, А, Ротк.
Заявка получает отказ, если приходит в момент, когда все n каналов заняты. Вероятность этого равна:
.
Вероятность того, что заявка будет принята к обслуживанию (она же q) дополняет Ротк до 1: q = 1-pn. И наконец: А= q=(1- pn).
Одной из важных характеристик СМО с отказами является среднее число занятых каналов (в данном случае оно совпадает со средним числом заявок, находящихся в системе). Обозначим это среднее число . Величину можно вычислить непосредственно по формуле:
как математическое ожидание дискретной случайной величины, принимающей значение 0,1, …n с вероятностями p0, p1…pn.
Однако значительно проще выразить через А . А есть не что иное, как среднее число заявок, обслуживаемых в единицу времени; один занятый канал обслуживает в среднем за единицу времени заявок; следовательно, среднее число занятых каналов
или .
5. Одноканальная СМО с ожиданием
На СМО поступает поток заявок с интенсивностью , интенсивность обслуживания (т.е. в среднем непрерывно занятый канал будет выдавать обслуженных заявок в единицу времени), n=1. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания. Предположим, что количество мест в очереди ограничено числом m (в дальнейшем, при m можно получить характеристики одноканальной СМО без ограничений по длине очереди). Будем нумеровать состояния СМО по числу заявок, находящихся в системе (как обслуживаемых, так и ожидающих обслуживания):
S0 – канал свободен; S1 – канал занят, очереди нет; S2 – канал занят, одна заявка стоит в очереди; Sk – канал занят, k -1 стоят в очереди; Sm+1 – канал занят, m заявок стоят в очереди. Граф состояний (размеченный) имеет вид:
Снова схема гибели и размножения. Пользуясь общим решением, напишем выражения предельных вероятностей состояния:
или (9.9).
В знаменателе выражения для р0 стоит геометрическая прогрессия, суммируя её находим
(9.10).
(9.10) справедливо только при (иначе неопределенность вида ). Но сумму геометрической прогрессии со знаменателем найти ещё проще, чем по (9.10); она равна (m+2) и в этом случае p0=1/(m+2) {то же самое получится, если раскрыть неопределенность по правилу Лапиталя}.
Определим характеристики СМО: Ротк q, А, среднюю длину очереди , среднее число заявок, связанных с системой .
Очевидно, заявка получает отказ только в том случае, когда канал занят и все m мест в очереди – тоже:
(9.11).
(9.12).
А=q. Найдем среднее число , находящихся в очереди; определим эту величину как математическое ожидание дискретной случайной величины R – числа заявок , находящихся в очереди:.
.
Выведем формулу для суммы. Эта сумма не что иное, как производная по суммы , а для этого выражения мы можем воспользоваться формулой суммы геометрической прогрессии:
Продифференцируем её по и проведя преобразования, найдем
(9.13).
Тогда .
Подставляем p0 из (10) и получаем
(9.14).
Выведем теперь формулу для . Рассмотрим общее число заявок К, связанных с системой, как сумму двух случайных величин: числа заявок, стоящих в очереди и числа заявок, находящихся под обслуживанием: .
По теореме сложения математических ожиданий:
, где - среднее число заявок в очереди; - среднее число заявок под обслуживанием. Найдем . Т.к. канал у нас один, то случайная величина может принимать только два значения: 0 или 1. Значение 0 она принимает, если канал свободен; вероятность этого равна . Значение 1 она принимает, если канал занят; вероятность этого равна .
Отсюда находим:
.
, где находим из (9.14).
Выведем выражение еще для одной существенной характеристики СМО с ожиданием: среднего времени ожидания заявки в очереди. Обозначим его . Пусть заявка приходит в систему в какой-то момент времени. С вероятностью p0 канал обслуживания не будет занят и ей не придется стоять в очереди (tож=0). С вероятностью p1 она придет в систему во время обслуживания какой-то заявки, но перед ней не будет очереди, и заявка будет ждать начала своего обслуживания в течение времени 1/ (среднее время обслуживания одной заявки). С вероятностью p2 в очереди перед ней будет стоять еще одна заявка и время ожидания в среднем будет 2/ и т.д. Вообще, с вероятностью pk пришедшая заявка застанет в системе k заявок и будет ждать в среднем k/ единиц времени (1km). При k=m+1 (в очереди m заявок, вероятность этого pm+1) tож=0 (заявка не обслуживается).
.
Подставим сюда выражения для p1,p2,…pm из (9.9).
.
Преобразуем сумму в скобках, используя (9.13)
Или, выражая p0 через
.
Сравнивая это выражение с (9.14) , замечаем, что
, (9.15)
т.е. среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.
Выведем ещё одну формулу для среднего времени пребывания заявки в системе. Обозначим случайную величину – время пребывания заявки в СМО через Тсист.. Она складывается из двух слагаемых (тоже случайных):
Тсист.=Тож +, где Тож - время ожидания заявки в очереди, случайная величина, равная времени обслуживания Тоб, если заявка обслуживается и 0, если она не обслуживается (получает отказ). По теореме сложения математических ожиданий: , но в наших обозначениях , а . Отсюда находим: или с учетом (9.15)
.
Формула Литтла (первая): для любой СМО, при любом характере потока заявок, при любом распределении времени обслуживания, при любой дисциплине обслуживания среднее время пребывания заявки в системе равно среднему числу заявок в системе, деленному на интенсивность потока заявок.
Формула Литтла (вторая): для любой СМО, при любом характере потока заявок, при любом распределении времени обслуживания, при любой дисциплине обслуживания среднее время пребывания заявки в очереди равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.
Теперь можно рассмотреть работу одноканальной СМО с ожиданием при m (неограниченная очередь). Совершить предельный переход m.
6. Многоканальные СМО с ожиданием
Можно рассмотреть работу многоканальной СМО с ожиданием.
Состояние системы будем нумеровать по числу заявок, связанных с системой:
S0 – все каналы свободны;
S1 – занят один канал, остальные свободны;
… … …
Sk – заняты k каналов, остальные свободны;
… … …
Sn – заняты все n каналов;
Sn+1 – заняты все n каналов, одна заявка стоит в очереди;
… … …
Sn+r – заняты все n каналов, r заявок в очереди;
… … …
Sn+m – заняты все n каналов, m заявок в очереди.
Размеченный граф состояний имеет вид
Написать уравнения Колмогорова. Найти вероятности состояний. В их помощью рассчитать все интересующие величины. Затем опять можно рассмотреть и случай m.
7. СМО с ограниченным временем ожидания
Можно рассмотреть СМО с ограниченным временем ожидания , суть которой в следующем: на каждую заявку, стоящую в очереди действует как бы «поток уходов» с интенсивностью (- среднее время пребывания в очереди).
Существуют и другие разновидности СМО:
замкнутые СМО (интенсивность потока поступающих заявок зависит от состояния самой СМО),
СМО с «взаимопомощью» между каналами (незанятые каналы «помогают» занятому в обслуживании). и т.д.
S0
S1
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
S0
S1
S2
Sk
Sn
2
3
k
(k+1)
n
S0
S1
S2
Sk
Sm+1
EMBED Equation.3
S0
EMBED Equation.3
S1
Sk
Sn
Sn+1
Sn+r
Sn+m
2
k
(k+1)
n
n
n
n
n
n
Sn
Sn+1
Sn+r
n+
n
n+2
n+r
n+(r+1)