ОДНОКАНАЛЬНАЯ СМО С АБСОЛЮТНЫМ ПРИОРИТЕТОМ И НЕТЕРПЕЛИВЫМИ ЗАЯВКАМИ
|
АННОТАЦИЯ 3
ВВЕДЕНИЕ 3
1 СМО с абсолютным приоритетом и нетерпеливыми заявками вида
M2 |(M1,M2)| 1|(2,2) 9
1.1 Математическая модель 9
1.2 Граф возможных состояний 11
1.3 Система дифференциальных уравнений Колмогорова 11
1.4 Система уравнений для стационарных вероятностей 13
1.5 Численная реализация нахождения распределения вероятностей
системы 14
1.6 Характеристики качества обслуживания 18
2 СМО с абсолютным приоритетом и нетерпеливыми заявками вида
M2|(M1,M2)|1|(N1,N2) 22
2.1 Математическая модель 22
2.2 Состояния системы 24
2.3 Граф переходов 26
3 Алгоритм автоматического построения матриц переходов 30
3.1 Формирование списка состояний системы 30
3.2 Построение матрицы переходов 31
3.3 Получение характеристик качества обслуживания 34
3.4 Визуализация результатов 36
ЗАКЛЮЧЕНИЕ 40
СПИСОК ЛИТЕРАТУРЫ 42
ВВЕДЕНИЕ 3
1 СМО с абсолютным приоритетом и нетерпеливыми заявками вида
M2 |(M1,M2)| 1|(2,2) 9
1.1 Математическая модель 9
1.2 Граф возможных состояний 11
1.3 Система дифференциальных уравнений Колмогорова 11
1.4 Система уравнений для стационарных вероятностей 13
1.5 Численная реализация нахождения распределения вероятностей
системы 14
1.6 Характеристики качества обслуживания 18
2 СМО с абсолютным приоритетом и нетерпеливыми заявками вида
M2|(M1,M2)|1|(N1,N2) 22
2.1 Математическая модель 22
2.2 Состояния системы 24
2.3 Граф переходов 26
3 Алгоритм автоматического построения матриц переходов 30
3.1 Формирование списка состояний системы 30
3.2 Построение матрицы переходов 31
3.3 Получение характеристик качества обслуживания 34
3.4 Визуализация результатов 36
ЗАКЛЮЧЕНИЕ 40
СПИСОК ЛИТЕРАТУРЫ 42
Теория массового обслуживания представляет собой важное направление прикладной математики, основанное на методах теории вероятностей и математической статистики. Она находит широкое применение в различных сферах человеческой деятельности и позволяет моделировать и анализировать процессы поступления, ожидания и обслуживания заявок в системах с ограниченными ресурсами. Основные концепции и модели систем массового обслуживания, а также методы их математического анализа представлены в работах Б. В. Гнеденко [5-6], Л. Клейнрок [12], А. А. Назарова [23].
Системы массового обслуживания с абсолютным приоритетом и нетерпеливыми заявками представляют собой особый класс систем, где каждая заявка имеет свойство приоритета и может быть характеризована степенью нетерпимости к ожиданию обслуживания. Абсолютный приоритет означает, что заявки с более высоким приоритетом имеют преимущество перед заявками с более низким приоритетом и должны быть обработаны в первую очередь. Нетерпеливые заявки требуют немедленного или приоритетного обслуживания из-за ограниченности их времени ожидания. Основные модели СМО приоритетного обслуживания изложены в работах О. И. Бронштейн [1], Б. В. Гнеденко [7], Н. К. Джейсуол [9], С. П. Моисеева [20]. Модели с нетерпеливыми заявками рассмотрены в работах А. И. Коваленко [13], Д. А. Малышева [15].
Для более глубокого понимания и анализа СМО с абсолютным приоритетом и нетерпеливыми заявками используются различные математические методы, включая теорию вероятностей, статистику, теорию случайных процессов и моделирование. Теория вероятностей и случайных процессов играют ключевую роль в изучении теории массового обслуживания, поскольку они предоставляют математические инструменты и методы анализа, необходимые для оценки производительности и оптимизации систем обслуживания. Основы этих дисциплин подробно изложены в пособиях О.Н. Галажинской, С.П. Моисеевой [3-4], А.А. Назарова, А.Ф. Терпугова [22], С.П. Моисеевой [19], О. Н. Галажинской [2], Д. Д. Даммер [8], Т.В. Кабановой [10-11].
Для детального изучения динамики работы СМО часто создают её имитационную модель. Подробные примеры построения таких моделей можно найти в работах Е. Ю. Лисовской и M. Pagano [14], у Н. Ю. Марголиса [18], в публикациях А. Н. Моисеева [21], а также в совместном труде Е. П. Полина, А. Н. Моисеева и К. Войтикова [24]. Все эти материалы были изучены до того, как возникла идея разработки алгоритма автоматизированного формирования матриц переходов в среде Google Colaboratory на Python, обходящегося без имитационного моделирования.
Одноканальные системы массового обслуживания с абсолютным приоритетом и нетерпеливыми заявками являются важным объектом исследования в тех областях, где необходимо эффективно управлять потоками запросов и обеспечивать качественное обслуживание клиентов. Такие системы находят применение в телекоммуникациях, информационных технологиях, здравоохранении, общественном питании и других сферах. Их изучение позволяет разрабатывать оптимальные стратегии обслуживания, минимизировать время ожидания различных классов заявок и поддерживать высокий уровень качества обслуживания даже в условиях перегрузки или изменяющихся внешних условий.
Возрастающая потребность в гибких и адаптивных системах управления потоками заявок при ограниченных ресурсах усиливает научную и практическую значимость рассматриваемых моделей. Современные технические и организационные комплексы — такие как call-центры, серверы обработки онлайн-запросов, медицинские регистратуры — функционируют в условиях, когда невозможно одновременно обработать все поступающие обращения. В таких ситуациях критически важно наличие механизмов приоритетного обслуживания и моделирования потерь, вызванных нетерпеливостью заявок.
Системы с абсолютным приоритетом допускают прерывание текущего обслуживания в случае поступления более приоритетной заявки. Примеры прикладного использования таких моделей включают:
- службы экстренного реагирования (медицина, МЧС), где текущая задача может быть прервана ради более срочного вызова;
- вычислительные системы и сетевые протоколы, приостанавливающие фоновую обработку ради приоритетных задач;
- логистические и складские системы, перераспределяющие ресурсы в пользу срочных заказов.
Такое поведение возможно только в системах, допускающих прерывание обслуживания, что требует строгого математического описания и существенно влияет на расчёт характеристик: вероятностей отказа, среднего времени ожидания, загрузки системы и других метрик.
Особый интерес представляет характеристика «нетерпеливости» — поведенческого параметра, описывающего склонность заявок покидать систему при превышении допустимого времени ожидания. На практике это проявляется, например, в отказе пользователей от онлайн-сервиса при долгой загрузке, уходе пациентов из очереди или покупателей с кассы.
Математическое моделирование «нетерпеливости» реализуется через случайные величины с различными распределениями (экспоненциальным, равномерным и др.). Совмещение моделей с приоритетом и нетерпеливостью представляет собой сложную задачу из-за возрастания числа возможных состояний системы и усложнённой логики переходов между ними.
Особое внимание в работе уделено одноканальным системам обслуживания. Такие модели представляют значительный интерес с теоретической и практической точек зрения: в отличие от многоканальных систем, здесь обслуживание осуществляется строго по одному запросу за раз, что резко обостряет проблему выбора — какая заявка будет обслужена, а какая потеряна.
Применение моделей одноканальных систем массового обслуживания с абсолютным приоритетом и нетерпеливыми заявками встречается во множестве прикладных областей. Рассмотрим наиболее характерные примеры таких систем.
Авиадиспетчерские службы.
В условиях ограниченных ресурсов управления воздушным движением сигналы от воздушных судов, находящихся в аварийной ситуации, обладают высшим приоритетом и могут прерывать обслуживание гражданских рейсов. Система функционирует в одноканальном режиме (например, обслуживание одним диспетчером), где приоритет определяется степенью угрозы безопасности полётов. Проявление нетерпеливости выражается в отказе от вылета или перенаправлении рейса при длительном времени ожидания разрешения на посадку или взлёт.
Медицинская регистратура.
В медицинских учреждениях с ограниченным числом регистраторов (в предельном случае — один) экстренные пациенты (например, направленные на срочную госпитализацию) обслуживаются вне очереди, прерывая текущее взаимодействие с пациентами с низким приоритетом. Заявки с низким приоритетом могут покинуть очередь при превышении допустимого времени ожидания, что моделируется через параметр нетерпеливости.
Логистические и складские системы.
В логистических и складских системах с ограниченными ресурсами обработки заказов перераспределение ресурсов осуществляется в пользу срочных или приоритетных заказов. Обслуживание текущих заявок может быть прервано для обработки более важных грузов или заказов с кратчайшими сроками доставки. Заявки с низким приоритетом, не выдержавшие ожидания, могут быть отклонены либо перенаправлены, что соответствует модели систем с нетерпеливыми заявками.
Вычислительные системы и сетевые протоколы.
Одноканальные вычислительные ресурсы (например, однопроцессорные серверы или узлы обработки данных) и сетевые протоколы реализуют приоритетную обработку задач с возможностью приостановки выполнения фоновых процессов ради срочных и приоритетных заданий. В таких системах фоновые задачи могут быть прерваны или отменены при превышении допустимого времени ожидания, что отражает поведение нетерпеливых заявок.
Для анализа таких моделей используются:
- построение графа состояний в виде непрерывной цепи Маркова;
- формулировка и решение системы уравнений Колмогорова;
- численные методы и автоматизированные алгоритмы получения стационарного распределения.
Таким образом, разработка математического и программного инструментария для анализа одноканальных СМО с абсолютным приоритетом и нетерпеливыми заявками способствует решению актуальных задач в условиях высокой нагрузки, роста клиентских ожиданий и ограниченных вычислительных ресурсов.
Цель работы состоит в построении и исследовании системы обслуживания с абсолютным приоритетом и нетерпеливыми заявками вида M21 (M1,M2)|1| (N15N2)U её частного случая M21 (M1,M2) |1| (2,2). А также реализация алгоритма автоматического построения матрицы переходов состояний и решения системы уравнений Колмогорова для определения стационарного распределения вероятностей и анализа характеристик качества обслуживания.
В соответствии с целью были поставлены и решены следующие задачи:
• построить модель СМО с абсолютным приоритетом и нетерпеливыми заявками вида M21 (M1,M2)|1| (2,2);
• построить граф возможных состояний системы M2 | (M , M ) | 1 | (2, 2) ;
• составить систему уравнений Колмогорова для стационарного распределения вероятностей состояний системы M21 (MPM2) |1|(2,2);
• реализовать алгоритм для численного нахождения распределения вероятностей системы M21 (M1,M2)|1| (2,2);
• определить вероятности нахождения системы M21 (MPM2) |1| (2,2) в различных состояниях;
• построить модель СМО с абсолютным приоритетом и нетерпеливыми заявками вида M2 |(M1,M2)|1| (N1,N2);
• составить систему уравнений Колмогорова для стационарного
распределения вероятностей состояний системы
M2|(M1,M2)|1|(N1,N2);
• реализовать алгоритм автоматического построения матриц системы с произвольным объемом бункеров;
• определить вероятности нахождения системы M2 |(M1,M2)|1|(N1,N2) различных состояниях.
Системы массового обслуживания с абсолютным приоритетом и нетерпеливыми заявками представляют собой особый класс систем, где каждая заявка имеет свойство приоритета и может быть характеризована степенью нетерпимости к ожиданию обслуживания. Абсолютный приоритет означает, что заявки с более высоким приоритетом имеют преимущество перед заявками с более низким приоритетом и должны быть обработаны в первую очередь. Нетерпеливые заявки требуют немедленного или приоритетного обслуживания из-за ограниченности их времени ожидания. Основные модели СМО приоритетного обслуживания изложены в работах О. И. Бронштейн [1], Б. В. Гнеденко [7], Н. К. Джейсуол [9], С. П. Моисеева [20]. Модели с нетерпеливыми заявками рассмотрены в работах А. И. Коваленко [13], Д. А. Малышева [15].
Для более глубокого понимания и анализа СМО с абсолютным приоритетом и нетерпеливыми заявками используются различные математические методы, включая теорию вероятностей, статистику, теорию случайных процессов и моделирование. Теория вероятностей и случайных процессов играют ключевую роль в изучении теории массового обслуживания, поскольку они предоставляют математические инструменты и методы анализа, необходимые для оценки производительности и оптимизации систем обслуживания. Основы этих дисциплин подробно изложены в пособиях О.Н. Галажинской, С.П. Моисеевой [3-4], А.А. Назарова, А.Ф. Терпугова [22], С.П. Моисеевой [19], О. Н. Галажинской [2], Д. Д. Даммер [8], Т.В. Кабановой [10-11].
Для детального изучения динамики работы СМО часто создают её имитационную модель. Подробные примеры построения таких моделей можно найти в работах Е. Ю. Лисовской и M. Pagano [14], у Н. Ю. Марголиса [18], в публикациях А. Н. Моисеева [21], а также в совместном труде Е. П. Полина, А. Н. Моисеева и К. Войтикова [24]. Все эти материалы были изучены до того, как возникла идея разработки алгоритма автоматизированного формирования матриц переходов в среде Google Colaboratory на Python, обходящегося без имитационного моделирования.
Одноканальные системы массового обслуживания с абсолютным приоритетом и нетерпеливыми заявками являются важным объектом исследования в тех областях, где необходимо эффективно управлять потоками запросов и обеспечивать качественное обслуживание клиентов. Такие системы находят применение в телекоммуникациях, информационных технологиях, здравоохранении, общественном питании и других сферах. Их изучение позволяет разрабатывать оптимальные стратегии обслуживания, минимизировать время ожидания различных классов заявок и поддерживать высокий уровень качества обслуживания даже в условиях перегрузки или изменяющихся внешних условий.
Возрастающая потребность в гибких и адаптивных системах управления потоками заявок при ограниченных ресурсах усиливает научную и практическую значимость рассматриваемых моделей. Современные технические и организационные комплексы — такие как call-центры, серверы обработки онлайн-запросов, медицинские регистратуры — функционируют в условиях, когда невозможно одновременно обработать все поступающие обращения. В таких ситуациях критически важно наличие механизмов приоритетного обслуживания и моделирования потерь, вызванных нетерпеливостью заявок.
Системы с абсолютным приоритетом допускают прерывание текущего обслуживания в случае поступления более приоритетной заявки. Примеры прикладного использования таких моделей включают:
- службы экстренного реагирования (медицина, МЧС), где текущая задача может быть прервана ради более срочного вызова;
- вычислительные системы и сетевые протоколы, приостанавливающие фоновую обработку ради приоритетных задач;
- логистические и складские системы, перераспределяющие ресурсы в пользу срочных заказов.
Такое поведение возможно только в системах, допускающих прерывание обслуживания, что требует строгого математического описания и существенно влияет на расчёт характеристик: вероятностей отказа, среднего времени ожидания, загрузки системы и других метрик.
Особый интерес представляет характеристика «нетерпеливости» — поведенческого параметра, описывающего склонность заявок покидать систему при превышении допустимого времени ожидания. На практике это проявляется, например, в отказе пользователей от онлайн-сервиса при долгой загрузке, уходе пациентов из очереди или покупателей с кассы.
Математическое моделирование «нетерпеливости» реализуется через случайные величины с различными распределениями (экспоненциальным, равномерным и др.). Совмещение моделей с приоритетом и нетерпеливостью представляет собой сложную задачу из-за возрастания числа возможных состояний системы и усложнённой логики переходов между ними.
Особое внимание в работе уделено одноканальным системам обслуживания. Такие модели представляют значительный интерес с теоретической и практической точек зрения: в отличие от многоканальных систем, здесь обслуживание осуществляется строго по одному запросу за раз, что резко обостряет проблему выбора — какая заявка будет обслужена, а какая потеряна.
Применение моделей одноканальных систем массового обслуживания с абсолютным приоритетом и нетерпеливыми заявками встречается во множестве прикладных областей. Рассмотрим наиболее характерные примеры таких систем.
Авиадиспетчерские службы.
В условиях ограниченных ресурсов управления воздушным движением сигналы от воздушных судов, находящихся в аварийной ситуации, обладают высшим приоритетом и могут прерывать обслуживание гражданских рейсов. Система функционирует в одноканальном режиме (например, обслуживание одним диспетчером), где приоритет определяется степенью угрозы безопасности полётов. Проявление нетерпеливости выражается в отказе от вылета или перенаправлении рейса при длительном времени ожидания разрешения на посадку или взлёт.
Медицинская регистратура.
В медицинских учреждениях с ограниченным числом регистраторов (в предельном случае — один) экстренные пациенты (например, направленные на срочную госпитализацию) обслуживаются вне очереди, прерывая текущее взаимодействие с пациентами с низким приоритетом. Заявки с низким приоритетом могут покинуть очередь при превышении допустимого времени ожидания, что моделируется через параметр нетерпеливости.
Логистические и складские системы.
В логистических и складских системах с ограниченными ресурсами обработки заказов перераспределение ресурсов осуществляется в пользу срочных или приоритетных заказов. Обслуживание текущих заявок может быть прервано для обработки более важных грузов или заказов с кратчайшими сроками доставки. Заявки с низким приоритетом, не выдержавшие ожидания, могут быть отклонены либо перенаправлены, что соответствует модели систем с нетерпеливыми заявками.
Вычислительные системы и сетевые протоколы.
Одноканальные вычислительные ресурсы (например, однопроцессорные серверы или узлы обработки данных) и сетевые протоколы реализуют приоритетную обработку задач с возможностью приостановки выполнения фоновых процессов ради срочных и приоритетных заданий. В таких системах фоновые задачи могут быть прерваны или отменены при превышении допустимого времени ожидания, что отражает поведение нетерпеливых заявок.
Для анализа таких моделей используются:
- построение графа состояний в виде непрерывной цепи Маркова;
- формулировка и решение системы уравнений Колмогорова;
- численные методы и автоматизированные алгоритмы получения стационарного распределения.
Таким образом, разработка математического и программного инструментария для анализа одноканальных СМО с абсолютным приоритетом и нетерпеливыми заявками способствует решению актуальных задач в условиях высокой нагрузки, роста клиентских ожиданий и ограниченных вычислительных ресурсов.
Цель работы состоит в построении и исследовании системы обслуживания с абсолютным приоритетом и нетерпеливыми заявками вида M21 (M1,M2)|1| (N15N2)U её частного случая M21 (M1,M2) |1| (2,2). А также реализация алгоритма автоматического построения матрицы переходов состояний и решения системы уравнений Колмогорова для определения стационарного распределения вероятностей и анализа характеристик качества обслуживания.
В соответствии с целью были поставлены и решены следующие задачи:
• построить модель СМО с абсолютным приоритетом и нетерпеливыми заявками вида M21 (M1,M2)|1| (2,2);
• построить граф возможных состояний системы M2 | (M , M ) | 1 | (2, 2) ;
• составить систему уравнений Колмогорова для стационарного распределения вероятностей состояний системы M21 (MPM2) |1|(2,2);
• реализовать алгоритм для численного нахождения распределения вероятностей системы M21 (M1,M2)|1| (2,2);
• определить вероятности нахождения системы M21 (MPM2) |1| (2,2) в различных состояниях;
• построить модель СМО с абсолютным приоритетом и нетерпеливыми заявками вида M2 |(M1,M2)|1| (N1,N2);
• составить систему уравнений Колмогорова для стационарного
распределения вероятностей состояний системы
M2|(M1,M2)|1|(N1,N2);
• реализовать алгоритм автоматического построения матриц системы с произвольным объемом бункеров;
• определить вероятности нахождения системы M2 |(M1,M2)|1|(N1,N2) различных состояниях.
В ходе исследования была успешно достигнута цель работы, которая заключалась в построении и изучении системы обслуживания с абсолютным приоритетом и нетерпеливыми заявками. Для достижения этой цели были решены следующие задачи:
1) построена модель СМО с абсолютным приоритетом и нетерпеливыми заявками вида M2 | (MPM2) |1|(2,2);
2) построен граф возможных состояний системы м21 (MPM2) |1|(2,2);
3) составлена система уравнений Колмогорова для стационарного распределения вероятностей состояний
системы M21 (M1,M2)|1| (2,2);
4) реализован алгоритм для численного нахождения распределения вероятностей системы M21 (M1,M2)|1| (2,2);
5) определены вероятности нахождения системы м21 (MPM2)| 1| (2,2) в различных состояниях;
6) построена модель СМО с абсолютным приоритетом и нетерпеливыми заявками вида м21 (MPM2) 111 (NPN2) ;
7) составлена система уравнений Колмогорова для стационарного распределения вероятностей состояний
системы M2 |(M1,M2)|1|(N1,N2);
8) реализован алгоритм автоматического построения матриц системы с произвольным объемом бункеров;
9) определены вероятности нахождения системы M21 (M1,M2)|1| (N1,N2) различных состояниях.
По материалам исследований были сделаны доклады на следующих конференциях и опубликованы статьи:
1. Мануйлова, Е. А. Однолинейная смо вида M | (M1,M2) |1| (N1,N2) с абсолютным приоритетом и нетерпеливыми заявками / Е. А. Мануйлова, С. П. Моисеева // Ляпуновские чтения - 2024 : Материалы 40-й международной конференции, Иркутск, 02-06 декабря 2024 года. - Иркутск: Институт динамики систем и теории управления им. В.М. Матросова СО РАН, 2024. - С. 141-142.
2. Мануйлова, Е. А. Система массового обслуживания с абсолютным приоритетом и нетерпеливыми заявками / Е. А. Мануйлова, С. П. Моисеева // Математика : Материалы 62-й Междунар. науч. студ. конф. 17-23 апреля 2024 г. - Новосиб. гос. ун-т. - Новосибирск: ИПЦ НГУ, 2024. - С. 205-206.
1) построена модель СМО с абсолютным приоритетом и нетерпеливыми заявками вида M2 | (MPM2) |1|(2,2);
2) построен граф возможных состояний системы м21 (MPM2) |1|(2,2);
3) составлена система уравнений Колмогорова для стационарного распределения вероятностей состояний
системы M21 (M1,M2)|1| (2,2);
4) реализован алгоритм для численного нахождения распределения вероятностей системы M21 (M1,M2)|1| (2,2);
5) определены вероятности нахождения системы м21 (MPM2)| 1| (2,2) в различных состояниях;
6) построена модель СМО с абсолютным приоритетом и нетерпеливыми заявками вида м21 (MPM2) 111 (NPN2) ;
7) составлена система уравнений Колмогорова для стационарного распределения вероятностей состояний
системы M2 |(M1,M2)|1|(N1,N2);
8) реализован алгоритм автоматического построения матриц системы с произвольным объемом бункеров;
9) определены вероятности нахождения системы M21 (M1,M2)|1| (N1,N2) различных состояниях.
По материалам исследований были сделаны доклады на следующих конференциях и опубликованы статьи:
1. Мануйлова, Е. А. Однолинейная смо вида M | (M1,M2) |1| (N1,N2) с абсолютным приоритетом и нетерпеливыми заявками / Е. А. Мануйлова, С. П. Моисеева // Ляпуновские чтения - 2024 : Материалы 40-й международной конференции, Иркутск, 02-06 декабря 2024 года. - Иркутск: Институт динамики систем и теории управления им. В.М. Матросова СО РАН, 2024. - С. 141-142.
2. Мануйлова, Е. А. Система массового обслуживания с абсолютным приоритетом и нетерпеливыми заявками / Е. А. Мануйлова, С. П. Моисеева // Математика : Материалы 62-й Междунар. науч. студ. конф. 17-23 апреля 2024 г. - Новосиб. гос. ун-т. - Новосибирск: ИПЦ НГУ, 2024. - С. 205-206.
