Закон Литтла

В математической массового обслуживания теории закон Литтла (также результат , теорема , лемма или формула) ^{[ 1 ]}^{[ 2 ]}) — это теорема Джона Литтла , которая утверждает, что долгосрочное среднее количество L клиентов в стационарной системе равно долгосрочному среднему эффективному коэффициенту прибытия λ, умноженному на среднее время W , которое клиент проводит в системе. Выражаясь алгебраически, закон имеет вид

L=\lambda W.

На отношения не влияет распределение процессов прибытия, распределение услуг, порядок обслуживания или практически что-либо еще. В большинстве систем массового обслуживания время обслуживания является узким местом , создающим очередь. ^{[ 3 ]}

Этот результат применим к любой системе и, в частности, к системам внутри систем. ^{[ 4 ]} Например, в отделении банка линия клиентов может представлять собой одну подсистему, а каждый кассир — другую подсистему, и результат Литтла можно применить к каждой из них, а также ко всей системе в целом. Единственные требования — чтобы система была стабильной и невытесняющей. ^{[ нечеткий ]}; это исключает переходные состояния, такие как первоначальный запуск или выключение.

В некоторых случаях можно не только математически связать среднее число в системе со средним временем ожидания, но даже связать с ожиданием все распределение вероятностей (и моменты) числа в системе. ^{[ 5 ]}

История

В статье 1954 года закон Литтла считался истинным и использовался без доказательств. ^{[ 6 ]}^{[ 7 ]} Форма L = λW была впервые опубликована Филипом М. Морсом , где он предложил читателям найти ситуацию, в которой связь не сохраняется. ^{[ 6 ]}^{[ 8 ]} Литтл опубликовал в 1961 году свое доказательство закона, показав, что такой ситуации не существует. ^{[ 9 ]} За доказательством Литтла последовала более простая версия Джуэлла. ^{[ 10 ]} и еще один от Эйлон. ^{[ 11 ]} Шалер Стидхэм опубликовал другое, более интуитивное доказательство в 1972 году. ^{[ 12 ]}^{[ 13 ]}

Примеры

Находим время ответа

Представьте себе приложение, в котором нет простого способа измерения времени отклика . Если известно среднее число в системе и пропускная способность, среднее время отклика можно найти с помощью закона Литтла:

среднее время ответа = среднее количество в системе / средняя пропускная способность

Например: измеритель глубины очереди показывает в среднем девять заданий, ожидающих обслуживания. Добавьте один для обслуживаемого задания, так что в системе будет в среднем десять заданий. Другой счетчик показывает среднюю пропускную способность 50 в секунду. Среднее время ответа рассчитывается как 0,2 секунды = 10/50 в секунду.

Покупатели в магазине

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

вход → просмотр → стойка → выход

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

Закон Литтла говорит нам, что среднее количество покупателей в магазине L — это эффективная скорость прибытия λ , умноженная на среднее время, которое покупатель проводит в магазине W , или просто:

L=\lambda W

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

L=10\times 0.5=5

Теперь предположим, что магазин рассматривает возможность увеличения количества рекламы, чтобы увеличить количество посетителей до 20 в час. Магазин должен либо быть готов принять в среднем 10 человек, либо сократить время, которое каждый покупатель проводит в магазине, до 0,25 часа. Магазин может добиться последнего, если будет быстрее выставлять счета или устанавливать больше прилавков.

Мы можем применить закон Литтла к системам внутри магазина. Например, рассмотрим счетчик и его очередь. Предположим, мы заметили, что в очереди и у стойки в среднем 2 покупателя. Мы знаем, что скорость прибытия составляет 10 человек в час, поэтому клиенты должны тратить в среднем 0,2 часа на выезд.

W={\frac {L}{\lambda }}={\frac {2}{10}}=0.2

Мы можем даже применить закон Литтла к самому счетчику. Среднее количество людей у стойки будет находиться в диапазоне (0, 1), поскольку одновременно у стойки может находиться не более одного человека. В этом случае среднее количество людей у стойки также называется загрузкой стойки.

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

Оценка параметров

Чтобы использовать закон Литтла о данных, необходимо использовать формулы для оценки параметров, поскольку результат не обязательно применим непосредственно к конечным интервалам времени из-за таких проблем, как регистрация клиентов, уже присутствующих в начале интервала регистрации, и тех, у кого есть еще не ушел, когда регистрация прекращается. ^{[ 14 ]}

Приложения

Закон Литтла широко используется в производстве для прогнозирования времени выполнения заказа на основе темпа производства и объема незавершенного производства. ^{[ 15 ]}

Тестировщики производительности программного обеспечения использовали закон Литтла, чтобы гарантировать, что наблюдаемые результаты производительности не связаны с узкими местами, создаваемыми аппаратурой тестирования. ^{[ 16 ]}^{[ 17 ]}

Другие области применения включают укомплектование персоналом отделений неотложной помощи в больницах. ^{[ 18 ]}^{[ 19 ]}

Форма распространения

Расширение закона Литтла обеспечивает взаимосвязь между устойчивым распределением количества клиентов в системе и временем, проведенным в системе в соответствии с дисциплиной обслуживания в порядке очереди . ^{[ 20 ]}

См. также

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

Ссылки

^ Альберто Леон-Гарсия (2008). Вероятность, статистика и случайные процессы в электротехнике (3-е изд.). Прентис Холл. ISBN 978-0-13-147122-1 .
^ Аллен, Арнольд А. (1990). Вероятность, статистика и теория массового обслуживания: с приложениями в области информатики . Профессиональное издательство Персидского залива. п. 259 . ISBN 0120510510 .
^ Симчи-Леви, Д.; Трик, Массачусетс (2013). «Введение в «Закон Литтла в свете его 50-летия» ». Исследование операций . 59 (3): 535. doi : 10.1287/opre.1110.0941 .
^ Серфозо, Р. (1999). «Маленькие законы». Введение в стохастические сети . стр. 135–154 . дои : 10.1007/978-1-4612-1482-3_5 . ISBN 978-1-4612-7160-4 .
^ Кейлсон, Дж .; Серви, Л.Д. (1988). «Распределительная форма закона Литтла» (PDF) . Письма об исследованиях операций . 7 (5): 223. дои : 10.1016/0167-6377(88)90035-1 . hdl : 1721.1/5305 .
^ Перейти обратно: ^а ^б Литтл, Джойнт ; Грейвс, Южная Каролина (2008). «Закон Литтла» (PDF) . Развитие интуиции . Международная серия по исследованию операций и науке управления. Том. 115. с. 81. дои : 10.1007/978-0-387-73699-0_5 . ISBN 978-0-387-73698-3 .
^ Кобэм, Алан (1954). «Распределение приоритетов в проблемах очереди». Исследование операций . 2 (1): 70–76. дои : 10.1287/opre.2.1.70 . JSTOR 166539 .
^ Морс, Филип М. (1958). Очереди, запасы и обслуживание: анализ операционной системы с переменным спросом и предложением . Уайли. Те читатели, которые хотели бы на собственном опыте убедиться в скользкости фундаментальных понятий в этой области и неразрешимости действительно общих теорем, могли бы попытаться показать, при каких обстоятельствах это простое соотношение между L и W не выполняется.
^ Литтл, Джойнт (1961). «Доказательство формулы массового обслуживания: L = λW ». Исследование операций . 9 (3): 383–387. дои : 10.1287/опре.9.3.383 . JSTOR 167570 .
^ Джуэлл, Уильям С. (1967). «Простое доказательство: L = λW ». Исследование операций . 15 (6): 1109–1116. дои : 10.1287/опре.15.6.1109 . JSTOR 168616 .
^ Эйлон, Сэмюэл (1969). «Простое доказательство L = λW » . Исследование операций . 17 (5): 915–917. дои : 10.1287/опре.17.5.915 . JSTOR 168368 .
^ Стидэм-младший, Шалер (1974). «Последнее слово о L = λW » . Исследование операций . 22 (2): 417–421. дои : 10.1287/опре.22.2.417 . JSTOR 169601 .
^ Стидхэм-младший, Шалер (1972). « L = λW : аналог со скидкой и новое доказательство». Исследование операций . 20 (6): 1115–1120. дои : 10.1287/опре.20.6.1115 . JSTOR 169301 .
^ Ким, Ш.; Уитт, В. (2013). «Статистический анализ с использованием закона Литтла» (PDF) . Исследование операций . 61 (4): 1030. doi : 10.1287/opre.2013.1193 .
^ Коррелл, Николаус (13 июня 2021 г.). «Сроки производства» . Проверено 12 июня 2021 г.
^ Узкие места программной инфраструктуры в J2EE, Дипак Гоэл
^ Сравнительный анализ ошибок и вещей, которые происходят ночью, Нил Гюнтер
^ Литтл, Джойнт (2011). «Закон Литтла глазами его 50-летия» (PDF) . Исследование операций . 59 (3): 536–549. дои : 10.1287/opre.1110.0940 . JSTOR 23013126 .
^ Харрис, Марк (22 февраля 2010 г.). «Закон Литтла: наука, лежащая в основе правильного подбора кадров» . Ежемесячник врачей скорой помощи. Архивировано из оригинала 5 сентября 2012 года . Проверено 4 сентября 2012 г.
^ Берцимас, Д.; Наказато, Д. (1995). «Закон Литтла о распределении и его применение» (PDF) . Исследование операций . 43 (2): 298. doi : 10.1287/opre.43.2.298 . JSTOR 171838 .

Внешние ссылки

Доказательство формулы массового обслуживания L = λ W , Сигман, К., Колумбийский университет
Доказательство формулы массового обслуживания L = λ W , Эдуардо, Мальдонадо, Алексби Усм

[1] Альберто Леон-Гарсия (2008). Вероятность, статистика и случайные процессы в электротехнике (3-е изд.). Прентис Холл. ISBN 978-0-13-147122-1 .

[allen-2] Аллен, Арнольд А. (1990). Вероятность, статистика и теория массового обслуживания: с приложениями в области информатики . Профессиональное издательство Персидского залива. п. 259 . ISBN 0120510510 .

[3] Симчи-Леви, Д.; Трик, Массачусетс (2013). «Введение в «Закон Литтла в свете его 50-летия» ». Исследование операций . 59 (3): 535. doi : 10.1287/opre.1110.0941 .

[4] Серфозо, Р. (1999). «Маленькие законы». Введение в стохастические сети . стр. 135–154 . дои : 10.1007/978-1-4612-1482-3_5 . ISBN 978-1-4612-7160-4 .

[5] Кейлсон, Дж .; Серви, Л.Д. (1988). «Распределительная форма закона Литтла» (PDF) . Письма об исследованиях операций . 7 (5): 223. дои : 10.1016/0167-6377(88)90035-1 . hdl : 1721.1/5305 .

[little-graves-6] Перейти обратно: ^а ^б Литтл, Джойнт ; Грейвс, Южная Каролина (2008). «Закон Литтла» (PDF) . Развитие интуиции . Международная серия по исследованию операций и науке управления. Том. 115. с. 81. дои : 10.1007/978-0-387-73699-0_5 . ISBN 978-0-387-73698-3 .

[7] Кобэм, Алан (1954). «Распределение приоритетов в проблемах очереди». Исследование операций . 2 (1): 70–76. дои : 10.1287/opre.2.1.70 . JSTOR 166539 .

[8] Морс, Филип М. (1958). Очереди, запасы и обслуживание: анализ операционной системы с переменным спросом и предложением . Уайли. Те читатели, которые хотели бы на собственном опыте убедиться в скользкости фундаментальных понятий в этой области и неразрешимости действительно общих теорем, могли бы попытаться показать, при каких обстоятельствах это простое соотношение между L и W не выполняется.

[9] Литтл, Джойнт (1961). «Доказательство формулы массового обслуживания: L = λW ». Исследование операций . 9 (3): 383–387. дои : 10.1287/опре.9.3.383 . JSTOR 167570 .

[10] Джуэлл, Уильям С. (1967). «Простое доказательство: L = λW ». Исследование операций . 15 (6): 1109–1116. дои : 10.1287/опре.15.6.1109 . JSTOR 168616 .

[11] Эйлон, Сэмюэл (1969). «Простое доказательство L = λW » . Исследование операций . 17 (5): 915–917. дои : 10.1287/опре.17.5.915 . JSTOR 168368 .

[12] Стидэм-младший, Шалер (1974). «Последнее слово о L = λW » . Исследование операций . 22 (2): 417–421. дои : 10.1287/опре.22.2.417 . JSTOR 169601 .

[13] Стидхэм-младший, Шалер (1972). « L = λW : аналог со скидкой и новое доказательство». Исследование операций . 20 (6): 1115–1120. дои : 10.1287/опре.20.6.1115 . JSTOR 169301 .

[14] Ким, Ш.; Уитт, В. (2013). «Статистический анализ с использованием закона Литтла» (PDF) . Исследование операций . 61 (4): 1030. doi : 10.1287/opre.2013.1193 .

[15] Коррелл, Николаус (13 июня 2021 г.). «Сроки производства» . Проверено 12 июня 2021 г.

[16] Узкие места программной инфраструктуры в J2EE, Дипак Гоэл

[17] Сравнительный анализ ошибок и вещей, которые происходят ночью, Нил Гюнтер

[50aniv-18] Литтл, Джойнт (2011). «Закон Литтла глазами его 50-летия» (PDF) . Исследование операций . 59 (3): 536–549. дои : 10.1287/opre.1110.0940 . JSTOR 23013126 .

[19] Харрис, Марк (22 февраля 2010 г.). «Закон Литтла: наука, лежащая в основе правильного подбора кадров» . Ежемесячник врачей скорой помощи. Архивировано из оригинала 5 сентября 2012 года . Проверено 4 сентября 2012 г.

[20] Берцимас, Д.; Наказато, Д. (1995). «Закон Литтла о распределении и его применение» (PDF) . Исследование операций . 43 (2): 298. doi : 10.1287/opre.43.2.298 . JSTOR 171838 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

v т и Теория массового обслуживания
Одиночные узлы массового обслуживания	Очередь Д/М/1 Очередь М/Д/1 Очередь М/Д/Ц Очередь М/М/1 Теорема Берка Очередь М/М/Ц Очередь М/М/∞ Очередь M/G/1 Формула Поллачека – Хинчина Матричный аналитический метод Очередь M/G/k Очередь G/M/1 Очередь G/G/1 Формула Кингмана Уравнение Линдли Разветвить очередь – присоединиться к ней Массовая очередь
Процессы прибытия	Точный процесс Пуассона Марковский процесс прибытия Рациональный процесс прибытия
Сети массового обслуживания	Сеть Джексона Уравнения дорожного движения Теорема Гордона – Ньюэлла Анализ среднего значения Алгоритм Бузена сеть Келли G-сеть Сеть BCMP
Политика обслуживания	ФИФО ЛИФО Совместное использование процессора Круговой Самая короткая работа следующая Кратчайшее оставшееся время
Ключевые понятия	Цепь Маркова с непрерывным временем Обозначения Кендалла Закон Литтла Решение в форме продукта Уравнение баланса Квазиобратимость Потоко-эквивалентный серверный метод Теорема о прибытии Метод разложения метод Бенеша
Предельные теоремы	Предел жидкости Теория среднего поля Приближение интенсивного движения Отраженное броуновское движение
Расширения	Жидкая очередь Многоуровневая сеть массового обслуживания Система опроса Состязательная сеть массового обслуживания Сеть потерь Очередь повторных попыток
Информационные системы	Буфер данных Эрланг (единица измерения) Распределение Эрланга Управление потоком (данные) Очередь сообщений Перегрузка сети Сетевой планировщик Конвейер (программное обеспечение) Качество обслуживания Планирование (вычисления) Телетрафик инжиниринг
Категория