Нестационарная пуассоновская модель непрерывно функционирующей системы обслуживания | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2020. № 52. DOI: 10.17223/19988605/52/12

Нестационарная пуассоновская модель непрерывно функционирующей системы обслуживания

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

Non-stationary Poisson model of continuously functioning queuing system.pdf Исследование нестационарных систем массового обслуживания связано с их применениями в вычислительных системах (см., напр.: [1]), развитием моделирования производственных процессов и связи, процессов торговли и бытового обслуживания (см., напр.: [2-4]). В этой связи следует упомянуть активно развивающиеся сейчас государственные программы «Умный город», «Цифровизация экономики» (см., напр.: [5-7]). Алгоритмы расчета нестационарных систем обслуживания являются достаточно сложными (см., напр.: [8, 9]). Поэтому требуется строить нестационарные модели обслуживания так, чтобы их расчет был бы достаточно простым и удобным для вычислений. В настоящей работе построены модели обслуживания, основанные на предположениях детерминированности времени пребывания заявок в системе, пуассоновости входного нестационарного потока и наличия бесконечного числа приборов, исключающих пребывание заявки в очереди. Системы обслуживания, удовлетворяющие этим условиям, можно назвать системами непрерывного действия, и в них пользователь в течение фиксированного времени получает требуемую услугу сразу после своего прихода. Подобный способ обслуживания очень удобен потребителю, так как не привязывает его к графику работы системы обслуживания, не требует задержки пользователя в очереди и поэтому вписывается, например, в программу «Умный город». Наряду с рассмотренными однофазными системами обслуживания в работе построены различные конвейерные системы обслуживания непрерывного действия: многофазные системы, древовидные системы и ациклические системы обслуживания непрерывного действия. Такие системы моделируют работу непрерывных транспортных линий (конвейеров), включенных в процесс маркировки, упаковки, сортировки и перемещения продукции в производственных логистических системах. Для исследования систем обслуживания непрерывного действия разработана специальная математическая техника, основанная на вероятностных расчетах и элементах теории графов. 1. Математическая модель системы обслуживания непрерывного действия Рассмотрим систему массового обслуживания с нестационарным пуассоновским входным потоком интенсивности t), t > 0, детерминированным временем а пребывания пользователя в системе. Обозначим n (t) количество пользователей в системе в момент t > 0. Полагаем, что интенсивность 98 Нестационарная пуассоновская модель непрерывно функционирующей системы обслуживания пуассоновского потока Ц(t), 0 < t < T, является непрерывной функцией времени t. Для удобства вычислений следует предположить, что Ц(t) = 0 при t < 0 и t > T. В этом случае число пользователей п (t) имеет пуассоновское распределение с параметром Л(? )=I X(x)d х. (1) Пусть в независимые случайные моменты времени Тк, к = 1,...,n, с непрерывными плотностями распределения pk(t), к = 1,...,п, наряду с этими заявками в систему приходят группы пользователей, количества которых независимы друг от друга, имеют пуассоновское распределение с параметрами Хк и не зависят от пуассоновского потока интенсивности X(t). Пребывание каждой такой группы строго регламентируется моментами Тк начала и Т^ + а окончания обслуживания. Тогда в момент времени t число пользователей в системе имеет пуассоновское распределение с параметром Л( t), удовлетворяющим равенству _ _ п Л(0=Г 4x)dx, Цх) = Цк) + ^Xkpk(t). (2) к=1 Так как функции X(t), pk(t), к = 1,...,n, непрерывны, то функция Л(t) непрерывно дифференцируема. Таким образом, построена модель массового обслуживания непрерывного действия. Замечание 1. Для сравнения заметим, что при допуске пользователей в фиксированные моменты времени функция Л(t) кусочно постоянна и время ожидания посетителей в очереди положительно. При этом в системе непрерывного действия время ожидания равно нулю. Предположим теперь, что имеется r независимых пуассоновских потоков с интенсивностями ЦДО,...,Цr(О, а детерминированное время обслуживания заявки j-го потока равно Рj, j = 1,...,r. Тогда число пользователей в системе в момент t имеет пуассоновское распределение с параметром r X Л(< ) = ZLy (x)dx. (3) j=1 Pj Замечание 2. Предложенная в этом разделе математическая модель системы обслуживания непрерывного действия основана на набюдениях за реально функционирующим спорткомплексом. Переход в этом комплексе к системе обслуживания непрерывного действия существенно улучшил качество обслуживания, сгладил нагрузку на систему в реальном времени и позволил пользователям не зависеть от переменчивой транспортной ситуации в городе. 2. Математическая модель ациклической сети обслуживания непрерывного действия В настоящем разделе рассматриваются различные сети обслуживания непрерывного действия: многофазная система, сеть с древовидной структурой, сеть с ациклической структурой. Такие сети могут возникнуть не только при обслуживании пользователей, но и в конвейерных системах обработки различных деталей. Многофазные системы обслуживания непрерывного действия. Рассмотрим га-фазную систему обслуживания c детерминированными временами а обслуживания на i-й фазе, i = 1,...,m. Пусть пуассоновский входной поток имеет непрерывную интенсивность X(t), 0 < t < Т, причем Ц(t) = 0 при t < 0 и t > Т. Тогда число пользователей п (t) на i-й фазе в момент времени t имеет пуассоновское распределение с параметром Л- (t )=i t-а -...-a / ч сх Ц(x)dx, 1 < i < m, Л1 (t)= I X(x)dx. -1-...-aj ' ’ Jx-aj (4) 99 Г.Ш. Цициашвили Сети обслуживания непрерывного действия с древовидной структурой. Предположим, что в корень 0 ориентированного дерева D поступает входной пуассоновский поток интенсивности Х(t) . Множество вершин K дерева D состоит из непересекающихся подмножеств K,l = 0,...,L, K0 = {0}. Заявка, окончив обслуживаться в узле к е Ki детерминированное время ак, с положительной вероятностью pkt перемещается в один из узлов множества К/+1. Обозначим Kk ,i+i £ Ki+i совокупность узлов множества Kl+1, куда могут переходить заявки из узла к е Kt с положительной вероятностью pk,t, t е Kk,l+1, ^ pkt = 1, причем Kk,l+1 Kk*,t+1 = 0, к,к* е K, к ф к*, следоваteKk ,l +1 тельно, в узел t е Kk і+1 могут переходить только заявки из узла к е K. Обозначим рк вероятность поступления заявки входного потока в вершину к е K и положим Тк - суммарное время пребывания заявки в сети до момента ее выхода из вершины к. Из определения сети с древовидной структурой следует, что из вершины 0 в вершину к е K существует единственный путь У к = {0, ^(1), 5(2),..., s(l -1), s(l) = к}, s(1) е Kr,..., s(l -1) е K _j, к е K , и значит выполняются равенства рк = p0,s(1) ' ps(1),s(2) '...' ps(l - 1),k, Tk = a0 + as (1) + as (2) + ... + as (l -1) + ak ■ (5) Используя формулу (4), получаем, что в момент времени t случайное число заявок в вершине к имеет пуассоновское распределение с параметром Ак (t )=Г I" pk 'k(y)d т. (6) JX-1s (l-1) Заметим, что пуассоновские случайные потоки, поступающие в вершины к е Kl, и, значит, пуассоновски распределенные случайные величины, характеризующие число заявок в вершинах к е Kt в момент t > 0, также независимы. Следовательно, если S £ Kl, то число заявок, находящихся в момент времени t в множестве вершин S имеет пуассоновское распределение с параметром Аs (t)=£Аk (t). (7) ksS Ациклические сети обслуживания непрерывного действия. Предположим теперь, что структура сети обслуживания непрерывного действия определяется ациклическим орграфом F с входной вершиной 0. Полагаем, что на множестве К вершин ациклического орграфа F определяется отношение частичного порядка между вершинами і у- j\\ если и только если в F существует путь из вершины / в вершину /. Пусть в множестве К вершина 0 является единственной максимальной в смысле порядка >- вершиной, и значит из нее можно провести путь в любую другую вершину. В [10] построен алгоритм вычисления максимальной (по числу ребер) длины L(i) пути из вершины 0 в любую другую вершину i. Множество K разбивается на непересекающиеся подмножества K0,K1,..,KL, по правилу Kt ={: L(i) = l}, l = 0,1,.,L. Причем любое ребро орграфа F идет из вершины множества i в вершину j, только если L(i) < L(j). Если L(j) _ L(i) = r > 1, то в ребро (i,j) можно ввести фиктивные вершины i1 е KL(i)+1,...,ir_1 е KL^r)+r_1. В результате дополненный фиктивными вершинами орграф, обозначим его F, как и орграф F, также является ациклическим. Действительно, при такой замене ребро (i, j) преобразуется в последовательность ребер, идущих одно за другим. Следовательно, в каждую вновь введенную вершину входит ровно одно ребро и из каждой вновь введенной вершины выходит ровно одно ребро. Поэтому доказательство ацикличности орграфа Fl можно проводить от обратного. Предположим, что переход из вершины i в следующую за ней фиктивную вершину j осуществляется с единичной вероятностью, а время пребывания заявки в фиктивной вершине j 100 Нестационарная пуассоновская модель непрерывно функционирующей системы обслуживания удовлетворяет равенству а]- = 0. Индукцией по L преобразуем орграф Fj в древовидный орграф F2. Если в вершину j орграфа F входит несколько ребер, то эту вершину делим на несколько вершин jj,...,js так, чтобы в каждую из них входило только одно ребро. Такое преобразование ациклического орграфа F в орграф F никак не меняет процесс обслуживания заявок, поскольку в сети нет задержек заявок в очередях перед обслуживанием. Следовательно, для древовидной сети F2 можно применить формулу (6). Причем в момент t > 0 случайные количества заявок в фиктивных вершинах j,..., js имеют пуассоновские распределения и являются независимыми, поэтому параметр этого распределения, задающего в момент t > 0 число точек в вершине j е F, вычисляется по формуле (7). Пример. Пусть ациклическая сеть обслуживания F состоит из вершин 0, 1, 3. Заявка входного потока обслуживается в вершинах 0, 1, 3 детерминированное время а0, а, а3 соответственно и с вероятностямиp0 j, p03, pj3, причем p0j + p03 = j, pj3 = j, переходит после обслуживания из одной вершины в другую. Преобразуем сеть F в сеть F , добавляя фиктивную вершину 2 между вершинами 1 и 3, при этом переходные вероятности p0 2 = p0 3, p2 3 = j, а время обслуживание в этой вершине а2 = 0. Далее преобразуем сеть Fj в сеть F2 , разделив вершину 3 на две вершины: 3.1, 3.2. Рис 1. Сеть F (слева), сеть F (по\\ середине), сеть F2 (справа) Fig. 1. Network F (left), Network Fi (in the middle), Network F 2 (right) Тогда параметры пуассоновского распределения числа заявок в вершинах сети F2 расчитываются по формулам Л0 (t) = Г т, Aj (t)= f_ а° аj p0,j^(x)dт, Л2 (t)= J p0,2^(T)dт, t a t a t а Л3Д (t ) = J 04 p0,j^(T)dт, Л3,2 (t )=| 04 p0,2k(T)dT Л3 (t ) = A3,j (t) + Л3,2 (t). ’ ' 7 И-Oq -a{~азі ’ ’ ' 7 И-a0 - - Заключение В настоящей работе построена математическая модель системы массового обслуживания непрерывного действия. В этой модели предполагается, что входной поток заявок является пуассоновским с меняющейся интенсивностью. Заявки сразу после своего поступления начинают обслуживаться. Время обслуживания является детерминированным. Данная модель вполне согласуется с наблюдениями за работой бассейна в спорткомплексе. Методы расчета такой системы существенно проще известных методов анализа систем массового обслуживания с меняющейся интенсивностью входного потока. Это позволяет обобщить данную модель на многофазные, древовидные и ациклические системы обслуживания конвейерного типа, встречающиеся в конвейерных системах обработки различных деталей. При таком обобщении используются как вероятностные методы, так и методы прикладной теории графов.

Ключевые слова

система массового обслуживания непрерывного действия, пуассоновский входной поток с меняющейся интенсивностью, многофазные, древовидные и ациклические системы обслуживания, queuing system, Poisson input flow with varying intensity, multiphase and tree-based service systems

Авторы

ФИООрганизацияДополнительноE-mail
Цициашвили Гурами ШалвовичИнститут прикладной математики Дальневосточного отделения РАНпрофессор, доктор физико-математических наук, главный научный сотрудникguram@iam.dvo.ru
Всего: 1

Ссылки

Горцев A.M. Адаптивное управление потоками задач в вычислительной системе // Автоматика и вычислительная техника. 1982. № 6. С. 53-60.
Догадина Е.П., Холкина Н.Е. Математическая модель функционирования производственных процессов с учетом их особенностей // Системы управления, связи и безопасности. 2016. Вып. 1. С. 1-9.
Дуплякин В.М., Княжева Ю.Н. Выбор закона распределения входного потока заявок при моделировании системы массо вого обслуживания торгового предприятия // Вестник Самарского госудаственного аэрокосмического университета. 2012. № 1 (37). С. 102-111.
Поршнев С.В., Корелин И.А. Исследование особенностей нестационарной одноканальной системы массового обслужива ния в разрезе числа обслуженных заявок // Cloud of Science. 2017. V. 3, Na 4. P. 366-374.
Greenfield A. Against the Smart City. London : Verso, 2013. 152 р.
Boyle D.E., Yates D.C., Yeatman E.M. Urban Sensor Data Streams: London 2013 // IEEE Internet Computing. 2013. V. 17, No. 6. P. 12-20.
Намиот Д.Е., Шнепс-Шнеппе М.А. Об отечественных стандартах для Умного города // Int. J. of Open Information Technologies. 2016. V. 4, No. 7. P. 3-36.
Ивницкий В.А. Теория сетей массового обслуживания. М. : Физматлит, 2004. 772 с.
Катрахов В.В., Рыжков Д.Е. Введение в функционально-аналитический метод в динамической теории массового обслу живания. Владивосток : Изд-во ДВГУ, 2004. 102 с.
Цициашвили Г.Ш., Осипова М. А. Стационарные потоки в ациклических сетях массового обслуживания // Дальневосточный математический журнал. 2016. Т. 16, № 2. С. 223-228.
 Нестационарная пуассоновская модель непрерывно функционирующей системы обслуживания | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2020. № 52. DOI: 10.17223/19988605/52/12

Нестационарная пуассоновская модель непрерывно функционирующей системы обслуживания | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2020. № 52. DOI: 10.17223/19988605/52/12