автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Оптимизация систем массового обслуживания с конечными источниками требований

Введение.

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]. Но это — из области исключений.) с целевым функционалом предельного (по времени) типа, в силу чего классические методы управления случайными процессами почти неприменимы. Так, метод динамического программирования помогает — за редчайшими исключениями — лишь при управлении на конечном промежутке времени. (Например, при минимизации функционала

Ef(x"(t))dt. о

Здесь Е — знак математического ожидания, f — заданная функция, х11 — управляемый случайный процесс, и — управление. Да и то, надо сказать, получаемые на этом пути интегро-дифференциальные уравнения Беллмана очень редко поддаются эффективному исследованию. Подробнее см. [8 - 10].) Если же рассмотреть целевой функционал limijEf(xu(t))dt о кстати, именно такие функционалы фигурируют в настоящей работе), то метод динамического программирования практически бессилен: лишь в исключительных случаях удается решить «конечную» задачу при любом Т > 0 и " осуществить предельный переход при Т—»со. (См. по этому поводу [11], стр. 530.) Другой метод — неявное вычисление нужных статистических характеристик и последующее применение общих экстремальных принципов — как правило, не проходит из-за сложности возникающих уравнений. Поэтому приходится прибегать к специальным, часто оригинальным, методам; следствие — точные решения оптимизационных задач удается получить весьма редко. Но все же удается: см. [12-36].

Широко распространены методы приближенного решения (например, типа Монте-Карло: работа СМО моделируется на компьютере; «прогоняются» различные дисциплины обслуживания; выбирается лучшая). Число соответствующих работ огромно; некоторый обзор имеется в книгах [1-4].

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

Цели работы: решения задач оптимального (по некоторому естественному критерию, см. ниже) стационарного и программного управлений определенными СМО; исследование задачи позиционной оптимизации СМО; анализ качества полученных решений; исследования границ применимости полученных результатов.

Научная новизна. Все полученные результаты являются новыми; основные из них приведены в §2 Введения. Новым также является метод (невероятностного характера), примененный при анализе задачи позиционного управления: была поставлена и решена некоторая вариационная задача на бесконечномерном пространстве. (Задача решалась с существенным использованием специфики. Общая теория вариационного исчисления на бесконечномерных пространствах была впоследствии построена А.В. Углановым в работах [42-45]; одновременно выяснилось, что это исчисление вообще тесно связано с управлением случайными процессами).

Методы исследования. Теоретико-вероятностные, экстремальных задач и классического математического анализа. Результаты отрицательного характера главы 4 получены нестандартными построениями соответствующих контрпримеров.

Теоретическая и практическая значимость. 1.Точное решение задачи оптимального стационарного управления; в частности, доказательство равенств Ri=.Rk при этом управлении (теорема 1.1.2.; см. также замечание 1.3.3. к главе 1). 2. Точное решение задачи оптимального программного управления (и явное же выражение для целевой функции при таком управлении (теоремы 2.1.1., 4.2.3.)). 3. Эффективная оценка для целевой функции при любом управлении (теорема 3.1.4.). 4. Поучительные результаты отрицательного характера главы 4 (теоремы 4.1.2., 4.2.1., 4.3.1.). 5. Результаты теорем 1.1.2., 2.1.1., 4.2.3., 3.1.4. позволяют легко оптимизировать практически значимые СМО: оптимальное стационарное управление и соответствующее значение целевой функции найдены почти явно и вычисляются на компьютере стандартными подпрограммами; оптимальное программное управление найдено явно и не требует вообще никаких вычислений; теорема 3.1.4. обозначает ситуации, когда оптимальное позиционное управление и не нужно. 6. Выявленные зависимости качества (оптимальных) управлений от задаваемых параметров полезны при проектировании СМО.

Апробация работы. Результаты диссертации докладывались на Всероссийской конференции молодых ученых (Москва, МГУ, 17-21 апреля 2000 г.) и на Юбилейной научной конференции ЯрГУ (Ярославль, ЯрГУ, 20-21 ноября 2000 г.; два доклада).

Публикации. Основные результаты диссертации опубликованы в работах [46-51].

Структура работы. Диссертация состоит из введения, четырех глав и библиографии. Общий объем — 44 стр.