ТЕОРИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ И ЕЕ ПРИЛОЖЕНИЯ

УДК 519.872

Н.Н. Максимова, О.И. Сергамасова

ТЕОРИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ И ЕЕ ПРИЛОЖЕНИЯ

В статье рассматриваются понятие теории массового обслуживания и ее приложения. Представлены составление уравнений Колмогорова и нахождение финальных вероятностей. Рассмотрены также примеры. Статья носит обзорный характер.

The paper is a review, in which the concept of queuing theory and its applications is considered. The paper presents the Kolmogorov equations set-up and finding offinal probabilities. Some examples are given.

Введение

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

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

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

Работа СМО представляет собой случайный процесс с дискретными состояниями и непрерывным временем.

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

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

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

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

Кроме этих признаков, СМО делятся на два класса: «открытые» и «замкнутые». В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии сама СМО (сколько каналов занято), в замкнутой - зависят [1].

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

Основы марковских процессов. Уравнения Колмогорова

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

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

данный момент и не зависят от того, когда и как система пришла в это состояние.

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

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

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

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

Рассмотрим некоторую произвольную систему. Система имеет n состояний S^S2,...,Sn. Процесс перехода из одного состояния в другое описывается непрерывной цепью Маркова. Пусть pi (t) - вероятность того, что в момент времени t система будет находиться в состоянии Si (i = 1,2,...,n) . Поскольку система не может находиться одновременно в двух состояниях, то события, заключающиеся в нахождении системы в состояниях S1,S2,...,Sn, несовместны и образуют полную систему событий. Отсюда следует:

t^Pi (t)=i.

Это соотношение называется условием нормировки. Задача заключается в определении вероятности любого состояния pi (t) в любой момент времени t.

Введем понятие вероятности перехода системы из состояния i, где она находилась в момент времени t, в состояние j за время At p^ (t, At). Очевидно, что ptj (t, At) представляет собой

условную вероятность того, что в момент времени t + At система окажется в состоянии Sj при

условии, что в момент времени t она находилась в состоянии Si: Pj (t, At) = p(S}- (t + At) / Sf (t)).

Предел отношения вероятности перехода pj}- (t, At) к длине интервала времени At назовем

плотностью вероятности перехода

Pa (t, At) 1 (t) = lim ^ .

j w At®0 At

Плотность вероятности перехода определим только для случаев i Ф j .

Если 1ij (t) = const, то марковская цепь называется однородной. В противном случае, когда lij (t) являются функциями времени, цепь называется неоднородной. При расчетах вероятностей состояний марковской цепи предполагается, что все эти плотности вероятностей переходов 1

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

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

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

Начальные условия для системы уравнений Колмогорова определяются начальным состоянием системы. Например, если начальное состояние было S2 , то начальные условия имеют вид: p1(0) = 0; p2(0) = 1; p3(0) = 0;...;

P„ (0) = 0.

Рассмотрим систему с размеченным графом состояний, изображенным на рис. 1. Система уравнений Колмогорова для

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

этого случая в соответствии с правилом будет иметь вид:

= -(112 + 113) Pl +131 Рэ.

= -123 P2 +112 Pl +132 Рз.

= -(131 + ^32 )P3 +^13 Pl + ^23P2 .

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

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

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

Теперь поставим вопрос: что будет происходить с вероятностями состояний при t ® ¥ ? Будут ли P1(t),P2(t),... стремиться к каким-то пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний. В теории случайных процессов доказывается, что если число n состояний системы конечно и из каждого из них можно (за конечное число шагов) перейти в любое другое, то финальные вероятности существуют [1].

Финальные вероятности будем обозначать теми же буквами P1, P2,..., что и сами вероятности состояний, но под ними уже не переменные величины (функции времени), а постоянные числа. Очевидно, они тоже образуют в сумме единицу.

Финальную вероятность состояния Si можно истолковать как среднее относительное время пребывания системы в этом состоянии.

Если вероятности P1,P2,... постоянны, то их производные равны нулю. Значит, чтобы найти финальные вероятности, нужно все левые части в уравнениях Колмогорова положить равными нулю и решить полученную систему уже не дифференциальных, а линейных алгебраических уравнений. Можно и не писать уравнений Колмогорова, а прямо по графу состояний написать систему линейных алгебраических уравнений. Если перенести отрицательный член каждого уравнения из правой части в левую, то получим сразу систему уравнений, где слева стоит финальная вероятность данного состояния Pi умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа - сумма произведений интенсивностей всех потоков, входящих в i-e состояние, на вероятности тех состояний, из которых эти потоки исходят.

(112 + 113) P1 =11 Pз,

(131 + 132) P3 =13 P1 + 1233 P2.

Для решения данной системы необходимо исключить одно из уравнений и добавить условие нормировки:

P1 + P2 + P3 =1.

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

Схема гибели и размножения

Часто в системах самого различного назначения протекают процессы, которые можно представить в виде модели «гибели и размножения».

Граф состояний такого процесса показан на рис. 2.

Рис. 2. Схема «гибели и размножения».

Особенностью модели является наличие прямой и обратной связей с каждым соседним состоянием для всех средних состояний; первое и последнее состояния связаны только с одним «соседом».

Название модели - «гибель и размножение» - связано с представлением, что стрелки вправо означают переход к состояниям, связанным с ростом номера состояния («рождение»), а стрелки влево - с убыванием номера состояний («гибель»).

Составлять уравнения Колмогорова нет необходимости, так как структура регулярна, необходимые формулы приводятся в справочниках.

Для приведенных на рис. 2 обозначений формулы имеют вид:

^ 1 1101 . . Лп-1,п ...Л2Д01 ^

Пример 1

Л0 Л21Л10 Ро, Р2

+... +

Лп,п-1Л21Л10

Л21Л10

Лп,п-1Л10

Зо 1 2

Рис. 3. Схема «гибели и размножения».

Процесс «гибели и размножения» представлен графом на рис. 3. Найти предельные вероятности состояний.

Решение

По формулам, указанными выше, найдем:

Р0 = Г1 +1 + — 1 = 0.706, р =1 • 0.706 = 0.176, 0 ^ 4 3 • 4) 1 4

Р2 = — • 0.706 = 0.118, 2 3 • 4

т.е. в установившемся, стационарном режиме в среднем 70,6% времени система будет находиться в состоянии S0, в 17,6% - в состоянии 51 и в 11,8% - в состоянии 52 .

Пример 2

Имеется система из двух одинаковых и работающих параллельно компьютеров. Требуется определить надежностные характеристики этой системы.

Решение

В этой системе возможны три состояния: - оба компьютера исправны; 52 - один компьютер исправен, другой ремонтируется; 53 - оба компьютера неисправны и ремонтируются. Будем полагать, что процессы отказов и восстановлений - однородные марковские, одновременный выход из строя обоих компьютеров, как и одновременное восстановление двух отказавших компьютеров, практически невозможны.

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

С учетом сказанного, ситуация моделируется схемой «гибели и размножения» ( рис. 4).

Ли. Я2, - интенсивности потоков отказов; Рис. 4. Схема «гибели

и размножения» М21 > М32 - интенсивности потоков восстановлений.

Пусть среднее время безотказной работы каждого

компьютера ^=10 сут., а среднее время восстановления одного компьютера ^ =0.1 сут.

Тогда интенсивность отказов одного компьютера будет равна:

а интенсивность восстановления одного компьютера:

т = — = — = 10 (1/сут). 0.1

В состоянии 51 работают оба компьютера, следовательно: 1 = 21 = 2 • 0.1 = 0.2 (1/сут). В состоянии 52 работает один компьютер, значит: 123 =1 = 0.1 = 0.1 (1/сут).

В состоянии 52 восстанавливается один компьютер, тогда: т21 =м =10 (1/сут).

В состоянии 5 3 восстанавливаются оба компьютера: м32 = 2 т = 20 (1/сут).

Найдем вероятность состояния, когда обе машины исправны:

Р = 1 + 1 + Ц = 1 + 02 + 0.2 • 0.1 = 1 + 0.02 + 0.0004 = 098. Ми М21М32 10 10 • 20

Найдем вероятность второго состояния 52 (работает один компьютер):

р2 =1 • р = 0.02 • 0.98 = 0.0196.

Аналогично вычисляется и р3. Хотя найти р3 можно и так: р3 = 1 - (р1+р2) = 1 - (0.98 + 0.0196) = 1 - 0.9996 = 0.0004 Пример 3

Работа системы обслуживания клиентов, состоящей из двух работающих касс, задается графом состояний, изображенным на рис. 5.

Здесь состояние - обе кассы работают; 52 - первая касса не обслуживает, а вторая -обслуживает; 53 - обслуживает только первая касса; 54 - обе кассы не обслуживают. Интенсивности переходов задаются величинами: 11= 2, М= 1, 1= 3, М2= 2, 13= 3, ц3 = 3. Составить систему уравнений Колмогорова при заданных параметрах. Решение

Система уравнений Колмогорова в соответствии с вышеизложенным правилом будет иметь вид:

^ = -т + т) Рх +Ар2 +1 Рз, Шг

-(Л +1 +1з) Р2 +№Рх +№ Рз + №2 Р4,

Шр Шг

Шр3 = -(Л2 + №з + Л1) Рз + №2 Рх + Л3 Р 2 +№хР 4 ,

= -(№ + №2) Р4 + Л Рз + Л2 Р2 •

Рис. 5. Граф состояний.

Учтем, что рх + р2 + рз + р4 = 1, выразим отсюда р 4 и подставим в

систему, при этом можно не учитывать последнее уравнение. Получим систему из трех уравнений с

тремя неизвестными.

ШРх =_ Шг

ШР2 = Шг Шр

-(№х + №) Рх +Л Р 2 + Л2 Рз,

-(Л1 + Л2 + Лз) Р2 + № Р1 + №з Рз + №(1 - Р1 - Р 2 - Рз X

"Г^ = (Л2 + №з + Лх)Рз + №2Рх + ЛзР2 +№(1 - Рх - Р2 - Рз). Шг

При заданных интенсивностях система примет вид:

^ = -з рх + 2 Р2 + з рз,

ШР2 Шг

-2 Рх-10 Р2 + Рз + 2

Рис. 6. Граф состояний.

^ = Р1 + 2 Р2 - 9 Рз +1.

Пример 4

Работа системы, состоящей из двух независимо работающих приборов, задается графом состояний, изображенным на рис. 6. Здесь состояние £х - оба приборы исправны и работают; S2 - первый прибор вышел из строя, а второй - исправно работает; £з - второй прибор вышел из строя, а первый - исправно работает; £4 - оба прибора вышли из строя. Интенсивности переходов задаются величинами: Лх= 2, № = 1, Л2= з, №2= 2. Найти финальные вероятности для системы £.

Решение

Система алгебрических уравнений, описывающих стационарный режим данной системы, имеет вид:

(№ + №) Рх =Л Р2 +Л2 Рз, (Л +Л) Р2 =№х Рх +№2 Р4, (Лх + Л2 )Рз =№хР4 +№2Рх, (№ + №)Р4 = Л1 Рз +Л2 Р2 .

Учтем, что рх + р2 + рз + р4 = 1. Выражаем р4, подставляем в систему, при этом можно не учитывать последнее уравнение. Получим следующую систему: (№ +№) Рх =ЛР2 +Л2 Рз, (Л1 +Л) Р2 = №Рх + №(1 - Рх - Р2 - Рз X (Л1 +Л2)Рз = №(1 - Рх - Р2 - Рз) + №2Рх. При заданных интенсивностях система примет вид:

Решив систему уравнений, получим Р1= 0.31, Р2= 0.19, Р3 = 0.19, Р4= 0.31. То есть в предельном стационарном режиме система 5 в среднем 31% времени будет находиться в состоянии (оба приборы исправны и работают), 19% - в состоянии 52 (первый прибор вышел из строя, а второй - исправно работает), 19% - в состоянии 53 (второй прибор вышел из строя, а первый исправно работает), 31% - в состоянии 54 (оба прибора вышли из строя).

Заключение

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

Математическая дисциплина, изучающая модели реальных систем массового обслуживания, получила название теории массового обслуживания. Задача теории массового обслуживания -установить зависимость результирующих показателей работы системы массового обслуживания (вероятности того, что требование будет обслужено; математического ожидания числа обслуженных требований и т.д.) от входных показателей (количество приборов в системе, параметров входящего потока требований и т.д.). Установить такие зависимости в формульном виде можно только для простых систем массового обслуживания. Изучение же реальных систем проводится путем имитации, или моделирования их работы на ЭВМ с привлечением метода статистических испытаний [2-6].

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

В дальнейшем планируется не только составить уравнения Колмогорова, но и решить их с помощью ППП МаЙаЬ для задачи моделирования транспортного потока на нерегулируемом пересечении. А также вычислить основные характеристики: средние длины очередей, вероятность не застать мест для ожидания в очереди, среднее время ожидания в очереди. И провести анализ характеристик при различных значениях интенсивности.