«МАССОВОГО ОБСЛУЖИВАНИЯ СИСТЕМА»

понятие, к-рое включает в себя случайный "входящий" поток требований (вызовов, клиентов), нуждающихся в "обслуживании", и механизм (алгоритм), осуществляющий это "обслуживание".

Типичным примером М. о. с. являются автоматич. телефонные станции, на к-рые случайным образом поступают требования - вызовы абонентов (входящий поток вызовов), а механизм обслуживания состоит из фиксированного числа n каналов (линий) связи, каждый из к-рых остается занятым под обслуживание очередного вызова случайное время, равное длительности разговора. Если все пканалов заняты, то вызов получает "отказ". Механизм (алгоритм) обслуживания может включать в себя также указания, на какую из свободных линий следует направлять очередной вызов, предложение ждать, если требуемый абонент занят, и др.

Существуют и системы другого типа, когда каждое требование непременно должно быть обслужено, как ато имеет место, напр., в потоке самолетов, прибывающих в аэропорт для посадки, пли в потоке задач (программ), к-рые должны быть реализованы на электронно-вычислительной машине. "Случайную" часть М. о. с. удобно описывать с помощью случайных последовательностей или процессов. Наиболее простые М. о. с. можно описывать двумерными управляющими случайными последовательностями

неотрицательных случайных величин. Последовательность определяет поток вызовов е:она указывает случайные моменты времени

в к-рые в систему поступают требования, подлежащие обслуживанию. Эквивалентным образом входной поток можно характеризовать случайным процессом значение е(t).указывает число вызовов, поступивших в систему к моменту времени t. Вторая последовательность описывает процесс обслуживания s: случайная величина означает время, к-рое тратится на обслуживание вызова с номером j. Обслуженные вызовы выбывают из рассмотрения.

Весьма распространено описание управляющих последовательностей с помощью маркированных точечных процессов, в к-рых представляют собой интервалы между точками, а - марки этих точек.

Задание управляющей последовательности не определяет однозначно поведение системы. Необходимо задать "еще алгоритм обслуживания - правило, которое определяет моменты начала обслуживания и поведение вызовов в зависимости от состояния системы.

Многообразие алгоритмов обслуживания порождает чрезвычайно много различных видов систем обслуживания. Ниже приведена классификация простейших из них.

I. Системы с ожиданием (или системы с очередь ю). Вызовы, поступившие в систему и не принятые немедленно к обслуживанию, накапливаются, образуя "очередь", ожидающую обслуживания. В дальнейшем вызовы обслуживаются в порядке поступления. Система занята в момент времени t, если в этот момент есть очередь или происходит обслуживание очередного вызова. В противном случае система наз. свободной в момент времени t. Различают два типа систем с очередью.

I₁. Обычные системы. Если система свободна, то она начинает действовать (обслуживать очередной вызов) немедленно при поступлении вызова. Если система занята, то обслуживание очередного вызова начинается после окончания обслуживания предыдущего. Такие системы наз. также п о л н о д о с т у п н ы м и.

I₂. Системы с автономным обслуживанием. Здесь обслуживание начинается только в моменты времени

II. Системы с ограниченной очередью. Считают, что длина q(t).очереди в момент tравна если один вызов в этот момент находится на обслуживании и п -1 вызовов ждут обслуживания. Пусть длина очереди в момент прихода n-го вызова (без учета этого вызова). В системах с ограниченной очередью вызов с номером п"получает отказ" и выбывает из рассмотрения, если в момент его прихода длина q _п очереди оказывается равной максимальному допустимому значению Число Nявляется существенной характеристикой системы. Если то получаются обычные системы с неограниченной очередью.

Рассматривают также системы со случайной ограниченной очередью и системы со случайным ограниченным временем ожидания.

III. Системы с ограниченной очередью в случае N=1 наз. системами с отказами. Для систем с отказами автономное обслуживание обычно не рассматривается.

В каждом из рассмотренных простейших видов систем задание управляющей последовательности полностью определяет эволюцию системы. Другими словами, для каждого элементарного события w и любого tоднозначно определено состояние системы к моменту времени t.

Помимо перечисленных выше типов систем обслуживания, возможны и другие, более сложные системы. Они связаны с более сложными управляющими последовательностями и алгоритмами обслуживания.

IV. Групповой входной поток и групповое обслуживание. Управление такими системами может происходить с помощью четырехмерных управляющих последовательностей

где - неотрицательны и целочисленны. Смысл новых переменных следующий: вызовы поступают группами объемов (соответственно в моменты времени ); обслуживание также происходит группами: в первой партии обслуживается вызовов, во второй вызовов и т. д. (объемы этих групп могут быть и меньше, если в очереди не окажется достаточного количества вызовов). При этом на обслуживание k- йпартии тратится время

Для систем с групповым входом и обслуживанием возможны те же алгоритмы обслуживания, к-рые были описаны выше.

V. Многоканальные системы. В таких системах обслуживание может вестись одновременно в каналах, так что обслуживание очередного вызова (или партии вызовов при групповом обслуживании) может начаться прежде, чем закончится обслуживание предыдущей. Алгоритмы обслуживания многоканальных систем выглядят аналогично для всех рассмотренных типов обслуживания (каждый канал действует как самостоятельное обслуживающее устройство). Надо лишь дополнить эти алгоритмы указаниями, в какой канал должны направляться вызовы, если свободными оказались одновременно несколько каналов. При этом по-прежнему на обслуживание i-й партии (объема ) тратится время

Многоканальная система наз. системой с отказами, если вызовы, в момент прихода к-рых все каналы оказались занятыми, получают отказ и выбывают из рассмотрения.

Иногда для того чтобы упростить природу управляющих последовательностей для многоканальных систем, удобно задавать не две, a m+1 управляющих двумерных последовательностей

так что k- йканал обслуживания управляется последовательностью Напр., есть время обслуживания партии вызовов, к-рая является i-й в k- мканале.

Приведенная классификация охватывает далеко не все виды систем обслуживания. Широкое распространение имеют, напр., системы, у к-рых вызовы подразделяются на два или более типов и одни типы имеют приоритет в обслуживании перед другими (такая ситуация возникает, когда стоимость простоя одних вызовов выше, чем у других). Характеризация таких систем требует введения в рассмотрение нескольких входящих потоков вызовов - по числу типов требований. К системам с приоритетным обслуживанием можно отнести также системы, у к-рых обслуживающее устройство требует перерывов в работе. Закон появления и длительности перерывов можно характеризовать специальным входным потоком.

В литературе по массового обслуживания теории рассмотрены и др. специальные виды систем обслуживания. Однако при этом следует иметь в виду, что:

1) основные и наиболее распространенные типы М. о. с. находятся в рамках приведенной выше классификации;

2) методы исследования М. о. с. для различных систем, как правило, отличаются мало и в достаточной степени иллюстрируются методами изучения "основных" систем; в основе этих методов лежит аппарат теории вероятностей, как общие его разделы, так и специально разработанные.

Основной целью изучения является исследование распределений различных параметров, характеризующих состояние системы (напр., длины очереди, времени ожидания начала обслуживания, вероятности данному вызову получить отказ и т. д.). Главный интерес при этом представляют эргодич. теоремы, описывающие поведение указанных характеристик через большой промежуток времени. Напр., одной из характеристик эффективности работы автоматической телефонной станции является доля вызовов, получивших отказ, т. е. предел рпри (если он существует) отношения r(t)/e(t).числа r(t).вызовов, потерянных за время t, к общему числу e(t).вызовов, поступивших за это время. Этот предел можно с достаточными на то основаниями называть вероятностью отказа. Показателями, характеризующими системы с ожиданием, являются предельные при распределения вероятностей для времени w_n, к-рое n-й вызов ожидал начала обслуживания с момента прихода, и для длины q _п очереди в момент появления в системе n-го вызова.

Метод исследования часто состоит в отыскании марковских процессов или последовательностей, характеризующих состояние системы. Если, напр., случайные величины и показательно распределены и при разных индексах независимы, то "процесс очереди" q(t).будет марковским и допускает описание с помощью простых дифференциальных уравнений для стационарного распределения. В других случаях обычно пытаются построить случайные моменты времени t₁, t₂,... такие, что q(t_n).или значения других характеристик (напр., времени ожидания), взятые в моменты t₁, t₂,..., образовывали бы цепь Маркова. Это т. н. метод вложенной цепи Маркова. Этот метод часто используется в модифицированном виде, когда строятся полумарковские процессы, описывающие интересующие нас состояния системы.

В более сложных случаях приходится использовать асимптотич. методы (см. Массового обслуживания теория).или прибегать к моделированию случайных процессов, описывающих поведение М. о. с., по Монте-Карло методу.

В статьях Массового обслуживания система с ожиданием и одним каналом обслуживания, Массового обслуживания система с ожиданием многоканальная, Массового обслуживания система с отказами, Массового обслуживания система (входящий поток вызовов) более подробно рассматриваются основные виды систем обслуживания и входные потоки. В этих статьях приняты следующие обозначения.

Е - класс последовательностей независимых случайных величин с показательным распределением. Запись означает, что

Запись означает, что случайные величины независимы и одинаково распределены (само распределение может быть произвольным). Соотношения вида или обычно предполагают также, что управляющая последовательность не зависит от остальных управляющих последовательностей.

Класс стационарных в узком смысле последовательностей обозначен G_S.

Приведенные обозначения могут применяться и к многомерным последовательностям. Напр., означает, что двумерная последовательность стационарна и составлена из независимых векторов.

Для простоты изложения, как правило, ограничиваются рассмотрением "ординарных" входных и выходных процессов, когда (вызовы поступают и обслуживаются по одному). Возможности обобщений на "неординарный" случай (вызовы поступают и обслуживаются группами: или ) оговаривают отдельно.

Кроме того, природа управляющих последовательностей будет простой и однородной, если выделять из них начальные условия. Именно, рассматривают управляющие последовательности при и считают, что q(0)=0, а первый вызов пришел в систему в момент Если управление задается входным процессом e(t), то фиксация не производится.

Лит. см. при СТ. Массового обслуживания теория.

А. А. Боровков.

с отказами - система массового обслуживания, алгоритм к-рой предусматривает выбывание вызовов, в момент прихода к-рых все каналы оказались занятыми. Основные определения и обозначения см. в ст. Массового обслуживания система.

1) Естественными характеристиками состояния М. о. с. с отказами являются число q_n (или q(t)).занятых линий в момент прихода п-го вызова (в момент времени t). Однако, в отличие от систем с бесконечным числом каналов обслуживания, здесь всегда где т - число каналов в системе. Если в момент прихода n-го вызова оказывается q _п=т, то этот вызов получает отказ и выбывает из рассмотрения. Если же q _п<m, то вызов направляется на обслуживание в один из свободных каналов.

Предположив, что управляющая последовательность метрически транзитивна, можно сформулировать эргодич. теорему для систем с отказами, используя систему с бесконечным числом каналов обслуживания, управляемую той же последовательностью. Для такой системы существует собственная стационарная последовательность {Q^k} длины очереди. Величину Q⁰ можно представлять как число занятых линий стационарной системы в момент прихода нек-рого вызова. Обозначив условно номер этого вызова через g, определяют как число линий, занятых вызовами, пришедшими до вызова g₀, в момент прихода вызова с номером g+l, так что Тогда если вероятность события

положительна, то распределения последовательностей длин очереди для систем с отказами будут сходиться при к распределению нек-рой стационарной последовательности . Смысл события Авесьма прост: оно состоит в "обновлении" системы: после него в системе будут находиться лишь вызовы с номерами уи выше.

Приведенная теорема есть частный случай более общего утверждения, использующего т. н. метод обновлений. Если то для выполнения сформулированных условий достаточно, чтобы

Утверждение, аналогичное сформулированному выше, будет иметь место и относительно сходимости при процессов к стационарному процессу длины очереди. При этом помимо приведенных условий дополнительно требуется, чтобы входной процесс е(t).(число поступивших вызовов к моменту времени t).был процессом со стационарными приращениями.

2) Если то справедливы формулы Э р л а н г а

где

a - показатель распределения

Если то последовательность q _п связана в простую однородную цепь Маркова с конечным числом (m+1) состояний. В этом случае вероятности

также можно найти в явном виде. Если, кроме того, распределение нерешетчато и то

где a - показатель распределения

Эти утверждения указывают условия существования и явный вид для стационарной вероятности отказа, равной

3) Теоремы устойчивости для систем с отказами вполне аналогичны теоремам устойчивости для систем с бесконечным числом каналов. Пусть даны последовательности управляющие системами с отказами и удовлетворяющие следующему условию:

(А) существует последовательность к распределениям к-рой сходятся при конечномерные распределения Кроме того, все названные последовательности удовлетворяют условиям (см., напр., п. 1), обеспечивающим существование стационарных последовательностей длины очереди. Чтобы имела место сходимость распределений этих стационарных последовательностей длины очереди, к-рые обозначены следует ввести еще два условия:

(В)

(С).распределения

при всех непрерывны в точке 0.

При выполнении условий (А), (В), (С) конечномерные распределения последовательности слабо сходятся к распределениям

4) Асимптотич. методы исследования систем с отказами могут быть эффективными также при изучении систем с интенсивным входным потоком или с большим числом каналов обслуживания.

Исследование систем с интенсивным входом связано с получением результатов в предположениях, близких к тем, к-рые рассматриваются при асимптотич. анализе систем с бесконечным числом каналов обслуживания. Изучение систем с большим числом каналов проводится как путем асимптотич. анализа явных формул, к-рые становятся малоэффективными при больших m, так и с помощью изучения близости распределения q^k к распределению числа занятых линий в аналогичной системе, но с бесконечным числом каналов обслуживания.

Напр., для систем с последовательностями стационарная вероятность отказа равна

где

a - показатель распределения Эти соотношения при больших тстановятся малопригодными для отыскания числовых значений р _т. В то же время оказывается, что при действуют достаточно простые формулы, к-рые устанавливают асимптотич. поведение р _т и к-рые, следовательно, можно использовать для приближенных вычислений вероятности отказа. При этом определяющую роль играет параметр характеризующий отношение среднего числа вызовов, поступивших в систему, к среднему числу вызовов к-рое может обслужить система за единицу времени. Если r<1, то система обычно полностью загружена, если r>1, то система недогружена. Если r<1-e при и нек-ром e>0, то Если при то приведенное соотношение для р _т сохраняется и при если только Если же то р _т ведет себя асимптотически как где постоянная bнайдена в явном виде. Найдено также асимптотич. поведение р _т и в случае

5) Несколько более полно могут быть изучены одно-канальные системы с отказами (когда m=1). Пусть, напр., Случайную величину h) определяют равенством

где Тогда, для того чтобы при любом начальном условии существовал предел

необходимо и достаточно, чтобы наибольший общий делитель возможных значений h равнялся 1. При этом Если t ^е нерешетчата, то всегда существует

При более широком понимании вероятности отказа как предела отношения p=r_n/n, где r_n - число необслуженных вызовов среди первых n поступивших, условия существования lim p_n будут более широкими. Напр., для случая предел p_n существует всегда и равен

Лит. см. при ст. Массового обслуживания теория.

А. А. Боровков.

входящий поток вызовов - случайный процесс, заданный тем или иным образом и описывающий поступление вызовов в систему обслуживания. Входящий поток определяется обычно случайной последовательностью где указывают интервалы между поступлениями в систему групп требований объемов соответственно Если то поток наз. ординарным. Эквивалентным образом входящий поток можно задавать с помощью точечного процесса или процесса {e(t); }, указывающего количество вызовов, поступивших в систему к моменту времени t. Можно считать для определенности, что e(t)=e(t-0).

Наиболее распространенное требование, к-рое обычно предъявляется к входному потоку, состоит в его стационарности. Это условие может быть двояким: либо требуется стационарность в узком смысле последовательности (обозначается либо требуется, чтобы процесс e(t).был процессом со стационарными в узком смысле приращениями (обозначается Эти два требования, вообще говоря, не совпадают.

Интенсивностью стационарного потока наз. число

Если

то

так что m равно среднему числу вызовов, поступивших в систему за единицу времени. Если последовательность стационарна и эргодична и то

В остальных случаях связь m с распределением последовательности может быть более сложной. Пусть дан процесс с интенсивностью m и с начальным значением е(0)=0. С числом m тесно-связан другой параметр входного потока, определяемый равенством

Этот предел всегда существует и Если

то тогда и только тогда, когда входной поток ординарен.

При изучении свойств входного потока часто используются т. н. функции Пальма

(здесь е(0)=0), к-рые имеют смысл условных вероятностей того, что на интервале (0, t).появится kвызовов при условии, что в момент времени 0 пришел вызов. С распределением е(t).функции j_k (t).связаны равенствами

Если

то

Значительную роль в теории массового обслуживания играют т. н. простейшие, или пуассоновские, входные потоки - стационарные входные потоки, для к-рых Чтобы определить простейший поток в терминах процесса e(t), требуют, чтобы процесс {e(t)}был пуассоновским. Приращения этого процесса на непересекающихся интервалах времени независимы и имеют распределение-Пуассона с параметрами, пропорциональными длинам интервалов.

Находят широкое применение (особенно в телефонии) также и неоднородные пуассоновские потоки, к-рые характеризуются процессами е(t).с независимыми приращениями, распределенными по закону Пуассона

где A(t) - ведущая функция процесса (в однородном случае ).

Особая роль пуассоновских процессов в теории массового обслуживания во многом объясняется основной предельной теоремой для входящих потоков, к-рая устанавливает, что в широких предположениях сумма большого числа произвольных независимых стационарных входных потоков малой интенсивности сходится к пуассоновскому процессу. Частое использование предположения о том, что входной поток пуассоновский, обусловливается тем, что во многих приложениях реальные входные потоки образуются именно таким способом (напр., поток вызовов, поступающих на телефонную станцию, представляет собой сумму слабых потоков, исходящих от отдельных абонентов).

Ниже приведена основная предельная теорема в двух формах. Первая относится к суммам произвольных (нестационарных) входных потоков.

Пусть даны возрастающие вместе с псовокупности независимых процессов зависящих от параметра n (т. е. рассматривается схема серий), п введены следующие обозначения

Пусть, кроме того, при любом фиксированном t>0 выполнено условие

при равномерно по т(это и есть условие малой интенсивности потоков ). Тогда, для того чтобы конечномерные распределения процесса

сходились к распределениям пуассоновского процесса с ведущей функцией A.(t), необходимо и достаточно, чтобы при

Если в рассматриваемой схеме серий, процессы и ординарны, то имеет место также следующее утверждение. Пусть - интенсивность и при

Тогда для сходимости конечномерных распределений процессов е _п(t).к распределениям пуассоновского процесса е(t).с параметром aнеобходимо и достаточно, чтобы при каждом t

где - функция Пальма для процесса определенная равенством (1). Если при

равномерно по г, то условие (2) очевидно будет выполнено.

Лит. см. при ст.. Массового обслуживания теория.

А. А. Боровков.

с ожиданнем и одним каналом обслуживания - система массового обслуживания, алгоритм к-рой предусматривает, что вызовы, не принятые немедленно к обслуживанию (заставшие систему занятой), накапливаются в очереди; при этом обслуживание следующего вызова (или партии вызовов) может начаться лишь после того, как окончится обслуживание предыдущего (или предыдущей партии, если вызовы обслуживаются группами). Основные определения и обозначения см. в ст. Массового обслуживания система.

Наиболее естественными характеристиками состояния систем с очередью являются следующие: а) время w_n ожидания начала обслуживания требования с номером пи виртуальное время w(t).ожидания, к-рое определяется как время, необходимое для освобождения системы от вызовов, пришедших до момента времени t; б) длина q _п очереди в момент прихода n-го вызова и длина q(t).очереди в момент времени t.

1) В "ординарном" случае значения w_n связаны рекуррентным соотношением

Такого же типа уравнениями (для времени ожидания или для длины очереди) могут описываться системы с ожиданием и в "неординарном" случае, когда отличны от единицы. Напр., для длины q_n очереди справедливы соотношения

где b_n - число вызовов, к-рое может быть обслужено за время при бесперебойной работе системы. Если то распределение b_n можно найти из соотношений

где а - показатель распределения

Если обозначить то решение уравнения (1) имеет вид

Отсюда следует, что если

при любом фиксированном интервале и то существует предельное распределение времени ожидания:

где

Здесь величины - элементы последовательности являющейся расширением до последовательности, стационарной на всей оси. В дальнейшем будет предполагаться что такое расширение произведено над всеми управляющими последовательностями. Значения

удовлетворяют уравнению (1) и имеют распределение, совпадающее с предельным распределением w_n. Это - стационарный процесс времени ожидания.

Пусть последовательность и эргодична ( с вероятностью 1). Тогда

Если то тогда и только тогда, когда (тривиальный случай исключается).

2) Как уже отмечалось, другой возможной характеристикой состояния системы является виртуальное время w(t).ожидания. Грубо говоря, это - время, к-рое прождал бы начала своего обслуживания вызов, пришедший в момент t. Пусть S(t) есть сумма времен обслуживания вызовов, поступивших в систему до момента времени t, X(t)=S(t)-t. Аналогом равенства (3) здесь является соотношение

Пусть G_IS- класс процессов со стационарными в узком смысле приращениями и G_II - класс процессов с независимыми приращениями (G_II и G_IS здесь можно понимать и более узко; напр., можно считать, что G_II - класс обобщенных пуассоновских процессов с положительными скачками и сносом -1). Если процесс то он может быть расширен до процесса заданного на всей оси и также принадлежащего G_IS В этом случае существует

где

Если, кроме того,

то распределение процесса

сходится при

к распределению процесса

к-рый является собственным стационарным процессом виртуального времени ожидания. Сходимость здесь имеет место в сильной форме:

для любого измеримого В.

Далее, если и а<0, то существует условная функция восстановления Н ₀ (х).процесса X(t).

при этом

Приведенные формулы сохраняются и в случае

Для систем, у к-рых существуют простые связи между распределениями w^k и w^s(t).3) Эргодические теоремы для длины очереди могут быть получены с помощью соответствующих теорем для времени ожидания. Пусть, напр., последовательность эргодична (метрически транзи-тивна).' Если, кроме того, то существует предельное (стационарное) распределение q_n такое, что

Если же

и распределение

нерешетчато, то существует

где все компоненты под знаком вероятности в правой части независимы, g имеет плотность, равную

Если

то предельные распределения q_n и q(t).совпадают.

4) Если

(допускается также, что

то можно получить точные формулы и для допредельного распределения w(t).

При a<0 и имеет место формула X и н ч и н а для стационарного распределения:

где q - величина скачка процесса X(t)(если

), a - показатель распределения Пусть T_j,;=1, 2,...,- п е р и о д ы занятости системы (т. е. длины интервалов времени в течение к-рых w(t)>0). Тогда для рассматриваемых систем

5) Для систем, у к-рых

(допускается, также

распределение w^k совпадает с распределением величины

По известному распределению x_j распределение Yможет быть найдено следующим образом. Если (это всегда при ), то справедливо следующее факторизационное тождество

где - величина первой неположительной суммы среди x₁, x₁+x₂,... Это соотношение позволяет отождествить с отношение в любом тождестве

в к-ром функции

допускают представление

( - функции ограниченной вариации). Равенство (5).осуществляет т. н. V-факторизацию функции Оно позволяет указать следующие случаи, когда возможно отыскание в явном виде.

Предполагают, что и обозначают

так что

А) Если -рациональная функция: где Р _т к Q_n- многочлены степеней ти n соответст-

венно, то функция (1-f)Q_n в области Iml<0 имеет ровно пнулей l₁,..., l_n и

Это означает, что если распределение t^s представимо в виде

где Р _k (х) - многочлены, то такого же вида представление (при других a_k и Р _k, определяемых нулями l₁,..., l_n) будет иметь место и для

В) Если - рациональная функция, то функция (i-f)Q_n в области Iml>0 имеет n-1 нулей l₁,..., l_n-1 и

Кроме этих формул, дающих явное выражение для распределения У, можно также в широком классе случаев описать асимптотич. поведение при Именно, если

и то определен единственный корень q>0 уравнения В этом случае при

Если же

то

Постоянные с ₁ и с ₂ найдены в явном виде.

Результаты, аналогичные изложенным в пп. 2) - 5), справедливы и для систем с дискретным временем, когда время tи случайные величины управляющих последовательностей принимают лишь целочисленные значения.

6) Теоремы устойчивости выясняют условия, при к-рых малое изменение конечномерных распределений управляющих последовательностей влечет за собой малое изменение стационарного распределения времени ожидания или длины очереди. Важность вопроса об устойчивости систем обслуживания объясняется тем, что обычно в реальных задачах пользуются теми или иными предположениями о природе управляющей последовательности (напр., предполагается, что x_j независимы или что t^e_j распределены по показательному закону), в то время как на самом деле эти предположения выполняются лишь приближенно. Спрашивается, будет ли решение таких "идеализированных" задач близко к решению истинной задачи.

Чтобы получить точную постановку проблемы рассматривают схему серий, когда уравнением (1) управляют стационарные последовательности (серия последовательностей)

Кроме того, рассматривают стационарную последовательность

и обозначают

Ответ на поставленный выше вопрос дает следующее утверждение.

Пусть конечномерные распределения x⁽ⁿ⁾ слабо сходятся к соответствующим распределениям последовательности x, относительно к-рой предполагается, что она эргодична и Тогда для слабой сходимости

(т. е. для сходимости распределений стационарных времен ожидания) достаточно, чтобы

Сформулированное условие сходимости близко к необходимому.

Если управляющие последовательности и таковы, что независимы, а распределения слабо сходятся к распределениям , то для выполнения (6) достаточно, чтобы

Аналогично обстоит дело со стационарным распределением виртуального времени w^s(t).ожидания. Если конечномерные распределения процессов сходятся к распределениям и последовательность эргодична, то для сходимости распределений

достаточно, чтобы

7) Асимптотич. методы исследования одноканалъных систем (они включают в себя и теоремы устойчивости) дают приближенные формулы для случая больших и малых нагрузок. Пусть Тогда говорят, что система имеет большую нагрузку, если

близко к 0, и малую нагрузку, если аблизко к -1. Точная постановка задачи связана здесь как и в п. 6) с введением схемы серий. Именно, для случая больших нагрузок рассматривают процессы X^a(t), зависящие от параметра Пусть Х ^а(t).удовлетворяют условиям слабой зависимости, обеспечивающим при выполнение условий

равномерно по а, где

Тогда для стационарного виртуального времени w^s(t).при справедливо

Аналогичный результат будет иметь место и для стационарного распределения w^k.

Если условия большой нагрузки наложить на последовательности (также в схеме серий по параметру п), потребовав, чтобы

то весьма полно можно описать также и распределение допредельного времени w_n ожидания, включая т. н. переходные явления. Именно, пусть в дополнение к (7)

при любом Тогда если при не меняя знака, так что то

где w(и) - стандартный винеровскии процесс. Значение правой части (8) вычислено в явном виде. Если то

Если

то

Если

то

8) Системы с ограниченной очередью характеризуются тем, что вызовы, пришедшие в систему и заставшие очередь объема получают отказ и выбывают из рассмотрения. В этом случае а вероятность будет также вероятностью того, что n-й вызов получил отказ.

Уравнения (2) здесь следует заменить на уравнение вида

Пусть и последовательность метрически транзитивна. Пусть, кроме того, выполнено следующее условие: или или но во втором случае h_n не представимы в виде где При выполнении этих условий существует предельное распределение q _п при

Если, кроме того, (это имеет место, напр., в случае, когда а остальные управляющие последовательности принадлежат G), то можно найти явный вид стационарного распределения для q_n при поскольку в этом случае q_n связаны в простую однородную цепь Маркова с конечным числом состояний.

Существует также следующее представление для стационарного паспведеления:

где - положение частицы, вышедшей из О и блуждающей со скачками h_k, k=1, 2,..., в момент ее первого выхода за пределы интервала (-l, т). Если (т. е. если . то вероятности (9) могут быть явным образом выражены через распределения

9) В системах с автономным обслуживанием обслуживание вызовов в отличие от обычных систем с ожиданием может начинаться лишь в моменты времени О, где - элементы управляющей последовательности. Таким образом, вызов, заставший систему свободной, должен ждать до начала очередного этапа обслуживания.

Наряду с процессом {e(t)}, описывающим входящий поток, рассматривают процесс {s(t)}, где s(t).определяется как число вызовов, к-рое приняла бы на обслуживание система к моменту tпри бесконечной очереди. Обозначив через q(t).длину очереди в момент t, не считая вызовов уже находящихся на обслуживании, и положив X(t) = e(t)-s(t), получают

Это равенство аналогично соотношению (4) и приводит к следующему результату. Если процесс и эргодичен,

сходится при к распределению стационарного процесса

Если или а остальные управляющие подпоследовательности принадлежат G₁, то можно указать явные формулы для распределения

Лит. см. при ст. Массового обслуживания теория.

А. А. Боровков.

с ожиданием многоканальная - система массового обслуживания, алгоритм к-рой предусматривает накапливание вызовов в очереди, если в момент их прихода система оказалась занятой; при этом обслуживание вызовов ведется в нескольких каналах одновременно. Основные определения и обозначения см. в ст. Массового обслуживания система.

Функционирование многоканальных систем с очередью, управляемых последовательностью происходит следующим образом. Вызовы прибывают в моменты времени На обслуживание вызова с номером j тратится время в каком бы из каналов ни обслуживался этот вызов. Пришедшие вызовы тут же направляются (в порядке поступления) в любой свободный канал, если каналы не все заняты, или ждут, когда освободится какой-нибудь из каналов, куда и поступают на обслуживание. Пусть для простоты в момент времени t=0 система свободна.

1) Для наглядности изложения использованы следующие обозначения: - вектор времени ожидания n-го вызова, где w_n,j - время, к-рое должен ждать этот вызов до освобождения i каналов от вызовов, пришедших раньше, чем он; так что w_n,1 - "истинное" время ожидания. Пусть, кроме того,

а вектор получен из упорядочиванием по возрастанию его координат (так что первая координата равна min(x₁,..., х _т)).Тогда имеет место следующее рекуррентное соотношение для обобщающее свой одномерный аналог

Если последовательность и то существует собственная последовательность удовлетворяющая (1) и такая, что функция распределения при монотонно сходится к функции распределения Это утверждение допускает обобщение на случай и распространяется также на длину q_n очереди в момент прихода n-го вызова (под q_n понимают очередь, включая вызовы, находящиеся на обслуживании). Существуют формулы, связывающие предельные распределения для и q_n.

Если то (1) позволяет записать интегральное уравнение для стационарного распределения w⁰. В этом случае можно указать также простые связи между стационарными распределениями длины очереди и времени ожидания. Именно, если означает k-ю координату вектора то при существуют

Если

то

Здесь все случайные величины, стоящие под знаком вероятности, независимы.

Если, кроме того, распределение нерешетчато, то аналогичные формулы верны и для предельного распределения q(t). Если то

2) Если то можно указать явные формулы для предельных распределений q_n, q(t), Пусть а - показатель распределения и Тогда числа

описываются как известного вида рациональные функции от значений m, и где m - единственный корень в области|m|<1 уравнения

Если k>m, то

причем Аот k не зависит. Для предельного распределения времени ожидания

имеет место равенство

Если - нерешетчатая случайная величина, то существуют

где

В случае

где

3) Теоремы устойчивости (о непрерывной зависимости стационарного распределения от распределений и ) получены в менее общей форме, чем для одноканальных систем, и связаны с условием о существовании т. н. обновляющих событий. Однако в случае это условие с необходимостью выполнено. Если для таких систем в схеме серий распределения слабо сходятся соответственно к распределениям и, кроме того, то распределение будет слабо сходится к распределению

4) Асимптотич. методы исследования многоканальных систем для больших нагрузок дают результаты, аналогичные соответствующим результатам для одно-канальных систем.

Пусть в схеме серий для управляющих последовательностей. выполнено условие

(wDd равно разности между средним количеством вызовов, поступивших в систему, и средним количеством вызовов, к-рое система может обслужить за единицу времени; если то в качестве параметра б можно выбрать число имеющее тот же смысл). Тогда если

и равномерно ограничены при нек-ром e>0, то для длины q(t).очереди в момент времени tсправедливы при следующие соотношения:

при

где w(u).- стандартный винеровский процесс;

при

при

Аналогичные соотношения верны для длины q_n очереди и для времени ожидания.

Другое возможное направление асимптотич. исследований для многоканальных систем состоит в изучении систем с интенсивным входным потоком и неограниченно возрастающим (вместе с ) числом каналов обслуживания.

5) Поведение многоканальных систем с бесконечным числом каналов обслуживания, управляемых последовательностью описывается так же, как поведение многоканальных систем с очередью, с той лишь разницей, что здесь всегда есть свободные каналы и, следовательно, время ожидания для любого вызова равно 0. В качестве характеристики состояния системы рассматривают число q_n занятых линий в момент прихода n-го вызова или число q(t).занятых линий в момент времени t(как и везде выше q_n и q(t).- длины очереди и q₁=0).

Пусть и, кроме того, последовательность метрически транзитивна. Тогда если < то распределение последовательности при монотонно сходится к распределению собственной стационарной последовательности

где I{А} индикатор события А. Условие близко к необходимому условию для конечности (2).

6) Для систем, у к-рых распределение стационарной длины q^k очереди можно описать с помощью уравнений. Для этого следует ввести, величины

Число q⁰ (х).указывает, сколько вызовов осталось в системе, работающей в стационарном режиме, спустя время хпосле прихода нек-рого вызова, но без учета данного вызова и всех вызовов, поступающих после него.

Обозначив

получают

система функций P_j(x)удовлетворяет уравнениям

Здесь Р _-1 (х).следует положить, равной 0. Каждые из первых k+1 уравнений этой системы относительно имеют единственное решение в классе функций ограниченной вариации, обладающих свойствами

Аналогичные утверждения справедливы для распределения процесса q(t).

Если

то

где

a - показатель распределения

Если

то

где

a - показатель распределения Если, кроме того, - нерешетчатые случайные величины, то

7) Теоремы устойчивости в случае как и в предыдущих разделах, выясняют условия, при к-рых малое изменение управляющих последовательностей влечет за собой малое изменение стационарного распределения числа q^k занятых линий.

Для схемы серий, когда система управляется стационарными последовательностями зависящими от параметра n=1, 2,..., пусть выполнены следующие условия.

(А) Существует последовательность

такая, что метрически транзитивна, и конечномерные распределения сходятся при к распределениям

(В) при

(С) Распределения при всех

непрерывны в точке 0.

Теорема устойчивости утверждает тогда, что при выполнении условий (А), (В), (С) распределения последовательностей {q^(n)k} длин очередей (к-рые определяются равенством (2) с управляющими последовательностями ) сходятся при к распределениям {q^k}.

Все три условия (А), (В), (С), присутствующие в этом утверждении, существенны; отказ хотя бы от одного из них сразу позволяет строить примеры, где сходимость распределений {q^(n)k} отсутствует.

8) Асимптотич. анализ систем с бесконечным числом каналов обслуживания становится естественным и эффективным при изучении т. н. нагруженных систем, когда велика интенсивность входного потока. Несомненным преимуществом асимптотич. подхода является большая общность и универсальность установленных закономерностей.

Пусть входной поток означающий число вызовов, поступавших в систему к моменту времени t, зависит от параметра (схема серий), так что при для каждого фиксированного t>0, и, кроме того, существуют неубывающая функция m(t), функция при и непрерывный случайный процесс x(t), заданный на [0, t₀], такие, что распределения где

слабо сходятся при к распределению для любого измеримого и непрерывного относительно равномерной метрики функционала f.

Если, напр., и управление системой происходит с помощью последовательности то сформулированные условия будут выполнены при любом t₀, при этом

x(t).- стандартный винеровский процесс.

Относительно обслуживающего устройства предполагают, что Тогда:

1) Если то конечномерные распределения нормированного процесса очереди

слабо сходятся при к распределениям процесса

2) Если то конечномерные распределения процесса

слабо сходятся к конечномерным распределениям процесса

где q(t) -центрированный гауссовский процесс, не зависящий от x(t), с ковариационной функцией

Если потребовать от функций m(t).пли G(t).нек-рой гладкости, то сходимость процессов z_i(t).к процессам z_i(t), i=1, 2, будет иметь место и в более сильном смысле (напр., сходимость распределений f(z_i(t)) к при для всех функционалов, непрерывных относительно равномерной метрики).

Лит. см. при ст. Массового обслуживания теория.

А. А. Боровков.