Управляемые системы массового обслуживания с неоднородными приборами

• Автор: Ефросинин, Дмитрий Владимирович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 247 с. : ил.

Содержание
Введение

Глава 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. Пороговая структура оптимального управления. Пороговая функция для ШМзадачи
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. Выводы
Заключение
Литература


Марковская задача принятия решений состоит в нахождении такой оптимальной стратегии, которая минимизировала бы потери относительно заданного критерия до момента принятия первого решения. Таким образом, теория управляемых марковских процессов в некотором смысле устанавливает взаимосвязь между множествами управлений, состояний, вероятностей переходов и цен для решения поставленной задачи. Фактическое определение оптимальных стратегий сопряжено с большими трудностями. Поэтому естественно стремление сузить класс исследуемых на оптимальность стратегий. В некоторых случаях такое сужение оказывается естественным и не ухудшает качества управления. Для широкого класса систем, к которым относятся и исследуемые в данной работе, оказывается, что оптимальную стратегию можно искать в классе так называемых однородных марковских стратегий. Определение 1. Однородная марковская стратегия 5 = {/(х),х € Е} предписывает управляющему устройству независимо от времени принимать одно и то э/се решение /(х) € А(х), где А(х) множество доступных управлений в состоянии х, каждый раз, когда система находится в состоянии х в момент управления. Теперь можно дать определение управляемого марковского процесса. Наблюдения над системами во времени будут производиться непрерывно 0 < * < оо, поэтому рассматриваемые системы будут описываться процессами с непрерывным временем. В общем случае рассматривают управляемый процесс {? Наблюдаемый процесс {^(? В качестве управляющего процесса рассмотрим процесс {? Пусть А множество заданных допустимых управлений и А(х) С А множество заданных допустимых управлений, если текущее состояние системы х. Согласно определению марковской однородной стратегии, если в некоторый момент времени t система находится в состоянии х, X(t) = х € Е, то диспетчер выбирает допустимое управление (будем предполагать детерминированное) в этом состоянии, т. U(t) = а = }{х) € А(х)} В настоящей работе будет предполагаться, что множества состояний Е и управлений А являются конечными. Предположение о конечности множества состояний не является жёстким ограничением в случае моделей с неинтенсивным трафиком (light traffic models)2 и совсем не является ограничением для систем с конечной ёмкостью буфера. Определение 1. Управляемый процесс называется марковским, если выпол)1яется следующее марковское свойство. Выплачивается штраф размера с(х) за единицу времени пребывания в состоянии х. Детерминированная политике управления может рассматриваться как специальный случай рандомизированной политики, для которой распределение вероятностей па множестве управлений является вырожденным, т. Р(1/(0 — о|ЛГ(t) = х) = 1. Для систем массового обслуживания это означает значительное превышение среднего времени между поступлениями заявок над средним временем их обслуживания. Ахх (а) = — уб? Аху(а). Аху(а) интенсивности переходов процесса {2(1)}. При любой стратегии 5 вероятность того, что за время [? Л) в процессе произойдёт более одного изменения, бесконечно мала по сравнению с 1г. Как мы видим, более важными параметрами управляемого марковского процесса с непрерывным временем являются интенсивности, а не вероятности переходов. Мы будем рассматривать только такие процессы, для которых интенсивности переходов Ахг/(а) постоянны. Это предположение эквивалентно допущению для процессов с дискретным временем, состоящему в том, что вероятности переходов нс изменяются со временем 3. Также заметим, что на управляющее устройство налагается фиксированный штраф с(х) за единицу времени в течении всего периода пребывания системы в состоянии X. Таким образом, рассматриваемые управляемые марковские процессы будут скачкообразными, и изменения управления могут происходить лишь в моменты изменения их состояний. В связи с этим следует отметить, что управляемые системы массового обслуживания также могут быть описаны процессами с дискретным временем (вложенной цепыо по моментам изменения состояния). В этом случае модель с непрерывным временем можно преобразовать к сё дискретному аналогу. Процедура такого преобразования хорошо известна и описана в работах, например Липмана [], Розбсрга [] и Ссрфозо []. Тпкис процессы пазыиаются однородными.