ВЗАИМОСВЯЗЬ ОБЩИХ И МАРГИНАЛЬНЫХ ХАРАКТЕРИСТИК СОСТОЯНИЯ В ДВУХКАНАЛЬНОЙ СИСТЕМЕ С ПРОСТЕЙШИМ ПОТОКОМ ПОСТУПЛЕНИЯ ЗАЯВОК
Журнал: ВЕСТНИК АСТРАХАНСКОГО ГОСУДАРСТВЕННОГО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА. СЕРИЯ: УПРАВЛЕНИЕ, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА
№ 3
, 2017
Рубрики: МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
Авторы:
1.
Астраханский государственный технический университет
Тип:
Статья
Страницы:
с 7
по 19
Статус:
Опубликован
Получено:
05.07.2017
Одобрено:
25.07.2017
Опубликовано:
25.07.2017
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 007:681.518.2
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 007:681.518.2
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
Язык материала:
русский
Ключевые слова:
система массового обслуживания, два прибора, пуассоновский входящий поток, длина очереди, маргинальные характеристики, рекуррентные соотношения
Аннотация (русский):
Рассматривается двухканальная система массового обслуживания с пуассоновским входящим потоком вызовов, в которой длительность обслуживания заявок на каждом из приборов различна. Подобные модели используются, в частности, при описании работы системы выбора заявок на обслуживание в ряде операционных систем. Введена комплексная характеристика системы в моменты окончания обслуживания хотя бы на одном из приборов, включающая длину очереди, остаточное время обслуживания на занятом приборе и время с начала текущего периода занятости. Указанная характеристика определяет состояние системы в произвольный момент времени. Получены рекуррентные соотношения, связывающие комплексную характеристику с ее маргинальными значениями, когда в системе нет очереди. В качестве одного из основных методов анализа модели выбран метод введения дополнительных событий. Получены соотношения, которые могут быть использованы для анализа средних характеристик двухканальной системы массового обслуживания, а также в процессе ее имитационного моделирования. Перенос результатов исследования на многоканальные системы с произвольным числом обслуживающих устройств позволит значимо снизить затраты времени на имитационное моделирование сложных систем, описываемых наборами многоканальных систем массового обслуживания.
Рассматривается двухканальная система массового обслуживания с пуассоновским входящим потоком вызовов, в которой длительность обслуживания заявок на каждом из приборов различна. Подобные модели используются, в частности, при описании работы системы выбора заявок на обслуживание в ряде операционных систем. Введена комплексная характеристика системы в моменты окончания обслуживания хотя бы на одном из приборов, включающая длину очереди, остаточное время обслуживания на занятом приборе и время с начала текущего периода занятости. Указанная характеристика определяет состояние системы в произвольный момент времени. Получены рекуррентные соотношения, связывающие комплексную характеристику с ее маргинальными значениями, когда в системе нет очереди. В качестве одного из основных методов анализа модели выбран метод введения дополнительных событий. Получены соотношения, которые могут быть использованы для анализа средних характеристик двухканальной системы массового обслуживания, а также в процессе ее имитационного моделирования. Перенос результатов исследования на многоканальные системы с произвольным числом обслуживающих устройств позволит значимо снизить затраты времени на имитационное моделирование сложных систем, описываемых наборами многоканальных систем массового обслуживания.
Ключевые слова:
система массового обслуживания, два прибора, пуассоновский входящий поток, длина очереди, маргинальные характеристики, рекуррентные соотношения
система массового обслуживания, два прибора, пуассоновский входящий поток, длина очереди, маргинальные характеристики, рекуррентные соотношения
Введение Многоканальные системы массового обслуживания (СМО) в самом общем случае представляют собой математические модели, включающие три компонента: поступающие потоки заявок, которые приносят в систему определенную работу; процесс обслуживания заявок с помощью обслуживающих приборов, которые и выполняют работу, принесенную заявками; дисциплину обслуживания при определении порядка выбора заявок на обслуживание в случае возникновения конкурентной ситуации, когда несколько заявок пытаются одновременно получить возможность для обслуживания. Подобными моделями описываются очень многие реальные системы в самых разных сферах [1, 2]. Однако точные соотношения для ряда важных характеристик имеются только для наиболее простых СМО описанного типа, когда все поступающие потоки являются простейшими и функции распределения длительностей обслуживания - экспоненциальными. В этом случае СМО обладает свойством отсутствия памяти, когда будущие состояния системы не зависят от ее прошлых состояний, а зависят только от ее текущего состояния. Имеются также соотношения для СМО с простейшим потоком поступлений, когда длительность обслуживания всех вызовов одинакова и равна константе [3]. Именно поэтому получение соотношений для характеристик многоканальных СМО, отличных от указанных выше, имеет важное теоретическое и прикладное значение. Цель исследования - получение соотношений, связывающих распределения длины очереди в произвольный момент времени с маргинальными состояниями системы, когда очередь отсутствует для двухканальных СМО с простейшим поступающим потоком вызовов. Соотношения указанного вида для многоканальных СМО в научной литературе отсутствуют. Описание системы и исследуемая характеристика Рассматривается СМО M|G|2|∞, в которой обслуживающие приборы, вообще говоря, не идентичны. Пусть α > 0 - интенсивность поступления вызовов; , - функция распределения длительности обслуживания вызовов на i-м приборе; - вероятность того, что при поступлении в свободную систему вызов выберет для обслуживания i-й прибор; - вероятность того, что в момент t = 0 в системе имеется k вызовов, . Основной исследуемой характеристикой является следующая. Пусть есть n-й по порядку, начиная с момента t = 0, момент окончания обслуживания вызовов; есть вероятность того, что в интервале времени на i-м приборе заканчивается n-е по порядку обслуживание (т. е. , в системе имеется по крайней мере один вызов, в момент t + dt в системе нет z-синих вызовов, с начала последнего перед t периода занятости до момента t не было s-катастроф, а прибор, отличный от j-го, будет занят ещё время меньшее x. Указанная характеристика однозначно определяет состояние системы в произвольный момент времени. Здесь под периодом занятости понимается длительность промежутка, начинающегося в последний перед t момент, когда в системе нет ни одного вызова, и заканчивающегося первым после t моментом, когда в системе не будет ни одного вызова. Обозначим как вероятность того, что в момент заканчивается обслуживание на j-м приборе, в момент t, t + dt система свободна (т. е. закончился период занятости), а с начала периода занятости, который заканчивается в момент t, не было s-катастроф. Очевидно, что где определяется аналогично , но только требование отсутствия в момент t + dt z-синих вызовов заменяется на следующее событие: в момент t + dt в системе k вызовов (k ≥ 0). Формулировка основного результата Введем обозначения Далее, введем обозначения для соответствующих маргинальных характеристик, когда очередь отсутствует: (1) (2) где . Величины включают как общие характеристики системы , так и их маргинальные значения. Отметим, что из определений следует равенство : Тогда справедливо соотношение : (3) Обозначим как r загрузку системы; тогда . Пусть величины определяются аналогично величинам в условиях стационарного состояния системы (т. е. вместо момента tn рассматривается произвольный момент окончания обслуживания в стационарном состоянии системы), а величины и определяются аналогично и с заменой величин на величины Пусть r < 1. Тогда при любых допустимых существуют приведенные ниже пределы и выполняются равенства (4) При этом справедливы соотношения: (5) Таким образом, основным результатом работы является соотношение (3). Соотношение (5) получается из (3) на основе предельного перехода при n → ∞. Вывод результатов Докажем соотношение (3). При получении соотношений используется метод введения дополнительных событий [4]. Введем в рассмотрение следующие функции: -переходные вероятности: есть вероятность того, что в момент окончания обслуживания на j-м приборе на другом приборе остаточное обслуживание меньше x, в предыдущий момент начала обслуживания вызов поступил для обслуживания на l-й прибор, а другой прибор был в этот момент занят, за время между этими окончаниями обслуживания не было η-катастроф; при условии, что при предыдущем окончании обслуживания величина оставшегося обслуживания на приборе, отличном от l-го, равна t и в системе есть вызовы. Получим соотношения для . Ниже, чтобы облегчить понимание, возможные ситуации будут отображаться с помощью диаграммы, где точка «·» будет обозначать момент окончания или начала обслуживания. Если j = l и v - промежуток времени между последовательными моментами окончания обслуживания (время перехода), то длительность оставшегося обслуживания равна что по условию меньше x (рис. 1, а). При этом может изменяться от 0 до τ. j-ый прибор Рис. 1. Диаграмма состояний: а - для случая j = l; б - для случая Просуммировав по возможным значениям , имеющим функцию распределения Bj(t), получаем соотношение (6) Пусть . Тогда время перехода равно t (рис. 1, б); и если ξ - время обслуживания вызова, поступившего на l-й прибор для обслуживания в предыдущий момент окончания обслуживания, то и остаточное обслуживание . Так как вероятность того, что за время перехода не наступает η-катастроф, равна , то получаем Предположим, что есть рациональная функция. Тогда все особые точки лежат в области . Из разложения на простые дроби вида где b > 0, следует, что соответствующее слагаемое в плотности равно , где x > 0, и, следовательно, функция распределения Bj(t) с плотностью распределения имеет экспоненциальный порядок убывания на бесконечности. Тогда имеет при порядок не ниже 1/x, поэтому (j = 1, 2): при достаточно больших . Из формулы обращения для характеристических функций [5] имеем (в силу последней оценки, интеграл сходится абсолютно): (7) где - контур, изображенный на рис. 2. Рис. 2. Контур интегрирования Получим уравнения для функции (μ > 0): где есть вероятность того, что первая µ-катастрофа произойдет после n-го по порядку момента окончания обслуживания и произойдут события, сформированные в определении Пусть n ≥ 1. Рассмотрим возможные состояния системы в момент окончания обслуживания, предшествующий моменту (рис. 3). Рис. 3. Диаграмма вариантов для случая n ≥ 1: а - система свободна; б - система занята и m = j; в - система занята и m = В n-й момент окончания обслуживания tn (рис. 3, а) в системе было по крайней мере 2 вызова (не считая обслуженного) и не было z-синих вызовов; в момент tn обслуживание закончилось на m-м приборе (1 ≤ m ≤ 2); с начала периода занятости, содержащего моменты tn+1 и tn, не было s-катастроф, с момента t = 0 не было µ-катастроф, в момент время дообслуживания на -м приборе лежит в интервале Вероятность этого события равна где Далее произошел переход в состояние, описывающее вероятность и за время перехода не было z-синих вызовов, s- и µ-катастроф, т. е. η-катастроф; вероятность указанного перехода равна . Кроме того, необходимо снять «окраску» с обслуженного вызова (т. е. разделить на z). Таким образом, вероятность осуществления события, описывающего в исходя из состояния на рис. 3, а, равна В момент tn обслуживание закончилось на m-м приборе (рис. 3, б). В системе остался один вызов (z-красный), с начала периода занятости, содержащего , не было s-катастроф, с момента t = 0 не было µ-катастроф, а время дообслуживания на -м приборе в момент tn лежит в интервале Вероятность этого события равна Далее в некоторый момент времени u < τ поступил вызов (z-красный), который будет обслуживаться m-м прибором, а за время u не было (s + μ)-катастроф (в этот момент время дообслуживания на -м приборе равно (τ - u), затем произошел переход, описываемый вероятностью за время перехода не было z-синих вызовов, s- и μ-катастроф (η-катастроф). Вероятность этого события равна: Таким образом, вероятность перехода из состояния на рис. 3, б в состояние, описываемое вероятностью , равна где снята «окраска» с обслуженного вызова (т. е. результат разделили на z). В некоторый момент система свободна, и до этого, c момента t = 0, не было µ-катастроф (вероятность z-красный вызов поступает раньше µ-катастрофы (вероятность для обслуживания выбирается-й прибор (вероятность длительность его обслуживания лежит в интервале (вероятность а дальше происходят события, представленные на рис. 3, в. Вероятность этого события равна Поскольку нет других состояний в момент t = 0, приводящих к состоянию, описываемому вероятностью , то, объединяя все три случая и просуммировав по m и l, получим (8) где есть вероятность того, что в момент система свободна и до этого момента не было µ-катастроф. Пусть теперь n = 0, т. е. рассматривается маргинальное состояние СМО. Тогда, как и в случе n ≥ 1 (рис. 3), рассматриваются три аналогичных случая. В момент t = 0 в системе есть по крайней мере 2 вызова, которые красные, время дообслуживания на -м приборе равно ; вероятность этого события равна Далее произошел переход в состояние, описываемое вероятностью и вероятность этого перехода равна Отсюда следует, что вероятность попадания в состояние, описываемое вероятностью на рис. 3, а, равна где деление на z вызвано снятием «окраски» с обслуженного вызова. Поскольку при этом один и тот же переход учитывается дважды - с и то результат умножаем на 1/2. В момент t = 0 в системе один вызов (красный), этот вызов обслуживается на -м приборе (с вероятностью и время его обслуживания равно τ. Далее произошли события, аналогичные событиям на рис. 3, б для момента tn при n ≥ 1. Получаем вероятность попадания в состояние, описываемое вероятностью на рис. 3, б, которая равна Данный случай аналогичен случаю на рис. 3, в при n ≥ 1. Получаем, что требуемая вероятность равна Объединяя все три случая, получаем (9) Преобразуем соотношения (8) и ( 9). Пусть в начале n ≥ 1. Из (7), в силу (8), выводим : (10) Далее, из (6) и (7) следует: Так как то (11) Подсчитаем преобразование Лапласа - Стильтьеса (ПЛС) по x каждого слагаемого правой части. Имеем (l > 0): (12) где перестановка знаков интеграла и дифференциала по x законна, т. к. и является функцией распределения по и x. После интегрирования по частям имеем: Далее, поскольку то аналогично выводу (11) получаем Проинтегрировав по частям, получаем : Следовательно, ввиду (12) : (13) Подынтегральная функция в правой части (13) аналогична для любых и и в окрестности любой точки интервал в правой части (13) сходится равномерно. Отсюда следует, что правая часть аналитична при В силу аналитичности левой части при заключаем, что (13) имеет место для любых Аналогично находится ПЛС остальных слагаемых в правой части (8). Далее, из (10) получаем: (14) При из (11) получаем (15) Наконец, соотношения, аналогичные (6) и (15), выписываются и в случае замены на именно, при (т. е. (16) При m ≠ j (т. е. (17) Из (8) и (13)-(17) следует соотношение (18) С учетом введенных обозначений (2) последнее соотношение можно переписать в виде : (19) Пусть . Тогда в области имеет единственную особую точку являющимся простым полюсом, и, значит, (20) что позволяет переписать (19) в виде (21) Далее, при функции аналитичны в области откуда следует (22) Из (21), (22) получаем (23) Поскольку в полосе функция аналитична, то (24) где, и, следовательно, у интеграла в правой части (в отличие от интеграла в левой части) при действительной прямой точки обходится снизу. Действительно, после замены получаем Рассмотрим контур (рис. 4) где и точка обходится снизу}, и точка обходится сверху}, с направлением обхода по часовой стрелке. Рис. 4. Контур интегрирования Функция аналитична в области, ограниченной контуром γ, и, следовательно, (25) Так как при имеем то, по теореме Жордана, Отсюда получаем что влечет соотношение (25). Аналогично (26) где при обходе действительной прямой в интеграле правой части точка обходится снизу. Из (23) на основе (24) и (26) получаем (j = 1, 2) (27) Сравнивая соотношения (27) при j = 1 и j = 2, заключаем (28) В силу аналитичности по обеих частей, (28) справедливо для всех l, . Нетрудно доказать, что верно и обратное, т. е. из (28) следует (27). Пусть n = 1. Тогда аналогично из (13)-(15) выводим: (29) и (30) Из (9), на основе (29) и (30), аналогично выводу (18), получаем Используя обозначения (1), перепишем (28) в виде (19) с n = 0, откуда выводим справедливость (28) при n = 0. Соотношение (28), ввиду аналитичности левой и правой частей по l для , справедливо для l, . Заменяя в (28) l на , приходим к (4). Соотношение (3) доказано. Заключение В ходе исследования получены соотношения, связывающие базовые характеристики двухканальной СМО с пуассоновским входящими потоками и с произвольными распределениями длительности обслуживания вызовов с маргинальными значениями этих характеристик - как для нестационарного случая, так и для стационарного. Полученные соотношения могут быть использованы для построения процедур имитационного моделирования двухканальных систем, позволяющих ускорить процесс выполнения каждой итерации при моделировании и тем самым повысить точность конечного результата.
1. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979. 432 с.
2. Кокс Д. Р., Смит У. Л. Теория очередей. М.: Мир, 1966. 218 с.
3. Саати Т. Л. Элементы теории массового обслуживания и её приложения. М.: Сов. радио, 1966. 511 с.
4. Гнеденко Б. В., Даниелян Э. А., Димитров Б. Н., Климов Г. П., Матвеев В. Ф. Приоритетные системы обслуживания. М.: Изд-во Моск. ун-та, 1973. 448 с.
5. Феллер В. Введение в теорию вероятностей и ее приложения. Т. 2. М.: Мир, 1966. 752 с.
