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

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

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

Написание

Написание "queueing" вместо "queuing" обычно встречается в области академических исследований. Фактически, один из ведущих журналов в этой области - Queueing Systems .

Описание

Теория очередей является одной из основных областей изучения в дисциплине науки управления . С помощью науки управления предприятия могут решать различные проблемы, используя различные научные и математические подходы. Анализ очередей является вероятностным анализом очередей ожидания, и, таким образом, результаты, также называемые эксплуатационными характеристиками, являются вероятностными, а не детерминированными. [5] Вероятность того, что n клиентов находятся в системе очередей, среднее количество клиентов в системе очередей, среднее количество клиентов в очереди, среднее время, проведенное клиентом в общей системе очередей, среднее время, проведенное клиентом в очереди, и, наконец, вероятность того, что сервер занят или простаивает, — все это различные эксплуатационные характеристики, которые вычисляют эти модели очередей. [5] Общая цель анализа очередей — вычислить эти характеристики для текущей системы, а затем протестировать несколько альтернатив, которые могут привести к улучшению. Вычисление эксплуатационных характеристик для текущей системы и сравнение значений с характеристиками альтернативных систем позволяет менеджерам увидеть плюсы и минусы каждого потенциального варианта. Эти системы помогают в процессе принятия окончательного решения, показывая способы увеличения экономии, сокращения времени ожидания, повышения эффективности и т. д. Основные модели очередей, которые можно использовать, — это система с одним сервером и система с несколькими серверами, которые обсуждаются ниже. Эти модели могут быть дополнительно дифференцированы в зависимости от того, является ли время обслуживания постоянным или неопределенным, длина очереди конечна, количество вызывающих абонентов конечно и т. д. [5]

Отдельные узлы очередей

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

Черный ящик. Задания поступают в очередь и покидают ее.

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

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

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

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

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

Система переходит между значениями k посредством "рождений" и "смертей", которые происходят при скоростях прибытия и скоростях отправления для каждой работы . Для очереди эти скорости обычно считаются не зависящими от количества работ в очереди, поэтому предполагается единая средняя скорость прибытия/убытия за единицу времени. При этом предположении этот процесс имеет скорость прибытия и скорость отправления . λ я {\displaystyle \лямбда _{я}} μ я {\displaystyle \mu _{i}} я {\displaystyle я} λ = в среднем ( λ 1 , λ 2 , … , λ к ) {\displaystyle \lambda ={\text{avg}}(\lambda _{1},\lambda _{2},\dots ,\lambda _{k})} μ = в среднем ( μ 1 , μ 2 , … , μ к ) {\displaystyle \mu = {\text{avg}}(\mu _{1},\mu _{2},\dots,\mu _{k})}

Процесс рождения–смерти. Значения в кругах представляют состояние системы, которое развивается на основе скоростей прибытия λ i и скоростей отправления μ i .
Очередь с 1 сервером, скоростью поступления λ и скоростью отправления μ

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

Уравнения стационарного состояния для процесса рождения и смерти, известные как уравнения баланса , следующие. Здесь обозначает вероятность стационарного состояния находиться в состоянии n . П н {\displaystyle P_{n}}

μ 1 П 1 = λ 0 П 0 {\displaystyle \mu _{1}P_{1}=\lambda _{0}P_{0}}
λ 0 П 0 + μ 2 П 2 = ( λ 1 + μ 1 ) П 1 {\displaystyle \lambda _{0}P_{0}+\mu _{2}P_{2} = (\lambda _{1}+\mu _{1})P_{1}}
λ н − 1 П н − 1 + μ н + 1 П н + 1 = ( λ н + μ н ) П н {\displaystyle \lambda _{n-1}P_{n-1}+\mu _{n+1}P_{n+1} = (\lambda _{n}+\mu _{n})P_{ н}}

Первые два уравнения подразумевают

П 1 = λ 0 μ 1 П 0 {\displaystyle P_{1}={\frac {\lambda _{0}}{\mu _{1}}}P_{0}}

и

П 2 = λ 1 μ 2 П 1 + 1 μ 2 ( μ 1 П 1 − λ 0 П 0 ) = λ 1 μ 2 П 1 = λ 1 λ 0 μ 2 μ 1 П 0 {\displaystyle P_{2}={\frac {\lambda _{1}}{\mu _{2}}}P_{1}+{\frac {1}{\mu _{2}}}(\ mu _{1}P_{1}-\lambda _{0}P_{0})={\frac {\lambda _{1}}{\mu _{2}}}P_{1}={\frac {\lambda _{1}\lambda _{0}}{\mu _{2}\mu _{1}}}P_{0}} .

По математической индукции,

П н = λ н − 1 λ н − 2 ⋯ λ 0 μ н μ н − 1 ⋯ μ 1 П 0 = П 0 ∏ я = 0 н − 1 λ я μ я + 1 {\displaystyle P_{n}={\frac {\lambda _{n-1}\lambda _{n-2}\cdots \lambda _{0}}{\mu _{n}\mu _{n- 1}\cdots \mu _{1}}}P_{0}=P_{0}\prod _{i=0}^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}} .

Состояние приводит к ∑ н = 0 ∞ П н = П 0 + П 0 ∑ н = 1 ∞ ∏ я = 0 н − 1 λ я μ я + 1 = 1 {\displaystyle \sum _{n=0}^{\infty }P_{n}=P_{0}+P_{0}\sum _{n=1}^{\infty }\prod _{i=0 }^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}=1}

П 0 = 1 1 + ∑ н = 1 ∞ ∏ я = 0 н − 1 λ я μ я + 1 {\displaystyle P_{0}={\frac {1}{1+\sum _{n=1}^{\infty }\prod _{i=0}^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}}}}

что вместе с уравнением для полностью описывает требуемые вероятности стационарного состояния. П н {\displaystyle P_{n}} ( н ≥ 1 ) {\displaystyle (n\geq 1)}

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

Отдельные узлы очередей обычно описываются с помощью нотации Кендалла в форме A/S/ c , где A описывает распределение длительностей между каждым прибытием в очередь, S — распределение времен обслуживания заданий, а c — количество серверов в узле. [6] [7] В качестве примера нотации можно привести очередь M/M/1 , которая представляет собой простую модель, в которой один сервер обслуживает задания, поступающие в соответствии с пуассоновским процессом (где длительности между прибытиями распределены экспоненциально ) и имеющие экспоненциально распределенные времена обслуживания (M обозначает марковский процесс ). В очереди M/G/1 G означает «general» и указывает на произвольное распределение вероятностей для времен обслуживания.

Пример анализа очереди M/M/1

Рассмотрим очередь с одним сервером и следующими характеристиками:

  • λ {\displaystyle \лямбда} : скорость прибытия (обратная величина ожидаемого времени между прибытием каждого клиента, например, 10 клиентов в секунду)
  • μ {\displaystyle \мю} : величина, обратная среднему времени обслуживания (ожидаемое количество последовательных завершений обслуживания за одну и ту же единицу времени, например за 30 секунд)
  • n : параметр, характеризующий количество клиентов в системе
  • П н {\displaystyle P_{n}} : вероятность того, что в системе в устойчивом состоянии будет n клиентов

Далее, пусть представляет собой количество раз, когда система входит в состояние n , а представляет собой количество раз, когда система выходит из состояния n . Тогда для всех n . То есть, количество раз, когда система выходит из состояния, отличается не более чем на 1 от количества раз, когда она входит в это состояние, поскольку она либо вернется в это состояние в какой-то момент в будущем ( ), либо нет ( ). Э н {\displaystyle E_{n}} Л н {\displaystyle L_{n}} | Э н − Л н | ∈ { 0 , 1 } {\displaystyle \left\vert E_{n}-L_{n}\right\vert \in \{0,1\}} Э н = Л н {\displaystyle E_{n}=L_{n}} | Э н − Л н | = 1 {\displaystyle \left\vert E_{n}-L_{n}\right\vert =1}

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

Таким образом, уравнения баланса

μ П 1 = λ П 0 {\displaystyle \mu P_{1}=\lambda P_{0}}
λ П 0 + μ П 2 = ( λ + μ ) П 1 {\displaystyle \lambda P_{0}+\mu P_{2} = (\lambda +\mu )P_{1}}
λ П н − 1 + μ П н + 1 = ( λ + μ ) П н {\displaystyle \lambda P_{n-1}+\mu P_{n+1} = (\lambda +\mu)P_{n}}

подразумевать

П н = λ μ П н − 1 ,   н = 1 , 2 , … {\displaystyle P_{n}={\frac {\lambda }{\mu }}P_{n-1},\ n=1,2,\ldots }

Тот факт, что приводит к формуле геометрического распределения П 0 + П 1 + ⋯ = 1 {\displaystyle P_{0}+P_{1}+\cdots =1}

П н = ( 1 − ρ ) ρ н {\displaystyle P_{n}=(1-\rho )\rho ^{n}}

где . ρ = λ μ < 1 {\displaystyle \rho ={\frac {\lambda }{\mu }}<1}

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

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

L = λ − σ μ {\displaystyle L={\frac {\lambda -\sigma }{\mu }}} .

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

μ λ = e − W μ {\displaystyle {\frac {\mu }{\lambda }}=e^{-W{\mu }}}

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

W = 1 μ l n λ μ {\displaystyle W={\frac {1}{\mu }}\mathrm {ln} {\frac {\lambda }{\mu }}}

Двухэтапная модель «одного ящика» широко распространена в эпидемиологии . [8]

История

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

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

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

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

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

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

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

Системы со связанными орбитами играют важную роль в теории очередей в применении к беспроводным сетям и обработке сигналов. [19]

Современное применение теории массового обслуживания касается, помимо прочего, разработки продукции , где (материальные) продукты имеют пространственно-временное существование в том смысле, что продукты имеют определенный объем и определенную продолжительность. [20]

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

Дисциплины обслуживания

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

Первый пришел, первый ушел
Пример очереди «первым пришел, первым вышел» (FIFO)
Этот принцип также называется «первым пришел, первым обслужен » (FCFS) [21] . Он гласит, что клиенты обслуживаются по одному, и клиент, который ждет дольше всех, обслуживается первым. [22]
Последний пришел, первый ушел
Этот принцип также обслуживает клиентов по одному, но клиент с самым коротким временем ожидания будет обслужен первым. [22] Также известен как стек .
Совместное использование процессора
Мощность обслуживания делится поровну между клиентами. [22]
Приоритет
Клиенты с высоким приоритетом обслуживаются в первую очередь. [22] Приоритетные очереди могут быть двух типов: невытесняющие (когда работа в обслуживании не может быть прервана) и вытесняющие (когда работа в обслуживании может быть прервана работой с более высоким приоритетом). Ни одна работа не теряется ни в одной из моделей. [23]
Сначала самая короткая работа
Следующей работой, которую нужно обслужить, является работа с наименьшим размером. [24]
Сначала упреждающая самая короткая работа
Следующим заданием, которое будет выполнено, будет задание с наименьшим исходным размером. [25]
Кратчайшее оставшееся время обработки
Следующим заданием для обслуживания будет то, у которого осталось наименьшее количество обработки. [26]
Объект обслуживания
  • Один официант: клиенты выстраиваются в очередь, и есть только один официант
  • Несколько параллельных серверов (одна очередь): клиенты выстраиваются в очередь, и есть несколько серверов
  • Несколько параллельных серверов (несколько очередей): есть много счетчиков, и клиенты могут решать, к какому из них встать в очередь
Ненадежный сервер

Сбои сервера происходят в соответствии со стохастическим (случайным) процессом (обычно Пуассона) и сопровождаются периодами настройки, в течение которых сервер недоступен. Прерванный клиент остается в зоне обслуживания, пока сервер не будет исправлен. [27]

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

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

Сети очередей

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

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

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

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

Алгоритмы маршрутизации

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

Пределы среднего поля

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

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

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

Пределы жидкости

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

Приложения для очередей

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

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

Теория очередей углубляется в различные основополагающие концепции, при этом центральными являются процесс прибытия и процесс обслуживания. Процесс прибытия описывает способ, которым сущности присоединяются к очереди с течением времени, часто моделируемый с использованием стохастических процессов, таких как процессы Пуассона. Эффективность систем очередей измеряется с помощью ключевых показателей производительности. К ним относятся средняя длина очереди, среднее время ожидания и пропускная способность системы. Эти показатели дают представление о функциональности системы, направляя решения, направленные на повышение производительности и сокращение времени ожидания. [43] [44] [45]

Смотрите также

Ссылки

  1. ^ abc Sundarapandian, V. (2009). "7. Теория очередей". Вероятность, статистика и теория очередей . PHI Learning. ISBN 978-81-203-3844-9.
  2. ^ Лоуренс В. Доуди, Вирджилио А. Ф. Алмейда, Дэниел А. Менасче. «Производительность по проектированию: планирование вычислительной мощности на примере». Архивировано из оригинала 2016-05-06 . Получено 2009-07-08 .
  3. ^ Шлехтер, Кира (2 марта 2009 г.). «Медицинский центр Херши откроет переоборудованное отделение неотложной помощи». The Patriot-News . Архивировано из оригинала 29 июня 2016 г. Получено 12 марта 2009 г.
  4. ^ Mayhew, Les; Smith, David (декабрь 2006 г.). Использование теории очередей для анализа времени выполнения в отделениях неотложной помощи и травматологии в свете правительственной цели в 4 часа. Cass Business School . ISBN 978-1-905752-06-5. Архивировано из оригинала 7 сентября 2021 г. . Получено 2008-05-20 .
  5. ^ abc Тейлор, Бернард В. (2019). Введение в науку управления (13-е изд.). Нью-Йорк: Pearson. ISBN 978-0-13-473066-0.
  6. ^ Tijms, HC, Алгоритмический анализ очередей , Глава 9 в Первом курсе по стохастическим моделям, Wiley, Чичестер, 2003
  7. ^ Кендалл, Д. Г. (1953). «Случайные процессы, происходящие в теории очередей, и их анализ методом вложенной цепи Маркова». Анналы математической статистики . 24 (3): 338–354 . doi : 10.1214/aoms/1177728975 . JSTOR  2236285.
  8. ^ Эрнандес-Суарес, Карлос (2010). «Применение теории очередей к моделям эпидемий SIS и SEIS». Math. Biosci . 7 (4): 809– 823. doi : 10.3934/mbe.2010.7.809 . PMID  21077709.
  9. ^ "Agner Krarup Erlang (1878-1929) | plus.maths.org". Pass.maths.org.uk. 1997-04-30. Архивировано из оригинала 2008-10-07 . Получено 2013-04-22 .
  10. ^ Асмуссен, СР; Боксма, О.Дж. (2009). «Редакционное введение». Системы массового обслуживания . 63 ( 1–4 ): 1–2 . doi :10.1007/s11134-009-9151-8. S2CID  45664707.
  11. ^ Эрланг, Агнер Краруп (1909). «Теория вероятностей и телефонные разговоры» (PDF) . Nyt Tidsskrift для Matematik B. 20 : 33–39 . Архивировано из оригинала (PDF) 2011-10-01.
  12. ^ abc Kingman, JFC (2009). «Первый век Erlang — и следующий». Системы массового обслуживания . 63 ( 1– 4): 3– 4. doi :10.1007/s11134-009-9147-4. S2CID  38588726.
  13. ^ Поллачек, Ф., Ueber eine Aufgabe der Wahrscheinlichkeitstheorie, Math. З. 1930 г.
  14. ^ abc Whittle, P. (2002). «Прикладная вероятность в Великобритании». Исследование операций . 50 (1): 227– 239. doi : 10.1287/opre.50.1.227.17792 . JSTOR  3088474.
  15. ^ Кендалл, Д.Г.: Стохастические процессы, происходящие в теории очередей, и их анализ методом вложенной цепи Маркова, Ann. Math. Stat. 1953
  16. ^ Поллачек, Ф., Стохастические проблемы, связанные с явлением формирования очереди
  17. ^ Кингман, Дж. Ф. К .; Атья (октябрь 1961 г.). «Очередь с одним сервером в условиях интенсивного трафика». Математические труды Кембриджского философского общества . 57 (4): 902. Bibcode : 1961PCPS...57..902K. doi : 10.1017/S0305004100036094. JSTOR  2984229. S2CID  62590290.
  18. ^ Рамасвами, В. (1988). «Устойчивая рекурсия для вектора стационарного состояния в цепях Маркова типа m/g/1». Сообщения по статистике. Стохастические модели . 4 : 183– 188. doi :10.1080/15326348808807077.
  19. ^ Морозов, Е. (2017). "Анализ устойчивости многоклассовой системы повторных вызовов со связанными очередями орбит". Труды 14-го Европейского семинара . Конспект лекций по информатике. Том 17. С.  85–98 . doi : 10.1007/978-3-319-66583-2_6 . ISBN 978-3-319-66582-5.
  20. ^ Карлсон, EC; Фелдер, RM (1992). «Моделирование и моделирование сетей очередей для кампаний по производству одного продукта». Компьютеры и химическая инженерия . 16 (7): 707– 718. doi :10.1016/0098-1354(92)80018-5.
  21. ^ ab Manuel, Laguna (2011). Моделирование бизнес-процессов, имитация и проектирование. Pearson Education India. стр. 178. ISBN 978-81-317-6135-9. Получено 6 октября 2017 г.
  22. ^ abcd Пенттинен А., Глава 8 – Системы массового обслуживания , Конспект лекций: S-38.145 - Введение в теорию телетрафика.
  23. ^ Харчол-Балтер, М. (2012). «Планирование: невытесняющие, основанные на размере политики». Моделирование производительности и проектирование компьютерных систем . стр.  499–507 . doi :10.1017/CBO9781139226424.039. ISBN 978-1-139-22642-4.
  24. ^ Эндрю С. Таненбаум; Герберт Бос (2015). Современные операционные системы. Pearson. ISBN 978-0-13-359162-0.
  25. ^ Харчол-Балтер, М. (2012). «Планирование: упреждающие политики на основе размера». Моделирование производительности и проектирование компьютерных систем . стр.  508–517 . doi :10.1017/CBO9781139226424.040. ISBN 978-1-139-22642-4.
  26. ^ Харчол-Балтер, М. (2012). «Планирование: SRPT и справедливость». Моделирование производительности и проектирование компьютерных систем . стр.  518–530 . doi :10.1017/CBO9781139226424.041. ISBN 978-1-139-22642-4.
  27. ^ Димитриу, И. (2019). «Многоклассовая система повторных вызовов со связанными орбитами и перерывами в обслуживании: проверка условий устойчивости». Труды FRUCT 24. 7 : 75–82 .
  28. ^ "Архивная копия" (PDF) . Архивировано (PDF) из оригинала 2017-03-29 . Получено 2018-08-02 .{{cite web}}: CS1 maint: archived copy as title (link)
  29. ^ Джексон, Дж. Р. (1957). «Сети очередей ожидания». Исследование операций . 5 (4): 518– 521. doi :10.1287/opre.5.4.518. JSTOR  167249.
  30. ^ Джексон, Джеймс Р. (октябрь 1963 г.). «Системы очередей типа Jobshop». Management Science . 10 (1): 131– 142. doi :10.1287/mnsc.1040.0268. JSTOR  2627213.
  31. ^ Рейзер, М.; Лавенберг, С.С. (1980). «Анализ среднего значения закрытых многоцепочечных сетей очередей». Журнал ACM . 27 (2): 313. doi : 10.1145/322186.322195 . S2CID  8694947.
  32. ^ Ван Дейк, НМ (1993). «О теореме прибытия для сетей связи». Компьютерные сети и системы ISDN . 25 (10): 1135– 2013. doi :10.1016/0169-7552(93)90073-D. S2CID  45218280. Архивировано из оригинала 24.09.2019 . Получено 24.09.2019 .
  33. ^ Гордон, У. Дж.; Ньюэлл, Г. Ф. (1967). «Закрытые системы очередей с экспоненциальными серверами». Исследование операций . 15 (2): 254. doi :10.1287/opre.15.2.254. JSTOR  168557.
  34. ^ Баскетт, Ф.; Чанди, К. Мани ; Мунц, Р. Р.; Паласиос, Ф. Г. (1975). «Открытые, закрытые и смешанные сети очередей с различными классами клиентов». Журнал ACM . 22 (2): 248– 260. doi : 10.1145/321879.321887 . S2CID  15204199.
  35. ^ Buzen, JP (1973). "Вычислительные алгоритмы для закрытых сетей очередей с экспоненциальными серверами" (PDF) . Communications of the ACM . 16 (9): 527– 531. doi :10.1145/362342.362345. S2CID  10702. Архивировано (PDF) из оригинала 2016-05-13 . Получено 2015-09-01 .
  36. ^ Келли, Ф. П. (1975). «Сети очередей с клиентами разных типов». Журнал прикладной вероятности . 12 (3): 542– 554. doi :10.2307/3212869. JSTOR  3212869. S2CID  51917794.
  37. ^ Геленбе, Эрол (сентябрь 1993 г.). «G-сети с инициированным движением клиентов». Журнал прикладной вероятности . 30 (3): 742– 748. doi :10.2307/3214781. JSTOR  3214781. S2CID  121673725.
  38. ^ Ньюэлл, GF (1982). "Применение теории очередей". SpringerLink . doi :10.1007/978-94-009-5970-5. ISBN 978-94-009-5972-9.
  39. ^ Боббио, А.; Грибодо, М.; Телек, М.С. (2008). «Анализ крупномасштабных взаимодействующих систем методом среднего поля». Пятая международная конференция по количественной оценке систем 2008 г. стр. 215. doi :10.1109/QEST.2008.47. ISBN 978-0-7695-3360-5. S2CID  2714909.
  40. ^ Чен, Х.; Уитт, В. (1993). «Приближения диффузии для открытых сетей очередей с прерываниями обслуживания». Системы очередей . 13 (4): 335. doi :10.1007/BF01149260. S2CID  1180930.
  41. ^ Ямада, К. (1995). «Аппроксимация диффузии для открытых сетей очередей, зависящих от состояния, в условиях интенсивного трафика». Анналы прикладной вероятности . 5 (4): 958–982 . doi : 10.1214/aoap/1177004602 . JSTOR  2245101.
  42. ^ Bramson, M. (1999). «Стабильная сеть очередей с нестабильной моделью жидкости». The Annals of Applied Probability . 9 (3): 818– 853. doi : 10.1214/aoap/1029962815 . JSTOR  2667284.
  43. ^ Гросс, Д. и Харрис, К. М. (1998). Основы теории очередей . John Wiley & Sons.
  44. ^ Клейнрок, Л. (1976). Системы массового обслуживания: Том I - Теория . Wiley.
  45. ^ Купер, Б. Ф. и Митрани, И. (1985). Сети очередей: фундаментальный подход . John Wiley & Sons.

Дальнейшее чтение

  • Гросс, Дональд; Карл М. Харрис (1998). Основы теории очередей . Wiley. ISBN 978-0-471-32812-4.Онлайн
  • Цукерман, Моше (2013). Введение в теорию очередей и стохастические модели телетрафика (PDF) . arXiv : 1307.2968 .
  • Deitel, Harvey M. (1984) [1982]. Введение в операционные системы (пересмотренное первое издание). Addison-Wesley. стр. 673. ISBN 978-0-201-14502-1.гл.15, стр. 380–412
  • Геленбе, Эрол; Иси Митрани (2010). Анализ и синтез компьютерных систем. World Scientific 2-е издание. ISBN 978-1-908978-42-4.
  • Ньюэлл, Гордрон Ф. (1 июня 1971 г.). Приложения теории очередей . Чепмен и Холл.
  • Леонард Клейнрок, Информационный поток в больших коммуникационных сетях (MIT, Кембридж, 31 мая 1961 г.) Предложение по докторской диссертации
  • Леонард Клейнрок. Информационный поток в крупных коммуникационных сетях (RLE Quarterly Progress Report, июль 1961 г.)
  • Леонард Клейнрок. Коммуникационные сети: стохастический поток сообщений и задержка (McGraw-Hill, Нью-Йорк, 1964)
  • Клейнрок, Леонард (2 января 1975 г.). Системы массового обслуживания: Том I – Теория . Нью-Йорк: Wiley Interscience. С. 417. ISBN 978-0-471-49110-1.
  • Клейнрок, Леонард (22 апреля 1976 г.). Системы массового обслуживания: Том II – Приложения компьютеров. Нью-Йорк: Wiley Interscience. С. 576. ISBN 978-0-471-49111-8.
  • Lazowska, Edward D.; John Zahorjan; G. Scott Graham; Kenneth C. Sevcik (1984). Количественная производительность системы: анализ компьютерных систем с использованием моделей сетей очередей. Prentice-Hall, Inc. ISBN 978-0-13-746975-8.
  • Джон Кляйнберг; Ева Тардос (30 июня 2013 г.). Алгоритм проектирования. Пирсон. ISBN 978-1-292-02394-6.
Найдите значение слова «очередь  » в Викисловаре — бесплатном словаре.
  • Учебник и калькуляторы по теории очередей от Teknomo
  • Курс теории массового обслуживания Виртамо
  • Страница теории очередей Мирона Глинки
  • LINE: универсальный движок для решения моделей очередей


Retrieved from "https://en.wikipedia.org/w/index.php?title=Queueing_theory&oldid=1268995479"