Система массового обслуживания с переналадкой прибора тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение . стр.

Глава I. Постановка задачи. Описание работы системы массового обслуживания как управляемого марковского процесса.

§1.1 Описание системы массового обслуживания с переналадкой прибора.

§ 1.2 Представление функционирования системы массового обслуживания с переналадкой прибора как управляемого марковского процесса.

§ 1.3 Оптимальные стратегии управления очередью. Вид функционала.24.

Глава 2. Существование и методы построения оптимальной стратегии управления очередью.

§ 2.1 Оптимальный порядок обработки требований в пакете для системы массового обслуживания с переналадкой прибора.

§ 2.2 Существование оптимальной стационарной стратегии. Построение -оптимальных стратегий

§ 2.3 Существование стационарной стратегии, оптимальной на множестве всех стратегий, включая нестационарные.

Глава 3. Реализация алгоритма построения £ -оптимальных стратегий. Примеры и приложения.

§ 3.1 Исследование управляемого марковского процесса на конечном подмножестве состояний.

§ 3.2 Преобразование матрицы вероятностей перехода и вектора средних ожидаемых штрафов для процесса, рассматриваемого на конечном подмножестве состояний.

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

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

В диссертации предлагается постановка задачи управления системой массового обслуживания с переналадкой прибора в терминах управляемых марковских процессов. Исследуется одна из наиболее гибких дисциплин обслуживания, предполагающая возможность управления в каждый из моментов очередного освобождения прибора. Функционирование исследуемой системы массового обслуживания представлено как управляемый марковский процесс со счетным множеством состояний. В качестве целевого функционала рассматриваются средняя стоимость ожидания требования , в очереди и средняя стоимость пребывания требования в системе. Вводится понятие управляемого марковского процесса со счетным множеством состояний, устойчивого относительно изменения стратегии. Найдены условия устойчивости исследуемого процесса с рассматриваемыми целевыми функционалами. Методы исследования марковских процессов принятия, решений с конечным множеством состояний распространены на случай устойчивых процессов, множество.состояний которых счетно. Решен принципиальный вопрос о существовании и форме оптимальных правил обслуживания, доказана теорема существования оптимальной стационарной стратегии управления для устойчивых марковских процессов, а также оптимальность ее на множестве всех стратегий, включая нестационарные. Предложен и обоснован алгоритм определения £ -оптимальных стратегий, модифицирующий метод Ховарда в случае процесса со счетным множеством состояний.

На защиту выносится:

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. Предложен и обоснован алгоритм построения £ -оптимальных стратегий для устойчивого процесса путем сведения к управляемому марковскому процессу с конечным множеством состояний. Метод сходится на множестве значений функционала и на множестве стратегий.

1. Еиллингслей П. Эргодическая теория и информация. -М.: Мир, 1969.- 238 с.

2. Волковинский М.И., Кабалевский А.Н. Анализ многоуровневых приоритетных систем с подготовкой и перенастройкой обслуживающего прибора. Совместные распределения длин очередей. -Изв. АН СССР, Техн. киберн., 1978, №3, с. 209-214.

3. Гершт A.M., Марбух В.В. Один вариант задачи о переналадке.-Изв. АН СССР, Техн. киберн., 1975, Ю, с. 87-93.

4. Гершт A.M., Марбух В.В. Система массового обслуживания с переналадкой. Изв. АН СССР, Техн. киберн., 1975, №4,с. 74-82.

5. Веклеров Е.Б. Об оптимальных приоритетах в системах массового обслуживания. Автом-ка и телемех-ка, 1971, №6,с. 149-153.

6. Даниелян Э.А. Приоритетные задачи в системах обслуживания одним прибором. М.: ВЦ МГУ, Серия: стат. и стох. сист., вып. 13, 1971. - 68 с.

7. Даниелян Э.А., Димитров Б.Н. Обслуживание с изменяющимся приоритетом и "разогревом". Уч. зап. ЕрГУ, 1971, №1,с. 3-10.

8. Дмитриев М.У. Однолинейная система массового обслуживания с групповым обслуживанием в режиме разделения процессора. -Изв. АН СССР, Техн. киберн., 1979, №4, с. 102-105.

9. Духовный. И.М. Системы обслуживания с ненадежным прибором и обобщенными приоритетами. Изв. АН СССР, Техн. киберн., 1970, И, с. 73-79.

10. Духовный И.М. Об однолинейной системе обслуживания с чередованием приоритетов и "разогревом". Изв. АН СССР, Техн. киберн., 1969, №4, с. 66-74.

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

12. Дынкин Е.Б., Юшкевич А.А. Теоремы и задачи о процессах Маркова. М.: Наука, 1972. - 2 6 7 с.

13. Джейсуол Н. Очереди с приоритетами. М.: Мир, 1973.-279 с.

14. Кемени Д.Д., Снелл Д.Л. Конечные цепи Маркова. М.: Наука, 1970. - 271 с.

15. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979, - 432 с.

16. Клейнрок Л. Вычислительные системы, с очередями. M.s Наука, 1979. - 599 с.

17. Климов Г.П. Стохастические системы обслуживания. -М.: Наука, 1976. 243 с.

18. Климов Г.П., Мишкой Г.К. Приоритетные системы обслуживания .с ориентацией. - М.: МГУ, 1979. - 222 с.

19. Крейнин А.Я. Оценки среднего времени ожидания в однолинейной системе с переналадкой. Изв. АН СССР, Техн. киберн., 1980, №7, с. 97-101.

20. Майн X., Осаки С. Марковские процессы принятия решений. -М.: Наука, 1977. 175 с.

21. Малинковский Ю.В. Об оптимальной дисциплине обслуживанияв системе с динамическими приоритетами по времени ожидания.-Вестн. БГУ, сер.1 (мат., диз., мех.), 1978, №2, с. 23-29.

22. Марбух В.В. Об однолинейной системе массового обслуживания заявок,в системе с ограниченной очередью. Изв. АН СССР, Техн. киберн., 1980, №7, с. 97-101.

23. Мишкой Г.К. Система обслуживания с ориентацией и абсолютным приоритетом. Идентичное обслуживание заново прерванного вызова. Изв.АН СССР, Техн.киберн., 1974, №6, с. 95-103.

24. Мишкой Г.К. Обслуживание с ориентацией и двумя типами относительного приоритета. Изв. АН СССР, Техн. киберн., 1977, №4, с. II0-II4.

25. Мова В.В., Калиновский A.M. Оптимальная дисциплина обслуживания заявок в системе с ограниченной очередью. В кн.: Мат ем. сб. / Киев: Наук, думка, 1976. - с. 13 7-140.

26. Мова В.В., Пономаренко Л .А. Об оптимальном назначении приоритетов, зависящих от состояния обслуживающей системы с ограниченным числом мест для ожидания. Изв. АН СССР, Техн. киберн., 1974, №5, с. 64-68.

27. Назаров А.А. Нахождение оптимальной дисциплины обслуживания в системе с динамическими приоритетами. Изв. АН СССР, Техн. киберн., 1975, №4, с. 64-68.

28. Назаров А.А. Нахождение оптимальных динамических приоритетов. Изв. АН СССР, Техн. киберн., 1976, №3, с. I0I-I04.

29. Назаров Л.В. Система обслуживания с ориентацией. -Изв. АН СССР, Техн. киберн., 1981, №4, с. I3I-I35.

30. Назаров Л.В., Смирнов С.Н. Обслуживание вызовов, распределенных в пространстве. Изв. АН СССР, Техн. киберн., 1982, М, с. 95-99.

31. Проненко В.Д. Определение дисциплины обслуживания, максимизирующей производительность вычислительной системы.

32. M., 1976. 12 с. - Деп. в ВИНИТИ 27.10.76, № 3793-76.

33. Толмачев А.Л. Обслуживание нескольких потоков со случайными переключениями. Изв. АН СССР, Техн. киберн., 1979,5, с. 86-91.

34. Федоткин Н.А. Управление конфликтными потоками заявок при минимальной информации о состоянии системы с переменной структурой обслуживания. Изв. АН СССР, Техн. киберн., 1976, М, с. 65-71.

35. Феллер В. Введение в теорию вероятностей и ее приложения. Т. 2. М.: Мир, 1967. - 762 с.

36. Ховард Р.А. Динамическое программирование и марковские процессы. M.s Сов, радио, 1964. - 189 с.

37. Deman C. Oh qe^uantLad deeusCo^s and ТЛсИгои cfWnS.

38. X Wath.QnaC.QppC. ? 496:1,9,