Закон Литтла

Закон Литтла — фундаментальная теорема теории массового обслуживания (теории очередей) и исследования операций, устанавливающая связь между средним числом объектов в системе, средней интенсивностью их поступления и средним временем пребывания объекта в системе. В стандартной форме закон записывается как $L=\lambda W$, где $L$ — среднее число требований (клиентов, заявок, изделий) в системе, $\lambda$ — средняя эффективная интенсивность поступления требований в систему (единиц в единицу времени), $W$ — среднее время пребывания требования в системе. Теорема не зависит от распределений интервалов между прибытиями и времён обслуживания, дисциплины обслуживания (FIFO, LIFO, приоритетная и др.), числа каналов обслуживания и других деталей структуры системы при условии существования и конечности соответствующих средних величин.

Несмотря на название, речь идёт не об эмпирическом «законе» в физическом смысле, а о строго доказанной математической теореме. Ключевая особенность результата состоит в его модельной общности: базовое равенство не зависит от конкретных распределений, числа каналов обслуживания или дисциплины обслуживания; критично лишь то, чтобы долгосрочные средние были корректно определены и конечны.

Формулировка

Закон Литтла выражается формулой:

$L=\lambda W$

где:

• $L$ — среднее число объектов (требований, клиентов, заявок, изделий) в системе, включая очередь и обслуживание;
• $\lambda$ — средняя эффективная интенсивность поступления объектов в систему (единиц в единицу времени);
• $W$ — среднее время пребывания одного объекта в системе (от поступления до выхода).

Формула справедлива для любой системы, в которой элементы прибывают, проводят некоторое время (в очереди и/или на обслуживании) и покидают систему. Закон применим к подсистемам внутри более крупных систем, а также к сетям очередей.

В производственном контексте закон часто переформулируют как:

$\text{TH}=\frac{\text{WIP}}{\text{CT}}$

где TH — пропускная способность (throughput), WIP — незавершённое производство (work-in-process), CT — время цикла (cycle time).

В демографии и биологии популяций используется эквивалентная форма: $P=B\times e$, где $P$ — размер популяции, $B$ — рождаемость, $e$ — ожидаемая продолжительность жизни.

История и предпосылки

Отдельные случаи соотношения $L=\lambda W$ (или эквивалентных форм) фиксировались в литературе по теории очередей с 1950-х годов без строгого доказательства. В 1954 году А. Кобхэм (A. Cobham) использовал соотношение как очевидное в работе по приоритетным очередям. В 1958 году Ф. М. Морс (P. M. Morse) в книге «Queues, Inventories and Maintenance» явно записал формулу $L=\lambda W$ и предложил читателям найти ситуацию, в которой она не выполняется.

Первое общее доказательство опубликовал Джон Д. К. Литтл (John D. C. Little) в 1961 году в статье «A Proof for the Queuing Formula: L = λW» в журнале Operations Research (том 9, № 3, с. 383–387). Доказательство опиралось на предположения строгой стационарности процессов и метрической транзитивности (эргодичности) входного потока.

Впоследствии появились более простые доказательства:

• У. С. Джуэлл (W. S. Jewell, 1967) — доказательство на основе теории восстановления;
• С. Эйлон (S. Eilon, 1969) — компактное доказательство без явных предположений о распределениях, числе серверов или дисциплине обслуживания;
• Ш. Стидхэм (S. Stidham, 1972, 1974) — интуитивные sample-path доказательства (анализ траекторий), показавшие большую общность закона без строгой стационарности; требуется лишь существование и конечность предельных средних.

В 2011 году Литтл опубликовал обзор к 50-летию теоремы, обобщив теоретические и практические разработки.

Теоретические основы

Формальное утверждение

Пусть $L(t)$ — число элементов в системе в момент времени $t$, $N(T)$ — число прибытий за интервал $[0,T]$, $W_i$ — время пребывания $i$-го элемента в системе. Тогда определяются три средние величины:

$L=\underset{T\to \mathrm{\infty }}{\lim }\frac{1}{T}\underset{0}{\overset{T}{\int }}L(t)dt$ (среднее по времени),

$\lambda =\underset{T\to \mathrm{\infty }}{\lim }\frac{N(T)}{T}$ (средняя интенсивность прибытия),

$W=\underset{n\to \mathrm{\infty }}{\lim }\frac{1}{n}\sum _{i=1}^n{W}_i$ (среднее время пребывания).

Теорема утверждает: если $\lambda$ и $W$ существуют и конечны, то существует $L$ и выполняется $L=\lambda W$.

Геометрическая интерпретация

Площадь под кривой $L(t)$ за большой интервал $T$ равна суммарному времени пребывания всех элементов, что даёт $L\cdot T\approx \lambda \cdot T\cdot W$. При $T\to \mathrm{\infty }$ и пренебрежимо малых краевых эффектах (система пуста в начале и конце или эффекты исчезают) получается точное равенство.

Траекторная (sample-path) формулировка

В траекторной формулировке рассматривается одна реализация очередного процесса без явного указания вероятностного пространства. Пусть $t_n$ — моменты поступления клиентов, $W_n$ — их времена пребывания, $t_n^d=t_n+W_n$ — моменты ухода. Доказательство основано на оценке площади под траекторией $L(s)$ через суммы времён пребывания:

$\sum _{j:t_j^d\le t}{W}_j\le \underset{0}{\overset{t}{\int }}L(s)ds\le \sum _{j:t_j\le t}{W}_j$

и последующем переходе к пределу $t\to \mathrm{\infty }$. Этот подход позволяет формулировать закон Литтла без глобальных предположений о стационарности, при условии существования соответствующих пределов.

Частные формы

Закон Литтла имеет ряд стандартных частных форм в зависимости от выбора границ системы:

• Для очереди (зоны ожидания): $L_q=\lambda W_q$, где $L_q$ — среднее число ожидающих, $W_q$ — среднее время ожидания до начала обслуживания.
• Для обслуживающего устройства (серверов): $L_s={\lambda }_{s}S$, где $L_s$ — среднее число одновременно обслуживаемых клиентов, $S$ — среднее время обслуживания.
• Для закрытых интерактивных систем: $N=X(R+Z)$, где $N$ — число пользователей, $R$ — время отклика, $Z$ — время «размышления» пользователя.

При смене определения системы меняются значения $L$, $\lambda$ и $W$, но остаётся справедливым их произведение $L=\lambda W$.

Обобщения

• $H=\lambda G$ (Brumelle, 1971; Heyman, Stidham, 1980) — обобщение, где $H$ — время-среднее некоторой функции (например, работы, стоимости), $G$ — среднее значение этой функции по элементам. Закон Литтла — частный случай при функции, равной 1.
• Distributional Little's law (Keilson, Servi, 1988; Bertsimas, Nakazato, 1995) — связь распределений числа элементов и времени пребывания. При условиях FIFO, стационарности и независимости распределение числа элементов в системе совпадает с распределением числа поступлений за случайное время $W$.
• Применимость к подсистемам, классам элементов и сетям очередей (в том числе сетям Джексона) при соответствующих условиях балансировки потоков.

Условия применимости

Для корректного применения закона Литтла необходимо соблюдение следующих условий:

• Стационарность или существование стационарных средних: процессы числа требований, интервалов поступления и времён пребывания либо строго стационарны, либо соответствующие средние по времени и по выборке существуют и конечны.
• Сохранение потока: каждый элемент, входящий в систему, в конечном итоге покидает её; граница между системой и внешней средой корректно определена.
• Ненулевая конечная интенсивность $\lambda$: поток поступления устоялся и имеет конечную плотность во времени.

Отсутствие предположений о распределениях интервалов и времён обслуживания, а также о дисциплине обслуживания отличает закон Литтла от многих других результатов классической теории очередей.

Методология применения

Закон применяется путём измерения любых двух из трёх величин ($L$, $\lambda$, $W$) и вычисления третьей. Система может быть любой (очередь, производство, сеть, популяция), если определены «поступление», «пребывание» и «система» согласованно.

Практическое применение начинается не с подстановки в формулу, а с выбора границ системы и согласованного определения трёх величин. Несогласованность определений — главный источник методологических ошибок.

Для конечного интервала наблюдения $[0,T]$ существуют точные версии:

• Если система пуста в моменты $0$ и $T$, то $L(T)=\lambda (T)\cdot W(T)$ строго.
• В общем случае вводится корректировка на элементы, присутствовавшие в начале или оставшиеся в конце.

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

Эмпирические данные и примеры

Примеры применения закона Литтла

Область	Система	$\lambda$ (поступление)	$W$ (время пребывания)	$L$ (среднее число)	Условия	Источник
Производство	Полупроводниковый завод	1 000 пластин/день	45 дней	45 000 пластин	Стационарный режим, 9 месяцев наблюдений	Little, Graves (2008)
Здравоохранение	Отделение неотложной помощи	10 пациентов/ч (целевое)	3 часа	30 пациентов	Целевое время пребывания; 4 врача + буфер 10–20 %	Harris (2010)
Здравоохранение	Отделение наблюдения в больнице	55,4 пациентов/день (20 % на наблюдение)	1,14 дня	≈14 коек (утилизация 90 %)	Стационарный поток	Lovejoy, Desmond (2011)
Производство	Проект разработки нефтяных скважин	0,274 скважины/день	240 дней	66 скважин	Долгосрочные средние	Project Production Institute
Виноделие	Винный погреб	96 бутылок/год	1,67 года	160 бутылок	Ёмкость 240, заполнение 2/3	Little, Graves (2008)
Общепит	Кофейня	20 человек/ч	0,25 часа (15 мин)	5 человек	Стабильный режим	Иллюстративный пример
IT-системы	Обработка запросов к серверу	50 запросов/с	0,2 секунды	10 запросов	Средняя глубина очереди + обслуживание	Lazowska et al. (1984)

Применение

Производство и операционный менеджмент

Закон Литтла служит базовым инструментом для связи WIP, пропускной способности (throughput) и времени цикла (lead time) в бережливом производстве (Lean), системах Kanban и CONWIP. Ограничение WIP при фиксированной пропускной способности снижает время цикла, что является одним из ключевых принципов Lean-менеджмента.

Компьютерные системы и телекоммуникации

В вычислительных системах закон Литтла используется для анализа задержки (latency), планирования параллелизма (concurrency), проектирования кэш-иерархий и масштабирования серверов. Среднее число запросов $L$ и пропускная способность $\lambda$ позволяют вычислить время отклика $W=L/\lambda$. Закон применяется при нагрузочном тестировании веб-приложений для проверки согласованности измеренных метрик.

Здравоохранение

Закон Литтла применяется для планирования кадрового состава (staffing) в отделениях неотложной помощи, определения необходимого числа коек в отделениях наблюдения (observation units), а также для анализа потока пациентов. В типичных исследованиях используются данные за длительный период (от нескольких недель до месяцев), чтобы обеспечить приближение к стационарному режиму.

Демография и биология

В демографии и экологии закон Литтла применяется в форме $P=B\times e$: размер стационарной популяции равен произведению рождаемости на ожидаемую продолжительность жизни (при однородной популяции без миграции).

Управление проектами и разработка ПО

В системах Kanban и Agile-методологиях закон Литтла используется для оценки среднего времени выполнения задач (lead time) при известном количестве активных задач (WIP) и среднем темпе выполнения (throughput). Ограничение числа задач в работе (WIP-лимит) позволяет снижать время выполнения без увеличения пропускной способности.

Логистика и розничная торговля

В логистике и складских системах $L$ интерпретируется как число единиц товара в системе, $\lambda$ — интенсивность входа/выхода грузов, $W$ — среднее время нахождения груза от приёмки до отгрузки. Закон используется при анализе оборота запасов и проектировании складских мощностей.

Ограничения и открытые проблемы

• Требование стационарности. При ярко выраженной транзиентной динамике (запуск или остановка системы, резкие изменения нагрузки) закон в прямой форме $L=\lambda W$ может не описывать краткосрочное поведение.
• Только для средних. Базовая форма не даёт квантилей, хвостовых вероятностей, дисперсий; для описания распределений требуются дополнительные модели (например, M/M/1, GI/G/1) либо distributional Little's law.
• Эффективная интенсивность. В системах с блокировками или потерями необходимо использовать эффективную $\lambda$ (только присоединившиеся элементы), а не номинальную интенсивность внешнего потока.
• Краевые эффекты. Для конечных интервалов измерений необходимы коррекции; рекомендуется метод batch means и построение доверительных интервалов.
• Определение системы. Неправильное определение «системы» или «прибытия» приводит к кажущимся нарушениям закона.

Открытые вопросы: статистическая оценка параметров из конечных данных, применение к сильно нестационарным системам, time-varying версии закона Литтла, интеграция с моделями вариабельности и overhead.

Перспективы и направления исследований

Обзоры (Little, 2011; Whitt, 1991) выделяют несколько направлений развития:

• Конечновременные и статистические версии для реальных журналов событий, включая построение доверительных интервалов и коррекцию смещения.
• Time-varying Little's Law для нестационарных сервисных систем.
• Взвешенные формы $H=\lambda G$ для экономических метрик (стоимость, запасы работы, риск).
• Распределительные формы (distributional Little's law), связывающие не только средние, но и распределения.
• Интеграция с big-data мониторингом реального времени и машинным обучением для прогнозирования в цепочках поставок и облачных вычислениях.
• Применение в сложных сетях и биологических системах, включая модели экспрессии генов и экологические системы.

Хронология ключевых работ

Хронология развития закона Литтла

Год	Автор(ы)	Вклад
1954	A. Cobham	Использование соотношения $L=\lambda W$ без доказательства в работе по приоритетным очередям
1958	P. M. Morse	Явная публикация формулы $L=\lambda W$ в книге «Queues, Inventories and Maintenance»
1961	J. D. C. Little	Первое строгое доказательство общей теоремы в журнале Operations Research
1967	W. S. Jewell	Упрощённое доказательство на основе теории восстановления
1969	S. Eilon	Компактное доказательство без предположений о распределениях и числе серверов
1971	S. Brumelle	Обобщение $H=\lambda G$ для взвешенных функций
1972–1974	S. Stidham	Траекторное (sample-path) доказательство без вероятностных предпосылок
1988	J. Keilson, L. Servi	Distributional Little's law — связь распределений
1991	W. Whitt	Обзор $L=\lambda W$ и расширений
1995	D. Bertsimas, D. Nakazato	Distributional Little's law и его приложения
2008	J. D. C. Little, S. C. Graves	Обзорная глава с практическими примерами
2011	J. D. C. Little	Обзор к 50-летию теоремы
2013	S.-H. Kim, W. Whitt	Статистический анализ с законом Литтла; конечновременные оценки

Литература

• Little, J. D. C. (1961). A Proof for the Queuing Formula: L = λW. Operations Research, 9(3), 383–387. DOI: 10.1287/opre.9.3.383.
• Little, J. D. C. (2011). Little's Law as Viewed on Its 50th Anniversary. Operations Research, 59(3), 536–549. DOI: 10.1287/opre.1110.0940.
• Little, J. D. C.; Graves, S. C. (2008). Little's Law. In: Building Intuition, Springer, pp. 81–100. DOI: 10.1007/978-0-387-73699-0_5.
• Stidham, S. Jr. (1974). A Last Word on L = λW. Operations Research, 22(2), 417–421. DOI: 10.1287/opre.22.2.417.
• Jewell, W. S. (1967). A Simple Proof of: L = λW. Operations Research, 15(6), 1109–1116. DOI: 10.1287/opre.15.6.1109.
• Eilon, S. (1969). A Simpler Proof of L = λW. Operations Research, 17(5), 915–917. DOI: 10.1287/opre.17.5.915.
• Whitt, W. (1991). A Review of L = λW and Extensions. Queueing Systems, 9, 235–268. DOI: 10.1007/BF01158466.
• Keilson, J.; Servi, L. D. (1988). A Distributional Form of Little's Law. Operations Research Letters, 7(5), 223–227. DOI: 10.1016/0167-6377(88)90035-1.
• Bertsimas, D.; Nakazato, D. (1995). The Distributional Little's Law and Its Applications. Operations Research, 43(2), 298–310. DOI: 10.1287/opre.43.2.298.
• Kim, S.-H.; Whitt, W. (2013). Statistical Analysis with Little's Law. Operations Research, 61(4), 1030–1045. DOI: 10.1287/opre.2013.1193.
• Hopp, W. J.; Spearman, M. L. (2011). Factory Physics. 3rd ed. Waveland Press.
• Lovejoy, W. S.; Desmond, J. S. (2011). Little's Law Flow Analysis of Observation Unit Impact and Sizing. Academic Emergency Medicine, 18(2), 183–189. DOI: 10.1111/j.1553-2712.2010.00969.x.
• El-Taha, M.; Stidham, S. Jr. (1999). Sample-Path Analysis of Queueing Systems. Springer. DOI: 10.1007/978-1-4615-5111-9.
• Morse, P. M. (1958). Queues, Inventories and Maintenance. John Wiley & Sons.
• Cobham, A. (1954). Priority Assignment in Waiting Line Problems. Operations Research, 2(1), 70–76.
• Lazowska, E. D. et al. (1984). Quantitative System Performance: Computer System Analysis Using Queueing Network Models. Prentice-Hall.

Ссылки

• Little's law — Wikipedia (EN)
• Sigman K. Notes on Little's Law — Columbia University
• Little's Law as Viewed on Its 50th Anniversary — PDF