Закон Литтла: различия между версиями
Киберрыба (обсуждение | вклад) ← Новая страница: «В теории массового обслуживания, разделе Тео…» |
(нет различий)
|
Версия от 14:41, 25 мая 2017
В теории массового обслуживания, разделе теории вероятностей, законом Литтла (англ. 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. (2013). "Introduction to "Little's Law as Viewed on Its 50th Anniversary"". Operations Research. 59 (3): 535. doi:10.1287/opre.1110.0941.
{{cite journal}}: Шаблон цитирования имеет пустые неизвестные параметры:|1=(справка) - ↑ Serfozo, R. Little Laws // Introduction to Stochastic Networks. — 1999. — P. 135–154. — ISBN 978-1-4612-7160-4. — doi:10.1007/978-1-4612-1482-3_5.
- ↑ Keilson, J.; Servi, L. D. (1988). "A distributional form of Little's Law". Operations Research Letters. 7 (5): 223. doi:10.1016/0167-6377(88)90035-1.
- ↑ 1 2 Little, J. D. C. Little's Law // Building Intuition / J. D. C. Little, S. C. Graves. — 2008. — Vol. 115. — P. 81. — ISBN 978-0-387-73698-3. — doi:10.1007/978-0-387-73699-0_5.
- ↑ Cobham, Alan (1954). "Priority Assignment in Waiting Line Problems". Operations Research. 2: 70—76. doi:10.1287/opre.2.1.70. JSTOR 166539.
- ↑ Morse, Philip M. Queues, inventories, and maintenance: the analysis of operational system with variable demand and supply. — Wiley, 1958.
- ↑ 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. JSTOR 167570.
- ↑ Jewell, William S. (1967). "A Simple Proof of: L=λ W". Operations Research. 15 (6): 1109–1116. doi:10.1287/opre.15.6.1109. JSTOR 168616.
- ↑ Eilon, Samuel (1969). "A Simpler Proof of L=λ W". Operations Research. 17 (5): 915–917. doi:10.1287/opre.17.5.915. JSTOR 168368.
- ↑ Stidham Jr., Shaler (1974). "A Last Word on L = λW". Operations Research. 22 (2): 417—421. doi:10.1287/opre.22.2.417. JSTOR 169601.
- ↑ Stidham Jr., Shaler (1972). "L = λW: A Discounted Analogue and a New Proof". Operations Research. 20 (6): 1115—1120. doi:10.1287/opre.20.6.1115. JSTOR 169301.