Массового Обслуживания Теория

Теория очередей, — раздел теории вероятностей, изучающий математич. модели разного рода реальных массового обслуживания систем. Эти модели представляют собой случайные процессы специального вида, к-рые наз. иногда процессами обслуживания. Чаще всего используется описательное определение этих процессов, поскольку формальное их построение оказывается весьма сложным и не всегда эффективным. М. о. т. использует главным образом аппарат теории вероятностей. Основные задачи М. о. т. обычно состоят в том, чтобы на основании "локальных" свойств рассматриваемых случайных процессов изучить их стационарные характеристики (если таковые существуют) или поведение этих характеристик за большой промежуток времени. Одна из главных конечных целей исследований в этой области состоит в выборе наиболее разумной организации систем массового обслуживания. Напр., для такого типичного объекта М. о. т., как автоматические телефонные станции (см. Массового обслуживания система с отказами), одной из основных характеристик является доля вызовов получивших отказ, т. е. предел рпри (если он существует) отношения r(t)/e(t).числа r(t).вызовов, получивших отказ за время t, к общему числу e(t).вызовов, поступивших за это время. При этом предполагаются известными распределение интервалов времени между поступлениями вызовов и распределение времени обслуживания этих вызовов. Задание распределения случайной (управляющей) последовательности вместе с описанием алгоритма, по к-рому происходит эволюция системы массового обслуживания, и составляют исходные данные, характеризующие "локальные свойства" процесса обслуживания. Аналогичным образом для массового обслуживания систем с ожиданием многоканальных изучаются предельные при распределения вероятностей для времени wn к-рое n-й по счету вызов, поступивший в систему, ожидал начала своего обслуживания с момента прихода, и для длины qn очереди в момент появления в системе n-го вызова. Рассматриваются также предельные распределения для длины очереди в момент времени t и др. При этом исходным опять является задание управляющей последовательности случайных величин (распределение интервалов и времени обслуживания) и алгоритм, определяющий работу системы массового обслуживания. Для сравнительно простых систем массового обслуживания и при нек-рых предположениях относительно управляющей последовательности случайных величин удается найти требуемые характеристики аналитич. методами. Однако число таких систем не велико. Характер условий, накладываемых на управляющие последовательности, можно продемонстрировать на примере системы массового обслуживания с отказами (автоматические телефонные станции). Пусть: 1) случайные величины показательно распределены: т. е. входящий поток является пуассоновским; 2) величины независимы, одинаково распределены и не зависят от Тогда определенная выше вероятность отказа рсуществует и равна где р равно отношению математич. ожиданий Для рассматриваемой системы отказ от одного из условий 1) — 2) значительно усложняет или делает невозможным отыскание явных формул для числа р. В основе аналитич. одхода в поисках явных выражений для искомых характеристик лежит прием, связанный с построением марковских процессов, описывающих состояние системы. Этот тип процессов достаточно хорошо изучен, и решение задачи в этом случае сводится к составлению и решению соответствующих уравнений для стационарных распределений (инвариантной меры). Такой подход часто используется в модифицированном виде, когда строятся полумарковские процессы или вложенные марковские процессы (свойство марковости выполняется лишь в нек-рые случайные моменты времени). Для более сложных систем массового обслуживания точные аналитич. методы, как правило, не эффективны и приходится использовать асимптотич. методы исследования или моделировать соответствующие случайные процессы с помощью Монте-Карло метода. Асимптотич. методы уместны в тех случаях, когда рассматриваемая система близка (в смысле ее локальных свойств) к другой системе, к-рая либо достаточно хорошо изучена и допускает вычисление нужных характеристик, либо эта система является в каком-то смысле критической. Направление асимптотич. исследований в первом случае описывается теоремами устойчивости (или непрерывности). Во втором случае стационарные характеристики часто не существуют, но для них удается устанавливать "собирательные" предельные теоремы, т. е. такие, в к-рых предельное поведение определяется не индивидуальными свойствами управляющих последовательностей, а лишь несколькими их числовыми параметрами. Примером второго типа асимптотич. результатов могут служить т. н. теоремы о нагруженных одноканальных системах с ожиданием. Они устанавливают следующее. Пусть интервалы j=1, 2, ... , между поступлениями вызовов и временем обслуживания j=1, 2, ... , образуют независимые друг от друга последовательности независимых одинаково распределенных величин и пусть математич. ожидание разности случайных величин положительно. Тогда существует невырожденное предельное распределение для времени wn ожидания n-го вызова. Кроме того, пусть случайные величины меняются так, что оставаясь положительным, дисперсия сходится к положительному пределу а математич. ожидание равномерно ограничено при нек-ром g>0. Тогда при каждом фиксированном z Это соотношение дает возможность приближенно вычислять w(x).при малых значениях а. Предельная система, соответствующая значению a=0, является критической в том смысле, что для нее не существует невырожденного предельного распределения w(х), и для каждого x>0 выполняется w(x)=1 (время ожидания n-го клиента неограниченно растет с ростом и). Соотношение (*) может быть распространено на широкий класс систем обслуживания с ожиданием при очень общих предположениях на управляющие последовательности. Возникновение М. о. т. было вызвано интересом к новым математич. задачам, возникающим в организации телефонных сетей. Первые публикации по этому поводу принадлежат А. Эрлангу (A. Erlang) и относятся к 20-м гг. 20 в. Дальнейшее развитие М. о. т. получила в 40-50-е гг. в работах К. Пальма (С. Palm), Ф. Поллачека (F. Pollaczek), А. Я. Хинчина и др. Последнему принадлежит и термин "массового обслуживания теория". В СССР эти работы по М. о. т. были продолжены Б. В. Гнеденко с группой его учеников и др. Развитие М. о. т. стимулируется как расширением круга ее приложений, так и математич. содержательностью возникающих при этом задач. Являясь формально частью теории случайных процессов, М. о. т. выделилась в самостоятельную область исследований со своим кругом проблем и своими подходами к их решению. Лит.:[1] X и н ч и н А. Я., Работы по математической теории массового обслуживания, М., 1963; [2] Г н е д е н к о Б. В., Коваленко II. Н., Введение в теорию массового обслуживания, М., 196В; [3] Боровков А. А., Вероятностные процессы в теории массового обслуживания, М., 1972; [4] его же, Асимптотические методы в теории массового обслуживания, М., 1980. А. А. Боровков.