Содержание к диссертации
Введение
Глава 1. Анализ моделей и методов исследования центров обслуживания вызовов 10
1.1 Понятие единого и распределенного центров обслуживания вызовов 10
1.2 Сравнение единых и распределенных ЦОВ 11
1.2.1 Недостатки единых ЦОВ 11
1.2.2 Преимущества распределенных ЦОВ 13
1.3 Необходимость исследований математических моделей ЦОВ 17
1.4 Анализ моделей и методов исследования ЦОВ 19
1.4.1 Модели единых ЦОВ 19
1.4.2 Модели РЦОВ с учетом схем обслуживания вызовов 24
1.4.3 Модели РЦОВ с учетом полноты информации о вызове 28
1.5 Выводы по главе 1 32
Глава 2. Разработка гомогенной модели РЦОВ 34
2.1 Анализ моделей и методов управления командами 34
2.2 Формулировка модели функционирования РЦОВ как работы команды 35
2.3 Гомогенная модель без учета совместной работы команды 36
2.4 Гомогенная модель РЦОВ с учетом совместной работы членов команды 42
2.5 Выводы по главе 2 51
Глава 3. Разработка гетерогенной модели РЦОВ 53
3.1 Гетерогенная модель РЦОВ 53
3.2 Реализация задачи маршрутизации вызовов в РЦОВ при наличии полной информации о ЦОВ 66
3.3 Реализация задачи маршрутизации вызовов в РЦОВ при наличии неполной информации о ЦОВ з
3.4 Решение задачи маршрутизации в ЦОВ на основе общих знаний 71
3.4.1 Маршрутизация в РЦОВ на основе равновесий Нэша 72
3.4.2 Маршрутизация в РЦОВ на основе эффективности по Парето 75
3.4.3 Рефлексивная модель функционирования РЦОВ 76
3.5 Выводы по главе 3 83
Глава 4. Экспериментальное исследование моделей РЦОВ 84
4.1 Разработка компьютерной модели РЦОВ 84
4.1.1 Обобщенная схема модели РЦОВ 84
4.1.2 Поступление вызовов в РЦОВ 87
4.1.3 Реализация распределения вызовов в блоке решений 88
4.1.4 Нахождение заявки в очереди в РЦОВ 89
4.1.5 Реализация обслуживания вызовов в РЦОВ 90
4.1.6 Приемник заявок 91
4.1.7 Выходные и входные параметры разработанной модели РЦОВ 91
4.2 Алгоритмы реализации принятия решений 92
4.2.1 Разработка алгоритма интеллектуального распределения вызовов в РЦОВ между локальными центрами 92
4.2.2 Процесс перераспределения нагрузки в РЦОВ с помощью алгоритма интеллектуального распределения вызовов 99
4.3 Экспериментальное исследование модели РЦОВ 100
4.4 Оценка погрешности алгоритма интеллектуальной перемаршрутизации 109
4.5 Выводы по главе 4 114
Заключение 117
Перечень основных сокращений 119
Список используемой литературы
- Преимущества распределенных ЦОВ
- Формулировка модели функционирования РЦОВ как работы команды
- Реализация задачи маршрутизации вызовов в РЦОВ при наличии полной информации о ЦОВ
- Реализация распределения вызовов в блоке решений
Преимущества распределенных ЦОВ
До сих пор программное обеспечение, на котором работают современные ЦОВ, использует простейшие аналитические модели систем массового обслуживания (СМО) с ожиданием и потерями, которые основаны на базе двух формул Эрланга. С помощью них определяется уровень занятости операторов центра в определенное время суток. Также с помощью математических моделей строятся разные алгоритмы перенаправления заявок, благодаря которым принимается решение о перемаршрутизации вызова к определенному оператору. Создание математических моделей - неотъемлемая часть управления работой центров обслуживания вызовов.
В процессе соперничества компаний и усовершенствования математических моделей увеличиваются требования к качеству обслуживания заявок клиентов. Следует отметить, что в таких условиях при планировании ЦОВ должна реализовываться многоуровневая иерархическая архитектура данной системы, которая может работать с разноприоритетными входящими потоками заявок, в условиях неопределенности поведения внешней среды и с различным уровнем квалификации входящих в ЦОВ операторов. Очень важно обеспечить гарантированные значения показателей качества обслуживания потоков вызовов в call-центре при условии априорной неопределенности их интенсивностей при определенном количестве операторов с разной квалификацией [5].
И, естественно, использование математических расчетов необходимо на каждом уровне эксплуатации ЦОВ, даже на этапах проектирования. И известно, что сложное планирование задач ЦОВ ни одна компьютерная система только лишь на основе математических расчетов не сможет полностью автоматизировать.
В настоящее время становится обязательным, чтобы центр обслуживания вызовов мог работать круглые сутки, без выходных, качественно реализуя необходимую концепцию обслуживания и, соответственно, обеспечивая эффективное предоставление услуг своим клиентам. Для этого часто арендуются операторы в других часовых поясах, и используются модели распределённых ЦОВ.
Некоторая часть задач в функционировании центров обслуживания вызовов, такие как маршрутизация заявок, до конца автоматизирована. Однако известно, что вначале должно быть принято определенное решение, с помощью которого был бы реализован алгоритм маршрутизации поступивших в ЦОВ заявок. Очевидно, что понимание реализации математических методов в работе центров обслуживания вызовов помогает принимать более обоснованные и взвешенные организационные решения. Это касается и долгосрочных решений о структуре центра. Математические методы здесь направлены на помощь в выработке количественных решений, которые касаются алгоритмов обработки заявок, многоканального управления, принципов управления маршрутизацией заявок и т.д. [8].
Использование математических моделей в проектировании и реализации процессов работы ЦОВ является неоднократный процесс улучшения, который не может закончиться моделированием входящих в него показателей всего один раз. Несколько раз повторяются и модель построения, и сбор, и анализ данных, и реализация. Между установленными требованиями и исходными данными какого-либо ЦОВ именно математическое моделирование может показать разные ситуации для нахождения компромиссного решения [9]. В связи с этим весьма актуальным является разработка таких математических моделей и определенных методов их расчета ЦОВ, позволяющих на стадии системных и предпроектных исследований просто и легко получать количественные характеристики любых схем обслуживания поступающих заявок в РЦОВ с целью выбора наиболее оптимальной по определенным показателям.
В последнее время появился ряд зарубежных и отечественных исследований и публикаций по функционированию ЦОВ, где предлагаются разные модели и схемы обслуживания вызовов. Однако решение проблемы не найдено, и создание новых, более усовершенствованных моделей и принципов исследования ЦОВ актуально, особенно для распределенных схем обслуживания.
Это такие модели ЦОВ, которые в соответствие с параметрами, введенными Кендаллом, обозначаются как М/М/п, либо М/М/п/п, в которых поступающий поток заявок пользователей подчиняется закону распределения Пуассона, время обслуживания заявок распределено по экспоненциальному закону, а в системе независимо друг от друга могут работать п операторов одновременно. Данные модели подробно рассмотрены в большом числе работ отечественных и зарубежных авторов [3, 17, 24 - 28]. В ряде последних работ [3, 17] было показано, что «классические» математические модели уже не могут работать по принципам современных мультисервисных ЦОВ (МЦОВ).
Такие модели были рассмотрены в работах [17, 29 - 38]. Это такие модели, в которых определенная часть клиентов оставляет очередь сразу после поступления в неё, другая часть пользователей может покинуть очередь в процессе ожидания обслуживания. Эти модели не учитывают нетерпеливость клиентов, а следовательно, дают весьма сомнительные сведения. В [38] была рассмотрена модель с нетерпеливостью пользователей и с учетом отказов от услуг. Данная модель может быть описана как MIMIN+M, где N - число операторов. К обозначениям Кендалла добавляется знак «+» и буква, которая, в свою очередь, характеризует распределение времени нетерпеливости клиентов. Такая модель показана на рисунке 1.4.
Формулировка модели функционирования РЦОВ как работы команды
Исследуем множество центров обслуживания вызовов К={\, 2, ..., и}, входящих в состав РЦОВ. Отметим, что работа локального /-го ЦОВ будет определяться выбором оптимального действия (операции) х( (обслуживание вызова операторами данного ЦОВ или маршрутизация его для обслуживания в другие центры), которое определено выражением СІ\ХІ,ГІ), означающим временные затраты на обслуживание вызова в /-ом центре, где гг О - знания /-го ЦОВ о том, какое время было потрачено другими локальными центрами на обслуживание данного вызова.
Главной задачей совместного функционирования всех центров в составе РЦОВ является следующая задача: гарантия минимальной суммарной величины временных затрат, необходимых для обслуживания поступающих вызовов:
Пусть знания о загруженности всех локальных ЦОВ в составе распределенного описываются вектором обслуживания вызовов г = (rj, г2, ..., гп), следовательно, исследуя выбор оптимального действия для каждого из локальных ЦОВ, можно найти наилучший вектор действий (шагов) всего распределенного ЦОВ: действия по перенаправлению вызовов отдельных ЦОВ при определенном знании г, где f; и ґ. - соответственно время обслуживания вызова в z-ом или -ом центрах, включающее и время ожидания в очереди. Исследуем два основных варианта информированности локальных ЦОВ о загруженности других центров обслуживания вызовов в составе РЦОВ [81, 83]: 1) имеется определенное представление (знание) rt- О о загруженности /-го ЦОВ и любого другого ЦОВ, который выбирается из состава РЦОВ случайным способом; 2) имеется определенное знание Гу„ 0 о загруженности всех центров, входящих в РЦОВ /, j, neN.
При наличии определенных знаний о загруженности других ЦОВ каждый локальный центр, входящий в состав распределенного, может прогнозировать, какие именно действия по перенаправлению заявок выберут другие центры и, исходя из этого, может прогнозировать величину их суммарных значений временных затрат на обслуживание вызовов.
Исследуем группу возможных действий /-го локального ЦОВ, примем, что XJJGN. В исследуемой модели обслуживания вызовов /-ым ЦОВ в историю игры будет входить 5 вариантов информированности отдельных ЦОВ [82]: 1) решение по перенаправлению поступившего вызова, принятое /-ым ЦОВ, будет зависеть от других решений, принятых каждым из локальных центров в составе РЦОВ: Xi = Г \Х\- Х2- ---- Хп) 2) решение по перенаправлению поступившего вызова, принятое /-ым ЦОВ, будет зависеть от временных затрат на обслуживание вызовов каждого из центров сети: x.=F(q,c2,...,c„); 3) решение по перенаправлению поступившего вызова, принятое z-ым ЦОВ, будет зависеть от суммы временных затрат на обслуживание вызовов всех центров в составе РЦОВ: 4) решение по перенаправлению поступившего вызова, принятое z-ым ЦОВ, будет зависеть от решений о перемаршрутизации, принятых каждым из локальных центров в составе РЦОВ и временных затрат на обслуживание пришедшей заявки каждого из ЦОВ:
Следует заметить, что последний вариант несет большее количество информации, нежели предпоследний. Предпоследний, в свою очередь, несет большее количество информации, нежели третий, и т.д. Выбор определенного варианта информированности из выше предложенных - есть главный принцип организации функционирования всего распределенного ЦОВ [82, 84].
Исследуя два варианта знаний о загруженности rt- и г п, а также выше перечисленные пять случаев по принятию решений о перенаправлении вызовов каждым из ЦОВ, получим десять типов моделей функционирования распределенного ЦОВ (таблица 2.2). Таблица 2.2 Типы моделей функционирования РЦОВ
Берем в расчет, что на каждом этапе функционирования РЦОВ все локальные центры принимают решения о перемаршрутизации, ориентируясь на знания о занятости других ЦОВ, которые они получили в предыдущий период времени. Здесь отсутствует только тот вариант, где принятие решений о перемаршрутизации было реализовано, опираясь на всю предысторию поступления и обслуживания вызовов.
Пусть W. (х Л - текущее состояние загруженности /-го ЦОВ с определенным периодом сбора информации о загрузке операторов каждого ЦОВ t и 1{ -состояние загруженности других центров в РЦОВ за тот же период t,t= 0, 1, 2, ...
Отметим, что в момент времени t z-ый ЦОВ имеет состояние загрузки Ii и оно будет меняться в зависимости истории поступления вызовов [83]. Определенное суждение при выборе решения о перемаршрутизации вызова у каждого ЦОВ, когда его действия зависят от предыдущего шага, называется «гипотезой индикаторного поведения» [83]. Действие по перенаправлению вызова, которое было бы наилучшим при обстановке на предыдущем шаге: I?x=rt+/tty:( t)-r?\,t = \,2,...,ieN (2.14) где li - состояние ЦОВ в следующий период времени t+\, Yi - некоторый коэффициент, составляющие которого входят в промежуток [0;1], означающий что это есть "величины шагов" к минимальным временным затратам на обработку поступившего в ЦОВ вызова и имеющие необходимые особенности, которые нужны для сходимости формулы (2.14) [81].
Из-за того, что знания каждого локального ЦОВ могут определяться конечным значением величин rtj или rjjn, i,j,nE N, то под выражением (2.14) следует иметь в виду "векторное" определение закона вариации значений величин информированности. В распределённых центрах выбор одного из ЦОВ при перенаправлении вызова ему на обслуживание согласован с иерархией взаимных представлений о загруженности каждого локального ЦОВ друг о друге (предысторией ранее обслуженных вызовов).
В исследуемой модели РЦОВ каждый локальный центр имеет особую структуру информированности о загрузке друг друга, что решения о перенаправлении, выбираемые данными ЦОВ в зависимости от их знаний, находятся с помощью формул (2.10) или (2.13).
Реализация задачи маршрутизации вызовов в РЦОВ при наличии полной информации о ЦОВ
В данной главе рассмотрены гетерогенные модели РЦОВ, а также реализация задач маршрутизации вызовов в РЦОВ при наличии полной информации о каждом локальном ЦОВ и при наличии неполной информации обо всех центрах. Рассмотрено решение задач маршрутизации вызовов на основе равновесий Нэша, на основе эффективности по Парето и рассмотрена рефлексивная модель функционирования РЦОВ. Разработаны теоретико-игровые модели распределенного ЦОВ.
Можем отметить, что основной характеристикой рефлексивных игр является то, что каждый ЦОВ имеет свои собственные представления о загруженности других локальных центров, представлениях других ЦОВ и т.д. Анализ рефлексивных моделей функционирования РЦОВ, а также анализы моделей ЦОВ на основе равновесий Нэша и на основе эффективности по Парето дают возможность моделировать поведение каждого ЦОВ в составе РЦОВ и исследовать зависимость выигрышей каждого ЦОВ. Проведенный в данной главе анализ также дает возможность исследовать результат функционирования всего РЦОВ в целом.
Использование теоретико-игровых моделей распределенных ЦОВ на практике позволяет повысить качество обслуживания вызовов, уменьшить количество потерянных вызовов, снизить загрузку каждого центра, причем этот эффект повышается с увеличением информированности центров о состоянии друг друга.
Как уже описывалось выше, РЦОВ представляет собой сеть массового обслуживания. В качестве элементов такой сети выступают многоканальные СМО. На вход в такую систему поступают не только собственные вызовы, но и вызовы от других центров (рисунок 4.1). Поступившие вызовы и, соответственно, обслуживающие их операторы являются главными элементами модели распределенного ЦОВ. Пришедшие из бесконечного источника в систему заявки могут сразу попасть к оператору (при отсутствии очереди из других заявок), либо могут встать в очередь (при наличии других вызовов и если операторы заняты). Для качественного обслуживания поступивших в систему вызовов необходимо обеспечить минимально возможное время ожидания в очереди, для чего будет необходимо оптимальное распределение поступающей в РЦОВ нагрузки с применением перемаршрутизации поступивших заявок, а также для этого потребуется определенное количество операторов в каждом ЦОВ. Таким образом, необходимо организовать работу всех операторов РЦОВ, как единой команды [80]. Аналитические модели могут быть реализованы только для простых детерминированных алгоритмов управления. Сложные модели работы РЦОВ, особенно на основе теории игр можно исследовать только методом имитационного моделирования.
Инженерный программный пакет MATLAB включает в себя множество средств для построения моделей в самых разных предметных областях.
Для решения поставленной задачи был выбран инструмент, входящий в состав Simulink - библиотека SimEvents [116 - 120]. Эта библиотека представляет собой набор блоков Simulink, предназначенных для моделирования систем дискретных событий (Discrete Event System, DES). Эта библиотека обладает рядом полезных свойств и функций [117, 120, 121]: 1. В состав библиотеки входят модули, описывающие очереди с различными дисциплинами обслуживания (в т. ч. с управляемыми приоритетами); 2. Имеются блоки для описания различных (в т. ч. множественных) каналов обслуживания; 3. Для описания заявок библиотека предусматривает особый тип данных - сущности, которые позволяют не только рассматривать каждую заявку как самостоятельный цельный предмет интереса, но и наделять его особыми свойствами (атрибутами).
Перечисленные особенности определяют выбор библиотеки SimEvents в качестве основного инструментального средства (наряду с MATLAB и Simulink) для решения поставленной задачи.
Для построения данной модели воспользуемся нисходящим подходом к проектированию. Сначала обозначим наиболее общие и очевидные составные части будущей модели, а затем по мере понимания и необходимости будем детализировать каждый из них по отдельности.
Согласно поставленной задаче моделируемая система в первом приближении должна представлять собой блок ("черный ящик"), имеющий вход для поступающих заявок и выход для обслуженных. В состав этого блока должны, очевидно, входить как минимум пять подблоков - собственно источник заявок, блок решений, канал обслуживания и предшествующая ему очередь, а также приемник заявок [120].
Описанные требования позволяют в общих чертах обозначить функциональную схему проектируемой модели, а возможность использования иерархических блоков (подсистем) в Simulink - начать составление этой схемы (рисунок 4.1).
Основываясь на рисунке 4.1, составим схему проектируемого РЦОВ, состоящего из 5-ти ЦОВ, непосредственно в среде MATLAB (рисунок 4.2). Моделирование будет запущено в то время, когда операторы свободны, и вызовы полностью отсутствуют. Заданными входными величинами разработанной модели будут являться следующие величины: заданные интенсивности поступления вызовов в систему лг и заранее заданные интенсивности обслуживания МІ , также среднее время терпеливости пользователей w, заданные вероятности поступления собственных вызовов в
ЦОВ р1 и перенаправленные от других локальных ЦОВ Vi, число операторов в каждом из пяти центров Ки и, естественно, время прекращения процесса моделирования Т. Случайные события, происходящие в разработанной системе, будут моделироваться благодаря генератору случайных чисел.
Реализация распределения вызовов в блоке решений
Для оценки погрешности работы предложенного алгоритма интеллектуальной перемаршрутизции необходимо рассмотреть показатели функционирования каждого центра из состава РЦОВ. Проведем эксперимент с использованием одного алгоритма для разных ЦОВ с разным количеством операторов. Данные для эксперимента оставим прежними (таблица 4.1).
На рисунке 4.19 представлены зависимости количества потерянных вызовов от загрузки для разных центров при полной информированности и при её отсутствии. Видно, что при полной информированности центров о состоянии друг друга, количество потерянных вызовов даже при больших загрузках /7 0,95 не превышает трёх из 7000 вызовов, поступивших в сутки. Как показано на графике, эти данные справедливы для каждого ЦОВ из состава РЦОВ. Однако ж, при отсутствии какой-либо информации друг о друге, количество потерянных вызовов при той же загрузке составит 887 вызовов для первого ЦОВ, 853 вызова для второго ЦОВ и 841 вызов для третьего ЦОВ, 800 вызовов для четвертого ЦОВ и 779 вызовов для пятого ЦОВ. Получим, что при использовании алгоритма интеллектуальной перемаршрутизации вызовов даже при отсутствии какой-либо информации о состоянии других центров, количество потерянных вызовов в сутки будет варьироваться в интервале от 11,13% до 12,67%. Отметим, что разница между потерянными вызовами при одинаковой загрузке /7 = 0,95 для разных ЦОВ по предложенному алгоритму составит около 100 вызовов, а это не более 1,5%. Соответственно, получим, что эксперименты целесообразно проводить только для одного ЦОВ из состава РЦОВ, поскольку показатели функционирования по одному и тому же алгоритму не будут существенно отличаться.
Зависимости количества потерянных вызовов от загрузки для разных ЦОВ при полной информированности и при её отсутствии
Рассмотрим работу алгоритма на таких показателях, как длина очереди при наличии неполной информированности для разных ЦОВ в составе РЦОВ и оценим погрешность работы алгоритма. Из 5-ти выше предложенных вариантов информированности выберем неполную информированность, когда известны текущее состояние загрузки каждого ЦОВ W ix A q- средние длины очереди во всех ЦОВ, / - количество нетерпеливых клиентов в предыдущий период времени, время ожидания в очереди которых превысило 180 с, а также известно состояние
ЦОВ в предыдущий период времени /,- . Данные по информированности будут одинаковы для пяти центров. По-прежнему используем алгоритм, предложенный на рисунках 4.8 и 4.9. На рисунке 4.20 представлен результат данного эксперимента.
На рисунке 4.20 представлен интервал загрузок р = [0,75; 0,97], потому что характеристики разных ЦОВ при одинаковой информированности с использованием одного алгоритма на интервале уО=[0,5; 0,75] будут совпадать. Отметим, что даже при больших загрузках р = [0,85; 0,97] и неполной информированности длина очереди при использовании разработанного алгоритма составит не более 4-х вызовов. Погрешность работы алгоритма составит не более 2%.
С помощью имитационного моделирования убедимся в сходимости средних результатов к теоретическим значениям выигрышей, основываясь на работе [130]. Сначала найдем оптимальные по Нэшу решения (по пункту 3.4.1 главы 3) в смешанных стратегиях, далее оценим средние возможные результаты игры при случайном перемешивании стратегий с найденными оптимальными по Нэшу пропорциями (среднее время обслуживания вызовов в каждом ЦОВ при фиксированной загрузке и при определенной информированности) [130, 132, 133]: подтверждают сходимость средних результатов игры всех центров к теоретическим значениям. Как видно из приведенных данных, безусловная устойчивая сходимость наблюдается после числа повторений игры п от 375 до 500, хотя при рассматриваемой статистической имитации хорошее совпадение с теоретическими расчётами наблюдается также при и=50 и и=280 в случае ЦОВз и ЦОВ4, но это можно считать случайным совпадением.
В этой главе представлены результаты имитационного моделирования с применением разработанного алгоритма реализации принятия решений о маршрутизации. Именно подтверждение эффективности разработанного алгоритма и оценка влияния перенаправления заявок по данному алгоритму на ключевые показатели эффективности работы всего РЦОВ и было главной целью имитационного моделирования.
Экспериментальное исследование модели РЦОВ на основе компьютерного моделирования показало, что применение алгоритма интеллектуального управления входящей нагрузкой ЦОВ повышает качество работы по обслуживанию вызовов, уменьшить количество потерянных вызовов, снизить загрузку каждого центра, причем этот эффект повышается с увеличением поступающей нагрузки. С помощью проведенных экспериментов доказано, что чем больше информированность ЦОВ друг о друге, тем наиболее верным становится выбор оптимального действия хігЛ по перенаправлению вызовов и тем меньше время ожидания в очереди. При больших загрузках р в случае полной информированности среднее время ожидания вызовов в очереди составит не более 10 секунд, а длина очереди не более двух вызовов, количество потерянных вызовов сократится практически до 0. В то же время при отсутствии информированности о параметрах других ЦОВ длина очереди при большой загрузке составляет более 14 вызовов, время ожидания более 180 с, количество потерянных вызовов возрастет до 887 из 7000 поступивших в сутки. Доказано, что 20 проведенных серий по 10 испытаний в каждой с точки зрения инженерной практики можно считать достаточно точной. Исследована сходимость средних результатов игры всех центров к теоретическим значениям. Показано, что безусловная устойчивая сходимость наблюдается после числа повторений игры п от 375 до 500.
Разработанный в главе алгоритм позволяет улучшить качественные показатели работы всего РЦОВ в целом, уменьшить задержки при обслуживании заявок и сократить загрузку каждого локального центра, что приведет к увеличению эффективности функционирования всего РЦОВ.
