Управляемые системы массового обслуживания с неоднородными приборами тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Ефросинин, Дмитрий Владимирович

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

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

Введение

Глава 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. Для всех рассматриваемых систем проведён объёмный численный анализ свойств оптимальных политик управления с помощью специальных таблиц и диаграмм управлений. Эти таблицы и диаграммы также используются для сравнения характеристик дисциплин обслуживания для различных систем.

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

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.