Теория массового обслуживания
Тео́рия ма́ссового обслу́живания, раздел теории вероятностей, изучающий потоки требований, поступающие в системы обслуживания и выходящие из них, длительности ожидания начала обслуживания, длины очередей и другие характеристики систем обслуживания. Целью исследований является рациональный выбор структуры системы и процесса обслуживания. Многие реально протекающие процессы обслуживания на транспорте, в торговле, медицине и т. д. можно изучать исходя из соответствующих им математических моделей систем обслуживания. Стимулом развития теории массового обслуживания в 1920-х гг. послужило создание систем телефонной связи и необходимость расчёта их пропускной способности. С 1970-х гг. в теории массового обслуживания разрабатываются методы анализа и оптимизации процессов обслуживания с использованием ЭВМ.
В большинстве задач теории массового обслуживания предполагается, что входящий поток требований является случайным, т. е. последовательность моментов времени поступления требований на обслуживание рассматривается как последовательность случайных величин. Требования характеризуются длительностью обслуживания и могут относиться к одному или нескольким классам. Принадлежность требований к определённым классам может служить основанием для приоритетного обслуживания. Требования, имеющие абсолютный приоритет, обслуживаются в первую очередь, при их поступлении в систему обслуживания прерывается обслуживание требований с низшим приоритетом. Например, абсолютный приоритет имеют некоторые виды отказов в вычислительных устройствах, «обслуживание» таких «требований» состоит в их выявлении и устранении.
Часто в качестве приближения принимается, что входящий в систему обслуживания поток требований является пуассоновским процессом с постоянной интенсивностью , т. е. неотрицательные случайные величины , являются независимыми случайными величинами с экспоненциальной функцией распределения , где – интенсивность потока, равная среднему числу требований, поступающих в систему обслуживания в единицу времени. Продолжительности обслуживания предполагаются взаимно независимыми случайными величинами с функцией распределения , имеющей конечное среднее значение . Система обслуживания обычно может быть представлена в виде набора устройств (каналов) обслуживания. Если все каналы заняты обслуживанием, то вновь поступающие требования накапливаются и могут образовывать очереди (иногда теорию массового обслуживания называют теорией очередей). Движение очереди может быть организовано по-разному, например, в порядке поступления, что типично для многих процессов обслуживания в торговле, или в обратном порядке: «пришёл последним – обслуживаешься первым», что типично для некоторых вычислительных систем.
Примером системы обслуживания является система, состоящая из одного обслуживающего устройства, в которую поступает пуассоновский поток требований интенсивности , функция распределения длительности обслуживания имеет вид , , , требования образуют очередь в порядке поступления, ограничений на длину очереди нет. Если коэффициент загрузки , то такая система работает в стационарном режиме, т. е. её вероятностные характеристики постоянны во времени. Очередь с вероятностью 1 конечна, её средняя длина равна . Вероятность застать в момент поступления очередь длины равна , случайное время ожидания начала обслуживания имеет функцию распределения
Расчёт характеристик системы обслуживания существенно усложняется, если функция распределения отлична от приведённой выше. Стационарный режим возможен при ограничении . Средняя длина очереди в момент окончания обслуживания очередного требования равна
где – второй момент функции распределения . Для общей одноканальной системы обслуживания справедлива формула, по которой средняя длина очереди в стационарном режиме равна произведению интенсивности входящего потока на среднее время пребывания требования в системе.
Для многих систем обслуживания не удаётся получить явные аналитические выражения для их характеристик. Поэтому в теории массового обслуживания большое внимание уделяется асимптотическим методам анализа систем обслуживания, анализу устойчивости стационарных характеристик при малых изменениях и т. п. При асимптотическом анализе выделяются два предельных случая: малой нагрузки (быстрого обслуживания), когда , и большой нагрузки, когда .
В теории массового обслуживания актуальными являются задачи расчёта сетей, состоящих из систем обслуживания. Такого рода задачи возникают при расчёте систем связи с большой пропускной способностью, управляемых ЭВМ, а также при анализе вычислительных систем коллективного пользования. В таких системах обслуживания возможна реализация разнообразных дисциплин обслуживания, среди которых – т. н. дисциплина разделения времени. При такой дисциплине возможно одновременное обслуживание множества требований одним обслуживающим устройством (например, процессором ЭВМ). Однако скорость обслуживания при дисциплине разделения времени уменьшается обратно пропорционально числу одновременно обслуживаемых требований.
В теории массового обслуживания разрабатываются общие методы расчёта систем обслуживания. В основу некоторых методов положена идея представления процесса изменения состояний системы обслуживания как марковского процесса с дискретным или непрерывным множеством состояний. В простейших случаях вероятности состояний систем обслуживания находятся как решения конечных или бесконечных систем линейных уравнений. Более широкий класс систем обслуживания описывается системами смешанного типа – интегро-дифференциальными уравнениями с частными производными. Показатели качества работы многих систем обслуживания находят на основе статистического моделирования (метода Монте-Карло). Наряду с общими методами в теории массового обслуживания используются методы, связанные со спецификой конкретных систем обслуживания, применимые лишь к частным задачам.