В теории массового обслуживания, разделе теории вероятностей, законом Литтла (англ. Little's law, также результатом, леммой, формулой Литтла[1][2]) называют сформулированную американским учёным Джоном Литтлом теорему:

Долгосрочное среднее количество L заявок в стационарной системе равно долгосрочной средней интенсивности λ входного потока, умноженной на среднее время W пребывания заявки в системе. Алгебраически,  L = λW.

Иными словами, при заданной интенсивности входного потока время в системе пропорционально количеству заявок в системе. Хотя результат и выглядит интуитивно понятным, он замечателен, так как выраженная связь не опосредована распределением поступления, распределением обслуживания, порядком обслуживания или другими посторонними характеристиками[3].

Закон применим к любым системам, в частности, к подсистемам[4]. Например, очередь клиентов в банке может быть одной подсистемой, а каждый из кассиров — другой. Закон Литтла применим как к каждой из подсистем, так и ко всей системе в целом. От системы требуется лишь стационарность и отсутствие вытесняющей многозадачности. Наличие этих свойств исключает переходные состояния, в том числе запуск и остановку.

В некоторых случаях мы можем не только математически соотнести не только средние количество и ожидание, но и их целые распределения (с моментами)[5].

В статье от 1954 года закон Литтла приведён как само собой разумеющийся, доказательство отсутствовало[6][7]. Формула L = λW впервые опубликована Филипом М. Морсом, который предложил читателям найти ситуацию, в которой отношение бы не выполнялось[6][8]. В 1961 году Литтл предложил своё доказательство, тем самым продемонстрировав, что таких ситуаций не существует[9]. Затем более простые доказательства опубликовали Джуэлл[10] и Филон[11]. Ещё одно более интуитивное доказательство вышло из-под пера Стидема в 1972 году[12][13].

ПримечанияПравить

  1. Alberto Leon-Garcia. Probability, statistics, and random processes for electrical engineering. — 3rd. — Prentice Hall, 2008. — ISBN 0-13-147122-8.
  2. Allen Arnold A. Probability, Statistics, and Queueing Theory: With Computer Science Applications. — Gulf Professional Publishing, 1990. — P. 259. — ISBN 0120510510.
  3. (2013) «Introduction to "Little's Law as Viewed on Its 50th Anniversary"». Operations Research 59 (3): 535. DOI:10.1287/opre.1110.0941.
  4. Little Laws // Introduction to Stochastic Networks. — 1999. — P. 135–154. — ISBN 978-1-4612-7160-4.
  5. (1988) «A distributional form of Little's Law». Operations Research Letters 7 (5): 223. DOI:10.1016/0167-6377(88)90035-1.
  6. 1 2 Little's Law // Building Intuition. — 2008. — Vol. 115. — P. 81. — ISBN 978-0-387-73698-3.
  7. (1954) «Priority Assignment in Waiting Line Problems». Operations Research 2: 70–76. DOI:10.1287/opre.2.1.70.
  8. Morse Philip M. Queues, inventories, and maintenance: the analysis of operational system with variable demand and supply. — Wiley, 1958.
  9. (1961) «A Proof for the Queuing Formula: L = λW». Operations Research 9 (3): 383–387. DOI:10.1287/opre.9.3.383.
  10. Jewell, William S. (1967). «A Simple Proof of: L=λ W». Operations Research 15 (6): 1109-1116. DOI:10.1287/opre.15.6.1109.
  11. Eilon, Samuel (1969). «A Simpler Proof of L=λ W». Operations Research 17 (5): 915-917. DOI:10.1287/opre.17.5.915.
  12. (1974) «A Last Word on L = λW». Operations Research 22 (2): 417–421. DOI:10.1287/opre.22.2.417.
  13. (1972) «L = λW: A Discounted Analogue and a New Proof». Operations Research 20 (6): 1115–1120. DOI:10.1287/opre.20.6.1115.