Автоматика и телемеханика, № 3, 2015
© 2015 г. Ю.Б. ГРИШУНИНА (juliagri@list.ru, grishunina@hse.ru) (Московский институт электроники и математики Национального исследовательского университета "Высшая школа экономики")
ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ ОЧЕРЕДЬЮ В СИСТЕМЕ М|С|1|то С ВОЗМОЖНОСТЬЮ ОГРАНИЧЕНИЯ ПРИЕМА ЗАЯВОК
Рассматривается задача оптимизации стратегии управления очередью в системе массового обслуживания Ы|С|1|то, где решение о продолжении или прекращении приема заявок принимается в моменты окончания обслуживания каждой заявки в соответствии с распределением на множестве решений, зависящим от числа заявок, оставшихся в системе. В качестве критерия эффективности выбран средний удельный доход в стационарном режиме, а множество допустимых стратегий управления совпадает с множеством однородных марковских рандомизированных стратегий. Доказано, что если оптимальная стратегия существует, то она является вырожденной и пороговой с одной точкой переключения управления, т.е. если число заявок в системе превышает некоторый уровень, то прием заявок следует прекратить, а если не превышает, то продолжить.
1. Введение
Оптимизация управления стохастическими системами в различных сферах экономики и социальной жизни является важным условием повышения эффективности их функционирования. Одним из основных методов решения задач управления является математическое моделирование; в частности, широко используется математический аппарат управляемых марковских и полумарковских случайных процессов с конечным или счетным множеством состояний [1]. При этом общая схема исследования включает следующие этапы:
• построение математической модели в виде управляемого случайного процесса;
• выбор критерия эффективности и постановка задачи оптимизации;
• вычисление критерия эффективности на основе характеристик введенного случайного процесса;
• исследование зависимости критерия эффективности от стратегии управления;
• выбор оптимального управления (решение задачи оптимизации).
В данной статье решается задача оптимизации управления для счетной полумарковской модели системы массового обслуживания М|С|1|го с возможностью ограничения приема заявок.
Рассматривается одноканальная система массового обслуживания с бесконечной очередью; входящий поток - простейший, интервалы между поступлениями требований в систему - независимые случайные величины, имеющие
экспоненциальное распределение с параметром Л: ^(ж) =
1 - е-Лх, ж > 0, 0, ж < 0;
длительности обслуживания требований тоже независимы и одинаково распределены: функция распределения длительности обслуживания одного требования С (ж) - произвольная; т = ж^С(ж) - математическое ожидание длительности обслуживания одного требования. Предполагается также, что в начальный момент времени в системе нет заявок.
Управление очередью осуществляется следующим образом: в момент окончания обслуживания очередного требования в системе проводится контроль числа требований, находящихся в очереди, и в зависимости от него принимается решение о продолжении или прекращении приема заявок в систему; если в момент окончания обслуживания очередного требования в системе осталось к требований, то с вероятностью Рк принимается решение о продолжении приема заявок в систему, а с вероятностью д^ = 1 — Рк прием заявок прекращается.
Выберем в качестве критерия эффективности функционирования системы средний удельный доход в единицу времени в стационарном режиме. Доход определяется следующими параметрами:
Со - доход, получаемый в единицу времени обслуживания одной заявки;
С1 - плата в единицу времени простоя системы;
С2 - плата в единицу времени за техническое обслуживание прибора;
Сз - плата в единицу времени ожидания одного требования в очереди;
с4 - штраф за потерю одного требования.
Цель исследования - нахождение оптимальной стратегии управления очередью в рассматриваемой системе.
Математической моделью данной системы массового обслуживания является управляемый однородный полумарковский процесс (£(£), и(£)) [1] со счетным пространством состояний, Е - множество состояний £(£), Е = = {0,1, 2,...}; и(£) € и = {0,1}, где 0 - решение о прекращении приема заявок, 1 - решение о продолжении приема заявок; £(£) = + 0), ¿п < £ ^ ^ £п+1, где п = 1, 2,..., - моменты окончания обслуживания заявок (марковские моменты), + 0) - число заявок в системе в момент окончания обслуживания п-й заявки; £(£) = 0, 0 ^ £ ^ ¿1.
Множество стратегий управления совпадает с множеством однородных марковских рандомизированных стратегий, т.е. решение в состоянии к выбирается в моменты ¿п + 0 (марковская стратегия) в соответствии с законом
висит от времени (однородная стратегия); и(£) = и(£п + 0), ¿п < £ ^ ¿п+1.
Аддитивный функционал дохода на траекториях описанного полумарковского процесса задается следующим образом: пусть Е^(ж,£, и), г, € Е, ж,£ € € (0, то), ж ^ ¿, и € и - числовая функция, условное математическое ожидание дохода, полученного в состоянии г за время ж при условии, что выбрано
2. Математическая модель
(рандомизированная стратегия) и не за-
решение и и процесс за время £ перейдет в состояние Е^(£, и) = Е^(£, и) -условное математическое ожидание полного дохода в состоянии г при условии, что выбрано решение и и процесс за время £ перейдет в состояние Обозначим через Ьп = ®т, п ^ 1, ¿о = 0, моменты изменения состоя-
ния процесса £(£) (марковские моменты, моменты окончания обслуживания заявок), вт = £т — £т-1, т ^ 1, - интервалы между последовательными изменениями состояния процесса £(£); V(¿) = тах{п ^ 0 : < ¿} - считающий процесс - число изменений состояния процесса £(£) в интервале (0; ¿); ^ = = £ — - время от последнего момента изменения состояния процесса в интервале (0; ¿) до момента ¿. Тогда условное математическое ожидание дохода на траектории описанного полумарковского процесса в интервале (0; ¿) имеет вид:
(Ео;?(41)М1,и(0)), V (£) = 0,
К*)-1
т=0
V(¿) ^ 1.
П(*) = <
Обозначим через £(£) = Еп(£) математическое ожидание дохода, полученного за время £ на траектории управляемого полумарковского процесса (£(£), «(£)). Тогда о; = Ит^оо^^ - средний удельный доход в единицу времени в стационарном режиме. Отметим, что если вложенная марковская цепь {£«, = С(£п), п ^ 0} эргодична и выполнены условия существования указанного предела, то средний удельный доход вычисляется по формуле:
те
Е Е3
\ 3=0
(1) « = —-,
Е Т3 П3 3=0
где числитель - это математическое ожидание дохода за один переход полумарковского процесса, знаменатель - математическое ожидание длительности этого перехода; Е3 - математическое ожидание полного дохода в состоянии Т3 - математическое ожидание длительности пребывания процесса в состоянии (п3- )3-ее - стационарное распределение вложенной марковской цепи [1, 2].
3. Задача оптимизации
Задача оптимального управления состоит в определении набора вероятностей {рк, к € Е}, при которых достигается максимум среднего удельного дохода на траекториях управляемого полумарковского процесса (£(£), и(£)) в стационарном режиме, т.е.
те
Е Ез п
3=0
(2) а = —--> тах
Е Т3 П3 3=0
{pfc, кеЕ}
4. Стационарное распределение вложенной марковской цепи
Обозначим через = /0°° е Хх(Ю(х) вероятность того, что за время обслуживания требования в систему пришло 3 требований.
Выпишем переходные вероятности вложенной марковской цепи (£п = п ^ 0}. Пусть в момент окончания обслуживания очеред-
ной заявки в системе осталось г ^ 1 заявок. Если принято решение не принимать заявки, то к моменту окончания обслуживания следующего требования в системе с вероятностью единица останется г — 1 требований; если прием требований продолжается, то в следующий марковский момент число заявок либо станет г — 1, если за время обслуживания не придет ни одной заявки, либо их будет г + 3 — 1, если придет 3 заявок. Если же в момент окончания обслуживания очередной заявки в системе не осталось заявок и принято решение не принимать заявки, то будем считать, что следующая пришедшая заявка обслуживается мгновенно и момент ее прихода совпадает с моментом окончания ее обслуживания, т.е. является марковским моментом; при этом вложенная цепь переходит в нулевое состояние. Если принимается решение о продолжении приема заявок, то на момент окончания обслуживания очередной заявки в системе либо не остается заявок, если за время обслуживания не пришло ни одного требования, либо, если придет 3 заявок, их станет 3. По формуле полной вероятности получаем, что переходные вероятности вложенной марковской цепи имеют вид:
'0, 3 < г — 1,
Рг/0 + 9г, 3 = г — 1, г ^ 1,
Рг? = < Ро/о + 9о, г = 0, 3 = г,
Р0/7, г = 0, 3 > г,
. Р/'-г+Ъ 3 ^ г, г ^ 1.
Утверждение 1. 1. Если р0 = 0, то стационарное распределение вложенной марковской цепи имеет вид: п0 = 1, п? = 0, 3 ^ 1;
2. Если р0 = 0 и коэффициент загрузки системы р = Лт < 1, то стационарное распределение вложенной марковской цепи существует и определяется рекуррентными соотношениями [3] :
П? = Р0Г,' П0, П0 =
1
(3)
те
1 + Р0 Е г? ?=1
Г1
(1 — /0)
1—Р1(1 — /0)'
— /? — Е ГгРг/?-г+1
_г=1_
1-^+1(1-/0)
3 > 1.
Доказательство. По определению из [4] стационарное распределение марковской цепи (п?является решением системы линейных уравнений: п? = ^пгрг?, ^пг = 1. Подставляя рг? в (3), получаем систему уравне-
ний для нахождения стационарного распределения:
' По = no(qo + po/o) + ni(qi + Pi/o),
П1 = ПоРо/i + niPi/i + П2 (q2 + P2/0), j
< nj = noPofj + E niPi/j-i+i + nj+i(qj+i + Pj+i/o), j ^ 2, i=i
E ni = 1.
i&E
Очевидно, что если po = 0, то независимо от остальных pj стационарное распределение вложенной цепи существует и имеет вид: по = 1, nj = 0, j ^ 1.
Рассмотрим случай po = 0. Для решения системы воспользуемся методом производящих функций [5]. Обозначим через n(z) = Ej=0 njzj производящую функцию стационарного распределения; f (z) = j=o fjzj ; np(z) = = Ej=0 nj Pj zj. Умножая j-е уравнение системы на zj и суммируя по j, получаем выражение для производящей функции:
7t(z) = 7Го(1 " P0(l ~ f(z))) ~zMz)(f(z) " 1) +
Отсюда
z — 1
Из условия нормировки находим no:
TT(l) = 1 = 7Г0 + lim = ^ + 7Гр(1)//(1).
z^i Z —
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.