ОПТИМИЗАЦИЯ МАРКОВСКИХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С ОТКАЗАМИ В СИСТЕМЕ MATLAB
Журнал: ВЕСТНИК АСТРАХАНСКОГО ГОСУДАРСТВЕННОГО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА. СЕРИЯ: УПРАВЛЕНИЕ, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА
№ 1
, 2018
Рубрики: МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
Авторы:
1.
Национальный исследовательский Мордовский государственный университет им. Н. П. Огарева
(кандидат технических наук, доцент; доцент кафедры автоматизированных систем обработки информации и управления)
Россия
Россия
2.
Мордовский государственный университет им. Н. П. Огарева
Тип:
Статья
Страницы:
с 112
по 120
Статус:
Опубликован
Получено:
05.01.2018
Одобрено:
25.01.2018
Опубликовано:
25.01.2018
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 65.012.122
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 65.012.122
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
Язык материала:
русский
Ключевые слова:
система массового обслуживания, вероятность отказа, относительная пропускная способность, оптимизация, минимизация, максимизация, целевая функция, модельное время, MATLAB
Аннотация (русский):
Рассматривается задача оптимизации многоканальной марковской системы массового обслуживания с отказами в условиях большой загрузки системы, что наблюдается в реальных условиях функционирования многих систем массового обслуживания различного назначения. Задача оптимизации сводится к минимизации вероятности отказов в обслуживании, которая соответствует максимизации относительной пропускной способности системы. Для решения задачи использовалась система MATLAB R2016b, в которой имеются средства (функции) для минимизации целевых функций многих переменных с ограничениями. Естественные ограничения накладываются на параметры системы - интенсивность входного потока и интенсивность обслуживания, которые являются положительными величинами по смыслу функционирования систем массового обслуживания. Полученные результаты могут быть использованы для тестирования моделей систем массового обслуживания с отказами при пиковых, значительных нагрузках.
Рассматривается задача оптимизации многоканальной марковской системы массового обслуживания с отказами в условиях большой загрузки системы, что наблюдается в реальных условиях функционирования многих систем массового обслуживания различного назначения. Задача оптимизации сводится к минимизации вероятности отказов в обслуживании, которая соответствует максимизации относительной пропускной способности системы. Для решения задачи использовалась система MATLAB R2016b, в которой имеются средства (функции) для минимизации целевых функций многих переменных с ограничениями. Естественные ограничения накладываются на параметры системы - интенсивность входного потока и интенсивность обслуживания, которые являются положительными величинами по смыслу функционирования систем массового обслуживания. Полученные результаты могут быть использованы для тестирования моделей систем массового обслуживания с отказами при пиковых, значительных нагрузках.
Ключевые слова:
система массового обслуживания, вероятность отказа, относительная пропускная способность, оптимизация, минимизация, максимизация, целевая функция, модельное время, MATLAB
система массового обслуживания, вероятность отказа, относительная пропускная способность, оптимизация, минимизация, максимизация, целевая функция, модельное время, MATLAB
Система массового обслуживания (СМО) с отказами - достаточно распространенный тип систем массового обслуживания. Примерами СМО с отказами являются автоматическая телефонная станция (АТС), вычислительный центр с несколькими взаимозаменяемыми ЭВМ (компьютерами), справочные службы и пр. Эти и другие процессы, которые могут быть представлены в виде моделей СМО, достаточно хорошо описываются теорией марковских СМО [1, 2]. Для марковских СМО приемлемо их аналитическое моделирование [3-7]. В частности, для марковских СМО с отказами получены аналитические зависимости (формулы) для расчета таких показателей работы системы, как вероятность отсутствия требований в системе, вероятность отказов, вероятность нахождения в системе какого-то числа требований и т. д. Эти аналитические зависимости включены во многие учебные пособия, например в [1-7]. Вопросы оптимизации СМО рассматриваются в работах [8-13]. Постановка задач оптимизации СМО может быть самой различной. В рамках нашего исследования задача оптимизации рассматривается как задача минимизации вероятности отказов, которая выступает целевой функцией двух переменных, параметров СМО - интенсивности l входного пуассоновского потока требований и интенсивности m экспоненциального обслуживания. Необходимо выбрать такое число приборов обслуживания, которое обеспечивает минимальную вероятность отказов СМО и, соответственно, максимальную относительную пропускную способность. Ясно, что при неограниченном увеличении числа приборов обслуживания вероятность отказов будет стремиться к нулю. Однако на практике это не является приемлемым условием. Очевидно, что следует искать компромисс, который, собственно, и выливается в задачу оптимизации, решение которой стало целью нашего исследования. Задача анализировалась в системе MATLAB и полученные результаты выносятся на обсуждение в предлагаемой статье, которую можно рассматривать как продолжение наших работ [8, 9]. В отличие от решений, приведенных в [8, 9], нами была применена условная оптимизация, связанная с положительностью параметров системы l и m. Кроме того, решение задачи рассматривается как процесс моделирования, который позволяет прослеживать изменение параметров СМО при минимизации вероятности отказов, когда они имеют динамический характер до значений установившегося режима. При оптимизации как инструменте моделирования реальных систем следует учитывать модельное время, которое может заметно влиять на условия работы стандартных алгоритмов минимизации и, соответственно, на соответствующие функции системы MATLAB. Для малых значений параметров системы их можно увеличить путем перевода модельного времени из минут в секунды и т. д. Математическая модель системы массового обслуживания с отказами В соответствии с символикой Кендалла СМО с отказами обозначается как M/M/m: первые две буквы означают пуассоновский входной поток требований и их экспоненциальное обслуживание, третья буква соответствует числу приборов обслуживания, включенных параллельно [1-7]. Размеченный граф состояний многоканальной СМО с отказами приведен на рис. 1. Рис. 1. Граф состояний СМО с отказами Считая, что в системе существует стационарный режим, можно определить вероятности состояний системы на основе равенства потоков вероятностей на границе двух состояний, а также условие нормировки: сумма несовместных вероятностей равна единице. Стационарная вероятность произвольного состояния Pk определяется по формулам где l - интенсивность входного пуассоновского потока требований; m - интенсивность обслуживания одним прибором по экспоненциальному закону; m - число приборов обслуживания, m ≥ 1; P0 - вероятность отсутствия требований в системе. Значения интенсивности l и m являются положительными величинами по смыслу функционирования любой СМО. Отказ в обслуживании начинается, когда все приборы (каналы) заняты. Вероятность отказа обозначим как Pm. Расчет вероятности отказа выполняется по формуле Вероятность P0 - величина ограниченная, поэтому предельное значение вероятности отказов Pm будет определяться отношением степенной функции (числителем) к факториалу числа от количества приборов обслуживания. Используя правило Лопиталя, можно показать, что при m ® ¥ вероятность отказов будет равна нулю. Следовательно, задаваясь допустимой величиной вероятности отказов, можно определить соответствующее значение числа приборов обслуживания. Пропускную способность СМО определяют с помощью таких характеристик, как относительная пропускная способность Q и абсолютная пропускная способность А. Относительная пропускная способность Q определяет долю обслуженных требований, поэтому она определяется как единица минус вероятность отказа. Абсолютная пропускная способность определяет количество обслуженных требований в единицу времени. Постановка задачи оптимизации В задачу оптимизации входит минимизация вероятности отказа и, соответственно, максимизация относительной пропускной способности при условии, что значения интенсивности входного потока и обслуживания должны быть больше нуля. В общем виде вероятность отказа можно определить как целевую функцию трех переменных - интенсивности входного потока, интенсивности обслуживания и числа приборов обслуживания: Как отмечалось выше, при m ® ¥ вероятность отказа стремится к нулю. Однако здесь введем условие: поставим задачу определения значений интенсивности входного потока и интенсивности обслуживания в результате минимизации вероятности отказа. Предполагается, что при изменении числа приборов обслуживания и выполнения условной минимизации значений вероятности отказов СМО значения параметров l и m системы будут также изменяться. При этом необходимо найти их установившиеся значения, соответствующие минимальному числу приборов обслуживания с минимальной вероятностью отказов и, соответственно, максимальной относительной пропускной способностью. Если положить, что вероятность отказов СМО непрерывно зависит от ее аргументов, включая число приборов обслуживания, то тогда неизбежно число приборов обслуживания станет не целым, а вещественным числом, поэтому количество приборов обслуживания СМО следует принять в качестве параметра задачи оптимизации. Решение задачи оптимизации Для решения задачи оптимизации с ограничениями используем функцию fmincon системы MATLAB R2016b, которая предназначена для решения задач нелинейного программирования с ограничениями. Для применения функции fmincon следует задать вектор начальных условий и границы изменения аргументов - интенсивности входного потока l и интенсивности обслуживания m. В качестве ограничений на изменения этих аргументов примем системные величины: eps = 2-52 и плюс бесконечность, которую определяют как [] в аргументах функции fmincon. В опциях этой функции обычно задается алгоритм оптимизации в виде строкового литерала. Исследования показали, что для решаемой задачи оптимизации должны использоваться следующие алгоритмы: SQP-алгоритм (Sequential quadratic programming - последовательное квадратичное программирование) и active-set. Алгоритм active-set минимизирует целевую функцию на каждой итерации активного множества (подмножество ограничений, которые локально активны) до тех пор, пока не будет достигнуто решение [14]. Следует заметить, что не на все начальные условия поиска будет найдено решение с помощью функции fmincon - в случае алгоритма SQP не удается перехватить исключение, а в случае алгоритма active-set это возможно с последующей коррекцией вектора начальных условий. Прежде всего это касается большой приведенной нагрузки, т. е. когда отношение l/m велико и функция fmincon с алгоритмом active-set может возвращать NaN (Not a Number - не число), а с алгоритмом sqp процесс оптимизации прерывается с выводом сообщения об ошибках. Именно поэтому в случае использования алгоритма active-set остается определить величину изменения m и последовательно увеличивать значение интенсивности обслуживания до того уровня, когда возобновится процесс оптимизации функцией fmincon. Выбор алгоритма оптимизации для функции fmincon остается за пользователем, который должен знать величину отношения l к m. При небольшой величине приведенной нагрузки предпочтение следует отдать алгоритму SQP. Следует также отметить зависимость результатов решения задачи оптимизации от заданной вычислительной точности. Схема алгоритма решения задачи минимизации вероятности отказов марковской СМО с отказами, позволяющая составить о нем общее представление, показана на рис. 2. Рис. 2. Схема алгоритма оптимизации СМО с отказами В представленном алгоритме вектор начальных условий обозначен как x0 - одномерный массив из двух значений - l и m, которые, возможно, получены из экспериментальных данных. Например, в сотовых компаниях существует отдел биллинга, который фиксирует количество вызовов в единицу времени, т. е. интенсивность входного потока вызовов. Допустимая величина приведенной нагрузки r определяется экспериментально в случае применения алгоритма sqp. В случае выбора алгоритма оптимизации active-set предусматривается оценка решения, возвращаемого функцией fmincon. Если решение не найдено, то это проверяется библиотечной функцией MATLAB isfinite, которая возвращает истину для вещественного типа данных, а для данных типа NaN, inf (infinity - бесконечность) она возвращает нуль, т. е. «ложь». В этом случае осуществляется увеличение параметра m с целью уменьшения приведенной нагрузки r = l/m. После найденного оптимального решения выполняются операции построения пояснительных диаграмм. Численные эксперименты Приведем некоторые значения параметров СМО с отказами, полученные в результате моделирования, выполненного в процессе оптимизации СМО с отказами: - интенсивность входного потока λ = 39,012; - интенсивность обслуживания одним прибором μ = 0,6; - приведенная интенсивность потока заявок (интенсивность нагрузки канала) ρ = 65,02; - вычислительная точность: 2,220446e-16; - вектор начальных условий x0 = [39,012; 0,6]; - расчетная интенсивность λ = 39,0119972; - расчетная интенсивность μ = 0,6001794; - оптимальное число каналов обслуживания: 120; - максимальное значение вероятности отказа: 3,584473e-09; - минимальное/максимальное значение Q: Qmin = 0,9999999; Qmax = 1,0000000. Изменения параметров системы в процессе оптимизации показаны на рис. 3. Рис. 3. Изменение параметров СМО в процессе оптимизации Начальный процесс изменения параметров СМО на рис. 3 не показан в целях большей наглядности основного процесса оптимизации. Приведенные результаты получены при установке в опции функции fmincon алгоритма оптимизации active-set. Расчет оптимального количества приборов обслуживания при минимальной вероятности отказов наиболее удобно определять по зависимости приведенной нагрузки от числа приборов обслуживания, для каждого из которых величина вероятности отказов не превосходит величины 3,584473e-09. Диаграмма изменения приведенной нагрузки показана на рис. 4. Рис. 4. Изменение приведенной нагрузки СМО с отказами Как видно из рис. 4, для определения оптимального количества приборов обслуживания с минимальной вероятностью отказов следует определить скачок зависимости приведенной нагрузки, когда параметры системы l и m практически не меняются. Для этого достаточно обработать соответствующие массивы данных, полученные в результате моделирования процесса оптимизации СМО с отказами. Следует заметить, что результаты оптимизации для приведенных входных данных зависят от принимаемой вычислительной точности: в частности, если вычислительную точность установить в виде double(eps('single')), то оптимальное число приборов обслуживания станет 102, т. е. уменьшится. Для справки: при использовании алгоритма sqp оптимальное число приборов обслуживания было равно 136. При увеличении величины l до значения 49,012 при неизменной величине m = 0,6 процесс оптимизации прерывался, если использовался алгоритм sqp. При тех же параметрах, в случае применения алгоритма active-set, процесс (с учетом алгоритма на рис. 2) выполнялся успешно. Предлагаемый подход к оптимизации СМО с отказами может использоваться не только при больших значениях приведенной нагрузки (приведенной интенсивности потока заявок), но и при других значениях l и m. Например, l может быть меньше m, или l и m могут быть равны между собой. Такой возможный случай при равенстве l и m показан на рис. 5. Рис. 5. Процесс с равными l и m в СМО с отказами Во всех рассмотренных случаях процессы оптимизации получены при минимальной вероятности отказов при изменении числа приборов обслуживания от 1 до 170. Заключение В ходе решения задачи оптимизации марковской СМО с отказами с помощью функции fmincon системы инженерных и математических вычислений MATLAB (R2016b) получены следующие результаты: - показано, что в качестве вектора начальных условий для минимизации вероятности отказов следует задавать параметры системы, которые присущи реальным СМО, в частности системам с отказами; - приведена схема алгоритма оптимизации СМО с отказами, которая не вызовет затруднений при разработке программного алгоритма, прежде всего в системе MATLAB. Результаты исследования могут быть использованы для тестирования моделей СМО с отказами при пиковых нагрузках, а также и в других случаях, определяемых соотношением параметров системы l и m
1. Шелухин О. И. Моделирование информационных систем. М.: Горячая линия - Телеком, 2016. 516 с.
2. Таранцев А. А. Инженерные методы теории массового обслуживания. СПб.: Наука, 2007. 175 с.
3. Афонин В. В., Федосин С. А. Моделирование систем: учеб.-практ. пособие. М.: ИНТУИТ; БИНОМ, Лаборатория знаний, 2016. 231 с.
4. Афонин В. В., Никулин В. В. Методы моделирования и оптимизации с примерами на языке С/С++ и MATLAB: Ч. 1: Методы моделирования: учеб. пособие. Саранск: Изд-во Мордов. ун-та, 2015. 184 с.
5. Афонин В. В., Никулин В. В. Методы моделирования и оптимизации с примерами на языке С/С++ и MATLAB: учеб. пособие. Ч. 1. Методы моделирования. Саранск: Изд. Афанасьев В. С., 2017. 188 с.
6. Афонин В. В., Мурюмин С. М., Федосин С. А. Основы анализа систем массового обслуживания: учеб. пособие. Саранск: Изд-во Мордов. ун-та, 2003. 236 с.
7. Гефан Г. Д. Марковские процессы и системы массового обслуживания: учеб. пособие. Иркутск: ИрГУПС, 2009. 80 с.
8. Афонин В. В., Никулин В. В. Методы моделирования и оптимизации с примерами на языке С/С++ и MATLAB: Ч. 2. Методы безусловной оптимизации: учеб. пособие. Саранск: Изд. Афанасьев В. С., 2017. 231 с.
9. Афонин В. В. Оптимизация марковской системы массового обслуживания с отказами // Журнал научных и прикладных исследований. 2017. № 1. С. 100-103.
10. Балясников В. В., Богданов А. А., Маслаков В. П., Староселец В. Г. Многокритериальная оптимизация транспортных систем массового обслуживания // Транспорт Российской Федерации. 2012. № 6 (43). С. 73-76.
11. Бояршинова И. Н., Исмагилов Т. Р., Потапова И. А. Моделирование и оптимизация работы системы массового обслуживания // Фундаментальные исследования. 2015. № 9 (ч. 1). С. 9-13.
12. Самочернова Л. А., Петров Е. С. Оптимизация системы массового обслуживания с однотипным резервным прибором // Изв. Томск. политехн. ун-та. 2010. Т. 317, № 5. С. 28-31.
13. Фадхкал З. Особенности числовых характеристик многоканальных систем массового обслуживания с ожиданием и отказами: автореф. … дис. канд. техн. наук. Казань: КНИТУ, 2015. 22 с.
14. Гольдштейт А. Л. Оптимизация в среде MATLAB: учеб. пособие. Пермь: Изд-во Перм. нац. исслед. политехн. ун-та, 2015. 192 с.
