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

Введение.

Глава I. МЕТОДЫ ПРИБЛИЖЕННОГО РАСЧЕТА ХАРАКТЕРИСТИК

АДАПТИРУЮЩИХСЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

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

§ 1.2. Приближенный расчет характеристик адаптирующихся

СМО с переменной интенсивностью обслуживания

§ 1.3. Приближенный расчет характеристик адаптирующейся системы массового обслуживания с динамическими приоритетами.

Выводы.

Глава П. ОЦЕНКА ИНТЕНСИВНОСТИ ВХОДЯЩЕГО ПОТОКА ЗАЯВОК И АДАПТИВНОЕ УПРАВЛЕНИЕ СИСТЕМОЙ МАССОВОГО ОБСЛУЖИВАНИЯ.

§ 2.1. Автоматы-адаптеры для систем массового обслуживания.

§ 2.2. Адаптивная оценка интенсивности дважды стохастического пуассоновского процесса.

§ 2.3. Некоторые характеристики предложенных автоматов-адаптеров

Выводы.

Глава Ш. ИМИТАЦИОННАЯ МОДЕЛЬ И ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ

РЕЗУЛЬТАТОВ РАБОТЫ.

§ 3.1. Использование результатов работы.

§ 3.2. Имитационная модель адаптирующейся СМО.

§ 3.3. Описание программ

§ 3.4. Анализ результатов численных расчетов

Выводы.

Актуальность проблемы. Развитие вычислительных систем и систем передачи информации выдвинуло проблему оптимизации их функционирования. Необходимость решения задач оптимального управления этими системами дала толчок новому направлению в теории массового обслуживания - управлению системами массового обслуживания [65]. Большинством авторов управляемая система массового обслуживания рассматривается в предположении, что все ее параметры заранее известны и не меняются со временем [б5, ТС]. Однако для реальных систем, т.е. наиболее интересных с точки зрения приложений, такое предположение не всегда справедливо. В такой ситуации естественно при управлении системой пользоваться адаптивным подходом [61]. Таким образом, возникает задача адаптации системы к меняющимся условиям с целью оптимизации ее функционирования. Ниже рассматриваются примеры таких систем.

1°. Вычислительные комплексы.

Функционирование вычислительных комплексов хорошо описывается методами теории массового обслуживания и является одним из основных ее приложений [з, 30, 38, 52, 64, 67, 83]. Вычислительные комплексы работают в условиях неполной информации о внешней среде, т.е. потоках задач, предназначенных для решения [52, 63, 64, 83]. Во многих случаях параметры этих потоков заранее неизвестны либо меняются со временем, возможно, даже случайным образом. Более того, со временем могут меняться вероятностные свойплекса обычно позволяет осуществить перестройку элементов системы и, следовательно, открывает большие возможности для адаптаства потока время структура вычислительного комции. "Не будет преувеличением сказать, что будущие большие вычислительные комплексы и сети попросту не смогут существовать без мощного обеспечения алгоритмами адаптации, поддерживающими их в оптимальном состоянии независимо от изменений среды и самих вычислительных систем" £б2].

2°. Системы обработки информации.

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

3°. Сети связи.

При проектировании сетей связи возникают задачи оптимального управления потоками и каналами связи. Для их решения широко используются модели.и методы теории массового обслуживания (^29 , 35 , 43, 71, 92^. В реальных условиях управление сетью связи происходит в условиях неопределенности. Параметры нагрузок заранее неизвестны, кроме того, через случайные интервалы времени могут выходить из строя отдельные узлы и линии связи. В этой ситуации для обеспечения эффективности функционирования сети необходимо использовать адаптивное управление сетью (б, 35, 71, 73].

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

Цель работы. При выполнении данной работы ставились следующие задачи:

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

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

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

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

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

Работа выполнялась в соответствии с' разделом 1.12.10.1.Г "Адаптивные системы управления" координационного плана НИР АН СССР по комплексной проблеме "Кибернетика" на 1982-1985 г.г. на проведение НИР "Разработка теории управляемых систем массового обслуживания".и в рамках хоздоговорной темы "Путь-ПТ", заключенной Сибирским Физико-Техническим институтом с организацией п/я А-1332.

Состояние проблемы. Изучение управляемых систем массового обслуживания (СМО) началось в конце 60-х г.г. Понятие управляемой ОД О было введено О.И.Бронштейном и В.В. Рыковым £9]. Система массового обслуживания задается Ц элементами: входящими потоками требований, механизмом и длительностями обслуживания, структурой системы, дисциплиной обслуживания. В управляемой СМО элементы системы допускают применение управляющих воздействий. Большинство авторов рассматривают управляемую СМО и решают задачи оптимального управления ею в предположении, что параметры потоков и состояние системы в каждый момент времени известны. В этих предположениях решен ряд задач об оптимальном (в смысле некоторого критерия качества, например, минимизации определенной функции потерь) выборе параметров обслуживания £2, 7, 14, 91, 96, 98, III]. Параметр обслуживания может принимать несколько фиксированных значений [2, 98]либо изменяется в ограниченном интервале £91, III]. Задачи оптимального включения резервного прибора решались в [8, 21, 79, 80, 85, 90, 105].

В случае, когда параметры входящих потоков неизвестны либо изменяются со временем, для управления системой необходимо использовать адаптивный подход [52, 61, 62, 63, 64]. В настоящее время работ по адаптирующимся СМО опубликовано мало (автору известно не более 30)» Большинство авторов для адаптивного управ ления системой использует вероятностные автоматы [l0, 76 ] либо произвольные автоматы-адаптеры. Вопросы назначения оптимальных приоритетов с помощью вероятностных автоматов изучались в flO, II, 27, 42, 45, 60, 68]. В работах [22, 34, 45-49] вероятностные автоматы использовались для адаптации интенсивности обслуживания £24, 45, 48, 49], управления включением резервного прибора [22, 4б], диспетчеризации входящих потоков [l2, 13, 19, 34, 47, 48]. Оптимальность предложенных алгоритмов адаптации доказывалась либо на основе свойств используемых автоматов ¡45-48, 68], либо результатами моделирования на ЭВМ flO, II, 13, 24].

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

Адаптивные алгоритмы управления СМО в байесовской ситуации предложены и исследованы в [21, 50, По]. В работах [i, 36, 37, 53, 54, 58, 64, 77, 83, 89, 107] предлагались и исследовались различные алгоритмы адаптации в системах массового обслуживания.

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

L4 где характеристика системы при реализации I -ой структуры, вероятность реализации этой структуры. Формулы такого вида использовались, например, для вычисления среднего времени ожидания заявок [53]. Получить точные явные выражения характеристик адаптирующихся СМО не представляется возможным в силу сложности этой задачи. В самом деле, поведение числа заявок в системе описывается случайным блужданием по ц-мерной целочисленной решетке, а даже исследование случайных блужданий- на плоскости сопряженно с очень большими математическими трудностями [ад, 41].

Вместе с тем при анализе адаптирующихся СМО желательно пользоваться более точными формулами, чем

Необходимо отметить работы, посвященные СМО, управляемым случайными процессами. Именно, параметры входящих потоков и обслуживающих приборов таких систем (или сами законы распределения длительностей обслуживания и интервалов между приходами заявок) зависят от состояния некоторого дискретного случайного процесса. Хотя авторы этих работ не касаются вопросов адаптации в СМО, задача расчета характеристик адаптирующихся GI.10 очень близка задаче расчета характеристик подобных систем. В ряде случаев можно непосредственно перенести результаты этих работ на случай адаптирующихся СМО,задав определенным образом управляющий процесс.

Система M/M/I, управляемая марковской цепью с конечным числом состояний, рассматривалась в [30, 87, 97, 100, ЮЗ]. Получены условия существования стационарного режима [102, ЮЗ]. В случае, когда управляющая цепь Маркова содержит всего 2 состояния, найдены распределение числа заявок в системе и средняя длина очереди [87, 97]. В этом же случае (2 состояния управляющей цепи) найдена средняя длина очереди и для системы M/G7I [55]. Система M/G-Д, управляемая марковской цепью, изучалась также в £82, 99, ЮЧ]. В работе [59] предложен метод расчета средней длины очереди в системах массового обслуживания, управляемых особого вида полумарковским процессом. В работах [72, 88, 108] изучалась СМО с несколькими входными потоками и прибором, переключающимся с обслуживания одной очереди на другую по произвольным законам,

Для приближенного анализа СМО в условиях большой загрузки (т.е. при близкой к нулю вероятности простоя приборов) часто используется аппроксимация длины очереди диффузионным случайным процессом [21, 30, 51, 93, В частности, с использованием диффузионной аппроксимации получены приближенные формулы для характеристик систем

M/G-Д [9ч] и M/G/I/W [93], управляемых марковской цепью с конечным числом состояний,

Одной из возможных моделей входящего потока реальной системы является дважды стохастический пуассоновский процесс, т.е. пуассоновский процесс, интенсивность которого является случайным процессом. Для адаптивного управления системой массового обслуживания, на которую поступает такой поток заявок, необходимо иметь на каждый момент времени оценку интенсивности этого потока. Уравнения для оптимальной в среднеквадратическом оценки интенсивности дважды стохастического пуассоновского процесса были получены в работах [78, 86, Юб1 однако решить эти уравнения не представляется возможным в силу их сложности. Задача об обнаружении момента разладки пуассоновского процесса решалась в [56, 57, 109]. Кроме этого, различные вопросы, связанные с оцениванием интенсивностей дважды стохастических пуассоновских процессов и полей рассматривались в [81, 84, 95, 101].

Содержание работы. В первой главе предлагаются и рассматриваются методы приближенного расчета характеристик адаптирующихся СМО. В первом параграфе предложен метод расчета стационарного распределения числа заявок в адаптирующейся однолинейной (140 с резервным прибором. Рассмотрены также модификации метода, учитывающие инерционность процесса на выходе адаптера. Во втором параграфе предложен метод приближенного расчета средней длины очереди в адаптирующихся СМО с.переменными интенсивностями обслуживания. Метод обобщен на случай многолинейной адаптирующейся ОЙ О с резервными приборами и переменными интенсивностями обслуживания. В третьем параграфе предложен метод приближенного расчета характеристик адаптирующихся СМО с динамическими приоритетами или с формированием очередей.

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

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

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

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

2. Предложено, несколько автоматов-адаптеров для адаптивного управления системой массового обслуживания. Исследованы их характеристики и применение в адаптирующихся СМО.

3. Предложена и исследована адаптивная оценка интенсивности дважды стохастического пуассоновского процесса.

Практическая ценность. Предложенные методы могут использоваться для расчета характеристик вычислительных комплексов, систем обработки информации, сетей связи. Для расчета характеристик этих систем может использоваться также предложенная имитационная модель адаптирующейся (МО. Для адаптации к входящим потокам заявок в реальных системах можно использовать предложенные автором автоматы-адаптеры. Предложенные методы расчета характеристик адаптирующихся СМО и имитационная модель адаптирующейся СМО реализованы в виде программ на языках FORTRAjV-iy и PL/l и были использованы для расчета характеристик системы обработки информации, разрабатываемой в п/я A-I332. Зти программы были переданы п/я A-I332 в соответствии с хоздоговрной темой "Путь-ПТ" и используются там для расчета характеристик разрабатываемых систем обработки информации.

Публикация. По тематике диссертации опубликовано 9 печатных работ [П2-120]. Материалы диссертации.были также изложены в отчетах по госбюджетной НИР и хоздоговорной НИР, выполняемым в Сибирском Физико-Техническом институте:

1, Управляемые и адаптивные системы массового обслуживания. Отчет (промежуточный) по НИР "Разработка управляемых систем массового обслуживания" (шифр "УСМ0")./СФТИ, руководитель НИР Горцев A.M., № ГР 0I82506XII2. - Томск, 1981. - 212 с. (Депонирован в ВНТИЦ, инв. № 028200805^3).

2. Управляемые и адаптивные системы массового обслуживания Отчет (промежуточный) по НИР "Разработка теории управляемых систем массового обслуживания" (шифр "УСМ0")./СФТИ, руководитель НИР Горцев A.M., ГГР 0I82506III2. - Томск, 1983. - 92 с.

3. Разработка, алгоритмов управления потоками зявок в многомашинной вычислительной системе. Отчет (промежуточный) по НИР "Путь-ПТ-У/СФТИ, руководитель НИР Горцев A.M., № ГР 0I824037C74.-Томск, 1982. - 234 с.

4. Разработка алгоритмов управления потоками заявок в многомашинной вычислительной системе. Отчет (заключительный) по НИР "Путь-ПТ"./(МИ, руководитель НИР Горцев А.М.,№ ГР 01824037074,-Томск, 1983. - 186 с.

Апробация работы. Основные положения диссертации и отдельные ее результата докладывались и обсуждались:

1. На П-ом Всесоюзном совещании-семинаре "Оптимизация динамических систем" (г.Минск, сентябрь, 1980 г.).

2. На областном семинаре "Математические методы в задачах управления" (г.Пенза, май 1981 г.).

3. На Всесоюзном научно-практическом семинаре "Прикладные аспекты управления сложными системами" (г.Кемерово, март 1983г.).

4. На Всесоюзной конференции "Теория адаптивных систем и ее применения" (г.Ленинград, май 1983 г.).

5. На УП семинаре по проблемам непрерывности и устойчивости стохастических моделей (г.Саратов, июнь 1983 г.).

6. На ХП Всесоюзной школе-семинаре по адаптивным вистемам (г.Могилев, январь 1984 г.).

7. На симпозиуме "Математическое обеспечение для автоматизации исследований, идентификации и планирования эксперимента" (г.Харьков, февраль 1984 г.).

ВЫВОДЫ

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

2. Предложена имитационная модель адаптирующейся системы массового обслуживания. '

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

В первом параграфе предлагается метод расчета стационарного распределения числа заявок в однолинейной адаптирующейся СМО с резервным прибором. Управление включением-выключением резервного прибора осуществляется адаптером. Структура адаптера не конкретизируется. Предполагается, что адаптер включает резервный прибор с интенсивностью об и выключает с вероятностью ^ в момент окончания обслуживания резервным прибором очередной заявки. Обслуживание предполагается экспоненциальным. Предлагается учитывать инерционность процесса на выходе адаптера, замедляя выключение резервного прибора в зависимости от времени его беспрерывной работы. Время работы резервного прибора учитывается косвенно, по числу событий, произошедших за это время в системе. Задача во всех случаях сводится к отысканию стационарного распределения вероятностей состояния для случайного блуждания в полосе { ) : Ь-О^к, 1 • Пусть случайное блуждание задается инфинитезимальными коэффициентами перехода У* » , уг ). Тогда стационарные вероятности состояния Р(ь , / ) отвечают системе уравнений >г

-о п,

2 1 ч(с,],1<,1)Ра ,1):0

П ОС (2)

I I = 1

I. 1=0 , . г\,

Подставляем в уравнение (I) г\1 ^j ) в виде *

СЗ) выбирается из условия равенства нулю определителя системы (2) Л после подстановки туда (3). Если уравнение Д =0 имеет равно С И, +1) корней, лежащих в интервале (0,1), то решение системы (1)-(2) имеет вид п. где ) определяются с точностью до постоянного множителя (0) из системы (I) при подстановке туда корни уравнения Л =0, лежащие в интервале (0,1). ^$(0) определяются из граничных условий (2).

Во втором параграфе рассматривается метод приближенного расчета среднего числа заявок в однолинейной адаптирующейся СМ0 с переменной интенсивностью обслуживания. Обслуживание экспоненциальное с одной из двух возможных интенсивностей /л^ и^ С Аг Переключение интенсивностей осуществляется адаптером. Время работы прибора с интенсивностью ¡и£ есть случайная величина с функцией распределения ^Входящий поток простейший, с параметром & . В предположении, что к моменту переключения прибора с одной интенсивности на другую в системе успевает установиться стационарное распределение, найдено преобразование Лапласа-Карсона от среднего числа заявок в системе в момент £ при работе с интенсивностью ^ (4-Р^А,- д М1 -3.+6+ /¿Ящ - 4Я«£ ^

Среднее число заявок в системе определяется по формуле

Лс/Р^М+р:^) где

Получены формулы, позволяющие определять непосредственно, без применения обратного преобразования в (4). Оценена скорость сходимости переходного распределения к стационарному, т.е. качество приближения. При /л^ предлагается аппроксимировать число заявок в системе при работе с интенсивностью жу разностью двух пуассоновских процессов, с параметрами «Я и ^ . Доказывается, что такое приближение является достаточно точным. Среднее число заявок в системе в этом случае также найдено в явном виде. Предложенный метод легко переносится на другие адап тирующиеся СМО. В качестве примеров найдено среднее число заявок в адаптирующейся СМО с резервным прибором, адаптирующейся СМО с N интенсивностями обслуживания, многолинейной адаптирующейся СМО с резервными приборами.

В третьем параграфе предлагается метод приближенного расчета характеристик адаптирующейся СМО с динамическими приоритетами. Рассматривается СМО с двумя входящими простейшими потоками с параметрами «Я/ и Дэ и одним обслуживающим прибором. Обслуживание экспоненциальное, с параметром /U¿ для заявок ¿-го потока. В случае большой загрузки, при л,*! + -М -о1 т /*г 1 длины очередей аппроксимируются диффузионными процессами и {((£). Области , в которых прибор берет на обслуживание заявку I -го потока, задаются в виде

•• (х,*(£))<у I о^(^) - состояние адаптера в момент t, (Ж, - некоторая непрерывная и неубывающая по ОС функция. В случае, когда о1 (¿) - дискретный марковский процесс, найдены средние значения процессов эс(£), у(^) методом, аналогичным описанному в предыдущем параграфе. В случае, когда Ы.(£) - непрерывный случайный процесс, приближенным решением соответствующего уравнения Фоккера-Планка определена стационарная плотность распределения На приведенном примере показана возможность применения метода к расчету характеристик адаптирующейся СМО с формированием очередей.

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

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

Во втором параграфе предлагается и исследуется адаптивная оценка интенсивности дважды стохастического пуассоновского процесса. Предполагается, что эта интенсивность Ж*) - стационарный в широком смысле случайный процесс. Оценка берется в виде со кч где ¿у, . - моменты прихода заявок, перенумерованные в порядке удаления от текущего момента времени Ь . Функция & (¿) выбирается из условия минимума среднеквадратической ошибки, которое сводится к уравнению типа Винера-Хопфа о о где Б случае, когда т. и $(5) заранее неизвестны, предлагается вначале строить их оценки на интервале ЕоТ 3 , а затем вместо О. (£) пользоваться решением уравнения тт 6(±)+1 йт а с1в (б) о

Л Л где - оценки. и К (б). Показано, что построенА ные в работе оценки и при определенных ограничениях на сходятся в среднеквадратическом при Т—* 00 к истинным значениям, а решение уравнения (б) сходится в среднеквадратическом при Т-*- сх» к решению уравнения (5)

X Предложен также другой метод отыскания <Х состоящий в разложении Л на СО/Г! в ряд Фурье и оценке коэффициентов разложения я С*). Показано, что построенные оценки крэффициентов сходятся в среднеквадратическом при Т-* к истинным значениям.

В третьем параграфе найдены характеристики автоматов-адаптеров, необходимые для расчета характеристик адаптирующихся СМО, использующих данные автоматы. Интенсивность перехода в некоторый класс состояний определяется как среднее число переходов в этот класс в единицу времени при условии, что в данный момент автомат находится вне этого класса. Для произвольного автомата с инфинитезимальными коэффициентами перехода из состояния в состояние О^. 'эта интенсивность имеет вид Pi T Яч

LkA J€A J

1 Pc ibA где Р^ - стационарная вероятность того, что автомат находится в состоянии i . Показано также, что распределение оценки act), предложенной в предыдущем параграфе, при ¿Of можно с достаточной степенью точности аппроксимировать нормальоо ным распределением со средним Л и дисперсией Л Jetwdt. о

В третьей главе приводится анализ численных результатов, описание имитационной модели адаптирующейся СМО, описание программ, сведения об использовании результатов работы.

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

Во втором параграфе предлагается и рассматривается имитационная модель адаптирующейся СМО.

В третьем параграфе приводится описание программ, осуществляющих расчет характеристик адаптирующихся СМ0 и автоматов-адаптеров по методам, предложенным в первых двух главах. Программы написаны на языке Ф0РТРАН-1У*. Приводится также описание программы имитационного моделирования адаптирующейся С40, реализующей модель, описанную в предыдущем параграфе. Программа написана на языке Р1-/1.

В четвертом параграфе проводится анализ численных расчетов. Анализ полученных численно характеристик предложенных в § 2.1 автоматов-адаптеров подтверждает целесообразность применения этих автоматов для оценки интенсивности входящего потока. Сравнение характеристик адаптирующихся СМО, полученных в результате применения предложенных автором методов и в результате имитационного моделирования на ЭВМ, позволяет заключить, что предложенные методы дают достаточно точные результаты.

В заключение автор выражает благодарность своему научному руководителю профессору А.Ф.Терпугову за постоянное внимание к работе.

1. Абрамов А.Х., Дагкесаманский Н.Д. Об одной управляемой системе обслуживания с неполной информацией. - В кн.: Теория массового обслуживания. Труды Всесоюзной школы-семинара, м., 1981, с. 41-42.

2. Абрамов А.Х., Цвиркун А.Д. Об оптимальном назначении скорости обслуживания. Автоматика и телемеханика, 1968, № 2, с. 76-80.

3. Авен О.И., Турин Н.Й., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982. - 464 с.

4. Адаптация в системах обработки информации/Под ред. Растри-гина Л.А. Рига: Зинатне, 1977. - 94 с.

5. Андерсон Т. Статистический анализ временных рядов. М.: Мир, 1976. - 705 с.

6. Адаптивные алгоритмы управления в сетях связи ЭВМ/Под ред. Солодянникова Ю.В. Куйбышев: Изд-во КГУ, 1980. - 191 с.

7. Арсенишвили Г.Л., Заалишвили Н.З. Многофазовая система с меняющейся интенсивностью обслуживания. Сообщения АН ГССР, 1983, т. 109, № 3, с. 465-467.

8. Афанасьева Л.Г. Система с включением резервного прибора. -Известия АН СССР. Техническая кибернетика, 1971, № 2, с. 34-40.

9. Бронштейн О.Й., Рыков В.В. Об оптимальных дисциплинах обслуживания в управляющих системах. В кн.: Управление производством. Труды Ш Всесоюзн. совещания по автомат, упр-ию. М., 1967. - с. 215-224.

10. Варшавский В.И. Коллективное поведение автоматов. М.: Наука, 1973. - 407 с.

11. Варшавский В.И., Мелешина М.В., Цетлин M.JI. Организация дисциплины ожидания в системе массового обслуживания с использованием модели коллективного поведения автоматов. Проблемы передачи информации, т.4, вып.1, 1968, с. 73-7б.

12. Василевская Т.П., Горцев A.M. Адаптивная модель распределения заявок по очередям в двухлинейной системе массового обслуживания автоматом-адаптером. В кн.: Управляемые системы массового обслуживания, вып. I. Томск: Изд-во ТГУ, 1982,с.13-25.

13. Василевская Т.П., Горцев A.M. Адаптивное управление формированием очередей в двухлинейной СЙО. В кн.: ХП Всесоюзная школа-семинар по адаптивным системам. Тезисы докладов. Минск: Изд-во БГУ, 1984, с. 2D.

14. Воробьев Н.М. Управление временем обслуживания простейшего потока требований. В кн.: Труды I Всесоюзного симпозиума-по статистическим, проблемам в технической кибернетике. Адаптивные системы. М.: Наука, 1971, с. 447-451.

15. Гнеденко Б.В. Курс теории вероятностей. М.: Наука, 1969. -400 с.

16. Годунов С.К., Рябенький B.C. Разностные схемы. М.: Наука, 1973. - 400 с. .

17. Горцев A.M. Системы массового обслуживания с адаптивной дисциплиной обслуживания. В кн.: Структурная адаптация многомашинных систем обработки информации. Рига: Зинатне, 1978, с. 21-25.

18. Горцев A.M. Адаптивная модель управления резервной ЭВМ в вычислительной системе при больших загрузках. ' Автоматика и вычислительная техника, 1981, № I, с. 44-51.

19. Горцев A.M. Адаптивное управление потоками задач в вычислительной системе. Автоматика и вычислительная техника, 1982, № 6, с. 53-60.

20. Горцев A.M., Ивонина H.A., Проскурина Л.В. Адаптивное управление включением резервного канала в однолинейной СМО. Автоматика и телемеханика, 1978, № 10, с. 78-86.

21. Горцев A.M., Назаров A.A., Терпугов А.Ф. Управление и адаптация в системах массового обслуживания. Томск: йзд-во ТГУ,1978. 208 с.

22. Горцев A.M., Поттосина C.A. Структурная адаптация двухлинейной системы массового обслуживания со вспомогательным прибором. Автоматика и вычислительная техника, 1980, № 5, с. 43-49.

23. Диткин В.А., Прудников А.П. Справочник по операционному исчислению. М.: Высшая школа, 1965. - 466 с.

24. Камилов М.М., Пулатов А.К., Рахманов С.Т. Автоматная модель управления в системах массового обслуживания. Изв. АН УзССР, серия техн. наук, 1981, № 2, с- 7-9.

25. Камке Э. Справочник по обыкновенным дифференциальным уравнениям. М.: Наука,, 1976. - 576 с.А

26. Карлин С. Основы теории случайных процессов. М.: Мир, 1971. - 536 с.

27. Кельманс Г.К., Лгобчик Л.М., Позняк A.C. Адаптивное управление замкнутыми приоритетными системами массового обслуживания. -Известия АН СССР. Техническая кибернетика, 1978, № 4, с.81-93.

28. Кениг Д., Штойян Д. Методы теории массового обслуживания. -М.: Радио и связь, 1981. 127 с.

29. Клейнрок Л. Коммуникационные сети. Стохастические потоки и задержки сообщений. М.: Наука, 1970. - 255 с.

30. Клейнрок Л. Вычислительные системы с очередями. М.: Мир,1979. 600 с.

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

32. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров.~М.: Наука, 1978. 832 с.

33. Кофман А., Крюон Р. Массовое обслуживание. Теория и приложения. М.: Мир, 1965. - 302 с.

34. Лапко A.A., Поварич М.П. Диспетчеризация потоков требованийс переменными параметрами в приоритетных СМО. В кн.: Теория и методы автоматизации проектирования. Вып. I. Минск, 1978, с. 98-104.

35. Лазарев В.Г., Саввин Г.Г. Сети связи. Управление и коммутация. М.: Связь, 1973. - 264 с.

36. Любчик Л.М. Адаптивная коммутация приоритетных систем. В кн.: Труды ИНЭУМ, М., 1975, вып. 52, с. 3-6.

37. Любчик Л.М. Адаптивное управление приоритетным обслуживанием в многомашинных вычислительных системах. В кн.: Структурная адаптация многомашинных систем обработки информации. Рига: Зинатне, 1978, с. 35-38.

38. Максимей И.В. Функционирование вычислительных систем. М.: Сов.радио, 1979. - 272 с.

39. Малахов А.Н. Кумулянтный анализ случайных негауссовых процессов и их преобразований. М.: Сов.радио, 1978. - 376 с.

40. Малышев В.А. Асимптотическое поведение стационарных вероятностей для двумерных положительных случайных блужданий* -Сибирский математический журнал, 1973, т.14, № I, с. 156-169.

41. Малышев В.А. Случайные блуждания. Уравнения Винера-Хопфа в четверти-плоскости. Автоморфизмы Гаула. М.: Изд-во Моск. ун-та, 1970. - 201 с,

42. Мелешина М.В. Автоматная модель .организации взаимодействия между клиентами в СМО с ожиданием. Автоматика и телемеханика, 1969, № 5, с. 148-150.

43. Модели информационных сетей и коммутационных систем/Под ред. Харкевича АД., Гармаша В.А. М.': Наука, 1982. - 165 с.

44. Морс Фешбах Г. Методы теоретической физики. T.I. М.: Изд-во иностр. лит., 1958, - 930 с.

45. Назаров A.A. Об адаптивных системах массового обслуживания, управляемых автоматами с линейной тактикой. Автоматика и телемеханика, 1979, № 5, с. 99-103.

46. Назаров A.A. Адаптивное распределение заявок по приборам различной производительности. Известия АН СССР. Техническая кибернетика, 1979, № 5, с. II5-II9.

47. Назаров A.A. Адаптация интенсивности обслуживания к неизвестному параметру входного потока автоматом с целесообразным поведением. Автоматика и вычислительная техника, 1979, № 5, с. 56-61.

48. Назаров A.A." Адаптивное включение резервного прибора автоматом с целесообразным поведением. Автоматика и телемеханика, 1981, № 3, с. 170-174.

49. Назаров A.A. Автоматная адаптация оптимального по времени ожидания режима обслуживания. В кн.: ХП всесоюзная школа-семинар по адаптивным системам. Тезисы докладов. Минск: Изд-во ЕГУ, 1984, с. 73.

50. Назаров A.A., Терпугов А.Ф. Адаптация в управляемых системах массового обслуживания. Автоматика и телемеханика, 1976,7, с. 76-79.

51. Назаров A.A., Чекменев В.А. Нахождение оптимального управления в СМО при больших загрузках методом пограничного слоя. -В кн.: Управляемые системы массового обслуживания. Вып. I. Томск: Изд-во ТГУ, 1982, с. II3-I26.

52. Никифорова Н.Е. Методы оптимизации дисциплины обслуживанияв вычислительных системах. В кн.: Адаптация в вычислительных системах. Рига: Зинатне, 1978, с. 84-107.

53. Никифорова Н.Е. Об одной модели вычислительной системы с адаптивной дисциплиной обслуживания. В кн.: Адаптация в многомашинных вычислительных системах. Рига: Зинатне, 1980, с. 56-65.

54. Никифорова Н.Е. Исследование модели вычислительной системы с адаптивной дисциплиной обслуживания методом планирования эксперимента.-гВ кн.: Проблемы случайного поиска. Вып. 9. Рига: Зинатне, 1981, с. 228-235.

55. Новицкий А.Л. Однолинейная система с альтернирующим входным потоком. Известия АН СССР. Техническая кибернетика, 1976,6, с. 132-139.

56. Пашнев С.Я., Пертель В.А. Определение момента изменения интенсивности пуассоновского потока. В кн.: Труды 05ТИ. Вып. 63. Томск: Изд-во ТГУ, 1973, с. 235-238.

57. Пертель В.А. Точная нижняя граница дисперсии оценки момента разладки пуассоновского потока. Известия АН СССР. Техническая кибернетика, 1971, № 5, с. 167-170.

58. Петрушина А.Л. Адаптивное назначение приоритетов различным классам требований. Известия АН СССР. Техническая кибернетика, 1981, }Ь 3, с. 185-187.

59. Попов H.H. Системы массового обслуживания, управляемые полумарковскими процессами. Известия АН СССР. Техническая кибернетика, 1977, № I, с. 94-101.

60. Пулатов А.К. Автоматное управление в системе выработки относительных приоритетов. В кн.: Логическое управление. Вып. 3. М., 1981, с. 63-68.

61. Растригин Л.А. Современные принципы управления сложными объектами. М.: Сов. радио, 1978. - 232 с.

62. Растригин Л.А. Случайный поиск как метод адаптации вычислительных систем. В кн.: Вопросы кибернетики. Вып. 57, М., 1979, с. II3-I30.

63. Растригин Л.А. Вычислительные системы и сети как объекты применения случайного поиска. В кн.: Проблемы случайного поиска. Вып. 10. Рига: Зинатне, 1983, с. 5-30.

64. Растригин Л.А., Ширин A.B. Адаптивный выбор дисциплины обслуживания в вычислительной системе. В кн.: Адаптация в многомашинных вычислительных системах. Рига: Зинатне, 1980, с. 49-55.

65. Рыков В.В. Управляемые системы массового обслуживания. В кн.: Итоги науки и техники. Теория вероятностей. Математическая статистика. Теоретическая кибернетика, т.12. М., 1975, с. 43-154.

66. Самарский A.A., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978. - 591 с.

67. Самойленко С.И. Адаптивная коммутация в вычислительных сетях.- В кн.: Адаптация в многомашинных вычислительных системах. Рига: Зинатне, 1980, с. 7-35.

68. Сильвестрова Э.М. Марковские конечные автоматы линейного типа и адаптивные системы обслуживания. Киев, 1974. - 56с. (Препринт/ЙК АН УССР, № 74-40).

69. Справочник по специальным функциям/Под ред. М.Абрамовицы и И.Стиган. М.: Наука, 1979. - 832 с.

70. Титчмарш Е. Введение в теорию интегралов Фурье. М.-Л.: Гостехиздат, 1948. - 479 с.

71. Тобаги Ф.А., Герла м., Пиблз Р.У., Маннинг Э.Г. Методы моделирования и измерений в сетях с коммутацией пакетов. ТИЙЭР, 1978, т.66, № II, с. 156-185.

72. Толмачев А.Л. Обслуживание нескольких потоков со случайнымпереключением. Известия АН СССР. Техническая кибернетика, 1979, Ш 5, с. 107-114.

73. Умрихин Ю.Д. Вероятностные методы прогнозирования и адаптивного управления сетью связи в условиях неопределенности.

74. В кн.: Автоматы и управление. Управление на сетях и в узлах связи. М.: Наука, 1979, с. 18-41.

75. Файнберг М.А., Файнберг Е.А. Управление в системах массового обслуживания. Зарубежная радиоэлектроника, 1975, К 3, с. 3-34.

76. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений. М.: Мир, 1980. - 279 с.

77. Цетлин M.JI. Исследования по теории автоматов и моделированию биологических систем. М.: Наука, 1969. - 316 с.

78. Яшков ССвойства инвариантности вероятностных моделей адаптивной диспетчеризации в системах коллективного использования. Автоматика и вычислительная техника, 1980, № 6, с. 56-62.

79. Baker K.R. A note on operating policies for queue M/M/1 with exponential startus. -INFORM. Can. J. Oper. Res. and Inform. Process, 1973, v.11, N1, p. 70-72.

80. Bartoszewicz J», Rolski T. Queueing system with a reserve serwice channel. -Zast. mat., 1970, v. 11, N4» p.439-449.

81. Boel R.K., Benes V.E. Recursive nonlinear estimation of a diffusion acting as a rate of an observed Poisson process.

82. EE Trans, on Inf. Theory, 1980, v. IT-26, U5, p. 561-575.

83. Clevenson M.L., Zidek J.V. Bayes linear estimators of the intensity function of the nonstationary Poisson process. —J.of Amer. Stat. Assoc., 1977, v.72,' U357, p. 112-120.

84. Connor M.A. Optimal addition of servers time dependent queueing process. -Int. J. Contr., v.12, N2, p. 353-356.

85. Davidson P.M., Carlson R.T. Point process estimators of Gaussian optical field intensities. -IEEE Trans. Inform. Theory, 1979, v.IT-25, N5, p. 620-624*

86. Eisen M., Tainter M. Stochastic Variations in Queueing Processes. -Oper. Res., 1963»f v. 11,p. 922-927.

87. Eisenberg M. Two queues with changeover times. -Oper. Res., 1971, v.19, N2, p. 386-401.

88. Perenstein E.,1 Wydro K. A method of dinamical adapting of the service system to the varying arrival streams. -Math. Res., 1980, v.5 p. 352-356.

89. Heyman D.P. Optimal operating plicies for M/G/1 queueing systems. -Oper. Res., v.16, F2, p. 362-382.

90. Jo Kyung Y. Optimal service rate control of exponential queueing systems. -J. Oper. Res. Soc. Jap.,! 1983, v.26, U2, p. 147-165.

91. Kobayashi H., Konheim A.G. Queueing models for computer communication system analysis. -IEEE Trans. Commun., 1977, v.COM-25, H1, p. 2-29.

92. Kogan Ya. A., Litvin V.G. Computing the characteristics of aqueueuing system with a finite buffer and operating in a random environment. -Automat. Remote Contr., 1976, v.37» N12, p. 1828-1835.

93. Mitchel B. Optimal service-rate selection on an M/G/1 queue* -SIAM J. Appl. Math., 1973,1 v*24, N1, p. 19-35.

94. Naor P.,' Yechiali TJ. Queueing problems with heterogeneous arrivals and service» -Oper. Res., 1971, v.9, p. 722-734»

95. Nelson R*T. A decision-making model for applications of queueing theory. -AIIE Trans. 1970, v*2,3 N2, p. 112-117*99» Neuts M.F* A queue subject to extraneous phase cha nges. «*' Adv* Appl. Prob., v.3, N1,' p. 78-119.

96. Sykes J.S. Simplified analysis of an alternating priority queueing model with set-up times. -Oper. Res., 1970, v.18, N6, p. 1182-1192.

97. Zacks S., Yadin M., Analitic characterisation of the optimal , control of a queueing system. -J. Appl. Probab., 1970, v.7» ИЗ, p. 617-633.

98. Коротаев И.А., Терпугов А.Ф. Приближенный расчет характеристик адаптирующейся резервной ЭВМ. Автоматика и вычислительная техника, 1982, № с. 83-87.

99. Коротаев И.А., Терпугов А.Ф. Приближенный расчет характеристик адаптирующихся многолинейных систем массового обслуживания со вспомогательными приборами. Автоматика и вычислительная техника, 1982, № 6, с. 61-65.

100. Коротаев И.А. Приближенный расчет средней длины очереди в адаптирующихся системах массового обслуживания с переменной интенсивностью обслуживания. В кн.: Управляемые системымассового обслуживания. Вып. I. Томск: Изд-во ТГУ, 1982, с. 79-86.

101. Коротаев И.А. Приближенный расчет характеристик адаптирующейся CMQ с одним прибором и двумя входящими потоками.

102. В кн.: Управляемые системы массового обслуживания. Вып. 2. Томск: Изд-во ТГУ, 1983, с. 80-88.

103. Коротаев И.А. Адаптивная оценка интенсивности дважды стохастического пуассоновского процесса. В кн.: Управляемые систе мы массового обслуживания. Вып. 3. Томск: Изд-во ТГУ, 1984, с. 50-57.

104. Коротаев И.А., Терпугов А.§. Приближенный метод расчета адаптирующихся систем массового обслуживания с резервным прибором. В кн.: П-е Всесоюзное совещание-семинар "Оптимизация динамических систем". Минск, 1980, с. 38-39.

105. Коротаев Й.А. Приближенный расчет характеристик адаптирующейся системы массового обслуживания с двумя интенсивностями обслуживания. В кн.: Математические методы в задачах управления. Пенза, 1981, с. 12-13.

106. Коротаев И.А. Адаптирующиеся системы массового обслуживания с переменной интенсивностью обслуживания. В кн.: Всесоюзная конференция "Теория адаптивных систем и ее применения". Тезисы докладов и сообщений. М.-Л., 1983, с. 392.