Бесконечнолинейные СМО с потоками отрицательных заявок
|
АННОТАЦИЯ 2
ВВЕДЕНИЕ 4
1 Марковские системы массового обслуживания с отрицательными
заявками 8
1.1 Модель системы обслуживания для случая, когда отрицательная заявка
не ждет положительную 8
1.1.1 Функциональная модель 8
1.1.2 Математическая модель 9
1.2 Модель системы обслуживания для случая, когда отрицательная заявка
ожидает прихода положительной 11
1.2.1 Функциональная модель 11
1.2.2 Математическая модель 11
1.3 Модель системы обслуживания для случая, когда отрицательная заявка
ожидает прихода положительной в течении ограниченного времени 16
1.3.1 Функциональная модель 16
1.3.2 Математическая модель 16
1.4 Численные алгоритмы для вычисления распределения вероятностей
числа положительных и отрицательных заявок 20
2 Исследование процесса изменения числа положительных заявок при
наличии отрицательной заявки в системе 30
2.1 Функциональная модель 30
2.2 Математическая модель СМО с отрицательной заявкой 30
2.3 Система дифференциальных уравнений Колмогорова 31
2.4 Производящие функции 33
2.5 Допредельное распределение вероятностей числа положительных
заявок в системе 41
2.6 Алгоритм для вычисления распределения вероятностей числа
положительных заявок 42
3 Асимптотический анализ системы, в которой отрицательная заявка ожидает прихода положительной 47
3.1 Функциональная модель 47
3.2 Математическая модель 47
3.3 Система дифференциальных уравнений Колмогорова 48
3.4 Асимптотический анализ первого порядка 49
3.5 Асимптотический анализ второго порядка 52
3.6 Численный анализ асимптотического распределения вероятностей числа положительных заявок в системе 60
ЗАКЛЮЧЕНИЕ 65
ЛИТЕРАТУРА 68
ВВЕДЕНИЕ 4
1 Марковские системы массового обслуживания с отрицательными
заявками 8
1.1 Модель системы обслуживания для случая, когда отрицательная заявка
не ждет положительную 8
1.1.1 Функциональная модель 8
1.1.2 Математическая модель 9
1.2 Модель системы обслуживания для случая, когда отрицательная заявка
ожидает прихода положительной 11
1.2.1 Функциональная модель 11
1.2.2 Математическая модель 11
1.3 Модель системы обслуживания для случая, когда отрицательная заявка
ожидает прихода положительной в течении ограниченного времени 16
1.3.1 Функциональная модель 16
1.3.2 Математическая модель 16
1.4 Численные алгоритмы для вычисления распределения вероятностей
числа положительных и отрицательных заявок 20
2 Исследование процесса изменения числа положительных заявок при
наличии отрицательной заявки в системе 30
2.1 Функциональная модель 30
2.2 Математическая модель СМО с отрицательной заявкой 30
2.3 Система дифференциальных уравнений Колмогорова 31
2.4 Производящие функции 33
2.5 Допредельное распределение вероятностей числа положительных
заявок в системе 41
2.6 Алгоритм для вычисления распределения вероятностей числа
положительных заявок 42
3 Асимптотический анализ системы, в которой отрицательная заявка ожидает прихода положительной 47
3.1 Функциональная модель 47
3.2 Математическая модель 47
3.3 Система дифференциальных уравнений Колмогорова 48
3.4 Асимптотический анализ первого порядка 49
3.5 Асимптотический анализ второго порядка 52
3.6 Численный анализ асимптотического распределения вероятностей числа положительных заявок в системе 60
ЗАКЛЮЧЕНИЕ 65
ЛИТЕРАТУРА 68
В современном мире сферы обслуживания, такие как клиентские сервисы, транспортные системы, медицинские учреждения и многие другие, сталкиваются с растущими потоками заявок, где как положительные, так и отрицательные обращения требуют эффективного управления. Подобные ситуации нередко включают в себя не только обслуживание клиентов, но и управление нежелательными событиями или запросами. Информационные технологии играют все более важную роль в повседневной деятельности как предприятий, так и частных лиц. От электронной коммерции до социальных сетей, наша цифровая инфраструктура подвергается постоянному потоку запросов, которые можно рассматривать как заявки в системе массового обслуживания (СМО).
В реальной жизни, сфера информационных технологий сталкивается с различными вызовами, связанными с обработкой разнообразных заявок и выявлением оптимальных стратегий управления. Например, атаки злоумышленников или сбои в работе могут негативно отразиться на производительности и безопасности информационных систем. Отрицательные заявки, как и в реальной жизни, в системах обслуживания могут не только потреблять ресурсы, но и влиять на обработку положительных заявок. Например, они могут вызывать задержки или даже блокировки процессов обслуживания, что отрицательно сказывается на общей эффективности системы.
Системы и сети с отрицательными заявками были введены Е. Геленбе [31, 32], где он представил новый класс сетей массового обслуживания с двумя типами заявок. Первый тип клиентов — это постоянные клиенты, и сервер обслуживает их обычным образом. Таких клиентов называют положительными или постоянными клиентами. Положительный клиент подчиняется установленным правилам обслуживания и маршрутизации, которые определяют динамику рассматриваемой сети. С другой стороны, второй тип отрицательных требований действует как сигнал, побуждающий положительного запроса в узле, если таковой имеется, немедленно покинуть узел. Изначально такие сети применялись для моделирования биофизических нейронных сетей. В этом контексте узел представляет нейрон. Положительные и отрицательные запросы, маршрутизирующиеся в сети, представляют собой сигналы возбуждения и торможения, которые увеличивают или уменьшают в единицу потенциал нейрона, к которому они приходят. Расширения исходной сети Геленбе приводят к созданию универсального класса, называемого в литературе G-сетями, поскольку он обеспечивает объединяющую основу для массового обслуживания и нейронных сетей. Эта аналогия подробно обсуждалась в обзорных статьях [25, 30].
С момента своего появления сети и системы массового обслуживания с отрицательными заявками изучались многими авторами, и было рассмотрено несколько расширений, в которых отрицательные поступления влияют на поведение сети различными способами. В литературе по этому предмету было представлено несколько различных возможностей:
Индивидуальное удаление. Отрицательный запрос отменяет положительный запрос в очереди, в которую он поступил, или не оказывает никакого эффекта, если очередь пуста.
Пакетное удаление. Отрицательное поступление вынуждает группу клиентов покинуть сеть.
Катастрофа. Отрицательное прибытие приводит к катастрофе в узле, в который оно прибывает. Таким образом, все клиенты удаляются автоматически.
Вызванное движение. Отрицательное поступление действует как сигнал, который либо запускает мгновенное перемещение клиента в какой - либо другой узел, либо вынуждает группу клиентов покинуть сеть.
Случайное удаление работы. При приходе отрицательного заказа из системы мгновенно удаляется случайный объем работы.
Первые статьи о G-сетях и одноузловых очередях с отрицательными заявками (G-очередях) были написаны в конце 20-го века. Таким образом, основные результаты были разработаны за короткий период времени. Возможно, из-за этой новизны и особого интереса к G-сетям многие авторы одновременно работали над схожими темами исследований. Следует отметить обзорные работы [2, 45], и наиболее полный обзор, включающий более 300 ссылок в работе [44].
СМО с отрицательными клиентами можно использовать для моделирования сбоев и потерь пакетов, завершения задач при спекулятивном параллелизме, неисправных компонентов в производственных системах и поломок серверов, а также сети реакций взаимодействующих молекул. Отрицательные запросы с соответствующей дисциплиной уничтожения расширяют возможности моделирования этих моделей очередей, поскольку такие явления в реальном мире, как сбои, потеря пакетов в радиоинтерфейсе, балансировка нагрузки и катастрофы, могут быть легко зафиксированы. Среди современных работ следует отметить [28, 29, 33-37, 39].
В настоящее время применение таких систем достаточно широкое от практических задач в телекоммуникациях [2, 18], до социально¬
экономических постановок [8]. Бесконечнолинейная СМО с отрицательными заявками была впервые предложена А. А. Натаном [16] и в дальнейшем модифицирована в работах А. А. Назарова и Н. М. Феропонтовой [13, 14].
СМО с положительными и отрицательными заявками представляет собой класс систем, в которых положительные заявки обслуживаются в течение случайного промежутка времени, в то время как отрицательные заявки могут вызывать различные взаимодействия с положительными. Эти взаимодействия могут привести к задержкам, сбоям или даже разрушению системы.
Изучению и анализу таких моделей посвящена данная выпускная квалификационная работа магистра. Целью работы является исследование математических моделей систем массового обслуживания с отрицательными заявками различного поведения в предложенных системах.
В соответствии с целью были поставлены и решены следующие задачи:
1. Построение математических моделей СМО с отрицательными заявками без ожидания, с ожиданием, с ограниченным ожиданием; с отрицательной заявкой, которая может полностью «уничтожить» все положительные заявки в системе; с отрицательными заявками, которые накапливаются в системе и при этом не взаимодействуют с уже обслуживающими положительными заявками.
2. Исследование методом производящих и характеристических функций систему с отрицательной заявкой, которая может полностью «уничтожить» все положительные заявки в системе.
3. Исследование методом асимптотического анализа систему с отрицательными заявками, которые накапливаются в системе и при этом не взаимодействуют с уже обслуживающими положительными заявками.
4. Разработка численных методов расчета допредельных распределений вероятностей числа положительных заявок в системе без ожидания; распределений вероятностей числа положительных и отрицательных заявок в системах с ожиданием и ограниченным ожиданием, а также асимптотического распределения вероятностей числа положительных заявок в системе с накопленными отрицательными заявками.
5. Составление комплекса проблемно-ориентированных программ, реализующих предложенные численные методы.
1 Марковские системы массового обслуживания с отрицательными заявками
В данной главе рассматриваются марковские модели систем массового обслуживания с отрицательными заявками различного поведения. Первая модель представляет систему массового обслуживания для случая, когда отрицательная заявка не ждет положительную. Вторая модель представляет систему массового обслуживания для случая, когда отрицательная заявка ожидает прихода положительной. Третья модель представляет систему массового обслуживания для случая, когда отрицательная заявка ожидает прихода положительной с ограниченным ожиданием. В конце главы приведены численные алгоритмы для вычисления распределения вероятностей числа положительных и отрицательных заявок во всех рассмотренных системах.
В реальной жизни, сфера информационных технологий сталкивается с различными вызовами, связанными с обработкой разнообразных заявок и выявлением оптимальных стратегий управления. Например, атаки злоумышленников или сбои в работе могут негативно отразиться на производительности и безопасности информационных систем. Отрицательные заявки, как и в реальной жизни, в системах обслуживания могут не только потреблять ресурсы, но и влиять на обработку положительных заявок. Например, они могут вызывать задержки или даже блокировки процессов обслуживания, что отрицательно сказывается на общей эффективности системы.
Системы и сети с отрицательными заявками были введены Е. Геленбе [31, 32], где он представил новый класс сетей массового обслуживания с двумя типами заявок. Первый тип клиентов — это постоянные клиенты, и сервер обслуживает их обычным образом. Таких клиентов называют положительными или постоянными клиентами. Положительный клиент подчиняется установленным правилам обслуживания и маршрутизации, которые определяют динамику рассматриваемой сети. С другой стороны, второй тип отрицательных требований действует как сигнал, побуждающий положительного запроса в узле, если таковой имеется, немедленно покинуть узел. Изначально такие сети применялись для моделирования биофизических нейронных сетей. В этом контексте узел представляет нейрон. Положительные и отрицательные запросы, маршрутизирующиеся в сети, представляют собой сигналы возбуждения и торможения, которые увеличивают или уменьшают в единицу потенциал нейрона, к которому они приходят. Расширения исходной сети Геленбе приводят к созданию универсального класса, называемого в литературе G-сетями, поскольку он обеспечивает объединяющую основу для массового обслуживания и нейронных сетей. Эта аналогия подробно обсуждалась в обзорных статьях [25, 30].
С момента своего появления сети и системы массового обслуживания с отрицательными заявками изучались многими авторами, и было рассмотрено несколько расширений, в которых отрицательные поступления влияют на поведение сети различными способами. В литературе по этому предмету было представлено несколько различных возможностей:
Индивидуальное удаление. Отрицательный запрос отменяет положительный запрос в очереди, в которую он поступил, или не оказывает никакого эффекта, если очередь пуста.
Пакетное удаление. Отрицательное поступление вынуждает группу клиентов покинуть сеть.
Катастрофа. Отрицательное прибытие приводит к катастрофе в узле, в который оно прибывает. Таким образом, все клиенты удаляются автоматически.
Вызванное движение. Отрицательное поступление действует как сигнал, который либо запускает мгновенное перемещение клиента в какой - либо другой узел, либо вынуждает группу клиентов покинуть сеть.
Случайное удаление работы. При приходе отрицательного заказа из системы мгновенно удаляется случайный объем работы.
Первые статьи о G-сетях и одноузловых очередях с отрицательными заявками (G-очередях) были написаны в конце 20-го века. Таким образом, основные результаты были разработаны за короткий период времени. Возможно, из-за этой новизны и особого интереса к G-сетям многие авторы одновременно работали над схожими темами исследований. Следует отметить обзорные работы [2, 45], и наиболее полный обзор, включающий более 300 ссылок в работе [44].
СМО с отрицательными клиентами можно использовать для моделирования сбоев и потерь пакетов, завершения задач при спекулятивном параллелизме, неисправных компонентов в производственных системах и поломок серверов, а также сети реакций взаимодействующих молекул. Отрицательные запросы с соответствующей дисциплиной уничтожения расширяют возможности моделирования этих моделей очередей, поскольку такие явления в реальном мире, как сбои, потеря пакетов в радиоинтерфейсе, балансировка нагрузки и катастрофы, могут быть легко зафиксированы. Среди современных работ следует отметить [28, 29, 33-37, 39].
В настоящее время применение таких систем достаточно широкое от практических задач в телекоммуникациях [2, 18], до социально¬
экономических постановок [8]. Бесконечнолинейная СМО с отрицательными заявками была впервые предложена А. А. Натаном [16] и в дальнейшем модифицирована в работах А. А. Назарова и Н. М. Феропонтовой [13, 14].
СМО с положительными и отрицательными заявками представляет собой класс систем, в которых положительные заявки обслуживаются в течение случайного промежутка времени, в то время как отрицательные заявки могут вызывать различные взаимодействия с положительными. Эти взаимодействия могут привести к задержкам, сбоям или даже разрушению системы.
Изучению и анализу таких моделей посвящена данная выпускная квалификационная работа магистра. Целью работы является исследование математических моделей систем массового обслуживания с отрицательными заявками различного поведения в предложенных системах.
В соответствии с целью были поставлены и решены следующие задачи:
1. Построение математических моделей СМО с отрицательными заявками без ожидания, с ожиданием, с ограниченным ожиданием; с отрицательной заявкой, которая может полностью «уничтожить» все положительные заявки в системе; с отрицательными заявками, которые накапливаются в системе и при этом не взаимодействуют с уже обслуживающими положительными заявками.
2. Исследование методом производящих и характеристических функций систему с отрицательной заявкой, которая может полностью «уничтожить» все положительные заявки в системе.
3. Исследование методом асимптотического анализа систему с отрицательными заявками, которые накапливаются в системе и при этом не взаимодействуют с уже обслуживающими положительными заявками.
4. Разработка численных методов расчета допредельных распределений вероятностей числа положительных заявок в системе без ожидания; распределений вероятностей числа положительных и отрицательных заявок в системах с ожиданием и ограниченным ожиданием, а также асимптотического распределения вероятностей числа положительных заявок в системе с накопленными отрицательными заявками.
5. Составление комплекса проблемно-ориентированных программ, реализующих предложенные численные методы.
1 Марковские системы массового обслуживания с отрицательными заявками
В данной главе рассматриваются марковские модели систем массового обслуживания с отрицательными заявками различного поведения. Первая модель представляет систему массового обслуживания для случая, когда отрицательная заявка не ждет положительную. Вторая модель представляет систему массового обслуживания для случая, когда отрицательная заявка ожидает прихода положительной. Третья модель представляет систему массового обслуживания для случая, когда отрицательная заявка ожидает прихода положительной с ограниченным ожиданием. В конце главы приведены численные алгоритмы для вычисления распределения вероятностей числа положительных и отрицательных заявок во всех рассмотренных системах.
В представленной выпускной квалификационной работе магистра исследованы математические модели систем массового обслуживания с входящими простейшими потоками положительных и отрицательных заявок, в ситуациях, когда отрицательные заявки не ждут положительные, когда отрицательные заявки ждут положительные неограниченное и ограниченное время; математическая модель системы, в которой одна отрицательная заявка «уничтожает» обсуживающиеся положительные заявки, а также система, в которой отрицательные заявки накапливаются и не взаимодействуют с обсуживающимися положительными.
В главе 1 построены функциональная и математическая модели систем массового обслуживания с отрицательными заявками различного поведения. Для приведенных моделей был построен рекуррентный алгоритм для нахождения распределения вероятностей числа положительных заявок в системе без ожидания и распределения вероятностей числа положительных и отрицательных заявок в системах с ограниченным и неограниченным ожиданием. Разработан комплекс численных методов для расчета распределений вероятностей числа положительных и отрицательных заявок в системах.
В главе 2 построены функциональная и математическая модели системы массового обслуживания с отрицательной заявкой, которая поступает в систему и постепенно уничтожает обслуживаемые положительные заявки, подобно информационному вирусу. Для приведенной модели с помощью производящих функций, характеристических функций, а также обратного преобразования Фурье было получено распределение вероятностей числа положительных заявок в системе. Разработан комплекс численных методов для расчета распределения вероятностей числа положительных заявок в рассмотренной системе.
В главе 3 построены функциональная и математическая модели
системы массового обслуживания с накопленными отрицательными заявками, которые, при поступлении в систему не взаимодействуют с уже обслуживающими положительными заявками, а ждут новые положительные заявки для «уничтожения». Для приведенной модели выполнен асимптотический анализ первого и второго порядков (в условии эквивалентно высокой интенсивности входящих потоков). Разработан комплекс численных методов для построения асимптотического распределения вероятностей числа положительных заявок в рассмотренной системе.
По материалам исследований были сделаны доклады на следующих конференциях:
1) Информационные технологии и математическое моделирование (ИТММ-2022). XXI Международная конференция им. А.Ф. Терпугова. 24.10.2022 - 29.10.2022 (Карши, Узбекистан)
2) Международный научный семинар молодых ученых в рамках 50- летия кафедры теории вероятностей и математической статистики. Томск, 01.12.2022 - 10.12.2022.
3) Системы управления, информационные технологии и математическое моделирование-2023 (СУИТИММ-2023). V Всероссийская с международным участием научно-практическая конференция студентов, аспирантов и работников образования и промышленности. Омск, 25.04.2023 - 26.04.2023.
4) XIV конференция с международным участием
«Информационные и телекоммуникационные технологии и математическое моделирование высокотехнологичных систем». Москва, 08.04.2024 -
12.04.2024.
Результаты исследования были опубликованы:
1) Королев Д. А., Бушкова Т. В., Моисеева С. П. Математическая модель изменения количества товара в виде СМО M(n)|M1|M2|...|Mn|w // Информационные технологии и математическое моделирование (ИТММ- 66
2022) : материалы XXI Международной конференции имени А. Ф. Терпугова, 25-29 октября 2022 г. Томск: Изд-во Том. ун-та, 2023. С. 193-198.
2) Королев Д. А., Моисеева С. П. Бесконечнолинейные системы массового обслуживания с отрицательными заявками // Системы управления, информационные технологии и математическое моделирование : материалы V Всероссийской научно-практической конференции с международным участием (Россия, Омск, 25-26 апреля 2023 г.). Омск: Издательство ОмГТУ, 2023. С. 215-221.
3) Королев Д. А., Моисеева С. П. Моделирование передачи многомодальной информации с ограничением времени жизни пакетов // материалы XIV конференции с международным участием «Информационные и телекоммуникационные технологии и математическое моделирование высокотехнологичных систем» (в печати).
Было получено свидетельство о государственной регистрации программы для электронных вычислительных машин:
1) Свидетельство о регистрации программы для ЭВМ. Программа вычисления стационарного распределения вероятностей числа отрицательных и положительных запросов на ресурсы (ПЭВМ). Свидетельство № 2023685936. 01.12.2023.
В главе 1 построены функциональная и математическая модели систем массового обслуживания с отрицательными заявками различного поведения. Для приведенных моделей был построен рекуррентный алгоритм для нахождения распределения вероятностей числа положительных заявок в системе без ожидания и распределения вероятностей числа положительных и отрицательных заявок в системах с ограниченным и неограниченным ожиданием. Разработан комплекс численных методов для расчета распределений вероятностей числа положительных и отрицательных заявок в системах.
В главе 2 построены функциональная и математическая модели системы массового обслуживания с отрицательной заявкой, которая поступает в систему и постепенно уничтожает обслуживаемые положительные заявки, подобно информационному вирусу. Для приведенной модели с помощью производящих функций, характеристических функций, а также обратного преобразования Фурье было получено распределение вероятностей числа положительных заявок в системе. Разработан комплекс численных методов для расчета распределения вероятностей числа положительных заявок в рассмотренной системе.
В главе 3 построены функциональная и математическая модели
системы массового обслуживания с накопленными отрицательными заявками, которые, при поступлении в систему не взаимодействуют с уже обслуживающими положительными заявками, а ждут новые положительные заявки для «уничтожения». Для приведенной модели выполнен асимптотический анализ первого и второго порядков (в условии эквивалентно высокой интенсивности входящих потоков). Разработан комплекс численных методов для построения асимптотического распределения вероятностей числа положительных заявок в рассмотренной системе.
По материалам исследований были сделаны доклады на следующих конференциях:
1) Информационные технологии и математическое моделирование (ИТММ-2022). XXI Международная конференция им. А.Ф. Терпугова. 24.10.2022 - 29.10.2022 (Карши, Узбекистан)
2) Международный научный семинар молодых ученых в рамках 50- летия кафедры теории вероятностей и математической статистики. Томск, 01.12.2022 - 10.12.2022.
3) Системы управления, информационные технологии и математическое моделирование-2023 (СУИТИММ-2023). V Всероссийская с международным участием научно-практическая конференция студентов, аспирантов и работников образования и промышленности. Омск, 25.04.2023 - 26.04.2023.
4) XIV конференция с международным участием
«Информационные и телекоммуникационные технологии и математическое моделирование высокотехнологичных систем». Москва, 08.04.2024 -
12.04.2024.
Результаты исследования были опубликованы:
1) Королев Д. А., Бушкова Т. В., Моисеева С. П. Математическая модель изменения количества товара в виде СМО M(n)|M1|M2|...|Mn|w // Информационные технологии и математическое моделирование (ИТММ- 66
2022) : материалы XXI Международной конференции имени А. Ф. Терпугова, 25-29 октября 2022 г. Томск: Изд-во Том. ун-та, 2023. С. 193-198.
2) Королев Д. А., Моисеева С. П. Бесконечнолинейные системы массового обслуживания с отрицательными заявками // Системы управления, информационные технологии и математическое моделирование : материалы V Всероссийской научно-практической конференции с международным участием (Россия, Омск, 25-26 апреля 2023 г.). Омск: Издательство ОмГТУ, 2023. С. 215-221.
3) Королев Д. А., Моисеева С. П. Моделирование передачи многомодальной информации с ограничением времени жизни пакетов // материалы XIV конференции с международным участием «Информационные и телекоммуникационные технологии и математическое моделирование высокотехнологичных систем» (в печати).
Было получено свидетельство о государственной регистрации программы для электронных вычислительных машин:
1) Свидетельство о регистрации программы для ЭВМ. Программа вычисления стационарного распределения вероятностей числа отрицательных и положительных запросов на ресурсы (ПЭВМ). Свидетельство № 2023685936. 01.12.2023.
