Оптимальное управление немарковскими потоками в системах с разделением времени тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Зорин, Андрей Владимирович

• Зорин, Андрей Владимирович
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Зорин, Андрей Владимирович

Введение

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 строится математическая модель в виде векторной марковской цепи, описывающей изменение состояния обслуживающего устройства, флуктуацию длин очередей и состояния внешней среды. Арифметические свойства этой цепи выражаются через рекуррентные соотношения для распределения цепи и для производящий функций этого распределения. Проводится классификация состояний цепи. Условия существования стационарно

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Зорин, Андрей Владимирович

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

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

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

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

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

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

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Зорин, Андрей Владимирович, 2005 год

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