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

Материал из wikixw
Перейти к навигации Перейти к поиску

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

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

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

Правописание[править]

Написание "queuinging" вместо "queuing" обычно встречается в области академических исследований. На самом деле, один из флагманских журналов этой профессии называется системами массового обслуживания .

"Queuing" - это, кстати,единственное английское слово, имеющее более четырех последовательных гласных.

Одиночные узлы массового обслуживания[править]

Простое описание и аналогия

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

Инжир. 1. Черный ящик. Вакансии приходят и уходят из очереди.

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

Инжир. 2. Узел массового обслуживания с 3 серверами. Сервер а простаивает, и таким образом ему дается приход для обработки. Сервер b в настоящее время занят и займет некоторое время, прежде чем он сможет завершить обслуживание своей работы. Сервер c только что завершил обслуживание задания и, таким образом, будет рядом с получением поступающего задания

Часто используется аналогия с кассиром в супермаркете. Есть и другие модели, но это одна из наиболее распространенных в литературе. Клиенты прибывают, обрабатываются кассиром и отправляются. Каждый кассир обрабатывает одного клиента одновременно, и поэтому это узел очереди только с одним сервером. Настройка, при которой клиент сразу же уйдет, когда по прибытии он обнаружит, что кассир занят, называется очередью без буфера (или без "зоны ожидания", или аналогичных терминов). Настройка с зоной ожидания для до n клиентов называется очередью с буфером размера n .

Процесс рождения-смерти

Поведение / состояние одной очереди (также называемого "массового обслуживания узел") может быть описана рождения-смерти процесс, который описать прибывших и выбывших из очереди, вместе с количеством рабочих мест (также называемые "клиенты" или "запросы", или любое количество других вещей, в зависимости от области) в настоящее время в системе. Приход увеличивает количество рабочих мест на 1, а уход (работа, завершающая свое обслуживание) уменьшает k на 1 ( см. Рис.1). 3).

Инжир. 3. Процесс рождения / смерти. Значения в кругах представляют собой состояние процесса рождения-смерти, К. Система переходит от значений k к "рождениям" и "смертям", которые происходят со скоростью, заданной различными значениями λ i и μ i соответственно. Для системы массового обслуживания, k это число заданий в системе (либо обслуживаемых, либо ожидающих, если очередь имеет буфер из ожидающих заданий). Далее, для очереди, как правило, считается, что скорость прибытия и скорость отправления не зависит от количества рабочих мест в очереди, так что мы рассматриваем один средний показатель прибытия/отправления за единицу времени до очереди. Следовательно, для очереди эта диаграмма имеет скорость прибытия λ = λ 1 , λ 2 , ..., λ k и скорости вылета μ = μ 1, μ 2 , ..., μ k ( см. рис. 4).
Инжир. 4. Очередь с 1 сервером, скорость прибытия λ и скорость отправления μ

Нотация Кендалла

Одиночные узлы массового обслуживания обычно описываются с помощью нотации Кендалла в виде A/ S / c, где A описывает распределение длительностей между каждым прибытием в очередь, S распределение времени обслуживания для заданий и c число серверов на узле. для примера нотации очередь M/M/1 представляет собой простую модель, в которой один сервер обслуживает задания, поступающие в соответствии с процессом Пуассона (межприходные длительности экспоненциально распределены ) и имеют экспоненциально распределенное время обслуживания. В очереди M/G/1 буква G обозначает общее и обозначает произвольное число распределение вероятностей для времени обслуживания.

Обзор развития теории[править]

В 1909 году датский инженер Агнер Краруп Эрланг, работавший на копенгагенской телефонной станции, опубликовал первую статью, посвященную тому, что сейчас называется теорией массового обслуживания. он смоделировал количество телефонных звонков, поступающих на биржу с помощью процесса Пуассона, и решил модель очереди M/D/1 в 1917 году и модель очереди M/D/ k в 1920 году. в нотации Кендалла:

  • M обозначает Марков или без памяти и означает, что прибытие происходит в соответствии с процессом Пуассона;
  • D обозначает детерминированные и означает задания, поступающие в очередь, которые требуют фиксированного объема обслуживания;
  • k описывает количество серверов в узле очереди (k = 1, 2,...).

Если на узле больше заданий, чем серверов, то задания будут стоять в очереди и ждать обслуживания

Очередь M/G / 1 была решена Феликсом Поллачеком в 1930 году, [11] решение позже было переработано в вероятностных терминах Александром Хинчиным и теперь известно как формула Поллачека–Хинчина .

После 1940-х годов теория массового обслуживания стала областью исследовательского интереса математиков.[12] В 1953 году Дэвид Джордж Кендалл решил очередь GI/M/ k [13] и ввел современную нотацию для очередей, теперь известную как нотация Кендалла . В 1957 году Поллачек изучил GI/G / 1, используя интегральное уравнение . Джон Кингман дал формулу для среднего времени ожидания в очереди G/G/1 : Формула Кингмана .

Леонард Клейнрок работал над применением теории массового обслуживания к коммутации сообщений и коммутации пакетов . Его первоначальным вкладом в эту область была докторская диссертация в Массачусетском технологическом институте в 1962 году, опубликованная в виде книги в 1964 году в области цифровой коммутации сообщений. Его теоретическая работа после 1967 года основывалась на использовании пакетной коммутации в ARPANET, предшественнике Интернета.

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

Такие проблемы, как показатели производительности для очереди M/G/ k, остаются открытыми.

Дисциплины обслуживания[править]

Пример очереди First in first out (FIFO).

На узлах очереди можно использовать различные политики планирования:

Первый в первый выход

  • Этот принцип, также называемый первым поступившим, первым обслуженным (FCFS), гласит, что клиенты обслуживаются по одному, и что клиент, который ждал дольше всего, обслуживается первым.

Последний в первом выходе

  • Этот принцип также обслуживает клиентов по одному, но клиент с самым коротким временем ожидания будет обслужен первым. Также известный как стек .

Общий доступ к процессору

  • Емкость обслуживания делится поровну между клиентами.

Приоритет

  • Клиенты с высоким приоритетом обслуживаются в первую очередь. приоритетные очереди могут быть двух типов: непостоянные (когда задание в службе не может быть прервано) и непостоянные (когда задание в Службе может быть прервано заданием с более высоким приоритетом). Ни в одной из этих моделей не теряется работа.

Самая короткая работа первая

  • Следующая работа, которая будет обслуживаться-это та, которая имеет наименьший размер

Упреждающее самое короткое задание сначала

  • Следующее задание, которое будет подаваться, - это задание с оригинальным наименьшим размером

Самое короткое оставшееся время обработки

  • Следующая работа, чтобы служить является тот, с наименьшим оставшимся требованием обработки.

Сервисный центр

  • Одиночный сервер: клиенты выстраиваются в очередь и есть только один сервер
  • Несколько параллельных серверов-одна очередь: клиенты выстраиваются в очередь и есть несколько серверов
  • Несколько серверов-несколько очередей: есть много счетчиков и клиенты могут решить, куда идти в очередь

Поведение клиента в ожидании

  • Отказ: клиенты, решившие не присоединяться к очереди, если она слишком длинная
  • Jockeying: клиенты переключаются между очередями, если они думают, что они будут обслуживаться быстрее, сделав это
  • Reneging: клиенты покидают очередь, если они слишком долго ждали обслуживания

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

Простая очередь из двух уравнений[править]

Общая базовая система массового обслуживания приписывается Эрлангу и является модификацией закона Литтла . Учитывая скорость прибытия λ, скорость отсева σ и скорость отправления μ, длина очереди L определяется как:

  • L = λ − σ μ .

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

  • μ λ = e − W μ

Второе уравнение обычно переписывается как:

  • W = 1 μ l n λ μ

В эпидемиологии широко распространена двухэтапная однокомпонентная модель.

Сети массового обслуживания[править]

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

Для сетей из m узлов состояние системы можно описать м-мерным вектором (x 1, x 2,...,.., x m)где x i представляет число клиентов в каждом узле.

Простейшая нетривиальная сеть очередей называется тандемными очередями . первыми значимыми результатами в этой области были Сети Джексона , для которых существует эффективное стационарное распределение формы продукта и анализ среднего значения , который позволяет вычислять средние показатели, такие как пропускная способность и время пребывания. Если общее число клиентов в сети остается постоянным, сеть называется замкнутой сетью, а также показано, что в теореме Гордона–Ньюэлла стационарное распределение имеет форму продукта . Этот результат был распространен на сеть BCMP [29] где показано, что сеть с очень общим временем обслуживания, режимами и маршрутизацией клиентов также демонстрирует стационарное распределение по форме продукта. Нормирующая константа может быть вычислена с помощью алгоритма Бьюзена, предложенного в 1973 году.

Также были исследованы сети потребителей, в которых клиенты разных классов имеют разные уровни приоритета на разных узлах обслуживания. другой тип сетей-это G-сети, впервые предложенные Эролом Геленбе в 1993 году: эти сети не предполагают экспоненциального распределения времени, как классическая сеть Джексона.

Пример анализа очереди M/M/1[править]

Рассмотрим очередь с 1 сервером и следующими переменными:

  • λ: средняя скорость прибытия (клиенты, прибывающие в систему за единицу времени, например, за 30 секунд);
  • μ: средняя скорость отправления (клиенты, покидающие систему-завершение обслуживания—за то же время единицы, например, за 30 секунд);
  • n: количество клиентов в системе на данный момент времени;
  • P n: вероятность наличия n клиентов в системе.

Далее, пусть E n - это число раз , когда система входит в состояние n, а L n-это число раз, когда система выходит из состояния N. Для всех п, мы имеем |ен − лн| ∈ {0, 1}, то есть количество раз, которое система оставляет государство отличается не более чем на 1 в число раз он переходит в это состояние, поскольку он либо вернется в это состояние в какой-то момент в будущем (ЕН = ЛН) или нет (|ЕН − ЛН| = 1).

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

Уравнение баланса

  • ситуация 0: μ 1 P 1 = λ 0 P 0
  • Ситуация 1: λ 0 P 0 + μ 2 P 2 = ( λ 1 + μ 1 ) P 1
  • ситуация n: λ n − 1 P n − 1 + μ n + 1 P n + 1 = ( λ n + μ n ) P n
  • По уравнению баланса, P 1 = λ 0 μ 1 P 0 P 2 = λ 1 μ 2 P 1 + 1 μ 2 ( μ 1 P 1 − λ 0 P 0 ) = λ 1 μ 2 P 1 = λ 1 λ 0 μ 2 μ 1 P 0
  • С помощью математической индукции, P n = λ n − 1 λ n − 2 ⋯ λ 0 μ n μ n − 1 ⋯ μ 1 P 0 = P 0 ∏ i = 0 n − 1 λ i μ i + 1
  • Потому что ∑ n = 0 ∞ P n = P 0 + P 0 ∑ n = 1 ∞ ∏ i = 0 n − 1 λ i μ i + 1 = 1
  • Мы получаем P 0 = 1 1 + ∑ n = 1 ∞ ∏ i = 0 n − 1 λ i μ i + 1

Алгоритмы маршрутизации[править]

В сетях дискретного времени, где существует ограничение на то, какие сервисные узлы могут быть активны в любое время, алгоритм планирования максимального веса выбирает политику обслуживания, чтобы дать оптимальную пропускную способность в случае, если каждое задание посещает только один сервисный узел . В более общем случае, когда задания могут посещать более одного узла, маршрутизация обратного давления обеспечивает оптимальную пропускную способность. Сетевой планировщик должен выбрать алгоритм организации очередей, который влияет на характеристики более крупной сети [ необходимая цитируемость ] . Смотрите также Stochastic scheduling для получения дополнительной информации о планировании систем массового обслуживания.

Средние пределы полей[править]

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

Пределы текучести[править]

Главная статья: Жидкий предел

Жидкие модели являются непрерывными детерминированными аналогами сетей массового обслуживания, полученными путем принятия предела, когда процесс масштабируется во времени и пространстве, позволяя гетерогенным объектам. Эта масштабированная траектория сходится к детерминированному уравнению, которое позволяет доказать устойчивость системы. Известно, что сеть массового обслуживания может быть стабильной, но иметь неустойчивый предел текучести.

Приближения интенсивного движения / диффузии[править]

Основная статья: Приближение интенсивного движения

В системе с высокой заполняемостью (использование около 1) для аппроксимации процесса длины очереди отраженным броуновским движением может быть использована аппроксимация интенсивного трафика , процесс Орнштейна–Уленбека или более общий диффузионный процесс . число размерностей RBM равно числу узлов массового обслуживания, а диффузия ограничена неотрицательным ортантом .

Смотрите также[править]

Дальнейшее чтение[править]

  • Гросс, Дональд; Карл М. Харрис (1998). Основы теории массового обслуживания . - Уайли. В сети
  • Deitel, Harvey M. (1984) [1982]. Введение в операционные системы (revisited first ed.). Эддисон-Уэсли.
  • Kleinrock, Leonard (2 Января 1975). Системы Массового Обслуживания: Том I-Теория . New York: Wiley Interscience.
  • Kleinrock, Leonard (22 Апреля 1976). Системы массового обслуживания: Том II-компьютерные приложения . New York: Wiley Interscience. p.
  • Lazowska, Edward D.; John Zahorjan; G. Scott Graham; Kenneth C. Sevcik (1984). Количественная Производительность Системы: Анализ Компьютерной Системы С Использованием Сетевых Моделей Массового Обслуживания . Prentice-Hall, Inc.

Пруф[править]

slate.com/business/2012/06/queueing-theory-what-people-hate-most-about-waiting-in-line.html

Источник — https://wikixw.ru/index.php?title=Теория_массового_обслуживания&oldid=9503