THE OUTPUT STREAM OF CYCLIC SERVICE SYSTEMS

Пройдакова Е. В.

Кандидат физико-математических наук, Нижегородский государственный университет им. Н.И. Лобачевского

ВЫХОДНЫЕ ПОТОКИ ЦИКЛИЧЕСКИХ СИСТЕМ ОБСЛУЖИВАНИЯ

Аннотация

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

Ключевые слова: выходной поток, циклическая система управления, Марковская векторная последовательность.

Keywords: output flow, cyclic control system, Markov vector chain.

Введение

В современной теории массового обслуживания одним из наиболее актуальных и перспективных направлений является изучение свойств выходных потоков. Это в первую очередь связано с широким применением задач и методов теории массового обслуживания в организации производства и при создании сложных информационных систем. Как правило, такие системы имеют разветвленную структуру и состоят из двух и более подсистем, объединенных некоторым образом. Если в такой структуре имеется последовательное соединение, то выходной поток одной подсистемы является входным для другой, и в этом случае закономерно возникает вопрос описания выходного потока подсистемы, а точнее, проблема исследования его вероятностных распределений.

Почти очевидно, что выходной поток существенно зависит от системы массового обслуживания, в которой он формируется. Следовательно, в описание выходного потока необходимо включать некоторые элементы самой системы массового обслуживания. Более того, целесообразно следить не за отдельным требованием, а за некоторой случайной группой заявок. Впервые такой подход был предложен  М.А. Федоткиным и назван нелокальным описанием потоков требований [1-2]. При этом в описание выходных потоков включены такие элементы самой системы массового обслуживания как состояния обслуживающего устройства и величины очередей по потокам. Для построения моделей выходных потоков управляющих систем обслуживания и получения нелокального описания выходных потоков будем использовать так называемый кибернетический подход, методологически разработанный А.А. Ляпуновым и С.В. Яблонским [3].

Построение математической модели выходных потоков в циклической системе  обслуживания

Рассмотрим систему управления m независимыми и конфликтными транспортными потоками на пересечении магистралей в классе циклических алгоритмов. Конфликтность потоков означает, что их нельзя суммировать и это не позволяет свести задачу к более простому случаю с одним потоком. Обслуживание машин (требований) из конфликтных потоков происходит в непересекающиеся промежутки времени. Эти промежутки называются основными этапами обслуживания заявок. Под обслуживанием машин понимается их переезд через перекресток. Кроме того, есть еще дополнительные промежутки времени – переналадки, за счет которых разрешается проблема конфликтности потоков. Во время переналадок продолжает обслуживаться тот же поток, что и на основном этапе, но уже с большей интенсивностью. 

Так как у каждого из m потоков есть основной этап обслуживания и этап переналадки, то обслуживающее устройство должно ровно иметь 2m состояний  причем:

― состояние обслуживающего устройства, при котором пропускается поток с интенсивностью  не пропускаются остальные (можно интерпретировать это состояние как зеленый свет для потока  и красный для остальных потоков);

― состояние обслуживающего устройства, при котором пропускается поток с интенсивностью  и не пропускаются остальные (можно интерпретировать это состояние как желтый свет для потока ). Здесь определяет число машин, пропускаемых в единицу времени в состоянии автомата-светофора соответственно.

Длительности состояний Г ⁽¹⁾, Г ⁽²⁾, ..., Г ^(2m) известны и равны соответственно Т₁, Т₂, …, Т_2m единиц времени. Работа обслуживающего устройства осуществляется по циклическому алгоритму. Такой алгоритм управления конфликтными потоками используется потому, что он прост в реализации. Более того, за счёт выбора вектора  b = (Т₁, Т₂, …, Т_2m) циклический алгоритм часто оказывается квазиоптимальным по условию минимума задержек при сильной загрузке системы.

Вектор b есть управление m независимыми конфликтными потоками в нашей системе, где 

Входные потоки П₁, П₂, …, П_m считаем пуассоновскими соответственно с интенсивностями

Заявки, пришедшие в систему, могут или сразу поступать на обслуживание, или образовывать неограниченные очереди O₁, O₂, …, O_m. Из соответствующей очереди заявки выбираются на обслуживание группами по принципу: первая пришла – первая ушла.

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

Рис. 1. Функциональная схема циклической системы массового обслуживания

На рис. 1 представлены следующие составляющие блоки схемы:

a)  входные потоки П₁, П₂, …, П_m первичных требований ― первый тип входных полюсов для управляющей системы обслуживания;

b)  потоки насыщения (выходные потоки системы при ее максимальной загрузке и эффективном функционировании) ― второй тип входных полюсов;

c)  накопители O₁, O₂, …, O_m очередей  по входным потокам ― внешняя память;

d)  устройства по организации дисциплины очередей в накопителях или стратегии обслуживания ― блок по переработке информации внешней памяти;

e)  обслуживающее устройство с 2m состояниями  Г ⁽¹⁾, Г ⁽²⁾, ..., Г ^(2m) ― внутренняя память;

f)  алгоритм смены состояний Г ⁽¹⁾, Г ⁽²⁾, ..., Г ^(2m) обслуживающего устройства ― блок  по переработке информации внутренней памяти;

g)  выходные потоки обслуженных требований ― выходные полюса.

Все рассматриваемые ниже случайные объекты будем задавать на некотором вероятностном пространстве , где  ― множество описаний всех элементарных исходов системы,  алгебра событий , а Р(А) ― вероятность исхода .

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

Введем на  при , i = 0, 1,… следующие случайные величины и элементы:

1. ― число заявок потока П_j, пришедших за время дискретная случайная величина принимает свои значения из  X = {0, 1, …};
2.  ― максимально возможное число заявок, которое может быть обслужено за время из очереди потока П_j; любая дискретная случайная величина принимает значения из множества , где l_j – максимально возможное число машин потока П_j, которое может проехать за время работы сигнала Г ^{(2j – 1)} и l_j = а ― это максимально возможное число машин потока П_j, которое может обслужиться за время работы сигнала Г ^(2j) и  = причемтак как
3.  Г_i ― состояние светофора на промежутке  каждый из случайных элементов Г_i  принимает значения из набора Г = {Г ⁽¹⁾, Г ⁽²⁾, ..., Г ^(2m)};
4.  æ_j, i ― длина очереди по потоку П_j в момент времени t_i, æ_j,i является дискретной случайной величиной со значениями из множества Х;
5. ― число реально обслуженных заявок потока П_j за случайная величина принимает значения из множества Y_j = {0, 1, …, l_j};
6. _–1 ― число реально обслуженных заявок потока П_j за время [0, t₀), случайная величина _–1 принимает значения из множества Y_j.

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

Поток насыщения по j-му направлению будем задавать в виде случайной последовательности Введем в рассмотрение функции:

образом: Для  можно записать общее вырожденное условное распределение вида:

Так как обслуживающее устройство или светофор имеет циклический алгоритм работы, то его следующее состояние Г_i + 1 зависит только от предыдущего состояния Г_i. Введем в рассмотрение функцию U(Г ^(r)), которая принимает значение Г ⁽¹⁾  при    r = 2m и принимает значение  Г ^{(r + 1)} в остальных случаях, т.е. при   Тогда зависимость Г_i + 1 от Г_i  определяется рекуррентным соотношением (4).

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

Осталось получить рекуррентное соотношение для очереди. Очередь в момент времени будет складываться из очереди в момент времени , плюс заявки, пришедшие за интервал времени , и минус те, которые обслужились на этом интервале. Таким  образом, при i = 0, 1, …, .для очереди можно записать следующее равенство:

Из соотношений (5) видно, что для всех  случайные величины æ_{j, i + 1} и  определяются как неслучайные функции от случайных аргументов как неслучайная функция от случайного элемента Г_i (состояния обслуживающего устройства или светофора в i-й момент времени).

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

Поведение системы по потоку П_j описывается векторной последовательностью которая определяет динамику состояний обслуживающего устройства, флуктуацию длин очередей по потокам и флуктуацию обслуженных требований. Более того, данная последовательность задает нелокальное описание выходного потока по j-му направлению, причем за выходной поток отвечает а компоненты Г_i и  æ_j, i играют роль меток. Здесь и далее все рассуждения проводятся для  j-го потока.

Совершенно аналогично можно получить результаты и для последовательности  Считаем, что в начальный момент t₀ задано распределение векторов   то есть известны вероятности

Из равенств (1) и (3) следует, что условное распределения случайных величин существенно зависит от выбора вектора  b = (Т₁, Т₂, …, Т_2m). Отсюда в силу соотношений (5) и (6) конечномерные распределения последовательности также зависят от выбора вектора b.

Свойства векторной последовательности

Был проведен анализ поведения системы при фиксированном векторе  и для каждого потока П_j были доказаны утверждения, приведенные ниже. Полное доказательство утверждений представлено в работах [4 - 6].

Введем обозначения:

Лемма 1. При заданном распределении трехмерного начального вектора управляемая случайная векторная последовательность  является марковской.

Лемма 2. Пространство состояний случайной векторной последовательности разбивается на незамкнутое подмножество   несущественных состояний и на замкнутое подмножество  существенных периодических состояний с периодом 2m.

Автором были получены рекуррентные по i соотношения для одномерных распределений  последовательности  Кроме этого, найдены рекуррентные соотношения для производящих функций  за один такт работы системы и для производящих функций  за период , Данные соотношения использовались при доказательстве предельной теоремы.

Теорема. Для существования стационарного распределения последовательности необходимо и достаточно выполнение следующего неравенства

Установлено, что в циклической системе обслуживания возможно существование стационарного распределения как для отдельного потока П_j, , так и для всей системы, в зависимости от выполнения либо только одного неравенства  при некотором  j, или же m неравенств  вида