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

На правах рукописи

Ефросинин Дмитрий Владимирович

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

05.13.17 - теоретические основы информатики

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

Москва - 2005

Работа выполнена в Российском университете дружбы народов.

Научный руководитель: доктор физико-математических наук

профессор В. В. Рыков Официальные оппоненты: доктор технических наук,

А. И. Ляхов

кандидат физико-математических наук, М. Ю. Китаев

Ведущая организация: Институт проблем управления РАН

(мфл1$

2005 г. в_

_мин. на заседа-

Защита состоится "_ нии Диссертационного совета Д 002.077.01 при Институте проблем передачи

информации РАН по адресу: 127994, г. Москва, ГСП-4, Б. Каретный пер., 19.

С диссертацией можно ознакомиться в библиотеке Института проблем передачи информации РАН.

Автореферат разослан "_"_2005 г.

Учёный секретарь Диссертационного совета Д 002.077.01 доктор физико-математических наук /{/^

И. И. Цитович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Модели и методы теории массового обслуживания широко применяются при конструировании компьютерных и телекоммуникационных сетей. Одним из первых, кто исследовал системы массового обслуживания, был выдающийся учёный А.К. Эрланг, занимавшийся в начале 1900 годов проблемами проектирования и анализа работы автоматических телефонных станций. Для удовлетворения потребностей пользователей коммуникационных сетей в получении определённого качества обслуживания невозможно по экономическим причинам беспредельно увеличивать ресурсы, например, число обслуживающих серверов, пропускную мощность канала и т.д. Таким образом, очень важной прикладной задачей является нахождение некоторого баланса между улучшением качества обслуживания и допустимыми затратами на это улучшение.

Для многих математических моделей, описывающих вероятностную природу реальных систем, с помощью теории массового обслуживания было получено большое число аналитических и численных результатов, характеризующих эксплуатационные качества этих систем. Но классические системы массового обслуживания не предполагают какого-либо вмешательства извне в процесс работы, то есть невозможно осуществлять управляющие воздействия на систему. Однако в реальной жизни существует множество систем основным свойством которых является именно возможность динамического управления ими в процессе работы, так как при этом можно достичь значительного улучшения характеристик, например, уменьшения длин очередей, увеличения пропускной способности или уменьшения эксплуатационных затрат. Основоположником исследований в области управляемых процессов по праву можно считать Ричарда Беллмана, который ещё в начале 1950-х годов занимался созданием вычислительных методов для процессов принятия последовательных решений на конечном интервале времени. Его идеи были обобщены Рональдом Ховардом (1960). В своих исследованиях Ховард использовал теорию марковских цепей и динамическое программирование для создания итерационного метода для отыскания оптимального решения в процессах большой длительности.

Таким образом, для фактического построения оптимальных политик

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

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

Подобные системы ранее не исследовались в данном объёме, поэтому тема диссертационной работы является актуальной.

Целью диссертационной работы является вычисление оптимальных политик управления для класса управляемых систем массового обслуживания МАР/РН/К относительно двух оптимизационных критериев: минимизации среднего числа заявок (NJM - Mean number of jobs и минимизации средних потерь

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

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

Теоретическая и практическая ценность работы. Полученные в диссертации результаты позволяют расширить класс реальных моделей, которые могут быть описаны управляемыми системами массового обслуживания. Качественные свойства оптимального управления, в том числе и пороговое свойство, позволяют значительно упростить применение оптимальных политик на практике, так как для этого достаточно задать пороговый уровень каждого прибора (критический уровень длины очереди), который будет давать серверу информацию о необходимости его включе-

ния.

Апробация работы. Основные результаты диссертации были представлены на российских и международных конференциях и семинарах: на XXXV-XXXVTV Всероссийских научных конференциях по проблемам математики, информатики, физики, химии и методики преподавания естественнонаучных дисциплин (Москва, РУДН, 1999-2003 гг.); First Madrid conference on queueing theory (Испания, Мадрид, 2002 г.); Applied stochastic models and information processes (Петрозаводск, 2002 г.); Distribution

(Москва, 2003 г.)

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

Научная новизна работы. Настоящая диссертация содержит следующие новые идеи и результаты:

Впервые рассматривается класс управляемых систем типа МАР/РН/К с несколькими неоднородными приборами. Для различных систем принадлежащих рассматриваемому классу получены уравнения оптимальности, и для различных значений входных параметров вычислены оптимальные политики управления.

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

Задача оптимизации рассматривается относительно двух критериев: минимизации среднего числа заявок в системе и минимизации средних потерь (в случае дополнительной структуры штрафов). Исследованы качественные свойства оптимального управления в зависимости от критерия оптимизации и различных распределений времён между поступлениями и обслуживания на приборах.

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

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

Реализация результатов работы. Работа выполнена в рамках проекта РФФИ № 01-07-90259.

Структура диссертации. Диссертация содержит 148 страниц текста и состоит из введения, 4 глав и 3 приложений, в которых приводятся результаты численного анализа управляемых систем массового обслуживания (УСМО), исследуемых в главах 2-4. Каждая глава состоит из параграфов и имеет отдельную нумерацию для формул, теоремм, лемм, следствий и т.д. (первая цифра указывает номер соответствующей главы). Содержание состоит в следующем.

СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава носит вспомогательный характер. В ней даны основные понятия и определения теории управляемых марковских процессов, в том числе управляемой системы массового обслуживания (УСМО), приведён обзор численных методов нахождения оптимального управления, а также теоретические аспекты задачи оптимизации для УСМО.

Относительно работы исследуемых систем делаются следующие предположения.

1.1. Наблюдения над системой и управления производятся на бесконечном интервале времени.

П 1.2. Моментами принятия решения являются моменты поступления заявок и окончания обслуживания на приборах. В момент поступления новой заявки управляющее устройство может направить её в буфер (если он не полный) или на один из свободных приборов. Если буфер не пустой в момент окончания обслуживания, управляющее устройство размещает одну заявку из буфера на свободном приборе или оставляет её для дальнейшего ожидания; в противном случае управление отсутствует.

П 1.3. Заявка теряется только в том случае, если при поступлении в буфере нет свободных мест и все приборы заняты.

П 1.4. Предполагается невозможность передачи обслуживаемой заявки с одного прибора на другой.

п 1.5. Наблюдателю над системой доступна вся необходимая для

управления информация о её поведении.

П 1.6. Управляющие воздействия принимают численные значения.

Во второй главе рассматривается управляемая система М/М/К/В-К (К < В < оо) состоящая из К неоднородных экспоненциальных приборов с интенсивностями обслуживания Ць (k = 1, -К"), общей очереди с В - К доступными местами, в которую поступает пуассонов-ский поток заявок с параметром Л. Определим величину — C^q как

стоимость за единицу времени пребывания q заявок в очереди, где Со > О стоимость ожидания, и величину стоимость за единицу

времени эксплуатации прибора с индексом и соответствующей интенсивностью file.

Вводятся следующие обозначения:

{Z(t)}t>о = {X(t), i/(t)}t>0 - управляемый процесс, описывающий поведение управляемой системы во времени;

{X(i)}t>o = (Q(£), Di(t),-Dtf(i)} - наблюдаемый процесс, представляющий состояние системы в момент времени длина очереди в момент

{[/(4)}«>0 - управляющий процесс, описывающий управление в ближайший к моменту £ следующий момент принятия решения; А = {0,1,...,К} - множество допустимых управлений;

множество допустимых управлений в состоянии

</о(х) И Л(х) - множества индексов свободных и занятых приборов в состоянии соответственно, т.е.

0, если прибор к свободен в момент времени £

1, в противном случае;

Л(*) =

Jo(i) U {0} для х, если q(x) <В- К, J0(x) для х, если q(x) = В- К,

Мх) = {j : dj(x) = 0}, Ji(x) = {j : d}(x) = 1};

Y(t) = fo(coQ(u) + ]Ol<k<K ck^k(u))du- функционал потерь на интервале [0, ij

Известно, что для управляемых относительно критерия средней цены марковских процессов с аддитивным функционалом потерь существует оптимальная однородная марковская стратегия: S = {f(x),x € .Б}, где функция f : Е А обозначает политику управления в состоянии X, причём f(x) € А(х). Таким образом, если в некоторый момент времени t система находится в состоянии х, X(t) = х, то управляющее устройство выбирает допустимое управление U(t) = f{x) £ А(х) (для его применения в ближайший момент принятия решения), где /(х) = k > 1 обозначает "включение прибора с индексом fc", И f(x) — 0 обозначает "не включение ни одного из приборов".

В рассматриваемых предположениях управляемый процесс {Z(t)} является марковским с конечным пространством состояний и управлений и интенсивностями переходов

I остальных случаях,

где обозначает управление при поступлении заявки в состо-

яние X, а ~ а,3 £ А(х — е3 — ео) обозначает управление после завершения обслуживания на приборе ]. Через е, = (О,^-^, 1|0, 10) обозначен К + 1. К~г

мерный вектор, компонента которого (нумерация начинается с нулевой координаты) равна 1, а все остальные - 0.

Для формулировки задачи оптимизации введём на множестве траекторий процесса распределение вероятностей

= у|Х(0) = х) при условии начального состояния х и выбранной стратегии а также математическое ожидание относительно данного распределения.

Задача минимизации средних потерь в системе с одним эргодическим классом состояний заключается в минимизации функционала

относительно всех допустимых стратегий S и для любого начального состояния х.

Специальным случаем задачи минимизации средних потерь является задача минимизации среднего числа заявок в системе. Для этого полагаем Со = С* = 1, к — 1,2,..., К. Более подробно описание модели и постановка задачи приводятся в

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

Здесь v(x) обозначает функцию оценок модели и вместе с ценой д являются неизвестными величинами, которые вычисляются, используя итерационный алгоритм Ховарда.

Теорема 2.4 Пусть dg и ctj, j € Ji{x) решения уравнения оптимальности (1) в пространстве управлений. Оптимальная политика f = {f{x) : X € Е} в моменты поступления определяется соотношени-

В случае окончания обслуживания на приборе j € Ji{x) в состоянии х при непустой очереди оптимальная политика управления совпадает с политикой управления при поступлении заявки в "смещённое" состояние,

Исходя из определения оптимальной политики (2), для получения ка--чественных свойств оптимального управления исследовались свойства монотонности функции оценок модели

В § 2 3 рассматривается задача минимизации среднего числа заявок в системе, если приборы упорядочены в соответствии с неравенством ^ 1*2 ^ "'' ^ Здесь приводятся результаты, полученные профессором Рыковым В.В. 1 В этих работах доказывается пороговый характер оптимальной политики управления для данного критерия оптимизации.

В § 2.4 исследуются свойства оптимального управления для задачи минимизации средних потерь в системе. Разобьём задачу на две части. Пусть приборы упорядочены в соответствии с неравенствами

Теорема 2.24 Оптимальное управление для РСМ-задачи при условиях (3) обладает пороговым свойством, т е для каждого прибора ] существует некоторый критический уровень длины очереди Ц* (зависящий от набора занятых приборов ^{х)), такой что необходимо включать прибор с наименьшей средней стоимостью обслуживания 1] — ^ (что соответствует также самому быстрому прибору) среди доступных только если д(х) > С^. Если в некотором состоянии х оптимальное управление состоит в размещении заявки в буфере, тогда данное управление также будет оптимальным во всех состояниях при том же наборе занятых приборов

Лемма 2.25 Для системы С А = 0 пороговые уровни могут быть найдены в явном виде

Эти пороги являются верхней границей соответствующих порогов при

А>0

^ Рыков В В Об условиях монотонности оптимальных политик управления системами массового обслуживания // Автоматика и телемеханика 1999 вьш 9 С 92-106

ñykov V. V Monotone Control of Queueing Systems with Heterogeneous Servers // Qaeaemg

Пусть теперь приборы упорядочены в соответствии с неравенствами

Лемма 2.27 Оптимальное управление в РСМ-задаче при выполнении условий (4) не состоит в использовании в любом состоянии системы прибора в зависимости от его характеристик (среднего времени обслуживания, стоимости обслуживания и т.д.), т.е. теорема 2.26 не выполняется для всех состояний.

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

В приводится итерационный алгоритм вычисления оптималь-

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

В третьей главе рассматриваются УСМО с более общими типами распределений времён между поступлениями заявок, например, с распределением Эрланга (Е) § 3.2 и общим РН-распределением § 3.3, а также марковским потоком заявок (MAP) § 3.4. Стохастическое поведение этих систем также описывается управляемым марковским процессом, где наблюдаемый векторный процесс {X(t)} имеет в данном случае дополнительный элемент обозначающий фазу генерации новой заявки в момент времени

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

Теорема (В диссертации эти результаты сформулированы в теоремах 3.6, 3.13, 3.18 для входящих потоков Е, РН и MAP, соответственно.) Оптимальное управление СМО с фазовым входящим потоком обладает пороговым свойством с конечными порогами cfc(dK+i) для каждой фазы генерации(1к+1, такими, что необходимо включать прибор с наименьшей средней стоимостью обслуживания = ^ (что соответствует также самому быстрому прибору) среди доступных только если q(x) > Qjidx+i)-Рассмотрим двухфазный (а, /3) процесс поступления заявок в систему. Пусть фазы упорядочены следующим образом:

для потока Е: а < 0, где а обозначает начальную фазу генерации, а ¡3 фазу поступления заявки в систему;

для потока РН: Ха > А^, а < /?, где Aj, i € {а,/?} обозначаетобщую интенсивность поступления с фазы

для потока где обозначает общую интенсивность

поступления с фазы

Следствие (В диссертации эти результаты сформулированы в следствиях 3.8, 3.14, 3.19 для входящих потоков Е, РН и MAP, соответственно.) В системах с фазовыми распределениями времени генерации заявок пороговые уровни i е {а, ¡3} для некоторого прибора j в случае различных генерирующих фаз удовлетворяют условию > относительно введённого на множестве фаз генерации порядка.

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

^ ^ 10, прибор к свободен в момент времени t и

1 dk = l,m*, прибор к занят на фазе dt,

где число фаз обслуживания на приборе

В этой задаче управления существует зависимость между принятием оптимального решения и состоянием обслуживающего процесса на прибо-

pax. Получение полных аналитических результатов для данных систем довольно сложная задача. Поэтому наряду с изучением качественных свойств оптимального управления, проведено подробное численное исследование, дающее исчерпывающий ответ об этих свойствах. Результаты представлены в виде предположений, базирующихся на численных примерах и аналогии поведения данных систем с теми УСМО, для которых получены теоретические доказательства.

Пусть приборы упорядочены в порядке (3), только вместо экспоненциальных интенсивностей рассматриваются средние интенсивности JL: распределения и для общего

РН-распределения.

Теорема 4.8 Оптимальное управление СМО с эрланговским обслуживанием обладает пороговым свойством с конечными порогами q*(di, dj-i) для каждого набора фаз занятых приборов d\,..., dj^i, такими что необходимо включать прибор с наименьшей средней стоимостью обслуживания 1j = (что соответствует также самому быстрому прибору) среди доступных только если q(x) > (^(¿i, •. •

Рассмотрим двухфазный (а, /3) процесс обслуживания заявок на приборах. Пусть фазы упорядочены следующим образом: обслуживание Е'. а < /3, где а обозначает начальную фазу обслуживания, а Р фазу окончания обслуживания заявки на приборе; обслуживание РН: а< ¡3, где ftp i € {а, /?} обозначает общую

интенсивность обслуживания на фазе прибора

Следствие 4.9 (Для эрланговского распределения длительности обслуживания Е.) Пороговые уровни gl(di,... ,dit..., dk-i), di € {a /3} для некоторого прибора k в случае различных фаз обслуживания на более быстром приборе i удовлетворяют условию

если а < р.

Обозначим через щ = rft, ■ ■ ■, T)™k) распределение начальной фазы обслуживания и в случае эрланговского обслуживания

Теорема 4.14 Пусть aj u a^j 6 Ji(x) решения уравнения оптимальности для систем с фазовым обслуживанием. Оптимальная политика f = {f(x): х G Е} в моменты поступления определяется соотношением

f(x) = «S = argminMx + eg), jj ijftfc + : k € А(д;)\{0». (5)

В случае окончания обслуживания на приборе j € Ji(x) в состоянии х при непустой очереди оптимальная политика управления совпадает с политикой управления при поступлении заявки в "смещённое" состояние,

- djCj - ео + dkek): keA(x- -ео)\{0}}.

Предположение 4.18 Оптимальное управление СМО с общим РН-распределением обладает пороговым свойством с конечными порогами <£(¿1,..., dj-1) для каждого набора фаз занятых приборов d3_i, та-

кими, что необходимо включать прибор с наименьшей средней стоимостью обслуживания уj = (что соответствует также самому быстрому прибору) среди доступных только если

Предположение 4.19 (Для РН - распределения длительности обслуживания.) В системах с фазовым обслуживанием на приборах пороговые уровни для некоторого прибора в случае различных фаз обслуживания на более быстром приборе удовлетворяют условию

если lij <

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

с пуассоновским входящим потоком и экспоненциальными приборами, М/М/К-,

с марковским входящим потоком, МАР/М ¡К;

с распределением времён обслуживания фазового типа, М/РН/К\

с марковским входящим потоком и распределением времён обслуживания фазового типа,

В работе получены следующие результаты:

1. Для всех типов систем определён управляемый марковский процесс и выведены уравнения оптимальности, которые используются для нахождения оптимальных политик управления для каждого состояния рассматриваемых систем.

2. Для всех типов систем рассмотрены две задачи оптимизации: относительно критерия минимизации среднего числа заявок и средних потерь в системе (с учётом дополнительной структуры штрафов).

3. Для систем МАР/М/К доказано, что оптимальная дисциплина обслуживания для критерия минимизации среднего числа заявок является пороговой, при этом следует включать наиболее быстрый го доступных приборов и значение порога имеет слабую зависимость от состояний более медленных приборов.

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

Для систем и, соответственно, приведённые

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

4. Исследована зависимость оптимальных пороговых уровней от состояний процесса поступления и обслуживания в случае распределений фазового типа. Значения пороговых уровней возрастают при увеличении

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

5. Для систем с отсутствием входящего потока заявок (задача расписания) получены явные формулы для вычисления пороговых уровней. Эти значения представляют собой верхнюю границу соответствующих пороговых уровней для аналогичных систем с входящим потоком.

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

Основные результаты диссертации отражены в следующих опубликованных работах:

1. Ефросиний Д. В. Исследование оптимального управления системой неоднородных приборов с наблюдаемой общей очередью // Тезисы докладов XXXVII Всероссийской научной конференции по проблемам математики, информатики, физики, химии и методики преподавания естественнонаучных дисциплин. 2001. 35 С.

2. Rykov V., Efrosinin D. Numerical analysis of optimal control policies for queueing systems with heterogeneous servers // Информационные процес-

3. Efrosinin D., Breuer L. An optimization algorithm for the MAP/PH/K queue with heterogeneous servers// Forschungsbericht, Trier

4. Рыков В. В., Ефросинин Д. В. Численное исследование оптимального управления системой с неоднородными приборами// Автоматика и телемеханика. 2003. Т. 2. С. 127-143.

5. Rykov V., Efrosinin D. Numerical analysis of optimal control policies for queueing systems with heterogeneous servers// Queueing Systems. 2004.

6. Efrosinin D. Threshold phenomenon in controlled retrial queues with heterogeneous servers// Reports of the mathematical institutes, Linz Univer-

Отпечатано в ООО «Компания Спутник+» ПД № 1-00007 от 25.06.2000 г. Подписано в печать 24.02.2005 Тираж 100 экз. Усл. печ. л. 1

Печать авторефератов 730-47-74,778-45-60

95,11 -05.!Ъ

Введение

Глава 1. Очереди и динамическое управление

1.1. Управляемый марковский процесс.

1.2. Численные методы.

1.3. Монотонность оптимальных политик

Глава 2. Управляемые М/М/К системы

2.1. Описание модели.

2.2. Постановка задачи.

2.3. Минимизация среднего числа заявок.

2.3.1. Функционал потерь

2.3.2. Уравнение оптимальности.

2.3.3. Преобразование уравнения оптимальности.

2.3.4. Свойство монотонности оптимальной политики

2.3.5. Оптимальность использования быстрого прибора

2.3.6. Субмодулярность функции оценок.

2.3.7. Пороговая структура оптимального управления. Пороговая функция для NJM-задачи.

2.4. Минимизация средних потерь.

2.4.1. Функционал качества.

2.4.2. Уравнение оптимальности.

2.4.3. Свойство монотонности оптимальной политики. Два типа структуры оптимального управления.

2.4.4. Оптимальность использования прибора с наименьшей средней стоимостью обслуживания.

2.4.5. Субмодулярность функции оценок.

2.4.6. Пороговая структура оптимального управления. Пороговая функция для РСМ-задачи.

2.4.7. Двухуровневая пороговая функция для РСМ-задачи

2.5. Алгоритм.

2.6. Выводы.

Глава 3. Системы со сложным входящим потоком

3.1. Описание модели.

3.2. Управляемые Е/М/К системы.

3.2.1. Уравнение оптимальности.

3.2.2. Свойства монотонности. Зависимость от фазы генерации

3.3. Управляемые РН/М/К системы.

3.3.1. Уравнение оптимальности.

3.3.2. Свойства монотонности. Зависимость от фазы генерации

3.4. Управляемые МАР/М/К системы.

3.4.1. Уравнение оптимальности.

3.4.2. Свойства монотонности. Зависимость от фазы генерации

3.5. Выводы.

Глава 4. Системы с фазовым обслуживанием

4.1. Описание модели.

4.2. Управляемые М/Е/К системы.

4.2.1. Уравнение оптимальности.

4.2.2. Свойства монотонности. Зависимость от фазы обслуживания

4.3. Управляемые М/РН/К системы.

4.3.1. Уравнение оптимальности.

4.3.2. Свойства монотонности. Зависимость от фазы обслуживания

4.4. Управляемые МАР/РН/К системы.

4.4.1. Уравнение оптимальности.

4.4.2. Свойства монотонности. Зависимость от фазы генерации и обслуживания.

4.5. Выводы.

Объект исследования и актуальность темы. Модели и методы теории массового обслуживания широко применяются в задачах организации производства, при конструировании компьютерных и телекоммуникационных сетей, в военном деле и т.д. Одним из первых, кто исследовал системы массового обслуживания, был выдающийся учёный А.К. Эрланг, занимавшийся в начале 1900 годов проблемами проектирования и анализа работы автоматических телефонных станций. В то время основной задачей в области телефонии была организация такого телефонного сообщения (с точки зрения числа необходимых телефонных линий) для обеспечения более менее гарантированного обслуживания. Аналогичная проблема возникает, . например, в современных компьютерных сетях, когда необходимо опреде-. лить минимальное число серверных станций, которое гарантировало бы -. непревышение заданной вероятности потери сообщения. Для удовлетворения потребностей пользователей коммуникационных сетей в получении определённого качества обслуживания (QoS)1 невозможно по экономическим причинам беспредельно увеличивать ресурсы, например, число обслуживающих серверов, пропускную мощность канала и т.д. Таким образом, одним из основных вопросов, с которым сталкивается теория массового обслуживания при решении прикладных задач, является нахождение некоторого баланса между улучшением качества обслуживания (QoS) и допустимыми затратами на это улучшение.

Для многих математических моделей, описывающих вероятностную

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], так как поведение УСМО описывается обычно некоторым случайным процессом, а наличие управляемых воздействий приводит к изменению его траекторий.

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

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

Подобные УСМО ранее не исследовались в данном объёме, поэтому тема диссертации является актуальной.

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

Исследуемыс системы состоят из нескольких неоднородных (в смысле скорости обслуживания) приборов, одной общей очереди и управляющего устройства, занимающегося распределением заявок по приборам. Таким образом, в каждый момент принятия решения, управляющее устройство согласно заданному оптимизационному критерию размещает заявки по приборам, имеющим различную скорость обслуживания и ценовые характеристики. Задача состоит в поиске оптимальной дисциплины обслуживания на приборах и исследовании её качественных и количественных свойств.

В соответствии с целью исследования были рассмотренны системы принадлежащие классу УСМО типа МЛР/РН/К, для обозначения которых используется известная классификация Кендалла:

1. М/М/К: входящий поток пуассоновский, время обслуживания на каждом приборе распределено по экспоненциальному закону с неравг ными для разных приборов параметрами;

2. М/РН/К: входящий поток пуассоновский, время обслуживания имеет распределение фазового типа, представляющего собой конечную сумму или смесь экспоненциально распределённых компонентов. Среднее время обслуживания заявки на разных приборах различно;

3. МАР/М/К: марковский поток заявок, время обслуживания распределено по экспоненциальному закону;

4. МАР/РН/К: объединение предыдущих двух моделей.

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

Научная новизна и результаты, выносимые на защиту:

1. Для различных оптимизационных критериев (модель без штрафов и со штрафами) определён класс УСМО. Общий случай такой системы характеризуется марковским входящим потоком (Markov Additive Arrival Process, MAP) и временем обслуживания, имеющим фазовый закон распределения (РН). В работе показано, что для таких систем, которые являются обобщением управляемой М/М/К системы, также сохраняются качественные свойства оптимальных политик управления, например, свойства монотонности оптимального решения и пороговая структура. Показано также, что системы с поступлением и обслуживанием фазового типа (MAP и РН-распределение) обладают также другими качественными свойствами, например, зависимостью оптимального управления от состояний (фаз) процесса поступления и обслуживания.

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

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

4. Представлен итерационный алгоритм (основанный на алгоритме Ховарда [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. Публикации работ. По теме диссертации опубликовано б работ [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 ,К пороговых уровней или порогов qj. То есть, если число ожидающих в очереди заявок достигает уровня qJ, при поступлении заявки происходит включение прибора j и управляющее устройство продолжает использование прибора j пока число заявок в очереди больше qj. В противном случае заявки вновь направляются для ожидания в буфер. Пороговые уровни упорядочены в соответствии со скоростями обслуживания, т.е., принимая во внимание упорядочение приборов, имеем q\ < < • • • < q*K. Численные исследования показывают, что эти пороги имеют слабую зависимость от состояний2 более медленных приборов. Таким образом, задача нахождения и анализа оптимального управления в данном случае сводится к задаче вычисления пороговых уровней qj для каждого сервера j G 1, К и исследованию их качественных свойств.

РСМ-модель характеризуется заданием структуры штрафов за использование приборов (стоимость эксплуатации Си) и за размещение заявки в буфере {стоимость ожидания С®). Средняя эксплуатацион

2Прибор может находиться как в состоянии "включён", так и в состоянии "выключен", что определяет возможность использования прибора для обслуживания заявки. ная стоимость % прибора к задаётся отношением =: заданной стоимости эксплуатации Си(цк) = с* к интенсивности обслуживания прибора fik, и приборы в данной задаче упорядочены в порядке возрастания их средних эксплуатационных стоимостей: < < . < Относительно этого порядка существует два типа оптимального управления. В случае, если среднее время обслуживания возрастает медленнее, чем убывает стоимость эксплуатации, то оптимальное управление имеет такую же структуру, как и в NJM-задаче, т.е. задаётся последовательностью пороговых уровней q\ < < • • • < q*K. В данном случае оптимальное управление также является "порогового типа"с пороговыми уровнями gj, и управляющее устройство всегда выбирает прибор с наименьшей средней стоимостью эксплуатации, что относительно введённого порядка для параметров системы эквивалентно правилу включения самого быстрого прибора. В случае, когда среднее время обслуживания убывает быстрее, чем возрастает стоимость эксплуатации, т.е. если < ^ < . < Цк и Cu{iii) < Cu(ii2) < . < Си{цк), но их значения удовлетворяют приведенному выше неравенству для средних эксплуатационных стоимостей, тогда оптимальное управление имеет более сложную структуру, чем в приведённых выше случаях, т.е. характеризуются пороговыми уровнями 910е) < 92:0е) ^ "" ^ Q*k(x)i зависящими от состояний системы х € Е. В соответствии с этим правилом управления, свободный в некотором состоянии х € Е прибор j должен быть включён только тогда, когда длина очереди q(x) в этом состоянии ограничена снизу и сверху соответствующими порогами q*(x) и q]+ г(х): q](x) < q{x) < Qj+1(x). Если q*(x) = q*j+l(x), тогда предпочтение отдаётся более быстрому прибору j + 1, и, если прибор j является последним свободным прибором3 в данном состоянии, тогда

3Имеется в виду свободный прибор с наибольшим индексом относительно выбранного упорядочения. его использование является оптимальным всякий раз, когда q(x) > gj(x)

U = 1,.,К).

В третьей главе рассматриваются УСМО с более общими типами распределений времён между поступлениями заявок, например, с распределением Эрланга (Е) и РН-распределением, а также более общим случаем -марковским потоком заявок (MAP). Так же как и в предыдущей главе, для данных управляемых очередей исследуются качественные и количественные свойства оптимального управления относительно введённых оптимизационных критериев, NJM и РСМ. В частности установлено, что для этих систем выполняются те же качественные свойства оптимальных политик, что и представленные в предыдущей главе, т.е. оптимальное управление имеет пороговую структуру как и в случае пуассоновского входящего потока. Единственное отличие состоит в том, что теперь оптимальные пороговые уровни зависят от состояний процесса поступления (фазы генерации новой заявки). Изучение такой зависимости является важным пунктом данной главы. Результаты численного анализа систем МАР/М/К приводятся в приложении 2.

В четвёртой главе исследуются УСМО с распределениями времён обслуживания фазового типа, к которым относятся эрланговское и РН-распределение. Получение полных аналитических результатов для данных систем довольно сложная задача, поэтому наряду с изучением качественных свойств оптимального управления проведено подробное численное исследование дающее исчерпывающий ответ об этих свойствах. Результаты представлены в виде предложений, базирующихся на численных примерах и аналогии поведения данных систем с теми УСМО, для которых получены теоретические доказательства. Оптимальное управление для изучаемых в данной главе систем снова имеет пороговую структуру, но теперь пороги зависят от состояний процесса обслуживания (фазы обслуживания) на приборах. В случае наличия более сложного входящего потока заявок оптимальные пороги зависят и от фаз генерации, и от фаз процесса обслуживания. Результаты численного анализа систем М/РН/К/ и МАР/М/К приводятся в приложении 3.

4.5. Выводы

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

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

Заключение

В работе получены следующие результаты:

1. Для всех типов систем определён управляемый марковский процесс и выведены уравнения оптимальности, которые используются для нахождения оптимальных политик управления для каждого состояния рассматриваемых систем.

2. Для всех типов систем рассмотрены две задачи оптимизации: относительно критерия минимизации среднего числа заявок и средних потерь в системе (с учётом дополнительной структуры штрафов).

3. Для систем МАР/М/К доказано, что оптимальная дисциплина обслуживания для критерия минимизации среднего числа заявок является пороговой, при этом следует включать наиболее быстрый из доступных приборов и значение порога имеет слабую зависимость от состояний более медленных приборов.

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

Для систем М/РН/К и, соответственно, МАР/РН[К приведённые результаты подтверждаются на основе численного анализа и сходства данных систем с теми, для которых получены теоретические доказательства.

4. Исследована зависимость оптимальных пороговых уровней от состояний процесса поступления и обслуживания в случае распределений фазового типа. Значения пороговых уровней возрастают при увеличении остаточного времени до поступления новой заявки и/или при уменьшении остаточного времени обслуживания более быстрых приборов.

5. Для систем с отсутствием входящего потока заявок (задача расписания) получены явные формулы для вычисления пороговых уровней. Эти значения представляют собой верхнюю границу соответствующих пороговых уровней для аналогичных систем с входящим потоком.

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

1. Бочаров П. П., Печинкин А.В. Теория массового обслуживания. М: Изд-во РУДН, 1995. 528 с.

2. Бочаров П. П., Печинкин А. В., Фонг Н. X. Стационарные вероятности состояний системы MAP/G/1/r с повторными заявками и приоритетным обслуживанием первичных заявок// Автоматика и Телемеханика. 2000. Т. 8. С. 68-78.

3. Бочаров П. П., Атенсия И. М., Д'Апиче Ч., Фонг Н. X. Однолинейная система массового обслуживания с многомерным пуассоновским потоком и повторными заявками// Автоматика и Телемеханика. 2000. Т. 11. С. 123-138.

4. Ванько В. И., Ермошина О. В., Кувыркин Г. Н. Вариационное исчисление и оптимальное управление. T.XV. М: Изд-во МГТУ имени Н.Э. Баумана, 2001. 480 С.

5. Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. М: Наука, 1987. 176 С.

6. Дынкин Е. Б., Юшкевич А. А. Управляемые марковские процессы и их приложения. М: Наука, 1975. 154 С.

7. Кофман А., Крюон Р. Массовое обслуживание. Теория и приложения. М: Наука, 1965. 323 С.

8. Рыков В. В. Управляемые марковские процессы с конечными пространствами состояний и управлений// Теория вероятностей и её применеия. 1966. Т. 11(2). С. 302-311.

9. Рыков В. В. Управляемые системы массового обслуживания// Итоги науки и техники. Теория вероятностей и математической статистики. Теоретическая кибернетика. 1975. Т. 12. С. 45-152.

10. Рыков В. В. Об условиях монотонности оптимальных политик управления системами массового обслуживания// Автоматика и Телемеханика. 1999. Т. 9. С. 92-106.

11. Рыков В. В., Ефросинин Д. В. Численное исследование оптимального управления системой с неоднородными приборами// Автоматика и Телемеханика. 2003. Т. 2. С. 127-143.

12. Ховард Р. А. Динамическое программирование и марковские процессы. М: Советское радио (перевод с английского), 1964, 191 С.

13. Agravala А. К., Goffman Е. G., Garey М. R., Tripathi S. К. А stochastic optimization algorithm minimizing expected flow times on uniform processors// IEEE Transactions on Computers. 1984. V. 33. C. 351-356.

14. Altman E., Koole G. On submodular functions of dynamic programming// Technical Report 2658, INRIA Sophia Antipolis. 1995. 14 C.

15. Altman E., Jimenez Т., Koole G. On optimal call admission control in a resource-sharing system// Technical Report, Vrije University, Amsterdam.2000. 18 C.

16. Asmussen S., Koole G. Marked point processes as limits of Markovian arrival streams// Journal of Applied Probability. 1993. V. 30(2). C. 365372. .

17. Asmussen S., Neman 0., Olsson M. Fitting phase-type distributions via the EM algorithm// Scandinavian Journal of Statistics. 1996. V. 23(4). C. 419-441.

18. Asmussen S., Mueller J. R. Calculation of steady state waiting time distribution in GI/PH/c and MAP/PH/c queues// Queueing systems.2001. V. 37. C. 9-29.

19. Baum D. Convolution algorithms for ВМАР/G/ 1-Queues// Forschungsbericht, Universitat Trier, Abteilung Mathematik und Informatik. 2002. 96(22). 48 C.

20. Baum D. The infinite server queue with Markov additive arrivals in space// Forschungsbericht, Universitat Trier, Abteilung Mathematik und Informatik. 2002. 98(31). 28 C.

21. Bocharov P. P., D'Apice C., D'Auria В., Salerno S. A queueing model of finite capacity with the server requiring a priority search for customers// Вестник РУДН, Прикладная математика и информатика. 2000. Т. 1. С. 49-59.

22. Boel R. К., Talat N. К. Performance analysis and optimal threshold policies for queueing systems with several heterogeneous servers and Markovmodulated arrivals// Technical Report, Katholik University, Belgium. 1997. 22 C.

23. Breuer L. The Periodic BMAP/PH/c Queue// Queueing Systems. 2001. V. 38(1). C. 67-76.

24. Breuer L. An EM Algorithm for Batch Markovian Arrival Processes and its Comparison to a Simpler Estimation Procedure// Annals of Operations Research. 2002. V. 112. 16 C.

25. Breuer L., Dudin A. N., Klimenok V. I. A Retrial BMAP/PH/N System// Queueing Systems. 2002. V. 40(4). C. 431-455.

26. Brouns G. Optimal control of routing to two parallel finite capacity queues or two parallel Erlang loss systems with dedicated and flexible arrivals// Technical Report, University of Amsterdam. 2002. 15 C.

27. Burman D. Y., Smith D. R. An asymptotic analysis of a queueing system with Markov modulated arrivals// Operations Research. 1986. V. 34. C. 105-119.

28. Crabill Г., Gross D., Magazine M. J. A classified bibliography of research on optimal design and control of queues// Operation Research. 1977. V. 25. C. 219-232.

29. Driankov D., Hellendoorn H., Reinfrank M. An introduction to fuzzy control. Springer-Verlag, Berlin, New York. 1993. 128 C.

30. Dudin A. N., Klimenok V. I. Optimal admission control in a queueing system with heterogeneous traffic// Operations Research Letters. 2003. V. 31. C. 108-118.

31. Dudin A. N., Choi B. D., Chung Y. H. The BMAP/SM/1 retrial queue with controllable operation modes// European Journal of Operational Research. 2001. V. 131. C. 16-30.

32. Efrosinin D. V,Breuer L. An optimization algorithm for the MAP/PH/K queue with heterogeneous servers// Forschungsbericht, Trier University, Germany. 2002. V. 2(15). C. 1-22.

33. Efrosinin D. V. Threshold phenomenon in controlled retrial queues with heterogeneous servers// Technical Reports of the mathematical institutes, Linz University, Austria. 2004. V. 560. C. 1-25.

34. Fu M. C., Marcus S. /., Wang I-J. Monotone optimal policies for a transient queueing staffing problem// Technical Report, Institute for Systems Research. 1998. 22 C.

35. Glasserman P., Yao D. D. Monotone structure in discrete event systems. Wiley Series, 1994. 128 C.

36. He Y., Fa M., Marcus S. Simulation-based algorithms for average cost Markov decision Processes// Technical Report, University of Maryland, USA. 1999. 20 C.

37. Hipp S. K., Holzbaur U. D. Decision processes with monotone hysteretic policies// Operations Research. 1988. V. 36(4). 12 C.

38. Jewell W. S. Controllable semi-Markov Processes// Cybernetics. 1967. V. 4. C. 97-137.

39. Kalashnikov V. V. Mathematical methods in queuing theory. Kluwer, 1994. 121 C.

40. Kelly F. P. Routing in circuit switched networks: optimization, shadow prices and decentralization. Applied Mathematics, 1987. 112 C.

41. Kitaev M. Yu., Rykov V. V. Controlled queueing systems. CRC Press, New York, 1995. 286 C.

42. Kleinrock L. Queueing Systems. Volume I: Theory. New York, Wiley Series, 1975. 246 C.

43. Koole G. A simple proof of the optimality of a threshold policy in a two-server queueing system// Systems Control Letters. 1995. V. 26. C. 301-303.

44. Krishnan K. R., Ott T. J. State dependent routing for telephone traffic: theory and results// Proceedings of the IEEE Conference on Decision and Control. 1986. 12 C.

45. Langrock P., Rykow W. W. Methoden und Modelle zur Steurung von.Bedienungssystemen// Handbuch der Bedienungs theorie, Berlin, Akademie-Verlag. 1984. V. 2. C. 422-486,

46. Larsen R. L. Control of multiple exponential servers with application to computer systems// Ph.D. thesis, University of Maryland. 1981. 168 C.

47. Larsen R. L., Agrawala A. K. Control of a heterogeneous two-server exponential queueing system// IEEE Transactions on Software Engineering. 1983. V. 9(4). C. 522-526.

48. Le Ny L.-M., Taffin B. A simple analysis of heterogeneous multi-server threshold queues with hysteresis// Technical Report, Institut National de Recherche en Informatique, Prance. 2000. 18 C.

49. Lerrna О. H., Lassere J. B. Discrete-Time Markov Control Processes. Applications of Mathematics, New-York, 1996. 146 C.

50. Lerrna О. H., Lassere J. B. Further topics on discrete-time Markov control processes. Application of Mathematics, New-York, 1999. 185 C.

51. Lin W., Kumar P. R. Optimal control of a qucueing system with two heterogeneous servers// IEEE Transactions on Automatic Control. 1984. V. 29. C. 696-703.

52. Lippman S. Applying a new device in the optimization of exponential queueing systems// Operations Research. 1975. V. 23. C. 687-710.

53. Lippman S. Semi-Markov decision processes with unbounded rewards// The Mathematical Scientist. 1973. V. 19(7). C. 717-731.

54. Lu F. V., Serfozo R. F. M/M/l Queueing decision processes with monotone hysteretic optimal policies// Operations Research. 1984. V. 32.1. C. 1116-1132.

55. Luh H. P., Viniotis I. Optimality of threshold policies for heterogeneous server systems// Technical Report, Raleign, North Carolina State• University 1990. 18 C.

56. Luh H. P., Viniotis I. Threshold control policies for heterogeneous server systems// Mathematical Methods of Operations Research. 2002. V. 55. C. 121-142.

57. Lucantoni D. M. New results on the single server queue with a batch Markovian arrival process// Communications in Statistics, Stochastic Models. 1991. V. 7(1). C. 1-46.

58. Lucantoni D. M., Hellstem K. S., Neuts M. F. A single-server queue with server vacations and a class of non-Renewal arrival processes// Advantage of Applied Probability. 1990. V. 22. C. 676-705.

59. Mine H., Osaki S. Markovian Decision Processes. Elsevier, 1970. V. XI. 142 C.

60. Naoumov V., Krieger U. R., Wagner D. Analysis of a multi-server delay-loss system with a general Markovian arrival process// Matrix-analytic methods in stochastic models, Flint, MI, Dekker, New York. 1997. C. 4366. ~

61. Neuts M. F. Markov chains with applications in queueing theory, which have a matrix-geometric invariant probability vector// Advanced Applied Probability. 1978. V. 10. C. 185-212.

62. Neuts M. F. Matrix-geometric solutions in stochastic models. The Johns Hopkins University Press, Baltimore, London, 1981. 15 C.

63. Neuts M. F. Structured stochastic matrices of M/G/l type and their applications. Marcel Dekker, New York, 1989. 28 C.

64. Nobel R. Hysteretic and heuristic control of queueing systems// Phd dissertation, Vrije University, Amsterdam. 1998. 140 C.

65. Nobel R., Tijms H. C. Optimal control of a queueing system with heterogeneous servers// IEEE Transactions on Autom. Control. 2000. V. 45(4). 18 C.

66. Nobel R. Optimal control of an Mx/G/1 queue with varying arrival rate and service mode// Motable Publications, Inc., Vrije University, Amsterdam. 1995. 15 C.

67. Piunovskiy А. B. Optimal control of random sequences in problems with constraints. Kluwer Academic Publishers, 1997. 360 C.

68. Puterman M. L. Markov Decision Process. Wiley series in Probability and Mathematical Statistics, 1994. 480 C.

69. Reiman M. I. Optimal control of a heterogeneous two server queue in light traffic// Technical Report, AT&T Bell Labs., Murray Hill, NJ. 1989. 17 C.

70. Reiman M. I., Simon В. Open queueing systems in light traffic// Mathematical Operations Research. 1989. V. 14. C. 26-59.

71. Ross Sh. Applied probability models with optimization applications. Holden Day, San Francisco, 1970. 225 C.

72. Rosberg Z., Makowski A. M. Optimal routing to parallel heterogeneous servers small arrival rates// Transactions on automatic control.' 1990. V. 35(7). C. 789-796.

73. Rosberg Z., Varaiya P., Walrand J. Optimal control of service in tandem queues// IEEE Transactions on Automatic Control. 1982. V. 27. C. 600610.

74. Rykov V. V. Markov decision processes with finite state and decision spaces// Probability Theoiy.and its Applications. 1966. V. 11(2). C. 302311.

75. Rykov V. V. On monotonicity conditions for optimal policies for controlling queueing systems// Autom. and Remote Control. 1999. V. 60(9). C. 12901301.

76. Rykov V. V. Monotone Control of Queueing Systems with Heterogeneous Servers// QUESTA. 2001. V. 37. C. 391-403.

77. Rykov V. V., Efrosinin D. V. Numerical analysis of optimal control policies for queueing systems with heterogeneous servers// Информационные процессы. 2002. T.2(2). С. 252-256.

78. Rykov V. У., Efrosinin D. V. Numerical analysis of optimal control policies for queueing systems with heterogeneous servers// Queueing Systems. 2004. V. 46. C. 389-407.

79. Sandjai В., Koole G. On the structure of value functions for threshold policies in qucueing models// Technical Report, University of Amsterdam. 2002. 18 C.

80. Schassberger R. Warteschlagen. Wien-New York, Springer-Vcrlag, 1973. 112 C.

81. Sennott L. Stochastic dynamic programming and control of queueing systems. New York, Wiley, 1999. 328 C.

82. Serfozo R. F. An equivalence between continuous and discrete time Markov decision processes// Operations Research. 1979. V. 27. C. 616-620.

83. Shenker S., Weinrib A. Asymptotic analysis of large heterogeneous queueing systems// Technical Research, Bell Communication. 1988. 22 C.

84. Stidham Jr Sh. Optimal control of admission to a queueing system// IEEE Transactions on Automatic Control. 1985. V. 30. C. 705-713.

85. Stidham Jr Sh., Weber R. A survey of Markov decision models for control of networks of queues// QUESTA. 1993. V. 13. C. 291-314.

86. Tijms H. C. Stochastic models. An algorithmic approach. John Wiley and Sons, 1994. 215 C.

87. Tijms H. C. Stochastic modeling and analysis. A computational approach. John Wiley and Sons, 1986. 232 C.

88. Topkis D. Minimizing a submodular function on a lattice// Operations Research. 1978. V. 26(2). C. 305-321.

89. Weber R. On a conjecture about assigning jobs to processors of different speeds// IEEE TVansactions on Automatic Control. 1993. V. 38. C. 166170.

90. Wolf F., Danzig G. Markov chains and linear programming// Cybernetics. 1967. V. 4. C. 86-96.

91. Walrand J. A note on 'Optimal control of a queueing system with two heterogeneous servers'// Systems Control Letters. 1984. V. 4. C. 131-134.

92. Viniotis L, Ephremides A. Extension of. the optimality of a threshold policy in heterogeneous multi-server queueing systems// IEEE Transactions on Automatic Control. 1988. V. 33. C. 104-109.

93. Zhang C., Baras J. S. A new adaptive aggregation algorithm for infinite horizon dynamic programming// Technical Report, the Center for Satellite and Hybrid Communication Networks. 2001. 18 C.

94. Zhang R., Phillis Y. A. Fuzzy routing of queueing systems with heterogeneous servers

95. EE Robotics and Automation. 1997. V. 3. C. 2340-2345.