Содержание к диссертации
Введение
ГЛАВА I. Анализ систеш эрланга при различных дисциплинах обслуживания 17
1. Описание системы и классов дисциплин обслуживания 17
2. Оптимальная дисциплина обслуживания в случае сильной информации 20
3. Асимптотические оценки вероятности потери требования при малой нагрузке 34
4. Об оптимальной дисциплине обслуживания при умеренной и высокой нагрузке 44
5. Оптимальные дисциплины обслуживания в случае слабой информации 54
ГЛАВА II. Двухфазовая система с идентичным обслуживанием при различных дисциплинах обслуживания 67
6. Описание двухфазовой системы с идентичным обслуживанием 67
7. Дисциплина d0 на первой фазе и дисциплина dz на второй фазе 75
8. Дисциплина а у на первой фазе и дисциплина на второй фазе 87
9. Дисциплина &ъ на первой фазе и дисциплина dt на второй фазе 91
10. Дисциплина d4 на второй фазе 95
Литература 9
- Оптимальная дисциплина обслуживания в случае сильной информации
- Оптимальные дисциплины обслуживания в случае слабой информации
- Дисциплина d0 на первой фазе и дисциплина dz на второй фазе
- Дисциплина &ъ на первой фазе и дисциплина dt на второй фазе
Оптимальная дисциплина обслуживания в случае сильной информации
Если в системе есть свободные приборы, то пришедшее требование становится на обслуживание к одному из них. Дисциплина обслуживания в системе Эрланга задается правилом потери : требование, пришедшее в систему в момент, когда все приборы заняты, либо теряется, либо становится в систему на место одного из требований, которое при этом теряется. Правило потери требования определяется имеющейся информацией о требованиях, находящихся в системе, и о пришедшем требовании. Мы рассмотрим несколько типов такой информации и соответствующих им классов дисциплин.
Определим класс дисциплин, который соответствует сильной информации о требованиях. Пусть в момент поступления требования в систему известна его длина. А в каждый момент времени известны выработанные и остаточные длины требований, находящихся в сие теме. Такую информацию будем называть сильной информацией. Класс дисциплин обслуживания, соответствующий сильной информа ции, обозначим ф . Он состоит из дисциплин обслуживания, у которых правило потери, вообще говоря, зависит от выработанных и остаточных длин требований, находящихся в заполненной системе в момент прихода туда требования, и от длины пришедшего требо вания. Если X - = \ Х , Х , ... , Ха ) - вектор выработанных длин, а Х+ { Х , ЭСг+,... , X ) вектор остаточных длин требований, находящихся в системе в мо мент прихода требования длины X , то правило потери представ ляет собой функцию d ( х- Х+ , X ) . эта функция в за висимости от X __, ос +, X принимает одно из П+ 4 значений і 9 Z , ... , (1 + 4 » которое указывает номер теряющегося требования. Заметим, что требования занумерованы в порядке их поступления в систему, и после каждой потери или обслуживания находящегося в системе требования происходит перенумерация требований в порядке их поступления в систему.
Пусть о требованиях в системе известно лишь то, в каком порядке они поступили в систему. Такую информацию будем называть слабой информацией типа А. Если в системе находится її требований ( К П,) , то они занумерованы числами от 4 до в порядке поступления в систему. Требование, пришедшее ранее остальных имеет номер і и т.д. ..., пришедшее последним, имеет номер ft . Располагая информацией о порядке прихода в систему требований определим класс Л)д дисциплин обслуживания. Этот класс состоит из (n+d) - ои различных дисциплин: dLw,dL№\ ... ,cl , oLm+1), cL - дисциплина, согласно которой приходящее в за полненную систему требование вышибает требование с номером і , которое теряется, и пришедшее требование становится на его место к прибору, L = 4, &,..,, п ; (X - дисциплина, при которой приходящее в заполненную систему требование теряется. Это обычная дисциплина потери.
Если о находящихся в системе требованиях известно в каждый момент времени их выработанные длины, то такую информацию будем называть слабой информацией типа В. Эта информация определяет класс J) о дисциплин обслуживания, для которых правило потери требования зависит от выработанных длин находящихся в системе требовании в момент поступления в заполненную систему еще одного требования.
Основной характеристикой для систем с потерями является вероятность потери требования Цель первой главы -найти оптимальные дисциплины, которые дают минимум стационарной вероятности потери требования в классах дисциплин, соответствующих сильной и слабой информации о требованиях в системе. А также оценить максимальный выигрыш для вероятности потери требования, который можно получить в результате применения нестандартных дисциплин обслуживания в системе Эрланга.
Как отмечалось в первом параграфе, класс фл состоит из дисциплин обслуживания, у которых правило потери, вообще говоря, зависит от выработанных и остаточных длин требований в системе в момент прихода в заполненную систему требования, а также от длины пришедшего требования. Обозначим Х0 дисциплину из этого класса, согласно которой приходящее в заполненную систему требование "вышибает" из системы требование с наибольшей остаточной длиной дообслуживания, если эта длина больше, чем длина пришедшего требования; в противном случае пришедшее требование теряется. Цель настоящего параграфа - доказать, что в классе дисциплин обслуживания S)r дисциплина С10 дает ми нимум стационарной вероятности потери требования.
Оптимальные дисциплины обслуживания в случае слабой информации
В последние годы одним из наиболее актуальных направлений в теории массового обслуживания является изучение систем обслуживания для различных дисциплин обслуживания, нахождение оптимальных дисциплин, асимптотический анализ систем обслуживания при различных дисциплинах обслуживания в условиях малой или критической нагрузки.
В работах Л.Шраге [24} \ 5\ была найдена оптимальная дис циплина обслуживания в системе MG) Цо , которую мы будем называть дисциплиной Шраге, при условии, что в момент поступления каждого требования нам известно его полное время обслуживания. В.В.Козлов [ii ] обобщил этот результат на произвольный входящий поток, независящий от процесса обслуживания.
В работах В.В.Козлова и А.Д.Соловьева [iZ \ [43І было показано, что в условиях малой нагрузки применение дисциплины Шраге дает большой выигрыш для основных характеристик обслуживания. И.В.Брысина и А.Д.Соловьев 1.2. ] провели полный асимптотический анализ сетей массового обслуживания весьма общей структуры при произвольных дисциплинах обслуживания в условиях малой нагрузки.
Большое значение имеют работы Г.П.Климова [3 J » \i0 J ,. который исследовал системы с разделением времени. В этих работах, в частности, найдены оптимальные дисциплины в классе дисциплин без прерывания обслуживания.
А.В.Печинкин,[ІТ ]Д {о \ , провел широкое исследование однолинейных систем для различных дисциплин и классов дисциплин, получил в ряде случаев замкнутые формулы для характеристик обслуживания, провел асимптотический анализ однолинейных систем для некоторых классов дисциплин в условиях малой и критической нагрузки, получил ряд интересных оценок и качественных выводов.
А.В.Павлов [45 "] нашел асимптотическое распределение процесса обслуживания в однолинейной системе для дисциплины Шраге, когда нагрузка стремится к единице. Этот очень сильный результат дал метод асимптотического анализа систем обслуживания для довольно широкого класса дисциплин в некотором смысле близких к дисциплине Шраге.
Цель настоящей работы - исследование многолинейных и многофазных систем при различных дисциплинах обслуживания. По сравнению с однолинейной системой исследование многолинейных и многофазных систем намного сложнее, требует введения новых методов и приемов. Данная работа только начинает разработку этой проблематики. В ней изучены система Эрланга и двухфазовая система обслуживания .
Диссертация состоит из введения, двух глав, разбитых на десять параграфов, и списка литературы.
Первая глава посвящена анализу системы Эрланга при различных дисциплинах обслуживания.
В 1 описана классическая система Эрланга, состоящая из П, однотипных приборов. Мест для ожидания в системе нет. Входящий поток требований является пуассоновским с параметром Л . Длины требований независимы и одинаково распределены по закону Є(х) со средним Т= jxdG(x) о , a 0 JiT нагрузка на систему.
Дисциплина обслуживания задается правилом потери: требование, пришедшее в систему в момент, когда все приборы заняты, либо теряется, либо становится в систему на место одного из требований, которое при этом теряется.
Правило потери требования зависит от имеющейся информации б требованиях, находящихся в системе, и о пришедшем требовании. Определены несколько типов такой информации и соответствующие классы дисциплин.
Дисциплина d0 на первой фазе и дисциплина dz на второй фазе
Определим дисциплину обслуживания в системе. Она представляет собой вектор Л = (d , d J , где dL - дисциплина обслуживания на -ой фазе = 1,2 . Каждая дисциплина задается матрицей скоростей где C«q - скорость обслуживания на 6-ой фазе -$ -го по сче ту из {. находящихся на этой фазе в данный момент времени требований (они нумеруются в порядке поступления на фазу) . Будем предполагать, что скорости на данной фазе в каждый момент времени зависят только от векторов выработанных и остаточных длин всех требований, находящихся в данный момент времени на этой фазе. На скорости накладывается существенное ограничение: для любого
Дисциплины, удовлетворяющие этому условию, называют консервативными. Класс і сі \ таких дисциплин обслуживания обозначим
В этой главе мы будем использовать следующие обозначения известных консервативных дисциплин обслуживания : дисциплина обслуживания на данной фазе требования с минимальной остаточной длиной на этой фазе, а если таких требований несколько, то из них обслуживается требование, которое поступило на фазу раньше; дисциплина обслуживания на данной фазе требований в порядке их поступления на эту фазу; дисциплина обслуживания на данной фазе требования, пришедшего на эту фазу последним (с прерыванием и дообслуживанием); дисциплина обслуживания на данной фазе без прерывания, при которой из очереди на обслуживание выбирается требование кратчайшей длины; дисциплина обслуживания на данной фазе требования кратчайшей длины с прерыванием и дообслуживанием; дисциплина, согласно которой на данной фазе со скоростью единица обслуживается требование с максимальной остаточной длиной на этой фазе, а если таких требовании несколько ( к штук), то каждое из них обслуживается с одинаковой скоростью i- .
Состояние системы в каждый момент времени можно задавать с помощью процесса (t) , где fy; (t) - число требований на -ой фазе в момент t , i= 1,2. Мы предполагаем, что входящий на первую фазу поток требований является пуассоновским с параметром X і . Пусть
Процесс обслуживания в нашей системе является регенерирующим процессом специального типа, период регенерации которого состоит из экспоненциально распределенного свободного периода, где [Ї) -(0,0) , и периода занятости, где (ijffao) [20] . Если период занятости системы имеет конечное среднее, то по теореме Смита для регенерирующих процессов [Щ 1 процесс обслуживания в системе является эргодическим, то есть существуют стационарные вероятности состояний процесса рл. .. . Докажем, что математическое ожидание длины периода занятости системы конечно. Обозначим j( "fc) - сумму остаточных длин требований на второй фазе в момент времени t . Поток требований с первой фазы на вторую не зависит от процесса обслуживания на второй фазе. Поэтому, при фиксированной дисциплине обслуживания на первой фазе процесс S (т) не зависит от консервативной дисциплины на второй фазе Г 1 . Отсюда следует, что при фиксированной дисциплине на первой фазе период занятости системы не зависит от консервативной дисциплины на второй фазе. Пусть d - произвольная консервативная дисциплина на первой фазе. Таким образом, процесс Ъ[ ) зависит только от консервативной дисциплины d, на первой фазе. Поэтому мы будем записывать этот процесс как 5 [t dL) » гДе d- Дисциплина обслуживания на первой фазе. Обозначим 3l{(Lj - математическое ожидание длины периода занятости системы при дисциплине GL на первой фазе ( эта величина не зависит от консервативной дисциплины на второй фазе).
Дисциплина &ъ на первой фазе и дисциплина dt на второй фазе
Рассмотрим двухфазовую систему с идентичным обслуживанием, описанную в шестом параграфе. Обозначим М W?, Я - среднее время пребыавния на второй фазе требования длины X в стацио нарном режиме. Если длина требования может принимать как угодно большие значения С В(зс) і для любого ЗС о) , то из работы [ 5 \ следует, что при обычной дисциплине (oLijdLi ) величина М-Vo % стремится к бесконечности при J\f-j для любого положительного X . Цель настоящего параграфа показать, что при дисциплине (dLudg) величина X стре мится к конечному пределу при и ВЫЧИСЛИТЬ этот предел.
Обозначим А - событие, состоящее в том, что в момент око нчания обслуживания требования j на первой фазе там осталось хотя бы одно требование длины не меньше, чем X . Тогда =Р(A)Mexpfi(V A)}+ (К)П о{-б(\х \1) te) ( здесь _Д - дополнительное к л событие ) .
Заметим, что для дисциплины а з выбора на обслуживание из очереди требования кратчайшей длины (если таких требований несколько, то они оОслуживаїштся в порядке поступления ) на первой фазе справедливо А=С0Е , где С - событие, состоящее в том, что в момент прихода требования S на первую фазу в очереди на этой фазе нет требований, длина которых больше или равна X ; - событие, состоящее в томг что за время Ф+ X на эту фазу не поступило ни одно требование длины большей или равной . Поэтому
Так как в классе консервативных дисциплин на первой фазе величина VX не зависит от дисциплины { \% \ , а также в силу свойств пуассововского потока и из работы [ { J следует, что при здесь (G"-i)- дисперсия длины требования.
Отсюда и из (1.9) следует, что при А Ті функции a:f-d) и М. &ZP 1-6 (V (А ) } стремятся к одному и тому же пределу. Найдем распределение величины ( /ZXIA) Так как на первой фазе дисциплина а3 , то в момент начала обслуживания на первой фазе требования С длины х на ней нет требовании длины меньшей, чем X . За время обслуживания на первой фазе требования р туда могут поступить требования длины меньшей, чем X . Кратчайшее из них начнет обслуживаться на первой фазе в момент tr перехода требования 6 на вторую фазу. Это требование длины меньшей, чем X , перейдет на вторую фазу, когда требование длины X там еще не закончит свое обслуживание в этот момент суглма остаточных длин требований, пришедших на вторую фазу не ранее момента Т (их два) , будет равна X . Это же, за исключением скобок, относится ко всем моментам перехода на вторую фазу требований длины меньшей, чем X , обслуженных на первой фазе непосредственно вслед за требованием на периоде занятости, образованном требованиями длины меньшей, чем X . Поэтому, в момент д окончания этого периода занятости требование длины X на второй фазе еще не закончит обслуживание, и в этот момент сумма остаточных длин требований, пришедших на вторую фазу не ранее момента Тґ будет равна X , включая перешедшее требование. Пусть выполнено событие Д. . Тогда в момент 0 на первой фазе начнет обслуживаться требование длины не меньше X и поэтому, требование , длины X закончит обслуживание на второй фазе в момент Р+я: ( оно закончит обслуживание последним из всех требований, перешедших на вторую фазу на отрезке
Поэтому, случайная величина ( Vg хІА ) имеет такое же распределение, как и период занятости с разогревом равным X для системы которую поступает пуассоновский поток требований с параметром D(,X) , а время обслуживания требований распределено по закону ВэЛм Следовательно,
