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

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

Definition

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

Scope

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

Sub-topics

• Markovian Queues
• Queueing Networks
• Regenerative Processes
• Renewal Theory

Core questions

• Как обобщение экспоненциальных интервалов между событиями на произвольные распределения расширяет пуассоновский процесс?
• Что говорят теоремы обновления о долгосрочных темпах и асимптотическом поведении?
• Как связаны средняя длина очереди и время ожидания в состоянии равновесия?
• Когда сети очередей допускают разрешимые решения в форме произведения?

Key theories

Теоремы обновления и модель обновления-вознаграждения

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

Закон Литтла

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

Clinical relevance

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

History

Эрланг основал теорию массового обслуживания между 1909 и 1920 годами со своими формулами телефонного трафика, теория обновления была разработана Феллером, Смитом и Коксом в 1940-х и 1950-х годах, а доказательство Литтла в 1961 году тождества длины очереди и результаты Джексона 1957 года по сетям расширили теорию на сложные системы обслуживания.

Key figures

• Agner Krarup Erlang
• William Feller
• David Cox
• John Little

Seminal works

• asmussen2003

Frequently asked questions

Как теория обновления обобщает пуассоновский процесс?

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

Что такое закон Литтла?

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