Спросить
Войти
УДК 519.872
ГоловинА людмила Юрьевна, кандидат физико-математических наук, доцент кафедры математики Института математики и компьютерных наук Северного (Арктического) федерального университета имени М.В. Ломоносова. Автор 14 научных публикаций, в т. ч. 5 учебно-методических пособий
анализ качества стационарного управления системами массового обслуживания
В статье рассматривается система массового обслуживания с конечными источниками требований. Приведены результаты поиска оптимального стационарного управления системой, полученные в предыдущей работе. Сформулировано и доказано как изменяется качество управления при равновероятностном подходе к обслуживанию составляющих системы.
Оптимальная (по каким-то естественным критериям) организация и эксплуатация систем массового обслуживания (СМО) составляет класс практически важных задач, постоянно возникающих при управлении различными производственными процессами. Являясь частью раздела теории вероятностей -управления случайными процессами, оптимизация СМО выделилась в относительно самостоятельную область исследований.
Зачастую рассматривается установившейся режим СМО с целевым функционалом предельного (по времени) типа, в силу чего классические методы управления случайными процессами почти неприменимы. Так, метод динамического программирования помогает -за редчайшими исключениями - лишь при управлении на конечном промежутке времени.
Что касается СМО с конечными источниками требований, то задачи их оптимизации исследованы мало, особенно задача равномерной минимизации, которая рассматривается в данной работе. Между тем оговариваемые задачи - практически важные: они возникают при проектировании и эксплуатации различных систем технического обслуживания, централизованной обработке набора информационных потоков, поддержании в надлежащем состоянии группы сложных разбросанных объектов. Вот один пример последнего типа. Есть к пунктов (например, городов). В /-ом пункте расположено п. единиц некоторого оборудования; каждая единица выходит из строя (независимо от других) через некоторое случайное время. В центре обслуживания расположены I ремонтных бригад; время поездки бригады в /-й пункт есть
© Головина Л.Ю., 2012
ґ, время возвращения в центр - s .. При поездке в какой-либо пункт бригада восстанавливает все вышедшие из строя единицы оборудования, возвращается в центр, после чего снова готова к работе. Теперь естественным образом возникают задачи оптимального (по какому-то критерию) порядка обслуживания (поездок).
Рассматривается система ЫкЮк/1/(п1,..., п) На обслуживающий прибор поступаю к > 2 независимых потоков требований, причем і-й поток формируется конечным источником объема п так, что каждое требование поступает (независимо от других) после пребывания в источнике случайное время с функцией распределения 1 - в~Хх(Х > 0). Ориентированный на і-й поток прибор «разогревается» случайное время ґ затем мгновенно обслуживает (т. е. возвращает в -й источник) все требования, затем «остывает» случайное время s , после чего снова готов к работе (т. е. к ориентации на тот или иной поток). Считается, что ґ + s . > 0 для всех і = 1,..., к. Положим х = х(ґ) = {х .(ґ)} (і = 1,..., к; ґ є [0; да)), где х(ґ) = 1 - п - • у (г), где у(ґ) есть число требований і-го потока в момент ґ (хг(ґ) есть мгновенный коэффициент готовности і-го источника). Управлением (стохастическим стационарным) назовем вектор {рД, где і =1,...к;
р >0; =1.
Управление определяет дисциплину обслуживания требований: прибор включается в момент т0 = 0 и действует непрерывно; если тп(п = 0,1,.) есть п-й по счету момент готовности прибора, то он (прибор) ориентируется на -й поток с вероятностью р . Уточним, что конкретная ориентация осуществляется вероятностным диспетчером, в который поступает лишь вектор {р }, «внутренняя» же работа диспетчера не зависит ни от тп, ни от х, ни от работы диспетчера в прошлом. Обозначим через и множество всех управлений. Далее для определенности считаем, что х(0)={1,...,1} (это предположение несущественно). Для и є и положим
Яі=Я(и) = Ііт — | Ехі (Ї)Ж, Я=тіп ,
Г^т Г 0 И іі к
где Е - знак математического ожидания; Я. - коэффициент готовности /-го источника; Я - равномерный коэффициент готовности системы.
В работе [1] была рассмотрена задача поиска оптимального управления и0 е и такого,
что Я(и0) = яирЩи). Используются обозначения: т, = ^ + я,, аг = Ххг, а = 2а, Р,- = е &.
Было доказано следующее утверждение:
лемма 1. Справедливы следующие неравенства:
______і=1_________ г т
і=1, і Ф т
где а = 2 Рг а,.
Теорема 1.
Оптимальное стационарное управление существует, единственно и дается формулами
где г - единственное на интервале (1; да) решение уравнения
к 1 - в
е—вг=і у =
г =1 г - в і
При этом
= Я(ы0) = Ж щ) =... = Як (и0) =
к а г
г х в"
г=1 Р г
Также в работе [1] было доказано, что при оптимальном управлении на более широком классе управлений
К0е = Я(ы0) = Я1(и0) = ... = Як К) =
При этом прибор последовательно обслуживает все потоки требований.
В свете последнего утверждения интересен анализ стационарного управления р =... = рк = 1; обозначим через Яу = Яу(а1,...,ак)
соответствующий коэффициент готовности системы. Заметим, что функция Яу определена и непрерывна на компактном множестве а. > 0,
£ аі = а> 0 (см. (1)).
Теорема 2. Решения экстремальных задач Я ^тах, R ^тіп
мулами
а і > 0, £аі = а
даются форУ
Таким образом, задача (2) эквивалентна задаче
к -^ к
--------к-----------> тіп, а1 -аі < 0(і = 2,..., к),
к -їе-аі к
і=2 ^аі -а = 0.
Зафиксируем а1 и решим сначала следующую подзадачу задачи (3)
к к -аі
і=2 і=2
а =... = а*ч = о, а к = а, ^ ■
Решение первой задачи единственно; решение второй задачи единственно с точностью до перестановок (а1,..., ак).
Доказательство. Рассмотрим задачу
Яг ^ тах, а, > 0, X а, = а .
По формуле (1) имеем (р = ... = рк = —)
а, = тіп а т . Тогда
Я = 1 —
к -^ е~
Рассмотрим вспомогательную случайную
величину £ такую, что Р{Ъ, = а1} = ——- (/ =
= 2,...,к). Тогда для /(£) = е £ верно Р(/(£) =
/(а.)} = —1— (/ = 2,...,к). Поскольку е-х является ! к -1
выпуклой функцией, то Ее~£ > еЕ£. Отсюда
к 1 -2“<^ 1 *
у е-аі ------> е і=2 к-і ----------у е-аі > е
і=2 к -1 к -1 і=2
У е~аі > (к - 1)е
Далее найдем Я = тт Ят . Нетрудно заме1< т< к
тить, что Ят минимально при минимальном а (т =1,...,к). Пусть для определенности
Таким образом, мы нашли решение задачи
а - а 1
(4): аі = ——і" (і = 2,.,к). Далее положим а1 = х, а1 =у(і = 2,.,к). Задача (3) примет вид
х->-X
-> тіп, х + (к -1)у = а, 0 < х < у,
к - (к - 1)е
что аналогично задаче
-а+(к-1) у
к - (к - 1)є
> тт, — < у <--------.
к к -1
аі=1=2
Простой анализ последней задачи показывает, что на рассматриваемом отрезке целевая функция монотонно возрастает, а следовательа
но, достигает своего минимума при у = — .
Таким образом, решением задачи (2) являются а
числа а1=...= ак = у, что и утверждает теорема. Теперь равенство
получается при подстановке в (1) Рі а
а = к (і = 1,.,к).
Далее рассмотрим задачу
Я ^ тіп, а1 > 0, 2аі = а.
Пусть а1 = тіп аг-, тогда
І = 2 к
Ь =|>-а + £Хіаі +ЦХа-а I;
где X, Х.еЯ1 - множители Лагранжа, причем
дЬ а. .
X< 0. Для а. Ф0, / = 2,., к получим д^_-е ‘
Необходимое условие экстремума: _______= о отсюда все а. Ф 0 должны быть равны между собой. Пусть к1 - количество равных нулю а., тогда (к — к1—1) - количество а. отличных от нуля, =1 и тогда для а. Ф 0 имеем а. =------------—. Отсюда
и из (7) получим
к - к -1
К =1-----------*------•
к -^ а 1
(см. начало доказательства теоремы 2). Теперь задача (5) эквивалентна задаче
-----;---------> тах, а, - а, < 0,
к ’ 1 г ’
к -£е-а г
’= 2 к
а, > 0(, = 1,...,к), £ а, =а. (6)
Зафиксируем а1 > 0 и рассмотрим подзадачу
к1 + (к - к1 - 1)ек к 1 ^ тах, 1 < к1 < к - 2.
Для удобства обозначим х = к — к1 — 1, тогда получим задачу
/(х) = к -1 - х + хе х ^ тах, 1 < х < к - 2. Решим ее
— а -а,
X_________1
/&(х) = -1 + е
Легко проверить, что на указанном отрезке Ах) < 0, т. е. /(х) убывает и максимум достигается при х = 1, а значит, к= к — 2. Отсюда и из того, что а1 = тт а, следует, что решение задачи (5) есть а1 = ”... = ак1 = 0, ак = а (с точность до перестановок (а1,..., ак)), что и утверждает теорема. Яу найдем, подставив в (1) найденное решение и р, =— (г = 1,., к)
Теорема доказана.
К - (к - 1) - 8
= 1 -1 1 -82-8- а 2-8Она является расширенной по отношению к (6), где а. > а1 (. = 2,., к), а значит, искомое решение не меньше решения задачи (6). Составим функцию Лагранжа задачи (7).
Результаты теоремы приводят к следующим заключениям: наибольшая эффективность работы равномерного вероятностного диспетчера
(р = ... = рк) достигается при условии равенства сильно перекошенных значениях параметров параметров а1(а1 = ... = ак), и наименьшая при а.(а1 = ... = ак-1= 0, ак= а).
Список литературы
Golovina Liudmila Yuryevna
Northern (Arctic) Federal University named after M.V Lomonosov, Institute of Mathematics and Computer Sciences
QUALITY ANALYSIS OF THE STATIONARY ORGANIZATION OF QUEUEING SYSTEMS
The queueing system with finite sources of requirements is considered in the article. The results of the search for optimal stationary system organization, acquired in the previous work, are presented. It is formulated and proved how the quality of organization changes at the equal probability approach to the service of the system components.
Контактная информация: e-mail: foxmill@rambler.ru
Рецензент - Попов В.Н., доктор физико-математических наук, доцент, заведующий кафедрой математики Института математики и компьютерных наук Северного (Арктического) федерального университета имени М.В. Ломоносова
