Algorithm of estimationfor number of states and state rates of MC-flow..pdf МС-поток широко применяется в качестве модели входящего потока заявок в теории массового обслуживания. Это обусловлено тем, что модель МС-потокадостаточно адекватно описывает входящий поток заявок в различных системахмассового обслуживания.Под МС-потоком будем понимать случайный поток событий, интенсивностькоторого представляет собой кусочно-постоянный марковский процесс Ґл(t), принимающий значения из конечного множества констант {Ґл1,Ґл2 ,...,Ґлn}( Ґлi ЎБ Ґл j при i ЎБ j ), называемых состояниями процесса Ґл(t). Длительности -----участков стационарности, т. е. участков, где λ (t ) = const , распределены по экспоненциальному закону. Переход процесса из состояния i в состояние j определяется матрицей инфинитезимальных коэффициентов ij nЎїn Ґб , где Ґбij > 0, i, j = 1, n, 1, , n ii ij j= jЎБiҐб = − ҐТ Ґб i = 1,n . Величина Ґбij , i ЎБ j, - интенсивность переходапроцесса Ґл(t) из состояния i в состояние j. Введем в рассмотрение следующиевеличины: Ґбi = −Ґбii , i = 1,n, Ґбi > 0, - параметр экспоненциального распределения длительности пребывания процесса Ґл(t ) в состоянии i, i = 1,n ; ij ij iipҐб−Ґбi ЎБ j, i, j = 1,n , 10 1, 0nij ij j p p ЎВ ЎВ ҐТ = - вероятности перехода процессаҐл(t) из состояния i в состояние j по окончании состояния i. Таким образомМС-поток событий с n состояниями полностью описывается следующими параметрами: Ґл = {Ґл1,Ґл2 ,...,Ґлn} , Ґлi > 0, i = 1, n, Ґлi ЎБ Ґл j , i = 1,n, Ґб = {Ґб1,Ґб2 ,Ў¦,Ґбn}, Ґбi > 0, i = 1,n , 20 Е.Н. Беккерман, С.С. Катаева1, 0 1, 0, 0, , 1, n ij n n ij ii ij j P p p p p i j n Ўї= ЎВ ЎВ = ҐТ = = .На участке стационарности МС-поток ведет себя как простейший поток событий (пуассоновский поток с постоянной интенсивностью). Таким образом, реализация МС-потока состоит из отрезков простейших потоков; интенсивность потокана отрезке определяется состоянием МС-потока.Для того чтобы использовать модель МС-потока при описании реальной системы массового обслуживания, необходимо определить характеристики МСпотока таким образом, чтобы модель хорошо аппроксимировала входящий потоксобытий этой системы. МС-поток, полученный в результате процедуры определения характеристик, будем называть аппроксимирующим МС-потоком. Характеристиками, определяющими МС-поток, являются количество состояний МС-потока, интенсивности состояний, а также интенсивности и вероятности переходов из состояния в состояние. Зачастую определить характеристики возможно лишь на основании информации о моментах наступления событий реального потока на некотором интервале времени.1. Общие принципы оценивания числа состоянийи значений интенсивностиЕсли известны только моменты наступления событий в реализации потока, то первоначально необходимо разбить реализацию на отрезки, которые бы соответствовали участкам стационарности. В работе [1] представлен алгоритм выделенияучастков постоянства интенсивности в реализации случайного потока событий и оценки интенсивности потока на этих участках.По выделенным из реализации случайного потока событий интервалам постоянства интенсивности оценим количество состояний аппроксимирующего МСпотока. Прежде чем оценивать количество состояний аппроксимирующего МСпотока, приведем несколько соображений.Для расчета характеристик СМО важно, чтобы модель входящего потока, с одной стороны, достаточно точно описывала реальный поток, а с другой - имелане слишком большое количество параметров. В случае МС-потока, количествопараметров модели определяется количеством состояний процесса Ґл(t).Вычислив оценки интенсивности на выделенных участках стационарности, можно определить количество состояний потока как количество различных по значению оценок. Однако понятно, что даже оценки интенсивности простейшегопотока, полученные по разному количеству событий или на различных временныхинтервалах, не будут равны между собой. Таким образом, маловероятно получитьна двух различных интервалах постоянства интенсивности равные значения оценок интенсивности потока.Разумно будет исходить из того, что оценки интенсивности на разных интервалах стационарности, относящихся к одному и тому же состоянию МС-потока, различаются, так как являются случайными величинами, но, тем не менее, близкипо значению. То есть участки стационарности реального потока с «близкими» интенсивностями относятся к одному и тому же состоянию. Определив критерий"близости" значений интенсивности на различных участках стационарности, можно будет разбить множество оценок на группы, в которые войдут оценки интенсивности интервалов стационарности, относящиеся к одному и тому же соАлгоритм оценивания числа состояний и значений интенсивностей MC-потока событий 21стоянию аппроксимирующего МС-потока. Количество получившихся групп и будет определять количество состояний аппроксимирующего МС-потока.Пусть с помощью алгоритма выделения интервалов стационарности МСпотока по реализации моментов наступления событий выделено некоторое числоk интервалов постоянства интенсивности вида1 1 2 2 3 31[ , ],[ , ],[ , ], ,[ , ], , 1, , , 1, 1, k k l l i j i j i j i j i j l l t t t t t t t t t t l k j i - l k Ў¦< < = −где , , 1, til t jl l k = , есть определенные моменты наступления событий из реализации. Таким образом, в рассматриваемой реализации выделено k интервалов стационарности. Моменты времни , , 1, til t jl l k = , являются соответственно временами наступления первого и последнего событий на l-м интервале стационарности.Для каждого интервала стационарности найдем оценку интенсивности потока на данном интервале по формулеˆ ( ) 1, 1, l l l l l j i j i l k t t − Ґл = −.Заметим, что такие оценки интенсивности есть оценки интенсивности простейшего потока, полученные по методу максимального правдоподобия, и они обладают всеми полезными свойствами таких оценок.Далее, полученные оценки интенсивности на выделенных интервалах стационарности нужно разбить на классы, содержащие оценки интенсивности интервалов стационарности, относящихся к одному и тому же состоянию аппроксимирующего МС-потока. Очевидно, что для того, чтобы относиться к одному классу, оценки должны быть близкими по значению, то есть группироваться на числовойоси. Между группами же должно быть значительное расстояние. Если перенумеровать полученные оценки таким образом, чтобы они оказались упорядоченнымипо возрастанию, то очевидно, что процедура деления этого ряда на группы должна основываться на расстояниях между соседними значениями оценок ряда. В качестве критерия близости при группировке оценок интенсивности примем расстояние между соседними оценками в упорядоченной по возрастанию совокупности оценок интенсивностей выделенных интервалов стационарности.Внутри же группы, которая включает оценки интервалов, относящихся к одному и тому же состоянию аппроксимирующего МС-потока, оценки должны бытьв некотором смысле однородны. Вряд ли возможна единственно верная формулировка критерия однородности оценок в группе. Однако представляется естественным в качестве критерия однородности взять соотношение между размахом значений в группе (разницей между минимальным и максимальным значением в группе) и средним значением оценок в группе, то есть как сильно крайние значения отличаются от среднего.Пусть {ˆ (i) , ˆ (i 1) , , ˆ ( j)}Lij = Ґл Ґл - Ў¦ Ґл - группа оценок интенсивностей, следующихпо порядку. Назовем величину( ) ( ˆ ( ) ˆ ( ) ) 1 ˆ ( )1jj i l ij l i c L j i = Ґл −Ґл Ґл − - ҐТ 22 Е.Н. Беккерман, С.С. Катаевапоказателем однородности группы Lij. Здесь числителем является размах значенийв группе, знаменателем - среднее значений в группе. Будем говорить, что группаоценок однородна, если c(Lij ) ЎВ с0 , и неоднородна в противном случае, где с0 -пороговое значение показателя однородности группы, некоторая наперед заданная положительная величина, выбираемая исходя из того, что разброс значенийоценок интенсивности в однородной группе сопоставим с величиной среднегоэлементов группы. Заметим при этом, что группа, состоящая из одного значения, однородна.Если группа оценок интенсивностей однородна, то группа соответствует состоянию интенсивности предполагаемого MC-потока событий, при этом оценка интенсивности, соответствующая данному состоянию, рассчитывается по формулеˆ ˆ ( ) ˆ ( )jl l ij j l i s s i n L= n Ґл = Ґл =ҐТ Ґл ҐТ , где Ґлˆ (l) - l-я оценка интенсивности в группе, ns - количество событий на интервале стационарности, соответствующем s-й оценке интенсивности в группе. То естьоценка интенсивности состояния есть средневзвешенная по числу событий оценокинтенсивности на участках постоянства интенсивности, отнесенных к этому состоянию.Группы оценок из всей совокупности предлагается выделять следующим образом. Для начала нужно проверить, не является ли вся совокупность оценок L1k однородной. В случае, если совокупность L1k не является однородной, разбить ее на две части: L1j и Lj-1k, причем так, чтобы граница между двумя группами пролегалав том месте набора значений оценок интенсивности, где разница между двумя соседними значениями максимальна. То есть граница между частями определяетсярасстоянием между соседними значениями упорядоченного ряда интенсивностейвыделенных интервалов стационарности. Каждую из групп вновь проверяем на однородность и, если они не однородны, снова разбиваем на части. Процесс заканчивается, когда все выделенные группы будут однородны, то есть для всех выделенных групп показатель однородности будет меньше единицы. Однородные группы и будут содержать оценки интенсивности на участках стационарности, которые можно отнести к одному и тому же состоянию аппроксимирующего МС-потока.Число групп оценок, полученное в результате классификации, будет являтьсяоценкой числа состояний интенсивности аппроксимирующего MC-потока событий. В качестве оценки интенсивности состояния МС-потока естественно будетвзять величину, равную взвешенному среднему оценок внутри класса, соответствующего данному состоянию.2. Алгоритм оценивания числа состояний и значенийинтенсивности МС-потока событийС учетом приведенных выше рассуждений, сформулируем алгоритм группировки оценок интенсивностей.Шаг 1. Задаются величины, nˆ = 0, i = 1, j = k , где nˆ - оценка количествасостояний МС-потока, k - количество интервалов постоянства интенсивности, выделенных в реализации исследуемого потока событий L = {Ґлˆ (1) ,Ў¦,Ґлˆ (k )} .Алгоритм оценивания числа состояний и значений интенсивностей MC-потока событий 23Шаг 2. Вычислить показатель однородности группы оценок Lij по формуле( ) ( )( )ˆ ˆ( )1 ˆ1j i ij j l l i c L j i Ґл −ҐлҐл− - ҐТ .Шаг 3. Если Lij < 1, то 3.1. Оценку количества состояний аппроксимирующего МС-потока ˆ n увеличить на 1; 3.2. Оценку интенсивности потока в состоянии, определенном группой оценок Lij , вычислить по формулеˆ ( ) ˆ ( )jl l ij j l i s s i n L= n Ґл =ҐТ Ґл ҐТ ; в противном случае: 3.3. Найти такое l- , что - ( 1) ( ), 1argmax( ˆ l ˆ l )l i j l = −= Ґл − Ґл ; 3.4. Положить i = i, j = l- и для группы Lij проделать шаги 2 и 3; 3.5. Положить i = l- -1, j = j и для группы Lij проделать шаги 2 и 3.Шаги 2 и 3 алгоритма представляют собой рекурсивную процедуру (пункты3.3, 3.4, 3.5 шага 3 производят повторение проверки однородности группы с новыми данными, пункты 3.1, 3.2 определяют условие останова рекурсии). Результатом работы алгоритма являются: - величина ˆ n - оценка числа состояний; - значения 1 ˆ Ґлˆ ,Ў¦,Ґлˆ n - значения оценок интенсивности состояний аппроксимирующего MC-потока событий.3. Алгоритм оценивания значений интенсивности МС-потока событийпри ограничении числа состоянийВ некоторых случаях количество состояний входящего потока заявок заранееограничено условиями задачи. Зачастую количество состояний должно быть не более некоторого наперед заданного числа. В таких случаях также можно руководствоваться приведенными выше соображениями с той лишь разницей, что процедура деления ряда оценок на группы заканчивается по достижении заранееизвестного количества групп (состояний потока) или когда все группы признаныоднородными.Шаг 1. Задать величины, nˆ = 1, i = 1, j = k, n- , где nˆ - оценка количествасостояний МС-потока, k - количество интервалов постоянства интенсивности, выделенных в реализации исследуемого потока событий L = {Ґлˆ (1) ,Ў¦,Ґлˆ (k )} , n- -максимально возможное по условию задачи количество состояний аппроксимирующего МС-потока. Сформировать список групп оценок L

Скачать электронную версию публикации