Содержание к диссертации
Введение
Глава 1. Очереди и динамическое управление 16
1.1. Управляемый марковский процесс 16
1.2. Численные методы 23
1.3. Монотонность оптимальных политик 26
Глава 2. Управляемые М/М/К системы 35
2.1. Описание модели 38
2.2. Постановка задачи 40
2.3. Минимизация среднего числа заявок 43
2.3.1. Функционал потерь 43
2.3.2. Уравнение оптимальности 44
2.3.3. Преобразование уравнения оптимальности 49
2.3.4. Свойство монотонности оптимальной политики . 52
2.3.5. Оптимальность использования быстрого прибора . 53
2.3.6. Субмодулярность функции оценок 56
2.3.7. Пороговая структура оптимального управления. Пороговая функция для NJM-задачи 57
2.4. Минимизация средних потерь 63
2.4.1. Функционал качества 63
2.4.2. Уравнение оптимальности 64
2.4.3. Свойство монотонности оптимальной политики. Два тина структуры оптимального управления 65
2.4.4. Оптимальность использования прибора с наименьшей средней стоимостью обслуживания G7
2.4.5. Субмодулярность функции оценок 73
2.4.6. Пороговая структура оптимального управления. Пороговая функция для РСМ-задачи 74
2.4.7. Двухуровневая пороговая функция для РСМ-задачи 78
2.5.' Алгоритм 80
2.6. Выводы 85
Глава 3. Системы со сложным входящим потоком 86
3.1. Описание модели 88
3.2. Управляемые Е/М/К системы 91
3.2.1. Уравнение оптимальности 93
3.2.2. Свойства монотонности. Зависимость от фазы генерации 93
3.3. Управляемые РН/М/К системы 98
3.3.1. Уравнение оптимальности 100
3.3.2. Свойства монотонности. Зависимость от фазы генерации 101
3.4. Управляемые MAP/И/К системы 104
3.4.1. Уравнение оптимальности 106
3.4.2. Свойства монотонности. Зависимость от фазы генерации 106
3.5. Выводы 109
Глава 4. Системы с фазовым обслуживанием 111
4.1. Описание модели 112
4.2. Управляемые М/Ё/К системы 116
4.2.1. Уравнение оптимальности 118
4.2.2. Свойства монотонности. Зависимость от фазы обслуживания 119
4.3. Управляемые М/РН/К системы 129
4.3.1. Уравнение оптимальности 131
4.3.2. Свойства монотонности. Зависимость от фазы обслуживания 133
4.4. Управляемые МАР/РН/К системы 141
4.4.1. Уравнение оптимальности 142
4.4.2. Свойства монотонности. Зависимость от фазы генерации и обслуживания 143
4.5. Выводы 146
Заключение 147
Литература 149
Приложение 160
- Монотонность оптимальных политик
- Свойство монотонности оптимальной политики
- Свойства монотонности. Зависимость от фазы генерации
- Свойства монотонности. Зависимость от фазы обслуживания
Введение к работе
Объект исследования и актуальность темы. Модели и методы теории массового обслуживания широко применяются в задачах организации производства, при конструировании компьютерных и телекоммуникационных сетей, в военном деле и т.д. Одним из первых, кто исследовал системы массового обслуживания, был выдающийся учёный А.К, Эрланг, занимавшийся в начале ISO 0 годов проблемами проектирования и анализа работы автоматических телефонных станций. В то время основной задачей в области телефоннії была организация такого телефонного сообщения (с точки зрения числа необходимых телефонных линий) для обеспечения более менее гарантированного обслуживания. Аналогичная проблема возникает, например, в современных компьютерных сетях, когда необходимо опреде-. лить минимальное число серверных станций, которое гарантировало бы испревышение заданной вероятности потери сообщения. Для удовлетворения потребностей пользователей коммуникационных сетей в получении определённого качества обслуживания (QoS)1 невозможно по экономическим причинам беспредельно увеличивать ресурсы, например, число обслуживающих серверов, пропускную мощность канала и т.д. Таким образом, одним из основных вопросов, с которым сталкивается теория массового обслуживания при решении прикладных задач, является нахождение некоторого баланса между улучшением качества обслуживания (QoS) и допустимыми затратами на это улучшение.
Для многих математических моделей, описывающих вероятностную
1 Quality of Service (QoS) - качество обслуживания, термин, использующийся в теории телекоммуникационных систем.
природу реальных систем, с помощью теории массового обслуживания (см. [1, 5, 8]) было получено большое число аналитических и численных результатов характеризующих эксплуатационные качества этих систем. К этим результатам можно отнести формулы для выражений распределения длины очереди и времени ожидания, вероятность потерь, среднее время пребывания в системе, производительность и т.д. (см., например, [1, 2, 3, 21, 22, 24, 26]}. В классической теории массового обслуживания соответствующие модели не предполагают какого-либо вмешательства извне на процесс работы, то есть невозможно совершать управляющие воздействия на систему. Но в реальной жизни существует множество систем, основным качеством которых является именно возможность динамического управления ими в процессе работы, так как при этом можно достичь значительного улучшения качественных свойств, например уменьшения длин очередей, увеличения пропускной способности или уменьшения эксплуатационных затрат. Такие системы, в которых какие-либо из параметров, определяющих тот или иной из её элементов, допускают применение управляющих воздействий мы будем называть управляемъши системами массового обслуживания (УСМО) или управляемыми очередями [10, 52, 66]. Методы теории УСМО применяются для решения задач оптимального управления доступом, обслуживанием, маршрутизацией, распределением заявок по очередям и в сетях массового обслуживания [6, 10, 46, 85, 86, 88]. Управляемые очереди также могут быть с управляемым входящим потоком, с управляемым механизмом обслуживания, с управляемой дисциплиной и т.д. В системах с одним прибором управление может состоять в изменении скорости обслуживания на приборе (см., например, [31, 67]); примеры очередей с управляемым доступом исследуются в [16, 32]. Управляемым очередям е однородными приборами посвящены работы [27, 80].
В качестве теоретического аппарата для исследования многих типов управляемых очередей применяется теория марковских и полумарковских случайных процессов принятия решений [9, 42, 50, 60, 68, 69, 72, 75, 82], так как поведение УСМО описывается обычно некоторым случайным процессом, а наличие управляемых воздействий приводит к изменению его траекторий.
Нахождение оптимального управления даже для простейших марковских систем требует довольно объемной вычислительной работы. Поэтому имеет смысл постараться уменьшить вычислительную составляющую исследований путём качественного анализа свойств оптимальных политик, например изучение их монотонных свойств.
Несмотря на то, что существует большое число научных трудов, посвященных управляемым очередям, многие темы этого направления не достаточно представлены в мировой научной литературе, что является стимулом для дальнейшего исследования и развития этой области прикладной математики. В данной работе исследуются системы массового обслуживания с неоднородными приборами относительно различных оптимизационных критериев. Длительности между поступлениями заявок и длительности обслуживания могут иметь как простейшие пуассоновское и экспоненциальное распределения, так и более общие распределения фазового типа.
Подобные УСМО ранее не исследовались в данном объёме, поэтому тема диссертации является актуальной.
В связи с вышеизложенным, целью диссертационной работы является исследование управляемых систем массового обслуживания с несколькими неоднородными приборами, поведение которых может быть описано марковским процессом принятия решений (или управляемьил марковским процессом).
Исследуемые системы состоят из нескольких неоднородных (в смысле скорости обслуживания) приборов, одной общей очереди и управляющего устройства, занимающегося распределением заявок по приборам. Таким образом, в каждый момент принятия решения, управляющее устройство согласно заданному оптимизационному критерию размещает заявки по приборам, имеющим различную скорость обслуживания и ценовые характеристики. Задача состоит в поиске оптимальной дисциплины обслуживания на приборах и исследовании её качественных и количественных свойств.
В соответствии с целью исследования были рассыотренны системы принадлежащие классу У СМ О типа МАР/Р~Н/К, для обозначения которых используется известная классификация Ксндалла:
М/М/К: входящий поток пуассоновский, время обслуживания на каждом приборе распределено по экспоненциальному закону с неравг ными для разных приборов параметрами;
М/РН/К: входящий поток пуассоновский, время обслуживания имеет распределение фазового типа, представляющего собой конечную сумму или смесь экспоненциально распределённых компонентов. Среднее время обслуживания заявки на разных приборах различно;
МАР/М/К: марковский поток заявок, время обслуживания распределено по экспоненциальному закону;
МАР/РН/К: объединение предыдущих двух моделей.
Методы исследования. В качестве теоретического аппарата для ис-' следования рассматриваемых систем применяется методы теории вероятностей, теории массового обслуживания и управляемых марковских случайных процессов.
Научная новизна и результаты, выносимые на защиту:
Для различных оптимизационных критериев (модель без штрафов и со штрафами) определен класс УСМО. Общий случай такой системы характеризуется марковским входящим потоком (Markov Additive Arrival Process, MAP) и временем обслуживания, имеющим фазовый закон распределения (РН). В работе показано, что для таких систем, которые являются обобщением управляемой MfMjK системы, также сохраняются качественные свойства оптимальных политик управления, например, свойства монотонности оптимального решения и пороговая структура. Показано также, что системы с поступлением и обслуживанием фазового типа (MAP и РН-распределение) обладают также другими качественными свойствами, например, зависимостью оптимального управления от состояний (фаз) процесса поступления и обслуживания.
Задачу поиска оптимального управления с дополнительными штрафами разбита на несколько подзадач в зависимости от упорядочения штрафов за использование приборов и среднего времени обслуживания. В данной работе доказано, что в некоторых случаях оптимальное управление обладает теми же качественными свойствами, что и в задаче без штрафов, в то время как в некоторых случаях существует другой тип оптимальной пороговой политики.
Получены явные формулы для оптимальных порогов в случае разреженного входящего потока, т.е. когда время между соседними поступлениями велико по сравнению со временем обслуживания. Для общего типа систем с распределениями фазового типа для времён между соседними поступлениями и обслуживанием найденные по этим формулам пороги могут рассматриваться как условно оптимальные.
Представлен итерационный алгоритм (основанный на алгоритме Хо-
варда [13]), который можно использовать для получения значений оптимальных политик для управления системами массового обслуживания с большим числом состояний.
5. В работе проведён численный анализ различных типов управляемых очередей, а также сравнительный анализ результатов вычислений. Для этого используются специально разработанные таблицы и диаграммы управлений.
Научная и практическая ценность. Полученные в диссертации результаты позволяют расширить класс реальных моделей, которые могут быть описаны управляемыми системами массового обслуживания. Качественные свойства оптимального управления, в том числе и пороговое свойство, позволяют значительно упростить применение оптимальных политик на практике, так как для этого достаточно задать пороговый уровень каждого прибора (критический уровень длины очереди), который будет давать серверу информацию о необходимости его включения.
Апробация работы. Результаты работы докладывались и обсуждались на следующих конференциях: XXXV-XXXVIV Всероссийские научные конференциии по проблемам математики, информатики, физики, химии и методики преподавания естественнонаучных дисциплин (Москва, Россия, 1999-2003 гг.); First Madrid conference on queueing theory (Мадрид, Испания, 2002 г.); Applied stochastic models and information processes (Петрозаводск, Россия, 2002 г.); Distribution computer communication networks (Москва, Россия, 2003 г.).
Работа выполнена в рамках проекта РФФИ № 01-07-90259.
Публикации работ. По теме диссертации опубликовано 6 работ [7, 12, 33,34,78,79].
Структура и объём работы. Диссертация содержит 148 страниц тек-
ста и состоит из введения, 4 глав и 3 приложений, в которых приводятся результаты численного анализа УСМО, исследуемых в главах 2-4. Каждая глава состоит из параграфов и имеет отдельную нумерацию для формул, теоремм, лемм, следствий и т.д. (первая цифра указывает номер соответствующей главы). Содержание состоит в следующем.
Во введении обосновывается актуальность темы диссертации, приводится обзор опубликованных по данной теме работ, кратко излагаются основные результаты диссертации и содержание по главам.
Первая глава носит вспомогательный характер, в ней даны основные понятия и определения теории управляемых марковских процессов, приводен обзор численных методов нахождения оптимального управления, а также теоретические аспекты задачи оптимизации для управляемых систем массового обслуживания.
Во второй главе рассматривается система М/М/К.с управляемым размещением заявок по К неоднородным приборам. В каждый момент принятия решения, то есть в момент поступления новой заявки или окон-, чания обслуживания на каком-то из приборов, управляющее устройство может принимать решение о необходимости включения свободного прибора или о направлении заявки в буфер. Данная система исследуется как без дополнительных штрафов за использование приборов и ожидание в очереди, так и со штрафами. Для модели без штрафов задача состоит в поиске такой оптимальной стратегии размещения заявок, которая минимизировала бы среднее число заявок в системе в единицу времени [number of jobs minimization "problem, или сокращённо будем называть NJM-задача) и такой стратегии для модели со штрафами, которая бы минимизировала средние потери в единицу времени [processing cost minimization problem, или РСМ-задача). Для этих двух оптимизационных задач формулируется
марковская модель принятия решений и применяется итерационный алгоритм Ховарда для численного вычисления оптимальных политик управления в каждом состоянии системы. Результаты численного анализа систем М/М/К приводятся в приложении 1.
Для NJM-задачи с упорядочением приборов в порядке убывания их интенсивности обслуживания приводятся полученные ранее результаты. То есть оптимальное управление состоит в использовании самого быстрого свободного в данном состоянии прибора, если управляющее устройство принимает решение на обслуживание заявки. Необходимость размещение заявок на приборе или в очереди определяется согласно пороговой политике управления, которая состоит из заранее установленных для каждого прибора j Є 1, А" пороговых уровней или порогов #j. То есть, если число ожидающих в очереди заявок достигает уровня gj, при поступлении заявки происходит включение прибора j и управляющее устройство продолжает использование прибора j пока число заявок в очереди больше q*-. В противном случае заявки вновь направляются для ожидания в буфер. Пороговые уровни упорядочены в соответствии со скоростями обслуживания, т.е., принимая во внимание упорядочение приборов, имеем q\ < q\ < < q*K, Численные исследования показывают, что эти пороги имеют слабую зависимость от состояний2 более медленных приборов. Таким образом, задача нахождения и анализа оптимального управления в данном случае сводится к задаче вычисления пороговых уровней qj для каждого сервера j Є 1, К и исследованию их качественных свойств.
РСМ-модель характеризуется заданием структуры штрафов за использование приборов [стоимость эксплуатации Си) и за размещение заявки в буфере (стоимость ожидания CQ), Средняя эксплуатацион-
2Прибор пожег находиться как в состоянии "включён", так и в состоянии "выключен", что определяет возможность использования прибора для обслуживания заявки.
пая стоимость у^ прибора к задаётся отношением - ^ =: ^ задан-ной стоимости эксплуатации Си(цк) = с* к интенсивности обслуживания прибора дь и приборы в данной задаче упорядочены в порядке возрастания их средних эксплуатационных стоимостей: ^ < -^ < ... < -. Относительно этого порядка существует два типа оптимального управления. В случае, если среднее время обслуживания возрастает медленнее, чем убывает стоимость эксплуатации, то оптимальное управление имеет такую же структуру, как и в NJM-задаче, т.е. задаётся последовательностью пороговых уровней q{ < q\ < < q*K. В данном случае оптимальное управление также является "порогового типа"с пороговыми уровнями д!-, и управляющее устройство всегда выбирает прибор с наименьшей средней стоимостью эксплуатации, что относительно введённого порядка для параметров системы эквивалентно правилу включения самого быстрого прибора. В случае, когда среднее время обслуживания убывает быстрее, чем возрастает стоимость эксплуатации, т.е. если pti < / < - < №к и Си(ці) < Си(}і2) < ... < Си([ік), но их значения удовлетворяют приведённому выше неравенству для средних эксплуатационных стоимостей, тогда оптимальное управление имеет более сложную структуру, чем в приведённых выше случаях, т.е. характеризуются пороговыми уровнями qt(x) < q^ix) — '" — Qk(x)> зависящими от состояний системы х Е. В соответствии с этим правилом управления, свободный в некотором состоянии х Є Е прибор j должен быть включён только тогда, когда длина очереди q(x) в этом состоянии ограничена снизу и сверху соответствующими порогами q*{x) и д]+1(х): q)(x) < q(x) < q]+1{x). Если q]{x) = д]+1(х), тогда предпочтение отдается более быстрому прибору j + 1, и, если прибор j является последним свободным прибором3 в данном состоянии, тогда
3Имеется в виду свободный прибор с наибольшим индексом относительно выбранного упорядочения.
его использование является оптимальным всякий раз, когда д(х) > gUx)
0 = 1,...,70-
В третьей главе рассматриваются УСМО с более общими типами распределений времён между поступлениями заявок, например, с распределением Эрланга (Е) и РН-распределением, а также более общим случаем -марковским потоком заявок (MAP). Так же как и в предыдущей главе, для данных управляемых очередей исследуются качественные и количественные свойства оптимального управления относительно введённых оптимизационных критериев, NJM и РСМ. В частности установлено, что для этих систем выполняются те же качественные свойства оптимальных политик, что и представленные в предыдущей главе, т.е. оптимальное управление имеет пороговую структуру как и в случае пуассоновского входящего потока. Единственное отличие состоит в том, что теперь оптимальные пороговые уровни зависят от состояний процесса поступления (фазы генерации новой заявки). Изучение такой зависимости является важным пунктом данной главы. Результаты численного анализа систем МЛР/М/К приводятся в приложении 2.
В четвёртой главе исследуются УСМО с распределениями времён обслуживания фазового типа, к которым относятся эрланговское и РН-распредсленис. Получение полных аналитических результатов для данных систем довольно сложная задача, поэтому наряду с изучением качественных свойств оптимального управления проведено подробное численное исследование дающее исчерпывающий ответ об этих свойствах. Результаты представлены в виде предложений, базирующихся на численных примерах и аналогии поведения данных систем с теми УСМО, для которых получены теоретические доказательства. Оптимальное управление для изучаемых в данной главе систем снова имеет пороговую структуру, но теперь поро-
ги зависят от состояний процесса обслуживания (фазы обслуживания) на приборах. В случае наличия более сложного входящего потока заявок оптимальные пороги зависят и от фаз генерации, и от фаз процесса обслуживания. Результаты численного анализа систем М/РН/К/ и МАР/М/К приводятся в приложении 3.
Монотонность оптимальных политик
Исследования свойств монотонности оптимальных политик в задачах дискретной оптимизации (задачах с детерминированными управлениями) обычно связано с решением задач оптимизации субмодулярных {супермоду-лярпых) функций на решётках (см. [15, 35, 89]). Эта тема (в том числе для более общих задач) также рассматривалась в работе [36], и для очередей - в работах [76, 85, 86]. Специальный случай гистерезисных оптимальных политик исследовался в [55] и в [38].
Рассмотрим управляемую систему массового обслуживания. Поиск оптимальных политик управления такими системами приводит к необходимости решать многомерную задачу оптимизации действительной функции Ь{х\ а), заданной на некотором подмножестве G Z Е х А прямого произведения дискретных переменных-х Є Е и а А. Как было сказано выше мы ограничимся исследованием задачи минимизации
Е представляет собой пространство состояний и А пространство допустимых управлений. Множества А{х) возможных локальных управлений могут быть различными для разных состояний системы х є Е. Минимизируемая функция Ь(х;а), которую будем называть функцией Беллмана, определяется постановкой конкретной задачи.
В силу неединственности возможных решений задача дискретной минимизации состоит в том, чтобы для всех х Е найти множество А (х) всех оптимальных решений и любую из управляющих функций (политик управления) f(x) Є А (х)
Функцию v{x) будем называть оценкой решения. Для формулировки условия монотонности решения f(x) необходимо, чтобы пространство состояний Е и решений А были наделены структурой, по крайней мере, частичного порядка. Следующее определение хорошо известно
Определение 1.6 Множество Е называется частично упорядоченным, если на нем задано бинарное отношение " "(or " ") обладающее свойствами
Строгое неравенство х у записывается, если х у А х ф у. Элементы х} у Є Е называются несравнимыми, если ни х у, ни у х. Частично упорядоченное множество называется линейно упорядоченным, если оно не имеет несравнимых элементов.
Рассматриваемые системы массового обслуживания характеризуются тем, что пространство состояний Е многомерно и на нем задан частичный порядок, в то время как конечное множество управлений А является изоморфным некоторому подмножеству NA множества No неотрицательных целых чисел, и, соответственно, является линейно упорядоченным. То есть мы введем линейное биективное отображение і : A -+ NA = {1,2,..., \А\} и определим порядок на множестве А как и на множестве NA- Состояние системы может быть описано в виде х = (q, dj,..., d#), где q это целое число, описывающее количество заявок в очереди, и d {0,1} показывает, свободен ли прибор к (к = 1,..., К) или занят. На множестве Е частичный порядок вводится в отношении достижимости состояния при выборе управляющего воздействия.
Заметим, что в большинстве прикладных задач, в том числе в теории массового обслуживания, динамику системы и изменение управлений удобно задавать с помощью операторов сдвигов, которые будем обозначать через {S Jj/gNo и 0. В некоторый момент управления оператор Sv перемещает состояние х є Е в другое состояние Svx Є Е согласно принятому решению а(х) А(х), где v обозначает номер г(а(х)) управления а(х). G вводится на множестве А и обозначает изменение управляющих воздействий при изменении управляющей политики.
Операторы сдвига определяют индивидуальные направления на множестве возможных траекторий в виде структурных деревьев, определённых порядком, как показано на рисунке 1.7. Совокупность направлений определяет так называемый "конус порядка"в G.
В этих педположениях задача состоит в исследовании условий, накладываемых на функцию Ь(х; а) и область G, обеспечивающих допустимость выбора монотонного решения / : Е — А (со значением А (х) в состоянии х Є Е) задачи дискретной минимизации по одному, нескольким или всем направлениям.
В большинстве прикладных задач порядок на множестве состояний системы также, вообще говоря, допускает вариацию. Поэтому более широкая постановка задачи состоит в поиске таких отношений порядка на пространствах состояний и управлений, относительно которых оптимальное решение допускает монотонный выбор.
Чтобы сформулировать эти условия, естественно потребовать согласованности порядков в подмножествах А(х). В рассматриваемом здесь случае одномерного пространства управлений, допускающего полное их упорядочение, будем предполагать, что А = иА(х), так что А(х) С А при этом полная упорядоченность множества А индуцирует полный порядок в множествах А(х). Кроме того, чтобы обеспечить "cBfl3HOCTb"HcxoflHoro множества О и монотонность решений на его "границе", воспользуемся по нятисм монотонного (по фиксированному направлению S) семейства множеств
Определение 1.8 Семейство А множеств А(х), х Є Е, называется монотонно возрастающим (убывающим) в направлении S (S-монотонпым), если для любых а Є А{х)} а" Є A(Sx) минимальный из них а Л а" принадлежит множеству А(х) (A(Sx))} а максимальный из них а V а" принадлежит множеству A(Sx) (А{х)).
Функция f(x) называется S-монотонно возрастающей (убывающей) 7, если f(Sx) ( )f(x) для всехх є Е.
Определение 1.9 Прямоугольником в направлении S (S-прямо-угольник) позиваєшся семейство А$ С Л, которое не изменяется в направлении S} т.е. As = {A(Snx) : A(Snx) = A(x)7 n No, x Є E}.
Свойство монотонности оптимальной политики
В данном разделе мы применим полученные в разделе 1.3 условия монотонности к системе М/М/К, опираясь на результаты В.В. Рыкова, полученные в работе [77]. Для исследования свойств монотонности оптимальных политик введем отношение частичного порядка в пространстве состояний Е2 и полного порядка на множестве управлений Л рассматриваемой системы. С этой целью перенумеруем приборы в порядке убывания их интенсивы остей (возрастания средних длительностей обслуживания) и в том же самом порядке расположим компоненты вектора d = (di,.,., djc).
Определим теперь с помощью операторов сдвигов So и Si частичный порядок в Е, полагая, что эти операторы сдвигают точки пространства в положительном направлении, т.е. Введённые операторы определяют частичный порядок ""в пространстве состояний Е, т.е. х — у если у = Svx. Сдвиги Sv упорядочим между собой в порядке возрастания средних длительностей обслуживания Нетрудно проверить, что введённые соотношения действительно определяют частичный порядок в пространстве состояний Е, причём точки SQX И SJX, (j ф 0) не сравнимы в этом порядке. В пространстве управлений введём полный порядок, при котором 0 1 К, а на множествах Л(х) определим индуцированный им порядок. В работе [77] было доказано следующее утверждение Лемма 2.5 Операторы То и Tj сохраняют свойство неубывания функций v(x) относительно введённого в Е порядка, Доказательство: Для доказательства см. соответствующую лемму 2.17 для РСМ-задачи, где все стоимости необходимо положить равными 1, т.е. СІ = 1, і = OJC. П Следствие 2.7 Функция оценок модели v = {v(x) : х Е} удовлетворяет условию где у является последним устойчивым состоянием. Доказательство: Доказательство следует непосредственно из леммы 2.6. Действительно, для некоторого устойчивого состояния х Є Е, в котором прибор с индексом і занят, справедливо v(x) — + v(Sf1x).
Применяя теперь лемму 2.6 к функции v{S xx) (состояние S x должно быть также устойчивым) и далее для всех занятых в состоянии х приборов к, таких что к Є J\(x)\Ji(y), получим исходное неравенство. Состояние у является последним устойчивым состоянием, т.е. при освобождение с любого занятого в у прибора на него немедленно направляется заявка. Следующим результатом, приведённым в работе [77], было доказательство свойства неубывания функции оценок модели v = { ( ) Є Е} при переходе от точки Siх к точке SjXt i,j Є JQ(X), (І j). Лемма 2.8 Функция оценок модели v = {v(x) : х Є Е} монототш не убывает при переходе от точки SjX к точке Six, т.е. выполняется неравенство Из леммы 2.8 следует, что Теорема 2.9 Оптимальное управление состоит в активизации самого быстрого из доступных приборов, если включение прибора необходимо. Следующее утверждение является в принципе очевидным, но мы приведём доказательство. Лемма 2.10 Оптимальное управление предписывает всегда использовать прибор 1, если он свободен. Доказательство: Пусть Х(0) = х начальное состояние, такое что L(0) О и D\ (0) = 0 и пусть 5 стратегия управления, согласно которой прибор 1 не включается в этом состоянии.
Покажем, что 5 может быть улучшена. Из теоремы 2.9 мы можем предполагать, что 6 не включает ни один из приборов в момент времени і = 0 (в противном случае 6 не является оптимальной стратегией). Введём стратегию 5 и соответствующий наблюдаемый процесс {X(i)}t o, для которого Х(0) = Х(0) = х и все моменты поступления и окончания обслуживании совпадают с оригинальной системой. В момент времени t = 0 стратегия 5 активизирует прибор 1. Пусть Hi время обслуживания заявки на первом приборе при использовании 5 и пусть обозначает момент времени, когда 5 использует прибор в первый раз (непременно прибор 1 по теореме 2.9). Для любой реализации, где {Hi }, мы определим стратегию 5 аналогичную всем действиям стратегии 5 иллюстрируемые процессом {X(t)}t o, за исключением размещения заявки на приборе 1 в момент времени . Для всех реализаций, где {Hi } стратегия 5 копирует все действия стратегии S. Ясно, что такая стратегия управления как 6 существует, и для всех реализаций, L() L(t) для всех t 0, Более того, сопоставляя реализации процессов, получаем, что L(t) = L(t) — 1 в течении периода времени . Таким образом, любая стратегия 5 которая не использует прибор 1 как только он доступен, может быть улучшена другой, которая на нём размещает заявку. D
Свойства монотонности. Зависимость от фазы генерации
В этом разделе рассматриваются УСМО с более общим входящим потоком, подразумевающим наличие модулирующих фаз, т.е. некоторых фиктивных состояний для генерации новой заявки. Будут исследоваться системы с такими входящими потоками как Е-эрланговский (относящийся к рекуррентным потокам 1, у которых времена между поступлениями заявок распределены по закону Эрланга), РН-фазового типа (времена между поступлениями имеют РН-распределение), а также пуассоновский поток, управляемый цепью Маркова (ММРР) и марковский поток заявок (MAP).
В системе с m-фазным эрланговским входящим потоком генерация заявки предполагается завершённой (таким образом, заявка может быть направлена в систему), если все т фаз процесса поступления последовательно были пройдены. Время прохождения каждой фазы генерации распределено по экспоненциальному закону с одинаковым для всех фаз параметром. Таким образом, общее время между соседними поступлениями представляет собой сумму т независимых одинаково распределённых случайных величин, а распределение этого времени выражается через свёртку (композицию) распределений слагаемых, т.е. имеет эрланговское распределение.
Входящий поток РН-фазового типа является более сложным типом потока, так как времена между поступлениями выражаются как распределение первого выхода из множества состояний марковской цепи с непрерывным временем, как описано Ньютсом в работе [63].
Марковский поток заявок (MAP - Markov arrival process), введенный Ньютсом в [64], является обобщением РН-распределсния. MAP поток описывается двумерной марковской цепью, одна компонента которой формирует интервал между поступлениями заявок, а вторая указывает на число заявок, поступивших к данному моменту времени. Поэтому MAP формально задаётся двумя матрицами (A, N), а не матрицей и вектором, как РН-распределение. Заметим, что A+N является инфинитезимальной матрицей описывающей переходы состояний марковской цепи. В общем виде MAP не является процессом восстановления, и времена между поступлениями заявок не являются независимыми, что зачастую встречается на практике.
Одним из частных случаев MAP является пуассоновский поток, управляемый цепью Маркова (ММРР - Markov modulated Poisson process) с диагональной матрицей N. Также простейший пуассоновский поток является частным случаем MAP при наличие только одного переходного состояния лежащей в основе марковской цепи.
Важность исследования систем с фазовой генерацией заявок состоит в их способности более адекватно и эффективно описывать поведение реальных моделей потоков в отличие от простейшего пуассоновского потока. Например, системы с эрланговским поступлением могут применяться в коммуникационных сетях, когда заявка (электронное письмо, пакет данных и т.д.) поступает в систему по частям, но должна быть обслужена сразу же после поступления всех частей. Подобные системы с двумя экспоненциальными приборами изучались Виниотисом и Эфремидисом в работе [93], где было дано определение пороговой структуры оптимального управления этой моделью. Системы с MAP являются полезным обобщением для различных приложений, например для В — ISDN сетей, где поступление на узел сети является выходом другого узла, что приводит к значитель ной корреляции последовательных длительностей между поступлениями, что в свою очередь, оказывает существенное влияние на поведение системы (см., например [28]). Метод получения распределения времени ожидания в однолинейной системе с MMPPJдемонстрировался в [59] и для случая нескольких приборов в [23].
Ниже приводится структура главы. В следующем разделе 3.2 даётся описание СМО с эрланговским входящим потоком заявок. Случаи потоков РН-фазового типа и MAP рассматриваются, соответственно, в разделах 3.3 и 3.4. Для каждого типа УСМО мы получим уравнение оптимальности и исследуем качественные и количественные свойства оптимального управления данными системами. Ввиду более сложной схемы поступления заявок, важную роль в предстоящем исследовании играет численный анализ (см. Приложение 2) и сравнение полученных результатов для различных типов распределений времени между поступлениями.
Рассмотрим систему массового обслуживания, состоящую из К экспоненциальных неоднородных приборов с интенсивностями обслуживания рк (& = 17 К) и буфера ёмкостью В — К (К В оо)( представленную на рисунке 3.1. На этом рисунке D +i(t) обозначает случайный модулирующий процесс, обозначающий фазу генерации новой заявки в момент времени і. Этот процесс будет описан ниже и определён для каждого типа входящего потока.
Формулировка и обозначения для оптимизационной задачи в этом случае аналогичны предыдущему случаю с пуассоновским поступлением, см. главу 2. Отличие состоит лишь в том, что теперь фаза генерации заявки является элементом состояния системы. Таким образом, рассматриваемые в данной главе УСМО моделируются с помощью марковского процесса принятия решений {Z{t)} = {X(i)jC/(f)}, и наблюдаемый процесс {X(t)}t a с пространством состояний = Nx {0,1} х {1,.„,т} включает в этом случае дополнительную компоненту DK+i{t)t обозначающую неприводимый генерирующий процесс с множеством состояний {1,... ,т}. Поэтому для каждого состояния х = (do,di,... ,dic,dic+i),dK4-iO 0 обозначает состояние процесса поступления заявки в состоянии х (например в случае эрланговского входящего потока d +\: 1 —+ 2712).
Свойства монотонности. Зависимость от фазы обслуживания
Системы, в которых процесс обслуживания включает наличие фаз, довольно сложно анализировать теоретически, но вполне реально это сделать с помощью проведения большого числа численных экспериментов. Основываясь на этих результатах, а также на некотором сходстве поведения таких систем с исследованными выше, свойства монотонности оптимальных управлений могут быть формализованы в виде следующих правдоподобных предположений. Предположение 4.4 Оптимальное управление в NJM- и РСМ- задаче при выполнении условий (4.11)-(4-13) обладает таким свойством, что если управляющее устройство направляет заявку на один из приборов, то этот прибор должен быть самым быстрым из доступных (4-Ю) и (4-11)- В РСМ-задаче при выполнении условий (4-11) и (4-Ц) управляющее устройство может использовать любой из доступных приборов и переключать их по мере изменения длины очереди. Предположение 4.5 Оптимальное управление обладает пороговым свойством с одним конечным пороговым уровнем для каждой фазы обслуживания. Для NJM- и РСМ-задачи при выполнении условий (4-11)-(4-13) для каждого прибора и каждой фазы генерации существует па одному пороговому уровню, в то время как для РСМ-задачи при выполнении условий (4-11) и (4-Ц) ля свободных приборов существует в каждом состоянии двухуровневое пороговое правило использования этих приборов. Заметим, что только некоторые из элементов предположений 4.4 и 4.5 могут быть доказаны. Остальные утверждения довольно сложно доказать теоретически, но они подтверждаются по результатам численного анализа. Введем частичный порядок на пространстве состояний Е с помощью операторов сдвигов S0 и Sf ,
Последнее неравенство устанавливает порядок для различных приборов i, j Є JQ{X), НО при условии равного числа эрланговских фаз, т» = щ = т. Теперь можно сформулировать следующее утверждение относительно свойств функции оценок рассматриваемой модели. Лемма 4.6 Функция оценок v = {v{x) : х Є Е} модели с эрланговским процессом обслуживания заявок обладает следующими свойствами монотонности относительно порядка на Е Доказательство: Покажем сначала, что оператор То сохраняет свойство неубывания функций относительно введённого в Е порядка. Пусть для ограниченной, неубывающей функции v(x) выполняются условия 1, 2 и 3. Тогда справедливы следующие соотношения. что следует в силу сделанных предположений о неубывании функции v(x) и из соотношения A(SQX) = А(х), Аналогично доказывается неравенство
В силу определения формулой (4.7) операторы 7) (I i,j) также сохраняют эти свойства. Покажем далее, что оператор В, введённый соотношением (4.5), сохраняет свойство монотонного неубывания функции. Первое неравенство 1 справедливо в силу линейности оператора В и монотонности функции с{х) относительно сдвигов SQ И Sf . Для доказательства второго неравенства из 1 используется тот же подход, что и в лемме 2.17, т.е. справедливо, например, vffiix)—v(Sfi+lx) , d = 1,тп — 1, откуда следует исходное неравенство. Пусть процесс обслуживания на каком-либо приборе г состоит из двух фаз {а,/3}, причём а /?. Выберем масштаб времени так, чтобы Л + Y rLiP-J = 1- Тогда для неравенства 2 из уравнения оптимальности В правой части этого выражения первые четыре слагаемых не отрицательны в силу постоянства функции с(х) при переходе от точки Sfx к S?x для фаз обслуживания а и /9 и свойств функции г/(дг) и операторов Го и 7). Для последнего слагаемого в силу свойств оператора 7} имеем Рассмотрим теперь неравенство 3. Для его доказательства также необходимо проверить, что оператор В сохраняет это свойство. К сожалению, нам не удалось доказать это неравенство ни для системы типа МJ Ет МJ К с более быстрым эрланговским прибором, ни для более общего случая М/Етр EmJK, ТПІ ф rrij. Доказательство оказалось возможным провести либо для системы М/М, EmjK% где необходимо сравнить два прибора, более быстрый экспоненциальный (интенсивность обслуживания fij) с медленным эрланговским (интенсивность обслуживания на фазе fii), а также для системы М/Ет Е К с равным числом фаз m = rrij = т, причём /Xj fii для N JM-задачи и & для РСМ-задачи. Итак, положим Л + 2Jj=i Щ 1
Для неравенства 3 в случае системы М/ЕщуЕгщ/К с равным числом фаз на всех приборах из уравнения Наконец, справедливость неравенства 3 для функции оценок следует из монотонной сходимости последовательности {Bnvo(x)}n 0 (см. (2.12)) к функции оценок модели v = {v(x) : х Е}, где начальная итерация VQ(X)X Є Е сохраняет указанные свойства. Для системы М/М, EmJK последнее неравенство доказывается аналогично. D Замечание 4.7 Неравенство 2 для случая т 2, к = \,К и неравенство 3 для более общих систем с эрланговским обслуживающим процессом подтверждаются численными результатами. Теорема 4.8 Оптимальное управление СМ О с эрланговским обслуживанием обладает пороговым свойством с конечными порогами qUdi,..., dj-i) для каждого набора фаз занятых приборов d\,..., dj_i, такими, что необходимо включать прибор с наименьшей средней стоимостью обслуоісивания 7у = Ц- (что соответствует также самому быстрому прибору) среди доступных только если q{x) q (rfi,..., dj-i). Доказательство: Проводя аналогичные рассуждения, как в теореме 2.12, для системы Af/Emj7Em./K (m,- = Щ — т) функция оценок модели является [SQ, Sk) субмодулярной, т.е. удовлетворяет условию (2.21) где di = l,mi, А: Є JQ(S1 X), Для более общего типа системы численный анализ подтверждает справедливость этого неравенства. Таким образом, оптимальное управление имеет пороговую структуру и заключается в использовании прибора с минимальным средним временем обслуживания (NJM-задача) или с минимальной средней стоимостью обслуживания {РСМ-задача с условиями (4.11)-(4.13)). Как и раньше, оптимальные пороговые уровни имеют слабую зависимость от состояния медленных приборов, поэтому этой зависимостью будем пренебрегать.
