Оптимальное управление немарковскими потоками в системах с разделением времени

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

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

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

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

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

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

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

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

Заключение

.