В теории массового обслуживания - дисциплина в рамках математической теории вероятностей , результат , теорема , лемма , закон или формула Литтла [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]
Смотрите также
- Список одноименных законов (законы, пословицы и другие краткие наблюдения или предсказания, названные в честь лиц)
Заметки
- ↑ Альберто Леон-Гарсия (2008). Вероятность, статистика и случайные процессы для электротехники (3-е изд.). Прентис Холл. ISBN 978-0-13-147122-1.
- ^ Аллен, Арнольд А. (1990). Теория вероятностей, статистики и массового обслуживания: с приложениями компьютерных наук . Издательство Gulf Professional Publishing. п. 259 . ISBN 0120510510.
- ^ Simchi-Levi, D .; Уловка, Массачусетс (2013). «Введение в« Закон Литтла в свете его 50-летия » ». Исследование операций . 59 (3): 535. DOI : 10,1287 / opre.1110.0941 .
- ^ Серфозо Р. (1999). «Маленькие законы». Введение в стохастические сети . стр. 135 -154. DOI : 10.1007 / 978-1-4612-1482-3_5 . ISBN 978-1-4612-7160-4.
- ^ Кейлсон, Дж .; Серви, LD (1988). «Распределительная форма закона Литтла» (PDF) . Письма об исследованиях операций . 7 (5): 223. DOI : 10,1016 / 0167-6377 (88) 90035-1 . ЛВП : 1721,1 / 5305 .
- ^ а б Литтл, Джойнт ; Graves, SC (2008). «Закон Литтла» (PDF) . Развитие интуиции . Международная серия исследований операций и управления. 115 . п. 81. DOI : 10.1007 / 978-0-387-73699-0_5 . ISBN 978-0-387-73698-3.
- ^ Кобэм, Алан (1954). «Распределение приоритетов при проблемах в очереди». Исследование операций . 2 (1): 70–76. DOI : 10.1287 / opre.2.1.70 . JSTOR 166539 .
- ^ Морс, Филип М. (1958). Очереди, запасы и обслуживание: анализ операционной системы с переменным спросом и предложением . Вайли.
- ^ Литтл, JDC (1961). «Доказательство формулы массового обслуживания: L = λW ». Исследование операций . 9 (3): 383–387. DOI : 10.1287 / opre.9.3.383 . JSTOR 167570 .
- ^ Джуэлл, Уильям С. (1967). «Простое доказательство: L = λW ». Исследование операций . 15 (6): 1109–1116. DOI : 10.1287 / opre.15.6.1109 . JSTOR 168616 .
- ^ Эйлон, Самуэль (1969). «Более простое доказательство L = λW » . Исследование операций . 17 (5): 915–917. DOI : 10.1287 / opre.17.5.915 . JSTOR 168368 .
- ^ Стидхам младший, Шалер (1974). «Последнее слово о L = λW » . Исследование операций . 22 (2): 417–421. DOI : 10.1287 / opre.22.2.417 . JSTOR 169601 .
- ^ Стидхам младший, Шалер (1972). « L = λW : дисконтированный аналог и новое доказательство». Исследование операций . 20 (6): 1115–1120. DOI : 10.1287 / opre.20.6.1115 . JSTOR 169301 .
- ^ Kim, SH; Уитт, В. (2013). «Статистический анализ с законом Литтла» (PDF) . Исследование операций . 61 (4): 1030. DOI : 10,1287 / opre.2013.1193 .
- ^ Коррелл, Николаус (13 июня 2021 г.). «Срок изготовления» . Проверено 12 июня 2021 года .
- ^ Узкие места инфраструктуры программного обеспечения в J2EE, Дипак Гоэль
- ^ Сравнительный анализ грубых ошибок и вещей, которые происходят ночью, Нил Гюнтер
- ^ Литтл, JDC (2011). "Закон Литтла в свете его 50-летия" (PDF) . Исследование операций . 59 (3): 536–549. DOI : 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 , Сигман К., Колумбийский университет.