stringtranslate.com

Закон Литтла

В математической теории массового обслуживания закон Литтла ( также результат , теорема , лемма или формула [1] [2] ) — это теорема Джона Литтла , которая утверждает, что долгосрочное среднее число L клиентов в стационарной системе равно долгосрочная средняя эффективная скорость поступления λ, умноженная на среднее время 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 , или просто:

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

Рекомендации

  1. ^ Альберто Леон-Гарсия (2008). Вероятность, статистика и случайные процессы в электротехнике (3-е изд.). Прентис Холл. ISBN 978-0-13-147122-1.
  2. ^ Аллен, Арнольд А. (1990). Вероятность, статистика и теория массового обслуживания: с приложениями в области информатики. Профессиональное издательство Персидского залива. п. 259. ИСБН 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 .
  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). Очереди, запасы и обслуживание: анализ операционной системы с переменным спросом и предложением . Уайли.
  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. ^ Ким, SH; Уитт, В. (2013). «Статистический анализ с использованием закона Литтла» (PDF) . Исследование операций . 61 (4): 1030. doi :10.1287/opre.2013.1193.
  15. ↑ Коррелл, Николаус (13 июня 2021 г.). «Сроки производства» . Проверено 12 июня 2021 г.
  16. ^ Узкие места программной инфраструктуры в J2EE, Дипак Гоэл
  17. ^ Сравнительный анализ ошибок и вещей, которые происходят в ночи, Нил Гюнтер
  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.

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