OPTIMIZATION OF MARKOV SYSTEMS OF QUEUEING WITH WAITING TIME IN THE MATLAB SYSTEM
Authors:
1.
National Research Ogarev Mordovia State University
(Candidate of Technical Sciences, Assistant Professor; Assistant Professor of the Department of Automated Information Processing Systems and Management)
Russian Federation
Russian Federation
2.
N. P. Ogarev Mordovia State University
Type:
Article
Pages:
from 39
to 47
Status:
Published
Received:
05.04.2017
Accepted:
25.04.2017
Published:
25.04.2017
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 65.012.122
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 65.012.122
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
queueing system, probability of failure, relative throughput, minimization, maximization, desired parameters, objective function
Abstract (English):
The article focuses on attempt to optimize two well-known Markov systems of queueing: a multichannel queueing system with finite storage, and a multichannel queueing system with limited queue time. In the Markov queuing systems, the intensity of the input stream of requests (requirements, calls, customers, demands) is subject to the Poisson law of the probability distribution of the number of applications in the stream; the intensity of service, as well as the intensity of leaving the application queue is subject to exponential distribution. In a Poisson flow, the time intervals between requirements are subject to the exponential law of a continuous random variable. In the context of Markov queueing systems, there have been obtained significant results, which are expressed in the form of analytical dependencies. These dependencies are used for setting up and numerical solution of the problem stated. The probability of failure in service is taken as a task function; it should be minimized and depends on the intensity of input flow of requests, on the intensity of service, and on the intensity of requests leaving the queue. This, in turn, allows to calculate the maximum relative throughput of a given queuing system. The mentioned algorithm was realized in MATLAB system. The results obtained in the form of descriptive algorithms can be used for testing queueing model systems during peak (unchanged) loads.
The article focuses on attempt to optimize two well-known Markov systems of queueing: a multichannel queueing system with finite storage, and a multichannel queueing system with limited queue time. In the Markov queuing systems, the intensity of the input stream of requests (requirements, calls, customers, demands) is subject to the Poisson law of the probability distribution of the number of applications in the stream; the intensity of service, as well as the intensity of leaving the application queue is subject to exponential distribution. In a Poisson flow, the time intervals between requirements are subject to the exponential law of a continuous random variable. In the context of Markov queueing systems, there have been obtained significant results, which are expressed in the form of analytical dependencies. These dependencies are used for setting up and numerical solution of the problem stated. The probability of failure in service is taken as a task function; it should be minimized and depends on the intensity of input flow of requests, on the intensity of service, and on the intensity of requests leaving the queue. This, in turn, allows to calculate the maximum relative throughput of a given queuing system. The mentioned algorithm was realized in MATLAB system. The results obtained in the form of descriptive algorithms can be used for testing queueing model systems during peak (unchanged) loads.
Keywords:
queueing system, probability of failure, relative throughput, minimization, maximization, desired parameters, objective function
queueing system, probability of failure, relative throughput, minimization, maximization, desired parameters, objective function
Введение Системам массового обслуживания до сих пор уделяется много внимания. Результаты, полученные для марковских систем (нами они взяты из [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. Sheluhin O. I. Modelirovanie informacionnyh sistem. M.: Goryachaya liniya - Telekom, 2016. 516 s.
2. Tarancev A. A. Inzhenernye metody teorii massovogo obsluzhivaniya. SPb.: Nauka, 2007. 175 s.
3. Afonin V. V., Muryumin S. M., Fedosin S. A. Osnovy analiza sistem massovogo obsluzhivaniya: ucheb. posobie. Saransk: Izd-vo Mordov. un-ta, 2003. 236 s.
4. Balyasnikov V. V., Bogdanov A. A., Maslakov V. P., Staroselec V. G. Mnogokriterial'naya optimizaciya transportnyh sistem massovogo obsluzhivaniya // Transport Rossiyskoy Federacii. 2012. № 6 (43). S. 73-76.
5. Boyarshinova I. N., Ismagilov T. R., Potapova I. A. Modelirovanie i optimizaciya raboty sistemy massovogo obsluzhivaniya // Fundamental'nye issledovaniya. 2015. № 9 (ch. 1). S. 9-13.
6. Samochernova L. A., Petrov E. S. Optimizaciya sistemy massovogo obsluzhivaniya s odnotipnym rezervnym priborom // Izv. Tomsk. politehn. un-ta. 2010. T. 317, № 5. S. 28-31.
7. Gol'dshteyt A. L. Optimizaciya v srede MATLAB: ucheb. posobie. Perm': Izd-vo Perm. nac. issled. politehn. un-ta, 2015. 192 s.
