Оптимизация систем массового обслуживания с конечными источниками требований

• Автор: Филатова, Людмила Юрьевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Ярославль
• Количество страниц: 44 с.

Оглавление.
Введение

1. Общая характеристика работы

2. Краткое содержание диссертации

3. Замечания и комментарии,

Глава 1, Стационарное управление

1.1. Оптимальное стационарное управление

1.2. Качество управления при различных параметрах СМО.

1.3.Замечания и комментарии

Глава 2. Программное управление

2.1. Оптимальное программное управление

2.2. Замечания и комментарии
Глава 3. Позиционное управление..
3.1. Оптимальное позиционное управление
3.2. Замечания и комментарии
Глава 4. Обобщения и уточнения
4.1. К стационарному управлению
4.2. К программному управлению
4.3. К позиционному управлению
Список литературы
Введение.
1. Общая характеристика работы
Актуальность темы и состояние проблемы. Оптимальная (по каким-то естественным критериям) организация и эксплуатация систем массового обслуживания (СМО) составляет класс практически важных задач, постоянно возникающих при управлении различными производственными процессами (см, например, [1 - 6] и библиографию к этим работам). Являясь частью раздела теории вероятностей — управления случайными процессами, оптимизация СМО выделилась в относительно самостоятельную область исследований.
Однако, к сожалению, достижения в этой области пока что относительно скромные. Одно из объяснений тому — часто рассматривается установившийся режим СМО (что совершенно естественно. Рассматривались, правда, и СМО, для которых само понятие установившегося режима лишено смысла: см., например, [7]. Но это — из области исключений.) с целевым функционалом предельного (по времени) типа, в силу чего классические методы управления случайными процессами почти неприменимы. Так, метод динамического программирования помогает — за редчайшими исключениями — лишь при управлении на конечном промежутке времени. (Например, при минимизации функционала
{Ег(х“(ф)л.

Здесь Е — знак математического ожидания, f — заданная функция, хи — управляемый случайный процесс, и — управление. Да и то, надо сказать, получаемые на этом пути интегро-дифференциальные уравнения Веллмана очень редко поддаются эффективному исследованию. Подробнее см. [8 - 10].) Если же рассмотреть целевой функционал

(кстати, именно такие функционалы фигурируют в настоящей работе), то метод динамического программирования практически бессилен: лишь в
исключительных случаях удается решить «конечную» задачу при любом Т > 0 и осуществить предельный переход при Т-»С0. (См. по этому поводу [11], стр. 530.) Другой метод — неявное вычисление нужных статистических характеристик и последующее применение общих экстремальных принципов — как правило, не проходит из-за сложности возникающих уравнений. Поэтому приходится прибегать к специальным, часто оригинальным, методам; следствие — точные решения оптимизационных задач удается получить весьма редко. Но все же удается: см. [12-36].
Широко распространены методы приближенного решения (например, типа Монте-Карло: работа СМО моделируется на компьютере; «прогоняются» различные дисциплины обслуживания; выбирается лучшая). Число соответствующих работ огромно; некоторый обзор имеется в книгах [1-4].

Что касается СМО с конечными источниками требований, то задачи их оптимизации почти совсем не исследовались; кроме собственных, автору известны лишь пять соответствующих публикаций: [37-41]. Но в [37, 38] решалась задача минимизации общей (т.е. суммируемой по всем потокам: см. ниже) длины очереди. Найденные оптимальные управления оказались таковы, что при определенных значениях параметров задачи некоторые потоки практически вовсе не будут обслуживаться; ясно, что подчас такое управление неприемлемо. Свободная от указанного недостатка (существенно более нелинейная) задача равномерной минимизации, которая и исследуется в диссертации, впервые была рассмотрена в [39]. Но [39] (как и [40, 41]) — краткие публикации, в которых лишь анонсируются (да и то подчас нечетко) некоторые результаты. Между тем оговариваемые задачи — практически важные: они возникают при
проектировании и эксплуатации различных систем технического обслуживания, централизованной обработке набора информационных потоков (подробнее см. [37]), поддержании в надлежащем состоянии группы сложных разбросанных объектов. Вот один пример последнего типа. Есть к пунктов (например, городов). В i-ом пункте расположено п; единиц некоторого оборудования; каждая единица выходит из строя (независимо от других) через некоторое случайное время. В центре обслуживания расположены 1 ремонтных бригад; время поездки бригады в i-й пункт есть t;, время возвращения в центр — Sj. При поездке в какой-либо пункт бригада восстанавливает все вышедшие из строя единицы оборудования, возвращается в центр, после чего снова готова к работе. Теперь естественным образом возникают задачи оптимального (по какому-то критерию) порядка обслуживания (поездок).
Цели работы: решения задач оптимального (по некоторому естественному критерию, см. ниже) стационарного и программного управлений определенными СМО; исследование задачи позиционной оптимизации СМО; анализ качества полученных решений; исследования границ применимости полученных результатов.
Научная новизна. Все полученные результаты являются новыми; основные из них приведены в §2 Введения. Новым также является метод (невероятностного характера), примененный при анализе задачи позиционного управления: была поставлена и решена некоторая вариационная задача на бесконечномерном пространстве. (Задача решалась с существенным использованием специфики. Общая теория вариационного исчисления на бесконечномерных пространствах была впоследствии построена A.B. Углановым в работах [42-45]; одновременно выяснилось, что это исчисление вообще тесно связано с управлением случайными процессами).
Методы исследования. Теоретико-вероятностные, экстремальных задач и классического математического анализа. Результаты отрицательного характера главы 4 получены нестандартными построениями соответствующих контрпримеров.

где у = 1-е “. Хотя для дальнейшего это неважно, все же отметим, что перед радикалом следует брать знак «—», ибо в противном случае р>1.
Из (53) и классических формул (1-х)-1 =1 + х + о(х), л/Гкх = 1 + j + о(х) получаем р = 1 - л/еу-1 + o(Vs). Подставим это значение р в (51) (или (52)); тогда
п Г, /„ч + ^ + +
^1Ф/ “* 2 Ф/ — / - , _л 7= 7=7 I--- р ?
Х[1 — -y/sy е s +o(Vs)][l-y/£y' +s7ey +o(Vs)]
откуда
lim R, (p) = lim R j (p) = 0. (54)
e-»0 E—>
С другой стороны, взяв в (51), (52) р = - получаем
lim R, Г—1 =-------У- ,
«о (2 J A.(l + y)(l + s)
limR2f—1 = —-—. (55)
«о 2) X(l+s) v ’
Из (54) и (55) следует, что при достаточно малом в rQJ > R(p), т.е. управление (р,1-р) не является оптимальным. Теорема доказана.
4.2. К программному управлению.
Теорема 2.1.1. (глава 2) гласит, что оптимальным программным управлением является такое управление, при котором приборы включаются через равные промежутки времени и последовательно обслуживают все потоки требований. Однако теорема доказана для ситуации, когда время переориентации каждого прибора с i-ro на m-й поток равнялось Si+tm (см. введение). Обобщим ситуацию: пусть указанное время равняется т,т; во всем остальном СМО функционирует по прежним правилам (в момент т" j-й прибор ориентируется на
какой-угодно поток — это не имеет значения; моментом готовности прибора к работе считается момент окончания очередного акта обслуживания). В свете теоремы 2.1.1. представлялась естественной гипотеза, что (в измененной ситуации) оптимальным управлением будет следующее: г’ =(j-l)s/l; j-й прибор последовательно ориентируется на ПОТОКИ С номерами ibi2,...ik,ibi2vikv) гДе ibi2,...ibii есть замкнутый маршрут коммивояжера с матрицей {т|1П }, s — длина маршрута. Однако гипотеза оказалась неверна. Сейчас мы построим контрпример для 1=1, к=4 (при к<4 такой пример невозможен).