Численно-аналитические модели массового обслуживания с равномерными законами распределения
Журнал: Инфокоммуникационные технологии @ikt-psuti
Рубрика: Теоретические основы технологий передачи и обработки информации и сигналов
Статья в выпуске: 1 (93) т.24, 2026 года.
Бесплатный доступ
Статья является логическим продолжением [1] по изучению систем массового обслуживания (СМО), сформированных равномерными законами распределения вероятностей. В [1] было продемонстрировано, что стандартный подход с использованием спектрального разложения решения уравнения Линдли не позволяет получить точного аналитического решения для таких систем. С учетом того факта, что равномерный закон всем известный закон теории вероятностей и играет большую роль в имитационном моделировании, получение такого решения закрыло бы пробел в теории массового обслуживания. Поэтому было принято решение о получении приближенного (аппроксимативного) решения для среднего времени ожидания в очереди сведением задачи от интегрального уравнения Линдли к уравнению Фредгольма второго порядка. В источниках по имитационному моделированию в дискретно-событийной системе GPSS WORLD для моделирования систем массового обслуживания, наоборот, много примеров моделей СМО с равномерным законом распределения. Сравнение полученных результатов по приближенной численно-аналитической модели с данными имитационного моделирования по трудоемкости явно свидетельствует в пользу второго подхода. Видимо этот факт во многом объясняет отсутствие аналитического решения по таким системам в теории массового обслуживания.
Короткий адрес: https://sciup.org/140316410
IDS: 140316410 | УДК: 621.391.1: 621.395 | DOI: 10.18469/ikt.2026.24.1.01
Numerical and analytical queue service models with uniform distribution laws
The article is a logical continuation of [1] on the study of queuing systems (QS) formed by uniform probability distribution laws. In [1] it was demonstrated that the standard approach using spectral decomposition of the solution of the Lindley equation does not allow one to obtain an exact analytical solution for such systems. Considering the fact that the uniform law is a well-known law of probability theory and plays a major role in simulation modeling, obtaining such a solution would close the gap in queueing theory. Therefore, a decision was made to obtain an approximate solution for the average waiting time in a queue by reducing the problem from the Lindley integral equation to a secondorder Fredholm equation. In the sources on simulation modeling in the discrete-event system GPSS WORLD for modeling queuing systems, on the contrary, there are many examples of queuing system models with a uniform distribution law. A comparison of the results obtained using the approximate numerical-analytical model with the simulation data on labor intensity clearly indicates in favor of the second approach. Apparently, this fact largely explains the lack of an analytical solution for such systems in queuing theory.
Текст научной статьи Численно-аналитические модели массового обслуживания с равномерными законами распределения
Настоящая статья является логическим продолжением работы [1]. Рассмотрим систему массового обслуживания (СМО), сформированную двумя функциями плотности равномерного закона распределения на интервалах ( a , b ) и ( c , d ) . При этом интервалы между поступлениями требований тх е ( a , b ) , а случайные времена их обслуживания тц е ( c , d ) . Сами функции плотности имеют вид:
0, t < a ,
a х( t ) = О/ (b - a), a < t < b,
0, t > b ,
0, t < c ,
bц(t) = <1/(c — d), c< t < d,
. 0, t > d .
Условие существования установившегося режима функционирования такой системы в виде ограничения на коэффициент загрузки системы 0 < p = т^Т < 1 приводит к неравенству (c + d)/2 <( a + b)/2, что равносильно условию c + d a + b
< 1. В [1] для получения решения для такой системы был использован метод спектрального разложения [2] интегрального уравнения Линдли вида:
W (y ) = J IW(y- u)dC (u), y - 0,
0, y < 0.
Здесь W ( y ) - функция распределения вероятностей (ФРВ) времени ожидания требования в очереди,
C ( u ) = P ( u < u ) - ФРВ случайной величины й = x - t , где x - случайное время обслуживания требования, t - случайная величина - интервал времени между поступлениями требований. Уравнение (1) широко используется во многих сферах научных исследований [1, 2, 12, 13].
Это уравнение не позволило получить ни точного, ни приближенного решения. В то же время в научных публикациях по теории массового обслуживания, включая обширную литературу по ней, нельзя увидеть факты об использовании равномерного закона распределения вероятностей (uniform distribution law) [2‒6] и др.
Наоборот, в имитационном моделировании в большинстве источников по дискретнособытийному моделированию, в системе GPSS WORLD [7–10], сплошь и рядом используются имитационные модели СМО с равномерным законом распределения. В них используется хорошо зарекомендовавший себя стандартный генератор последовательности псевдослучайных чисел U [ 0,1 ] , распределенных по равномерному закону, являющийся основой моделирования случайных последовательностей по любому закону распределения. Для этого используются известные алгоритмы получения псевдослучайных последовательностей на основе генератора U [ 0,1 ] , поэтому генератор U [ 0,1 ] и играет фундаментальную роль в имитационном моделировании.
Постановка и решение задачи
В статье ставится задача получения прибли- женного решения для среднего времени ожидания требований в очереди в СМО с равно- мерными законами распределения интервалов поступлений и времени обслуживания. Для этого используем вторую форму интегрального уравнения Линдли [2] в виде:
то
W ( У ) = “
j C ( y - 1 ) dW ( t ) , y > 0
0 —
0, y < 0
В выражениях (1) и (2) сохранены исход- ные обозначения автора [2].
ядро уравнения C ( y - w ) то
В выражении (2) определяется как
C (u )= j B (u +1)■ dA (t). В [2] отмечено, что это t =0 / \ почти свертка ФРВ времени обслуживания B (t) и функции плотности интервалов поступлений aA (t), т.к. C (u ) = P(й < u) здесь функция распределения вероятностей случайной величины в виде разности u = x -1 , а не суммы.
Если же использовать свертку, то тем самым в данном случае в построение математической модели будет внесена некоторая погрешность.
Сведение уравнения Линдли к уравнению
Фредгольма
Уравнение Линдли (2) продифференцируем по y и придем к уравнению вида:
то
w ( У ) = Р 0 C '( У ) + j C '( У — x ) w ( x ) dx , (3)
здесь w ( y ) = W '( y ) - функция плотности распределения времени ожидания, p 0 – вероятность того, что в системе нет требований, а C ‘ - ядро уравнения Фредгольма, определяемое двумя функциями плотности равномерного распределения: то
C '( u ) = c ( u ) = j b ^ ( u + 1 ) ■ a z ( t ) dt . (4)
0 -
Перепишем (3) с использованием функции плотности C '( u ) = c ( u ) : то
w ( У ) = Р 0 c ( У ) + j c ( У - x ) w ( x ) dx . (5)
К уравнению (5) необходимо добавить условие нормировки:
то j w ( x ) dx + p 0 = 1 . (6)
Интегральное уравнение (5) относительно функции плотности времени ожидания является неоднородным уравнением Фредгольма второго порядка. Теперь необходимо решить промежуточную задачу определения композиции двух равномерных законов в виде функции ядра уравнения Фредгольма c ( u ) , где U - случайная величина в виде разности двух величин Y - T , а Y - равномерно распределена на [ c , d ] , T - на отрезке [ a , b ] . Если бы здесь была сумма двух случайных величин, c ( u ) была бы сверткой. Функция плотности c ( u ) будет непрерывной кусочно-линейной функцией вида (7) в зависимости от расположения интервалов [ a , b ] и [ c , d ] на числовой оси относительно друг друга [11]:
График этой функции представляет собой трапецию на отрезке [ c - b , d - a ] . В частном случае, когда ( b - a ) = ( d - c ) функция c ( u ) превращается в треугольное распределение Симпсона.
Аналитическое решение уравнений (5) и (6) с учетом ядра в виде (7) в общем случае возможно с применением теории операционного исчисления с использованием преобразования Лапласа, но это очень трудоемкий процесс. Поэтому в данной статье использован подход с дискретизацией уравнения (5) и сведением ее к системе линейных
0, u < c - b
c ( u ) = 7 A---- т ( b - a )( d - c )
u - ( c - b ) , c - b < u < min ( c - a , d - b )
min ( b - a , d - c ) , min ( c - a , d - b ) < u < max ( c - a , d - b ) . ( d - a ) - u , max ( c - a , d - b ) < u < d - a
0, u > d - a
алгебраических уравнений. Это удобно с точки зрения расчета среднего времени ожидания в очереди для конкретных примеров.
Численное решение уравнения Фредгольма
Для численного решения уравнения Фредгольма могут быть использованы метод итерационных приближений и метод дискретизации сведением к системе линейных алгебраических уравнений.
Численное решение уравнения Фредгольма (5) сведением к системе линейных алгебраических уравнений включает два этапа.
Первый этап включает организацию вычисления компонент вектора ядра c ( u ) = c ( у- - t j ) для всех возможных значений аргумента u = y i - t j . Например, на языке Python это будет def c ( u, a, b, c, d ) . Как видно из уравнения (5), ядро c ( u ) является функцией плотности случайной величины в виде разности U = Y - T , где Y - равномерно распределена на [ c , d ] , T - на отрезке [ a , b ] . На втором этапе формируются матрица коэффициентов A { a ij } и вектор свободных членов B { b i } системы уравнений вида:
Ax=B ,
где A = A { a ij } - матрица размерности ( n + 1 ) х ( n + 1 ) , n - размер дискретизации, x - искомый вектор значений функции плотности w ( у ) , B = B { b i } – вектор свободных членов.
Распишем компоненты матричной формы системы уравнений (8). Вектор неизвестных x = [ w 1 ,w2,...,wn , p 0 ] . Уравнения для функции плотности w ( у ) в узлах ( i = 1,2,..., n ) :
w ( yi )- hXc ( yi - yJ ) w ( yJ ) - p 0 c ( у - ) = 0 , (9) j =1
а уравнение для условия нормировки:
n h Ё w (y-)+p о=1. (10)
j =1
Для решения этой системы уравнений Ax =B используем стандартную программу NumPy на языке Python с подключением программы – функции c ( u, a, b, c, d ) .
После вычисления искомого вектора значений функции плотности времени ожидания w(у) остается определить численное значения инте-то грала W = | у ■ w (у) dy для получения среднего времени ожидания требований в очереди W .
Результаты численных расчетов по программе можно продемонстрировать только на конкретных примерах.
Результаты вычислительного эксперимента по расчету среднего времени ожидания
Пример 1. Пусть случайная величина т ^ интервала между поступлениями равномерно распределена на отрезке [ 0,5, 1,5 ] и случайные времена обслуживания тц также равномерно распределены на отрезке [ 0,4, 1,4 ] . Это обеспечивает коэффициент загрузки системы:
c + d
Р =----- = 0,9.
a + b
В этом случае в выражении (7) длины отрезков равны ( b - a ) = ( d - c ) и функция плотности c ( u ) композиции двух равномерных распределений принимает вид треугольного распределения Симпсона с центром в точке -0,1:
0, и < - 1,1
c ( и ) = ‘
и + 1,1, - 1,1 < и < - 0,1 0,9 - и , - 0,1 < и < 0,9
0, и > 0,9
Площадь под графиком функции плотности c ( и ) равна единице, и, следовательно, выражение (7) определено правильно.
Теперь для численного решения используем вышеупомянутые программы Python. Зададим шаг дискретизации h = 0,1 на интервале для w от нуля до четырех [ 0, 4 . Тогда размерность системы будет равна n = 41. Программа определяет вероятность отсутствия требований в системе p 0 = 0,305, а среднее время ожидания требований в очереди W = 0,618 .
При шаге дискретизации h = 0,05 размерность системы будет равна n = 81. Программа определяет вероятность отсутствия требований в системе p 0 = 0,3061, а среднее время ожидания требований в очереди W = 0,6172.
Зададим шаг дискретизации h = 0,01 на интервале для w от нуля до четырех [ 0, 4 ] . Тогда размерность системы линейных уравнений (9) и (10) n = 401. Программа определяет вероятность отсутствия требований в системе p 0 = 0,3055, а среднее время ожидания требований в очереди W = 0,6186.
Пример 2. Немного изменим один интервал из примера 1. Пусть интервал между поступлениями требований останется прежним [ 0,5, 1,5 ] , а интервал для времени обслуживания сузим до [ 0,5, 1,3 ] , чтобы оставить коэффициент загрузки системы равным р = c + d/a + b = 0,9. В этом случае функция плотности c ( и ) и ее график представляет собой трапецию вида с константой, равной 1 на участке [ - 0,2, 0 ] :
0, u < - 1
1,25 ( u + 1 ) , - 1 < u <- 0,2
c ( u ) = <
1, - 0,2 < u < 0
1,25 ( 0,8 - u ) , 0 < u < 0,8
_ 0, u > 0,8
Заметим, что в этом случае интервал для времени обслуживания несколько уже, тогда и дисперсия времени обслуживания также уменьшится, что влечет за собой уменьшение среднего времени ожидания. Убедимся в сказанном. Возьмем шаг дискретизации h = 0,1 на интервале для w от нуля до четырех [ 0, 4 ] . В этом случае p 0 = 0,354, W = 0,518.
При шаге дискретизации h = 0,05 программа определяет p 0 = 0,3552, W = 0,5168, а при шаге дискретизации h = 0,01, p 0 = 0,3546, W = 0,5186.
По обоим примерам можем сделать следующий вывод: для начальной прикидки результатов вполне достаточно шага дискретизации h = 0,1. Для практических исследований СМО может потребоваться более мелкий шаг. Заметим, что относительная погрешность при шагах дискретизации h = 0,05 и h = 0,01 результаты отличаются только на долю процента.
Решение задачи с использованием имитационного моделирования
Для вышерассмотренного примера 1 возьмем имитационную модель GPSS WORLD из работы авторов [1]. Кода программы на GPSS WORLD в этом случае содержит всего восемь строк.
10 GENERATE 1,0.5
20 QUEUE QCHAN
30 SEIZE CHAN
40 DEPART QCHAN
50 ADVANCE 0.9,0.5
60 RELEASE CHAN
70 TERMINATE 1
80 START 1000000
На рис. 1 приведена небольшая часть стандартного отчета GPSS для этого примера. Здесь число испытаний в прогоне модели велико n = 1000000 , что отражает работу СМО в установившемся режиме.
Результаты имитации подтверждают полное их соответствие исходным данным модели. Основные интересующие нас результаты: среднее время ожидания в очереди W = 0,622 единиц времени, а средняя длина очереди N4 = 0,622. Сравнивая исходные данные для модели и выходные результаты, убеждаемся, что совпадения идеальные.
Пример 2. Имитационная модель для второго примера на GPSS WORLD также включает всего восемь строк. Здесь поведение модели также рассматривается в установившемся режиме.
10 GENERATE 1,0.5
20 QUEUE QCHAN
30 SEIZE CHAN
40 DEPART QCHAN
50 ADVANCE 0.9,0.4
60 RELEASE CHAN
70 TERMINATE 1
80 START 1000000
Часть стандартного отчета GPSS для этого примера приведена на рис. 2.
Результаты имитации этой модели также подтверждают полное их соответствие исходным данным модели. Основные интересующие нас результаты: среднее время ожидания в очереди W = 0,494 единиц времени, а средняя длина очереди Nq = 0,494. Совпадения опять идеальные.
Заключение
В статье представлены результаты исследований СМО, образованных двумя функциями плотности с равномерным законом распределения. В [1] было продемонстрировано, что для таких СМО метод спектрального решения для среднего времени ожидания требований в очереди не позволяет по-
CHAN 1000001 0.900 0.900 1 1000001 0000
QCHAN 10 1 1000001 299046 0.622 0.622 0.888 0
Рисунок 1. Отчет GPSS WORLD для примера 1
CHAN 1000001 0.900 0.900 1 1000001 0000
QCHAN 9 1 1000001 323661 0.494 0.494 0.731 0
Рисунок 2. Фрагмент стандартного отчета GPSS для примера 2
лучить аналитического решения. В данной работе представлены приближенные численно-аналитические модели для таких систем, которые позволяют получить решение с заданной точностью.
Сравнение полученных результатов с данными имитации на универсальном языке моделирования GPSS WORLD, показывает их примерно одинаковую точность, которую можно получить также примерно за одинаковое время.
В то же самое время сравнение результатов однозначно подтверждает удобство и простоту решения поставленной задачи на языке моделирования GPSS WORLD. Трудоемкость решения данной задачи сведением интегрального уравнения Линдли к уравнению Фредгольма, несомненно, на порядок и более выше по сравнению с имитационным моделированием.
