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

Научная статья
Выпуск: № 1 (8), 2013
Опубликована:
08.02.2013
PDF

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

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

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

Аннотация

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

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

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

Введение

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

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

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

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

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

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

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

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

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

Входные потоки П1, П2, , Пm считаем пуассоновскими соответственно с интенсивностями

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

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

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

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

a)  входные потоки П1, П2, , Пm первичных требований первый тип входных полюсов для управляющей системы обслуживания;

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

c)  накопители O1, O2, …, Om очередей  по входным потокам внешняя память;

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

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

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

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

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

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

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

  1. ― число заявок потока Пj, пришедших за время дискретная случайная величина принимает свои значения из  X = {0, 1, …};
  2.  ― максимально возможное число заявок, которое может быть обслужено за время из очереди потока Пj; любая дискретная случайная величина принимает значения из множества , где ljмаксимально возможное число машин потока Пj, которое может проехать за время работы сигнала Г (2j1) и lj = а ― это максимально возможное число машин потока Пj, которое может обслужиться за время работы сигнала Г (2j) и  = причемтак как
  3.  Гi ― состояние светофора на промежутке  каждый из случайных элементов Гi  принимает значения из набора Г = {Г (1), Г (2), ..., Г (2m)};
  4.  æj, i ― длина очереди по потоку Пj в момент времени ti, æj,i является дискретной случайной величиной со значениями из множества Х;
  5. ― число реально обслуженных заявок потока Пj за случайная величина принимает значения из множества Yj = {0, 1, , lj};
  6. 1 ― число реально обслуженных заявок потока Пj за время [0, t0), случайная величина 1 принимает значения из множества Yj.

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

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

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

Так как обслуживающее устройство или светофор имеет циклический алгоритм работы, то его следующее состояние Гi + 1 зависит только от предыдущего состояния Гi. Введем в рассмотрение функцию U(Г (r)), которая принимает значение Г (1)  при    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-го потока.

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

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

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

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

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

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

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

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

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

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

Список литературы

  • Федоткин М.А. Процессы обслуживания и управляющие системы // Математические вопросы кибернетики.― М.: Наука, 1996. ― Вып. 6 ― С. 51–70.

  • Федоткин М.А. Нелокальный способ задания управляемых случайных процессов // Математические вопросы кибернетики. ― М.: Наука, 1998. ― Вып. 7. ― С. 333–344.

  • Ляпунов А.А., Яблонский С.В. Теоретические проблемы кибернетики // Проблемы кибернетики. ― М.: Физматгиз, 1963. ― С. 5–22.

  • Нелокальное описание выходных потоков в системе с циклическим обслуживанием и переналадками, Е.В. Пройдакова, М.А. Федоткин, ННГУ, Нижний Новгород, 2004–27с. / Деп.в ВИНИТИ, No 1856 –В2004.

  • Анализ свойств выходных потоков в системе с циклическим обслуживанием и переналадками Е.В. Пройдакова, М.А. Федоткин, ННГУ, Нижний Новгород, 2005 –32 с./ Деп. в ВИНИТИ, No442 –В2005.

  • Пройдакова Е.В., Федоткин М.А. Управление выходными потоками в системе с циклическим обслуживанием и переналадками // Автоматика и телемеханика . ― 2008. ― No 06 ― С.96-107.