научная статья по теме ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ ОЧЕРЕДЬЮ В СИСТЕМЕ M|G|1|∞ ВОЗМОЖНОСТЬЮ ОГРАНИЧЕНИЯ ПРИЕМА ЗАЯВОК Автоматика. Вычислительная техника

Текст научной статьи на тему «ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ ОЧЕРЕДЬЮ В СИСТЕМЕ M|G|1|∞ ВОЗМОЖНОСТЬЮ ОГРАНИЧЕНИЯ ПРИЕМА ЗАЯВОК»

Автоматика и телемеханика, № 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 рублей.

Показать целиком