автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Оптимальное управление немарковскими потоками в системах с разделением времени

На правах рукописи

ЗОРИН Андрей Владимирович

ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ НЕМАРКОВСКИМИ ПОТОКАМИ В СИСТЕМАХ С РАЗДЕЛЕНИЕМ ВРЕМЕНИ

Специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ (физико-математические науки)

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Нижний Новгород - 2005 г.

Работа выполнена на кафедре прикладной теории вероятностей факультета вычислительной математики и кибернетики Нижегородского государственного университета им Н.И. Лобачевского.

Научный руководитель: доктор физико-математических наук профессор Федоткин М.А.

Официальные оппоненты:

доктор физ.-мат. наук, профессор В. Г. Ушаков доктор техн. наук, профессор В. И. Вайсблат

Ведущая организация: Российский государственный университет нефти и газа им. И. М. Губкина

Защита диссертации состоится " » ЯМЬМ^ 200б г. в ^ " часов на заседании диссертационного совета Д.212.166.13 при ННГУ им. Н. И. Лобачевского по адресу: 603950, г. Нижний Новгород, пр. Гагарина, 23. 2 корп., конференц-зал.

С диссертацией можно ознакомиться в фундаментальной библиотеке ННГУ им. Н. И. Лобачевского.

Автореферат разослан 2005 :

Ученый секретарь

диссертационного совета Д 212.116.13 кандидат физико-математических наук, доцент ГП- Савельев

дг

1

1. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Известны и широко разрабатываются два класса моделей систем с разделением времени. В моделях первого класса предполагается, что требования обслуживаются по одному и обслуживаются повторно, и что это частое повторное обслуживание создает видимость параллельного обслуживания. В моделях другого класса считают, что присутствующие в системе требования обслуживаются одновременно и что скорость обслуживания каждого требования зависит от общего числа требований в системе. Многими авторами былй изучены разные варианты таких задач. Основные результаты принадлежат Л. А. Шрейджу, Л. Клейнроку, Г. П. Климову, В. В. Рыкову, М. А. Федоткину, С. Ф. Яшкову, В. М. Вишневскому и др. Естесствен-ным языком моделей стал язык теории вероятностей и случайных процессов. Большинство исследователей предполагают простейший входной поток требований. Получающиеся таким образом модели допускают описание в виде регенерирующих процессов (возможно, с несколькими типаг ми точек регенерации) и с помощью вложенных цепей Маркова. Наконец, результативны оказались исследования по оптимизации таких систем по стоимостным критериям типа средней стоимости пребывания требований в единицу времени или средней стоимости пребываний всех требований за такт функционирования обслуживающего устройства. Как правило, оптимальный оказывалось правило выбора требований с наименьшим отношением среднего времени обслуживания к стоимости.

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

Цель работы. В даННОЙ работе ра/тмятпиияртгд гч™^ г ем времени, обобщающая известные сист< Федотки-

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

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

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

Теоретическая и практическая значимость. Данная работа была

выполнена в рамках следующих г/б тем, проводимых на кафедре прикладной теории вероятностей ННГУ и в лаборатории теории вероятностей и математической статистики НИИ прикладной математики и кибернетики ННГУ: "Математическое моделирование и создание новых методов анализа динамических систем и систем оптимизации" (номер государственной регистрации 01.2.00107703), "Синтез и сложность алгоритмов для задач конфликтного обслуживания и диагностики" (номер государственной регистрации 01.2.00100352), "Анализ дискретных управляющих систем обслуживания и систем вычисления булевых функций" (номер государственной регистрации 01.2.00100352).

Исследование носит теоретический характер. Результаты исследования используются при чтении специального курса "Системы с разделением времени" для студентов пятого курса факультета ВМК ННГУ, специализирующихся по кафедре прикладной теории вероятностей.

Основные результаты, выносимые на защиту. Наиболее существенные научные результаты, выносимые на защиту, состоят в следующем.

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

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

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

— Поставлена и решена для важных классов систем задача отыскания оптимального управления системами изучаемого класса. Приводится алгоритм назначения оптимальных приоритетов.

— На созданной компьютерной имитационной модели исследован предложенный алгоритм в применении как к минимизации средней стоимости пребывания требований в системе за один такт работы, так и к минимизации среднего времени пребывания произвольного требования в системе.

Личный вклад автора. Постановка задач и методы исследования принадлежат руководителю. Автору работы принадлежат выполнение исследования, обработка и интерпретация результатов. Идея имитационного моделирования систем с разделении времени, создание программы и исследование имитационной модели целиком принадлежат автору. Постановка задачи о периоде занятости и ее решение также принадлежат автору.

Апробация работы и публикации. Результаты диссертации были представлены на следующих семинарах, конференциях и конгрессах:

1. Конференция "Вычислительная математика и кибернетика 2000" (Нижний Новгород, 2000 г.).

2. Международная конференция "Прикладная статистика в социально-экономических проблемах" (Нижний Новгород, 2003 г.).

3. Международная конференция "Колмогоров и современная математика" (Москва, 2003 г.).

4. Международная конференция "Современные математические методы анализа и оптимизации телекоммуникационных сетей" (Гомель, 2003 г.)

5. Научно-техническая конференция "Математика и кибернетика 2003" (Нижний Новгород, 2003 г.)

6. XXIV Международный семинар по проблемам устойчивости стохастических моделей (Юрмала, 2004 г.).

7. VI Международный конгресс по математическому моделированию (Нижний Новгород, 2004 г.).

По теме диссертации опубликованы 14 работ. Список публикаций приводится в конце автореферата.

Структура диссертации. Диссертация состоит из введения, пяти разделов, списка литературы, содержащего 119 наименований, и приложения с текстами программ и численными результатами имитационного моделирования в виде таблиц и графиков. Объем основного текста работы 146 страниц.

2. КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении дается краткая характеристика изучаемой темы в целом и обзор литературы по рассматриваемому вопросу. Изложены основные цели работы, а также даны сведения об апробации работы и практических применениях результатов.

В первом разделе строится математическая модель потока, формируемого в марковской случайной среде. Популярность такие модели обрели после работ Д. Лукантони. Состояние среды образует марковский процесс с непрерывным временем и двумя состояниями е'1' и е'2'. Одной из интерпретаций случайной среды могут быть погодные условия. Тогда е'1' можно считать "хорошей погодой", а е'2' — "плохой погодой". Пусть х(1) € € {е'1', е'2'} обозначает состояние среды в момент £. Матрица переходных интенсивностей процесса {х(£); Ь > 0} равна

д. /-ЧЦ а,\ аг -а2у

При состоянии среды е^ требования поступают группами с распределением х = 1,2,..Pi*' = 1. размера группы, зависящим от fc, и группы

х—1

образуют простейший поток с параметром Л^. Пусть T](t) 6 {0, 1, ...} — число требований, Поступивших на интервале [0, t). Обозначим вероятность события {ш: Tj(t, ш) = х, ш) = е'*'} через Р(х, к, t). Положим

Fk(t, z) = f) zxP{x, fc, t), /«(z) = £ fc = 1, 2. Доказаны следую-

x=0 x=l

щие теоремы.

Теорема l.1 Одномерные распределения процесса {(»?(£), x(t))'i t > 0} удовлетворяют следующей системе уравнений:

|р(0, 1, t) = ~(ai + \Ы)Р(0, 1, f) + а2Р(0, 2, t), J^P(0, 2, t) = а,Р(0, 1, *) - (а2 + А<2>)Р(0, 2, i),

О 1-1

1, t) = -(Gl + A«)P(*. 1, f) + a2P(x, 2, t) + A« 1. 0.

x'=0

a ®-l

¿P(®, 2, t) = ajPfo 1, t) - (a2 + A«)P(®, 2, t) 4- A<2> 2, t),

xM)

для а: = 1, 2,----

Теорема 2. Функции z), k = 1, 2, удовлетворяют уравнению

= (A(i)(/№(z) - 1) - г) + *),

где И € {1, 2}, ^ А:.

Обозначим через = —/^'(г) аг

стоянии среды через А^*' = интенсивность поступления требо-

ваний при том же состоянии среды. В диссертации найдено, что

средний размер группы при со-*=1

Щ{1) = ( (fli + од)2 " аДо, J +

^ ai + aj (01 + аг)2 у

(ai + «2)

1В автореферате приводятся только некоторые из имеющихся в диссертация утверждений, при этом нумерация утверждений совпадает с нумерацией в диссертации

dMv(t)

Тогда мгновенная интенсивность —j-^— потока в момент t равна

dt

+„ _ „,*•> _ «Pl-t«.++«**

а\ + а2 I ai + ai

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

Во втором разделе изучается применение кибернетического подхода к построению математических моделей управляемых систем. Означенный подход развит М.А. Федоткиным в ряде работ и обязан своим возникновением воззрениям A.A. Ляпунова и C.B. Яблонского (см. Ляпунов A.A., Яблонский C.B. Теоретические проблемы кибернетики. В сб. Проблемы кибернетики, вып. 9. М.: Физматгиз, 1968 г., С. 5-22). В диссертации применение кибернетического подхода демонстрируется на примере простейшей однолинейной системы с разделением времени, входной поток которой формируется в случайной среде. Математической моделью функционирования внешней среды в простейшем случае является однородная неприводимая непериодическая марковская цепь с двумя состояниями е'1' и е'2'. Вероятность перехода из состояния е^ в состояние е**' за один шаг есть ад, где I, к € {1, 2}. Смена состояния среды может происходить только в моменты окончания обслуживании. При состоянии среды етребования поступают группами так, что поток групп есть простейший с параметром А»), а размеры групп — независимые одинаково распределенные случай-

00 /1Л

ные величины с производящей функцией — Pc z<\ \z\ < 1 + £

С=1

для некоторого е > 0. Здесь величина р'*' определяет вероятность того, что число заявок в группе равно с, когда состояние случайной среды есть е'*'. Длительности обслуживания требований — независимые одинаково распределенные случайные величины с функцией распределения B(t). Обслуженное требование с вероятностью р поступает на повторное обслуживание, а с вероятностью 1 — р покидает систему. Разделение времени в этой системе заключается в разбиении полного времени обслуживания каждого требования на случайное число частей и обращение к каждому требованию снова и снова, чтобы дать ему очередную порцию обслуживания прибором. Поскольку периоды постоянства состояния среды не имеют показательного распределения, естественно называть входной поток системы немарковским.

В соответствии с кибернетическим подходом, выделяется дискретная временная шкала наблюдений за системой в моменты окончания обслуживания. Затем приводится схема управляемой системы обслуживания. На

схеме присутствуют следующие составные части: а) внешняя случайная среда, которая изменяет вероятностную структуру входного потока первичных требований; б) входной поток П первичных требований — первый тип входных полюсов для управляющей системы обслуживания; в) входной поток П' вторичных требований — второй тип входных полюсов; г) поток насыщения П' (выходной поток системы обслуживания при максимально возможной ее загруженности и эксплуатации и отсутствии перенаправления заявок на повторное обслуживание) — третий тип входных полюсов; д) накопитель О очереди по входному потоку — внешняя память; е) устройство 8 по организации дисциплины очереди в накопителе — элемент по переработке информации внешней памяти; ж) обслуживающее устройство, которое имеет одно состояние Г*1' — внутренняя память; з) выходной поток П в действительности обслуженных и покинувших систему требований — выходные полюса. Набор состояний внешней среды, очереди в накопителе, обслуживающего устройства, входного потока, потока насыщения и, наконец, набор состояний потока обслуженных требований полностью определяют информацию управляющей системы обслуживания. Номера состояний внешней случайной среды, входного потока, потока насыщения, выходного потока, накопителя, механизма по формированию очереди и номер состояния обслуживающего устройства задают расположение элементов на схеме. Функция этой системы — обслуживание требований с помощью алгоритма разделения времени.

Рассматриваемые случайные объекты определяются или задаются конструктивно на некотором вероятностном пространстве (П, 5, Р(-)); здесь П — пространство описаний элементарных исходов, 5 — <т-алгебр а событий А С Я, Р(-) — вероятностная мера на

Дискретная шкала функционирования системы задается случайной последовательностью {г,; г = О, 1, ...}, где т0 = 0 и каждый г, есть момент окончания обслуживания требования, причем т,+1 > г,. Пусть {а*; » = = 0, 1, . •■} — последовательность независимых случайных величин, имеющих равномерное распределение на интервале (0,1) и отображение Ф: {е^1', е^2'} х (О, 1) —» {е'1), е^} принимает значение е'1', если 0 < а < ан, и принимает значение е®, если ац < а < 1. Далее, пусть обозначает состояние среды на интервале времени (т„ т,+1], пусть ту, равно числу требований, поступивших на промежутке (г<, 75+1] как извне, так и в результате перенаправления на повторное обслуживание. Через обозначим наибольшее число требований, которое может быть обслужено на промежутке (т„ т,+1]. Через щ обозначим длину очереди в момент т, после прихода вторичной заявки или до начала акта обслуживания. Пусть Д, — это время активной работы прибора на промежутке (т„ г,+х], при этом Д, < т,+х — т,. Случайная последовательность {(хг, х»); 1 = 0, 1, ...} удовлетворяет рекуррентному по = 0, 1, ... соотношению (х,+ь Х1+1) = (*> + Ш ~ 1> <*«))•

Пусть для х = О, 1, ... и к = 1, 2 А((х, к) = {ш: = х, х>(^) =

Лемма 6. Последовательность {(яи х«); г = О, 1, ... } при заданном начальном векторе {но, хо) является марковской цепью.

Теорема 3. Для гу = 0, 1, ..., к € {1, 2} и г = 0, 1, ... вероятности Р(А{(ю, к)) удовлетворяют системе разностных уравнений

2 ш+1

Р(А+1(™, к)) = ^сЦРШО, ¿))((1 Р«>-у+ЛЬ 1)<1В(1)+

/=1 |Р=1

ш+1

+ Р

Ш - ШТ1 л

/Рш_у(£; 1)<Ш(0) + (1 -р)£Р(Мх, I)) /Рш-х+1(1; 1)йВ{1)+ { . °?*=! ^

1=1

где суммы по х и у от 1 до 0 по определению равны нулю.

Марковская цепь {(х,, х«); « = 0, 1, ...} является неразложимой и апериодической. Доказательство существования стационарного распределения проводится итеративно-мажорантным методом (см. М. А. Федоткин. Теория дискретных систем с переменной структурой обслуживания квази-регенерирующих потоков. Автореферат докторской диссертации. М.: МГУ,

1984 г, 43 е.). Пусть (¿к) =

— средний размер группы при

2=1

состоянии среды Л^*' = — интенсивность поступления требо-

оо

ваний при состоянии среды (5\ = $ ЬдВ{1) — средняя длительность

о

одного акта обслуживания, = — р)-1, к = 1, 2.

Теорема 6. Для существования стационарного распределения последовательности {(х„ х,); г = 0, 1, ...} необходимо выполнение неравенств (а21 р(1) + апр<Я){аи + ого-1 < 1.

Теорема 7.Для существования стационарного распределения последовательности {(х„ х0; » = 0, 1, ...} достаточно выполнения неравенства тах{рМ, р®} < 1.

Численный пример показывает, что при оц ф 021 случайные элементы Хг и х, зависимы относительно стационарного распределения. Однако эта зависимость носит слабый характер.

В предположении наличия стационарного режима изучается совместное распределение периода занятости системы и состояния среды, которое наступает по его окончании. Именно, предположим, что требования поступают поодиночке. Пусть — условная вероятность того, что период занятости, начавшийся при состоянии среды е®, продлится не дольше чем £ и по его окончании состояние среды станет е'*'. Пусть * Я2(£) =

г е

= / - £')ЛЯ2(£') = / Я2(£-£')йЯг(£') - стилтьесовская свертка ЯЦ£) о о

и H2(t). Для матрицы G(t) = (G,*(i)),,fc=1,2 через G*6(i) = (g£6) (*)),,*=i,2 обозначим fr-кратную свертку, определяемую следующим образом: =

= Glk(t), G{'b)(t) = G«6-1»^) * GU(<) + Gi(2*(6~1))(i) * G2k(t)-

Теорема 8.Функции G«(f), I, k € {1, 2}, удовлетворяют системе уравнений

Г 00

Gik(t) = (1 -р) Y1W-' 0(«aG<;6)(i -1') + anG%\t -11)) dB(t')+

о »=<>

/■ 00

+ P / £'XauG^1'^-0+ ai2G<;(6+1))(i-i'))¿5(0- (1)

о

Отметим интересное свойство последовательности состояний среды в моменты освобождения системы.

Теорема 10.Пусть оц ф а2Тогда Gik(oo) ф ац хотел бы <?ля одной пары I, k е. {1, 2}.

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

оо ...

его окончании состояние среды станет е^ равна £ Рх G%(t), где G/*(i) —

решение уравнений (1).

В третьем разделе изучается система управления т < оо конфликтными формируемыми в случайной среде потоками Пь П2, ..., Пт в классе алгоритмов с разделением времени и переналадками. Предположения относительно среды такие же, как и в предыдущей модели, только смена состояний может происходить уже в моменты окончания актов обслуживания и актов переналадок. При состоянии среды е'*' требования по потоку П_,, j — 1,2, ..., m, поступают группами так, что поток групп есть простейший с параметром а распределение числа заявок в группе имеет

производящую функцию ff\z) = |л| < 1 + £ для некоторого

с=0

е > 0. После обслуживания на фазе j требование может с вероятностью pjr

т

поступить в очередь Or, г = 1, 2, ..., т, а с вероятностью 1 — Pjr = Pjn

Т=1

(n = m, + 1) покинуть систему. Длительность обслуживания одного требования из очереди Oj, или на фазе с номером j = 1, 2, ..., то, задается функцией распределения Bj(t). Вероятностные свойства длительности

переналадки после обслуживания на фазе j определяются интегральной функцией Bj(t). Длительности обслуживания требований и переналадок предполагаются независимыми между собой и от входных потоков требований. Переналадка происходит после каждого акта обслуживания. Если по окончании переналадки очереди пусты, то на обслуживание поступает первое пришедшее требование. Если же по окончании переналадки очереди не пусты и их длины описываются вектором х = (xi, Х2, ..., хт), то немедленно начинается обслуживание заявки на фазе j = h(x). Здесь через h(-) обозначено некоторое заданное отображение целочисленной неотрицательной решетки X = {0, 1, .. .}т размерности го на множество {1, 2, ..., п} такое, что h(x) = j влечет Xj > 0 при j = 1, 2, ..., т. Прообразом точки п является только нулевой вектор. Множество таких отображений обозначим через Н. Напомним, что в случае нулевых очередей система переходит в режим ожидания прихода первой заявки и активной становится та фаза, на которую приходит первая заявка. Функция h(x): X —> {1, 2, ..., п}, определяющая порядок обслуживания требований в системе, называется функцией переключения фаз обслуживания.

В качестве дискретной временной шкалы выбрана последовательность {г,; i = 0, 1, ...}, где то = 0 и rj, г — 1, 2, ..., есть либо момент окончания обслуживания, либо момент окончания переналадки. С использованием кибернетического подхода построена математическая модель в виде векторной случайной последовательности {(Г„ X;, г = 0, 1, ...}, где X, — состояние среды на промежутке (т;, т,+1], Xi £ X вектор, описывающий длины очередей в момент Т{. Г, € {Г'1', Г'2', ..., Г'"'} — состояние обслуживающего устройства на промежутке (r,-„i, т,]. Эта последовательность является неразложимой периодической марковской цепью с двумя циклическими подклассами, отвечающими соответственно состоянию обслуживания требования и состоянию иереналадки. Предполагается также, что 1) первичное требование, поступившее в любую очередь с положительной вероятностью покидает систему через конечное число повторных обслуживаний; 2) длительности обслуживания и переналадок имеют конечные первые и вторые моменты /3,1, /3,2, Pji, j = 1, 2, ..., го; и 3) распределение числа требований в группе по потоку П, при состоянии среды е'*' имеет конечные первый и второй моменты ц^, ^ ■ Введем обозначения: Q = (Pr})rt]=T~m> Е ~ единичная матрица размерности го х го. Пусть Т - символ транспонирования. Введем следующие величины и векторы: для к = 1, 2 и j = 1, 2, ..., m /?_ = min Д.i, Р+ = max pri, Р_ =

l^r^m l^r^m

• H ~a H T<*) x C*) (« TW /"Г<*) TW T<fc)\T

= ,И"П pr 1, p+ = max prl, A = А) 'ц) ', A = ^ , A2 , ..., A„ )r,

P = (Аь Ai, • • •, A»i), P = (Piи Ai. • • •. Pmi), P(t) = P(E - QT)-l^k\

Большое количество достаточных условий получаются из следующий теоремы.

Теорема 13. Пусть существуют положительные числа 0\, 02, ■ , 0т

2 _

такие, что для вектора в = {0\, 02, ■ ■ ■, 0т) имеет место ^ ак1(Р^0(Е—

1-= 1

- д)-1^0 + Рп0{Е - д)"1^) - в, < 0 при к = 1, 2 и з = 1, 2, ..., т. Тогда марковская цепь {(Г„ х,, г = 0, 1, ...} имеет единственное стационарное распределение.

Приведем некоторые из таких условий для цепи {(Г„ н„ х,); г = = 0, 1, ...}.

Теорема 14. Для существования стационарного распределения достаточно выполнения либо для к = 1,2 неравенства + < 1, либо для ки к2 £ {1, 2], кх ± к2, неравенств + р(к^ < 1 < р(*г)

+ + Р**'1 - I) + ак1к2(3+(рЫ + р<*'> - 1) < 0, +

+ /М(р(*з) + Р^' - 1) + ак,к1р_(р{к,) + - 1) < 0.

Теорема 16. Для существования стационарного распределения достаточно выполнения неравенств аи/?+Р<1) + а120+Р(2) + /?_(/>(1) - 1) < 0. а^0+Р{2) + а21/?+Р(1) + /?-(р(2) - 1) < 0.

Общее необходимое условие содержится в следующей теореме.

Теорема 20. Для существования стационарного распределения марковской цепи {(Ц, щ, х,); г = 0, 1, ...} необходимо либо выполнение неравенств р*1' < 1, р(2> < 1, (р(1)а21+р(2)а12)(а12+а21)_1_< /?+(/?++/?_)-', либо выполнение неравенств ^ 1 < р'2\ а21рС'(/?+ + 0-) + а12Р^2\0- + + /?_) < а21/3+ + а 120-, наконец, либо выполнение неравенств ^ 1 < < Р(1), а21Р(1)(/3- + Р-) + а.2Р(2)(Л + ¡5-) < «12/?+ + 0.2x0-.

Условия существования стационарного распределения допускают простую наглядную интерпретацию. Разбору всех возможных случаев посвящен остаток третьего раздела.

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

Будем говорить, что состояние системы обслуживания не зависит от состояния внешней среды в стационарном режиме, если для всех I, к € 6 {1, 2}, { / к, в = 1, 2, ..., п и V) е X имеет место равенство

Фк)н = {а12а+а21)^'' "М + Ф2)М), (2)

где — стационарная вероятность состояния ги, е'*').

Теорема 22. Пусть ац Ф 0.21, изучаемая цепь имеет стационарное распределение и существует такое V = (ь\, г^, ..., ьт), < 1, ^ = 1, 2, ..., т, что выполнены неравенства ф ф <т|2*(г>),

Д(1) д(2) т ,,(1)

З^)/]1^) Ф «, ™™нец, £ V) -

* 0. состояние системы 1,,

ния и состояние внешней среды являются зависимыми случайными элементами относительно стационарного распределения.

Теорема 23. Для выполнения равенства (2) при I, к € {1, 2}, I ф к,

8 = 1, 2,......, п и и) € X достаточно выполнения условия Оц - «21-

Две приведенные теоремы накладывают сильные ограничения на класс систем, в которых может наблюдаться свойство независимости состояния системы обслуживания от состояния среды в стационарном режиме. Это ограничения на случайную среду и ограничения на входные потоки. Равенства ац = а21 и в12 = «22 означают, что матрица переходных вероятностей содержит одинаковые строки Легко подсчитать, что числа, стоящие в строках, будут совпадать со стационарным распределением для соответствующей марковской цепи. Переходные матрицы такого вида называют стационарными. Поэтому естественно случайную среду называть стационарной, если ее переходная матрица стационарна. Итак, стационарности случайной среды достаточно для того, чтобы состояние системы обслуживания было независимо от состояния среды в стационарном режиме. Для стационарной случайной среды можно привести явные формулы для стационарных вероятностей некоторых событий. Обозначим нулевой вектор (0, 0, ..., 0) € {0, 1, .. .}т, стационарную вероятность события {ш: Г,(и>) = Г^), Хг(ш) — е'*^} через стационарную вероятность события {ш\ Г<(ш) = Г(п), Н(ъ{и))) = = е<*)} через Ф^ и по-

ложим ШГ<*> = (ЯЛ**', <Я^к), ..., Ш = (Ши Ш12, ..., Шт)Т =

= ОТО + ОТ'2», Ф<*> = (Ф<к), ..., ф = (Фь ф2, ..., фт)т = = ф(0 + «го ф<«=) = ф<*> + ф^/х™, Ф« = (Ф<*>, Ц\ ..., т?як = £ *)(и>), х"к = £ У)аф к\и)), х™ = х™х + х™2, х™ =

= х^+х"2, 3, 9 = 1, 2, ..., тп, Л<*> = (Л« Л<".....ЛЙУ =

= (Е - д7')-'^*', А?> = Л« + А§> + ... + лй>, к = 1, 2. Можно мыслить величину

Л«

как суммарную интенсивность поступления требований в ]-ю очередь при состоянии среды е'*'.

Теорема 24. Пусть ац = «21 ив системе существует стационарное ¡мгщмчклеиие. Тогда

а{п)(у{п)) = - <*(Р{1)+- (1 - «)(р(2)+- о)

_ + р<") - л< V +г<2>)) + «л<<>1±|^+ +

МХ(1) I (1 - (1) ,л,2)Л"'

+ (1 - а)Л\.'—^---л®-У( + ( ' + }У '

аЛ'1) + (1 — а)Л'2' <*(1 — а ~ 2(аЛ!|!) + (1 - а)Л+') аЛ^ + (1 - а)Л(+2) *

А+/ЗЛ'1' 1 V А<"

+ /ЗЛ(2)\

а?> )■

Найденные выражения для вероятностей не зависят от выбора функции переключения Л(-).

Из этой теоремы следует, кстати, что при А*'' = А^2' имеем р'1' = р*2', р(') = р'2); Л'1' = Л<2>, л£> = Л?1 и для существования стационарного распределения в этом случае необходимо выполнение неравенства р'1' + р*1' <

, тт т<1)^т<2> 1 + /?А(1) 1 + /ЗА'2' < 1. Пусть теперь А ф А , но -^— = --щ—. И в этих предположениях очевидно простое необходимое условие существования стационарного распределения: +/5*1') + (1 — а)(р'2' + р^) < 1. Вероятность включения любой фазы обслуживания также зависит только от отношения усредненной интенсивности поступления заявок в эту фазу к усредненной интенсивности поступления заявок во все фазы. Этот пример показывает, что условие А^'' = А^2' не является необходимым для независимости состояния системы обслуживания от состояния среды в системах с обсуждаемым специальным типом внешней среды.

Рассмотрим теперь случайную среду с оц ф а21. Пусть стационарное распределение существует и выбрано в качестве начального. Обозначим С]*» = х,Н = еЩ)-ак,кх^,1({ш: = е<*'>})), С<*> -

= (с<*>, с*£\ ..., с%])Т,с<*> = (с[к\ с?\ с«])т = (е

. Величина С: пропорциональна избытку или недостатку среднего числа заявок в очереди С>;- при состоянии среды г'*' по сравнению со средним числом заявок в той же очереди при противном состоянии среды. Для к и / из {1, 2} выберем /', к' из {1, 2} так, чтобы 1ф1',кфк'.

Теорема 24. Пусть стационарное распределение существует и ац ф ф «21. Тогда имеют место соотношения:

= у(_+__| - &к)

\2Л+(012 + 021) Л?(1-а12-а21)/

у. ^^-^(.-^-^о-,

гЛ^а + аг,) V Л+' /

С?<"'*)(1/(п)) = а^ ( С{к)___

(а12+а21) Л^(1 - а12 - аи) 2Л(+к)(а12 + а21)

_у

- а12 - а21) /

-

+ — а!2 — <221)^ " ^ 12ЛГ(а12 + а21) + Х^Г

Следствие 3. Пусть ац ф а21 ы А^ = А^2', тогда имеют место ра-Л(1) £(«,%(»)) д(«. 2)(у(п>) 1 _ рт - р(1)

венства Ш = —777, -тгг--1--тгт-=-тгг-независимо

А+ А<2) 2Л<!>

от выбора функции /г(-).

Следствие 4. Яри А^ = а'2', ац / а21 условие р^ + р^1' < 1 является необходимым и достаточным для существования стационарного распределения.

Пусть обозначает суммарное время пребывания заявок в очереди 03 на интервале (т„ 75+1]. Пусть далее обозначает время пребывания в

очереди 02 заявок, поступивших не позднее момента ~ время пре-

бывания в очереди 0} заявок, поступивших за такт работы системы на интервале (т„ т.-ц]; наконец, — время пребывания в очереди 0} заявок, поступивших на интервале (г,, т,+1] до начала обслуживания. Имеем очевидное равенство = + С^] + Тогда средняя стоимость

' ' ' т

пребывания заявок на интервале (т„ 75+1] есть Л(Л) = Заме-

ть

тим, что выбранный функционал отличается от функционала из работы Г.П. Климова (см. Климов Г.П. Системы с разделением времени. // Теория вероятностей и ее применения. Т. 19, вып. 3. 1974 г. С. 558-576), в которой рассматривается задача минимизации средней стоимости в единицу времени пребывания всех требований в системе за достаточно большой промежуток времени в стационарном режиме. Теперь, если в качестве начального распределения выбрать стационарное, то выражения для М^1], и, следовательно, для Дф) не зависят от номера ¿.

Теорема..2Выберем стационрное распределение в качестве началъно-

, . тп __. . 2 тп ...

го. Тогда для j = 1,2, ... ,тп М<.( ] = £МС(2|= ЕЕ^х

г=1 к=1 г=1

х /я?»! Ф =

0 0 + Пусть ац = Й21- Тогда из теоремы следует, что величины не зависят от управления. Далее, функционал качества работы системы в стационарном режиме имеет вид:

т т

ЛИ) = + + сопз1 (3)

}=1 г=1

и минимизировать нужно первое слагаемое, которое линейно по переменным хг]. Заметим, что хгз ^ 0 для всех г, Чтобы полностью поставить задачу оптимизации, найдем ограничения, которым необходимо должны удовлетворять величины хтз.

Теорема 27. Пусть 011 = агь Тогда величины х91, д, } = 1, 2, ..., ... ,т, удовлетворяют системе уравнений

т

х93 +Х39- + йТяхТЗ) = с?3, (4)

г=1

где йгя = (ацА^ + а12А^2')(/3Г1 + /Зг1) +ргд, константы с?1 не зависят от отображения Л(-) и с?3 = о79.

Итак, для системы, функционирующей в стационарной среде, получена следующая задача линейного программирования: найти минимум функционала

т т }=1 г=1

при линейных ограничениях (4) и ограничениях хгз > 0. Задача линейного программирования такого класса впервые была решена Г. П Климовым в цитированной работе. Это позволяет построить алгоритм оптимального управления потоками в системах с разделением времени в случае стационарной случайной среды.

Аналогичная задача линейного программирования получается и для случайной среды общего вида при некоторых дополнительных предположениях относительно входных потоков. Из теоремы следует, что при Л*1' = = Л<2) величины не зависят от управления. Функционал каче-

ства работы системы в стационарном режиме имеет тот же вид (3).

3Даннм теорема следует из теоремы 26, которая здесь не приводится

Теорема 28. Пусть ап ф а2Ь А0' = А*2', А^/^ = ^Чг- Тогда величины х'я, д, j = I, 2, ..., ш, удовлетворяют линейным соотношениям

т

¿9 + Х93 _ ^{<Г9ХГ1 + ^хТа) = 0>Я, (5)

Г=1

где <ГЯ = + /?г1) + ртд, д>9 не зависят от выбора Л(-) и р>я = .

Полученная задача оптимизации функционала ^{Ь) при линейных ограничениях (5) и ограничениях х9* ^ 0, д, ] = 1, 2, ..., т., отличается только видом коэффициентов от задачи оптимизации в стационарной случайной среде. Поскольку выбранный на обслуживание тип заявки зависит от существующих на данный момент длин очередей, то класс всех допустимых управлений не совпадает с классом приоритетных управлений, а шире его. Однако оптимальным управлением оказалось приоритетное управление. Более того, оптимальное приоритетное управление инвариантно относительно внешней среды.

В пятом разделе изучение системы продолжается средствами имитационного моделирования. Поскольку общая модель содержит большое количество параметров и время моделирования существенно зависит от числа потоков в имитируемой системе, проводится исследование систем с различным числом входных потоков, причем учитываются оценка средней стоимости пребывания требований за такт, оценка загрузки системы и оценка среднего времени пребывания в системе произвольного требования. Для определенности длительности обслуживании и переналадок были распределены по закону Эрланга, а число входных потоков не превышало пяти. С целью оценивания стационарных характеристик моделирование одной траектории эволюции системы проводилось в два этапа. На первом этапе определялся момент вхождения системы в квазистационарный режим. Для двух систем по наблюдениям за выходными потоками вычислялись оценки среднего времени пребывания произвольного требования в системе Рис. 1 демонстрирует изменение оценок среднего времени пребывания в зависимости от числа покинувших систему требований. Единица по оси абсцисс в данном случае соответствует 30 требованиям. При этом в первой системе в начальный момент времени очереди пусты (линия 1), а во второй системе в начальный момент в каждой очереди находятся по 25 требований (линия 2). Сближение оценок на величину, определяемую выбранной точностью (в данном случае, 15 %), интерпретировалось как наступление квазистационарного режима. В момент наступления квазисгационарного режима находились длительность переходного процесса и оценка р загрузки системы. На втором этапе, продолжающем траекторию первого этапа, находились оценка 3 средней стоимости пребывания заявок в системе за один такт, оценка у среднего времени пребывания в системе произвольно-

го требования, оценка % дисперсии среднего времени пребывания в системе произвольного требования, оценка *'(?/"') вероятности к = 1, 2, оценка Ш® вероятности Ш(к\ ] = 1, 2, ..., т, к = 1, 2, оценка 3

средней длительности периода занятости системы, оценки к) величин {а;: х,(а>) = е'*'}). На основании центральной предельной теоремы по нескольким реализациям оценивались границы 95 %-х доверительных интервалов для изучаемых характеристик Аналитически вычислить оцениваемые величины нельзя. Таким образом, программа позволяет проводить численную оптимизацию управления системой по двум критериям: критерию минимального времени пребывания произвольного требования в системе и критерию минимальной стоимости пребывания требований в системе за один такт.

При решении задачи численной оптимизации выяснилось, что практически всегда оптимальный алгоритм управления системой совпадает с тем, которой был найден в аналитическом исследовании ограниченного класса систем. При этом оптимальные управления для обоих критериев совпали. На рис. 2 приведены оценки среднего времени пребывания произвольного требования (ось ординат) для различных управлений. Обслуживанию самой длинной очереди соответствуют точки с абсциссой 0, шести возможным приоритетным управлениям соответствуют точки с абсциссами 1-6. Линиями соединены точки, соответствующие одному набору параметров среды, потоков и обслуживания. При этом оценки загрузки для различных линий составили 8 %, 33 % и 80 %. Видно, что выигрыш от использования оптимального управления тем больше, чем больше загрузка системы. Изучение оценок Фп,к\у№), к) обнаружило слабую зависи-

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

3. ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

200 300 «00 500 МО

Рис. 1 Рис. 2

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

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

4. СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Зорин, A.B. Общий вид неординарного потока, управляемого марковским процессом / А. В. Зорин // Вычислительная математика и кибернетика 2000: Конференция, посвященная 80 летию Ю. И. Неймарка. — Нижегородский государственный университет им. Н. И. Лобачевского, 2000. - С. 41

2. Зорин, A.B. Входной поток, управляемый марковской цепью/A.B. Зорин; Нижогор. ун-т. — Нижний Новгород, 2001. — 15 с. — Деп. в ВИНИТИ 15.05.01 No.l253-B2001.

3. Фодоткин, М. А. Об оптимальном управлении процессом с разделением времени в случайной среде / М. А. Федоткин, А. В. Зорин // Мате-

матика и кибернетика 2003. Сборник научных статей юбилейной научно-технической конференции факультета ВМК ННГУ и НИИ ПМК. Нижний Новгород, 28-29 ноября 2003 г. - Нижний Новгород, 2003. - С. 269-273.

4. Зорин, А. В. Статистический анализ систем с разделением времени, функционирующих в случайной среде / A.B. Зорин, М. А. Федоткин // Прикладная статистика в социально-экономических проблемах. Материалы Международной конференции (Нижний Новгород, 14-15 февраля 2003 г.) В 2-х томах. - Т. I. — Нижний Новгород, 2003. - С. 73-75.

5. Зорин, А. В. Анализ процессов с разделением времени / А. В. Зорин, М. А. Федоткин // Вестник Нижегородского университета им. Н. И. Лобачевского. Серия Математика. — Т. 1, No. 1. — 2003. — С. 18-28.

6. Зорин, A.B. Процессы с разделением времени в случайной среде / А. В. Зорин, М. А. Федоткин // Международная конференция "Колмогоров и современная математика" (Москва, 16 21 июня 2003 г.), посвященная 100-летию со дня рождения Андрея Николаевича Колмогорова. Тезисы докладов. - М., 2003. - С. 635-636.

7. Зорин, А. О существовании стационарного распределения для процессов с разделением времени в случайной среде / А. Зорин // Массовое обслуживание. Потоки, системы, сети: Междунар. науч. конф. "Современные математические методы анализа и оптимизации телекоммуникационных сетей" 23 25 сентября 2003 г., Гомель. Вып. 17 / Под ред. Медведев Г. А. (отв. ред.) и др. - Мн.: ВГУ, 2003. - С. 274-278.

8. Зорин, А. В. Система с разделением времени в условиях изменения структуры обслуживающего устройства и структуры входных потоков / А. В. Зорин, М. А. Федоткин; Нижегор. ун-т. — Нижний Новгород, 2003. — 22 с. - Деп. в ВИНИТИ 19.09.03 No.l704-B2003.

9. Zorine, А. V. Optimal control of a time-sharing process in a stationary random environment / A.V. Zorine, M. A. Fedotkin // Сборник тезисов докладов VI Международного конгресса по математическому моделированию. — Нижний Новгород, 2004. — С. 136.

10. Зорин, А. В. Анализ и оптимизация процессов с разделением времени, функционирующих в случайной среде / А. В. Зорин, М. А. Федоткин // Вестник Нижегородского университета им. Н. И. Лобачевского. Серия Математика. - 2004. - No. 1. - С. 92-103.

11. Fedotkin, М. A. Optimal control of conflict flows with repeated service / M.A. Fedotkin, A.V. Zorine // Transactions of the XXIV International Seminar on Stability Problems for Stochastic Models / Под ред. Victor Korolev, Alexander Andronov, Pavel Bocharov. - Riga: TTI, 2004. - P. 126-132.

12. Зорин, А. В. Об оптимальном управлении процессами с разделением времени в случайной среде / А. В. Зорин, М. А. Федоткин; Нижегор. ун-т. — Нижний Новгород, 2004. - 58 с. - Деп. в ВИНИТИ 29.06.04 No.ll20-B2004.

13. Зорин, А. В. О периоде занятости системы с дважды стохастическим

входным потоком / А. В. Зорин // Вестник Нижегородского университета им. Н. И. Лобачевского. Серия Математика. — 2005. — Вып. 3. — С. 43-53.

14. Зорин, A.B. Оптимизация управления дважды стохастическими неординарными потоками в системах с разделением времени / A.B. Зорин, М. А. Федоткин // Автоматика и телемеханика. — No. 7. — 2005. — С. 102-111.

1

1

!

V

I

Подписано к печати 23.11.2005. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1. Заказ 1593. Тираж 100.

Типография Нижегородского госуниверситета им. Н.И. Лобачевского. Лицензия № 18-0099 603000, Н. Новгород, ул. Б. Покровская, 37.

¿г

» 30

Введение

I. Неординарные потоки в марковской случайной среде.

1.1. Основные виды входных потоков.

1.2. Модель неординарного потока, вероятностная структура которого задается марковской цепью.

I.3. Общий вид производящих функций и мгновенная интенсивность потока 20 ^ II. Кибернетический подход при изучении систем обслуживания немарковского потока.

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

11.2. Арифметические свойства векторной случайной последовательности, описывающей динамику состояний немарковской среды и флуктуацию длин очередей.

11.3. Предельные свойства векторной случайной последовательности, описывающей поведение системы обслуживания

11.4. Период занятости системы.

III. Дискретные управляющие системы обслуживания немарковских потоков в классе алгоритмов с разделением времени

III. 1. Постановка задачи на содержательном уровне и описание системы с ис-4 пользованием кибернетического подхода.

111.2. Построение управляемой векторной марковской цепи.

111.3. Необходимые и достаточные условия существования стационарного распределения

111.4. Графическая интерпретация условий существования стационарного режима системы.

IV. Оптимальное управление в стационарном режиме.

IV. 1. Исследование стационарного распределения с точки зрения независимости состояния среды от состояния системы обслуживания.

IV.2. Получение явных формул и функциональных соотношений для стационарного распределения состояний системы.

IV.3. Вычисление экономического критерия качества и оптимальное управление в случае стационарной случайной среды.

IV.4. Вид экономического критерия качества в случае постоянных интенсив-ностей первичных потоков и решение задачи оптимизации.

V. Имитационное моделирование системы в случае эрланговского распределения длительностей обслуживаний и переналадок.

V.I. Планирование имитационного эксперимента.

V.2. Сравнение различных алгоритмов управления в случае зависимости интенсивностей первичных потоков от состояния нестационарной среды

V.3. Качественное исследование основных характеристик имитационной модели в зависимости от параметров системы и алгоритма управления потоками

Характеристика изучаемой темы в целом

Начало исследования процессов образования очередей пришлось на первую половину двадцатого века. Общепризнано, что пионерские работы в этой области принадлежат датчанину А. К. Эрлангу, построившему в 1908-1922 годах математическую модель работы автоматических телефонных станций и объяснившему природу задержек абонентов этих станций [1]. Фундаментальные исследования по теории очередей, или теории массового обслуживания, принадлежат многим видным математикам XX века — JI. Такачу, T.JT. Саати, Д-Р. Коксу, У. Д. Смиту, JI. Клейнроку, Дж. Ф. Кингмэну, Ф. Поллачеку, Д. Дж. Кендаллу, М. С. Бартлетту и др., в нашей стране — прежде всего, А. Я. Хинчину, А. Н. Колмогорову, Б. В. Гнеденко, Ю. В. Прохорову, А. А. Боровкову, И. Н. Коваленко, Г. П. Климову, А. Д. Соловьеву, Г. П. Башарину, Б. А Севастьянову, Ю. К. Беляеву. Результаты теории массового обслуживания представлены во многих монографиях, например [2, 3, 4, 5, 6] и др.

Рост интереса к теории массового обслуживапия связан прежде всего с научно-техническим прогрессом цивилизации в XX веке. Начав с автоматических телефонных станций, исследователи обратились к задачам описания транспортных потоков, таких как автомобильное движение, работа крупных международных аэропортов, речное движение и работа портов, а также к различным задачам управления производством (классическая задача о станках А. Я. Хинчина). С появлением во второй половине XX века сложных электронно-вычислительных комплексов возникла задача оптимального распределения ресурсов процессоров, памяти и периферийных устройств в таких системах, что привело к постановке новых задач теории массового обслуживания.

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

Опишем те направления теории массового обслуживания и те классы задач, на пересечении которых находится предлагаемая диссертация.

В вычислительно-информационных системах с шестидесятых годов стали разрабатываться так называемые системы разделения времени [7], дававшие доступ к вычислительным ресурсам нескольким пользователям одновременно, а зачастую и пользователям, находящимся на значительном удалении от вычислительного комплекса. Примерно в то же время стали появляться математические работы, посвященные исследованию систем обслуживания в классе алгоритмов с разделением времени. В работе [8] Ю. К. Беляевым рассматривается простейшая модель системы с разделением времени. Предполагаются простейший входной поток и показательное распределение времени обслуживания. Требование в системе обслуживается не дольше фиксированного кванта

• времени, причем если по окончании кванта требований в системе нет, то обслуживание требования продолжается. Если же в системе будут находиться другие требования, то обслуженное требование встанет на ожидание в конец очереди. В 1963 году появилась работа JI. Такача [9], в которой исследовалась система с одним входным пуассоновским потоком, произвольным временем обслуживания и бернуллиевской обратной связью. Суть бернуллиевской обратной связи заключается в том, что каждое требование после обслуживания с заданной вероятностью возвращаесть в очередь, а с противоположной вероятностью покидает систему. В последующие годы появилось множество работ, в том числе и монографий, посвященных изучению вычислительных комплексов методами теории массового обслуживания [10, И, 12, 13, 14, 15, 16, 17, 18, 19, 20]. В 1974 году Г. П. Климов опубликовал статью [21] (а также [22]), в которой был приведен алгоритм оптимального управления пуассоновскими потоками разнотипных требований в классе алгоритмов с разделением времени по критерию минимальной стоимости пребывания

• требований в системе в единицу времени. В частности, было показано, что оптимальное управление лежит в классе управлений с относительными приоритетами. Эта задача была обобщена В. В. Рыковым [23] на случай ветвящегося потока требований на повтор

4 ное обслуживание. М. А. Федоткин [24, 25] рассмотрел похожую систему с разделением времени в предположении, что после каждого обслуженного требования прибору требуется переналадка. Выбрав в качестве критерия эффективности среднюю стоимость пребывания всех требований в системе за один такт работы системы, он показал, что оптимальное управление очередями может быть найдено с использованием алгоритма Г. П. Климова. Отметим, что в данном случае минимизация функционала Г. П. Климова и отличного от него функционала М. А. Федоткина привела к одному оптимальному управлению. Система с разделением времени с переналадками и неординарными входными потоками бартлеттовского типа исследовалась в [26]. Было показано, что

• оптимальное управление в смысле функционала М. А. Федоткина также находится по алгоритму Г. П. Климова. В [27] решена задача определения порядка выбора требования на обслуживание по информации о длинах очередей на момент принятия решения, при котором минимизируется заданная функция от средних длин очередей. Эта задача обобщает задачу В. В. Рыкова путем усложнения вида функционала. Наконец, в [28] рассматривается модель Г. П. Климова для двух потоков, описываемых произвольным точечным процессом, и экспоненциального обслуживания.

После [9] системы с обратной связью изучались многими авторами. Так, в [29] изучалось распределение времени пребывания требования в системе с обратной связью.

В [30] рассмотрена модель, в которой существуют простои прибора и пороговые политики, а распределения времени обслуживания требования в первый раз отличается от распределения времени повторного облуживания. Если в системе требования нет, то прибор отключается на случайное время. Если при включении прибора требования в системе есть, то они начинают обслуживаться. Если требований нет, то прибор снова выключается. При условиях, гарантирующих существование стационарного режима работы прибора, были исследованы длина очереди и распределение времени ожидания, а также другие характеристики. В недавней работе [31] рассмотрена система с пуас-соновским входным потоком, произвольным временем обслуживания, неограниченной очередью, и двумя фазами обслуживания. Первая фаза предоставляется всем потребителям, и после обслуживания на ней требование с заданной вероятностью поступает на обслуживание во вторую фазу, либо покидает систему. Система с повторным обслуживанием, в которую вызовы извне не поступают, была рассмотрена в [32]. Система с разделением времени на языке сетей обслуживания изучается в [33]. В предположении, что обслуживание в каждом узле экспоненциально, анализируется время ожидания ответа и пропускная спопобность.

Поскольку в реальных системах обслуживания присутствуют требования различных типов, например, по характеристикам длительности обслуживания, или по стоимости ожидания в очереди, большой интерес вызывали и вызывают системы приоритетного обслуживания. Результаты исследования таких систем собраны в [34, 35, 36]. К приоритетным системам относятся прежде всего системы с абсолютными приоритетами и системы с относительными приоритетами. В первом случае поступление более приоритетного требования прерывает обслуживание менее приоритетного требования, а во втором случае не прерывает. В [37] и других работах впервые рассматривались системы со смешанным приоритетом. В таких системах прерывание обслуживания менее приоритетного требования происходит только если более приоритетное требование поступает не позже фиксированного промежутка времени с начала обслуживания. Интересно было выяснить, каков должен быть этот фиксированный промежуток времени (так называемая точка переключения), чтобы стоимость пребывания требований в системе была минимальна. Было установлено, что при экспоненциальном времени распределения времени обслуживания оптимальным является система с относительными приоритетами, то есть точка переключения находится в бесконечности. Также было найдена конечная точка переключения для некоторых других типов распределения времени обслуживания: эрланговского, постоянного и др. Интересно отметить ряд новых исследований по системам без привычной очереди, но с так называемой "орбитой", на которую отправляются требования, заставшие прибор занятым. Такие требования в случайные моменты времени обращаюся с повторными попытками занять прибор и в случае неудачи возвращаются на орбиту. В работе [38] рассматривается такая система с требованиями двух типов. Требования поступают по независимым пуассоновским потокам и при занятом приборе помещаются на орбиту конечной вместимости. Интересно, что для требований установлен невытеснительный (non-preemprive) приоритет, при котором прибор сначала ищет на обслуживание требования первого типа, и только при отсутствии таковых начинает искать требования второго типа. Поиск требования занимает случайное время. В этом можно усмотреть идейную связь с классом систем с переналадками, ориентацией прибора. Целью статьи является алгоритм для вычисления стационарных вероятностей марковской цепи, описывающей эволюцию системы, интенсивности выходного потока и других показателей производительности системы.

Приоритетная обратная связь изучается в работе [39]. Приоритетные системы с марковскими входными потоками рассматриваются, например, в [40, 41, 42] и др. В частности, в [43] для однолинейной системы с двумя марковскими входящими потоками и накопителем ограниченной емкости рассматривается дисциплина обслуживания с относительным приоритетом. Особенностью системы является то, что распределение длительности обслуживания заявок каждого типа зависит от длин количеств требований каждого типа в начале обслуживания. Для вычисления стационарных вероятностей состояний применяется матричный алгоритм.

Применения в моделях ЭВМ находят алогоритмы приоритетного обслуживания с ориентацией [44]. Наличие ориентации (переналадки) учитывает тот факт, что переход обслуживающего устройства от одной очереди к другой не может происходить мгновенно. В [45] учитываются потери на переключение прибора для обслуживания требований и освобждепия прибора по окончании обслуживания для алгоритма с относительным приоритетом. Находятся характеристики системы на цикле обслуживания.

Оптимальному назначению приоритетов в системах обслуживания придается особое внимание. Однолинейная система с несколькими пуассоновскими входными потоками и с потерями требований рассмотрена в [46]. В статье решается задача минимизации доли потеряных требований. Рассматривались варианты абсолютных приоритетов и бесприоритетного обслуживания. В [47] исследовалась система с динамическими приоритетами, то есть такая система, в которой правило выбора требования на обслуживание определяется разбиением пространства состояний очередей на области. Входные потоки также пуассоновские. Обслуживание происходило без прерывания, требования размещались в накопителях неограниченного объема. Обслуженные требования сразу покидали систему. Требовалось найти оптимальное разбиение на области, обеспечивающее минимум средней стоимости пребывания всех требований в системе в единицу времени. Основой анализа служила вложенная цепь Маркова, для которой находились стационарные вероятности попадания в области, отвечающие различным решениям о выборе требования на обслуживание. Выяснилось, что оптимальным является алгоритм с простыми приоритетами, назначать которые нужно по сведениям о средних длительностях обслуживания и стоимости пребывания в каждой очереди в единицу времени. Отметим, что задача, решенная Г. П. Климовым в [21], является обобщением задачи о динамических приоритетах на случай повторно обслуживаемых требований (то есть обратной связи). Вопрос об оптимальном управлении системой в классе динамических приоритетов с прерыванием рассмотрен в статье [48]. Основной вывод статьи — оптимальное управление то же, что и в предыдущем случае. Итоговой явилась работа [49]. В ней исследуются свойства общей схемы обслуживания, частными случаями которой являются, кроме двух описанных выше, обслуживание одной очереди до исчерпания всех требований этой очереди, обслуживание всех требований одной очереди, присутствующих в момент начала ее обслуживания, и др. Показано, что особое упорядочивание очередей по относительным приоритетам всегда является оптимальным. Основным исследовательским приемом является сведение задачи оптимального управления к конечномерной задаче линейного программирования.

Теория приоритетных систем сближается с теорией управляемых систем массового обслуживания. Общее понятие управляемой системы обслуживания введено О. И. Бронштейном и В. В. Рыковым. К таковым системам относятся системы с управляемым входным потоком, системы с управляемым механизмом и длительностями обслуживания, системы с управляемой структурой, системы с управляемой дисциплиной обслуживания. В качестве целей управления выступают самые разнообразные функционалы. Часто используются линейные функционалы от среднего числа требований в системе в произвольный момент времени [21], линейные функционалы от среднего времени пребывания требований за такт работы системы [24], функционалы общего вида от среднего числа требований в системе в произвольный момент времени [27], линейный функционал потерь [50], функционал дисконтированных потерь [51, 52, 53, 54]. В работе [55] изучается класс систем параллельного обслуживания требований, работающих при высокой нагрузке. Найдены оптимальные дисциплины обслуживания, минимизирующие среднее суммраное количестко работы. Обзор результатов по управляемым системам массового обслуживания содержится в [56]. В последнее время уделяется внимание изучению свойств решений возникающих задач оптимизации. В работе [57] рассматривается система из нескольких параллельных очередей, обслуживаемых одним прибором. Время перехода прибора от одной очереди к другой случайно. Считаются извстными стоимости переключений и стоимости единицы времени пребывания одного требования в каждой очереди. Рассматривается дисциплина переключения, которая основывается на знании поведения очередей до настоящего момента. Показано, что введение интервала простоя способно улучшить характеристики переключения для некоторых дисциплин, однако для оптимальной дисциплины в смысле средней стоимости функционирования в единицу времени это не так. Показано, что при оптимальной дисциплине характеристики монотонны по отношению к интенсивностям входящих потоков, к некоторому стохастическому упорядочиванию длительностей переключения и длин требований. Важность исследования качественных свойств оптимального управления отмечается В. В. Рыковым в статье [58]. Автором ставится задача дискретной оптимизадии применительно к моделям управляемых систем обслуживания. Для системы с несколькими неоднородными приборами исследуются условия, при которых возможен монотонный выбор оптимального решения задачи.

Еще один тип алгоритмов, учитывающих переналадки, заключается в обслуживании одной очереди до некоторой степени ее истощения, и только после этого в переходе к следующей очереди, как, например, в работе [49]. Системы с таким алгоритмом управления получили название систем опроса (polling systems) [59, 60, 61]. Такие системы можно рассматривать одновременно как сети обслуживания, в которых обслуживающее устройство переходит от одной очереди к другой. Анализ длин очередей в случае тандемной конфигурации проводился, например, в [62, 63]. Другая конфигурация, в которой две параллельные очереди перенаправляют требования в третью очередь, рассмотрена в [64]. Общие модели систем, в которых обслуживающий прибор всего один и выбор очереди на обслуживание осуществляется по фиксированным приоритетам, изучались в [65, 66]. Многие авторы рассматривали системы опроса, в которых обслуженные требования покидают систему, и, либо переключения происходят мгновенно [67, 68]; либо циклическое обслуживание с немгновенными переключениями [69, 70, 71]; либо обслуживание в случайном порядке [72]. Система опроса с коррелированными моментами поступления требований изучена в [73]. В системах опроса часто применяются две дисциплины обслуживания требований: обслуживание очереди до тех пор, пока она не опустеет, и обслуживание только тех требований очереди, которые присутствуют там при начале обслуживания этой очереди (так называемая шлюзовая дисциплина). Смесь шлюзовой дисциплины и одиночного обслуживания изучается в работе [74]. Требования к классов поступают по пуассоновским потокам и образуют т групп. Приоритет при выборе очереди на обслуживание учитывает как класс требований, так и группу. В работе изучаются характеристики работы системы в стационарном режиме, предложен алгоритм вычисления среднего времени пребывания требований всех классов в системе. Система опроса с групповым поступлением требований изучается в работе [75], в вызывающие моменты группы поступают во все очереди сразу.

Первые исследования по теории массового обслуживания предполагали самый простой тип входного потока. И это оправдывало себя какое-то время. Например, известно, что в тридцатые годы интервалы времени между движущимися машинами хорошо описывались независимыми экспоненциальными случайными величинами, что приводит к модели пуассоновского простейшего потока. Но уже в 1963 году М. С. Бартлеттом было замечено [76], что реальный поток машин в Лондоне с большой вероятностью не согласуется с гипотезой о пуассоновском потоке. Большинство математических исследований в паши дни используют искусственное усложнение известных математических моделей, заменяя одиночные требования группами требований, независимые одинаково распределенные по показательному закону интервалы — на последовательность зависимых случайных величин, и т.д. При этом исследователи стремятся получить описание состояния потока требований в каждый момент времени, как это делали классики. Так, Д. М. Лукантопи [77] ввел понятие ВМАР-потока, предположив, что интервалы между поступлением групп вызовов зависимы и их распределением управляет вспомогательная марковская цепь с конечным числом состояний и непрерывным временем. Известны и более ранние работы по марковски-модулированным потокам с дискретным временем, например, [78]. В последнее время стали появляться работы, в которых раскрывается фрактальная структура информационных потоков [79, 80]. В настоящее время наиболее часто встречаемой неклассической моделью входного потока является модель группового марковского потока, ВМАР-потока. Ссылки на некоторые работы этого направления встречались выше. В монографии [81] рассматриваются вопросы анализа систем массового обслуживания, функционирующих в случайной среде. Рассматриваемый авторами входной поток — дважды стохастический пуассоновский поток, интенсивность которого принимает значения на конечном интервале и является либо диффузным, либо скач-нообразным процессом. Управление конфликтными потоками на перекрестке в случае, когда потоки формируются в случайной среде, изучались в [82, 83, 84, 85]. При этом рассматривались входные потоки, интенсивность которых неизменна при всех состояниях среды, а смена состояния среды могла происходить только в моменты переключения обслуживающего устройства.

Основные задачи и содержание работы

В данной работе рассматривается система с разделением времени, обобщающая известные системы Г. П. Климова, М. А. Федоткина и А. А. Высоцкого. Отличие заключается в выбранной модели входных потоков. Считается, что входные потоки формируются в случайной среде, которая определяет, поступают ли требования поодиночке или группами, какие распределения интервалов между группами или одиночными требованиями, и наконец, какое распределение имеет число требований в группе. Отличие изучаемой модели среды от известных в литературе заключается в том, что моменты смены состояний среды синхронизированы с моментами окончания работы обслуживающего устройства. Поскольку длительности обслуживаний и переналадок имеют произвольное распределение, процесс изменения состояния среды не является марковским. Принимается, что интервалы между поступлениями групп или одиночных требований распределены по показательному закону, параметр которого для каждого потока зависит от состояния внешней среды. А. А. Высоцкий предполагал конкретный вид распределения количества требований в группе. В предлагаемом исследовании это ограничение снято, но накладывается некоторое условие на область аналитичности производящей функции распределения размера группы. Заметим далее, что наличие переналадок в изучаемой системе с точки зрения изучения математической модели равнозначно наличию "прогулок", "ориентаций11 прибора, однако решение задачи оптимизации оказывается безразличным к наличию или отсутствию переналадок, см., например, [25]. Целью работы является изучение системы с разделением времени с общей позиции управляющей системы и использование кибернетического подхода при построении модели.

Диссертационная работа состоит из введения, пяти разделов, заключения, списка использованной литературы и приложений. В первом разделе строится математическая модель потока, управляемого марковской цепью. Предполагается, что процесс изменения состояния среды является марковским процессом. Подраздел 1.1 содержит обзор классических подходов к описанию входных потоков. В подразделе 1.2 на содержательном уровне описывается неординарный поток, управляемый марковской цепью. Строится его математическая модель. В подразделе 1.3 находятся производящие функции для совместного распределения числа поступивших требований и состояния среды. Вычисляются некоторые характеристики потока. Во втором разделе изучается простейшая система обслуживания с немарковским входным потоком. Отличие этого потока от предыдущего в том, что процесс изменения состояния среды не является марковским процессом. Подраздел II. 1 содержит сравнительное описание классически-го и кибернетического подходов к построению модели управляющей системы массового обслуживания. На примере однолинейной системы обслуживания алгоритмом с разделением времени потока, формируемого в случайной среде, демонстрируются основные этапы следования кибернетическому подходу: приводится схема системы, перерабаты-вамая ей информация, ее координаты и функция. Для рассматриваемого примера в разделе II.2 строится векторная случайная последовательность, описывающая изменение состояния случайной среды и числа требований в очереди. Доказывается, что построенная последовательность является марковской цепью и находятся соотношения, связывающие распределение этой цепи за один шаг. Исследование предельных свойств этой цепи проводится в подразделе II.3. Основной результат этого подраздела — теоремы, содержащие необходимое и достаточное условия существования стационарного режима функционирования системы. Наконец, в предположении, что эти условия выполнены, в подразделе II.4 изучается период занятости системы в терминах преобразований Лапласа-Стилтьеса функции совместного распределения периода занятости системы и состояния среды во время простоя прибора. В третьем разделе строится модель управляемой системы обслуживания нескольких конфликтных потоков в классе алгоритмов с разделением времени. При этом считается, что, как и во втором разделе, входные потоки формируются в случайной среде. Описание функционирования системы в приводится подразделе III. 1. Здесь же выявляются основные компоненты рассматриваемой системы с точки зрения кибернетического подхода. В подразделе III.2 строится математическая модель в виде векторной марковской цепи, описывающей изменение состояния обслуживающего устройства, флуктуацию длин очередей и состояния внешней среды. Арифметические свойства этой цепи выражаются через рекуррентные соотношения для распределения цепи и для производящий функций этого распределения. Проводится классификация состояний цепи. Условия существования стационарно

Основные результаты исследования управляющих систем с разделением времени в случае входных потоков, формируемых в случайной среде, сводятся к следующему.

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

Была поставлена и решена в некоторых важных случаях задача оптимального управления системой по условию минимума средней стоимости пребывания всех требований в системе за один такт работы или переналадки прибора. Оказалось, что оптимальное управление изучаемым классом систем имеет тот же приоритетный характер, как и у известных ранее систем с разделении времени: систем с пуассоновскими входными потоками, систем с переналадками и систем с неординарными входными потоками. Таким образом, был расширен класс систем, в которых это управление оказалось оптимальным.

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

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

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

Заключение

1. Erlang, А. К. Probability and telephone calls / А. К. Erlang // Nut Tidsskrift for Matematik. Ser. B. - 1909 - T. 20. - P. 33-39.

2. Хинчин, А. Я. Работы по математической теории массового обслуживания / А. Я. Хинчин. — М.: Физматгиз, 1963. — 312 с.

3. Климов, Г. П. Стохастические системы обслуживания / Г. П. Климов. — М.: Наука, 1966. 243 с.

4. Гнеденко, Б. В. Введение в теорию массового обслуживания / Б. В. Гнеденко, И. Н. Коваленко. М.: Наука, 1987. - 336 с.

5. Саати, Т. JI. Элементы теории массового обслуживания и ее применение / Т. JI. Са-ати. — М.: Советское радио, 1971. — 520 с.

6. Бочаров, П. П. Теория массового обслуживания / П. П. Бочаров, А. В. Печинкин.- М.: Издательство РУДН, 1995. 529 с.

7. Системы с разделением времени / Под ред. У. Карплюс. — М.: Мир, 1969.

8. Беляев, Ю. К. Труды 6-го Всесоюзного совещания по теории вероятностей и мате-матичсекой статистике. 1960 / Ю. К. Беляев. — Вильнюс, 1962.

9. Takacs, L. A single server queue with feedback / L. Takacs // The Bell System Technical Journal. 1963. - Vol. 42. - P. 487-503.

10. Клейнрок, JI. Вычислительные системы с очередями / JI. Клейнрок. — М.: Мир.- 1979. 561 с.

11. Авен, О. И. Математические модели сложных вычислительных систем / О. И. Авен, Я. А. Коган. // Автоматика и телемеханика. — 1971. — No. 1. — С. 109127.

12. Бронштейн, О. И. Модели приоритетного обслуживания в информационно-вычислительных системах /. О. И. Бронштейн, JI. М. Духовный. — М.: Наука, 1976.- 220 с.

13. Ивницкий, В. А. Сети массового обслуживания в ЭВМ (обзор) / В. А. Ивницкий // Зарубежная радиоэлектроника. — 1977. — Т. 7. — С. 33-70.

14. Артамонов, Г. Т. Аналитические вероятностные модели функционирования ЭВМ / Г. Т. Артамонов, О. М. Брехов. — М.: Энергия, 1978.

15. Димитров, М. Ц. Однолинейная система с групповым обслуживанием в режиме разделения времени / М. Д. Димитров // Сердика. Бълг. мат. списание. — 1978. — Т. 4, No. 4. С. 289-295.

16. Ляху, А. К. Модель работы ЭВМ в режиме разделения времени / А. К Ляху. В.Ф. Матвеев // Изв. АН СССР, сер. Техническая кибернетика. — 1979 — No. 5. С. 59-67,

17. Cohen, J. W. The multiple phase service network with generalized processor sharing / J.M. Cohen // Acta Inform. 1979. - Vol. 12, No. 3. - P. 245-284.

18. Климов, Г. П. Математические модели систем с разделением времени / Г. П. Климов, А. К. Ляху, В. Ф. Матвеев. — Кишинев: Штинца, 1983. — 220 с.

19. Kompton, K.J. Expected deadlock time in a multiprocessing system / K.J. Kompton, Ravishankar Chinga // J. Assoc. Comput. Mach. — 1995. — Vol. 42, No. 3. — P. 562583.

20. Yashkov, S. F. Time-dependent solution of the foreground-background processor-sharing queue / S.F. Yashkov // J. Appl. Math. 1993. - Vol. 6, No. 4. — P. 410.

21. Климов, Г. П. Системы обслуживания с разделением времени. I / Г. П. Климов // Теория вероятностей и ее применения. — 1974. — Т. 19, Вып. 3. — С. 558-576.

22. Климов, Г. П. Системы обслуживания с разделением времени. II / Г. П. Климов // Теория вероятностей и ее применения. — 1978. — Т. 23, Вып. 2. — С. 135-148.

23. Китаев, М. Ю. Системы обслуживания с ветвящимися потоками вторичных требований / М. Ю. Китаев, В. В. Рыков -// Автоматика и телемеханика. — 1980. — No. 9. С. 52-61.

24. Федоткин, М. А. Оптимальное управление конфликтными потоками и маркированные точечные процессы с выделенной дискретной компонентой. I / М. А. Федоткин // Литовский математический сборник. — 1988. — Т. 28, No. 4. — С. 783-794.

25. Федоткин, М. А. Оптимальное управление конфликтными потоками и маркированные точечные процессы с выделенной дискретной компонентой. II / М. А. Федоткин // Литовский математический сборник. — 1989. — Т. 29, No. 1. — С. 148-159.

26. Fedotkin, М. A. Bartlett flow control in time-sharing systems / M. A. Fedotkin, A. A. Vysotsky. // Twelth Prague Conference on information theory, statistical decision functions and random processes. Booklet of abstracts. Prague. — 1994.

27. Тимофеев, E. А. Оптимизация средних длин очередей в системе обслуживания с ветвящимсия потоками вторичных требований / Е. А. Тимофеев // Автоматика и телемеханика. — 1995. — No. 3. — С. 60-67.

28. Chao, X. On Klimov's model with two job classes and exponential processing times / X. Chao // J. Appl. Probab. 1993. - Vol. 30, No. 3. - P. 716-724.

29. Disney, L. R. A note on sojourn times in M/G/l queue with instantanous Bernoulli feedback / L. R. Disney // Naval.Research Logist Quart. 1981. — Vol. 28. — P. 679684.

30. Boxma, O. J. An M/G/l queue with multiple type of feedback and gated vacations / O.J. Boxma, U. Yechiali // Journal of Applied probability. — 1997. — Vol. 34. — P. 773-784.

31. Choudhury, G. A Two phase queueing system with Bernoulli feedback / G. Choudhury, M. Paul // Information and Managment Sciences. — 2005. — Vol. 16, No. 1. — P. 35-52.

32. Высоцкий, А. А. Предельные свойства и оптимизация процессов с разделением времени / А. А. Высоцкий, М. А. Федоткин // Доклады РАН. — 1996. — Т. 350, No. 3. С. 295-297.

33. Lipsky, L. A study of time-sharing systems considering as queueing networks of exponential servers / L. Lipsky // Comput. J. — 1980. — Vol. 23, No. 4. — P. 290-297.

34. Джейсуол, H. Очереди с приоритетами / H. Джейсуол. — М.: Мир, 1973. — 280 с.

35. Гнеденко, Б. В. Приоритетные системы обслуживания / Б. В. Гнеденко, Э.А. Да-ниелян, Б. Н. Димитров, Г. П. Климов, В. Ф. Матвеем. — М.: Издательство Московского университета, 1973. — 447 с.

36. Ушаков, В. Г. Приоритетные системы с рекуррентными входщими потоками / В. Г. Ушаков, Н. Г. Ушаков. — М.: Изд-во Фак. ВМиК МГУ, 2000. 44 с.

37. Etschaier, М. Discretionary Priority Processes: Master's thesis. / M. Etshaier. — Case Institute of Technology, Cleveland, Ohio, 1966.

38. Bocharov, P. P. A queueing system of finite capacity with the server requiring a priority search for customers / P.P. Bocharov, C. D'Apice, B. D'Auria, S. Salerno // Вестник РУДН, сер. Приклада, матем. и информ. — 2000. — No. 1. — С. 49-59.

39. Wu, Y. Weak convergence for queues with prioroty-feedback / Y. Wu // Gongchen Shuxue xuebao (Chin. J. Eng. xMath). 1995. - Vol. 12, No. 1. - P. 111-115.

40. Альборес, Ф. X. Анализ системы массового обслуживания MAP2\G2\\ |r / Ф.Х. Альборес, II. П. Бочаров // Автоматика и телемеханика. — 1997. — No. 11. С. 102-117.

41. Печинкин, А. В. Стационарные вероятности состояний в системе с входящим потоком марковского типа, относительным приоритеом и раздельными очередями / А. В. Печинкин // Автоматика и телемеханика. — 1998. — No. 1. — С. 107-119.

42. Бочаров, Г1.П. Стационарные вероятности состояний системы MAP\G\l\r с повторными заявками и приоритетным обслуживанием первичных заявок / П. П. Бочаров, А. В. Печинкин, Н. X. Фонг // Автоматика и телемеханика. — 2000. — No. 8.- С. 68-78.

43. Бочаров, П. П. Анализ системы массового обслуживания map2\g2\1\t с относительными приоритетом и обслуживанием, зависящим от длин очередей / П. П. Бочаров, Н. X. Фонг, Т. X. Хак // Вестник РУДН, сер. Прикладн. матем. и информ.- 1999. No. 1. - С. 92-109.

44. Климов, Г. П. Приоритетные системы обслуживания с ориентацией / Г. П. Климов, Г. К. Мишкой М.: Изд-во Московского университета, 1979. — 223 с.

45. Воковницкий, М. И. Модель n-уровневого приоритетного обслуживания с учетом потерь на переключения. Часть 2. Относительный приоритет / М. И. Воковницкий // Автоматика и телемеханика. — 1980. — Т. 6. — С. 28-33.

46. Бронштейн, О. И. Об однолинейной системе массового обслуживания с потерями / О. И. Бронштейн, A.JI. Райкин, В. В. Рыков // Изв. АН СССР, сер. Техническая кибернетика. — 1964. — No. 4. — С. 45-51.

47. Рыков, В. В. Об оптимальных динамических приоритетах в однолинейных системах массового обслуживания / В. В. Рыков, Э. Е. Лемберг // Изв. АН СССР. Техн. кибернетика. 1967. - No. 1. - С. 25-34.

48. Веклеров, Е. Б. Об оптимальных абсолютных динамических приоритетах в системах массового обслуживания / Е. Б. Веклеров // Изв. АН СССР. Техн. кибернетика. 1967. - No. 2. - С. 87-90.

49. Питтель, Б. Г. Оптимальное управление в системе массового обслуживания с несколькими потоками требований / Б. Г. Питтель // Изв. АН СССР. Техн. кибернетика. 1972. - No. 6. - С. 101-116.

50. Попов, Г. А. Нахождение оптимальной функции переключения в одном классе моделей с параметрами / Г. А. Попов // Сборник научных трудов: Автоматика и прикладные вопросы математики и физики. — Астрахань: Изд-во АГТУ, 2000. — С. 27-35.

51. Nam, P. Integchange arguments for classical scheduling problems in queues / P. Nain // Syst. and Contr. Lett. 1989. - Vol. 12, No. 2. - P. 177-184.

52. Ji, С. Sequential scheduling of priority queues and arm-acquiring bandits / C. Ji // J. Appl. Math, and Simul. 1987. - Vol.l, No. 2. - P. 115-135.

53. Nishimura, S. Optimal job scheduling of M|G|1 queue with feedback: The discounted case / S. Nishimura // J. Oper. Res. Soc. Jap. 1988. - Vol. 31, No. 3. - P. 371-388.

54. Song, D. P. Optimal control of a stochastic assembly production line / D. P. Song, Y.X. Sun, W. Xing// J. Optimiz. Theory and Appl. 1998. - Vol. 98, No. 3. -P. 681-700.

55. Gans, N. Optimal dynamic scheduling of a general class of parallel-processing queueing systems / N. Gans, G. Van Ryzin // Adv. Appl. Probab. 1998. - Vol. 30,-No. 4. -P. 1130-1156.

56. Рыков, В. В. Управляемые системы массового обслуживания / В. В. Рыков. // Итоги науки и техники. М.: ВИНИТИ, 1975. - Т. 12. - С. 43-153.

57. Van Oyen, М. P. Monotonicity of optimal performance measures for polling systems / M. P. Van Oyen // Probab. Eng. and Inf. Sci. 1997. - T. 11, No. 2. - P. 219-228.

58. Рыков, В. В. Об условиях монотонности оптимальных политик управления системами массового обслуживания / В. В. Рыков // Автоматика и телеменахика. — 1999. No. 9. - С. 92-106.

59. Takne, Т. Soujourn times in vacations and polling systems with Bernoulli feedback / T. Takne, H. Tagaki, T. Haseguawa // J. Appl. Probab. 1991. - Vol. 28, No. 2. -P. 422-432.

60. Sidi, M. A queueing network with a single cyclically roving server / M. Sidi, H. Levy, S. VV. Fuhrmann // Queueing Systems: Theory and Applications. — 1992. — Vol. 11, No. 1-2. C. 121-144.

61. Боровков, А. А. Эргодичность и устойчивость случайных процессов /А. А. Боровков. М.: Эдиториал УРСС, 1999. — 440 с.

62. Nair, S. S. A single server tandem queue / S. S. Nair // Journal of Applied Probability. 1971. - Vol. 8. - P. 95-109.

63. Taube-Netto, M. Two queues in tandem attenden by a single server / M. Taube-Netto // Operations Research. 1977. - Vol. 25. - P. 140-147.

64. Katayama, T. A cyclic service tandem queueing model with parallel queues in the first stage / T. Katayama // Communications in Statistica: Stochastic Models. — 1988. — Vol. 4, No. 3. P. 421-443.

65. Sidi, M. Structured priority queueing systems with applications to packet-radio networks / M. Sidi, A. Segall // Performance Evaluation. 1983. - P. 264-275.

66. Simon, B. Priority queues with Feedback / B. Simon // J. Ass. Сотр. Mach. — 1983.- Vol. 31. P. 134-149Л

67. Cooper, R. B. Queues served in cyclic order / R. B. Cooper, G. Murray // Bell Sys. Tech. J. 1969. - Vol. 48. - P. 675-689.

68. Cooper, R. B. Queues served in cyclic order: waiting times / R. B. Cooper // Bell Sys. Tech. J. 1970. - Vol. 49, - P. 399-413,

69. Eisenberg, M. Queues with periodic service and changeover time / M. Eisenberg // Oper. Res. 1972. - Vol. 20. - P. 440-451.

70. Swartz, G.B. Polling in a loop system / G. B. Swartz // J. Ass. Сотр. Mach. — 1980.- Vol. 27. P. 42-59.

71. Levy, H. Binomial Gated Service: a method for effective operation and optimization of polling systems / H. Levy // IEEE Transactions on communications. — 1991. — Vol. 39, No. 9. P. 1341-1350.

72. Kleinrock, L. The analysis of a random polling systems / L. Kleinrock, H. Levy // Operational Research. 1988. - Vol. 36. - P. 716-332.

73. Sidi, M. Polling systems with simultaneous arrivals / M. Sidi , H. Levy // IEEE Transactions on Communications. — 1991. — Vol. 39, No. 6. — P. 823-827.

74. Hiroyama, T. Analysis of multiclass M|G|1 queues with a mixture of 1-limited disciplines and gated disciplines / T. Hiroyama // J. Oper. Res. Soc Jap. — 1999.- Vol. 42, No. 3. P. 237-255.

75. Van der Mei, R. D. Polling systems with simultaneous batch arrivals / R. D. Van der Mei // Stochast. Models. 2001. - Vol. 17, No. 3. - P. 271-292.

76. Bartlett, M. S. The spectral analysis of point processes /.M. S. Bartlett // J. Roy. Statist. Soc. 1963. - Vol. 25, No. 2. - P. 264-296.

77. Lucantoni, D. M. New results on the single server queue with a batch Markovian arrival process / D. M. Lucantoni // Communications in Statistics: Stochastic Models. — 1991.- Vol. 7, No. 1. — P. 1-16.

78. Burman, D. An Asymptotic Analysis of a Queueing System with Markov-Modulated Arrivals / D. Burman, R. Smith // Oper. Res. — 1986. — Vol. 34.

79. Addie, R. Fractal Traffic: measurements, modelling and performance evaluation / R. Addie, M. Zukerman, T. Neame // Proceedings of IEEE INFOCOM'95. 1995. - P. 977-984.

80. Crovella, M. E. Self-similarity in World Wide Web traffic: evidence and possible causes / M. E. Crovella, A. Bestavros // Proceeding of ACM SIGMETRICS'96. 1996. -P. 160-169.

81. Головко, H. И. Анализ систем массового обслуживания, функционирующих в случайной среде / Н. И. Головко, В. В. Катрахов. — Владивосток: Изд-во ДВГАЭУ, 2000. 129 с.

82. Куделин, А. Н. Построение математической модели циклического управления конфликтными потоками заявок в случайной среде / А. Н. Куделин, М. А. Федоткин; Нижегор. ун-т. Нижний Новгород, 1995. - 19 с. - Деп. в ВИНИТИ 14.03.95 No.688-B95.

83. Куделин, А. Н. Анализ математической модели циклического управления конфликтными потоками заявок в случайной среде / А. Н. Куделин, М. А. Федоткин; Нижегор. ун-т. Нижний Новгород, 1995г - 16 с: - Деп. в ВИНИТИ 06.06.95 No.l636-B95.

84. Куделин, А. Н. Управление конфликтными потоками в случайной среде по ин-формуции о наличии очереди / А. Н. Куделин, М. А. Федоткин; Нижегор. ун-т. — Нижний Новгород, 1996. 22 с. - Деш в ВИНИТИ 28.05.96 No.l717-B<)6.

85. Куделин, А. Н. Предельные теоремы для систем управления потоками в случайной среде в классе алгоритмов с упреждением / А. Ы. Куделин, М. А. Федоткин; Нижегор. ун-т. — Нижний Новгород, 1996. 40 с. — Деп. в ВИНИТИ 02.08.96 No.2593-B96.

86. Зорин, А. В. Входной поток, управляемый марковской цепью / А. В. Зорин; Нижегор. ун-т. Нижний Новгород, 2001. - 15 с. - Деп. в ВИНИТИ 15.05.01 No.1253-В2001.

87. Федоткин, М. А. Об оптимальном управлении процессом с разделением времени в случайной среде / М. А. Федоткин, А. В. Зорин // Математика и кибернетика 2003. Сборник научных статей юбилейной научно-технической конференции факультета

88. ВМК ННГУ и НИИ ПМК. Нижний Новгород, 28-29 ноября 2003 г. Нижний Новгород, 2003. - С. 269-273.

89. Зорин, А. В. Анализ процессов с разделением времени / А. В. Зорин, М.А. Федоткин // Вестник Нижегородского университета им. Н. И. Лобачевского. Серия Математика. 2003. - Т. 1, No. 1. - С. 18-28.

90. Зорин, А. В. Система с разделением времени в условиях изменения структуры обслуживающего устройства и структуры входных потоков / А. В. Зорин, М. А. Федоткин; Нижегор. ун-т. Нижний Новгород, 2003. — 22 с. — Деп. в ВИНИТИ 19.09.03 No.L704-B2003.

91. Zorine, А. V. Optimal control of a time-sharing process in a stationary random environment / A. V. Zorine, M. A. Fedotkin // Сборник тезисов докладов VI Международного конгресса по математическому моделированию. — Нижний Новгород, 2004. С. 136.

92. Зорин, А. В. Анализ и оптимизация процессов с разделением времени, функционирующих в случайной среде / А. В. Зорин, М. А. Федоткин // Вестник Нижегородского университета им. Н. И. Лобачевского. Серия Математика. — 2004. — No. 1. С. 92-103.

93. Зорин, А. В. Об оптимальном управлении процессами с разделением времени в случайной среде / А. В. Зорин, М. А. Федоткии; Нижегор. ун-т. — Нижний Новгород, 2004. 58 с. - Деп. в ВИНИТИ 29.06.04 No.ll20-B2004.

94. Зорин, А. В. О периоде занятости системы с дважды стохастическим входным потоком / А. В. Зорин // Вестник Нижегородского университета им. Н. И. Лобачевского. Серия Математика. — 2005. — Вып. 3. — С. 43-53.

95. Зорин, А. В. Оптимизация управления дважды стохастическими неординарными потоками в системах с разделением времени / А. В. Зорин, М. А. Федоткин // Автоматика и телемеханика. — No. 7. — 2005. — С. 102-111.

96. Большаков, Н А. Прикладная теория случайных потоков / Н. А. Большаков,

97. B. С. Ракошиц. — М.: Советское радио, 1978.

98. Франкен, П. Очереди и точечные процессы / П. Франкен, Д. Кениг, У. Арндт, Ф. Шмидт. — Киев: Наукова думка, 1984.

99. Высокций, А. А. Анализ систем с разделением времени при обслуживании потоков вторичных заявок / А. А. Высоцкий, М. А. Федоткин; Нижегор. ун-т. — Нижний Новгород, 1995. 19 с. - Деп. в ВИНИТИ 03.02.95 No.325-B95.

100. Кокс, Д. Р. Теория очередей / Д. Р. Кокс, У. JI. Смит М.: Мир. — 1966. — 218 с.

101. Гантмахер, Ф. Р. Теория матриц / Ф. Р. Гантмахер. М.: Наука, 1988. — 552 с.

102. Боровков, А. А. Вероятностные процессы теории массового обслуживания / А. А. Боровков. — М.: Наука, 1972. — 368 с.

103. Боровков, А. А. Асимптотические методы в теории массового обслуживания / А. А. Боровков. — М.: Наука, 1980. — 382 с.

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

105. Федоткин, М. А. Нелокальный способ задания управляемых случайных процессов / М. А. Федоткин // Математические вопросы кибернетики. М.: Наука, 1998. —1. C. 333-344.

106. Анисимова,\Л. Н. Надежность управляющих систем и статистический анализ сбоев ее элементов / Л. Н. Анисимова, М. А. Федоткин // Вестник ННГУ. Математическое моделирование и оптимальное управление. — 2000. — Вып. 1. — С. 14-22.

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

108. Коваленко, IT. И. Теория вероятностей и математическая статистика / И. II. Коваленко, А. А. Филиппова. — М.: Высшая школа, 1982. — 256 с.

109. Невельсон, М. Б. Стохастическая аппроксимация и рекуррентное оценивание / М. Б. Невельсон, Р. 3. Хасьминский. — М.: Наука, 1972. — с.

110. Ширяев, А. Н. Вероятность. В 2-х кн. / А. Н. Ширяев. М.: МЦНМО, 2004.

111. Прабху, II. Методы теории массового обслуживания и управления запасами (изучение основных случайных процессов) / П. Прабху. — М.: Машиностроение, 1969.- 356 с.

112. Скороход, А.В. Элементы теории вероятностей и случайных процессов / А. В. Скороход. — Киев: Вища школа. Головное изд-во, 1980. — 344 с.

113. Боровков, А. А. Теория вероятностей: Учебное пособие для вузов / А. А. Боровков.

114. М.: Наука. Гл. ред. физ.-мат. лит., 1986. — 432 с.

115. Герцбах, И. Теория надежности с приложениями к профилактическому обслуживанию / И. Герцбах. — М.: ГУП Изд-во "Нефть и газ" РГУ нефти и газа им. И. хМ. Губкина, 2003-.— 263 с.

116. Литвак, Н. В. Вероятностная модель адаптивного управления конфликтными потоками. Качественное и численное исследование / Н. В. Литвак, М. А. Федоткин // Автоматика и телемеханика. — 2000. — No. 6. — С. 69-78.

117. Вишневский, В.М. Теоретические основы проектирования компьютерных сетей / В.М. Вишневский — М.: Техносфера, 2003. — 512 с.

118. Страуструп, Б. Язык программирования С++ / Б. Страуструп. — СПб.: Невский диалект, 2000. — 991 с.1. VI