Анализ функционирующих в полумарковской среде RQ-систем с возвратом заявок

Размещено на http://www.allbest.ru/

Анализ функционирующих в полумарковской среде RQ-систем с возвратом заявок

Вавилов Вячеслав Анатольевич

кандидат физико-математических наук

доцент, кафедра программной инженерии, Национальный исследовательский Томский государственный университет



Аннотация

Объектом исследования данной работы являются RQ-системы (retrial queueing systems, системы с повторными вызовами) с простейший входящим потоком требований, ожиданием на орбите, возвратом заявок и функционированием в случайной (полумарковской) среде. Рассматриваемые системы являются моделями широкого класса реальных систем обслуживания, в которых заявка по завершении успешного обслуживания может покинуть систему навсегда или через некоторый промежуток времени вернуться в систему для повторного обслуживания. Примерами таких систем являются банки, где выплативший кредит клиент может повторно обратиться за новым кредитом, центры занятости, где клиенты могут обращаться повторно в поисках новой работы и т. п. Эффективность функционирования таких систем зависит от ряда факторов, характер влияния которых можно определить как случайный (случайная полумарковская среда). В данной работе проводится математическое моделирование изучаемого класса систем. Инструментом исследования рассматриваемых систем является математический аппарат теории массового обслуживания. Предложенная математическая модель RQ-систем с возвратом заявок в полумарковской среде исследуется методом асимптотического анализа марковизируемых систем. Научная новизна работы заключается в том, что впервые предложена математическая модель функционирующей в полумарковской среде RQ-системы с вызываемыми заявками и проведён её асимптотический анализ. Найдено асимптотическое среднее нормированного числа заявок в системе, величины отклонения от среднего, получена основная вероятностно-временная характеристика - плотность распределения вероятностей значений процесса изменения состояний системы.

Ключевые слова: система массового обслуживания, орбита, случайная среда, полумарковский процесс, метод асимптотического анализа, диффузионная аппроксимация, диффузионный процесс, цепь Маркова, переменные параметры, простейший поток заявок

система вызов орбита заявка



Основным средством исследования стохастических систем являются марковские процессы [1-7]. Марковские цепи накладывают определённые ограничение на исследуемые процессы, что обусловлено требованием перехода из одного состояния марковской цепи в другое в каждый единичный промежуток времени. Если же снять это ограничение и допустить произвольное распределение времени пребывания в данном состоянии, то получится полумарковский процесс [4-6, 8-11], являющийся обобщением марковских процессов.

Необходимость оптимизации сетей связи, математическими моделями которых являются системы массового обслуживания, привела к рассмотрению управляемых систем массового обслуживания [12-15]. По-другому такие системы называют системами с переменными параметрами. Таким системам посвящены работы Коротаева И. А. [16-21].

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

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

Можно рассматривать задачу, когда изменяются не только параметры входящего потока, но и параметры обслуживания. Такие системы принято называть системами массового обслуживания, функционирующими в случайной среде [24-25]. Впервые понятие система, функционирующая в случайной среде, появилось в работе [26].

Соответствующие исследования применительно не только к системам массового обслуживания, но и к сетям связи представлены в трудах Дудина А.Н. [27-30], Neuts M.P. [31], Sztrick J. [32], Takahashi H., Akimaru H. A [33]. Возможные значения параметров систем массового обслуживания связываются со значениями некоторого случайного процесса, который называют управляющим процессом. Изменения значений управляющего процесса приводит к изменению параметров функционирования системы.

В связи с тем, что получение точных выражений для вычисления требуемых вероятностно-временных характеристик является достаточно сложной задачей, возникло направление решения задач теории массового обслуживания с помощью асимптотических методов [10, 34-37]. Эти методы позволяют отойти от явной разрешимости с использованием диффузионных процессов.

В ряде работ при анализе систем массового обслуживания, функционирующих в случайной среде, применяется метод диффузионной аппроксимации. В этом случае задача сводится к анализу характеристик диффузионного процесса с изменяющимися в случайные моменты времени коэффициентами переноса и диффузии. Плотности распределения можно найти из системы дифференциальных уравнений Фоккера-Планка. Такой подход используется в [38-43].

Особый интерес в последнее время представляет исследование RQ-систем (retrial queueing systems, системы с повторными вызовами), которые являются адекватными моделями широкого класса технических и социально-экономических систем [43-50]. Так, например, в работе [44] приводится более семи сотен ссылок на работы данной направленности. Тем не менее, исследованию RQ-систем, функционирующих в случайной среде, уделяется недостаточно внимания. В наших работах представлены RQ-системы, где в качестве математической модели случайной среды рассмотрена цепь Маркова [46-47], полумарковский процесс [48-49], диффузионный процесс [50].

В данной работе предлагается математическая модель RQ-систем с возвратом заявок и функционированием в полумарковской среде, проводится асимптотическое исследование.

Рассмотрим RQ-систему, на вход которой поступает простейший с параметром л поток заявок. Прибор этой системы может находиться в одном из двух состояний: k =0, если он свободен; k =1, если он занят обслуживанием заявки. Заявка, заставшая в момент поступления прибор свободным, начинает обслуживаться с интенсивностью µ. Если в течение обслуживания этой заявки другие требования на прибор не поступают, то исходная заявка по завершении обслуживания покидает систему с вероятностью r или с вероятностью 1-r переходит на орбиту. Если в течение обслуживания одной заявки поступает другая, то поступившая заявка переходит на орбиту. Повторное обращение заявок к прибору из орбиты происходит после случайной задержки, продолжительность которой имеет экспоненциальное распределение с параметром г. Число заявок на орбите обозначим i .

Система функционирует в случайной среде. В качестве математической модели случайной среды рассмотрим полумарковский процесс s (t ) с непрерывным временем t , то есть такой дискретный случайный процесс, который принимает значения из конечного множества состояний s =1,2,...,S и для которого вложенная по моментам времени t n изменения состояний цепь s (t n) является Марковской. Времена пребывания этого процесса в различных состояниях являются условно независимыми случайными величинами, распределение вероятностей значений которых зависит лишь от номера состояния полумарковского процесса.

Для определения полумарковского процесса s (t ) зададим стохастическую матрицу одношаговых вероятностей p s1s2 переходов вложенной цепи Маркова



при этом будем полагать, что p ss=0.

Понятно, что

Также зададим набор функций распределения G s(x ) значений времени пребывания полумарковского процесса в s -м состоянии.

Влияние случайной среды на функционирование RQ-системы определяется зависимостью интенсивности µ обслуживания заявок от состояний s (t )=s случайной среды, то есть µ=µ(s ), а также зависимостью параметров л и г от состояний s (t )=s случайной среды, то есть л=л(s ), г=г(s ). Вероятность окончания обслуживания заявки на приборе за бесконечно малый промежуток времени Дt равна µ(s )Дt +o(Дt ). Вероятность поступления нового требования в систему за бесконечно малый промежуток времени Дt равна л(s )Дt +o (Дt ). Вероятность обращения заявки на прибор из орбиты за бесконечно малый промежуток времени Дt равна г(s )Дt +o (Дt ).

В силу свойств приведенной математической модели трехмерный случайный вектор {k (t ),i (t ),s (t )} изменения во времени состояний {k (t ),i (t )} RQ-системы и состояний {s (t )} математической модели случайной среды является полумарковским процессом.

Для исследования описанной математической модели марковизируем процесс {k (t ),i (t ),s (t )} методом дополнительной переменной. Введем переменную ж(t ), имеющую смысл длины интервала времени от момента t до момента смены текущего состояния случайной среды, тогда процесс изменения значений вектора {k (t ),i (t ),s (t ),ж(t)} является марковским процессом.

Обозначим P (k (t )=k ,i (t )=i ,s (t )=s , ж(t )<ж)=P k(i ,s ,ж,t ).

В любой момент времени должно выполняться условие нормировки

Для распределения P k(i ,s ,ж,t ) можно составить систему дифференциальных уравнений Колмогорова:

Обозначим г(s )= гу(s ) и перепишем данную систему в следующем виде



Систему (1) будем исследовать методом асимптотического анализа [40] в условиях большой задержки заявок на орбите г>0. Для этого в (1) выполним замены:

тогда получим

3. Исследование асимптотических средних характеристик

Под асимптотическими средними характеристиками RQ-систем с вызываемыми заявками, будем понимать распределение вероятностей R k(x ) состояний k канала и предельную функцию



имеющую смысл асимптотического среднего нормированного числа заявок в системе.

В системе (3) перейдем к пределу при е>0 и, полагая, что существуют конечные пределы

получим систему

Решение H k(y ,s ,ж,ф) системы (5) будем искать в виде

Тогда Q k(x ,s ,ж), имеющая смысл условного совместного распределения вероятностей состояний k канала и s среды при условии x (ф)=x определяется системой вида



и условием нормировки



Будем полагать, что Q k(x ,s ,ж) известны, если удается каким либо образом решить систему (7).

Далее покажем, что x =x (ф) является детерминированной функцией.

В системе (3) функции H k(y ±е,s ,ф,е) разложим в ряд по приращениям аргумента y с точностью до o (е), получим

Уравнения системы (9) просуммируем по k и по s , и при ж>? получим

Поделим на е обе части полученного уравнения, выполним предельный переход (4), учтём (6), получим

Учтём условие нормировки (8), обозначим

заметим, что R k(x ) имеет смысл распределения вероятностей состояний канала, получим



Поскольку производная плотности распределения H (y,ф) не может тождественно равняться нулю, следовательно, функция x =x (ф) является решением обыкновенного дифференциального уравнения

Получили, что x =x (ф) является детерминированной функцией.

4. Величины отклонения нормированного числа заявок в системе от среднего

Рассмотрим процесс

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

Обозначим

Будем искать решение H k(y ,s ,ж,ф,е) системы (3) в виде



Подставим в систему (9) разложение (13), учтём (7) и запишем полученную систему, сократив на все уравнения, в следующем виде

Будем искать решение системы (14) в следующем виде

Подставим (15) в (14) и представим систему в виде двух систем



Продифференцируем систему (7) по x , получим



Из последней системы с учётом системы (17) следует, что решение

системы (17) имеет вид

С учётом (18) и (15) разложение (13) примет вид

Теперь найдём вид функции H (y ,ф). Для этого функции в правой части системы (3) разложим в ряд по приращениям аргумента y с точностью до o (е2), получим. Сложим все уравнения системы (20) по k , получим



Подставим в полученную систему разложение функций H k(y ,s ,ж,ф,е) в виде (19), учтём обозначение (10), получим



Просуммируем уравнения системы (21) по s , выполним предельный переход при ж>?, воспользуемся условием нормировки (8), обозначением (10), также обозначим

учтём, что

Получим



В силу дифференциального уравнения (11) уничтожим в (23) слагаемые порядка o (е), поделим обе части полученного уравнения на е2, выполним преобразования, будем иметь

Получили уравнение Фоккера - Планка для плотности распределения вероятностей H (y ,ф) значений диффузионного процесса авторегрессии y (ф). Заметим, что коэффициент переноса уравнения (24) есть производная по x от правой части дифференциального уравнения (11). В силу обозначения (12) можно записать

Коэффициент диффузии с учётом (24) обозначим следующим образом



если выражение в правой части больше нуля.

Из (24) следует, что H (y ,ф) является плотностью распределения вероятностей диффузионного процесса y (ф), который удовлетворяет стохастическому дифференциальному уравнению

где w (ф) является стандартным процессом Винера, то есть y (ф) является процессом авторегрессии.

5. Плотность распределения вероятностей процесса изменения состояний RQ-системы

Используя предельные процессы x (ф) и y (ф) для достаточно малых значений параметра е, рассмотрим процесс z (ф)=x(ф)+еy , который аппроксимирует процесс изменения числа заявок в системе е2i (ф/е2) и покажем, что он является однородным диффузионным процессом.

Дифференцируя z (ф) по ф получаем dz (ф)=x '(ф)d ф+еdy .

В силу (11) и (12) имеем

Так как правая часть содержит разложение в ряд по приращениям еy аргументаx, то можно записать



С точностью до o (е), имеем

Обозначим F (z ,ф) плотность распределения вероятностей значений процесса z (ф), тогда можно записать уравнение Фоккера - Планка для плотности этого процесса

Рассмотрим функционирование процесса z (ф) в стационарном режиме, то есть F (z ,ф)=F (z ), тогда стабильное распределение можно найти из уравнения Фоккера - Планка

Уравнение (29) является однородным дифференциальным уравнением второго порядка и имеет решение:



Таким образом, в данной работе предложена математическая модель функционирующей в полумарковской среде RQ-системы с вызываемыми заявками. Методом асимптотического анализа [8] получено обыкновенное дифференциальное уравнение (11), определяющее асимптотическое среднее x =x (ф) нормированного числа заявок в системе. Представлено распределение R k(x ), k =0,1, вероятностей состояний прибора в виде (10), где величины Q k(x ,s ,ж), k=0,1, имеющие смысл условного совместного распределения вероятностей состояний k канала и состояний sполумарковской среды, определяются системой уравнений вида (7). Показано, что процесс y (ф), характеризующий изменение величин отклонения нормированного числа заявок в системе от их асимптотического среднего, является диффузионным процессом авторегрессии и определяется стохастическим дифференциальным уравнением вида (27). Показано, что для достаточно малых значений параметра е процесс z (ф)=x (ф)+еy , является однородным диффузионным процессом. Найдена важнейшая вероятностно-временная характеристика процесса z (ф) - плотность распределения вероятностей его значений в виде (30).



Библиография

1. Баруча-Рид А. Г. Теория марковских процессов и ее приложения. - М.: Наука, 1969. - 511 с.

2. Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. - М.: Наука, 1987. - 336 с.

3. Жожикашвили В. А., Вишневский В. М. Сети массового обслуживания. Теория и применения к сетям ЭВМ. - М.: Радио и связь, 1988. - 192 с.

4. Клейнрок Л. Теория массового обслуживания. - М.: Машиностроение, 1979. - 432 с.

5. Матвеев В. Ф.; Ушаков В. Г. Системы массового обслуживания. - М.: Изд-во МГУ 1984. - 240 с.

6. Саати Т. Элементы теории массового обслуживания и ее приложения. - М.: Сов. радио, 1971. - 520 с.

7. Франкен П., Кениг Д., Арндт У., Шмидт Ф. Очереди и точечные процессы: Пер. с англ. - Киев: Наукова думка, 1984. - 284 с.

8. Апанасович В. В., Коледа А. А., Чернявский А. Ф. Статистический анализ случайных потоков в физическом эксперименте. - Минск: Университетское, 1988. - 254 с.

9. Башарин Г. П., Бочаров П. П., Коган Я. А. Анализ очередей в вычислительных сетях. Теория и методы расчета. - М.: Наука, 1989. - 336 с.

10. Боровков А. А. Асимптотические методы в теории массового обслуживания. - М.: Наука, 1980. - 210 с.

11. Джевелл В. С. Управляемые полумарковские процессы // Кибернетический сборник. - М.: Мир, 1967. Вып. 4. - С. 97-137.

12. Головко Н. И., Коротаев И. А. Приближенный расчет средней длины очереди в системах массового обслуживания с переменной интенсивностью входящего потока // Управляемые системы массового обслуживания. - Томск, 1986. Вып. 4. - С. 28-34.

13. Коротаев И. А. Системы массового обслуживания с переменными параметрами. - Томск: Изд-во Том. ун-та, 1991. - 167 с.

14. Назаров А. А. Управляемые системы массового обслуживания и их оптимизация. - Томск: Изд-во Том. ун-та, 1984. - 234 с.

15. Рыков В. В. Управляемые системы массового обслуживания // Теория вероятностей. Математическая статистика. Теоретическая кибернетика, 1975. Т.12. С. 43-154.

16. Головко Н. И., Коротаев И. А. Анализ некоторых систем массового обслуживания с переменной интенсивностью входящего потока // Поиск сигнала в многоканальных системах. - Томск, 1987. Вып. 2. - С. 65-76.

17. Головко Н. И., Коротаев И. А. Время задержки сообщения в узле сети при переменной интенсивности входящего потока // Автоматика и вычислительная техника, 1989. №2. С. 36-39.

18. Головко Н. И., Коротаев И. А. О времени задержки сообщения в узле сети при переменной интенсивности входящего потока // Вычислительные сети коммутации пакетов. Рига: ИЭВТ, 1987. Т.1. С. 107-111.

19. Коротаев И. А. Системы массового обслуживания с переменными параметрами. - Томск: Изд-во Том. ун-та, 1991. - 167 с.

20. Коротаев И. А. Приближенный расчет средней длины очереди в адаптирующихся системах массового обслуживания с переменной интенсивностью обслуживания // Управляемые системы массового обслуживания. - Томск, 1984. Вып. 3. С. 50-57.

21. Коротаев И. А., Терпугов А. Ф. Приближенный расчет характеристик адаптирующихся многолинейных систем массового обслуживания со вспомогательными приборами // Автоматика и вычислительная техника, 1982. №6. - С. 61-65.

22. Каспарсон В. А. Об обслуживании пуассоновского потока требований со случайной интенсивностью // Известия АН СССР. Техническая кибернетика, 1969. №6. С. 52-57.

23. Kingman J. F. On doubly stochastic Poisson process // Proceedings of Cambridge Philosophical Society. 1964. Vol. 60. #4. P. 923-930.

24. Дудин А. Н., Клименок В. И. Расчет характеристик однолинейной системы обслуживания, функционирующей в Марковской синхронной случайной среде // Автоматика и телемеханика, 1997. № 1. С. 74-84.

25. Коган Я. А., Литвин В. Г. К вычислению характеристик системы массового обслуживания с конечным буфером, работающей в случайной среде // Автоматика и телемеханика, 1976. № 12. С. 49-57.

26. Purdue P. The M/M/1 queue in a Markovian environment // Operations Research, 1974. Vol. 22. #3. P. 562-569.

27. Дудин А. Н. Об обслуживающей системе с переменным режимом работы // Автоматика и вычислительная техника, 1985. №2. С. 27-29.

28. Дудин А. Н., Клименок В. И. Расчет характеристик однолинейной системы обслуживания, функционирующей в Марковской синхронной случайной среде // Автоматика и телемеханика, 1997. № 1. С. 74-84.

29. Дудин А. Н. Оптимальное гистерезисное управление ненадежной системой BMAP/SM/1 с двумя режимами работы // Автоматика и телемеханика, 2002. №11. С. 58-73.

30. Dudin A. N. About queuing system operating in the random environment // Izvestia of USSR Academy of Sciences. Technical Cybernetics, 1985. С. 64-78.

31. Neuts M. P. Further results of the M/M/1 queue with randomly varying rates // Opsearch. 1978. Vol. 15. #4. P. 139-157.

32. Sztrick J. On the heterogeneous M/G/N blocking system in a random environment // Journal of Operations Research Society. 1987. Vol. 38. #1. P. 57-63.

33. Takahashi H., Akimaru H. A diffusion model for queues in a randomly varying environment // The Transactions of The IECE of Japan. 1986. Vol. E69. #1. P. 13-20.

34. Анисимов В. В., Закусило О. К., Донченко В. С. Элементы теории массового обслуживания и асимптотического анализа систем. - Киев: Вища школа, 1987. - 248 с.

35. Добрушин Р. Л., Прелов В. В. Асимптотический подход к исследованию сетей коммутации сообщений линейной структуры с большим числом узлов // Проблемы передачи информации. - 1979. Т.15. №1. - С. 61-73.

36. Коган Я. А., Нерсесян С. Г. Асимптотические методы анализа замкнутых сетей в условиях большой загрузки // Автоматика и телемеханика, 1984. №8. - С. 93-103.

37. Назаров А. А. Асимптотический анализ многолинейных систем массового обслуживания с повторными вызовами // Автоматика и вычислительная техника, 1990. №3. С. 65-71.

38. Коган Я. А., Литвин В. Г. К вычислению характеристик системы массового обслуживания с конечным буфером, работающей в случайной среде // Автоматика и телемеханика, 1976. №12. С. 49-57.

39. Kogan Ya. A., Litvin V. G. Piesewise diffusion approximations for queuing problems with heterogeneous arrivals and service // Problem of Operation and Theory Information, 1979. Vol. 8. #5-6. P. 133-143.

40. Назаров А. А., Моисеева С. П. Метод асимптотического анализа в теории массового обслуживания. - Томск: Изд-во НТЛ, 2006. - 112 с.

41. Гарайшина И. Р., Моисеева С. П., Назаров А. А. Методы исследования коррелированных потоков и специальных систем массового обслуживания. - Томск: Изд-во НТЛ, 2010. - 204 с.

42. Моисеев А. Н., Назаров А. А. Бесконечнолинейные системы и сети массового обслуживания. - Томск: Изд-во НТЛ, 2015. - 240 с.

43. Пауль С. В., Назаров А. А., Анализ RQ-системы M/GI/GI/1/1 с вызываемыми заявками, ненадёжным прибором и дообслуживанием прерванных заявок // Информационные технологии и математическое моделирование (ИТММ-2018): Материалы XVII Международной конференции имени А. Ф. Терпугова (10-15 сентября 2018 г.) - Томск: Изд-во НТЛ, 2018. - С. 139-145.

44. Artalejo J. R., Gomez-Corral A. Retrial Queueing Systems: A Computational Approach. Springer, Heidelberg, 2008.

45. Вавилов В. А. Исследование одноканальной системы с повторными вызовами // Методы прогнозирования в технике и технологиях: сборник статей Международной научно-практической конференции (г. Тюмень, 20 февраля 2018 г.). В 2 ч. Ч. 2. - Уфа: Аэтерна, 2018. - С. 6-13.

46. Вавилов В. А. Исследование немарковских RQ-систем, функционирующих в случайной среде // Современные концепции научных исследований: ежемесячный научный журнал. - М.: ЕСУ, 2014. - № 5 (13). - С. 56-59.

47. Вавилов В. А. Исследование RQ-систем в условиях возрастающего количества абонентских станций // Информационные технологии и математическое моделирование (ИТММ-2012): Материалы XI Всероссийской научно-практической конференции с международным участием (23-24 ноября 2012 г.) - Кемерово, 2012. Ч. 2. С. 80-85.

48. Вавилов В. А., Назаров А. А. Исследование RQ-систем в полумарковской среде // Международная конференция "Теория вероятностей и ее приложения", посвященная 100-летию со дня рождения Б. В. Гнеденко. - Москва: Ленанд, 2012. - С. 180-183.

49. Вавилов В. А. Исследование RQ-систем, функционирующих в полумарковской среде // Вестник Кемеровского госуниверситета. - Кемерово: Изд-во КемГУ, 2014. - № 3 (59). Т. 3. - С. 99-106.

50. Вавилов В. А. Математическое моделирование неустойчивых сетей случайного доступа в диффузионной среде при дважды стохастическом входящем потоке // Вестник Томского госуниверситета. Управление, вычислительная техника и информатика. Научный журнал. - Томск: Изд-во НТЛ, 2009. - № 2 (7). C. 31-51.

Размещено на Allbest.ru

...