Содержание к диссертации
Введение
I. Неординарные потоки в марковской случайной среде 13
1.1. Основные виды входных потоков 13
1.2. Модель неординарного потока, вероятностная структура которого задается марковской цепью 16
1.3. Общий вид производящих функций и мгновенная интенсивность потока 20
И. Кибернетический подход при изучении систем обслуживания немарковского потока 25
ИЛ. Традиционный и кибернетический подходы при построении моделей систем обслуживания 25
II.2. Арифметические свойства векторной случайной последовательности, описывающей динамику состояний немарковской среды и флуктуацию длиночередей 29
П.З. Предельные свойства векторной случайной последовательности, описывающей поведение системы обслуживания 37
II.4. Период занятости системы 42
III. Дискретные управляющие системы обслуживания немарковских потоков в классе алгоритмов с разделением времени 49
III. 1. Постановка задачи на содержательном уровне и описание системы с использованием кибернетического подхода 49
Ш.2. Построение управляемой векторной марковской цепи 51
III.3. Необходимые и достаточные условия существования стационарного распределения 62
Ш.4. Графическая интерпретация условий существования стационарного режима системы 77
IV. Оптимальное управление в стационарном режиме 92
IV. 1. Исследование стационарного распределения с точки зрения независимости состояния среды от состояния системы обслуживания 92
IV.2. Получение явных формул и функциональных соотношений для стационарного распределения состояний системы 98
IV.3. Вычисление экономического критерия качества и оптимальное управление в случае стационарной случайной среды 110
IV.4. Вид экономического критерия качества в случае постоянных интенсивностей первичных потоков и решение задачи оптимизации 116
V. Имитационное моделирование системы в случае эрланговского распределения длительностей обслуживании и переналадок 121
V.I. Планирование имитационного эксперимента 121
V.2. Сравнение различных алгоритмов управления в случае зависимости ин- тенсивностей первичных потоков от состояния нестационарной среды . 126
V.3. Качественное исследование основных характеристик имитационной модели в зависимости от параметров системы и алгоритма управления по токами 130
Заключение 135
Литература 137
- Модель неординарного потока, вероятностная структура которого задается марковской цепью
- Арифметические свойства векторной случайной последовательности, описывающей динамику состояний немарковской среды и флуктуацию длиночередей
- Необходимые и достаточные условия существования стационарного распределения
- Получение явных формул и функциональных соотношений для стационарного распределения состояний системы
Введение к работе
Характеристика изучаемой темы в целом
Начало исследования процессов образования очередей пришлось на первую половину двадцатого века. Общепризнано, что пионерские работы в этой области принадлежат датчанину А. К. Эрлангу, построившему в 1908-1922 годах математическую модель работы автоматических телефонных станций и объяснившему природу задержек абонентов этих станций [1]. Фундаментальные исследования по теории очередей, или теории массового обслуживания, принадлежат многим видным математикам XX века — Л. Такачу, Т. Л. Саати, Д. Р. Коксу, У. Д. Смиту, Л. Клейнроку, Дж« Ф. Кингмэну, Ф. Поллачеку, Д. Дж. Кендаллу, М. С. Бартлетту и др., в нашей стране — прежде всего, А. Я. Хинчину, А. Н. Колмогорову, Б. В, Гнеденко, Ю.В. Прохорову, А. А. Боровкову, И. Н. Коваленко, Г. П. Климову, А. Д. Соловьеву, Г. П. Башарину, Б. А Севастьянову, Ю. К. Беляеву. Результаты теории массового обслуживания представлены во многих монографиях, например [2, 3, 4, 5, 6] и др.
Рост интереса к теории массового обслуживания связан прежде всего с научно-техническим прогрессом цивилизации в XX веке. Начав с автоматических телефонных станций, исследователи обратились к задачам описания транспортных потоков, таких как автомобильное движение, работа крупных международных аэропортов, речное движение и работа портов, а также к различным задачам управления производством (классическая задача о станках А. Я. Хинчина). С появлением во второй половине XX века сложных электронно-вычислительных комплексов возникла задача оптимального распределения ресурсов процессоров, памяти и периферийных устройств в таких системах, что привело к постановке новых задач теории массового обслуживания.
К настоящему времени построенные и изученные модели сложных систем крайне разнообразны. Особый интерес в наши дни представляют, во-первых, системы с изменяемыми интенсивностями поступления и обслуживания требований, во вторых, системы с ненадежным прибором, в третьих, системы с включением и выключением дополнительных устройств обслуживания, далее, системы с изменяемой дисциплиной очереди, а также системы, в которых решаются задачи по управлению входными потоками требований, например, в классе приоритетных алгоритмов, в классе циклических алгоритмов, в классе алгоритмов с разделением времени, и т.д.
Опишем те направления теории массового обслуживания и те классы задач, на пересечении которых находится предлагаемая диссертация.
В вычислительно-информационных системах с шестидесятых годов стали разрабатываться так называемые системы разделения времени [7], дававшие доступ к вычислительным ресурсам нескольким пользователям одновременно, а зачастую и пользователям, находящимся на значительном удалении от вычислительного комплекса. При мерно в то же время стали появляться математические работы, посвященные исследованию систем обслуживания в классе алгоритмов с разделением времени. В работе [8] Ю. К. Беляевым рассматривается простейшая модель системы с разделением времени. Предполагаются простейший входной поток и показательное распределение времени обслуживания. Требование в системе обслуживается не дольше фиксированного кванта времени, причем если по окончании кванта требований в системе нет, то обслуживание требования продолжается. Если же в системе будут находиться другие требования, то обслуженное требование встанет на ожидание в конец очереди. В 1963 году появилась работа Л. Такача [9], в которой исследовалась система с одним входным пуассоновским потоком, произвольным временем обслуживания и бернуллиевской обратной связью. Суть бернуллиевской обратной связи заключается в том, что каждое требование после обслуживания с заданной вероятностью возвращаесть в очередь, а с противоположной вероятностью покидает систему. В последующие годы появилось множество работ, в том числе и монографий, посвященных изучению вычислительных комплексов методами теории массового обслуживания [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]. В 1974 году Г. П. Климов опубликовал статью [21] (а также [22]), в которой был приведен алгоритм оптимального управления пуассоновскими потоками разнотипных требований в классе алгоритмов с разделением времени по критерию минимальной стоимости пребывания требований в системе в единицу времени. В частности, было показано, что оптимальное управление лежит в классе управлений с относительными приоритетами. Эта задача была обобщена В. В. Рыковым [23] на случай ветвящегося потока требований на повторное обслуживание. М. А. Федоткин [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]. При этом рассматривались входные потоки, интенсивность которых неизменна при всех состояниях среды, а смена состояния среды могла происходить только в моменты переключения обслуживающего устройства.
Основные задачи и содержание работы
В данной работе рассматривается система с разделением времени, обобщающая известные системы Г. П. Климова, М. А. Федоткина и А. А. Высоцкого. Отличие заключается в выбранной модели входных потоков. Считается, что входные потоки формируются в случайной среде, которая определяет, поступают ли требования поодиночке или группами, какие распределения интервалов между группами или одиночными требованиями, и наконец, какое распределение имеет число требований в группе. Отличие изучаемой модели среды от известных в литературе заключается в том, что моменты смены состояний среды синхронизированы с моментами окончания работы обслуживающего устройства. Поскольку длительности обслуживании и переналадок имеют произвольное распределение, процесс изменения состояния среды не является марковским. Принимается, что интервалы между поступлениями групп или одиночных требований распределены по показательному закону, параметр которого для каждого потока зависит от состояния внешней среды. А. А. Высоцкий предполагал конкретный вид распределения количества требований в группе. В предлагаемом исследовании это ограничение снято, но накладывается некоторое условие па область аналитичности производящей функции распределения размера группы. Заметим далее, что наличие переналадок в изучаемой системе с точки зрения изучения математической модели равнозначно наличию "прогулок", "ориентации" прибора, однако решение задачи оптимизации оказывается безразличным к наличию или отсутствию переналадок, см., например, [25]. Целью ра боты является изучение системы с разделением времени с общей позиции управляющей системы и использование кибернетического подхода при построении модели.
Диссертационная работа состоит из введения, пяти разделов, заключения, списка использованной литературы и приложений. В первом разделе строится математическая модель потока, управляемого марковской цепью. Предполагается, что процесс изменения состояния среды является марковским процессом. Подраздел 1.1 содержит обзор классических подходов к описанию входных потоков. В подразделе 1.2 на содержательном уровне описывается неординарный поток, управляемый марковской цепью. Строится его математическая модель. В подразделе 1.3 находятся производящие функции для совместного распределения числа поступивших требований и состояния среды. Вычисляются некоторые характеристики потока. Во втором разделе изучается простейшая система обслуживания с немарковским входным потоком. Отличие этого потока от предыдущего в том, что процесс изменения состояния среды не является марковским процессом. Подраздел II. 1 содержит сравнительное описание классически-го и кибернетического подходов к построению модели управляющей системы массового обслуживания. На примере однолинейной системы обслуживания алгоритмом с разделением времени потока, формируемого в случайной среде, демонстрируются основные этапы следования кибернетическому подходу: приводится схема системы, перерабаты-вамая ей информация, ее координаты и функция. Для рассматриваемого примера в разделе П.2 строится векторная случайная последовательность, описывающая изменение состояния случайной среды и числа требований в очереди. Доказывается, что построенная последовательность является марковской цепью и находятся соотношения, связывающие распределение этой цепи за один шаг. Исследование предельных свойств этой цепи проводится в подразделе И.З. Основной результат этого подраздела — теоремы, содержащие необходимое и достаточное условия существования стационарного режима функционирования системы. Наконец, в предположении, что эти условия выполнены, в подразделе II.4 изучается период занятости системы в терминах преобразований Лапласа-Стилтьеса функции совместного распределения периода занятости системы и состояния среды во время простоя прибора. В третьем разделе строится модель управляемой системы обслуживания нескольких конфликтных потоков в классе алгоритмов с разделением времени. При этом считается, что, как и во втором разделе, входные потоки формируются в случайной среде. Описание функционирования системы в приводится подразделе III. 1. Здесь же выявляются основные компоненты рассматриваемой системы с точки зрения кибернетического подхода. В подразделе Ш.2 строится математическая модель в виде векторной марковской цепи, описывающей изменение состояния обслуживающего устройства, флуктуацию длин очередей и состояния внешней среды. Арифметические свойства этой цепи выражаются через рекуррентные соотношения для распределения цепи и для производящий функций этого распределения. Проводится классификация состояний цепи. Условия существования стационарно го распределения цепи приводятся в подразделе III.3. В подразделе III.4 приводится графическая интерпретация найденных условий, сравнивается их сила и выявляется их непротиворечивость. Четвертый раздел посвящен постановке и решению задачи оптимального управления формируемыми в случайной среде конфликтными потоками в классе алгоритмов с разделением времени. Таким образом, новый раздел продолжает исследование системы из раздела III. В подразделе IV. 1 вводится понятие независимости в стационарном режиме среды и состояния системы обслуживания, включающее состояние накопителей и прибора. Находятся необходимое условие зависимости и достаточное условие независимости. В подразделе IV.2 получены явные формулы для случая стационарной среды и функциональные соотношения в случае нестационарной среды для стационарного распределения состояний системы. Как следствие этих формул получен критерий существования стационарного распределения в системах, в которых интенсивность поступления требований постоянна. В подразделе IV.3 вводится функционал, характеризующий экономическую эффективность функционирования системы. Для случая стационарной случайной среды находится оптимальное управление. В подразделе IV.4 задача оптимизаци решается для потоков, интенсивность которых постоянна. Поскольку изученные в подразделах IV.3, IV.4 случаи не исчерпывают всех возможных ситуаций, в пятом разделе продолжается изучение системы средствами имитационного моделирования. Описание имитационного эксперимента содержится в подразделе V.I. Поскольку общая модель содержит большое количество параметров и время моделирования существенно зависит от числа потоков в имитируемой системе, в подразделе V.2 проводится исследование систем с различным числом входных потоков, причем учитываются оценка средней стоимости пребывания требований за такт, оценка загрузки системы и оценка среднего времени пребывания в системе произвольного требования. Наконец, в подразделе V.3 проводится изучение влияния различных параметров входных потоков, обслуживания и переналадок на показатели работы системы. Предложена формула для оценки загрузки.
Данная работа была выполнена в рамках следующих г/б тем, проводимых на кафедре прикладной теории вероятностей ННГУ и в лаборатории теории вероятностей и математической статистики НИИ прикладной математики и кибернетики ННГУ: "Математическое моделирование и создание новых методов анализа динамических систем и систем оптимизации" (номер государственной регистрации 01.2.00107703), "Анализ дискретных управляющих систем обслуживания и систем вычисления булевых функций" (номер государственной регистрации 01.2.00100352), "Синтез и сложность алгоритмов для задач конфликтного обслуживания и диагностики" (номер государственной регистрации 01.2.00100352).
Результаты исследований используются при чтении специального курса "Системы с разделением времени" для студентов пятого курса факультета ВМК ННГУ, специализирующихся по кафедре прикладной теории вероятностей.
Результаты диссертации были представлены на следующих семинарах, конференциях и конгрессах:
1. Конференция "Вычислительная математика и кибернетика 2000" (Нижний Новгород, 2000 г.).
2. Международная конференция "Прикладная статистика в социально-экономических проблемах" (Нижний Новгород, 2003 г.).
3. Международная конференция "Колмогоров и современная математика" (Москва, 2003 г.).
4. Международная конференция "Современные математические методы анализа и оптимизации телекоммуникационных сетей" (Гомель, 2003 г.)
5. Научно-техническая конференция "Математика и кибернетика 2003" (Нижний Новгород, 2003 г.)
6. XXIV Международный семинар по проблемам устойчивости стохастических моделей (Юрмала, 2004 г.).
7. VI Международный конгресс по математическому моделированию (Нижний Новгород, 2004 г.).
Основные результаты опубликованы в работах [86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
Модель неординарного потока, вероятностная структура которого задается марковской цепью
Пусть {x(t)\ t 0} — марковский процесс, x(t) Є { г\ е } и матрица переходных интенсивностей имеет вид: -а,} аг Л = «2 -а2
Мы будем интерпретировать случайный элемент x{t) как состояние случайной среды в момент L Введем последовательность 0 = t0 tг t2 ... моментов времени, в которые происходит смена состояния этого процесса. Относительно потока требований сделаем следующие предположения. Если событие {ш: x(t, ш) — е } имеет место на интервале [fi? ti+1), то требования на этом интервале времени поступают группами так, что интервалы между группами показательно распределены со средним (А )-1 и количества требований в группах представляют собой независимые случайные величины с производящей функцией f(k (z) распределения р\ , р2 , .. .числа требований в группе. Таким образом, значения процесса ( (t), x(t)) ПРИ t{ t tihi зависят только от значения (r)(ti), x(h))i но не от предыстории с t 1±. Таким образом определенный процесс (Ш, х№ t о} (і) будет марковским процессом с пространством состояний {{х, eik)):x = 0t 1, ..., к=1, 2}. Обозначим вероятность события {ш: r)(t, ш) = #, х(, ш) = е } через Р(х, к, t). Поскольку в начальный момент времени требования по потоку осутствуют с вероятностью единица, имеем: Р(0, 1, 0) = Р({ш: Х(0, ш) = е »}), Р(0, 2, 0) = Р({а;: Х(0, и) = е 2 }). Положим P({CL?: ,\(0, Ш) = е }) = р. Всюду далее производную по переменной t будем обозначать точкой над именем функции. Теорема 1. Одномерные распределения процесса (1) удовлетворяют следующей системе уравнений: Р(0, 1, t) = -(«і + Л(1))Р(0, 1, t) + а2Р(0, 2, ), (2) Р(0, 2, t) = в1Р(0, 1, t) - (а2 + А 2 )Р(0, 2, t), (3) Р(ж, 1, t) = (a1 + \(l))P(x, 1, t) + a2P(x, 2, t)+ +А(1 ЕІЇЇ Р(Я/,І,О, (4) х =0 P(x, 2, t) = atP(x, 1, t)-{a2 + \i2))P(x, 2, t)+ +A 2) рЦ,Р(о; , 2, ), x = 1, 2, ... . (5) x =0 Марковская цепь (1) является однородной.
Доказательство. Рассмотрим возможные изменения состояния процесса (1) за промежуток времени от t до t + , 0. Заметим, что переходы в состояния с меньшим значением r}(t +t ) по сравнению с T}(t) имеют нулевую вероятность. Поэтому такие переходы в дальнейшем учитываться не будут и это не будет специально оговариваться в каждом случае. Переход из состояния (0, е ) в момент t в состояние (0, е ) в момент t+t возможен следующими путями: состояние среды не изменилось и не пришло ни одной заявки; состояние среды изменилось четное число раз и не пришло ни одной заявки. Вероятность первого события есть (l-A V+o( ))(l-ai +o( ))- Вероятность последнего события есть o[t ). Переход из состояния (0, е ) в момент t в состояние (0, е 1)) возможен следующим образом: среда до момента t + et , 0 є 1, находилась в состоянии е и не пришло ни одной заявки, а после t+et среда перешла в состояіше 1 и тоже не пришло ни одной заявки; состояние среды между t n t + t менялось нечетное число раз. Вероятность первого события есть (a2t +o(t ))(l—X et +o(t ))(l—А (1—e)t +o(t )), или (a2t + o(t ))(l — (А е + A (l — e))t + o(t )). Вероятность последнего события есть опять o(t ). Таким образом, по формуле полной вероятности находим: Р(0, 1, t + t ) = P{0, 1, t)(l - axt -f-o(t))(l-A(1V + o{t ))+ + P(0, 2, t)(a2t + o(t ))(l - (A 2 + А (1 - e))t + o(t )) + o(t ). Перенесем P(0, 1, t) влево и разделим на t . Получим: тм+О- №і.«) = _(oi + Л „)т h t) + йгР(0і 2, () + Й2. При t — 0 предел правой части последнего равенства существует, значит существует и предел левой части, равный производной Р(0, 1, і). Окончательно получаем уравнение: Р(0, 1, tH-Caj + AjPtO, 1, t) + a2P(0, 2, t).
Рассуждая аналогично, мы находим, что процесс (1) может попасть в состояние (0, е ) к моменту t + t из состояния (0, е 2)) в момент t без изменения состояния среды с вероятностью (1 — \(2Ч + o(t ))(l — a2t + o(t )); из состояния (0, є 1 ), единожды сменив состояние среды в некоторый момент t + et , 0 е 1, с вероятностью (a2t + o(t ))(l — — (єА +(1—e)\ )t +o(t )); сменив состояние среды больше одного раза с вероятностью o(i ). Поэтому, пользуясь формулой полной вероятности, находим: Р(0, 2, t + О = Р$, 2, t)(l - a2t + o(t ))(l - A(2)t + o(0)+ + P(0, 1, i)(a/ + 0(0)(1 - (А(1)є + A(2)(l - e))t + o(t )) + o(i ), и P(0, 2, 0 = 0 (0, 1, t) - (a2 + A(2))P(0, 2, ).
Для любого а; = 1, 2, ... переход в состояние (ж, е ) может осуществляться из любого из состояний (0, е 1)), (1, е ), ... ,(ж, е(1 ), (0, е 2 ), (1, е 2 ), ... ,(ж, е 2 ). Без смены состояния среды переход может произойти из состояния (х1, е 1)), х = 0, 1, ..., ж — 1, с вероятностью (1 — aat + o(i ))(p .2I/A 1V + o(i )). Вероятность отсутствия перехода из (ж, е 1)) равна (1 — % + о( ))(1 — Х Н -+- o(t )). С одной сменой состояния среды (в момент t + є?) переход возможен из любого состояния вида (ж , е ), Xі = 0, 1, ..., ж. Рассмотрим переход из состояния (ж , е 2)) для х1 = 0, 1, ..., ж — 1. До момента t + et , О є 1, может придти любое число т/ заявок, у = О, 1, ..., ж , а остальные (ж — у) заявки должны поступить после момента t-\-et . Переход из состояния (ж, е 2 ) возможен с вероятностью (a2t + o(t )){l - Х(2Н + o(f)). Остальные переходы имеют вероятность порядка o{t ). Применяя формулу полной вероятности, последовательно вычисляем:
Арифметические свойства векторной случайной последовательности, описывающей динамику состояний немарковской среды и флуктуацию длиночередей
Все рассматриваемые случайные объекты определяются или задаются конструктивно на некотором вероятностном пространстве (Г2, #, Р(-)); здесь П — пространство описаний элементарных исходов, # — г-алгебра событий А С П, Р(-) — вероятностная мера на #. В качестве дискретной временной шкалы функционирования системы выберем слу чайные моменты времени {г4; і — 0, 1, ...}, где т0 = 0 и каждый т есть момент окончания обслуживания требования, причем гі+1 ц. Последнее неравенство отражает тот факт, что одновременно не может завершиться обслуживание более чем одного требования. Будем говорить, что Tj — момент окончания г-го такта работы системы. Момент начала г-го такта совпадает с т или больше т _х. В эти моменты происходит смена состояний внешней среды согласно следующему правилу. Пусть {щ; і = О, 1, ...} — последовательность независимых случайных величин, имеющих равномерное распределение на интервале (О, 1) и отображение Ф: {е , е(2)} х (0, 1) - {е(1), е(2)} определяется соотношением: Ф(е , а) = (Є(1) ЄСЛИ I е 2\ если ак1 а 1.
Тогда смена погоды описывается последовательностью случайных элементов {ХІ\ і = = 0, 1, ...}, ХІ Є {еІг\ є 2)}, связанных соотношением: Хні = ф( і « ) (7) и ХІ есть состояние среды на интервале времени (ті5 ті+1]. Известно [111], что так построенная последовательность {х г = 0, 1, ...} образует марковскую цепь. Введем теперь используемые в этом разделе случайные величины и элементы. Пусть гц , г = О, 1, ..., определяет число первичных требований, пришедших на промежутке (ri} ri+1] (2) до начала работы прибора. Далее, обозначим через г}\ , г = 0, 1, ..., случайное число первичных требований, пришедших на промежутке (гі5 ті+1] за время работы прибора. Наконец, случайная величина Щ , і = 0, 1, -.., задает число вторичных требований, пришедших на промежутке (тІУ ті+ї]. Положим 7 = Vi + % + Через обозначим наибольшее число требований, которое может быть обслужено на промежутке (гі5 ті+1], а через — величину реального изменения длины очереди вследствие обслуживания и перенаправления на промежутке (гі} ті+1], f задает поток насыщения на этом промежутке. Через я{ обозначим длину очереди в момент т- с учетом прихода вторичной заявки. Пусть Д$ — это время активной работы прибора на промежутке (ті} ті+ї], при этом Д{ ri+1 — т{. Напомним, что строгое неравенство имеет место, если в момент ц очередь пуста. Из условий функционирования системы с разделением времени, определения и выбора последовательности {TJ; І — 0, 1, ...} получаем = 1. С другой стороны, стратегия механизма обслуживания [24] для нашей системы при любом г = О, 1 "?/(!) (2) (3) .\ 1, ... определяется равенством = 7Дх{, щ , 7 , щ , ) и ограничениями вида Яг&и v\l\ Vi2\ Tj?\ 6) тїп{щ + і74(1), &}. Поскольку всегда + rj 1, то min{j + ц- , } = & = 1- Имеем очевидное равенство .= - rj\ \ следовательно, { Ф min-f + щ » »} Таким образом, для изучаемой системы с разделением времени стратегия механизма обслуживания не является экстремальной [107]. Учитывая это об стоятельство и неограниченность размеров очередей, находим, что последовательность {х{; і = 0, 1, ...} удовлетворяет рекуррентному соотношению xi+1 = Xi + TJi -\-Щ —І, или fi+1 = xf + т]{ — 1. Итак, доказана следующая Лемма 1. Случайная последовательность {( ХІ)І і = 0, 1, ...} удовлетворяет рекуррентному по і — 0, 1, ... соотношению: ( ї+і» Хі+і) = ( ї + Чі - 1, Ф(х4, «І)) Обозначим через i/f вектор (х, ХІІ Д»)? И пусть для х — 0, 1, ... и fc = 1, 2 Л4(х, fc) = {a : (а;) = x, ХІІШ) e }. Для задания входных потоков определим свойства условных распределений компоненты {т ; г = 0, 1, ...} маркированного точечного процесса {(г{, и Ї/J; г = 0, 1, ...}. При фиксированных значениях метки ( А \ (1) (2) (3) i/4 = (х , ХІЇ Д») величины щ , 7 j Ї?І независимы и их распределения имеют простой вид. Вероятность Р({си: щ (и) = 0}\Л{(х, к)) равна 1 при х = 1, 2, ... и fc = = 1, 2. Далее, Р({о;: 7?f V) = с}Л4(0, fc)) = pfc) при с = 1, 2, ... и к = 1, 2. Пусть F(t, г; fc) = exp{A (/(A: (z) - l)t} и Pc(t; fe)c! = J Ffa «і k) при с = 0, 1, ... Z-0 oo ,(2) Для b = 0, 1, ... вероятность P({w: 7 (w) =Ь}\А{(х, к)) равна JPb(t; k)dB(t). Нако o нец, P({cu: щ (tu) = 1}(Л{(о;, fc)) = p, а вероятность P({cu: щ (u ) — 0}\Ai(x, fc)) равна 1 -p. Обозначим ?4(у, 6, у1) = {w: (w) = у, г$ \ш) = b, % 3)(w) = у1} для і, у, b Є Є {0, 1, ... } и у1 Є {0, 1}. Заметим, что Р В,(у, b, у ) для всех х0 Є {0, 1, ...}, Xj Є {0, 1, ...},..., xt_! {0, 1, ...}, / Є {1, 2}, &г Є {1, 2}, ..., кг_± Є {1, 2}. Величина ск4 должна быть независимой от векторов 1 , «1 » Щ гі = ! » ПРИ каждом г = 0, 1, Лемма 2. Последовательность {(л , Xi)j г = 0, 1, ...} при заданное начальном векторе (х0, Хо) является марковской цепью. Доказательство. Чтобы доказать лемму, требуется установить равенство: t-i Р Мъ, Ь) П AuK Ю }=Р{ЧХі, і)Иі-і( «-1, ki-l)) І1=0 для всех х0, хг, ..., ХІ Є {0, 1, ...}, fc0, fct, ..., fc; Є {1, 2}. Суммируя по формуле полной вероятности, имеем:
Найденные рекуррентные соотношения позволяют провести классификацию состояний марковской цепи {(хі} ХІУІ = 0, 1, ... }. Лемма 3. Марковская цепь {(х{, ХІУІ « = 0, 1, ...} является неразложимой и апериодической.
Доказательство. Справедливость следющих утверждений проистекает из соотношений теоремы 3. В состояние (w, е")) можно попасть за один шаг из любого состояния (х, е ) сж ш. Для х w с положительной вероятностью можно совершить последовательность переходов (х, е ) _ (х - 1, е ) - ...- (w + 1, е ) -»(to, eW). В частности, из любого состояния можно попасть в состояние (0, е 1 ) и наоборот, из состояния (О, е ) можно попасть в любое состояние. Следовательно, все состояния существенные и образуют один сообщающийся класс. Апериодичность следует из того, что что с положительной вероятностью можно совершить переход (to, е ) — (го, е ) за один шаг. ( оо оо \ (1 — р)JPi(t; k)dB(t)+pJ P0(t, k)dB(t)\. о о / Поскольку все состояния цепи существенные и образуют один класс сообщающихся состояний, то может иметь место только одна из следующих ситуаций [113]. Либо для любого состояния (х, е ) имеет место lim Р(Л4(а;, к)) — 0, либо существует единствен ное стационарное распределение, то есть набор положительных чисел Q(x, I) таких, оо что Yl(Q(x 1) + Q(XJ 2)) = 1 и для всех w = 0, 1, ..., к = 1, 2
Необходимые и достаточные условия существования стационарного распределения
В настоящем подразделе мы найдем как необходимые, так и достаточные условия, при которых марковская цепь {(Ц, хь ХІ)І « = 0, 1, ...} имеет стационарное распределение. Физический смысл существования такого распределения раскрывается в следующей лемме.
Лемма 9. Пусть верно равенство (28) при всех (Г , х, е ) изГхХ х {е \ е }, f (т \ \ тогда средние М Y2 j г] і { неограниченно возрастают при г — оо. Доказательство. Пусть выполняются условия леммы. Напомним, что через 1(A) = = 1(А, ш) обозначен индикатор события А (Е # (см.стр. 37). Тогда для каждого 7 Є Г, х Є X, к = 1, 2 и произвольного М 0 найдется целое число г0(у, х, к, ЛГ) такое, что для всех г г0(7і xi J - 0 верно неравенство P({w: ГІ(Ш) = ъ iM = ж, ХІИ = e(fc)}) Єї для г = g + . Заметим, что все х і неотрицательны. Из цепи очевидных неравенств
Итак, неограниченное возрастание средних МI 5D xj,» ) Ї О г является необходимым условием отсутствия стационарного распределения в системе. Этот факт будет далее использован при доказательстве достаточных условий существования стационарного распределения. Наличие стационарного распределения в изучаемой марковской цепи имеет простую физическую интерпретацию. А именно, длины очередей ограничены по времени тогда, когда существует стационарное распределение. Приведем здесь выражение для среднего числа заявок в системе в момент т через производящие функции:
Для дальнейшего необходимо сделать следующие предположения. Ш. Первичное требование, поступившее в любую очередь, с положительной вероятностью покидает систему через конечное число повторных обслуживании.
Введем обозначения: Q = {Ргз)г,і-Т ті В единичная матрица размерности m х га. Пусть Г — символ транспонирования. Лемма 10. Если имеет место предположение П1, то матрица Е — Q обратима и (Е Q)-1 0. Доказатсгъство. Пусть Qx — (р1п, р2п, , Ртп)Т- Рассмотрим цепь Маркова {Ef; г = 0, 1, ...}, Ef Є {1, 2, ..., п}, с каким-нибудь начальным распределением и переходной матрицей блочного вида Содержательно такая цепь отображает историю пребывания произвольного требования в системе. Переход в поглощающее состояние п соответствует выходу требования из системы, а переходы внутри множества состояний {1, 2..., га} — перенаправлениям на повторное обслуживание. Пусть предположение Ш выполнено. Матрица вероятностей перехода за і шагов равна
Это соотношение связывает производящие функции Ш(і+2)(у, п, к), фЮ(ь, j, к) и вероятности Р(Аі(щ {у }, к))) за два шага. Пусть v(u) — (v u), v2(u), ..., vm(u)) — вектор дифференцируемых функций одного (комплексного) переменного и, удовлетворяющих условиям г (0) — 1, г -(О) 0 для всех j = 1, 2, ..., т. Такой выбор гарантирует, что точки и 0 будут отображаться в точки Vj 1 хотя бы в некоторой малой окрестности точки и = 0. Дополнительно потребуем, чтобы числа v j(0) удовлетворяли системе уравнений Д+(«)=тах] аыд , (г/(«))д )(г;(м))Яг(«(«)):г = 1,2,..., m, fc= 1,2І. Из определения следует, что Яь(0) = 1. Кроме того, вследствие (36), R+(u) 1 для всех и Є (0, U0): UQ 0. В силу ограничений на функции ft (z), найдется число щ Є Є (0, С/х), 0 Ux UQ, такое, что ft (уг(щ)) определены. Заметим, что їм- v r(0) 0 влечет fr (Угіщ)) 1. Из вышесказанного выводится оценка 2 т т№(ь(щ), п, 1) + rot 2 (v(Ul), п, 2) Л+(щ) Е Е ф(і)( (иі), г, к)+ fc=l г=1 2 m (fc) + R+MEEp n fo(n) Ш/ Ы)-і)-д+(«і)х fc=l r=l 1 2 2 m ,(fc) fc=l /b=l r=l t Выберем в качестве распределения элемента (Г0, х0, Хо) распределение, сосредоточенное на конечном числе значений этого элемента. Положим 2 2 т fc=l fc=l г=1 2 m Mf2) = («ШІ? + Я Ы) Е Е(/ ( («г)) - 1) fc=l Г=1 при і = 2, 3, Так построенная последовательность {М+ , г = 0, 1, ... } мажорирует последовательность {9Л()(г;Ы, гг, 1) 4- 9Я(і)( (иі), n, 2); г = 0, 1, ... } (37) и имеет предел, следовательно, она ограничена. Тогда последовательность (37) также ограничена. Следовательно, радиус сходимости степенного ряда, представляющего 2), больше единицы. Из равенства 2 m ЯЯ (ti, n, A) = ]Г «» Е да(і)К s 0 (38) следует, что радиус сходимости ряда 9Jl )(f, s, /) при всех г, s, / тоже больше единицы. Действительно, пусть и = щ. Тогда ь {щ) 1 и ряд 971 («(itj), s, Z) либо сходится, либо имеет бесконечную сумму для всех s = 1, 2,..., т. Кроме того, величина (ь(щ)) тоже положительна для г = 1, 2, ..., т. Поэтому бесконечной сумма быть не может, ибо ряд в левой части (38) конечен при v = ь(щ). Тогда, применяя формулу Коши = _!_ [ 0ЯЛ«(и, s, /) dvr HHP {v, s, о ,г t =l для достаточно малого є , убеждаемся, что ограничена последовательность производ ных _; » = 0, 1, ... . D=I J г aanTOfo, s, і) Вспоминая соотношение (29), убеждаемся в том, что необходимое условие равенства (28) не выполнено. Следовательно, стационарное распределение существует и оно един ственно.
Получение явных формул и функциональных соотношений для стационарного распределения состояний системы
Последние две теоремы накладывают сильные ограничения на класс систем, в которых может наблюдаться свойство независимости состояния системы обслуживания от состояния среды в стационарном режиме. Это ограничения на случайную среду и ограничения на входные потоки. Равенства ап — а21 и а12 = а22 означают, что матрица переходных вероятностей содержит одинаковые строки. Легко подсчитать, что числа, стоящие в строках, будут совпадать со стационарным распределением для соответствующей марковской цепи. Переходные матрицы такого вида называют стационарными. Поэтому естественно случайную среду называть стационарной, если ее переходная матрица стационарна. Итак, стационарности случайной среды достаточно для того, чтобы состояние системы обслуживания было независимо от состояния среды в стационарном режиме.
Проанализируем теперь ограничения, накладываемые теоремой 22 на входные потоки. Покажем, что эти ограничения в виде неравенств не могут одновременно обратиться в равенства кроме случая, когда входной поток неизменен при любом состоянии среды. Действительно, пусть для всех первичных входных потоков выполняют д(1) д(2) д(1) д(2) ся равенства: -щ/j (z) -jfifj (z)- Отсюда сразу следует, что -щ = - у, по д(1) скольку /j (1) = fj (1) = 1, и окончательно А - = —т л Но тогда необходимо f\ (z) = / (z), то есть для потока П- состояние среды определяет интенсивность поступления групп требований, а не вероятностное распределение числа требований в группе, и интенсивности поступления групп при разных состояниях среды должны состоять в одной и той же пропорции для всех потоков. Теперь легко находим: кроме тривиального случая Л _ = Х+ . Тривиальность заключается в том, что, фактически, структура входных потоков не зависит от состояния среды. Аналогично проверяется, что q$} {v) ф z (u)- Итак, достаточное условие независимости состояния среды от состояния системы, включающее только условия на входные потоки, не может требовать обращения всех неравенств в равенства одновременно, кроме тривиального случая неизменности структуры входных потоков.
Дальнейшие исследования свойств стационарного распределения векторной последовательности {(Ц, х{, Х); г = 0, 1, ...} и решение задачи оптимального управления потоками существенно основываются на факте зависимости или независимости состояния среды от состояния системы обслуживания.
По теореме 23, условия ап = а21 достаточно для того, чтобы состояние системы обслуживания не зависело от состояния среды в стационарном режиме. Вследствие соотношений (62)-(67) производящие функции 9Jl(u, s), Ф(и, j) и вероятность Q(") (?/")) удовлетворяют уравнениям: ЩУ, j) = (ogj fy) + (1- a) ff {v))Rs{vWv, j) + ( a jf )# (»)Д,( )+ \(2) \ + (1- a /ftt;;)?? \v)R,{v) J Q(% " ), (69) m m(v, n) = J2 Wiv, e)(atf (v) + (1- a)q?\v)), (70) и, кроме того, Ol(v, п) = Ф(ь, 1) + Ф(У, 2) + ... + Ф(«, т) + Q(n\yin)). (Число а в данном контексте введено на странице 96.) Обозначим стационарную вероятность события A{{j, X, к) через Щ = ЯЯ(1, j, к), стационарную вероятность события АІ(Щ Хр к) через Ф$ = Ф(Т, j, к) и положим 9Л - (т[к\ 9Я2 \ ..., rf)r, am(v, j, к) 0Ф(«, j, fc) an = (аяь ая2, ..., 9Jijr - mw + mw, Ф = (Ф \ Ф?\ Ф )Т, Ф = = ( 1, Ф2, ..., jr = Ф(1) + Ф(2), Щк) = Ф(Г, і, л), Ф(А) = (Ф?\ Ф?\ Jigfc _. igfc — ж х я = х 91 + a ff2 x g = EcJffl + ж- 92 дг?„ ю=і V-rl #«„ j, Я = 1, 2, ..., ro, A = (Л \ A \ ..., ALfc))T = (JS - QT) k\ hf = = Ax + A2 + ... + Am , к — 1, 2. Величину Aj- можно представить как суммарную интенсивность поступления требований в j-ю очередь при состоянии среды е . Действительно, непосредственно из определения следует равенство Aj = Xj + Y Prj r і r=l то есть суммарный поток требований, поступающих в очередь О -, складывается из всех первичных требований потока П , доли pXj- вторичных требований потока П , доли p2j-вторичных требований потока П2, и т.д. Рассмотрим два частных набора параметров. Во-первых, если А = А , то р 1 = = р(2\ р = ffi2\ А = Л&\ Л+ = Л+ и вероятности из теоремы принимают вид: « (V 2U Р Р Ч UX) A? JJ 2Л (аА(2) + (1-а)Х(;У cm Л 2Л?
Поскольку Q(n)(r/(" ) 0, для существования стационарного распределения в этом случае необходимо выполнение неравенства р -{- р 1 1. Также интересно отметить, что вероятность работы каждой фазы пропорциональна доле интенсивности суммарного потока требований, поступающих в соответствующий накопитель, в общей интенсивности первичных и вторичных требований, поступающих в очереди. Эта вероятность не зависит от распределений длительностей обслуживания и переналадок. Пусть те TW /Т 2 1 + jgAW 1 + /ЗА 2 перь А ф А , но тут— = у-:—. Сомножитель, входящий в выражение для А+ А+ Q(")(?/")) в минус первой степени, преобразуем следующим образом: «(1-а) ( -1 ) Л?У»+ )-ЛЇУ +Л)+
И в этих предположениях очевидно простое необходимое условие существования стационарного распределения: а(р -{р1 ) -Ь (1 — а)(р 4-р 2 ) 1. Вероятность включения любой фазы обслуживания также зависит только от отношения усредненной интенсивности поступления заявок на эту фазу к усредненной интенсивности поступления заявок на все фазы. Этот пример показывает, что условие А = А не является необходимым для независимости состояния системы обслуживания от состояния среды в системах с обсуждаемым специальным типом внешней среды.
Рассмотрим теперь случайную среду общего вида. Пусть стационарное распределение существует и выбрано в качестве начального. Введем обозначения: т т Cf = акк ( + rik) - ук ( + ) = a r=l r=l x M ( tI ({a;: Xi(u ) = e })) - «WM (x,,,/ ({w: XM = e " })) , C« = ( f\ c?\..., C f, C = (C[k\ cik\ ..., cY ={E- QT)-l&k\
Символ к был введен на странице 93. Из определения следует, что (7(1) + С 2 = 0, С + С = 0. Для выяснения физического смысла величин CJ преобразуем определяющее их выражение следующим образом: awM ( ЛІ/({«: ХІИ = e(fc)})) - awM ( it«/({w: ХІИ = e(fc,)})) = = %P ({w: ХІИ = eW}) M (xjt, {w: XlH = e }) -- a P ({a,: XiM = е )}) M ( ЛІ {a;: XiH = e }) = 105 „ ah k кл = ЧУ : м 12 г "21 х (М (xjti {w: Xi(w) = e fc }) - М (xit4 {ы: ХіИ - eM}))
Таким образом, величина пропорциональна избытку или недостатку среднего числа заявок в очереди Oj при состоянии среды е по сравнению со средним числом заявок в той же очереди при противном состоянии среды. Заметим также, что для стационарной внешней среды число заявок в очереди не зависит от состояния среды, поэтому имеет место равенство С- — 0.
Похожие диссертации на Оптимальное управление немарковскими потоками в системах с разделением времени
