Система Mk/G/1 C инверсионной вероятностной дисципилиной обслуживания тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.ЛОМОНОСОВА

Механико-математический факультет

На правах рукописи УДК 519.872

ПЕЧИНКИНА Ольга Александровна

СИСТЕМА Мк/С/1 С ИНВЕРСИОННОЙ ВЕРОЯТНОСТНОЙ ДИСЦИПЛИНОЙ ОБСЛУЖИВАНИЯ

01.01.05—Теория вероятностей и математическая статистика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва, 1996

Работа выполнена на кафедре теории вероятностей механико-математического факультета Московского государственного университета им. М.В.Ломоносова.

Научный руководитель—

доктор физико-математических наук, профессор А.Д.Соловьев.

Официальные оппоненты:

в 16 час. 05 мин. на заседании диссертационного совета Д.053.05.04 при Московском государственном университете им. М.В.Ломоносова по адресу:

119899, ГСП, Москва, Воробьевы горы, МГУ, механико-математический факультет, аудитория 16-24.

С диссертацией молено ознакомиться в библиотеке механико-математического факультета МГУ (14 этаж, Главное здание).

доктор физико-математических наук, профессор В.В.Рыков; доктор физико-математических наук, В.Г.Ушаков.

Ведущая организация—

Московский государственный институт электроники и математики (технический университет).

Защита диссертации состоится

1996 г.

Автореферат разослан

1996 г.

Ученый секретарь диссертационного совета Д.053.05.04 доктор физ.-мат. наук, профессор

Т.П.Лукашенко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Уже давно в теории массового обслуживания было замечено, что применение в системах массового обслуживания специальных дисциплин обслуживания, использующих дополнительную информацию о типах находящихся в системе требований или о работе, которая уже совершена или которую осталось совершить для обслуживания этих требований, позволяет в ряде случаев существенно улучшить показатели производительности систем.

Очень большое число работ посвящено приоритетным системам обслуживания, в которых улучшение качества обслуживания одних групп требований происходит за счет предоставления требованиям этих групп преимущественного права обслуживания. Однако исследования в этом направлении, несмотря на их многочисленность, не затрагивали таких систем, в которых используется более подробная информация о длинах находящихся в системе требований (т.е. о совершенной и остаточной работе для каждого требования), и поэтому анализ приоритетных систем производился более или менее традиционными методами.

К специальным дисциплинам обслуживания относятся: инверсионный порядок обслуживания; дисциплина равномерного разделения прибора; дисциплина случайного выбора из очереди; дисциплина преимущественного разделения прибора требованиями минимальной обслуженной длины; циклическая дисциплина обслуживания и т.д. Эти дисциплины давно уже используются в вычислительных системах и сетях и многих других технических устройствах. Однако для большинства из них аналитические выражения для характеристик обслуживания были получены лишь совсем недавно.

Можно привести еще много других примеров специальных дисциплин обслуживания. Однако мы не будем останавливаться на полном перечислении работ в этом направлении, а обратим внимание только на то, что, как показал опыт, для анализа почти каждой системы со специальной дисциплиной обслуживания приходится разрабатывать свои принципиально новые методы исследования.

Возникает вопрос: а нет ли среди специальных дисциплин такой, которая, допустим, для обычной однолинейной системы обслуживания минимизировала бы основные показатели обслуживания, в частности, длину очереди? Оказывается, такая днециплнна есть. Эта

дисциплина (дисциплина SRPT), введенная Л.Шраге и Л.Миллером, заключается в следующем: в любой момент времени нужно обслуживать то требование, остаточная длина которого минимальна. Оптимальность этой дисциплины в указанном смысле была показана Л.Шраге, В.В.Козловым и А.Д.Соловьевым и др., а различные показатели обслуживания для системы M/G/1/oo с дисциплиной SRPT найдены в работах Р.Шассбергера, С.А.Гришечкина и др.

В работах В.А.Нагоненко исследовалась система M/G/1/n с несколько более простой, но также обладающей хорошими оптимизационными свойствами дисциплиной—инверсионным порядком обслуживания с вероятностным приоритетом. При этой дисциплине сравнивались и разыгрывали между собой место на приборе н первое место в очереди только два требования: обслуживаемое требование и требование, поступающее в систему. Там был применен метод, основанный на случайной замене времени. Этот метод также активно используется в настоящей диссертации.

Однако и дисциплина SRPT, и инверсионный порядок обслуживания с вероятностным приоритетом с точки зрения практики обладают одним существенным недостатком: для их использования необходимо знать остаточную длину каждого находящегося в системе требования, что во многих случаях просто невозможно. Поэтому в настоящей работе вводится другая дисциплина—инверсионная вероятностная дисциплина обслуживания—и исследуется система Mi/G/1/n с такой дисциплиной.

Цель работы. Всесторонний анализ системы M^/G/l/n с инверсионной вероятностной дисциплиной обслуживания.

Методика исследования. При исследовании применяются результаты теории случайных процессов, теории восстановления, теории дифференциальных уравнений, теории оптимального управления.

Научная новизна и практическая ценность. Работа носит, в основном, теоретический характер. Все результаты, полученные в диссертации являются новыми. К ним относятся:

1. Введена инверсионная вероятностная дисциплина обслуживания (дисциплина LIFO Р).

2. Найдены стационарные характеристики длины очереди для системы Mfc/G/1/n с такой дисциплиной.

3. Изучено предельное поведение распределения длины очереди

в системе M/G/1/n" с "дисциплиной LIFO Р в условиях большой загрузки.

4. В системе M^/G/l/n с дисциплиной LIFO Р найдены стационарные распределения характеристик, связанных с временем пребывания требования в системе.

5. В системе M/G/1/oo с дисциплиной LIFO Р найдено совместное нестационарное распределение основных характеристик обслуживания.

G. Решена задача оптимизации линейного функционала, связанного с поведением системы M^/G/l/n на одном периоде занятости.

Апробация работы. Результаты диссертации докладывались

на:

XI Зимнем белорусском симпозиуме по теории массового обслуживания (Минск, 1995 г.);

XXX научной конференции факультета физико-математических

н естественных наук Российского университета дружбы народов (Москва, 1994 г.);

XXXI научной конференции факультета физико-математических и естественных наук Российского университета дружбы народов (Москва, 1995 г.);

семинаре "Вероятностные методы в технике (руководители: академик Украины Б.В.Гнеденко, профессор А.Д.Соловьев, профессор Ю.К.Беляев),

Публикации. Основные результаты диссертации опубликованы в 5 работах автора, список которых приведен в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, 5 глав и списка цитированной литературы. Работа изложена на 90 страницах. Список литературы содержит 41 наименование.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обсуждается постановка задачи и приводится аннотация полученных в диссертации результатов.

Рассмотрим систему Mfc/G/1/n (0 < п < оо), в которую поступает пуассоновский второго рода поток требований с интенсивностью А,-, зависящей от числа г находящихся в системе требований. Время обслуживания каждого требования распределено по произ-

вольному закону В(х) со средним значением b = /[1 — B(x)]dx < оо.

о

В дальнейшем для сокращения записи будем использовать обозначение В{х) = 1-В(х).

Инверсионная вероятностная дисциплина обслуживания (LIFO Р) заключается в следующем. Будем предполагать, что в любой момент времени известны (обслуженные) длины всех требований, находящихся в системе, в частности, длина х требования, находящегося на приборе. Тогда, если в этот момент в систему поступает требование, то оно с вероятностью ¿¿(ж), зависящей только от числа г находящихся в системе требований и длины х обслуживаемого на приборе требования, само становится на прибор, вытесняя обслуживавшееся ранее требование длины х на первое место в очередь, и с дополнительной вероятностью ¿,(х) = 1 — <5; (i) не прерывает обслуживания, но занимает первое место в очереди. Здесь 5{(х)— измеримая функция, 0 < 6{(х) < 1. Недо о б служенные требования дообслуживаются. Если число мест ожидания конечно (п < оо), то требование, поступившее в полностью занятую систему, с вероятностью 5n+i(x) теряется, а с вероятностью Jn+x(a;) = 1 — ¿п+1(а;) становится на прибор, вытесняя обслуживавшееся ранее требование длины х из системы.

В первой главе определяется стационарное распределение длины очереди в системе Mfc/G/1/n с дисциплиной LIFO Р. При этом используется метод случайной замены времени, с помощью которого показывается, что стационарное распределение длины очереди в системе Mfc/G/1/n с дисциплиной LIFO Р с точностью до постоянной не зависит от числа мест ожидания п.

Обозначим через ро стационарную вероятность отсутствия требований в системе, а через P, (xi,..., Xi) (1 < i < тг + 1)—стационарную вероятность того, что в системе имеется i требований, причем на приборе находится требование обслуженной длины меньше хь на первом месте в очереди—требование обслуженной длины меньше х2 на втором месте в очереди—требование обслуженной длины меньше хз и т.д. Основной результат первой главы содержится в следующей теореме.

Теорема 1.1. Стационарные вероятности состояний в системе Mfc/G/1/n с дисциплиной LIFO Р определяется с помощью формулы

Pi{xi, . . . , Xi) = — Р,(х 1, . . . , Xi) =

_ -Л, f - ---------

= 7?0ö(x1)e 0 ri(x1,...,xi),

где r,-(.Ti,..., x^) задаются рекуррентными формулами

Ti = A0 1 — Ai I ii(.r) Q'i(x) dx

-l

Xl

/О' i 7 )

¿i-i(y) ~~TT~ ri-i(У> хз, • ■ • i xi) dy, "¿(У)

12

гг(0,х2,... ,Xi) = [a,-_X J 5i^i(y)ai-i{y)ri^i(y,x3,...,xi)dy+

+A,A[ 5i(y) a,(y) f 6i-i{z) a' r,x3l.. .,x dz dy I x

x 1 - A; / <5,(гу) a,(y)dy

ai{x) = B(x)e °

Если входящий в систему поток является пуассоновскпм, т.е. Аг- = А, а вероятности ¿¡(х) постановки требования на приг ->р не зависят от числа i требований, находящихся в системе, т.е. <5;(.т) = = 5(х), то стационарное распределения pi(x) = ^ Р,(х, оо,..., схз) и pi = Р,- (co,..., оо) числа требований в системе можно выразить

оо

в терминах производящих функций (ПФ) P(z,x) = z'Pi{x) 11

i = i

оо

P{z) = £ z'Pi. 1=0

Теорема 1.2. В системах M/G/1/oo и M/G/1/n с дисциплиной LIFO Р ПФ P(z, ж) и P(z) задаются формулами

_ -А(1-2) / 6(у) dy

Р(г,.т) = Xzp0B(x)e о х

-A(l-z)j6(u)du ,

x{l-\jB(y)[l-(l-z)5(y))e о dy"j

о

и

оо

P{z)=p0\l + \z J Щх)

-A(l-z)JS(y)dy

[ \ е 0 dxx

о

х

°f_ —А(1 —г) J 6(у) dy _г

x(l-\ B(x)[l-(l-z)6(x)]e о dl) },

О

причем для системы M/G/1/oo рц = 1 — р, а для системы M/G/1/n

N

ро определяется из условия нормировки Yh Pi = 1-

¿=0

В качестве примеров полученных результатов выводятся хорошо известные формулы для распределений длин очередей в системах M/G/1/n с инверсионным порядком обслуживания и с прерыванием и без прерывания обслуживания.

Во второй главе изучается предельное поведение стационарного распределения длины очереди в системе M/G/1/n с дисциплиной LIFO Р в условиях большой загрузки. Для удобства изложения всюду во второй главе предполагается, что интенсивность входящего потока Л = 1.

Рассматриваются случаи докритической (р < 1), критической (р = 1) и надкритической (р > 1) загрузок. При этом в случае докритической загрузки асимптотическое поведение длины очереди изучается при р —» 1, а в случаях критической и надкритической загрузок—при п —> оо. Метод исследования основан на анализе полученной в первой главе явной формулы для ПФ стационарного распределения числа требований в системе, поскольку применение общих принципов асимптотического анализа встречает серьезные трудности из-за рассматриваемой дисциплины обслуживания.

Пусть имеется последовательность систем M/G/1/оэ с дисциплиной LIFO Р, причем время обслуживания требования в n-й системе имеет функцию распределения Вп(х), а вероятность постановки требования на обслуживание для нее равна 5п(х). Обозначим

через рп J Вп(х) dx загрузку n-й системы.--Положим

о

оо

ь:(х) = J~Bn(y)dy,

X

со у

bn(x) = J вп{у) J sn(u) dudy,

ап = / BJx

5п(х) + / 5n{y)dy

dx.

о о

Обозначим через 1/„ случайную величину, распределенную по тому же самому закону, что и число требований в п-й системе М/С/1/оо, функционирующей в стационарном режиме.

Теорема 2.1. Пусть выполнены условия:

1- рп Т 1;

2. Ь*„(х) —> 0 равномерно по п;

т—Ьоо

3. Ь** (х) —> 0 равномерно по п.

Т—УОо

Тогда,

ГЛ ■ ' .

Пусть теперь мы имеем последовательность систем M/G/1/n с конечными числами мест ожидания, причем число мест ожидания в n-й системе равно mn. Обозначим через v*n случайную величину, распределенную так же, как и число требований в функционирующей в стационарном режиме n-й системе. Из теоремы 2.1 выводится следующее

Следствие. Пусть для последовательности систем с конечным. числом, тп мест ожидания, выполнены условия 1-3 теоремы 2.1 и, кроме того,

4- (1 - Рп)тп/ап —> X.

п-+оо

Тогда

р 0<*<Х;

Q'n [ 1, х > X.

о

В следующих двух теоремах предполагается, что имеется последовательность систем M/G/1/n с конечными числами мест ожидания, причем число мест ожидания в п-й системе равно п. Обозначим через vn случайную величину, распределенную так же, как и число требований в функционирующей в стационарном режиме п-й системе.

Теорема 2.2. Пусть 1. ft (1 Рп) —> О

п—юо

и, кроме того, выполнены условия 2 и 3 теоремы 2.1. Тогда

<*} ад,

1П + 1 1 n-»oo V '

где R(x)—функция равномерного на отрезке [0,1] распределения.

Теорема 2.3. Пусть

1. рп —> р> 1 п-+оо

и выполнено условие 2 теоремы 2.1. Тогда

PK = n +1 -«} - (1 - 40))(40))'' —»■ о,

п—юо

где через z^ обозначен (единственный) корень уравнения dn(z) = 1, а

х

_ -(1-0/My)dy

dn(z)= I Bn{x)[l-(l-z)6n{x)]e ° dx.

о

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

В третьей главе найдены распределение периода занятости, стационарные распределения времени ожидания начала обслуживания и времени пребывания требования в системе M^/G/1/n с дисциплиной LIFO Р и некоторые другие связанные с ними характеристики этой системы.

Для того чтобы найти распределение периода занятости системы Mfc/G/1/n с дисциплиной LIFO Р, наряду с основной описанной системой вводится в рассмотрение ¿-система (0 < i < п + 1). /-система представляет собой систему Mt/G/1/n-i с п - г местами

ожидания, подобную исходной системе за исключением того, что для г-системы интенсивности А). определяются равенствами А). = Л^_,, а вероятности (х)—равенствами — х).

Очевидно, что ¿-система представляет собой исходную систему, в которой постоянно находится г требований, причем эти требования занимают места ожидания, но никогда не обслуживаются. Ясно также, что 0-система совпадает с исходной системой.

Для определенности предполагается, что если число п мест ожидания конечно, то поступающее в п + 1-систему требование немедленно покидает ее необслуженным.

Обозначим через ^(в) преобразование Лапласа-Стнлтьеса (ПЛС) периода занятости ¿-системы, а через 7¿(в |у)—ПЛС периода занятости ¿-системы, открываемого требованием длины у. Положим

Функции 7{(з) и 0¡(я | у) удовлетворяют системе уравнений

-Sll-\i+i —-Г.+ 1 (в) <5,+ 1 (г)] ¿г

7,-(,9) = / е ° (1В(и) х

о

+ 1 61+1{и) 0,+ ° (1и) ,

о

оо

!+П'гЧ'?; "г + 1

У

_8(и_у)_А;+1 J[1-7^, (8) 5(+1 (2)] <¿2

хе " (¡и.

В том случае, когда число п мест ожидания конечно (п < оо). функции 7,(5) и б^э | у) определяются из полученной системы рекур-рентно, начиная с г = н и кончая г = 0. При этом

7п+1(5) = 1, 6п+1(8\у) = В(у).

Остальные рассматриваемые в третьей главе характеристики вычисляются либо через распределения периодов занятости ¿-систем, либо аналогично тому, как вычисляются распределения этих периодов.

В четвертой главе найдено в терминах преобразований (преобразования Лапласа—ПЛ, ПЛС и ПФ) совместные нестационарное и стационарное распределения основных характеристик обслуживания в системе M/G/1/oo с дисциплиной LIFO Р.

Обозначим через в = e(z{,z2,z,si,s) ПЛ по t (аргумент s) выраженного в терминах преобразований совместного распределения основных характеристик обслуживания на первом периоде занятости, не закончившемся к моменту t: числа обслуженных к моменту t требований с учетом их длин (аргумент z[)\ числа находящихся в этот момент в очереди требований, которые уже обслуживались, также с учетом их длин (аргумент числа находящихся в очереди еще не обслуживавшихся требований (аргумент z), длины находящегося на приборе требования (аргумент s 1).

Теорема 4.1. Функция в задается формулой

оо

e = e{z;,zZ,z,sus) = J e-{s,+s^xq{z*1,z'2,z,s,x)dx, о

где входящие в эту формулу величины определяются соотношениями

__q*{zhz,s,x)_

ОО _ 1

1 - А Л%) 4(у) + Чу) 7(*i,s I у)} e->«q'(z;,z, s, у) dy о

оо

В(х) J

у

X X

_ -A[1-7(*V)]/<5(!/)d!/-A(l-i) ¡S(y)dy q*{z*,z,s,x) = B{x)e

OO

-y(z*,s) = J z*(x)e~sx-xil-i{z''s)]xdB{x). о

Предполагая для простоты изложения, что в начальный момент система свободна от требований (хотя приводимая далее теорема 4.2 с незначительными изменениями может быть перенесена и на случай любых начальных условий), обозначим через 7г =

= 7Г(г*, г|, г, S\, s2, s) ПЛ по t выраженного в терминах преобразований совместного распределения основных характеристик системы в момент £: числа обслуженных к моменту £ требований (аргумент ); прошедшей длины протекающего в момент i периода занятости (аргумент si); числа обслуженных на нем требований (аргумент 22); числа требований, находящихся в очереди в момент t, которые обслуживались, но не обслужились (аргумент Z3); числа находящихся в этот момент в системе требований, которые еще не обслуживались (аргумент 2); (обслуженной) длины находящегося на приборе требования (аргумент s2).

Теорема 4.2. Функция 7Г задается формулой

т = т(*1,22,23,2,51,52,8) = -ТТЛ-ыТЙ- >

s + А - ^7(2^5) где , г2,2, si, s2) определяется в теореме J^.l.

Наконец, обозначим через W = 7r(z2,23, 2, sb s2) выраженное в

терминах преобразований совместное стационарное распределение времени, прошедшего с начала периода занятости, не закончившегося к рассматриваемому моменту, числа требований, обслуженных от начала протекающего в этот момент периода занятости с учетом их длин, числа недообслуженных требований, находящихся в очереди с учетом их длины, числа необслуживавшихся требований, находящихся в очереди и длины требования, находящегося на приборе. Из теоремы 4.2 вытекает следующий результат.

Теорема 4.3. Функция ж задастся формулой

TT = Tf(z2,z3,z,si,s2) = (1 - р)[ 1 + A0(22,23i,2,S2,S1)], где 0(2i,22, 2, si, s2) определяется в теореме 4-1-

В четвертой главе приводятся также примеры применения теорем 4.1 4.2.

Наконец, в пятой главе решается следующая задача. Рассмотрим систему Mfc/G/1/n (0 < п < со) с дисциплиной

LIFO Р. Предположим, что существует кусочно-непрерывная плот-

_ 00

ность Ь(х) = В'(х), а средняя длина требования Ь = J xb(x)dx ко-

о _

нечна. Для удобства изложения положим и, (х) = 1 — 5i(x) = 5{(х). Набор функций {u,(a:), i = 1,п+ 1} будем называть управлением в системе Mjt/G/1/n с дисциплиной LIFO Р.

Предположим теперь, что если в системе находится ¿ требований и на приборе требование длины х, то за единицу времени система несет потери a,(x). Далее, пусть система полностью загружена и на обслуживании находится требование длины х. Тогда если в систему поступает новое требование и это требование выбивает обслуживавшееся требование длины х из системы, то система несет дополнительные потери rn+i{x). Если же систему покидает вновь прибывшее требование, то дополнительные потери равны rn+1 = rn+i(0). Предполагается, что функции ß{(a;) ограничены и кусочно-непрерывны, а функция rn+i(x) имеет ограниченную кусочно-непрерывную производную г'п+1 (х).

Обозначим через г суммарные средние потери на одном периоде занятости. Необходимо найти функции и*(х), минимизирующие средние потери г или в соответствии с принятым соглашением определить оптимальное управление в системе Mfc/G/1/n с дисциплиной LIFO Р.

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

Справедливы три леммы, которые, во-первых, показывают существование оптимального управления, а, во-вторых, позволяют свести задачу нахождения оптимального управления для системы M^./G/1/n к последовательности аналогичных задач для системы M/G/1/0.

Лемма 5.1. Оптимальное управление для рассматриваемой системы существует.

Рассмотрим теперь период занятости системы, открываемый требованием (обслуженной) длины х. Обозначим через г(х) средние потери на этом периоде занятости. Очевидно, что г(0) = г.

Лемма 5.2. Пусть {и-'(х)}—управление, доставляющее минимум средним потерям г. Тогда это же управление будет минимизировать и средние потери г(х).

Наряду с основной описанной системой, так же как и в главе 3, введем в рассмотрение ¿-систему (0 < г < п). ¿-система представляет собой систему Mjt/G/1/n-i с п — i местами ожидания, подобную исходной системе за исключением того, что для ¿-системы интенсивности Af> определяются равенствами A^' = Авероятности w^'(x)— равенствами и^(л') = uk-i{x), удельные потерн = гц._,-(.т) и

дополнительные потери г^^Д.г) = гп+1(.т). - — _______

Будем обозначать через г,- и г,(х) средние потери на одном периоде занятости г-системы и средние потери на периоде занятости г-системы, открываемом требованием длины х. Ясно, что п(0) = г,-.

Лемма 5.3. Пусть {г'^*(х), к = 1,тг+1 —г}—оптимальное управление для г-системы. Рассмотрим для исходной системы класс управлений и.1 (х),..., гх,(х), и\'^*(х),..., Тогда среди уп-

равлений этого класса найдется управление, оптимальное для исходной системы.

Последняя лемма дает рекуррентный алгоритм нахождения оптимального управления. Действительно, рассмотрим сначала тг-сис-тему и определим для нее оптимальное управление. При этом необходимо определить только одну функцию (х) = и*+1(х). Затем, полагая 14п-1^*(х) = и*+1(х), решим аналогичную задачу для тг — 1-спстсмы и определим и\п = «„(х). Продолжая эту процедуру,

полностью вычислим оптимальное управление {"'(х)} для основной рассматриваемой системы.

Для средних потерь г,- (:г) на одном периоде занятости г-системы справедлива следующая (формула:

X

^ А1 + 1 Jui + ,(v)dv Г'^ = Щх)е " У {аг+1(?у) + А1+1г1+1 -Л1+1г/,+ 1(г/)[г,+ 1-

X

У

_ -А.+ 1 / «1+1 (") Ам

Итак, мы показали, что задача выбора оптимального управления {и*(.г)} сводится к последовательному, начиная с г = п и кончая г = О, нахождению функций г/*+1(.г), минимизирующих функционалы г,-.

Положим (для краткости будем опускать индекс г)

г/и,(.т) = [(2{+1(.т) + А1+1Г!+,]5(.г-) - ([гг+1 - г!+1 (х)] В(х))' - и:Ь(х). Введем в рассмотрение функцию

У

/Х — А ^ u(v) йV

Чш{у)е ° ¿у.

о

Теорема 5.1.

1. Пусть и* (х) доставляет минимум г* функционалу г. Тогда выполнены соотношения

Q(<x>,r*,u*) = 0, (1)

если Q(x,r*,u*) > 0; , .

( > ~ \ 1, если Q{x, г\и*) < 0. ( J

2. Для любого w функция и(х), удовлетворяющая соотношению

( \ _ / если Q(x, w, и) > 0; . .

* ' ~ 1, если Q(x, w,u) < 0, ^ '

определяется единственным образом, является кусочно-постоянной и принимает только значения 0 или 1.

3. Оптимальное управление и* (а;) и минимальное значение г* функционала г определяются соотношениями (1) и (2) однозначно.

Теорема 5.1 дает конструктивный алгоритм вычисления оптимального управления, состоящий в следующем. Для произвольного iu\ определяем управление Uj (х), удовлетворяющее соотношению (3). Если при этом Q{оо, щ) < 0, то выбираем W2 < w\, в противном случае выбираем ui2 > wi. Процедуру продолжаем до тех пор, пока не получим значение wn, приближающее г* с заданной точностью. При численных расчетах удобно воспользоваться методом деления отрезка пополам или методом хорд.

В §§ 5, 6 пятой главы рассматриваются некоторые примеры, иллюстрирующие полученные результаты.

Наконец, § 7 решается задача вычисления управления {и,-(х)}, минимизирующее стационарную среднюю длину очереди в системе M/G/1/co. Хотя эта задача и не является частным случаем решенной ранее общей задачи, ее решение имеет чрезвычайно простой вид.

Пусть в систему с бесконечным числом мест ожидания поступает пуассоновский поток требований интенсивности Л. Будем предполагать, что загрузка системы р = Xb < 1 и, кроме того, второй момент

оо

М2' = J x2b(x) dx длины требования конечен. По-прежнему, в си-о

стеме реализована дисциплина LIFO Р, определяемая вероятностями и,(.т). Наша задача заключается в нахождении управления {uj1 (х)}, минимизирующего стационарное среднее число г требований в системе.

Можно показать, что при сделанных предположениях оптимальное управление {и*(х)} существует, и, кроме того, его можно искать в классе управлений, для которых все щ(х) совпадают (щ(х) = и(х)).

Оказывается, управление и*(х) оптимально тогда и только тогда, когда

,,*Г-И-/0' если Q(x) > 0;

[1 \l, если Q(x) < 0,

где

ОО

Q(x) = -^-В{х) + f B(y)dy.

1 - р 1 - р J

X

Значения управления и(х) в тех точках х, для которых Q(x) = 0, никак не влияют на значение функционала г.

Аналогично, управление и**(х), максимизирующее среднее число требований в системе, задается формулой

если > 0;

если Q(x) < 0,

т.е, связано с управлением и*(х) соотношением и**(х) = 1 — и*(х).

Автор выражает глубокую благодарность своему научному руководителю профессору Александру Дмитриевичу Соловьеву за постановку задачи, постоянное внимание и помощь в работе.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Печинкина O.A. Стационарное распределение очереди в системе Mfc/G/1/n с инверсионной вероятностной дисциплиной обслуживания // Тезисы докладов XXX научной конференции факультета физико-математических и естественных наук. 4.2. Математические секции.—М: РУДН, 1994,—С. 68.

2. Печинкина O.A. Система М /G/1 с инверсионной вероятностной дисциплиной обслуживания // Исследование сетей связи и компьютерных сетей методами теории массового обслуживания: Тез. докл. Минск,—1995.—С. 102.

3. Печинкина O.A. Асимптотическое распределение длины очереди в системе М/G/l с инверсионной вероятностной дисциплиной обслуживания // Тезисы докладов XXXI научной конференции факультета физико-математических и естественных наук. 4.1. Математические секции—М: РУДН, 1995.—С. 88.

4. Печинкина O.A. Асимптотическое распределение длины очереди в системе М/G/l с инверсионной вероятностной дисциплиной обслуживания // Вестник российского университета дружбы народов. Сер. Прикладная математика и информатика.—1995.— N 1.—С. 87-100.

5. Печинкина O.A. Характеристики обслуживания в системе Mfc/G/1 с инверсионной вероятностной дисциплиной обслуживания // Рукопись депонирована в ВИНИТИ 19.02.96 N 519-В96. 51 с.