книги / Прикладная теория систем массового обслуживания

'обе = fo, Цобс= 1 /kt=\i/k,

где /обе - время обслуживания заявки; к - число обслуживающих приборов; Робе - интенсивность обслуживания заявки.

В рамках принятых в главе 2 допущений состояние СМО представим в виде вектора *, = >-’* т > - Л тах ), где кт- число заявок в

системе, каждая из которых обслуживается т приборами; L = qmfiX- #тт+1 - число входных потоков.

Тогда количество занятых и свободных приборов (n2m(Xj ), лСн(*, )) в состоянии Xj определяется следующим образом:

9max

I>*m >

т~Ят\

псъ(**) п ^зан(**)*

Из состояния х; система может перейти в любое другое состояние

Xj . Так как в системе действует L входных потоков, то из каждого состоя­

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

т < исв(х, ), то заявка принимается на обслуживание и система переходит в

состояние Xj = (kqmin ,fc?min+1 ,- ,(к т + ) с интенсивностью К-

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

обслуживается с интенсивностью р/т , а общая интенсивность обслужи­ вания таких заявок (рт) определяется как р т = кт\х / т. При завершении обслуживания одной из заявок система перейдет в состояние, в котором соответствующая координата имеет значение, на единицу меньшее, чем в

состоянии X,, xv =[k4m.n,kqm.n+l,...,(km-ï),...,kqmM), т.е. произойдет об-

ратный переход. На рис. 3.9 представлен пример векторной модели СМО для п = 3, L = 3, <7mjn = 1, Ятах= 3, Р(т) = 1/3, XIt = X, интенсивность обслу­ живания прибора - р.

Следовательно, 5 = 1 + 5 + 1 = 7.

Для реализации реальных требований к обслуживающим приборам необходимо достаточно большое число п (40, ..., 50), а запросы на число обслуживающих приборов заявки на практике лежат в пределах 8-16. При таком соотношении приборов и запросов предложенный путь нахождения вероятностей становится чрезвычайно громоздким, т.к. векторная модель СМО имеет большое число состояний 5(50) = 1790, 5(60) = 4676, 5(70) = = 11075, а размер матрицы коэффициентов системы алгебраических урав­ нений пропорционален квадрату 5 [24], что требует большого объема па­ мяти ЭВМ и значительных затрат машинного времени. Стремление сни­ зить объем вычислений стимулировало поиск рекуррентных возможностей расчета P(xt ) на основе мультипликативных форм представления вероят­

ностей состояний. В работе [11] представлен подход к расчету P(xt ):

Использование предложенного в работе [11] критерия эквивалентно­ сти глобального и детального балансов цепей Маркова позволяет снижать размерность задачи и выполнять вычисления на ЭВМ средней мощности, используя рекуррентность вычислений. Кроме того, имеется возможность:

-произвести расчет для любых значений л;

-ускорить расчет и снизить затраты машинного времени. Аналогичным образом могут быть определены и другие характери­

стики системы.

3.4.5. Примеры систем массового обслуживания с отказами

Пример 3.1. Рассматривается работа районной автоматической те­ лефонной станции (АТС), которая обеспечивает не более 120 переговоров одновременно. Средняя длительность переговоров 1/р = 1 мин. Вызовы на станцию поступают через 0,5 с, т.е. \Гк = 0,5 с. Требуется найти характери­

стики работы АТС: к , J^j6c9 пЗ К, t з.к , / п.к •

Решение

АТС представляет собой 120-канальную СМО с отказами. Парамет­ ры системы следующие: п = 120; X= 2 сооб/с; р = 1/60 сооб/с; р = А/р = 120.

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

Ппи

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

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

Решение

Задачу будем решать при условии, что время установления стацио­ нарного режима в системах мало по сравнению со временем переоборудо­ вания тп и временем t (t > т„). Начало отсчета для времени тп и t одно. В этом случае можно записать следующее уравнение:

С1Х0(,)г= -С2+С,Ао(2)( г- тп)>

- абсолютная пропускная способность СМО с отка-

R{n,p)

1 Y ^

зами; Хо(2)= X-----^-г - абсолютная пропускная способность СМО с отка- 1 -х "+

зами и взаимопомощью; р = ХУр; х = ХУир.

Решая это уравнение, получим /, по истечении которого реорганиза­ ция начнет приносить прибыль:

Пример 3.3. Определить, насколько увеличится вероятность обслу­ живания для СМО с отказами, имеющей следующие параметры: п = 10, X= = 8 сооб/мин; р = 0,8 сооб/мин, если обеспечить взаимопомощь группы из двух каналов (/ = 2).

Решение

Для СМО с отказами без взаимопомощи вероятность обслуживания

л>бс(,)= Л(я-1,Р)

R(n,p)

Для примера

Для системы с частичной взаимопомощью имеем

N=10; х = Х/иц= 1; р/= X//р = 0,5; /г = ]«//[ = 5.

Для этой системы в случае, когда %= 1, вероятность обслуживания

Таким образом,

Робс(2)- Ллс(1) = 0,883 - 0,795 = 0,088.

Пример 3,4. Рассматривается система ПВО с нарушенным управле­ нием. Нарушение управления состоит в том, что каждую влетающую в зо­ ну обстрела цель обстреливают все свободные к этому времени каналы. Обстрел цели каждым каналом длится случайное время, распределенное по показательному закону с параметром ц. За это время каждый канал по­ ражает цель с вероятностью р независимо от других каналов, принимаю­ щих участие в обстреле. Определить характеристики работы системы, если параметры системы ПВО следующие: п = 4; X = 4 1/мин; ц = 1 1/мин; р = = 0,5.

Решение

у

В рассматриваемом примере величина а = —= 4 - целое число. Ве-

роятности различных состояний системы следующие:

а+п

Вероятности поражения цели

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

а

я,п.з а +п = 0,5.

Среднее время полной загрузки

tnз = — = 0,25 мин. n\i

Среднее время неполной загрузки

Гн з = ~ = 0,25 мин.

к

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

k = Z k p k =3,2.

k=0

Вероятность того, что канал занят,

л з.к = — = 0,8.

п

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

t3к = —= 1 мин.

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

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

Среднее число обстреливаемых целей

I =tX =1,75.

4.СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ

СОЖИДАНИЕМ

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

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

Вэтой главе будут рассмотрены системы массового обслуживания

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

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

системы понятие «отказ» не имеет смысла. Это системы массового обслу­ живания с бесконечной очередью.

Всистеме с ожиданием смешанного типа возможны как отказы, так

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

При рассмотрении СМО с ожиданием необходимо учитывать сис­ тему правил, регламентирующих порядок образования и обслуживания очереди (так называемую дисциплину очереди). Необходимо указать, яв­ ляется ли очередь общей или образуется к каждому каналу отдельно; каков порядок вызовов заявок из очереди и т.д. Из всего многообразия известных дисциплин обслуживания [17, 25] выберем дисциплину со следующими особенностями: очередь является общей, т.е. все приходящие заявки ста­ новятся в одну очередь к обслуживающим приборам; порядок вызовов зая­ вок из очереди FIFO (first in - first out) - «кто раньше встал в очередь, тот и раньше обслуживаете*».

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

4.1.Классическая система массового обслуживания с ожиданием

Постановка задачи. В качестве обслуживающей системы рассмот­ рим неблокирующую коммутационную систему, которая обслуживает полнодоступный пучок емкостью я ( 1 < я < оо) линий, на которые поступа­ ет простейший поток с параметром X. Каждая поступившая заявка для об­ служивания занимает любую свободную линию пучка и обслуживается с интенсивностью р. Если все я линий пучка заняты, то она становится в очередь и «терпеливо» ждет своего обслуживания. Дисциплина очереди - FIFO, максимальное число мест в очереди - т (СМО с конечной очере­ дью). Если заявка застает все т мест в очереди занятыми, то она получает отказ и исключается из обслуживания. Величины я, X, р, т будем называть параметрами СМО с ожиданием.

Макросостояния рассматриваемой системы будем связывать с чис­ лом заявок, находящихся в системе (обслуживаемых и ожидающих в оче­ реди):

хк - в системе имеется к заявок (к= 0, 1,2, ..., я), они обслуживают­ ся к каналами, очереди нет;

хп+ г - в системе имеется я + г заявок (г = 1,2, ..., /я), я из них об­ служиваются в я каналах и г заявок находятся в очереди.

Таким образом, система имеет я + т + 1 макросостояний. Граф мак­ росостояний рассматриваемой системы показан на рис. 4.1.

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

Этому графу состояний соответствует система дифференциальных уравнений для вероятностей состояний, которую обычно интегрируют для начальных условий

/> о ( 0 ) = 1 , Л ( 0 ) = 0 ( 1 * 0 ) ,

т.е. в момент времени t = 0 система свободна от заявок. Для стационарного режима работы СМО с ожиданием, когда X = const, р = const,

используя результаты главы 3, имеем

а* Рк =— Р0 (к =0,1,2,...,л); Рп+Г = хгР„ (г = 0,1,2,..,,т) ,

к\