Журналы
НЕФТЕГАЗОВЫЕ ТЕХНОЛОГИИ И ЭКОЛОГИЧЕСКАЯ БЕЗОПАСНОСТЬ Серия: Морская техника и технология Серия: РЫБНОЕ ХОЗЯЙСТВО Серия: УПРАВЛЕНИЕ, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА Серия: ЭКОНОМИКА

Вестник АГТУ (АРХИВНЫЙ)
История Ссылки Новости Контакты
Отправить рукопись
Главная / Журналы / Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика / Номер 3 / ОПТИМИЗАЦИЯ МНОГОКАНАЛЬНЫХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ ПРИ БОЛЬШИХ ЗАГРУЗКАХ
ОПТИМИЗАЦИЯ МНОГОКАНАЛЬНЫХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ ПРИ БОЛЬШИХ ЗАГРУЗКАХ
Отправить рукопись Скачать PDF
Текст
Цитировать
Цитирований:

ОПТИМИЗАЦИЯ МНОГОКАНАЛЬНЫХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ ПРИ БОЛЬШИХ ЗАГРУЗКАХ
УДК 65 Управление предприятиями. Организация производства, торговли и транспорта
Афонин Виктор Васильевич 1
Никулин Владимир Валерьевич 2
Авторы:
1.  Национальный исследовательский Мордовский государственный университет им. Н. П. Огарева (кандидат технических наук, доцент; доцент кафедры автоматизированных систем обработки информации и управления)

Россия
2.  Национальный исследовательский Мордовский государственный университет им. Н. П. Огарева (кандидат технических наук, доцент; заведующий кафедрой инфокоммуникационных технологий и систем связи)

Россия
Тип:
Статья
DOI:
https://doi.org/10.24143/2072-9502-2020-3-105-115
Страницы:
с 105 по 115
Статус:
Опубликован
Получено:
20.07.2020
Одобрено:
21.07.2020
Опубликовано:
21.07.2020
Классификаторы:
УДК 65 Управление предприятиями. Организация производства, торговли и транспорта
Язык материала:
русский
Ключевые слова:
система массового обслуживания, вероятность отказа, относительная пропускная способность, оптимизация, каналы обслуживания
Аннотация и ключевые слова
Аннотация (русский):
Рассматриваются аналитические модели марковских систем массового обслуживания с отказами в обслуживании поступающих в систему запросов, требований. Системы анализируются при конфликтных ситуациях, таких как значительные загрузки, – при больших отношениях интенсивности входного потока к интенсивности обслуживания, что является актуальным при различных экстремальных ситуациях как в технических приложениях, интернет-приложениях, так и социальных. Возникает задача оптимизации – минимизации числа каналов при условии гарантированной пропускной способности системы массового обслуживания в целом. Рассматривается такой подход к решению задачи оптимизации, когда максимизируется относительная пропускная способность системы с минимизацией числа каналов обслуживания. Из-за того, что в аналитических формулах марковских систем массового обслуживания присутствуют факториалы, аналитический анализ систем встречается с ограничениями вычислительного характера. В проведенных исследованиях для разрешения вычислительных затруднений принято решение применить аппроксимацию вероятностей состояний системы с помощью интеграла вероятностей Лапласа. Его применение оправдывается именно при больших интенсивностях загрузки системы и большом числе каналов обслуживания. Излагаются особенности применения интеграла Лапласа в совокупности с численной оптимизацией на условный экстремум. Приводится методика определения такого выбора числа каналов обслуживания, когда минимизируется вероятность отказа в обслуживании, соответственно, максимизации относительной пропускной способности системы. Дана графическая интерпретация предложенной методики оптимизации систем массового обслуживания с отказами со значительной ее загрузкой. Показано, что за период поиска оптимума имеется переходный процесс, при котором существуют значительные изменения параметров системы – интенсивности входного потока и интенсивности обслуживания.

Ключевые слова:
система массового обслуживания, вероятность отказа, относительная пропускная способность, оптимизация, каналы обслуживания
Текст
Текст (PDF): Читать Скачать
Введение Математические модели на основе систем массового обслуживания (СМО) используются во многих сферах. Многие положения анализа марковских СМО имеют аналитическое решение. Эти системы продолжают исследоваться [1–3]. Безусловно, следует отметить, что в настоящее время значительное внимание уделяется полумарковским и немарковским системам массового обслуживания [4–7]. В данной статье авторы расширяют известные положения марковских СМО. А именно, будет рассматриваться задача с предельно допустимыми нагрузками на системы обслуживания, когда требуется определить то минимальное число приборов (каналов) обслуживания, когда при высокой интенсивности входного потока требований обеспечивается практически безотказная работы СМО типа M/M/m с отказами. С наличием современных инструментальных и программ-ных средств и пакетов анализ СМО облегчается [8–13]. Для решения поставленной задачи при-нята система MATLAB. При решении задач оптимизации СМО рассматриваются различные целевые функции – функционалы оптимизации, решаются различные задачи оптимизации СМО [10–12, 14–20]. В предлагаемой работе в качестве целевой функции принимается функция двух аргументов для поиска минимума вероятности отказа в обслуживании. При этом в качестве параметра выступает количество каналов (приборов) обслуживания. Задача необходимого числа приборов, каналов обслуживания достаточно актуальна. В данной статье развивается подход оптимизации СМО, рассмотренный в [10–12]. В указанных работах существует ограничение на возможное число каналов обслуживания, вызванное тем, что в них применяются классические формулы Эрланга, содержащие вычисления факториалов числа [21–23]. Это ограничение можно обойти при использовании интеграла вероятностей или функции Лапласа для случая больших загрузок марковских СМО [24]. Приведенные в [24] положения в приложении к СМО послужили осно-вой для постановки и решения задачи оптимизации СМО с отказами в плане определения необ-ходимого числа каналов обслуживания с сохранением высокой загрузки системы. С применени-ем алгоритмов минимизации целевой функции нескольких переменных авторами в [24] показа-но, что существует некий переходный процесс до момента установления заданных параметров входного потока и обслуживания, которые по производственным и технологическим причинам не могут быть изменены. Постановка задачи оптимизации и ее решение Марковская система с отказами в соответствии с обозначениями Кендалла описывается тремя полями с дополнением: M/M/m с отказами. Для данной системы известны аналитические решения по определению вероятностей состояния, вероятности отказов, относительной про-пускной способности и т. д. [21–23]. Однако в случае числа каналов обслуживания, превышаю-щего 170, напрямую известными формулами пользоваться не удается в силу ограничений на вычисления факториала больших чисел. Учитывая это и предполагаемую большую загрузку системы, следует воспользоваться аппроксимацией классических формул Эрланга на основе интеграла вероятностей – функции Лапласа [24]. Приведем исходные формулы для описания в стационарном режиме систем массового обслуживания с отказами: (1) где pi – вероятность того, что в системе будет i требований; m – число каналов (приборов) об-служивания;  – приведенная плотность потока заявок; λ – интенсивность входного пуассонов-ского потока;  – интенсивность обслуживания по экспоненциальному закону; p0 – вероятность отсутствия требований (заявок, запросов) в системе. При больших значениях m (m > 20) вероятность отсутствия требований в системе при-ближенно можно заменить экспонентой в результате разложения ее в конечный ряд Тейлора: (2) Для введения интеграла вероятностей (функции Лапласа) принимаются следующие обозначения: (3) (4) (5) где Ф(х) – интеграл вероятностей, или функция Лапласа: Для Ф(–х) = –Ф(х) [24]. Вычитая из (3) выражение (4) и деля на (5), получим формулу для расчета вероятности со-стояний в СМО с отказами в виде (6) Соответственно, для вероятности отказов pm в обслуживании будем иметь (7) Если проследить выражения с (1) по (7), становится очевидным, что вероятность отказов зависит от трех величин: интенсивности входного потока , интенсивности обслуживания  и числа каналов обслуживания m. Но число каналов обслуживания – заранее не известная величина, в отличие от параметров входного потока и обслуживания. Поэтому предлагается рассматривать число каналов обслуживания в виде параметра, который заключен в интервале от одного до приемлемой большой величины, которая зависит от допустимых возможностей рассматриваемой СМО. Следовательно, можно сформулировать задачу минимизации вероятности отказов как функцию двух переменных , , и решать ее в виде итерационного процесса, который обусловлен изменением числа каналов обслуживания m как параметра: . (8) Переменные ,  как интенсивности входного потока и обслуживания должны быть больше нуля. Из анализа известных методов минимизации функций нескольких переменных с ограничениями следует, что, возможно, наиболее приемлемым является метод «active-set» (активный набор), который эффективен для задач средней размерности с негладкими ограничениями. Этот метод поддерживается функцией fmincon системы MATLAB [25]. Первым аргументом функции fmincon является указатель на функцию или имя анонимной функции, например f. При больших загрузках СМО приведем соотношение, связывающее интеграл вероятностей Ф(х) и функцию ошибок erf(х): (9) В свою очередь, функция ошибок erf(x) определяется по формуле (10) С учетом выражений (2)–(7) определяется выражение для правой части целевой функции (8), подлежащей минимизации. В терминах синтаксиса языка системы MATLAB вид анонимной целевой функции f будет следующим: f = @(x)(1 – (0,5 + 0,5 * erf((m – 1 + 0,5 – x (1) / x (2)) / sqrt (2))) / (0,5 + 0,5 * erf ((m + + 0,5 – x(1) / x (2)) / sqrt(2)))). Алгоритм оптимизации СМО с отказами приведен на рис. 1. Рис. 1. Схема предлагаемого алгоритма оптимизации СМО с отказами На рис. 1 не отражены процессы обработки контейнеров LMP, Xm, Fm, которые исполь-зуются для определения графических зависимостей и минимально необходимого числа каналов обслуживания, когда вероятность отказов будет минимальной при конечном числе каналов (устройств) обслуживания. Цикл прохода по числу каналов обслуживания позволяет накопить информацию о поведении параметров системы. В начальный вектор состояния X0 включены заданные параметры СМО. Алгоритм active-set, используемый в опциях функции fmincon, позволяет не прерывать процесс поиска оптимального решения, когда он не может быть найден. В этом случае возвращается NaN (не число), которое можно контролировать с помощью функции isfinite. Случай, когда допустимое число каналов обслуживания не пре-вышает 170, рассмотрен в [11]. Модельные эксперименты оптимизации СМО с отказами Для проверки предложенных алгоритмов по расчету минимального числа каналов обслу-живания СМО с отказами были использованы тестовые модели с параметрами, обеспечивающие высокую приведенную плотность потока заявок (требований). Параметры тестовых моделей СМО (Модель 1, Модель 2) с отказами и результаты поиска оптимального числа каналов обслуживания приведены в таблице. Результаты оптимизации тестовых моделей СМО* Параметры СМО Модель 1 Модель 2 Интенсивность входного потока  109,012 345 Интенсивность обслуживания  0,36 0,23 Приведенная плотность потока заявок  302,811 1 500 Вычислительная точность 1,192093e-07 2,220446e-16 1,192093e-07 2,220446e-16 Расчетная  109,011981 109,012002 345,000000 345,000000 Расчетная  0,365613 0,360468 0,230700 0,230126 Оптимальное число приборов обслуживания 308 310 1 506 1 507 Вероятность отказов при оптимальном числе приборов обслуживания 0,000000e+00 7,102097e-13 0,000000e+00 1,219025e-13 Зона недоступности оптимальных решений Загрузка СМО к оптимальному числу приборов – λ/(mμ) 0,968059 0,975542 0,992992 0,994809 * Размерность интенсивности потока и обслуживания предполагаются в условных единицах. Зона недоступности оптимальных решений определяется через значения контейнера Fm (см. рис. 1), в который заносилось число приборов обслуживания, при которых функция fmincon не определяла оптимального решения. Расчетные переменные  и  определялись при опти-мальном числе приборов обслуживания, которое находилось как минимальное значение, при котором переменные целевой функции принимали свои заданные значения, которые вклю-чались в начальный вектор поиска с помощью функции fmincon. Как видно из табл., вероятно-сти отказов при оптимальном числе приборов обслуживания предельно малы. Соответственно, относительная пропускная способность будет практически равна единице. Очевидно, что за-грузка СМО к общему числу приборов обслуживания m будет стремиться к нулю при m   при конечных значениях  и . Характер изменения контролируемых переменных показан на рис. 2–5 при вычислительной точности 1,192093e-07. Рис. 2. Изменения переменных целевой функции Модели 1 Рис. 3. Изменение загрузки системы Модели 1 Рис. 4. Изменение переменных целевой функции Модели 2 Рис. 5. Изменение загрузки системы Модели 2 Из приведенных диаграмм следует, что при большой загрузке системы характер изменения переменных в зависимости от числа каналов обслуживания наиболее ясно характеризуют за-висимости для тестовой Модели 2. Существует переходный период, при котором аргументы целевой функции значительно отклоняются от своих заданных практических значений, которые представляют собой параметры той или иной СМО. Заключение Рассмотрены возможности численной оптимизации систем массового обслуживания с отказами при большой загрузке. Получены приемлемые, на взгляд авторов, результаты для тестовых моделей СМО. Предложен эвристический алгоритм поиска минимально необходимого числа приборов обслуживания, при котором вероятность отказов предельна мала. Полученные результаты могут быть использованы при проектировании СМО с отказами и с большой приведенной загрузкой.
Список литературы

1. Sushil Ghimire, Gyan Bahadur Thapa, Ram Prasad Ghimire, Silvestrov S. A Survey on Queueing Systems with Mathematical Models and Applications // American Journal of Operational Research. 2017. V. 7. N. 1. P. 1-14.

2. Будылина Е. А., Гарькина И. А., Сухов Я. И. Системы массового обслуживания: марковские процессы с дискретными состояниями // Молодой ученый. 2014. № 6. С. 145-148.

3. Tonui B., Lang'at R., Gichengo J. On Markovian Queuing Models // International Journal of Science and Research (IJSR). 2014. V. 3. P. 93-96.

4. Назаров А. А., Измайлова Я. Е. Исследование RQ-системы M|E2|1 с вытеснением заявок и сохранением фазовой реализации обслуживания // Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2018. № 42. C. 72-78.

5. Песчанский А. И. Полумарковская модель однолинейной системы обслуживания с потерями и ненадежным восстанавливаемым каналом // Динамические системы. 2017. Т. 7 (35). № 1. С. 53-61.

6. Рыжиков Ю. И., Уланов А. В. Применение гиперэкспоненциальной аппроксимации в задачах расчета немарковских систем массового обслуживания // Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2016. № 3 (36). C. 60-65.

7. Назаров А. А., Семенова И. А. Асимптотический анализ систем массового обслуживания с неограниченным числом приборов и полумарковским входящим потоком // Изв. Том. политехн. ун-та. Сер.: Управление, вычислительная техника и информатика. 2012. Т. 320. № 5. С. 12-17.

8. Антонова В. М., Гречишкина Н. А., Кузнецов Н. А., Сухорукова Н. А. Моделирование трафика систем массового обслуживания в среде ANYLOGIC на примере пассажиропотока станции метро // Журнал радиоэлектроники [электронный журнал]. 2018. № 3. URL: http://jre.cplire.ru/jre/mar18/8/text.pdf (дата обращения: 12.02.2020).

9. Щукина Н. А., Горемыкина Г. И., Тарасова И. А. Дискретно-событийное моделирование деятельности отделения банка в среде MATLAB + SIMULINK // Фундаментальные исследования. 2016. № 10. С. 452-456.

10. Афонин В. В., Давыдкин В. В. Оптимизация системы массового обслуживания с ограниченной длиной очереди // XLVI Огарёвские чтения: материалы науч. конф.: в 3 ч. Саранск: Изд-во Мордов. ун-та, 2018. Ч. 1: Технические науки. С. 226-231.

11. Афонин В. В., Никулин В. В. Оптимизация Марковских систем массового обслуживания с отказами в системе MATLAB // Вестн. Астрахан. гос. техн. ун-та. Сер.: Управление, вычислительная техника и информатика. 2018. № 1. С. 112-120.

12. Афонин В. В., Никулин В. В. Оптимизация Марковских систем массового обслуживания с ожиданием в системе MATLAB // Вестн. Астрахан. гос. техн. ун-та. Сер.: Управление, вычислительная техника и информатика. 2017. № 2. С. 39-47.

13. Жерновый Ю. В., Жерновый К. Ю. Метод потенциалов для замкнутой системы с временем об-служивания, зависящим от длины очереди // Информационные процессы. 2015. Т. 15. № 1. С. 40-50.

14. Романенко В. А. Векторная оптимизация системы массового обслуживания с частичной взаимопомощью между каналами // Вестн. Самар. гос. аэрокосм. ун-та. 2017. № 6 (30). С. 264-272.

15. Назаров А. А., Фёдорова Е. А. Исследование RQ3 системы MMPP|GI|1 методом асимптотического анализа второго порядка в условии большой загрузки // Изв. Том. политехн. ун-та. Информационные технологии. 2014. Т. 325. № 5. С. 6-15.

16. Бояршинова И. Н., Исмагилов Т. Р., Потапова И. А. Моделирование и оптимизация работы си-стемы массового обслуживания // Фундаментальные исследования. 2015. № 9 (1). С. 9-13.

17. Балясников В. В., Богданов А. А., Маслаков В. П., Староселец В. Г. Многокритериальная оптимизация транспортных систем массового обслуживания // Транспорт Российской Федерации. 2012. № 6 (43). С. 73-76.

18. Miller B. M. Optimization of queuing system via stochastic control // Automatica. 2009. V. 45. P. 1423-1430.

19. Чекменев В. А., Антропов М. С. Анализ системы массового обслуживания с динамическими по числу требований приоритетами при большой загрузке // Вестн. Кузбас. гос. техн. ун-та. 2003. № 4. C. 6-8.

20. Назаров А. А., Чекменев В. А. Анализ и оптимизация системы массового обслуживания с дина-мическими по числу требований приоритетами при большой загрузке // Автоматика и телемеханика. 1984. № 10. С. 78-87.

21. Шелухин О. И. Моделирование информационных систем. М.: Горячая линия - Телеком, 2016. 516 с.

22. Таранцев А. А. Инженерные методы теории массового обслуживания. СПб.: Наука, 2007. 175 с.

23. Афонин В. В., Федосин С. А. Моделирование систем: учеб.-практ. пособие. М.: ИнтУИТ: БИНОМ, Лаборатория знаний, 2016. 231 с.

24. Волков И. К., Зуев С. М., Цветкова Г. М. Случайные процессы: учеб. для вузов / под ред. В. С. Зарубина, А. П. Крищенко. М.: Изд-во МГТУ им. Н. Э. Баумана, 2006. 448 с.

25. Гольдштейт А. Л. Оптимизация в среде MATLAB: учеб. пособие. Пермь: Изд-во Перм. нац. исслед. политехн. ун-та, 2015. 192 с.

Контент доступен под лицензией Creative Commons Attribution 3.0 Unported

© "Редакция научных журналов"
Поддержка Powered by Editorum,  Инструкции
Войти или Создать
* Забыли пароль?