Численное исследование системы с гетерогенными серверами и рандомизированной А-политикой | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2020. № 53. DOI: 10.17223/19988605/53/3

Численное исследование системы с гетерогенными серверами и рандомизированной А-политикой

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

Numerical investigation of queue with heteregeneous servers and randomized N-policy.pdf Одним из основных допущений в классических моделях систем массового обслуживания (СМО) является то, что серверы являются идентичными. Однако это допущение плохо соотносится с действительностью, так как в реальных СМО серверы отличаются друг от друга по различным показателям, например по скорости обработки заявок, надежности, стоимости эксплуатации и т.д. В литературе СМО с неидентичными серверами получили название систем с гетерогенными серверами (Queue with Heterogeneous Servers, QHS). Такие системы часто встречаются при моделировании компьютерных и телекоммуникационных систем, так как в процессе их расширения приходится использовать гетерогенные компьютеры (серверы). Кроме компьютерных и телекоммуникационных систем серверы с различными скоростями встречаются в колл-центрах с многими операторами, которые имеют различные квалификации, а также в производственных системах, где в процессе обслуживания заявок участвуют не машины, а люди. Первая серьезная работа, посвященная изучению моделей QHS, описана в [1]. В ней изучается марковская СМО с бесконечной очередью, в которой для обслуживания заявок с равными вероятностями назначается один из свободных серверов (эта схема называется рандомизированным доступом). Предложен алгоритм вычисления стационарных вероятностей состояний системы, а также найдены формулы для нахождения среднего числа заявок в системе. Доказано, что из результатов данной работы в частных случаях получаются классические результаты для СМО с идентичными серверами. Анализ доступной литературы показал, что в подавляющем большинстве работ изучены проблемы расчета характеристик QHS, в которых приняты схемы рандомизированного [1-5] и упорядоченного доступа [6-14]. Обзор этих работ можно найти в [15, 16]. В QHS важными являются проблемы определения оптимальных стратегий доступа заявок, а также схем включения серверов в зависимости от текущего состояния системы. Отметим, что в целях оптимизации QHS зачастую используется FSF-схема доступа (Fast Server First), т.е. в момент поступления заявки для обслуживания всегда выбирается сервер, который имеет наивысшую скорость среди свободных серверов. Это объясняется тем, что вероятность потери в системе M/M/k/k имеет минимальное значение при использовании FSF-схемы доступа [17]. Однако FSF-схема доступа не всегда является оптимальной и даже субоптимальной для QHS с очередями. Так, в работе [18] доказано, что для QHS с неограниченной очередью оптимальной для минимизации среднего числа заявок в системе является N-политика. Согласно данной политике в двух серверных QHS быстрый сервер работает всегда, если в системе имеется хоть одна заявка, а медленный сервер включается лишь тогда, когда длина очереди достигает определенного (порогового) значения N. С использованием 25 А.З. Меликов, Э.В. Мехбалыева разных подходов этот результат доказан различными авторами (см., напр.: [19-24]). Справедливости ради отметим, что задачи оптимизации СМО с однотипными резервными серверами (homogeneous servers), в которых моменты включения и отключения резервных серверов зависят от длины очереди, были изучены еще в 70-е гг. прошлого века [25] (после выхода в свет этой монографии в русскоязычной литературе появилась серия публикаций на эту тему; заинтересованный читатель может найти их в интернет-ресурсах). В дальнейшем в работах [26-28] с помощью известного алгоритма Ховарда эти результаты были распростренены на системы с дополнительной структурой штрафов, а в работе [29] исследована система с повторными заявками в предположении, что интервалы между их поступлениями и длительности их обслуживания имеют распределения фазового типа. Обобщения этой схемы для моделей QHS с ненадежными серверами рассмотрены в [30, 31]. В настоящей работе изучается QHS с двумя гетерогенными серверами и предлагается рандомизированная N-политика включения медленного сервера, согласно которой при достижении длины очереди заявок величины N медленный сервер включается с определенной вероятностью, а с дополнительной вероятностью он остается в спящем режиме. Данная политика является обобщением классической N-политики. Кроме того, здесь предлагается численный метод нахождения стационарных вероятностей состояний системы, а также вычисляются характеристики системы с неограниченным и ограниченным размером буфера для ожидания заявок. Отметим, что время выполнения алгоритма реализации предложенного метода практически равно нулю. 1. Описание моделей и постановка задачи Рассмотрим QHS с неограниченным буфером для ожидания заявок, которая содержит два сервера: быстрый (F-сервер) и медленный (S-сервер). Здесь приняты следующие допущения: (i) В систему поступает пуассоновский поток идентичных заявок с интенсивностью X, причем эта величина не зависит от состояния серверов. (ii) Время обслуживания заявок в обоих серверах являются случайной величиной с показательной функцией распределения; средние времена обслуживания в F-сервере и S-сервере равны ц^-1 и ц-1 соответственно, при этом цр > . (iii) F-сервер всегда является активным, а S-сервер может включатся лишь тогда, когда длина очереди не меньше определенной пороговой величины N, N N, п' = п +1, к' = 0, Ха, если п > N, п' = п, к' = 1, , если п > 0, п' = п -1, к' = 0; - случаи (п ,і)е E : ГХ, q^,!),^', к')) = < Kf , Mr + Ks, если п' = п +1, к' = 1, если 0 < п < N, п' = п -1, к' = 1, если п > N, п' = п -1, к' = 1, если п < N, п' = п, к' = 0. (3) [Ks, Рис. 1. Граф переходов между состояниями системы Fig. 1. Graph of transitions between states of the systems Стационарную вероятность состояния (п,к)е E обозначим через p (п, к) . Условием существования стационарного режима является X < pF + . Основными характеристиками данной модели QHS являются среднее число заявок в системе (Ls), среднее время пребывания заявки в системе (Ws) и интенсивность включения S-сервера (RS) . Среднее число заявок в системе определяются как математическое ожидание соответствующей случайной величины, т.е. да і Ls =Z пХ Р (^ к) • (4) п=1 к=С Среднее время пребывания заявок вычисляется с помощью известной формулы Литтла: Ws = !Ls . (5) Поскольку S-сервер включается с вероятностью а , то если в момент поступления заявки число заявок в системе не меньше величины N, то интенсивность включения S-сервера вычисляется следующим образом: 27 А.З. Меликов, Э.В. Мехбалыева да RS = Ха Z Р (п,0). (6) n=N Для нахождения стационарных вероятностей состояний p (n, к) может быть использован метод производящих функций. Однако его применение связано с определенными методологическими и техническими трудностями из-за сложной структуры производящей матрицы изучаемой цепи Маркова. Поэтому рассмотрим приближенный метод расчета вероятностей состояний и характеристик системы, основанный на принципах фазового укрупнения состояний многомерных цепей Маркова [15, 16]. Применение этого метода в изучаемой системе является корректным, так как согласно нашим допущениям скорость работы F-сервера много больше, чем скорость работы S-сервера. Кроме того, предположим, что а : к = 0,1}. Приближенные значения вероятностей состояний р(п,к), (п.к) е И исходной модели определяются как [15, 16] р(п,к) = рк(п)ті(), (7) где рк (n) - вероятность состояния (п, к) внутри расщепленной модели с пространством состояний Ек, а п(< к >) - вероятность укрупненного состояния < к > eQ. Из соотношений (2) заключаем, что интенсивности переходов между состояниями расщепленной модели с пространством состояний Е0 определяются следующим образом: Х, если п < N, п' = п +1, q0 (п, п') = Ш1 - а), если п > N, п'= п +1, (8) pF, если п'= п - 1. Из (8) получаем, что если выполняется условие vF < 1 , где vF = X/pF , vF = (l - a) vF, то вероятности состояний расщепленной модели с пространством состояний Е вычисляются как (9) (n\\- Jv^p°(0)’ если 0 если n>N, (11) Численное исследование системы с гетерогенными серверами где Pj (0) определяется из условия нормировки, т.е. Pj (0) = N Sv n=0 F + v F ,N VFS 1-V \\-1 FS J Тогда, объединяя условия vf в укрупненное состояние < к’>. Указанные интенсивности переходов вычисляются следующим образом: » f N-1 Л n=N 401 =^а2 Po(n) = Яа[ 1 - Z Po(n) ; (13) N 410 = Ps S Pi (n) • n=0 (14) Следовательно, из (13) и (14) имеем я(< 0 >) = q10 , л(< 1 >) = 1 -я(< 0 >). , , , , (15) 401 + q10 Таким образом, с учетом соотношений (8)-(15) из (7) вычисляются приближенные значения вероятностей состояний. После стандартных преобразований определяется приближенное значение среднего числа заявок в системе: 1 м f N Ls ~Ел()S nPk (n )=л()p0 (°)| Snv f+(!-аГ^G (v f ) к=0 n=1 n=1 N (16) где G ( x ) = я()P1 (0)|SnvF +(1 + PF) G(vFS) xN+1 (( N +1) (1 - x) + x) (1 - x )2 Приближенное значение интенсивности включения S-сервера вычисляется как N-1 (17) RS « А,ал (< 0 >) Z Po (n) = А,а7т(< 0 >)І 1 - 0 Po (n) • Отметим, что разработанный приближенный подход может быть использован и для изучения модели QHS с ограниченным размером буфера. Так, пусть общая вместимость системы равна M, где M > N (т.е. размер буфера равен M- 1). С этой целью во второй строке формул (9) и (11) верхняя граница изменения параметра n (бесконечность) заменяется конечной величиной M. При этом соответствующим образом изменяются формулы для нахождения величин рк (0),к = 0,1, т.е. в данной модели QHS имеем Ро(0) = [ +(\\-ayN Z v" , n=0 n=N+1 1 ( ; Pi(°) = N n=0 ( P^ Pf ^N M Z *"fs n=N+1 \\ -1 (18) 7 Вероятности укрупненных состояний вычисляются по формулам (13)-(15). Далее из формулы (16) и (17) заключаем, что в данной модели QHS приближенные значения характеристик системы вычисляются так: (19) (20) 1 , ,м ls « s я()s пРк (n); к=0 n=1 M RS *А,атс(< 0 >) S Р0 (n) • n=N 29 А.З. Меликов, Э.В. Мехбалыева В данной модели QHS появляется новая характеристика - вероятность потери заявок (PB). Точное значение этой величины определяется как PB = (1 -а)p(M,0) + p(M,1) . (21) Среднее время пребывания заявок в данной системе вычисляется следующим образом: (22) 1 Х(1 - PB ) Исходя из (6) заключаем, что приближенное значение этой величины определяется так: PB * (1 -а)р0 (M)п(< 0 >) + Pl (M)п(< 1 >) . (23) 3. Численные результаты Рассмотрим результаты численных экспериментов для изучаемых моделей. Проводимые эксперименты имеют три цели: 1) оценить точность разработанных приближенных формул для расчета стационарных вероятностей состояний и характеристик изучаемых систем; 2) изучить зависимости характеристик системы от значений порогового параметра N и вероятности включения медленного сервера; 3) решить задачи нахождения оптимального значения порогового параметра N. Относительно первой цели отметим, что точность разработанных приближенных формул для расчета стационарных вероятностей состояний оценивается с помощью двух мер близости (подобие косинуса (24), евклидово расстояние (25)): N X p{n,k)p(n,k) (я,А)еЯ X (p(n,k))2 y(n,k )е E ( X (Нп’к))2 (.п,к)еЕ у 1 ’ 2 (24) INI 2 X! (р(п’к)~Р(п’к))2 (25) У(п,к)еЕ J Некоторые результаты для модели с неограниченным размером буфера показаны в табл. 1. Из этой таблицы видно, что во всех экспериментах значения нормы (24) практически равны 1, а значения нормы (25) находятся в приемлемых для инженерных расчетов пределах. Иными словами, эти результаты показывают, что стационарные вероятности состояний вычисляются с высокой точностью. Таблица 1 Оценка точности вычисления вероятностей состояний относительно различных норм близости для модели с бесконечным буфером; а = 0,3; N = 5 1 (№ ^s) Значения нормы 1 Ms) Значения нормы (24) (25) (24) (25) (40, 20) 0,959 0,181 (40, 20) 0,942 0,183 20 (45, 30) 0,981 0,145 25 (45, 30) 0,972 0,150 (50,35) 0,986 0,135 (50, 35) 0,979 0,143 (55,40) 0,989 0,126 (55, 40) 0,983 0,136 Сравнительный анализ результатов вычисления характеристик данной модели с применением различных подходов показан в табл. 2. Здесь и далее приняты следующие сокращения: ТЗ - точные значения, ПЗ - приближенные значения, ОП - относительная погрешность. 30 Численное исследование системы с гетерогенными серверами Т аблица 2 Оценка точности вычисления характеристик модели с бесконечным буфером; а = 0,3; N = 5 1 (№ Ms) Ws RS ТЗ ПЗ ОП ТЗ ПЗ ОП 20 (40, 20) 0,0474 0,0476 0,0037 0,1131 0,1122 0,0085 (45, 30) 0.0388 0,0389 0,0024 0,0699 0,0703 0,0052 (50,35) 0,0327 0,0328 0,0014 0,044 0,0438 0,0046 (55,40) 0,0282 0,0283 0,0008 0,0287 0,0284 0,0106 25 (40, 20) 0,0570 0,0576 0,0109 0,3378 0,3622 0,0722 (45, 30) 0,0456 0,0460 0,0081 0,2220 0,2356 0,0611 (50,35) 0,0378 0,0380 0,0048 0,1450 0,1500 0,0347 (55,40) 0,0322 0,0323 0,0030 0,0969 0,0986 0,0179 Замечание. Поскольку для модели с неограниченным размером буфера система является бесконечномерной, то при вычислении норм (24) и (25) максимальное число заявок в системе сверху ограничивается достаточно большой конечной величиной. Такая замена является оправданной, так как при превышении этой величины определенного (достаточно большого) значения соответствующие вероятности состояний становятся бесконечно малыми величинами, т.е. практически равными машинному нулю. Важно отметить, что разработанные приближенные формулы имеют высокую точность и при вычислении характеристик системы. Так, из табл. 2 заключаем, что точные и приближенные значения характеристики (5) в худщем случае отличаются друг от друга в третьем знаке после десятичной точки. Иными словами, здесь максимальное значение ОП составляет меньше 1% (аналогичные результаты получены при вычислении характеристики (4), потому эти результаты здесь не приводятся; этого следовало ожидать, так как характеристики (4) и (5) отличаются друг от друга постоянным множителем). Точность вычисления характеристики (6) также является достаточно высокой для инженерных расчетов, так как при вычислении данной характеристики максимальное значение ОП составляет 7%. Таблица 3 Оценка точности вычисления вероятностей состояний относительно различных норм близости для модели с ограниченным буфером; а = 0,3; M = 7; N=5 1 (№ Ms) Значения нормы 1 (MF Ms) Значения нормы (24) (25) (24) (25) 20 (40, 20) 0,929 0,169 25 (40, 20) 0,924 0,128 (45, 30) 0963 0,146 (45, 30) 0,950 0,124 (50, 35) 0,971 0,144 (50, 35) 0,958 0,143 (55, 40) 0,977 0,140 (55, 40) 0,965 0,130 Результаты численных экспериментов для модели с ограниченным размером буфера показаны в табл. 3 и 4. Из табл. 3 заключаем, что и для этой модели разработанные приближенные формулы имеют высокую точность при вычислении стационарных вероятностей состояний. Отметим, что здесь также все характеристики вычисляются с высокой точностью для выбранных данных, так как максимальное значение ОП при вычислении характеристики (5) составляет меньше 1% и значения ОП при вычислении характеристик (6) и (21) составляют меньше 7% (см. табл. 4). Однако для тех же исходных данных при Х = 25 максимальное значение ОП при вычислении характеристики (6) составляет целых 26% (эти результаты отмечены жирным шрифтом в табл. 4). Отметим, что такие 31 А.З. Меликов, Э.В. Мехбалыева результаты в вычислительных экспериментах объясняются тем, что рассматриваемая здесь гипотетическая модель имеет слишком малую размерность (M = 7) и, кроме того, в данных экспериментах те вероятности состояний, которые участвуют в определении характеристики (6), вычисляются с большими погрешностями (нами сейчас проводятся исследования для разработки алгоритмов устранения подобных погрешностей в проводимых экспериментах). С другой стороны, предложенный подход предназначен для моделей большой и сверхбольшой размерности (для моделей малой размерности могут быть использованы балансовые уравнения для вероятностей состояний), и для таких моделей подобные (нежелательные) случаи нами не обнаружены. Т аблица 4 Оценка точности вычисления характеристик модели с ограниченным буфером; а = 0,3; M = 7; N = 5 7 (№ ps) Ws RS PB ТЗ ПЗ ОП ТЗ ПЗ ОП ТЗ ПЗ ОП 20 (40, 20) 0,0644 0,065 0,0093 0,7313 0,7808 0,0677 0,0139 0,0143 0,0312 (45, 30) 0,052 0,0524 0,0083 0,5174 0,5501 0,0631 0,0068 0,0072 0,0649 (50,35) 00431 0,0433 0,0059 0,3544 0,3685 0,0398 0,0037 0,0040 0,0683 (55,40) 0,0364 0,0366 0,0041 0,2453 0,2512 0,0240 0,0021 0,0023 0,0688 25 (40, 20) 0,0771 0,0784 0,0161 1,9402 2,4457 0,2605 0,0523 0,0526 0,0052 (45, 30) 0,0638 0,065 0,.0185 1,6253 1,9442 0,1962 0,0281 0,0299 0,0632 (50,35) 0,0536 0,0544 0,0151 1,2419 1,4171 0,1411 0,0169 0,0182 0,0748 (55,40) 0,0454 0,046 0,0119 0,934 1,0302 0,1030 0,0104 0,0112 0,0806 Теперь рассмотим вторую цель. На рис. 2 показаны зависимости характеристик модели с неограниченным буфером от порогового параметра N при различных значениях вероятности включения медленного сервера (а). Как и следовало ожидать, среднее время пребывания заявок в системе является возрастающей функцией относительно указанного параметра (см. рис. 2, а), в то время как интенсивность включения медленного сервера убывает с ростом указанного параметра (см. рис. 2, Ъ). Эти графики также показывают, что введение рандомизированной N-политики позволяет существенным образом влиять на характеристики системы, особенно при малых значениях порогового параметра N. Так, при трехкратном увеличении вероятности включения медленного сервера удается более чем на 70% уменьшить среднее время пребывания заявок в системе (см. рис. 2, а), при этом почти в два раза увеличивается интенсивность включения этого сервера (см. рис. 2, Ъ). С ростом порогового параметра N влияние вероятности включения медленного сервера на характеристики системы почти исчезает. Рис. 2. Зависимость характеристик модели с неограниченным буфером от параметра N; Х = 25, pF = 50, цх = 35 Fig. 2. Dependence of the characteristics of the model with an unlimited buffer on the parameter N; X = 25, pF = 50, px = 35 32 Численное исследование системы с гетерогенными серверами На рис. 3 показаны зависимости характеристик модели с ограниченным буфером от порогового параметра N при различных значениях вероятности включения медленного сервера. Здесь, как и выше, с ростом параметра N среднее время пребывания заявок в системе увеличивается (см. рис. 3, а), интенсивность включения медленного сервера убывает (см. рис. 3, b); введенная для данной модели новая характеристика - вероятность потери заявок - является возрастающей относительно указанного параметра (см. рис. 3, с). Поведение последней характеристики также было ожидаемо, так как увеличение указанного параметра уменьшает шансы поступающих заявок быть принятыми в буфер. Отметим, что здесь двухкратное увеличение вероятности включения медленного сервера позволяет уменшить вероятности потери заявок почти в 2 раза (см. рис. 3, с). В отличие от предыдущих двух характеристик, здесь с ростом порогового параметра N влияние вероятности включения медленного сервера на характеристики системы также растет. а AS Р$ Рис. 3. Зависимость характеристик модели с ограниченным буфером от параметра N; Х = 30, pF = 55, рх = 40, M = 10 Fig. 3. Dependence of the characteristics of the model with a limited buffer on the parameter N; X = 30, pF = 55, px = 40, M = 10 Наконец рассмотрим третью цель. Для конкретности изложения здесь задача оптимизации заключается в следующем: требуется найти такое (оптимальное) значение параметра N*, чтобы минимизировать суммарные штрафы (Total Cost, TC), связанные с пребыванием заявок в системе, их потерями (для модели с ограниченным буфером), а также с включением и работой медленного сервера. Отметим, что из-за сложности задачи нам не удалось доказать (или отвергнуть) существование и единственность решения этой задачи для модели с неограниченым размером буфера. Поэтому здесь мы рассматриваем решение этой задачи для модели с ограниченым размером буфера. Решение этой задачи для модели последнего типа всегда существует, так как множество допустимых решений является конечным и дискретным. Суммарные штрафы определяются следующим образом: TC = csWs + XPBct + c0п(< 1 >) + cRS , (26) где c - штраф за единицу времени пребывания одной заявки в системе; c - штраф за потери одной заявки; c0 - штраф за единицу времени работы ^-сервера; c - штраф из-за одноразовое включение ^-сервера. 33 А.З. Меликов, Э.В. Мехбалыева Результаты решения задачи оптимизации ( Х = 30 ) Таблица 5 О, ЦБ) а M N TC* (Цр, цб) а M N TC* (ЦР Цб) а M N TC* 5 2 0,258 5 2 0,258 0,2 5 3 0,134 0,2 10 6 0,052 0,2 10 6 0,052 10 8 0,014 15 11 0,019 15 11 0,019 15 13 0,006 5 3 0,232 5 3 0,232 0,4 5 3 0,116 (40, 20) 0,4 10 7 0,048 (40, 20) 0,4 10 7 0,048 (50, 35) 10 8 0,013 15 12 0,018 15 12 0,018 15 13 0,006 5 3 0,220 5 3 0,220 0,7 5 4 0,100 0,7 10 8 0,048 0,7 10 8 0,048 10 9 0,012 5 2 0,258 15 13 0,018 15 14 0,005 Т аблица 6 Результаты решения задачи оптимизации ( Х = 40 ) (ЦР Цб) а M N TC* (ЦР Цб) а M N TC* (ЦР Цб) а M N TC* 5 1 0,583 5 1 0,456 0,2 5 1 0,377 0,2 10 2 0,203 0,2 10 4 0,130 10 5 0,0845 15 6 0,108 15 8 0,060 15 10 0,031 5 1 0,568 5 2 0,412 0,4 5 2 0,329 (40, 20) 0,4 10 4 0,207 (45, 30) 0,4 10 6 0,126 (50, 35) 10 7 0,078 15 7 0,118 15 10 0,060 15 11 0,029 5 2 0,583 5 3 0,411 0,7 5 3 0,312 0,7 10 5 0,223 0,7 10 6 0,133 10 7 0,079 15 8 0,129 15 11 0,064 15 12 0,029 Т аблица 7 Результаты решения задачи оптимизации ( Х = 70 ) (ЦР Цб) а M N TC* (ЦР Цб) а M N TC* (ЦР Цб) а M N TC* 5 1 1,173 5 1 0,793 5 1 0,659 5 0,2 10 1 0,439 0,2 10 1 0,285 10 3 0,224 10 15 1 0,229 15 4 0,165 15 6 0,122 15 5 1 1,113 5 1 0,741 5 1 0,625 5 (40, 20) 0,4 10 1 0,443 (45, 30) 0,4 10 3 0,298 (50, 35) 10 4 0,228 10 15 1 0,250 15 6 0,188 15 8 0,132 15 5 1 1,131 5 1 0,781 5 2 0,631 5 0,7 10 1 0,466 0,7 10 4 0,329 10 5 0,247 10 15 1 0,273 15 7 0,216 15 19 0,147 15 Из-за сложности определения поведения функции (26) относительно аргумента N здесь для нахождения решения минимизации TC используется метод полного перебора. Результаты решения задачи оптимизации показаны в табл. 5-7. Из этих таблиц можно сделать следующие выводы: - если вероятность включения медленного сервера остается постоянной, то при фиксированных значениях интенсивности входящего потока с ростом размера буфера оптимальное значение N также растет; 34 Численное исследование системы с гетерогенными серверами - если размер буфер остается постоянным, то при фиксированных значениях интенсивности входящего потока с ростом вероятности включения медленного сервера оптимальное значение N также растет; - если все параметры системы остаются постоянными, то с ростом интенсивности входящего потока оптимальное значение N уменьшается. Заключение В работе предложена рандомизированная N-политика включения медленного сервера, согласно которой при достижении длины очереди заявок величины N медленный сервер либо с определенной вероятностью включается, либо с дополнительной вероятностью остается в спящем режиме. Рассматриваются модели двух типов: с неограниченным и ограниченным размером буфера для ожидания заявок. Получено условие эргодичности модели с неограниченным размером буфера. Разработан унифицированный приближенный метод расчета распределения вероятностей состояний и характеристик изучаемых систем и решена задача оптимизации системы с ограниченным размером буфера. В качестве объектов дальнейших исследований можно указать системы, в которых вероятность включения медленного сервера зависит от текущего числа заявок в системе, а также системы, где интервалы времени между поступлениями заявок и времена их обслуживания имеют распределения фазового типа. Благодарность. Авторы выражают искреннюю благодарность профессору А.А. Назарову за его ценные замечания во время обсуждения результатов работы.

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

система с гетерогенными серверами, рандомизированная N-политика, численный анализ

Авторы

ФИООрганизацияДополнительноE-mail
Меликов Агаси Зарбали оглыИнститут систем управления Национальной академии наук Азербайджанадействительный член академии наук Азербайджана, профессор, доктор технических наук, заведующий лабораториейagassi.melikov@gmail.com
Мехбалыева Эсмира Видади кызыСумгаитский государственный университеткандидат технических наук, докторантesmira.mehbaliyeva@mail.ru
Всего: 2

Ссылки

Gumbel H. Waiting Lines with Heterogeneous Servers // Operations Research. 1960. V. 8. P. 504-511.
Singh V.S. Two-Server Markovian Queues with Balking: Heterogeneous vs Homogeneous Servers // Operations Research. 1970. V. 18. P. 145-159.
Singh V.S. Markovian Queues with Three Servers // IIE Transactions. 1971. V. 3. P. 45-48.
Fakinos D. The M/G/k Blocking System with Heterogeneous Servers // Journal of Operations Research Society. 1980. V. 31. P. 919-927.
Fakinos D. The Generalized M/G/k Blocking System with Heterogeneous Servers // Journal of Operations Research Society. 1982. V. 33. P. 801-809.
Lin B.W., Elsayed E.A. A General Solution for Multichannel Queuing Systems with Ordered Entry // Computers & Operations Research. 1978. V. 5. P. 219-225.
Elsayed E.A. Multichannel Queuing Systems with Ordered Entry and Finite Source // Computers & Operations Research. 1983. V. 10. P. 213-222.
Yao D.D. The Arrangement of Servers in an Ordered Entry System // Operations Research. 1987. V. 35. P. 759-763.
Pourbabai B., Sonderman D. Server Utilization Factors in Queuing Loss Systems with Ordered Entry and Heterogeneous Servers // Journal of Applied Probability. 1986. V. 23. P. 236-242.
Pourbabai B. Markovian Queuing Systems with Retrials and Heterogeneous Servers // Computational Mathematics Applications. 1987. V. 13. P. 917-923.
Nawijn W.M. On a Two-Server Finite Queuing System with Ordered Entry and Deterministic Arrivals // European Journal of Operations Research. 1984. V. 18. P. 388-395.
Nawijn W.M. A Note on Many-Server Queuing Systems with Ordered Entry with an Application to Conveyor Theory // Journal of Applied Probability. 1983. V. 20. P. 144-152.
Yao D.D. Convexity Properties of the Overflow in an Ordered Entry System with Heterogeneous Servers // Operations Research Letters. 1986. V. 5. P. 145-147.
Isguder H.O., Kocer U.U. Analysis of GI/M/n/n Queuing System with Ordered Entry and no waiting line // Applied Mathematical Modelling. 2014. V. 38. P. 1024-1032.
Melikov A.Z., Mekhbaliyeva E.V. Analysis and optimization of system with heterogen-eous servers and jump priorities // Journal of Computer and Systems Sciences International. 2019. V. 58. P. 718-735.
Melikov A.Z., Ponomarenko L.A., Mekhbaliyeva E.V. Analysis of models of systems with heterogen-eous servers // Cybernetics and System Analysis. 2020. V. 56. P. 89-99.
Nath G., Enns E. Optimal Service Rates in the Multi-Server Loss System with Heterogeneous Servers // Journal of Applied Probability. 1981. V. 18. P. 776-781.
Larsen R.L., Agrawala A.K. Control of Heterogeneous Two-Server Exponential Queuing System // IEEE Transactions on Software Engineering. 1983. V. 9. P. 522-526.
Koole G. A simple Proof of the Optimality of a Threshold Policy in a Two-Server Queuing System // Systems and Control Letter. 1995. V. 26. P. 301-303.
Lin W., Kumar P.R. Optimal Control of Queuing System with Two Heterogeneous Servers // IEEE Transactions on Automatic Control. 1984. V. 29. P. 696-703.
Luh H.P., Viniotis I. Threshold Control Policies for Heterogeneous Servers Systems // Mathematical Methods in Operational Research. 2002. V. 55. P. 121-142.
Weber R. On a Conjecture about Assigning Jobs to Processors of Different Speeds // IEEE Transactions on Automatic Control. 1993. V. 38. P. 166-170.
Viniotis I., Ephremides A. Extension of the Optimality of a Threshold Policy in Heterogeneous Multi-Server Queuing Systems // IEEE Transactions on Automatic Control. 1988. V. 33. P. 104-109.
Rosberg Z., Makowski A.M. Optimal Routing to Parallel Heterogeneous Servers - Small Arrival Rates // IEEE Transactions on Automatic Control. 1990. V. 35. P. 789-796.
Горцев А.М., Назаров А.А., Терпугов А.Ф. Управление и адаптация в системах массового обслуживания. Томск : Изд-во Том. ун-та, 1978. 208 с.
Rykov V.V. Monotone Control of Queuing Systems with Heterogeneous Servers // Queuing Systems. 2001. V. 37. P. 391-403.
Efrosinin D.V., Rykov V.V. Numerical Study of the Optimal Control of a system with Heterogeneous Servers // Automation and Remote Control. 2003. V. 64. P. 302-309.
Rykov V.V., Efrosinin D.V. On the Slow Server Problem // Automation and Remote Control. 2009. V. 70. P. 2013-2023.
Efrosinin D.V., Breuer L. Threshold policies for controlled retrial queues with heterogeneous servers // Annals of Operations Research. 2006. V. 141. P. 139-162.
Efrosinin D., Sztrik J. Optimal Control of a Two-Server Heterogeneous Queuing System with Breakdowns and Constant Retrials // Communications in Computer and Information Sciences. 2016. V. 638. P. 57-72.
Efrosinin D., Sztrik J., Farkhadov M., Stepanova N. Reliability Analysis of Two-Server Heterogeneous Queuing System with Threshold Control Policy // Communications in Computer and Information Sciences. 2017. V. 800. P. 13-27.
 Численное исследование системы с гетерогенными серверами и рандомизированной А-политикой | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2020. № 53. DOI: 10.17223/19988605/53/3

Численное исследование системы с гетерогенными серверами и рандомизированной А-политикой | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2020. № 53. DOI: 10.17223/19988605/53/3