Minimization of unloading cost for an exponential time-sharing queueing process.pdf Повторное обслуживание присутствует во многих реальных управляющихсистемах: в системах обработки информации, системах управления конфликтны-ми транспортными потоками на пересечениях магистралей, системах таможенно-го досмотра в крупных аэропортах, системах управления комплексами микро-сварки и т. д. При этом следует учитывать возможность простоя обслуживающегоустройства при осуществлении переналадок (переориентаций прибора, жёлтогосвета светофора, переключения) и изменяющуюся во времени вероятностнуюструктуру промежутков времени между поступлениями требований входных по-токов. Другим источником повторного обслуживания требований могут служитьполомки прибора. Первые математические модели повторного обслуживания воз-никли при изучении алгоритмов разделения времени в многозадачных вычисли-тельных комплексах. В работе [1] рассматривалась система обслуживания пуас-соновского потока неоднородных требований по алгоритму с разделением време-ни без переналадок. В качестве экономического критерия эффективности управ-ления принималась средняя стоимость пребывания всех требований в единицувремени. Управление с относительными приоритетами оказалось оптимальным, ибыл предложен алгоритм назначения оптимальных приоритетных индексов длякаждого класса требований. Ветвящиеся потоки вторичных требований добавле-ны в работе [2]. В работах [3, 4] обслуживающее устройство кроме обслуживаниятребований осуществляло также внутренние переналадки. В качестве экономиче-ского критерия выбиралась ожидаемая стоимость пребывания всех требований всистеме за один такт её функционирования. Было установлено, что, несмотря наразличие в целевых функционалах, оптимальное управление принадлежит классууправлений с относительными приоритетами и для выбора приоритетных индек-сов можно воспользоваться аналогичным предложенному в [1] алгоритмом. Сис-тема массового обслуживания в классе алгоритмов с разделением времени и пе-реналадками для формируемых в случайной среде входных потоков и целевойфункцией вида средней стоимости пребывания всех требований за такт изучаласьв [5].На практике важно уметь оценивать загрузку системы обслуживания. Под за-грузкой чаще всего понимают долю времени, в течение которого система занятаобслуживанием требований. Однако для ряда реальных систем обслуживания та-кое определение не вполне однозначно, поскольку не учитывает возможностификсированного ритма функционирования систем обслуживания (например, приобслуживании конфликтных транспортных потоков) и наличия периодов перена-ладок и управления конфликтными потоками (системы управления транспортны-ми потоками, системы обработки информации по алгоритму разделения времени,и т. д.). В частности, неизвестно точное выражение для загрузки системы обслу-живания с разделением времени и переналадками, функционирующей в случай-ной среде [5]. В ряде работ для оценки загрузки системы используется функцио-нал достижения с запретами, называемый функционалом Чжуна [6]. В настоящейработе мы расширим понятие функционала Чжуна на счетные цепи Маркова с не-прерывным временем.1. Постановка задачи на содержательном уровнеВ систему поступают m <  конфликтных потоков требований ƒ1, ƒ2, …, ƒm.Потоки формируются в случайной среде с двумя состояниями: e(1) и e(2). При со-стоянии среды e(k), k = 1, 2, поток ƒj, j = 1, 2, …, m, пуассоновский с интенсивно-стью (k)ƒ j . Требования потока ƒj помещаются в накопитель Oj бесконечного объ-ема. Требования выбираются на обслуживание в порядке поступления. Обслужи-вающее устройство имеет n = 2m + 1 состояние ƒ(0), ƒ(1), …, ƒ(2m). В состоянии ƒ(r),1 ≤ r ≤ m, обслуживается требование из очереди Or. После состояния ƒ(r) приборпереходит в состояние ƒ(r) с r = r + m. В состоянии ƒ(r) осуществляется акт пе-реналадки и управления и требования не обслуживаются. Если в момент оконча-ния акта переналадки и управления очереди пусты, прибор переходит в состоянияƒ(0) ожидания поступления требований. При поступлении требования начинаетсяего обслуживание и состояние прибора становится ƒ(j), если первое требованиепоступило по потоку ƒj. Если по окончании акта переналадки и управления дли-ны очередей описываются ненулевым вектором x = (x1, x2, …, xm), то на обслужи-вание выбирается требование из очереди Oj, где j = h(x) - заданное отображениенеотрицательной целочисленной решетки X = {0, 1, …}m на множество {0, 1, …},удовлетворяющее ограничениям: h(x) = j влечет xj > 0 и прообразом точки 0 явля-ется только нулевой вектор 0 = (0, 0, …, 0)  X. Длительности обслуживаний ипереналадок независимы и имеют экспоненциальные распределения. Средняядлительность пребывания в состоянии ƒ(r) равна ƒr, средняя длительность перена-ладки и управления в состоянии ƒ(m+r) равна ƒr . Случайная внешняя среда син-хронизирована с обслуживающим устройством. Смена состояния случайной сре-ды может происходить только в моменты окончания обслуживания и актов пере-наладок и управления. Вероятность смены состояния e(k) на состояние e(l) равнаak,l, k, l = 1, 2. Итак, процесс смены состояния случайной среды не является мар-ковским. После обслуживания требование из Oj может с вероятностью pj,r посту-пить на повторное обслуживание в очередь Or, а с вероятностью,0 1 , 1 mj r jr p p = = − ƒ покидает систему. Таким образом, кроме потоков первичныхтребований, в систему поступают потоки вторичных требований и суммарныевходные потоки требований имеют сложную вероятностную структуру. Стои-мость пребывания одного требования в очереди Oj в единицу времени задана иравна cj. Считаем заданным разбиение множества X значений очередей на непус-тые непересекающиеся подмножества X0, X+, X−, X = X0  X+  X−. Множество X0интерпретируется как множество допустимых длин очередей, множество X+ - какмножество желательных длин очередей, наконец, множество X− - как множествозапрещенных длин очередей. Целью статьи на содержательном уровне являетсяматематическая формулировка и численное исследование алгоритма h(⋅), миними-зирующего условную среднюю стоимость достижения множества X+ из допусти-мого множества X0 при условии непопадания в запрещенное множество X−.2. Математическая модель и задача оптимизацииВсе объекты считаются заданными или конструируются на некотором вероят-ностном пространстве (ƒ, F, P), где ƒ - пространство описаний ƒ элементарныхисходов, F - ƒ-алгебра событий A  ƒ, P - вероятность. Введем следующие слу-чайные величины и случайные элементы: ƒ(t)  {e(1), e(2)} - состояние внешнейслучайной среды в момент t ≥ 0, ƒ(t)  ƒ = {ƒ(0), ƒ(1), …, ƒ(2m)} - состояние обслу-живающего устройства в момент t, ƒj(t) - число требований в очереди Oj в моментt, ƒ(t) = (ƒ1(t), ƒ2(t), …, ƒm(t)).Поскольку течение процесса{(ƒ(t), ƒ(t), ƒ(t)); t ≥ 0} (1)после момента t определяется только моментом окончания акта прибора, продол-жающегося в момент t, поступлением требований после момента t и состояниямислучайной среды после момента t, то при заданном начальном распределениислучайный процесс (1) является марковским со счетным числом состояний c фа-зовым пространствомS = {(ƒ(0), 0, e(k)): k = 1, 2}  {(ƒ(r), x, e(k)): r = 1, 2, …, m; x  X, xr > 0; k = 1, 2}  {(ƒ(r), x, e(k)): r = m + 1, m + 2, …, 2m; x  X; k = 1, 2}.Марковский процесс (1) является однородным. Обозначим q(r, x, k; r, w, l) -интенсивность перехода из состояния (ƒ(r), x, k)  S в (ƒ(r), w, l)  S. Пустьq(r, x, k) = − q(r, x, k; r, x, k), ƒs,s - символ Кронекера. Для s = 0, 1, …, m введем по-стоянные векторы y(s) = (ƒ1,s, ƒ2,s , …, ƒm,s)  X, причем y(0) = 0.Теорема 1. Интенсивности перехода марковского процесса (1) имеют вид( ) ( ) ( )(0, , ) 1k 2k kq 0k= ƒ + ƒ +…+ ƒm ,для r = 1, 2, …, m, s = 0, 1, …, m, x  X, xr > 0, j = 1, 2, …, m, r = h(x)1 ( ) ( ) ()( , , ) 1k 2k kq r x k = ƒr− + ƒ + ƒ +…+ ƒm,1 ( ) ( ) ()( , , ) 1k 2k kq m+r x k = ƒr− +ƒ +ƒ +…+ƒm,(0, , ; , (r), ) (k)q 0kry k= ƒr ,( , , ; , ( j), ) (k)q r x k r x+y k =ƒj ,( ) ( ) 1( , , ; , r s, ) , ,q r x k m+r x−y + y l =ak lƒ−r pr s ,q m+r x k m+r x+ y k = ƒ j ,1q(m+r, x,k;r, x,l)=ak,lƒr− .Прочие интенсивности равны нулю.Из вида интенсивностей перехода следует, что марковский процесс (1) имееттолько устойчивые непоглощающие состояния и консервативную инфинитези-мальную матрицу. Будем считать процесс (1) сепарабельным и измеримым [7,с. 211]. Пусть стоимость пребывания процесса (1) в состоянии (ƒ(r), x, e(k)) в еди-ницу времени равна c(ƒ(r), x, e(k)) ≥ 0 и фазовое пространство разложено на три не-пересекающихся подмножества: S0  ∅ - множество допустимых состояний,S+  ∅ - множество финальных состояний и S− - множество запрещенных состоя-ний (запрещенное множество). Введем случайную величинуƒ(ƒ) = inf {t ≥ 0: (ƒ(t), ƒ(t), ƒ(t))  S+, (ƒ(t), ƒ(t), ƒ(t)) ∉ S−, 0 ≤ t ≤ t}- момент достижения финального множества S+ без захода в запрещенное множе-ство S−. Обозначим ƒ(r, x, k) = {ƒ: ƒ(0) = ƒ(r), ƒ(0) = x, ƒ(0) = e(k)}. Тогда стоимостьƒ(ƒ) достижения финального множества S+ без захода в запрещенноемножество S− может быть вычислена как( )0( ) c( (t), (t), (t))dtƒ ƒƒ ƒ =  ƒ ƒ ƒ . (2)Средняя стоимость достижения финального множества S+ из допустимого состоя-ния (ƒ(r), x, e(k))  S0 без захода в запрещенное множество S− при функции пере-ключения h(⋅) определяется тогда какE(ƒ|ƒ(r, x, k)  џ]ю q{ƒ: ƒ < }).Здесь E - символ математического ожидания.При сделанных предположениях относительно марковского процесса (1) еереализации с вероятностью 1 являются кусочно-непрерывными и имеют разрывылишь первого рода. Пусть ƒ0 = 0 и ƒ1, ƒ2, … - моменты скачков процесса (1). Рас-смотрим вложенную цепь Маркова{(ƒi, ƒi, ƒi); i = 1, 2, …} (3)с ƒi = ƒ(ƒi + 0), ƒi = ƒ(ƒi + 0), ƒi = ƒ(ƒi + 0). Хорошо известно [4], что вероятностьперехода цепи (3) из состояния (r, x, k)  S в состояние (r, w, l)  S равна q(r, x, k;r, w, l)(q(r, x, k))−1 при (r, x, k)  (r, w, l) и равна 0 при (r, x, k) = (r, w, l), а величи-на ƒi+1 − ƒi при фиксированном (ƒi, ƒi, ƒi) = (ƒ(r), x, e(k)) имеет экспоненциальноераспределение с параметром q(r, x, k). Далее, момент ƒ совпадает с моментомскачка ƒƒ, со случайным номером ƒ = min{i: (ƒi, ƒi, ƒi)  S+, (ƒƒ, ƒƒ, ƒƒ) ∉ S−,0 ≤ ƒ ≤ i}. Вероятность f (r, x, k) = P({ƒ: ƒ < } | ƒ(r, x, k)), (ƒ(r), x, e(k))  S0 , назы-вается табу-вероятностью [6]. Напомним, что решение системы линейных урав-нений, найденное методом последовательных приближений с нулевыми началь-ными условиями, называется главным решением [8, с. 33]. Следующая теореманепосредственно выводится из теоремы 1 из [6] с учетом вида переходных веро-ятностей цепи Маркова (3). Содержательный смысл следующих ниже теорем 2, 3заключается в указании на те из ограниченных решений бесконечных систем ли-нейных алгебраических уравнений, которые несут интересующий нас вероятност-ный смысл.Теорема 2. Табу-вероятности {f(r, x, k); (ƒ(r), x, e(k))  S0} достижения с запре-том являются главным решением системы линейных уравнений( ( ), ,( ))( , , ) ( , , ) ( , , ; , , )s w el Sq r x k f r x k q r x k s w lƒ  += ƒ +( ) ( )( , , ) 0( , , ) ( , , ; , , )s w el Sf r x k q r x k s w lƒ + ƒ , (ƒ(r), x, e(k))  S0.Теорема 3. Условные средние стоимости достижения с запретом при f(r, x,k)  0 задаются выражениемE(ƒ | ƒ(r, x, k)  {ƒ: ƒ < }) = G(r, x, k)(f(r, x, k))−1,где величины G(r, x, k), (ƒ(r), x, e(k))  S0, являются главным решением системылинейных уравнений (0 ⋅  = 0)( ) ( )( , , ) 0( , , ) ( , , ) ( , , ) ( , , ) ( , , ) ( , , ; , , )s w el Sq r x k G r x k c r x k f r x k G r x k q r x k s w lƒ = + ƒ . (4)Доказательство. Используя вложенную цепь Маркова (3), стоимость дости-жения финального множества S+ без захода в запрещенное множество S− можнопривести к виду110c( , , )( )ƒ−ƒ ƒ ƒ ƒ+ ƒƒ=ƒ = ƒ ƒ ƒ ƒ ƒ − ƒ .Построим последовательность случайных величин( 1)( )10( , , )( )NN cƒ− ƒ ƒ ƒ ƒ+ ƒƒ=ƒ = ƒ ƒ ƒ ƒ ƒ −ƒ ,монотонно сходящуюся к случайной величине ƒ при N  , обозначимI(A) = I(A,ƒ) индикатор события A  F. Условное математическое ожидание отно-сительно события ƒ(r, x, k) будем для краткости обозначать символом E(r,x,k) . Обо-значим f (i)(r, x, k) вероятность достижения финального множества S+ без захода взапрещенное множество S− за i шагов. Последовательно вычисляемE(r,x,k)(ƒ(0)I({ƒ: ƒ < })) = E(r,x,k)(c(ƒ0, ƒ0, ƒ0)(ƒ1 − ƒ0)I({ƒ: ƒ < })) == c(r, x, k)(q(r, x, k))−1f(r, x, k),( 1)( , , )( N ({: }))E r x k ƒ + I ƒ ƒ N},то данную задачу можно интерпретировать как задачу о минимизации условнойсредней стоимости разгрузки системы, поскольку множество X+ на содержатель-ном уровне состоит из малых длин очередей. Аналитическое решение задачи ми-нимизации J(h, S+, S0, S−) в классе всех допустимых функций переключения h(⋅) неизвестно. В то же время, легко построить пример разбиения X, для которого мно-жество X+ желательных длин очередей не достижимо из множества X0 ни при ка-ком допустимом управлении. Пусть для произвольных натуральных чисел Nj < Nj,j = 1, 2, …, m, имеют место равенстваX+ = {x: xj ≤ Nj, j = 1, 2, …, m}, X− = {x: Nj < xj ≤ Nj, j = 1, 2, …, m }. (8)На рис. 1 приведен пример разбиения (8) множества X для двух очередей, m = 2 (ивыбору на обслуживание самой длинной очереди). Множество X+ ограниченоштрихпунктирной линией, множество X+ - штриховой линией, X− - пунктирнойлинией. Учитывая соотношения теоремы 1, находим( ( ), ,( ))( , , ; , , ) 0s w el Sq r x k s w lƒ  +ƒ = , (ƒ(r), x, e(k))  S0.Действительно, для достижения S+ из S0 необходимо, чтобы за один шаг обе оче-реди сократились, по крайней мере, на одно требование. По лемме 5 из [6] заклю-чаем, что f(r, x, k) = 0 для всех (ƒ(r), x, e(k))  S0.Пусть число входных потоков m = 2 и разбиение множества X имеет вид (7).Для проведения численных экспериментов мы ограничимся классом экстремаль-ных и пороговых функций переключения, поскольку решение задачи оптимиза-ции полным перебором представляется крайне трудоемким. В то же время, функ-ция переключения, реализующая управление с относительными приоритетамиможет быть представлена как частный случай пороговой функции переключения.Введем следующие обозначения. Считаем, что x = (x1, x2)  0 и a = 0, 1, …. Пусть1) hmax(x) принимает значение 1 при x1 ≥ x2 и значение 2 при x1 < x2; 2) hpri,1(x) при-нимает значение 1 при x1 > 0, значение 2 в остальных случаях; 3) hpri,2(x) принима-ет значение 2 при x2 > 0, значение 1 в остальных случаях; 4) hthr,1(x) принимаетзначение 1 при x2 = 0 или x1 ≥ a, значение 2 при x2 > 0 и x1 < a; 5) hthr,2(x) принима-ет значение 1 при x1 > 0 и x2 ≥ a, значение 2 при x1 = 0 или x2 > a. Функцияпереключения hmax(⋅) соответствует обслуживанию самой длинной очереди(см. рис. 1), hpri,1(⋅) и hpri,2(⋅) - обслуживанию с относительными приоритетами,hthr,1(x) и hthr,2(x) - обслуживанию приоритетного типа с ненулевым пороговымзначением a для приоритетной очереди (см. рис. 2). На рис. 1, 2 окрашивание точ-ки x = (x1, x2) в белый цвет соответствует выбору управления h(x) = 1, а в черный -управления h(x) = 2. Легко видеть, что hpri,1(⋅) совпадает с hthr,1(x), а hpri,2(⋅) совпада-ет с hthr,2(x) при a = 1. При данном выборе стоимостей c1, c2 пребыванияодного требования единицу времени в очередях O1, O2 соответственно имеем:c(ƒ(r), x, e(k)) = c1x1 + c2x2. Таким образом, мы вычисляем суммарное время пребы-вания всех требований в системе до момента разгрузки.Рис. 1. Вид разбиения множества X типа (8)и функция переключения hmaxРис. 2. Вид разбиения множества X типа (7)и пороговая функция переключения hthr,1при a = 6Пусть заданы параметры a1,1 = 0,5, a2,2 = 0,8, (1)ƒ1 = 0,1, (2)ƒ1 = 0, 2 , (1)ƒ2 = 0,15 ,(2)ƒ2 = 0,05 , ƒ1 = 0,375, ƒ2 = 0,5, ƒ1 = 0,125 , ƒ2 = 0, 25 , p1,1 = 0, p1,2 = 0,05,p2,1 = 0,02, p2,2 = 0,01, c1 = c2 = 1, N1 = 5, N1 = 15, N2 = 4, N2 = 10. Численно решаясистемы линейных уравнений из теорем 2, 3, находим: J(hmax) = 205,779,J(hpri,1) = 237,444, J(hpri,2) = 239,188, а наименьшее значение 193,852 функционалJ(⋅) достигает на функции переключения hthr,1 при a = 6 (рис. 2). Заметим, что гра-ница, разделяющая области выбора на обслуживание первой и второй очередей,совпадает с одной из границ вида xj > Nj множества X+. Такой характер оптималь-ного управления в рассматриваемом классе допустимых управлений наблюдалсянами практически всегда. Хотя мы не нашли оптимальной функции переключенияв классе всех возможных функций переключения, проведенные эксперименты по-зволяют сделать вывод: приоритетное обслуживание не является наилучшим в за-даче разгрузки систем обслуживания с разделением времени и переналадками привыбранном разбиении вида (7).ЗаключениеВ данной работе рассмотрена задача вычисления средней стоимости достиже-ния марковским процессом заданного множества состояний с запретом посеще-ния выделенного множества состояний при условии, что движение завершается законечное время. Такая задача возникает естественным образом при оптимизацииразгрузки экспоненциальных систем обслуживания конфликтных потоков неод-нородных требований. Важным практическим выводом работы является то, чтопри управлении в классе алгоритмов разделения времени с переналадками с це-лью уменьшения очередей следует пользоваться функцией переключения порого-вого, а не приоритетного типа.Работа выполнена в рамках госбюджетной НИР ННГУ им. Н.И. Лобачевского- национального исследовательского университета по теме № 01201154442 «Соз-дание методов численного анализа и синтеза динамических систем для исследо-вания нелинейной динамики сложных систем и процессов».

Скачать электронную версию публикации