OPTIMIZATION OF MARKOVIAN QUEUING SYSTEMS WITH FAILURES IN THE MATLAB SYSTEM
Journal: VESTNIK OF ASTRAKHAN STATE TECHNICAL UNIVERSITY. SERIES: MANAGEMENT, COMPUTER SCIENCE AND INFORMATICS
№ 1
, 2018
Rubrics: MATHEMATICAL MODELING
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 112
to 120
Status:
Published
Received:
05.01.2018
Accepted:
25.01.2018
Published:
25.01.2018
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:
queuing system, failure probability, relative throughput, optimization, minimization, maximization, objective function, model time, MATLAB
Abstract (English):
The paper touches upon the optimization task of the multichannel Markov queuing system suffering failures due to a heavy work load, which can be observed in realistic operational conditions for multi-purpose queuing systems. The optimization task is reduced to maximizing the system throughput with the minimum number of maintenance devices required, hence, to reducing the number of failures. To solve the task, MATLAB R2016b system has been used, which provides tools (functions) for minimizing the objective functions of many variables with constraints. The natural constraints are superimposed on the system parameters: intensity of the input flow and intensity of the service, which are positive quantities in the queuing system environment. Taking into account the fact that possibility of failures depends on the number of servicing tools, this number inevitably becomes a real number, and not a whole number, and should be taken as a parameter of the optimization task. The results obtained can be used to test models of queuing systems having failures under peak loads, as well as in cases which can be defined by the ratio of the intensity of Poisson arrivals to the intensity of a single machine processing.
The paper touches upon the optimization task of the multichannel Markov queuing system suffering failures due to a heavy work load, which can be observed in realistic operational conditions for multi-purpose queuing systems. The optimization task is reduced to maximizing the system throughput with the minimum number of maintenance devices required, hence, to reducing the number of failures. To solve the task, MATLAB R2016b system has been used, which provides tools (functions) for minimizing the objective functions of many variables with constraints. The natural constraints are superimposed on the system parameters: intensity of the input flow and intensity of the service, which are positive quantities in the queuing system environment. Taking into account the fact that possibility of failures depends on the number of servicing tools, this number inevitably becomes a real number, and not a whole number, and should be taken as a parameter of the optimization task. The results obtained can be used to test models of queuing systems having failures under peak loads, as well as in cases which can be defined by the ratio of the intensity of Poisson arrivals to the intensity of a single machine processing.
Keywords:
queuing system, failure probability, relative throughput, optimization, minimization, maximization, objective function, model time, MATLAB
queuing system, failure probability, relative throughput, optimization, minimization, maximization, objective function, model time, 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. 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., Fedosin S. A. Modelirovanie sistem: ucheb.-prakt. posobie. M.: INTUIT; BINOM, Laboratoriya znaniy, 2016. 231 s.
4. Afonin V. V., Nikulin V. V. Metody modelirovaniya i optimizacii s primerami na yazyke S/S++ i MATLAB: Ch. 1: Metody modelirovaniya: ucheb. posobie. Saransk: Izd-vo Mordov. un-ta, 2015. 184 s.
5. Afonin V. V., Nikulin V. V. Metody modelirovaniya i optimizacii s primerami na yazyke S/S++ i MATLAB: ucheb. posobie. Ch. 1. Metody modelirovaniya. Saransk: Izd. Afanas'ev V. S., 2017. 188 s.
6. 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.
7. Gefan G. D. Markovskie processy i sistemy massovogo obsluzhivaniya: ucheb. posobie. Irkutsk: IrGUPS, 2009. 80 s.
8. Afonin V. V., Nikulin V. V. Metody modelirovaniya i optimizacii s primerami na yazyke S/S++ i MATLAB: Ch. 2. Metody bezuslovnoy optimizacii: ucheb. posobie. Saransk: Izd. Afanas'ev V. S., 2017. 231 s.
9. Afonin V. V. Optimizaciya markovskoy sistemy massovogo obsluzhivaniya s otkazami // Zhurnal nauchnyh i prikladnyh issledovaniy. 2017. № 1. S. 100-103.
10. 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.
11. 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.
12. 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.
13. Fadhkal Z. Osobennosti chislovyh harakteristik mnogokanal'nyh sistem massovogo obsluzhivaniya s ozhidaniem i otkazami: avtoref. … dis. kand. tehn. nauk. Kazan': KNITU, 2015. 22 s.
14. Gol'dshteyt A. L. Optimizaciya v srede MATLAB: ucheb. posobie. Perm': Izd-vo Perm. nac. issled. politehn. un-ta, 2015. 192 s.
