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

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