Закон Литтлса - Википедия - Littles law

В теория массового обслуживания, дисциплина в рамках математической теория вероятности, Результат Литтла, теорема, лемма, закон, или же формула[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]

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

Примечания

  1. ^ Альберто Леон-Гарсия (2008). Вероятность, статистика и случайные процессы для электротехники (3-е изд.). Прентис Холл. ISBN  978-0-13-147122-1.
  2. ^ Аллен, Арнольд А. (1990). Теория вероятностей, статистики и массового обслуживания: с приложениями информатики. Gulf Professional Publishing. п.259. ISBN  0120510510.
  3. ^ Simchi-Levi, D .; Уловка, М.А. (2013). "Введение" в закон Литтла в свете его 50-летия"". Исследование операций. 59 (3): 535. Дои: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 / opre.9.3.383. JSTOR  167570.
  10. ^ Джуэлл, Уильям С. (1967). "Простое доказательство: L = λW". Исследование операций. 15 (6): 1109–1116. Дои:10.1287 / opre.15.6.1109. JSTOR  168616.
  11. ^ Эйлон, Сэмюэл (1969). "Более простое доказательство L = λW". Исследование операций. 17 (5): 915–917. Дои:10.1287 / opre.17.5.915. JSTOR  168368.
  12. ^ Стидхам младший, Шалер (1974). "Последнее слово о L = λW". Исследование операций. 22 (2): 417–421. Дои:10.1287 / opre.22.2.417. JSTOR  169601.
  13. ^ Стидхам младший, Шалер (1972). "L = λW: Обесцененный аналог и новое доказательство ». Исследование операций. 20 (6): 1115–1120. Дои:10.1287 / opre.20.6.1115. JSTOR  169301.
  14. ^ Kim, S. H .; Уитт, В. (2013). «Статистический анализ с законом Литтла» (PDF). Исследование операций. 61 (4): 1030. Дои:10.1287 / opre.2013.1193.
  15. ^ Узкие места программной инфраструктуры в J2EE, Дипак Гоэль
  16. ^ Сравнительный анализ грубых ошибок и вещей, которые случаются ночью, Нил Гюнтер
  17. ^ Литтл, Дж. Д. С. (2011). "Закон Литтла в свете его 50-летия" (PDF). Исследование операций. 59 (3): 536–549. Дои:10.1287 / opre.1110.0940. JSTOR  23013126.
  18. ^ Харрис, Марк (22 февраля 2010 г.). «Закон Литтла: наука, лежащая в основе надлежащего укомплектования кадрами». Врачи скорой помощи ежемесячно. Архивировано из оригинал 5 сентября 2012 г.. Получено 4 сентября, 2012.
  19. ^ Берцимас, Д .; Наказато, Д. (1995). «Распределительный закон Литтла и его приложения» (PDF). Исследование операций. 43 (2): 298. Дои:10.1287 / opre.43.2.298. JSTOR  171838.

внешняя ссылка