ОПТИМИЗАЦИЯ МАРКОВСКИХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С ОЖИДАНИЕМ В СИСТЕМЕ MATLAB
Авторы:
1.
Национальный исследовательский Мордовский государственный университет им. Н. П. Огарева
(кандидат технических наук, доцент; доцент кафедры автоматизированных систем обработки информации и управления)
Россия
Россия
2.
Мордовский государственный университет им. Н. П. Огарева
Тип:
Статья
Страницы:
с 39
по 47
Статус:
Опубликован
Получено:
05.04.2017
Одобрено:
25.04.2017
Опубликовано:
25.04.2017
Классификаторы:
ВАК 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. Полученные результаты в виде описательных алгоритмов могут быть использованы для тестирования моделей систем массового обслуживания при пиковых (неизменяемых) нагрузках.
Ключевые слова:
система массового обслуживания, вероятность отказа, относительная пропускная способность, минимизация, максимизация, заданные параметры, целевая функция
система массового обслуживания, вероятность отказа, относительная пропускная способность, минимизация, максимизация, заданные параметры, целевая функция
Введение Системам массового обслуживания до сих пор уделяется много внимания. Результаты, полученные для марковских систем (нами они взяты из [1-3]), являются классикой, они вошли во все учебные пособия и руководства по теории и практике систем массового обслуживания (СМО). Вопросы оптимизации СМО рассматриваются с различных точек зрения и в различной постановке [4-6] (интернет-источники, касающиеся данных вопросов исследования СМО, нами не рассматриваются). Марковские СМО во многих случаях являются отправной точкой для исследования более сложных систем. Нами в ходе исследования рассматриваются марковские многоканальные СМО с конечным накопителем и многоканальные СМО с ограниченным временем пребывания в очереди. Ставя задачу оптимизации, следует определиться с критерием оптимальности - целевой функцией. В качестве целевой функции будет рассматриваться такая важная характеристика СМО, как вероятность отказа в обслуживании (далее - вероятность отказа). Если минимизировать вероятность отказа, то происходит максимизация относительной пропускной способности СМО, поскольку эти две вероятностные величины дополняют друг друга до единицы. Минимизация вероятности отказа нами рассматривается с позиций сохранения заданных параметров СМО: интенсивности входного потока, интенсивности обслуживания и интенсивности ухода из очереди. При этом необходимо найти то минимальное количество приборов обслуживания, когда относительная пропускная способность будет максимальной, а параметры системы примут значения, которые были заданы до начала процесса оптимизации. Обзор интернет-источников и ряда работ [4-6] показал, что в такой постановке задачи оптимизации СМО с ожиданием не наблюдается. Таким образом, сформулируем задачу оптимизации марковских СМО с ожиданием в виде следующих этапов: 1. Определить заданные и конечные параметры систем: интенсивность входного потока требований, интенсивность обслуживания одним прибором, интенсивность ухода из очереди. 2. Определить целевую функцию в виде аналитической формулы вероятности отказов в обслуживании. 3. В качестве целочисленного параметра оптимизации задать число приборов обслуживания в допустимых диапазонах. 4. Выбрать метод оптимизации (минимизации вероятности отказа). 5. Осуществить поиск такого минимального количества приборов обслуживания, при которых вероятность отказов примет минимальное значение при условии, что параметры системы достигнут заданных значений. Вычислить относительную пропускную способность системы. 6. Задать точность вычислений. Следует отметить, что при бесконечном увеличении числа приборов отказы в обслуживании будут стремиться к нулю. Такой же результат получится, если интенсивность обслуживания будет стремиться к бесконечности: все поступающие требования будут обслужены мгновенно. Или, при конечном значении интенсивности обслуживания, будет бесконечно уменьшаться интенсивность входного потока. Но это теоретические замечания. На практике простое увеличение числа приборов обслуживания ограничено, и прежде всего экономическими соображениями. Кроме того, изменять интенсивность входного потока, обслуживания или ухода из очереди на практике также бывает невозможным. Остается только подобрать такое минимальное число приборов обслуживания, с которыми будет минимальной вероятность отказа в обслуживании и, соответственно, максимальной относительная пропускная способность и будут сохраняться заданные параметры системы: интенсивность входного потока, интенсивность обслуживания и интенсивность ухода из очереди «нетерпеливых» требований. Оптимизация марковской системы массового обслуживания с конечным накопителем В соответствии с символикой Кендалла [1-3] СМО с конечным накопителем обозначается как M/M/m/K: первые две буквы означают пуассоновский входной поток требований и их экспоненциальное обслуживание, третья буква соответствует числу приборов обслуживания, включенных параллельно, последняя буква означает допустимое число заявок или требований в системе. Следуя [1-3], запишем формулы распределения вероятностей pk того, что в системе типа M/M/m/K с конечным накопителем будет точно k требований: где λ - интенсивность входного пуассоновского потока; μ - интенсивность обслуживания по экспоненциальному закону; P0 - вероятность отсутствия требований; (К - m) - допустимая длина очереди в СМО с конечным накопителем. Считаем, что число приборов обслуживания не превышает 170 (в этом случае факториал числа еще можно будет вычислять традиционными приемами). Потребуем минимизации вероятности отказов и, соответственно, максимизации относительной пропускной способности с поиском того минимального числа приборов обслуживания, при котором будут выполнены условия оптимизации. Задача должна решаться для заданных параметров интенсивности l входного потока требований и интенсивности m обслуживания СМО. Вероятность отказа Pотк определяется как вероятность того, что СМО будет полностью занятой, когда она находится в состоянии K: где P0 - вероятность отказа в обслуживании; S = (К - m) - допустимая длина очереди в системе с конечным накопителем. В нашем случае вероятность отказа выступает как целевая функция двух переменных: интенсивности l входного потока требований и интенсивности m обслуживания СМО. По-прежнему предполагается, что в результате решения задачи заданные параметры l и m должны оставаться неизменными в конце итеративного (численного) поиска оптимального решения - выбора числа приборов обслуживания. Относительная пропускная способность Q вычисляется по формуле Предлагается следующий алгоритм оптимизации СМО с конечным накопителем: 1. Определить целевую функции минимизации - формулу расчета вероятности отказов, начальный вектор поиска минимума - заданные параметры СМО. Определить точность вычислений и метод минимизации целевой функции многих переменных. 2. Итеративно, с изменением числа приборов обслуживания, оптимизировать параметры СМО в смысле минимума вероятности отказа с запоминанием оптимальных параметров системы. 3. Вычислить минимальное число приборов обслуживания, при котором параметры системы l, m принимают заданные значения, а относительная пропускная способность системы будет максимальной. 4. Построить пояснительные диаграммы изменения параметров СМО в зависимости от числа приборов обслуживания. Реализация предложенного алгоритма осуществлялась в системе математических и инженерных расчетов MATLAB (версия R2015b). Результаты численного эксперимента представлены в табл. 1. Таблица 1 Результаты оптимизации СМО типа M/M/m/170 Заданные значения параметров СМО Интенсивность входного потока λ 19,678 Интенсивность обслуживания одним прибором m 0,86 Приведенная нагрузка r = l/m 22,8814 Допустимое число требований K в системе 170 Точность вычислений eps 2,22045е-16 Результаты вычислений Расчетная интенсивность входного потока λ 19,678000000000010 Расчетная интенсивность обслуживания μ 0,8600000000000000 Оптимальное число приборов обслуживания m 27 Максимальное значение вероятности отказа 2,502480e-12 Как следует из табл. 1, относительная пропускная способность Q будет отличаться от единицы на величину порядка 2,502480e-12, т. е. в худшем случае Q = 0,9999999999974976. Параметры системы были заданы такими, чтобы приведенная нагрузка была достаточно большой, что проявляется на практике в случае пиковых нагрузках для СМО с ограниченной длиной очереди. Рассматриваемая задача оптимизации является нелинейной с двумя параметрами поиска и одним целочисленным параметром - числом приборов обслуживания. Ограничения для параметров могут быть заданы в пределах от системной величины эпсилон (eps) до системной большой величины типа realmax в системе MATLAB или DBL_MAXв MSVisualStudio. Диаграммa изменения параметров l, m системы типа M/M/m/170 представлена на рис. 1. Рис. 1. Оптимальные зависимости параметров СМО типа M/M/m/170 На рис. 1 показаны зависимости параметров системы от числа приборов обслуживания, но для каждого конкретного числа приборов обслуживания параметры таковы, что относительная пропускная способность СМО практически равна нулю. На рис. 2 представлена диаграмма изменения вероятности отказов в зависимости от числа приборов обслуживания рассматриваемой системы. Рис. 2. Изменение вероятности отказов СМО На рис. 3. Представлена зависимость приведенной нагрузки r = l/m от числа приборов обслуживания. Рис. 3. Изменение приведенной нагрузки СМО Диаграммы на рис. 1-3 показывают, когда заканчивается переходный процесс установления требуемых параметров системы. Обработка соответствующих массивов позволяет найти то значение числа приборов обслуживания, когда параметры выходят на установившийся режим. Оптимизация системы массового обслуживания типа M/M/m с ограниченным временем ожидания в очереди Система массового обслуживания с ограниченным временем ожидания относится к системам смешанного типа [3]. В систему поступает пуассоновский поток требований, обслуживание которых осуществляется по экспоненциальному закону непрерывной случайной величины - времени. Предполагается, что интенсивность ухода из очереди так называемых «нетерпеливых» требований подчиняется экспоненциальному закону с параметром v. Для данной системы также поставим задачу минимизации вероятности отказов в обслуживании, которая будет представлять собой целевую функцию трех переменных: интенсивности l входного потока, интенсивности обслуживания m одним прибором и интенсивности v ухода из очереди «нетерпеливых требований» (заявок). Считая, что в системе существует стационарный режим, приведем формулу для расчета вероятности отказов, которая определяет вероятность Pотк того, что заявка покинет систему необслуженной [3]. (1) где где m - число приборов (каналов) обслуживания; l - интенсивность входного потока требований; m - интенсивность обслуживания каждым прибором обслуживания; v - интенсивность ухода из очереди «нетерпеливых» заявок (требований). Параметры α и β выражают соответственно среднее число заявок и среднее число уходов заявки, стоящей в очереди, приходящиеся на среднее время обслуживания одной заявки [3]. Для оценки ошибки, возникающей от отбрасывания всех членов бесконечных сумм, начиная с r-го, можно воспользоваться следующими формулами: При минимизации вероятности отказов СМО типа M/M/m с ограниченным ожиданием в очереди осуществим поиск минимального числа приборов обслуживания, когда относительная пропускная способность будет максимальной, а параметры СМО будут соответствовать заранее заданным. Задача минимизации вероятности отказов по формуле (1) является нелинейной с ограничениями и несколькими переменными: интенсивность входного потока, интенсивность обслуживания, интенсивность ухода из очереди, число приборов обслуживания, ограничитель вычисления бесконечных сумм. Основные этапы предлагаемого способа оптимизации СМО с ограниченным временем ожидания заключаются в следующем. 1. Установить заданные параметры СМО как начальный вектор поиска минимума вероятности отказов - целевой функции. 2. Задать максимально допустимое число приборов обслуживания в системе, число r - ограничитель вычисления бесконечных сумм. 3. Выбрать метод (решатель) минимизации. Задать точность вычислений. 4. В цикле изменения числа приборов обслуживания производить поиск оптимального решения: накапливать массив значений оптимизируемых параметров. 5. Построить диаграммы изменения параметров СМО в зависимости от числа приборов обслуживания. Для решения задачи оптимизации, так же как и в предыдущем случае, использовалась система MATLAB, в которой была выбрана функция fmincon c алгоритмом квадратичного программирования - sqp [7]. Результаты численных экспериментов для СМО типа M/M/m с ограниченным временем ожидания приведены в табл. 2, диаграммы оптимальных изменений параметров системы - на рис. 4-6. Таблица 2 Результаты оптимизации СМО типа M/M/m с ограниченным временем ожидания Заданные значения параметров СМО Интенсивность входного потока λ 21,3 Интенсивность обслуживания одним прибором μ 0,86 Интенсивность ухода из очереди v 0,43 Допустимое число требований K в системе 170 Величина предела бесконечной суммы r 110 Точность вычислений 2,22045e-16 Результаты вычислений Расчетная интенсивность λ 21,30000001079576 Расчетная интенсивность обслуживания μ 0,85999976603849 Расчетная интенсивность ухода из очереди v 0,42999993315386 Оптимальное число приборов обслуживания m 15 Максимальное значение вероятности отказа 3,251971e-10 Рис. 4. Изменение интенсивности входного потока СМО типа M/M/m/170 Как видно из рис. 4, после отметки в 8 приборов обслуживания наступил установившийся режим интенсивности входного потока, которая равна заданной перед началом оптимизации СМО. На рис. 5, так же как и на рис. 4, виден установившийся режим для интенсивности обслуживания и интенсивности ухода из очереди «нетерпеливых» требований. Рис. 5. Интенсивность обслуживания и интенсивность ухода из очереди СМО типа M/M/m/170 Результат, представленный на рис. 6, удобен для поиска минимального (оптимального) числа приборов обслуживания, когда изменение параметров СМО достигает установившегося режима. Рис. 6. Изменение вероятности отказов в СМО Все представленные результаты оптимизации рассмотренных СМО получены на основе программ, разработанных в системе MATLAB R2015b. Заключение Особенность поиска минимума вероятности отказов марковских СМО с ожиданием заключается в предложенном начальном векторе поиска минимума вероятности отказов. Вектор поиска состоит из заданных параметров СМО. Результаты численного эксперимента в MATLAB показали, что процесс выхода параметров СМО на установившейся режим осуществляется с этапом переходного процесса, когда параметры изменяются в зависимости от числа приборов обслуживания. При этом сохраняется минимизация вероятности отказов и, соответственно, максимизация относительной пропускной способности марковской СМО. В результате оптимизации определяется то количество приборов обслуживания, после достижения которого значения параметров СМО соответствуют заранее заданным с сохранением минимизации вероятности отказов и максимизации относительной пропускной способности системы. Значение относительной пропускной способности практически равно единице. Результаты исследования в виде описательных алгоритмов могут быть использованы для тестирования моделей СМО при пиковых (неизменяемых) нагрузках.
1. Шелухин О. И. Моделирование информационных систем. М.: Горячая линия - Телеком, 2016. 516 с.
2. Таранцев А. А. Инженерные методы теории массового обслуживания. СПб.: Наука, 2007. 175 с.
3. Афонин В. В., Мурюмин С. М., Федосин С. А. Основы анализа систем массового обслуживания: учеб. пособие. Саранск: Изд-во Мордов. ун-та, 2003. 236 с.
4. Балясников В. В., Богданов А. А., Маслаков В. П., Староселец В. Г. Многокритериальная оптимизация транспортных систем массового обслуживания // Транспорт Российской Федерации. 2012. № 6 (43). С. 73-76.
5. Бояршинова И. Н., Исмагилов Т. Р., Потапова И. А. Моделирование и оптимизация работы системы массового обслуживания // Фундаментальные исследования. 2015. № 9 (ч. 1). С. 9-13.
6. Самочернова Л. А., Петров Е. С. Оптимизация системы массового обслуживания с однотипным резервным прибором // Изв. Томск. политехн. ун-та. 2010. Т. 317, № 5. С. 28-31.
7. Гольдштейт А. Л. Оптимизация в среде MATLAB: учеб. пособие. Пермь: Изд-во Перм. нац. исслед. политехн. ун-та, 2015. 192 с.
