Актуальность темы
обосновывается большим количеством практических задач, описываемых системами массового обслуживания с переналадкой в качестве математической модели, и необходимостью разработки методов нахождения оптимальных дисциплин управления такими системами* Модели систем массового обслуживания с переналадкой прибора могут быть использованы для решения различных станочных задач (управление универсальными станками, способными обрабатывать различные виды деталей в разных режимах) — при оптимизации технологических процессов, где существенен порядок выполнения операцийпри исследовании функционирования ЭВМ, работающих с разделением времени, для управления обработкой программ многих пользователей. Недостаточная изученность систем массового обслуживания с переналадкой, особенно их управления с помощью внутрисистемных дисциплин, требует дальнейшей разработки методов исследования и нахождения наиболее гибких режимов обслуживания.
В диссертации предлагается постановка задачи управления системой массового обслуживания с переналадкой прибора в терминах управляемых марковских процессов. Исследуется одна из наиболее гибких дисциплин обслуживания, предполагающая возможность управления в каждый из моментов очередного освобождения прибора. Функционирование исследуемой системы массового обслуживания представлено как управляемый марковский процесс со счетным множеством состояний. В качестве целевого функционала рассматриваются средняя стоимость ожидания требования, в очереди и средняя стоимость пребывания требования в системе. Вводится понятие управляемого марковского процесса со счетным множеством состояний, устойчивого относительно изменения стратегии. Найдены условия устойчивости исследуемого процесса с рассматриваемыми целевыми функционалами. Методы исследования марковских процессов принятия, решений с конечным множеством состояний распространены на случай устойчивых процессов, множество. состояний которых счетно. Решен принципиальный вопрос о существовании и форме оптимальных правил обслуживания, доказана теорема существования оптимальной стационарной стратегии управления для устойчивых марковских процессов, а также оптимальность ее на множестве всех стратегий, включая нестационарные. Предложен и обоснован алгоритм определения? -оптимальных стратегий, модифицирующий метод Ховарда в случае процесса со счетным множеством состояний.
На защиту выносится:
1. Подход к решению задачи оптимизации работы системымассового обслуживания с многокомпонентным входным потоком и учетом времени переналадки обслуживающего прибора при дисциплинах, допускающих управление в каждый момент освобождения прибора, с использованием аппарата управляемых марковских процессов,.
2. Доказательство существования стратегии управления, оптимальной среди стационарных, для процесса со счетным множеством состояний, устойчивого относительно изменения стратегии. Частным случаем является процесс обслуживания требований в системе массового обслуживания с переналадкой прибора при использовании целевого функционала типа средней стоимости ожидания требования в очереди и средней стоимости пребывания требования в системе.
3. Доказательство для устойчивого процесса существования стационарной стратегии, оптимальной на всем множестве стратегий, включая нестационарные.
4. Алгоритм построения? -оптимальных стационарных стратегий для устойчивого процесса путем сведения к управляемому марковскому процессу с конечным множеством состояний.
Изложение материала диссертации проводится в трех главах. В § I.I главы I дано описание исследуемой системы массового обслуживания с двухкомпонентным входным потоком и учетом времени переналадки обслуживающего прибора при переходе от выполнения требования одного типа к другому. Предполагается, что на вход обслуживающего прибора поступают два независимых пуассо-новских потока интенсивностей ш А^. Время обслуживания распределено экспоненциально, интенсивность обслуживания, требования jго типа после гго равна Управление осуществляется в моменты освобождения прибора выбором в очереди требования определенного типа для направления на обслуживание. С целью изучения системы выделяется вложенная цепь Маркова со счетным множеством состояний. Ставится задача нахождения оптимальной дисциплины обслуживания требоваг-ний в очереди по критерию средней стоимости ожидания требования в очереди и средней стоимости пребывания требования в системе.
В § 1.2 и 1.3 поставленная задача оптимизации системы массового обслуживания формулируется в терминах управляемых марковских процессовфункционирование исследуемой системы представлено как управляемый марковский процесс со счетным множеством состояний. Найдены функции средних ожидаемых штрафов при выходе из состояния процесса для рассматриваемых целевых функционаловв дальнейшем исследуется общий случай штрафов, линейно зависящих от числа требований каждого типа, находящихся в очереди в данном состоянии. Найдены условия существования стационарного распределения для рассматриваемого процесса. Изложены основные методы исследования управляемых марковских процессов с конечным множеством состояний. Распространению этих результатов на рассматриваемый процесс, множество состояний которого счетно, посвящена глава 2.
В главе 2 рассмотрены метода нахождения квазиоптимальных и оптимальных дисциплин обслуживания очереди в исследуемой системе с переналадкой. В § 2.1 рассмотрен режим пакетной обработки требований в очереди. Найден вид оптимального порядка обработки по критерию среднего времени пребывания в системе требований данного пакета. Такая дисциплина обслуживания является оптимальной лишь локально (для данного пакета), но может быть использована в качестве подхода к решению задачи определения более гибких дисциплин, предполагающих возможность управления очередью в каждый из моментов освобождения прибора после выполнения, очередного требования.
§ 2.2 посвящен доказательству существования оптимальной в классе стационарных стратегии управления очередью в исследуемой системе, описываемой как управляемый марковский процесс со счетным множеством состояний. Вводится понятие управляемого марковского процесса принятия решений, устойчивого относительно изменения стратегии. С использованием оценок для вероятнос-тейстационарного распределения доказана устойчивость рассматриваемого процесса при данных функционалах. В основной теореме параграфа приведено доказательство существования стратегии, оптимальной в классе стационарных, и дано обоснование метода построения? -оптимальных стратегий путем сведения задачи к конечной для.устойчивого.марковского процесса.
В § 2.3 доказано, что стратегия, оптимальная в классе стационарных, является оптимальной на множестве всех стратегий, включая нестационарные. При доказательстве исходная задача рассматривается как предельный случай управляемого марковского процесса с переоценкой.
Глава 3 посвящена конкретной реализации предложенного алгоритма построения? -оптимальных стратегий, который сходится как на множестве значений функционала, так и на множестве стратегий, обеспечивающих существование стационарного режима в системе. В § 3.1 выведены формулыдля преобразования матрицы вероятностей перехода и вектора средних ожидаемых штрафов при исследовании процесса на конечном подмножестве состояний. Доказана возможность получения? -оптимальных стратегий по методу Ховарда, примененному к задаче с модифицированными матрицей вероятностей перехода и вектором средних ожидаемых штрафов.
В § 3.2. на основании полученных в § 3.1 формул преобразования найден конкретный вид матрицы вероятностей перехода и вектора средних ожидаемых штрафов для исследуемого процесса управления системой массового обслуживания с переналадкой, рассматриваемого на конечном подмножестве состояний. Примеры, иллюстрирующие использование систем массового обслуживания с переналадкой в качестве математических моделей для ряда реальных процессов, приведены в § 3.3.
При изложении содержания диссертации принята следующая система обозначений.
Вектора и их компоненты обозначаются одинаковыми буквами, так что, например, С|,(?э)есть вектор с компонентами. — единичный векторЕ — единичная матрицаО — нулевой вектор (матрица) — * означает операцию транспонированиязапись VC=i>Vb означает, что К изменяется от -1 до уъ — знак = употребляется вместо слов «обозначим», «положим по определению.
При нумерации формул и утверждений первая цифра соответствует номеру главы, вторая — номеру параграфа, третья является порядковым номером формулы или утверждения в данном параграфе.
Основные результаты опубликованы в следующих статьях:
1. Захаркина В. В. Оптимальное управление очередью в системе массового обслуживания с переналадкой прибора. — Рукопись депонирована в ВИНИТИ 7.08.80, № 3506−80. — 14 с.
2. Захаркина В. В. Об управлении системой массового обслуживания с переналадкой при помощи ступенчатых стратегий. -Рукопись депонирована в ВИНИТИ 21.09.81, № 4528−81, — б с.
3. Захаркина В. В. Оптимальный порядок обработки пакета требований в системе массового обслуживания с переналадкой прибора. — В кн: Управление, надежность и навигация. Саранск, 1981, с.183−184.
4. Захаркина В. В. О существовании оптимальной стратегии управления очередью в одной задаче теории массового обслуживания. — Рукопись депонирована в ВИНИТИ 15.09.82, № 4857−82. — 15 с.
5. Захаркина В. В. Об оптимальных стратегиях управления в одной системе массового обслуживания. — В кн.: Оптимальное управление механическими системами. Л., 1983, с. 81−88.
Результаты диссертации докладывались на конференциях молодых ученых факультета прикладной математики-процессов управления ЛГУ имени А. А. Жданова (1979, 1980 г.) и на семинарах кафедры теории управления того же факультетана конференции молодых ученых по проблемам микроэлектроники МИЗТ, Москва (1980 г.) — на семинаре кафедры теории вероятностей и математической статистики БГУ имени В. И. Ленина (1983 г.).
— ddlj.
ЗАКЛЮЧЕНИЕ
.
В диссертации рассмотрена задача оптимизации работы система1 массового обслуживания с переналадкой прибора при использовании дисциплины, допускающей возможность управления в каждый момент освобождения прибора после обслуживания очередного требования. Проблема разработки методов исследования систем с переналадкой при наиболее гибких режимах обслуживания, нахождение оптимальных дисциплин являются актуальными вследствие малой изученности подобных систем, особенно их управления с помощью внутрисистемных приоритетных дисциплин. Необходимость изучения систем с переналадкой диктуется потребностями практики. Результаты исследования таких систем могут быть применены при оптимизации различных производственных процессов, для управления обработкой программ многих пользователей в ЭВМ, работающих с разделением времени, во многих других практических задачах.
В диссертации получен ряд новых результатов.
В главе I приведено описание исследуемой СМО с переналадкой и поставлена задача управления очередью в терминах управляемых марковских процессов принятия решений со счетным множеством состояний. В качестве критерия оптимальности стратегии управления рассмотрены средняя стоимость ожидания требования в очереди и средняя стоимость пребывания требования в системе'. Найдены условия существования стационарного распределения для рассматриваемого марковского процесса. Приведена матрица вероятностей перехода и вектор средних ожидаемых штрафов, компоненты которого для рассматриваемых критериев линейно зависят от длин очередей каждого типа в данном состоянии.
В § 2.1 главы Z исследована дисциплина пакетной обработки для исследуемой системы массового обслуживания и найден вид оптимального порядка обслуживания требований в пакете по критерию среднего времени пребывания в системе требования данного пакета.
§ 2.2 посвящен исследованию стационарных стратегий, допускающих возможность управления очередью в каждый момент освобождения прибора. Вводится понятие управляемого марковского процесса принятия решений, устойчивого относительно изменения стратегии, которое играет существенную роль при доказательстве существования оптимальной стратегии. Устойчивость рассматриваемого процесса доказана в лемме 2.2.2 с использованием оценок для предельных вероятностей, полученных в лемме 2.2.1. Оценки позволяют сделать вывод о равномерной малости предельных вероятностей пребывания в состояниях с большими очередями для всех стратегий, обеспечивающих существование стационарного режима.
В теореме 2.2.1 доказывается для исследуемого процесса существование стратегии, оптимальной в классе стационарных, и обосновывается метод построения? -оптимальных стратегий путем сведения исходной задачи к конечной. Для получения? —оптимальной стратегии достаточно варьировать значения стратегии на конечном множестве состояний, фиксировав ее в остальных состояниях с достаточно большими очередями, в которых за счет устойчивости процесса стратегия мало влияет на значения функционала. Предлагаемый метод сходится на множестве значений функционала и на множестве стратегий.
В § 2.3 доказана оптимальность стратегии, оптимальной в классе стационарных, на множестве всех стратегий, включая нестационарные. Исследуемая задача рассматривается как предельный случай управляемого марковского процесса с перео.
— d±l ценной. Доказана устойчивость процесса с переоценкой (лемма 2.3.1) и существование для этого процесса стационарной стратегии, оптимальной на множестве всех стратегий, включая нестационарные (лемма 2.3.2). Существование стационарной стратегии, оптимальной на множестве всех стратегий, в исследуемой задаче без переоценки доказано в теореме 2.3.1. Полученные результаты справедливы, и для общего случая устойчивых марковских процессов С теорема 2.3.2).
В § 3.1 главы 3 проведено исследование управляемого марковского процесса, рассматриваемого на конечном подмножестве состояний. В лемме 3.1.I выведена формула для преобразования вектора средних ожидаемых штрафов в таком процессе (преобразование матрицы вероятностей перехода проведено по известной. формуле). Возможность получения? -оптимальных стратегий по методу Ховарда, примененному к процессу, рассматриваемому на подмножестве состояний, обоснована в лемме 3.1.2. Конкретный вид преобразованных матриц и векторов для процесса, описывающего работу исследуемой СМО, получен в § 3.2.
Примеры приложения полученных результатов для управления рядом реальных процессов приведены в § 3.3.
В диссертации получены следующие основные результаты.
1. Задача оптимизации системы массового обслуживания с многокомпонентным входным потоком и учетом времени переналадки прибора поставлена с использованием аппарата управляемых марковских процессов для дисциплин, допускающих управление в каждый момент освобождения прибора.
2. Для управляемого марковского процесса со счетным множеством состояний, устойчивого относительно изменения стратегии, частным случаем которого является, процесс управления исследуемой СМО, доказано существование стратегии управления, оптимальной в классе стационарных, при использовании целевого функционала типа средней стоимости ожидания требования в очереди и средней стоимости пребывания его в системе.
3. Доказано существование для устойчивого процесса стационарной стратегии, оптимальной на всем множестве стратегий, включая нестационарные.
4. Предложен и обоснован алгоритм построения? -оптимальных стратегий для устойчивого процесса путем сведения к управляемому марковскому процессу с конечным множеством состояний. Метод сходится на множестве значений функционала и на множестве стратегий.
