«Массового обслуживания теория»

математическая дисциплина, изучающая системы, предназначенные для обслуживания массового потока требований случайного характера (случайными могут быть как моменты появления требований, так и затраты времени на их обслуживание). Типичным примером объектов М. о. т. могут служить автоматические телефонные станции, на которые случайным образом поступают «требования» — вызовы абонентов, а «обслуживание» состоит в соединении абонентов с другими абонентами, поддержании связи во время разговора и т. д. Целью развиваемых в М. о. т. методов является, в конечном счёте, отыскание разумной организации обслуживания, обеспечивающей заданное его качество. С этой точки зрения М. о. т. рассматривают как часть операций исследования (См. Операций исследование).

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

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

Одной из характеристик эффективности работы такой линии связи является доля вызовов, получающих отказ, то есть предел р при Т→∞ (если он существует) отношения ν_T/N_T числа ν_T вызовов, потерянных в течение времени Т, к общему числуN_T вызовов, поступивших за это время. Этот предел можно назвать вероятностью отказа.

Другим, не менее естественным, показателем качества работы линии связи может служить относительное время её занятости, то есть предел р* при T→∞ (если он существует) отношения τ_Т/Т, где τ_Т — суммарное время, в течение которого за период Т все n каналов линии связи одновременно заняты. Этот предел можно назвать вероятностью занятости. Обозначим X(t) число каналов, занятых в момент t. Тогда можно показать, что: 1) если моменты поступления вызовов образуют Пуассоновский поток однородных событий, 2) длительности разговоров последовательных абонентов суть независимые (между собой и от моментов поступления вызовов) одинаково распределённые случайные величины, то случайный процесс X(t), t ≥ 0, обладает эргодическим распределением, то есть существуют [не зависящие от начального распределения Х(0)] пределы

причём

(*)

где ρ — произведение интенсивности потока поступлений вызовов на среднюю длительность разговора отдельного абонента. Кроме того, в этом случае р = р*, и их общее значение равно p_n. Формулы (*) используются для расчёта минимального количества каналов линии связи, обеспечивающей заданную вероятность отказа. Эти формулы называются Эрланга формулами (См. Эрланга формулы). Следует добавить, что при отказе от условия 1) равенство р = р* может не выполняться.

Становление М. о. т. было вызвано интересом к математическим задачам, возникающим в организации телефонных сетей, датского инженера А. К. Эрланга, первые публикации которого относятся к 20-м годам 20 века. М. о. т. получила дальнейшее развитие в 40—50-х годах в работах К. Пальма (Швеция), Ф. Поллачека (Франция), А. Я. Хинчина (СССР). Последнему принадлежит сам термин «М. о. т.». Эти работы были продолжены советским математиком Б. В. Гнеденко и другими. Развитие М. о. т. в значительной мере стимулируется расширением круга её применений. Являясь формально частью теории случайных процессов, М. о. т. выделилась в самостоятельную область исследований со своим кругом задач и методов их решения и в свою очередь стимулирует развитие теории случайных процессов.

Лит.: Хинчин А. Я., Работы по математической теории массового обслуживания, М., 1963; Розенберг В. Я., Прохоров А. И., Что такое теория массового обслуживания, М., 1965; Гнеденко Б. В., Коваленко И. Н., Введение в теорию массового обслуживания, М., 1966; Саати Т. Л., Элементы теории массового обслуживания и её приложения, перевод с английского, М., 1971; Боровков А. А., Вероятностные процессы в теории массового обслуживания, М., 1972.

О. В. Висков.

МАССОВОГО ОБСЛУЖИВАНИЯ ТЕОРИЯ - раздел математики, изучающий системы, предназначенные для обслуживания массового потока требований случайного характера. Типичный пример такой системы - автоматическая телефонная станция, где случайным образом поступают "требования" - вызовы абонентов, а "обслуживание" состоит в соединении их с др. абонентами.

ма́ссового обслу́живания тео́рия

раздел математики, изучающий системы, предназначенные для обслуживания массового потока требований случайного характера. Типичный пример такой системы — автоматическая телефонная станция, где случайным образом поступают «требования» — вызовы абонентов, а «обслуживание» состоит в соединении их с другими абонентами.

* * *

МА́ССОВОГО ОБСЛУ́ЖИВАНИЯ ТЕО́РИЯ, раздел математики, изучающий системы, предназначенные для обслуживания массового потока требований случайного характера. Типичный пример такой системы — автоматическая телефонная станция, где случайным образом поступают «требования» — вызовы абонентов, а «обслуживание» состоит в соединении их с др. абонентами.

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

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

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

Аналогичным образом для массового обслуживания систем с ожиданием многоканальных изучаются предельные при распределения вероятностей для времени w_n к-рое n-й по счету вызов, поступивший в систему, ожидал начала своего обслуживания с момента прихода, и для длины q_n очереди в момент появления в системе n-го вызова. Рассматриваются также предельные распределения для длины очереди в момент времени t и др. При этом исходным опять является задание управляющей последовательности случайных величин (распределение интервалов и времени обслуживания) и алгоритм, определяющий работу системы массового обслуживания.

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

т. е. входящий поток является пуассоновским; 2) величины независимы, одинаково распределены и не зависят от Тогда определенная выше вероятность отказа рсуществует и равна

где р равно отношению математич. ожиданий

Для рассматриваемой системы отказ от одного из условий 1) - 2) значительно усложняет или делает невозможным отыскание явных формул для числа р.

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

Для более сложных систем массового обслуживания точные аналитич. методы, как правило, не эффективны и приходится использовать асимптотич. методы исследования или моделировать соответствующие случайные процессы с помощью Монте-Карло метода. Асимптотич. методы уместны в тех случаях, когда рассматриваемая система близка (в смысле ее локальных свойств) к другой системе, к-рая либо достаточно хорошо изучена и допускает вычисление нужных характеристик, либо эта система является в каком-то смысле критической. Направление асимптотич. исследований в первом случае описывается теоремами устойчивости (или непрерывности). Во втором случае стационарные характеристики часто не существуют, но для них удается устанавливать "собирательные" предельные теоремы, т. е. такие, в к-рых предельное поведение определяется не индивидуальными свойствами управляющих последовательностей, а лишь несколькими их числовыми параметрами. Примером второго типа асимптотич. результатов могут служить т. н. теоремы о нагруженных одноканальных системах с ожиданием. Они устанавливают следующее. Пусть интервалы j=1, 2,..., между поступлениями вызовов и временем обслуживания j=1, 2,..., образуют независимые друг от друга последовательности независимых одинаково распределенных величин и пусть математич. ожидание

разности случайных величин положительно. Тогда существует невырожденное предельное распределение

для времени w_n ожидания 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. А. А. Боровков.

о ч е-редей теория, - раздел прикладной математики, изучающий процессы, связанные с удовлетворением массового спроса случайного характера на обслуживание к.-л. вида. Типичный пример - "обслуживание" абонентов автоматич. телеф. станции, состоящее в соединении их между собой при условии, что момент вызова абонентов ("спрос") и продолжительность их разговора имеют случайный характер. Возникла в нач. 20 в. применительно к расчетам телеф. сетей; позднее методы М. о. т. стали применять при решении задач обслуживания пассажиров аэропортов, пропускной, способности трансп. магистралей, планирования и орг-ции ж.-д. перевозок, накопления запасов продуктов и т. п. Со второй пол. 60-х гг. М. о. т. используется применительно к орг-ции взаимодействия ЭВМ, теории надёжности, решению задач радиотехники, радиолокации и др. М. о; т. широко использует аппарат теории вероятности и (в меньшей степени) матем. статистики. Задачи М. о. т., сформулированные математически, обычно сводятся к изучению случайных процессов. Исходя из заданных вероятностных хар-к спроса и продолжительности обслуживания и учитывая схему системы обслуживания, М. о. т. определяет соответствующие хар-ки качества обслуживания (вероятность отказа, среднее время ожидания начала обслуживания, среднее время простоя и т. д.), к-рые могут быть использованы при необходимости для корректировки структуры и режима исследуемой системы.