The method of calculating queuing system with impatient customers.pdf Одной из актуальных задач теории очередей является расчёт систем массового обслуживания (СМО) с «нетерпеливыми» заявками, уходящими из очереди при превышении некоторого допустимого (в общем случае случайного) времени ожидания (времени терпения). Обстоятельный обзор современного состояния вопроса приводится, например, в [1]. Приходится констатировать, однако, что подавляющее большинство известных методов либо относится к чисто марковским системам MIMIn-M [2] (в дополнении к нотации Кендалла через дефис указан тип распределения времени терпения), либо ограничено весьма стеснительными условиями - одноканальное обслуживание и большая загрузка [1]. Из работ по анализу многоканальных немарковских систем стоит выделить статью [3], в которой рассматривается диаграмма переходов системы с марковским обслуживанием и ^-распределением терпения MMIn-H2, а также работу [4], в которой предложен метод расчета системы с MAP-входящим потоком, матрично-фазовым (Ph) распределением обслуживания и марковским терпением. Ниже представлен метод расчета многоканальной системы с простейшим входящим потоком и ^-распределениями обслуживания и терпения MIH2In-H2. 1. Метод фиктивных фаз Традиционной технологией анализа многоканальных немарковских систем является метод фиктивных фаз. Расчёт при этом проходит следующие этапы: - аппроксимация непоказательных распределений распределениями фазового типа; - построение диаграммы переходов; - формирование в соответствии с диаграммой матриц интенсивностей переходов; - составление уравнений баланса переходов, их решение и расчёт стационарных характеристик СМО. Остановимся подробнее на каждом этапе. Аппроксимируем непоказательные распределения обслуживания и терпения по методу моментов ^-распределением. Оно относится к фазовым и позволяет выровнять три начальных момента любого (кроме Эрланга второго порядка) исходного. М.Дж. Кендалл и А. Стьюарт утверждают: «Практически аппроксимация такого рода оказывается очень хорошей, даже если совпадают только три или четыре момента» [5. С. 127]. Многочисленные вычислительные эксперименты [6] в области теории очередей также подтверждают, что трех моментов для проведения расчётов вполне достаточно. Далее, объединив представленную в [3] диаграмму для MIMIn-H2 с диаграммой системы без нетерпения MIH2ln, удалось получить схему переходов между состояниями системы MIH2In-H2. Остановимся подробнее на технологии ее построения. Напомним, что ^-распределение представляет собой две параллельные фазы с экспоненциальной задержкой в каждой из них. Пусть ^-обслуживание имеет параметры {yi, ц,}, где {y}, i = 1, 2, -вероятности выбора фаз, {.■}, j = 1, 2, - интенсивности показательного распределения времени обслуживания в них. Аналогично зададим параметры ^-распределения терпения - {ui, у,}. Интенсивность простейшего входящего потока обозначим X, число каналов - п. Далее рассмотрим состояния системы MIH2In-H2 без очереди. Поскольку в этом случае отсутствуют уходы по нетерпению, диаграмма переходов представлена на рис. 1. а Рис. 1. Диаграммы переходов в «недогруженной» системе MIH2In-H2 l/k /-1, m У 2 m/k i-1, j+I l, m-1 I- Л l/k _ l-1, m ; I j.2 I j_L l+1, m i, j l, m -- -H i, j lY1 l, m+1 my2 Обслуживание ^ Нетерпение l/k ---1 l-1, m i+1,j-1 .У2-.! m/k . ^ Прибытие заявки l, m -1 Длина очереди: k+1 k k-1 Рис. 2. Схема переходов в «загруженной» системе MIH2In-H2 На рис. 1, а показана диаграмма переходов по прибытию заявок, на рис. 1, б - по завершению обслуживания. Полужирные столбцы слева от диаграмм - номера ярусов, они соответствуют количеству заявок в системе. Двухразрядные индексы (00, 10, 01, 20 и т.д.) называются ключами микросостояний и указывают расстановку заявок по фазам (типам) ^-распределения обслуживания. Например, ключ «21» говорит о том, что в двух каналах заявки получают обслуживание первого типа (с показательной интенсивностью а в одном - второго типа (с интенсивностью ц2). У стрелок нанесены интенсивности соответствующих переходов между смежными микросостояниями. Заявка, пришедшая в занятую систему, становится в очередь. Для нее необходимо зафиксировать фазу ^-распределения терпения. При этом каждое микросостояние, начиная с (п+1)-го яруса, расщепляется для указания расстановки заявок по фазам Н2-терпения. Например, на n-м ярусе (рис. 1) количество микросостояний равно (n+1), все каналы обслуживания заняты и очереди нет. Прибывшая заявка застаёт систему в одном из микросостояний и в зависимости от типа её терпения попадает в одну из двух фаз. Поскольку терпящие в очереди заявки не влияют на процесс обслуживания, на (п+1)-м ярусе количество микросостояний удваивается, а к их ключам добавляется ключ (l, m), содержащий информацию о расстановке заявок по фазам Н2-терпения. Изобразить диаграмму переходов с сохранением наглядности не представляется возможным, поэтому представим всевозможные уходы из одного микросостояния с ключом (i, j; l, m), где (i, j) - расстановка заявок по фазам обслуживания, i+j=n; (l, m) - по фазам терпения, l+m=k, где k- число заявок в очереди (см. рис. 2). Поясним логику построения схемы. Заявка прибывает в систему с интенсивностью X, застает все каналы занятыми и становится в очередь. В зависимости от типа ее терпения (с вероятностью щ она будет первого типа, в вероятностью u2 - второго) выбирается следующее микросостояние. При уходе заявки по обслуживанию для начала выбирается, какой тип обслуживания требуется головной заявке очереди (с вероятностью y1 - первый тип, в вероятностью y2 - второй) и далее - какой тип терпения имела обслуженная заявка (вероятности пропорциональны доле заявок соответствующих типов терпения в очереди). При уходе нетерпеливой заявки уменьшается количество заявок соответствующего типа терпения. Таким образом, при переходе из одного микросостояния в другое коэффициенты у стрелок последовательно перемножаются. 2. Матрицы переходов и уравнения баланса На основе диаграммы на рис. 1 и схемы переходов на рис. 2 могут быть получены интенсивности переходов в микросостояния (i, j, l, m), необходимые для записи уравнений баланса вероятностей состояний системы. Обозначим через Sj множество всех микросостояний системы, когда в системе находится ровно j заявок (что соответствует j-му ярусу), а через cj - количество элементов в Sj. Определим матрицы интенсивностей переходов: ^j[OjXOj+i] - в Sj (по прибытию заявок), Bj [о/хо;_1] - в Sj_1 (по завершению обслуживания или уходу нетерпеливых), Dj[Oj^Oj] - ухода из микросостояний j-го яруса (диагональная матрица). В квадратных скобках здесь и далее указывается размер матриц. Элемент (i, k) любой из этих матриц представляет интенсивность перехода из i-го состояния j-го яруса в k-е состояние смежного (по переходам рассматриваемого типа) яруса. Поскольку уход нетерпеливых заявок автоматически уменьшает вероятность длинной очереди, количество ярусов диаграммы можно ограничить сравнительно небольшим числом R. Если в результате расчета окажется, что вероятность наличия в системе R заявок велика, необходимо повторить расчет с увеличенным R. Введём векторы-строки %j = (лj1,%j2,...,%ja } вероятностей нахождения СМО в микросостояниях j-го яруса. Теперь можно записать векторно-матричные уравнения баланса переходов между состояниями: j = 1, R. Система уравнений (1), дополненная условием нормировки, даже при ограничении очереди характеризуется чрезвычайно высокой размерностью, и стандартные методы решения систем линейных алгебраических уравнений применительно к ней оказываются неэффективными. Мы развили применительно к ситуации с нетерпеливыми заявками предложенный в [7] и детально проработанный в [8] итерационный метод решения системы (1). Вероятность ухода заявки по нетерпению находилась как (1) (2) к=1 j=0 где %k j - вероятность того, что в очереди к заявок, из которых j - первого типа терпения, находится суммированием вероятностей соответствующих микросостояний. Ценность итерационного метода напрямую зависит от возможности автоматического построения матриц интенсивностей переходов на основе диаграмм. В нашем случае алгоритмы построения матриц относительно очевидны, что следует из рис. 1, 2. Однако на практике программная реализация метода расчета системы MIH2ln-H2 на языке Фортран-90 оказалась нетривиальной и весьма поучительной. Исходными данными для программы являются число каналов и наборы моментов распределений обслуживания и терпения для их Н2-аппроксимации. Ниже представлены результаты расчета системы MIGIn-G при аппроксимации различных исходных распределений обслуживания и терпения гиперэкспонентами второго порядка. 3. Численные результаты Были рассчитаны стационарное распределение заявок в системе MIH2In-H2 и вероятность потери заявки по нетерпению - формула (2) - при следующих исходных данных: - число каналов n = 3; - среднее время обслуживания Ъ\ = 1; - среднее время терпения g = 1,5; - коэффициент загрузки р = 0,5; - предельное число заявок в системе R = 11. Необходимая для расчёта интенсивность входящего потока находится по формуле X = pnIb\. Заметим, что коэффициент загрузки не учитывает уход нетерпеливых заявок, поэтому он теряет определяющую роль и условие р < 1 для существования стационарного режима в данном случае не обязательно. По трём начальным моментам рассчитывались параметры гиперэкспоненты для аппроксимации следующих распределений терпения и обслуживания: детерминированного D (коэффициент вариации v = 0), Эрланга третьего порядка E3 (v = 0,577), показательного М (v = 1). Также был выполнен расчет при ^-распределении с вещественными параметрами (v = 1,5 и v = 2,0). В табл. 1 приведены результаты расчёта стационарного распределения {pj}, j = 0,11, числа заявок в системе MIDI3-E3 численным методом (числ.) и с помощью имитационной модели (ИМ), описание которой имеется в [9]. Заметим, что при аппроксимации D- и Е3-распределений гиперэкспоненциальным параметры последнего принимают комплексные значения, однако на конечный результат это не повлияло. Относительное отклонение рассчитанных численным методом характеристик от полученных на имитационной модели составляет 10%, что принято считать вполне приемлемым [10]. Заметим, что из-за несовершенства датчиков равномерно распределённых случайных чисел имитационная модель не может считаться идеальным эталоном. К тому же численный метод предполагает сохранение ограниченного количества начальных моментов исходных распределений при аппроксимации. Т а б л и ц а 1 Вероятности {p} состояний системы M/D/3-E3 j ИМ Числ. j ИМ Числ. j ИМ Числ. 0 3,912e-2 4,120e-2 4 1,807e-1 1,833e-1 8 1,534e-2 1,420e-2 1 1,206e-1 1,235e-1 5 1,227e-1 1,195e-1 9 5,926e-3 5,987e-3 2 1,935e-1 1,896e-1 6 7,060e-2 6,966e-2 10 1,919e-3 1,878e-3 3 2,147e-1 2,247e-1 7 3,486e-2 3,329e-2 11 9,029e-4 9,164e-4 Рассмотрим вероятности потери «нетерпеливой» заявки (формула (2)), которая является интегральной характеристикой СМО, при других распределениях обслуживания и терпения (табл. 2) и различных коэффициентах загрузки p=kb1ln. В скобках указаны коэффициенты вариации. Т а б л и ц а 2 Вероятность ухода заявки по нетерпению при различных коэффициентах вариации и загрузке Рас-пред. об-служ. Р Распределение терпения D (0) E3 (0,577) М (1) Н2 (2) ИМ Числ. ИМ Числ. ИМ Числ. ИМ Числ. D (0) 0,2 6,84e-3 7,55e-3 8,45e-4 5,22e-4 3,59e-3 3,47e-3 7,27e-3 6,96e-3 0,7 1,10e-1 1,23e-1 3,95e-2 4,18e-2 8,05e-2 8,04e-2 1,23e-1 1,22e-1 1,4 3,54e-1 3,61e-1 2,59e-1 2,72e-1 3,09e-1 3,10e-1 3,58e-1 3,56e-1 E3 (0,578) 0,2 2,43е-2 2,46e-2 9,53-3 9,21e-3 4,00-3 3,98e-3 7,64e-3 7,54e-3 0,7 1,48e-1 1,56e-1 5,17e-2 5,42e-2 8,96e-2 8,95e-2 1,30e-1 1,29e-1 1,4 3,70e-1 3,79e-1 2,63e-1 2,74e-1 3,14e-1 3,15e-1 3,66e-1 3,62e-1 М (1) 0,2 3,97е-1 4,04e-1 2,06e-3 1,93е-3 4,79e-3 4,79e-3 8,40e-3 8,35e-3 0,7 1,95e-1 1,99e-1 6,90e-2 7,18e-2 1,02-1 1,02e-1 1,39-1 1,38e-1 1,4 3,70e-1 3,79e-1 2,69e-1 2,77e-1 3,20e-1 3,20e-1 3,74e-1 3,71e-1 Н2 (1,5) 0,2 7,40e-2 7,25е-2 3,40e-3 3,31е-3 5,88e-3 5,86e-3 9,23e-3 9,22e-3 0,7 2,41e-1 2,42e-1 8,91e-2 9,15e-2 1,16-1 1,16e-1 1,48e-1 1,47e-1 1,4 4,27e-1 4,32e-1 2,79e-1 2,80e-1 3,27e-1 3,25e-1 3,81e-1 3,78e-1 Из табл. 2 следует, что при фиксированном распределении терпения с ростом коэффициента вариации обслуживания вероятность ухода заявки из очереди возрастает. Также с ростом коэффициента загрузки прослеживается снижение влияния вида распределений обслуживания и терпения на вероятность ухода из очереди. Поскольку в реальных организационно-технических системах уходы нетерпеливых заявок, как правило, приводят к негативным последствиям, интересной является задача исследования дробления производительности (т.е. замены одного канала обслуживания несколькими с той же суммарной производительностью) на вероятность потери заявки. С этой целью была рассчитана системы MlDl5-E3 при коэффициенте загрузки р = 0,9. Оказалось, что при замене одного канала двумя исследуемая вероятность уменьшилась в 1,7 раза, тремя - в 2,4 раза, четырьмя - в 3 раза. Заключение Предложена диаграмма переходов для системы MlH2ln-H2, на основе диаграммы составлена Фортран-программа генерации матриц интенсивностей переходов и расчёта стационарного распределения числа заявок и вероятности ухода нетерпеливой заявки. Хорошее согласие результатов, полученных численным методом и с помощью имитационной модели, подтверждает правильность теоретических выкладок и реализующих их программ. Показаны возможности Н2-аппроксимации различных исходных распределений обслуживания и терпения; недопустимость показательной аппроксимации времени обслуживания и терпения в том случае, когда коэффициенты вариации распределений заметно отличаются от единицы и коэффициент загрузки системы невысок; нетривиальный эффект снижения доли нетерпений от дробления производительности. В настоящее время ведется разработка метода расчета временных характеристик. Предложенный метод может быть применен при проектировании колл-центров, служб быстрого реагирования, систем обработки устаревающей информации и т.д.

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