МАССОВОГО ОБСЛУЖИВАНИЯ ТЕОРИЯ, теория очередей

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

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

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

Более сложные полумарковские процессы могут служить моделью математической процессов действия систем массового обслуживания. Их применение возможно при условии, когда среди случайных величин, характеризующих состояние системы в момент , может быть одна с произвольным законом распределения, все же остальные распределены по экспоненциальному закону (возможно, при некотором расширении пространства состояний процесса). Так, в системе массового обслуживания с экспоненциально распределенным временем обслуживания при входящем потоке с ограниченным последействием число требований в системе в момент t представляет собой полумарковский процесс Метод, в аналитическом отношении эквивалентный методу полумарковских процессов и называемый методом вложенных цепей Маркова, разработал англ. математик Д. Кендал (по существу, этот же метод сов. математик А. Я. Хинчин использовал при решении конкретных задач М. о. т. раньше Д. Кендала). Этот метод состоит в выборе такой последовательности моментов времени при которой последовательность значений процесса образует Маркова цепь с конечным или счетным мн-вом состояний. Чаще всего последовательность образуется моментами поступления в систему требований или моментами окончания операций обслуживания. Таким методом получены осн. ф-лы М. о. т. (см. Длина очереди, Хинчина—Полачека формула, Период занятости в системах массового обслуживания). Получена также теорема об общем аналитическом виде стационарных характеристик широкого класса однолинейных систем массового обслуживания и обобщена на нестационарный случай.

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

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

Первыми исследователями М. о. т. являются датский ученый А. Эрланг и сов. математик А. Я. Хинчин. В своих работах А. Эрланг в 1909-1922 гг. исследовал М. о. т. в связи с организацией телефонных сетей. А. Я. Хинчин в 1932-1933 гг. решил ряд задач из области многостаночного производства, а позднее разработал матем. теорию исследования систем массового обслуживания. Развитие производства, техники, эконом, связей в 50-е гг. привело к необходимости исследования новых систем массового обслуживания. В настоящее время М. о. т. успешно применяется в различных областях нар. х-ва, экономики, техники и науки, разрабатываются новые методы исследований, расширяется круг методов изучения и оптимизации систем массового обслуживания, поддающихся решению, изыскиваются новые пути практического приложения имеющихся теор. результатов. Исследования М. о. т. имеют большое значение при проектировании и построении различных систем автоматизированного управления производством и транспортом, для рациональной орг-ции производства и снижения себестоимости продукции.

Лит.: Хинчин А. Я. Работы по математической теории массового обслуживания. М., 1963; Бусленко Н. П. Математическое моделирование производственных процессов на цифровых вычислительных машинах. М., 1964 [библиогр. с. 361—362]; Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. М., 1966 [библиогр. с. 421—428]; Климов Г. П. Стохастические системы обслуживания. М., 1966 [библиогр. с. 242—243]; Саати Т. Л. Элемент теории массового обслуживания и ее приложения. Пер. с англ. М., 1971 [библиогр. с. 450—509]. И. Н. Коваленко.