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

Математическое исследование очередей или очередей

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

Теория очередей — это математическое исследование очередей ожидания . ^[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 \lambda _{i}}$ ${\displaystyle \mu _{i}}$ ${\displaystyle i}$ ${\displaystyle \lambda ={\text{avg}}(\lambda _{1},\lambda _{2},\dots ,\lambda _{k})}$ ${\displaystyle \mu ={\text{avg}}(\mu _{1},\mu _{2},\dots ,\mu _{k})}$

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

Очередь с 1 сервером, скоростью поступления λ и скоростью отправления μ

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

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

${\displaystyle \mu _{1}P_{1}=\lambda _{0}P_{0}}$

${\displaystyle \lambda _{0}P_{0}+\mu _{2}P_{2}=(\lambda _{1}+\mu _{1})P_{1}}$

${\displaystyle \lambda _{n-1}P_{n-1}+\mu _{n+1}P_{n+1}=(\lambda _{n}+\mu _{n})P_{n}}$

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

${\displaystyle P_{1}={\frac {\lambda _{0}}{\mu _{1}}}P_{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}}$.

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

${\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}}}}$.

Состояние приводит к ${\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}$

${\displaystyle P_{0}={\frac {1}{1+\sum _{n=1}^{\infty }\prod _{i=0}^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}}}}$

что вместе с уравнением для полностью описывает требуемые вероятности стационарного состояния. ${\displaystyle P_{n}}$ ${\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 \lambda }$: скорость прибытия (обратная величина ожидаемого времени между прибытием каждого клиента, например, 10 клиентов в секунду)
• ${\displaystyle \mu }$: величина, обратная среднему времени обслуживания (ожидаемое количество последовательных завершений обслуживания за одну и ту же единицу времени, например за 30 секунд)
• n : параметр, характеризующий количество клиентов в системе
• ${\displaystyle P_{n}}$: вероятность того, что в системе в устойчивом состоянии будет n клиентов

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

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

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

${\displaystyle \mu P_{1}=\lambda P_{0}}$

${\displaystyle \lambda P_{0}+\mu P_{2}=(\lambda +\mu )P_{1}}$

${\displaystyle \lambda P_{n-1}+\mu P_{n+1}=(\lambda +\mu )P_{n}}$

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

${\displaystyle P_{n}={\frac {\lambda }{\mu }}P_{n-1},\ n=1,2,\ldots }$

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

${\displaystyle P_{n}=(1-\rho )\rho ^{n}}$

где . ${\displaystyle \rho ={\frac {\lambda }{\mu }}<1}$

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

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

${\displaystyle L={\frac {\lambda -\sigma }{\mu }}}$.

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

${\displaystyle {\frac {\mu }{\lambda }}=e^{-W{\mu }}}$

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

${\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 ₁ , x ₂ , ..., 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]

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

Теория очередей широко применяется в информатике и информационных технологиях. Например, в сетевых технологиях очереди являются неотъемлемой частью маршрутизаторов и коммутаторов, где пакеты выстраиваются в очередь для передачи. Применяя принципы теории очередей, проектировщики могут оптимизировать эти системы, обеспечивая отзывчивую производительность и эффективное использование ресурсов. За пределами технологической сферы теория очередей актуальна для повседневного опыта. Будь то ожидание в очереди в супермаркете или в общественном транспорте, понимание принципов теории очередей дает ценные сведения об оптимизации этих систем для повышения удовлетворенности пользователей. В какой-то момент каждый будет вовлечен в аспект очередей. То, что некоторые могут считать неудобством, может оказаться наиболее эффективным методом. Теория очередей, дисциплина, уходящая корнями в прикладную математику и информатику, является областью, посвященной изучению и анализу очередей или линий ожидания и их последствий в разнообразном спектре приложений. Эта теоретическая структура доказала свою эффективность в понимании и оптимизации эффективности систем, характеризующихся наличием очередей. Изучение очередей имеет важное значение в таких контекстах, как транспортные системы, компьютерные сети, телекоммуникации и операции по обслуживанию. Теория очередей углубляется в различные основополагающие концепции, при этом центральными являются процесс прибытия и процесс обслуживания. Процесс прибытия описывает способ, которым сущности присоединяются к очереди с течением времени, часто моделируемый с использованием стохастических процессов, таких как процессы Пуассона. Эффективность систем очередей измеряется с помощью ключевых показателей производительности. К ним относятся средняя длина очереди, среднее время ожидания и пропускная способность системы. Эти показатели дают представление о функциональности системы, направляя решения, направленные на повышение производительности и сокращение времени ожидания. Ссылки: Gross, D., & Harris, CM (1998). Fundamentals of Queueing Theory. John Wiley & Sons. Kleinrock, L. (1976). Queueing Systems: Volume I - Theory. Wiley. Cooper, BF, & Mitrani, I. (1985). Queueing Networks: A Fundamental Approach. John Wiley & Sons

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

• модель Эренфеста
• единица Эрланга
• Линейное управление
• Моделирование сети
• Управление производством проекта
• Зона очереди
• Задержка в очереди
• Система управления очередями
• Правило большого пальца при постановке в очередь
• Раннее случайное обнаружение
• Теория обновления
• Пропускная способность
• Планирование (вычисления)
• Пробка
• Модель генерации трафика
• Сеть потоков

Ссылки

1. 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. Тейлор, Бернард В. (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. дои : 10.1007/s11134-009-9151-8. S2CID  45664707.
11. Эрланг, Агнер Краруп (1909). «Теория вероятностей и телефонные разговоры» (PDF) . Nyt Tidsskrift для Matematik B. 20 : 33–39. Архивировано из оригинала (PDF) 2011-10-01.
12. 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. 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. Manuel, Laguna (2011). Моделирование бизнес-процессов, имитация и проектирование. Pearson Education India. стр. 178. ISBN 978-81-317-6135-9. Получено 6 октября 2017 г.
22. Пенттинен А., Глава 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.

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

• Гросс, Дональд; Карл М. Харрис (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: универсальный движок для решения моделей очередей