Optimization of conflicting flows control parameters in the class of cyclic algorithms.pdf Входные потоки многих реальных систем массового обслуживания являются конфликтными. На содержательном уровне конфликтность означает, что требования различных потоков не могут обслуживаться одновременно и что путем сложения входных потоков нельзя существенно уменьшить их число. Для управления конфликтными потоками в настоящее время используется много разнообразных алгоритмов: циклические, пороговые, циклические с продлениями, с динамическими приоритетами и т.д. [1 - 11]. С целью разрешения конфликтности в процесс функционирования обслуживающего устройства вводятся этапы переналадок, во время которых требования не обслуживаются. Для управления конфликтными транспортными потоками на регулируемых перекрестках во многих странах мира используются целые компьютеризированные комплексы, включающие в себя детекторы, видеонаблюдение, и т.д., Такой комплекс способен как осуществлять мониторинг текущей ситуации на дорогах (моменты прибытия машин к стоп-линиям, число ожидающих переезда машин по каждой полосе, и т.д.), так и выбирать один из нескольких возможных алгоритмов управления, наиболее подходящий к текущей дорожной ситуации. С теоретической точки зрения важно уметь генерировать такие алгоритмы в ходе теоретического решения некоторых оптимизационных модельных задач. В работе [1] постановка и решение этой задачи искались в классе алгоритмов с динамическими приоритетами. Экономический критерий задавал среднее время пребывания всех требований в системе за один такт. В некоторых реальных системах массового обслуживания важно, чтобы поведение управляющего устройства было предсказуемым с точки зрения требований. Например, участники дорожного движения ожидают, что светофор предоставляет возможность проезда последовательно каждому из потоков и отклонения от такой последовательности может быть воспринято как поломка светофора и, вследствие этого, стать причиной дорожно-транспортных происшествий. Следовательно, представляет интерес изучения циклических алгоритмов с переменными длительностями обслуживаний и переналадок. В качестве экономического критерия естественно рассматривать среднее время пребывания всех требований в системе за один цикл. 1. Постановка задачи Пусть в систему массового обслуживания с потерями поступают m < ю конфликтных входных потоков П1, П2, ..., Пт. В течение промежутка времени А, 0 < А > 1 промежутков при неограниченном времени функционирования системы (т.е. при i ^ ю). Другие задачи оптимизации при циклическом управлении рассматривались, например, в [4, 8, 9, 12]. Приведенное выше формализованное описание управляемой системы массового обслуживания может быть проиллюстрировано следующим примером. Рассмотрим регулируемое светофором пересечение транспортных магистралей, изображенное на рис. 1. В этом частном случае т = 2. Входные потоки П1, П2 автомобилей являются конфликтными. Для разрешения конфликтности в режиме переналадки используется желтый свет светофора. Также естественно предположить, что перед стоп-линиями имеется лишь конечное число мест ожидания. Рис. 1. Перекресток автомагистралей, управляемый светофором 2. Построение математической модели Будем наблюдать систему в дискретные моменты времени 0, А, 2А, .... Пусть случайная величина к-,,- задает число требований в накопителе O - в момент i А, случайная величина j - число требований потока П-, поступивших за промежуток времени (i А, (i + 1) А], случайная величина ^j- - виртуальное число обслуженных требований из накопителя O- за промежуток времени (i А, (i + 1) А] в предположении наличия достаточного числа ожидающих требований в очереди, а случайный элемент Г,- е {Г(1), Г(2), ..., Г(2т)} - состояние обслуживающего устройства на промежутке ((i - 1) А, i А]. Введем также случайные вектор К = (к1,,, к2j, ..., Kmi). Из постановки задачи на содержательном уровне следует, что динамика формирование очереди O- из потока П- на интервале времени (i А, (i + 1) А] задается следующим рекуррентным соотношением: Kj,i + 1 = min{Nj, max{0, к,- + j - j }}. Обозначим Tir) = Thr + T2,r + ... + T2mr. Пусть т(0) = 0 и x(i + 1) = x(i) + fr) при m(kx(,-)) = r. Тогда имеет место равенство Г,- = r(s), если для целого 6 имеют место неравенства т(6) + T1r + T2,r + ... + Ts-1r (a), Q()(a) суть a-е степени матриц P() и Qr' соответственно, a = 0, 1, ... . Тогда переходная вероятность цепи Маркова (1) для х e X, u(x) = r и w = (w1, w2, ..., w^) e X имеет вид т Si) Si) (f)( эй Р({Ю : Ktp+D = w}|{co : кТ(г) = х}) = П [(Q(j) (Tu + T2,r + . • • + Tj^) x j=1 )Q( - )(T2 i-,r + T J +1 r + . + T2 тг ))x xP( J )(72 (2) 2 i-1, r где запись (■)kl обозначает элемент к-й строки и l-го столбца указанной в скобках матрицы. Из вида переходных вероятностей (2) следует, что состояния цепи Маркова (1) принадлежат единственному эргодическому классу при любом управлении. Пусть случайная величина j измеряет время пребывания всех требований в очереди OJ на промежутке времени (i A, (i + 1) А]. Математическое ожидание времени пребывания всех требований в системе за промежуток времени (x(i), x(i + 1)], заключающий в себе один цикл работы обслуживающего устройства, и при условии кт(,) = х определяется выражением т T(r)-1 Zi (х) = Z Z E(Z J,T(i) |{с° : кт(s) = х}) , r = u(x). j=1 t=0 С экономической точки зрения время ожидания представляет потери управляемой системы массового обслуживания. Поскольку моменты поступления требований и моменты окончания обслуживания требований непосредственно не наблюдаются, будем считать их равномерно распределенными в соответствующих интервалах. Поэтому ниже речь будет идти, на самом деле, об оценках для соответствующих экономических показателей обслуживания. Итак, для вычисления величин z(£), х e X, обозначим ^(Д) = кА при к = l = 1,2, ..., Nу, кА + А/2 при к + 1 = l = 1,2, ..., Nj, 0 при к Ф l, к Ф l -1 или к = l = 0; X ,р, А /4(1-X, +X ,р,) при к = l = 0, при к = l = 1, 2,..., Nу при к + 1 = l = 1, 2,. при к -1 = l = 0,1,. при к Ф l, к Ф l ± 1. к А к Д + Д/2 к А-А/2 0 —А) = ,N}, ,Nj -1, Здесь величина g^j (А) есть математические ожидание времени, проведенного в системе требованиями из очереди OJ и поступившим требованием из потока П- за промежуток времени вида (i A, (i + 1) А] при условии, что за этот промежуток число требований в очереди сменилось с к на l и очередь Oj не обслуживалась. Величина hkj (А) есть математические ожидание времени, проведенного в системе требованиями из очереди OJ и поступившим требованием из потока П- за промежуток времени вида (i A, (i + 1) А] при условии, что за этот промежуток число требований в очереди сменилось с k на I и очередь OJ обслуживалась. Пусть т^ = {1, 2 T(Г)}, j = {t2j,r + t2j+1,r + — +t2m,r +1, t2j,r + t2j+1,r + — + t2m,r + 2 . • •, T2j-1,r + T2j,r + T2j+1,r + + . +T2m,r}. Определим последовательно HiJ>)(0) = 0, при HJ,r)(i) = E?J (() + HiJ,r)(i-1)) k=0 i e ^r) \ i H(J,r)(i) = ((A) + HkJ,r)(i -1)) k=0 при i e TJ,r). Тогда, в силу марковского свойства, m z, (x) = XH^;,r)(T(r)), u(x) = r. (3) j =1 j Рекуррентные соотношения (2) и (3) задают марковскую цепь с доходами [13]. Известно [13], что потери за in шагов имеют асимптотическое выражение a(x) + g i + o(1), где o(1) — 0 при i — да, константа a(x) зависит от начального состояния x e X. Величина g не зависит от начального состояния и называется предельными одно-шаговыми потерями. Для отыскания оптимальной функции переключения u(-) естественно воспользоваться алгоритмом Ховарда [13]. 3. Результаты численных экспериментов Для проведения численных экспериментов использовался язык высокого уровня Octave [14]. Была написана программа, реализующая алгоритм Ховарда. В экспериментах изучался случай двух конфликтных входных потоков (m = 2) и тремя режимами (d = 3). Были выбраны следующие значения числовых параметров: X1 = 0,1, X2 = 0,05, Pj = 0,6, р2 = 0,65, Tu = 6, T21 = T41 = 4, T3,i = 10, Tu = 10, T22 = T42 = 4, T32 = 6, T13 = T3,3 = 8, T2,3 = T4,3 = 4. При таком выборе длительностей состояний прибора общая длина цикла 24 остается постоянной, а среднее число поступивших требований за цикл по каждому потоку не превосходит среднего числа требований потока насыщения: X - T < р - T2j-1r . Оптимальные правила выбора управления при переменных размерах (N1 = N2 = 10, N1 = N2 = 20, N1 = N2 = 40) накопителей представлены на рис. 2 и 3. Кружок белого цвета означает выбор при данных длинах очередей первого режима, кружок черного цвета -второго режима, треугольник серого цвета - третьего режима. Хотя интенсивности входных потоков различаются в два раза, границы смены режимов на всех трех рисунках близки к линейным и проходят вблизи биссектрисы первого квадранта. Кроме того, третий режим рекомендуется включать, только если длины очередей практически равны. Целевая функция (предельная скорость роста потерь) в указанных трех случаях оказалась приближенно равна 27,842. Интересно, что если отказаться от третьего режима (d = 2), то значение целевой функции оказывается равным 27,899. Однако использование только третьего режима (d = 1) дает предельные потери в размере 31,717, что на 13,7 % хуже оптимального. Можно заключить о достаточности двух режимов обслуживания при данных ин-тенсивностях входных потоков и интенсивностях обслуживания. фооооооо оооооооо оооооооо ооооооо оооооо ооооо оооо ООО оо х2 0 х1 Рис. 2. Вид оптимального управления при емкостях накопителей N1 = N2 = 10 (слева), N1 = N2 = 20 (справа). Остальные параметры указаны в тексте Рис. 3. Вид оптимального управления при емкостях накопителей N1 = N2 = 40 (остальные параметры указаны в тексте) Рис. 4. Вид оптимального управления при емкостях накопителей N1 = N2 = 40, интенсивных входных потоках и двух режимах с оптимальными длительностями (остальные параметры указаны в тексте) Естественно поставить задачу о выборе оптимальных параметров режимов T11, ..., Tmd . Рассмотрим случай двух режимов (d = 2). Пусть входные потоки характеризуются параметрами X1 = 0,2, X2 = 0,15, длительность цикла Tr) = T постоянна, а длительности переналадок равны между собой, T2,1 = T4,1 = T2,2 = T4,2. Пусть, далее, в первом меньше времени отдается на обслуживание первого потока, а во втором режиме - на обслуживание второго потока (неравенства нестрогие). Тогда перебором значений T11 в диапазоне от 1 до T - 2T12 и значений T32 в диапазоне от 1 до T - 2T2,2 можно установить такие, при которых величина g принимает наименьшее значение. В частности, при X1 = 0,1, X2 = 0,05, указанных выше значениях интенсивностей обслуживания, при длине цикла T = 24 и длительностях переналадки T21 = T41 = T22 = T42 = 4 оптимальными оказываются значения T11 = 7, T31 = 9, T12 = 11, T32 = 5. Вид оптимальной функции переключения в этом случае приведен на рис. 4, а значение g = 144,35. Замечательно, что в первом режиме среднее число поступивших за цикл требований из первого потока X1 T = 4,8 больше среднего числа требований потока насыщения р 1T11 = 4,2, а во втором режиме аналогичная ситуация имеет место для второго потока: X2 T = 3,6 > р 2T32 = 3,25, то есть очереди оказываются перегруженными. Тем не менее эта комбинация режимов является квазиоптимальной. Первый режим выбирается, когда длина первой очереди мала по сравнению с длиной второй очереди, а второй режим выбирается, когда мало число требований во второй очереди. С другой стороны, поведение оптимального правила переключения в правом верхнем углу рис. 4 является результатом влияния границ: заполненность одной очереди становится дополнительным источником контроля. Наконец, стоит отметить, что рис. 4 отличается от рис. 2 и 3 существенно отличной от линейной формой границы, что часто наблюдалось нами при высокоинтенсивных входных потоках. Заключение В данной работе была построена математическая модель и разработаны программные средства оптимизации режимов обслуживания конфликтных потоков в классе циклических алгоритмов. Основной результат работы состоит в демонстрации того, что наличие нескольких наборов параметров циклического алгоритма обслуживания может снизить среднее время пребывания требований конфликтных потоков в системе за цикл.

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