A use of hyperexponential distribution in non-markovian queuing systems analyses.pdf При исследовании немарковских процессов поступления и обслуживания заявок в многоканальных системах массового обслуживания (СМО) широко применяются распределения фазового типа (обозначаются Ph). К этим распределениям относятся взаимосвязанные параллельно-последовательные комбинации фаз прохождения заявок с показательно распределенными длительностями задержек в них. При фиксации номера фаз поступления или обслуживания заявок состояния СМО приобретают марковское свойство, что позволяет представить переходы между ними в виде дискретного марковского процесса с непрерывным временем. Идея метода фиктивных фаз была выдвинута еще А.К. Эрлангом. Порядком аппроксимации естественно считать количество сохраненных начальных моментов исходного распределения. Наиболее общей формой представления фазовых распределений является схема Ньютса [1], в которой длительность каждой реализации процесса соответствует случайному времени блуждания по сети с показательной задержкой в каждом узле и одним поглощающим состоянием. При этом расчет СМО проводится в терминах кронекеровых матричных операций и, как правило, для одноканальных систем [Там же]. Машинная реализация упомянутых операций крайне неэффективна из-за необходимости выполнения большого количества вычислений с заведомо нулевым результатом. По этой причине для аппроксимации распределений с коэффициентом вариации и > 1, как правило, используют гиперэкспоненциальную (Hk) аппроксимацию, а в остальных случаях - эрлангову (Ek). В обоих случаях параметры распределений предполагаются исключительно вещественными. В последнее время возрастает интерес к гиперэкспоненциальному распределению, применение которого показало высокую эффективность при решении задач суммирования рекуррентных потоков [2], расчета СМО с «нетерпеливыми» заявками [3], джексоновских сетей массового обслуживания [4], при анализе систем управления запасами [5]. В статье представлены результаты применения гиперэкспоненциального распределения второго порядка (Н2) с возможностью комплексного типа параметров, что позволяет аппроксимировать время обслуживания и интервалы между заявками входящего потока с произвольным (в том числе меньшим единицы) коэффициентом вариации и упростить расчетную схему. 1. Особенности применения ^-распределения Гиперэкспоненциальное распределение второго порядка относится к распределениям фазового типа и предполагает выбор случайным процессом одной из двух альтернативных фаз. С вероятностью y процесс попадает в первую фазу и задерживается в ней случайное время, распределенное по экспоненциальному закону с параметром ць с вероятностью y2 = 1 - y процесс попадает во вторую фазу, где экспоненциальная задержка имеет параметр ц2. Дополнительная функция ^-распределения имеет вид F (t) = yxe ^ + y 2 e . Подбор параметров ^-распределения возможен по методу моментов [1]. Поскольку данное распределение трехпараметрическое (четвертый параметр y2 = 1 - yi), оно позволяет выровнять три начальных момента аппроксимируемого, что принято считать вполне достаточным [6]. В зависимости от значений выравниваемых моментов параметры ^-распределения могут принимать комплексные и «парадоксальные» значения. Исследование #2-аппроксимации исходного гамма-распределения с коэффициентом вариации и выявило, что: - случай и > 1 дает вещественные параметры; - при 1 > и > 1/ V2 параметры гиперэкспоненты вещественны, но парадоксальны: один из параметров {у}, j = 1, 2 будет отрицательным, а другой превысит единицу; - строгое равенство и = 1/V2 недопустимо (соответствует Е2 распределению Эрланга с последовательной сменой фаз и не может быть заменено на параллельную); - при и < 1/ 42 имеем комплексные параметры #"2-аппроксимации. Поскольку параметры гиперэкспоненты {у}, j = 1, 2, интерпретируются как вероятности выбора случайным процессом одной из двух фаз, большинство специалистов по теории массового обслуживания рассматривают лишь тот случай, когда данные параметры определены на вещественном интервале [0, 1], что соответствует аппроксимации распределений с коэффициентом вариации и > 1. Именно поэтому для аппроксимации распределений с коэффициентом вариации и < 1 гипреэкспонента не используется, а применяется распределение Эрланга Ek. Однако обширная серия вычислительных экспериментов показала, что при расчете СМО с применением #"2-аппроксимации в области комплексных значений ее параметров потенциальная патология проявляется только в промежуточных результатах - вероятностях «фиктивных» микросостояний диаграммы переходов, на которые расщепляются «физические» состояния СМО. На этапе суммирования вероятностей микросостояний ярусов их комплексные части аннигилируются и компоненты результата расчета - вероятности числа заявок в системе - становятся вещественными. Комплексный тип параметров ^-распределения подчеркивает фиктивный характер расщепления процесса на фазы. Допустимость таких параметров при исследовании случайных процессов была впервые отмечена Д. Коксом в 1955 г. [7]. В статье [8] авторы попытались дать вероятностную интерпретацию комплексных интенсивностей переходов между состояниями цепи Маркова. Примеры различных диаграмм переходов для СМО с гиперэкспоненциальным распределением обслуживания или интервалов между заявками входящего потока приведены в [1, 3]. Дополнительным преимуществом #"2-аппркосимации по сравнению с эрланговской является более компактный вид диаграмм переходов марковизированных СМО. Например, для моделей с эрланговским обслуживанием ширина диаграммы (количество микросостояний на n-м ярусе) быстро растет по числу каналов n и порядку распределения k (табл. 1) [9]. Т а б л и ц а 1 Количество микросостояний на ярусах системы MIEkln Число каналов n Число фаз обслуживания k 2 3 4 5 6 2 3 6 10 15 21 3 4 10 20 35 56 5 6 21 56 126 252 10 11 66 286 1001 3003 20 21 231 1771 10626 53130 30 31 496 5456 46376 324632 Заметим, что при этом эрланговы распределения позволяют строго выровнять первый и лишь приближенно - второй момент распределения времени обслуживания. Наименьший коэффициент вариации из включенных в табл. 1 распределений (Е6) составил 1/л/б « 0,408. Для расчета СМО с еще меньшим коэффициентом вариации могут потребоваться гораздо большие значения к. С другой стороны, применение Н2-аппроксимации позволяет выровнять три начальных момента произвольного (исключая Е2) распределения, что обеспечивает более высокую точность расчета СМО. Поскольку диаграмма переходов для M/H2/n имеет ширину всего лишь n + 1, здесь можно рассчитывать системы с гораздо большим числом каналов. В «общий строй» можно поставить и распределение Е2 -если допустить небольшое отклонение дисперсии. Таким образом, достоинствами Н2-аппроксимации являются: - возможность выравнивания трех моментов исходного распределения, что, как будет показано ниже, обеспечивает приемлемую точность при расчете СМО; - гораздо более компактный (по сравнению эрланговской аппроксимацией) вид диаграмм переходов марковизированных СМО и, как следствие, необходимость расчета вероятностей меньшего числа микросостояний для систем с малыми коэффициентами вариации времени обслуживания или интервалов между заявками входящего потока; - удобство вычисления дополнительной функции распределения. 2. Расчет немарковских СМО Перечислим основные этапы расчета немарковских СМО методом фиктивных фаз с помощью Н2-аппроксимации: - расчет начальных моментов распределений обслуживания и (или) интервалов между заявками входящего потока; - подбор параметров Н2-распределения по рассчитанным на предыдущем шаге моментам; - построение диаграммы переходов; - составление уравнений баланса переходов между микросостояниями диаграммы и расчет вероятностей микросостояний; - суммирование вероятностей микросостояний по ярусам и получение распределения числа заявок в системе. Рассмотрим возможности Н2-аппроксимации с произвольным типом параметров на примере одно-канальных СМО. Выполним расчет распределения {pj} числа заявок в одноканальной системе M/G/1 методом вложенных цепей Маркова [1] и методом фиктивных фаз через Н2-аппроксимацию различных распределений обслуживания B(t): - гамма с параметром формы 0,5 (Г0,5) (коэффициент вариации и ~ 1,41); - Гх,5 (и « 0,816); - равномерного U на интервале [0; 2] (и ~ 0,577); - вырожденного D (и = 0). Среднее время обслуживания во всех случаях Ь = 1, коэффициент загрузки системы р = 0,7. Результаты расчета распределения числа заявок в системе {p}, j = 0,20, приведены на рис. 1. Сплошной линией показаны результаты, полученные методом вложенных цепей Маркова, штриховой - методом фиктивных фаз через Н2-аппроксимацию. В табл. 2 приведены параметры Н2-распределения, рассчитанные по трем начальным моментам исходного распределения B(t). Т а б л и ц а 2 Параметры ^-распределения B(t) >1 И1 И2 B(t) >1 И-1 И2 Г0,5 0,500 0,586 0,341 U 0,500+i0,866 0,150+i0,866 0,150-0,866 Г1,5 -0,765 0,263 0,137 D 0,500+i0,141 0,200+i0,141 0,200-0,141 Рис. 1. Распределение числа заявок в системе M/G/1 Из графиков видно очень хорошее согласие результатов расчета распределения числа заявок в системе даже в области комплексных и парадоксальных параметров аппроксимирующей время обслуживания гиперэкспоненты. Расстояние Колмогорова при Г0,5, Г15, U и D обслуживании составило {0,002; 0,0002; 0,0015; 0,0018} соответственно. Относительная погрешность на «хвостах» распределений, в области малых значений вероятностей, не превысила 15%. При этом следует особо подчеркнуть, что в области комплексных параметров (см. табл. 2), особенно при аппроксимации случайных величин с коэффициентом вариации, близким к нулю, Н2-плотность принимает отрицательные значения и вообще не удовлетворяет требованиям, предъявляемым к плотности распределения. Тем не менее расчет марковизированных СМО показывает, что «комплексность» проявляется лишь в вероятностях микросостояний ярусов диаграмм и на этапе их суммирования полностью аннигилируется. Указанный эффект сохраняется при анализе многоканальных немарковских СМО [1. С. 224]. Таким образом, при работе с Н2-распределением необходимо учитывать, что параметры гиперэкспоненты могут принимать комплексные значения, а качество аппроксимации следует оценивать не по критериям согласия исходного и подобранного распределений, а по точности расчета итоговых характеристик СМО. Заключение Применение гиперэкспоненциальной аппроксимации позволяет с высокой точностью проводить анализ немарковских систем обслуживания с произвольным коэффициентом вариации времени обслуживания и (или) интервалов между заявками входящего потока. При этом комплексные значения параметров гиперэкспоненты, возникающие при коэффициенте вариации и < 1, не влияют на конечный результат, поскольку при суммировании вероятностей микросостояний ярусов диаграммы марковизиро-ванной СМО их комплексные части аннигилируются. Непосредственно о качестве аппроксимации субслучайных (с малым коэффициентом вариации) величин не может идти и речи, поскольку плотность гиперэкспоненты в этом случае принимает отрицательные значения и вообще не удовлетворяет требованиям, предъявляемым к плотности распределения. Качество аппроксимации здесь возможно оценить опосредованно - через сопоставление распределения числа заявок в СМО, полученного через #2-аппроксимацию, с результатами, полученными альтернативными методами. Применение гиперэкспоненциальной аппроксимации с комплексными параметрами также показало высокую эффективность при расчете многоканальных СМО с рекуррентным входящим потоком и (или) немарковским обслуживанием.

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