COMMUNICATION OF COMMON AND MARGINAL CHARACTERISTICS OF CONDITIONS IN A TWO-CHANNEL SYSTEM WITH SIMPLE STREAMLINES OF APPLICATIONS
Journal: VESTNIK OF ASTRAKHAN STATE TECHNICAL UNIVERSITY. SERIES: MANAGEMENT, COMPUTER SCIENCE AND INFORMATICS
Volume 2017 № 3
, 2017
Rubrics: MATHEMATICAL MODELING
Authors:
1.
Astrakhan Technical State University
Type:
Article
Pages:
from 7
to 19
Status:
Published
Received:
05.07.2017
Accepted:
28.02.2020
Published:
25.07.2017
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 007:681.518.2
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 007:681.518.2
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
queuing system, two devices, Poisson incoming flow, queue length, marginal characteristics, recurrence relations
Abstract (English):
The article deals with a two-channel queuing system with a Poisson incoming call flow, in which the application processing time on each of the devices is different. Such models are used, in particular, when describing the operation of the system for selecting service requests in a number of operating systems. A complex system characteristic was introduced at the time of service endings on at least one of the devices, including the queue length, the remaining service time on the occupied device, and the time since the beginning of the current period of employment. This characteristic determines the state of the system at any time. Recurrence relations are obtained that connect this characteristic with its marginal values when there is no queue in the system. The method of introducing additional events was chosen as one of the main methods for analyzing the model. The relationships presented in this article can be used for analysis of the average characteristics of this system, as well as in the process of its simulation. Summarizing the results of work on multichannel systems with an arbitrary number of servicing devices will significantly reduce the time required for simulating complex systems described by sets of multichannel queuing systems.
The article deals with a two-channel queuing system with a Poisson incoming call flow, in which the application processing time on each of the devices is different. Such models are used, in particular, when describing the operation of the system for selecting service requests in a number of operating systems. A complex system characteristic was introduced at the time of service endings on at least one of the devices, including the queue length, the remaining service time on the occupied device, and the time since the beginning of the current period of employment. This characteristic determines the state of the system at any time. Recurrence relations are obtained that connect this characteristic with its marginal values when there is no queue in the system. The method of introducing additional events was chosen as one of the main methods for analyzing the model. The relationships presented in this article can be used for analysis of the average characteristics of this system, as well as in the process of its simulation. Summarizing the results of work on multichannel systems with an arbitrary number of servicing devices will significantly reduce the time required for simulating complex systems described by sets of multichannel queuing systems.
Keywords:
queuing system, two devices, Poisson incoming flow, queue length, marginal characteristics, recurrence relations
queuing system, two devices, Poisson incoming flow, queue length, marginal characteristics, recurrence relations
Введение Многоканальные системы массового обслуживания (СМО) в самом общем случае представляют собой математические модели, включающие три компонента: поступающие потоки заявок, которые приносят в систему определенную работу; процесс обслуживания заявок с помощью обслуживающих приборов, которые и выполняют работу, принесенную заявками; дисциплину обслуживания при определении порядка выбора заявок на обслуживание в случае возникновения конкурентной ситуации, когда несколько заявок пытаются одновременно получить возможность для обслуживания. Подобными моделями описываются очень многие реальные системы в самых разных сферах [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. Kleynrok L. Teoriya massovogo obsluzhivaniya. M.: Mashinostroenie, 1979. 432 s.
2. Koks D. R., Smit U. L. Teoriya ocheredey. M.: Mir, 1966. 218 s.
3. Saati T. L. Elementy teorii massovogo obsluzhivaniya i ee prilozheniya. M.: Sov. radio, 1966. 511 s.
4. Gnedenko B. V., Danielyan E. A., Dimitrov B. N., Klimov G. P., Matveev V. F. Prioritetnye sistemy obsluzhivaniya. M.: Izd-vo Mosk. un-ta, 1973. 448 s.
5. Feller V. Vvedenie v teoriyu veroyatnostey i ee prilozheniya. T. 2. M.: Mir, 1966. 752 s.
