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

Ключевые слова:
система массового обслуживания, два прибора, пуассоновский входящий поток, длина очереди, маргинальные характеристики, рекуррентные соотношения
Текст
Введение Многоканальные системы массового обслуживания (СМО) в самом общем случае представляют собой математические модели, включающие три компонента: поступающие потоки заявок, которые приносят в систему определенную работу; процесс обслуживания заявок с помощью обслуживающих приборов, которые и выполняют работу, принесенную заявками; дисциплину обслуживания при определении порядка выбора заявок на обслуживание в случае возникновения конкурентной ситуации, когда несколько заявок пытаются одновременно получить возможность для обслуживания. Подобными моделями описываются очень многие реальные системы в самых разных сферах [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 с.