Закон Литтла
В теории массового обслуживания, разделе теории вероятностей, законом Литтла (англ. 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].
Примечания править
- ↑ Alberto Leon-Garcia. Probability, statistics, and random processes for electrical engineering (англ.). — 3rd. — Prentice Hall, 2008. — ISBN 0-13-147122-8.
- ↑ Allen, Arnold A. Probability, Statistics, and Queueing Theory: With Computer Science Applications (англ.). — Gulf Professional Publishing, 1990. — P. 259. — ISBN 0120510510.
- ↑ Simchi-Levi, D.; Trick, M. A. Introduction to "Little's Law as Viewed on Its 50th Anniversary" (англ.) // Operations Research : journal. — 2013. — Vol. 59, no. 3. — P. 535. — doi:10.1287/opre.1110.0941.
- ↑ Serfozo, R. Little Laws // Introduction to Stochastic Networks (неопр.). — 1999. — С. 135—154. — ISBN 978-1-4612-7160-4. — doi:10.1007/978-1-4612-1482-3_5.
- ↑ Keilson, J.; Servi, L. D. A distributional form of Little's Law (англ.) // Operations Research Letters : journal. — 1988. — Vol. 7, no. 5. — P. 223. — doi:10.1016/0167-6377(88)90035-1. Архивировано 14 ноября 2017 года.
- ↑ 1 2 Little, J. D. C.; Graves, S. C. Little's Law // Building Intuition (неопр.). — 2008. — Т. 115. — С. 81. — (International Series in Operations Research & Management Science). — ISBN 978-0-387-73698-3. — doi:10.1007/978-0-387-73699-0_5. Архивировано 13 июля 2017 года.
- ↑ Cobham, Alan. Priority Assignment in Waiting Line Problems (англ.) // Operations Research. — 1954. — Vol. 2. — P. 70—76. — doi:10.1287/opre.2.1.70. — .
- ↑ Morse, Philip M. Queues, inventories, and maintenance: the analysis of operational system with variable demand and supply (англ.). — Wiley, 1958.
- ↑ Little, J. D. C. A Proof for the Queuing Formula: L = λW (англ.) // Operations Research : journal. — 1961. — Vol. 9, no. 3. — P. 383—387. — doi:10.1287/opre.9.3.383. — .
- ↑ Jewell, William S. A Simple Proof of: L=λ W (англ.) // Operations Research. — 1967. — Vol. 15, no. 6. — P. 1109—1116. — doi:10.1287/opre.15.6.1109. — .
- ↑ Eilon, Samuel. A Simpler Proof of L=λ W (англ.) // Operations Research. — 1969. — Vol. 17, no. 5. — P. 915—917. — doi:10.1287/opre.17.5.915. — .
- ↑ Stidham Jr., Shaler. A Last Word on L = λW (англ.) // Operations Research. — 1974. — Vol. 22, no. 2. — P. 417—421. — doi:10.1287/opre.22.2.417. — .
- ↑ Stidham Jr., Shaler. L = λW: A Discounted Analogue and a New Proof (англ.) // Operations Research. — 1972. — Vol. 20, no. 6. — P. 1115—1120. — doi:10.1287/opre.20.6.1115. — .