Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

COMPUTER MODELING OF QUEUING SYSTEMS WITH LIMITATIONS

Osipov G.S. 1
1 Sakhalin State University
A formal structure and a mathematical description of the functioning of single-channel and multi-channel Queueing system with a queue length limited are proposed. The derivation of formulas for calculating the average number of applications in the system is given. The formal structure of Queueing system with the possibility of early exit from the queue with a given intensity and a limit on the allowable time of stay of applications in the queue is developed. The mathematical model of systems functioning is described, the estimation from above for the remainder of the infinite series used for calculation of probability of idle time of channels is received. Practical approbation of theoretical material in the framework of computer and simulation modeling of Queuing systems is carried out. A fragment of a computer model in the environment of the Wolfram Mathematica symbolic mathematics package for a system with a known intensity of early Queuing is presented. The estimate of the effect of the value of the intensity of early withdrawal from the parameters of functioning of systems of mass service. The results of the study of the dependence of the probability of downtime of channels and the value of the residual term on the number of considered terms in its decomposition are presented. A study of systems with a limited waiting time with care by TimeOut in the environment of the simulation package AnyLogic. The structure of the simulation model is presented and the results of the experiment in the environment of the simulation package are presented.
queuing system
mathematical
computer and simulation modeling

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

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

Материалы и методы исследования

1. СМО с ограничением на длину очереди.

1.1. Одноканальные системы.

Рассмотрим одноканальную СМО, характризуемую следующими параметрами:

λ – интенсивнгость входящего потока заявок;

m – интенсивность обслуживания заявок в канале;

m – предельно допустимая длина очереди.

Диаграмма состояний одноканальной СМО с ограниченной длиной очереди может быть представлена следующим образом [1, 2]:

osip01.wmf

Состояния системы пронумерованы по числу заявок, находящихся в ней: S0 – канал свободен, заявок нет; osip02.wmf – канал занят, k заявок стоят в очереди.

Поток заявок переводит систему из состояния osip03.wmf в состояние Si+1 с интенсивностью λ, а обратно – поток обслуживания с интенсивностью μ.

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

Очевидно, предельные вероятности состояний определятся следующим образом [2, 3]:

osip04.wmf,

где osip05.wmf – коэффициент загрузки канала.

Из условия osip06.wmf получим вероятность простоя канала osip07.wmf.

Относительная пропускная способность (вероятность того, что заявка будет обслужена) и абсолютная пропускная способность (число заявок, обслуживаемых в единицу времени) определятся по следующим формулам: osip08.wmf.

Выведем формулу для вычисления среднего числа заявок в системе (длины очереди). Очевидно, суммирование будет осуществляться с состояния S2, когда в очереди одна заявка, до состояния S1+m, в котором m заявок стоят в очереди.

osip09.wmf

Выполнив элементарные преобразования, получим

osip10.wmf

Таким образом, длина очереди определится следующим образом:

osip11.wmf

1.2. Многоканальные системы.

Исследуем n-канальную СМО с ожиданием, на которую поступает поток заявок с интенсивностью λ; интенсивность обслуживания равна m (для одного канала); максимально допустимое число мест в очереди равно m.

Возможные состояния многоканальной СМО с ограничением на длину очереди могут быть представлены следующей структурой [2, 3]:

osip12.wmf

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

Выражения для предельных вероятностей состояний системы таковы:

osip13.wmf

В данном случае вероятность простоя каналов обслуживания при отсутствии заявок определится следующим образом:

osip14.wmf

Соответственно, определятся выражения для вероятности отказа в обслуживании (заняты все n каналов и длина очереди m) osip15.wmf, относительной пропускной способности системы osip16.wmf, абсолютной пропускной способности A = λQ, среднее число занятых обслуживанием каналов osip17.wmf.

Получим формулу для вычисления среднего числа заявок в системе (длины очереди). Суммирование будет осуществляться с состояния Sn+1, когда в очереди одна заявка до состояния Sn+m в котором m заявок стоят в очереди.

osip18.wmf

где osip19.wmf – интенсивность нагрузки канала.

Преобразуем полученное выражение:

osip20.wmf

Далее, выполнив дифференцирование суммы убывающей прогрессии со знаменателем φ, получим

osip21.wmf

Окончательно длина очереди найдется по следующей формуле:

osip22.wmf

2. СМО с ограниченной продолжительностью пребывания заявок в очереди.

Для формализации описания функционирования систем с ограниченным временем ожидания их также удобно представлять в виде структуры состояний [4], которая по сути является схемой гибели и размножения

osip23.wmf

Здесь введены следующие обозначения: osip24.wmf – число занятых каналов; r – число заявок, находящихся в очереди; ν – интенсивность уходящего из очереди (не дождавшись обслуживания) потока заявок.

Для систем с ограниченным временем ожидания предельные вероятности состояний определяются по следующим формулам (здесь osip25.wmf):

osip26.wmf

Исследуем формулу вероятности того, что система находится в состоянии S0 (все каналы свободны). Представим бесконечную сумму osip27.wmf в виде двух слагаемых, в первом учитывается конечное число q – 1 ее элементов, а второе (бесконечная сумма) – остаток.

osip28.wmf

Можно получить оценку остатка сверху:

osip29.wmf

Результаты исследования и их обсуждение

Проведем практическую апробацию моделирования, например, СМО с ограниченным временем ожидания на унифицированном примере: система состоит из n = 3 каналов, интенсивность входящего потока составляет λ = 4 заявки, интенсивность обслуживания на каждом из каналов μ = 2 заявки. На основании статистических данных известна интенсивность досрочного ухода заявок из очереди v.

Компьютерное моделирование осуществлялось в пакете символьной математики Wolfram Mathematica. Фрагмент реализации компьютерной модели при v = 0,1 приведен в табл. 1.

Таблица 1

Фрагмент компьютерной модели

Вероятность простоя

Число занятых каналов

Длина очереди

OS1T.tif

OS2T.tif

OS3T.tif

Использование пакета Wolfram Mathematica позволяет перенести в эту систему зависимости математической модели практически в исходном формальном представлении.

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

Таблица 2

Параметры функционирования СМО

Показатель

Режим

p0

Lоч

tоч

tСМО

Без досрочного ухода из очереди

0,111

0,889

0,222

0,722

Интенсивность ухода

v = 0,1

0,115

0,707

0,177

0,677

v = 0,2

0,118

0,605

0,151

0,651

v = 0,3

0,120

0,536

0,134

0,634

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

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

Результаты исследования зависимости вероятности простоя каналов и величины остатка R(q) от числа учитываемых членов в его разложении (при v = 0,1) приведены на рис. 1.

os1.tif

Рис. 1. Зависимость параметров от количества членов разложения

os2.tif

Рис. 2. Принципиальная схема модели

os3.tif

Рис. 3. Характеристики продолжительности пребывания заявок в СМО

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

Исследование систем с ограниченным временем ожидания c уходом по TimeOut осуществлялось в среде пакета имитационного моделирования AnyLogic. На рис. 2 представлена принципиальная схема модели в среде пакета имитационного моделирования.

На текущий период моделирования в систему поступило 37 заявок, из них 30 покинули СМО после обслуживания, 3 ожидают в очереди, 2 находятся на обслуживании в каналах и 2 покинули систему из-за превышения допустимого времени ожидания в очереди.

На рис. 3 приведены гистограммы распределения времени пребывания заявки в СМО без ограничений и при досрочном уходе из очереди в случае превышения этого времени на 1 (для ранее заданных интенсивностей входящего потока заявок и их обслуживания).

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

Выводы

Выполнен синтез математического описания функционирования систем массового обслуживания с ограничениями в виде:

– предельно допустимой для заявок длины очереди;

– заданной интенсивности досрочного ухода заявок из очереди без обслуживания;

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

Представленные в работе математические модели, формальные зависимости и оценки апробированы и подтверждены в результате компьютерного и имитационного экспериментов, выполненных на базе системы символьной математики Wolfram Mathematica и аналитической платформы AnyLogic.

Анализу систем массового обслуживания с другими дисциплинами очереди посвящены современные исследования, например, в публикациях [5, 6].