第1页 / 共20页
第2页 / 共20页
第3页 / 共20页
第4页 / 共20页
第5页 / 共20页
第6页 / 共20页
第7页 / 共20页
第8页 / 共20页
Little's-Law原理与应用.pdf
Chapter 5
Little's Law
John D.C. Little and Stephen C. Graves
Massachusetts Institute of Technology
The average waiting time and the average number of items waiting for..a service
in a service system are important measurements for a manager. Little's Law
relates these two metrics via the average rate of arrivals to the system. Thisfunda-
mental law has found numerous uses in operations management and managerial
decision making.
Introduction
Caroline is a wine buff and bon vivant. She likes to stop at her local wine store,
Transcendental Tastings, on the way home from work. She browses the aisles look-
ing for the latest releases from her favorite vineyards. Occasionally she picks up a
few bottles. She stores these in a rack in a cool corner of her cellar. She and her
partner eat out frequently but when they are at home they usually split a bottle of
wine at dinner. Sometimes they have friends over and that puts a bigger ,dentin the
wine inventory.
They have been doing this for some time. Her wine rack holds 240 bottles. She
notices that she seldom fills the rack to the top but sometimes after a good party the
rack is empty. On average it seems to be about 2/3rds full, which would equate to
160 bottles.
Many wines improve with age. After reading an article about this, Caroline
starts to wonder how long, on average, she has been keeping her wines. She went
back through a few months of wine invoices from Transcendental and estimates
that she has bought, on average, about eight bottles per month. But she certainly
doesn't know when she drank which bottle and so there seems to be no way she
can find out, even approximately, the average age of the bottles she has been
drinking.
This is a good task for Little's Law.
D. Chhajed and TJ. Lowe (eds.) Building Intuition: Insights From Basic
Operations Management Models and Principles.
doi: 10.1007/978-0-387 -73699-0, <9Springer Science + Business Media, LLC 2008
81
82
J.D.C. Little, S.c. Graves
Little's Law Deals with Queuing Systems
A "queuing system" consists of discrete objects we shall call "items" that "arrive" at
some rate to the "system." Within the system the items may form one or more queues
and eventually receive "service" and exit. Figure 5.1 shows this schematically.
Arrivals -~
I
queuing system:
queue & items in service
items in 1- Departures
Flow of items through a queuing system
Fig. 5.1 Schematic view of a queuing system
While items are in the system, they may be in queues ,or may be in service or
some in queue and some in service. The interpretation will depend on the applica-
tion and the goals of the modeler. For example in the case of the wine cellar, we say
that a bottle (an "item") arrives to the system when it is first placed into the wine
cellar. Each bottle remains in the system until Caroline selects it and removes it
from the cellar for consumption. If 'we view the wine rack as a single channel
server, the service time is the time between successive removals. It is interesting to
note, however, that we do not know which bottle Caroline will pick and there is no
particular reason to believe that she will pick according to a first-in, first-out (FIFO)
rule. In any case, to deal with the average number of bottles in the cellar or average
time spent by a bottle in the cellar, we need to consider the complete system con-
sisting of queue plus service.
Little's Law says that, under steady state conditions, the average number of
items in a queuing system equals the average rate at which items arrive multiplied
by the average time that an item spends in the system. Letting
L = average number of items in the queuing system,
W = average waiting time in the system for an item, and
A =average number of items arriving per unit time, the law is
L=AW
(1)
This relationship is remarkably simple and general. We require stationarity
assumptions about the underlying stochastic processes, but it is quite surprising
what we do not require. We have not mentioned how many servers there are,
whether each server has its own queue or a single queue feeds all servers, what the
service time distributions are, or what the distribution of inter-arrival times is, or
what is the order of service of items, etc.
In good part because of its simplicity and generality, the equation (1) is
extremely useful. It is especially handy for "back of the envelope" calculations.
The reason is that two of the terms in (1) may be easy to estimate and not the third.
Then Little's Law quickly provides the missing value.
5 Little's Law
83
Thus for Caroline,
the average number of bottles in the system is L =(240)*(2/3)
= 160 bottles and the average arrival rate is A = (12)*(8) = 96 bottles/year. Without
ever collecting individual data on how long each bottle remains in her cellar, she
can calculate the average amount of time a bottle stays in her cellar as W =
== 1.67 years. That's not very old. She needs a bigger rack and more
(160)/(96)
patience, or, alternatively, she should develop selection rules to favor holding
special bottles longer than the others. This wouldn't affect the average but might
give her some fine old wines.
Arguing Little's Law with a Picture
Figure 5.2 shows one possible realization of a particular queuing system. We can
make a heuristic argument for Little's Law by interpreting the area under the curve
in Fig. 5.2 in two different ways. Let
n( t) = the number of items in the queuing system at time t;
T =a long period of time;
A(T) = the area under the curve n( t) over the time period T;
N(T) =the number of arrivals in the time period T.
On the one hand, an item in the queuing system is simply there. The number of
items can be counted at any instant of time t to give n(t). Its average value over T
is the integral of n(t) over T (i.e., A(T)) divided by T. On the other hand, at time t
each of the items is waiting and so is accumulating waiting time. By integrating n(t)
over the time period T, we obtain a cumulative measure of the waiting time, again
equal to A(T). Furthermore, the arrivals are countable too, and given by N(T).
Therefore, inspecting the figure, we define
'"
n(t)
1stdeparture
inT
Fig.5.2 Number of items in a queuing system versus time
Time period T
84
lD.C. Little, S.c. Graves
A(T) =N(T)/T =arrival rate during time period T,
L(T) =A(T)/T =average queue length during time period T,
W(T) =A(T)/N(T) =average waiting time in the system per arrival during T.
A slight manipulation gives L(T) =A(T)W(T).
All of these quantities wiggle around a little as T increases because of the sto-
chastic nature of the queuing process and because of end effects. End effects refer
to the inclusion in W(T) of some waiting by items which joined the system prior to
the start of T and the exclusion of some waiting by items who arrived during T but
have not left yet. As T increases, L(T) and A(T) go up and down somewhat as items
arrive and later leave.
Under appropriate mathematical assumptions about the stationarity of the
underlying stochastic processes,
the end effects at the start and finish of T
become negligible compared to the main area under the curve. Thus, as T
increases, these stochastic "wiggles" in L(T), A(T), and'W(T) become smaller
and smaller percentages of their eventual values so that L(T), A(T), and W(T)
each go to a limit as we increase T to infinity. Then, using the obvious symbols
for the limits, we have:
-
limL(T)= L;
T~oo
lim A(T)= A;
T~oo
lim W (T):
T~oo
from which we get the desired result (1).
It is interesting and important to note that the formula holds for each realization
of the queuing system over time. This was argued by Little, in his original paper
(Little 1961), noting that the relationship (1) held for each evolution of the time
series of a particular queuing system. In other words, if we watch a specific case or
realization designated, say, by OJ,as it develops over time, then we will find that
5 Little's Law
85
L( m) =A(m) W(my, given the steady state and other assumptions made. Averaging
cross-sectionally
system gives
(1), but it is a useful insight
to know that the formula holds for each evolving time
series as it is observed over a long time period.
across the many possible realizations of a particular
Law or Tautology?
Equation (1) is commonly called Little's Law and we have cheerfully adopted
that terminology. However, as pointed out by various people, including Little
(1992), Eq. (1) is a mathematicaltheorem and therefore a tautology.The relationship
tu'rns out to be useful in practice, but there is no need to go out on the factory
floor and collect data to test it. This would be required in the case of a physical
law such as Newton's Law of Gravitation. Each side of Newton's equation has
to be measured and it is an empirical question whether they are equal within the
measurement error. For a mathematical
theorem, if the assumptions are satis-
fied by the application,
the result will hold. Note that calling a mathematical
theorem a law is not without precedent. The Law of Large Numbers would be
another instance.
Usefulness of Little's Law in Practice
In this section we try to convey the generality of the result and its usefulness in
different contexts by means of simple examples. In each case we see how ,the
observation of two of the three measures provides the third. We try to bring out
why such back-of-the-envelope analyses are of interest and value in different
situations.
Semiconductor Factory: Semiconductor devices are manufactured in extremely
capital-intensive fabrication facilities. The manufacturing process entails starting
with a silicon wafer anti then building the electronic circuitry for multiple identical
devices through hundreds of process steps. Suppose that the semiconductor factory
starts 1,000 wafers per day, on average; this is the input rate. The start rate has'
remained fairly stable over the past 9 months. We track the amount of work-in-
process (WIP) inventory. The WIP varies between 40,000 and 50,000 wafers; the
average WIP is 45,000 wafers.
Then we can infer the average flow time in the factory. The arrival rate to the
factory is the wafer start rate: A.= 1,000 wafers per day. The WIP is the system
queue length: L =45,000 wafers. Thus the wait time or expected time in the system
is W =45 days. In a manufacturing context, we often refer to this as the flow time,
the time between when a job starts and finishes in a factory. For instance, if we
think of one wafer as being a job, then it takes the factory on average 45 days to
process it, that is, to convert it from a blank wafer into a finished wafer comprised
86
J.D.C. Little, S.C. Graves
of electronic devices. Knowing the flow time is critical for planning and schedul-
ing the factory, and for making delivery commitments to customers. We shall
return later to the connection between Little's Law and operations management.
E-Mail: Managing our e-mail is a common and,time-consuming daily activity.
For many it is hard to keep up with the volume of messages, let alone provide
timely responses. A student Sue might receive 50 messages each day to which she
must generate a response. Can we easily assess how well this student handles her
e-mail duties?
to be answered. For instance,
Indeed we can apply Little's Law to get a quick sense of how promptly Sue
responds to messages. Suppose that she receives about 50 messages every day;
then this is the arrival rate: A= 50 messages/day. Suppose we can also track how
many messages have yet
suppose that Sue
removes a message from her InBox once she has responded to it. Then the
remaining messages in her InBox are the messages that are waiting to be
answered. Over the last semester, the size of the InBox has varied between one
and two hundred messages with an average of 150 messages. Then we can
regard this to be the system queue length: L = 150 messages. From Little's Law
we immediately have an estimate of how long it takes Sue to answer a message,
on average: W = 3 days.
Hospital Ward: We wish to determine the size and staffing levels for the
maternity ward for a local hospital. From historical records we know that the
birth rate for the local community is about five births per day. We also know that
most women stay in the maternity ward for 2 days before going home with child;
however occasionally, there are complications with the birth that require much
longer stays. Over the past 6 months, we find that 90% of the births have
resulted in 2-day stays; for the remaining 10% of the cases, the average length
of time in the maternity ward is 7 days. Thus, on average, the length of stay is
0.9 x 2 + 0.1 x 7 = 2.5 days.
We can use Little's Law to predict the average number of mothers in the mater-
nity ward. The arrival process corresponds to the women arriving to deliver their
babies; the arrival rate is A = 5 mothers per day. The relevant waiting time in the
system is the length of stay in the maternity ward: W =2.5 days. Thus, the expected
queue length or number in the system is L =12.5 mothers. This would be useful in
determining the size of the maternity ward (e.g., beds) and the staffing require-
ments. However, the law only provides the average requirements, and one would
need to design the maternityward to accommodateits peak requirements.For instance,
we would certainly want more than 12.5 or 13beds in order to handle the variability
in the occupancy of the ward. One needs to use queuing models and/or simulation
to explore the trade-offs between the utilization of the beds and the likelihood of
not having a bed for an expectant mother. Nevertheless, Little's Law provides a
starting point for this investigation, since we know the average number of beds that
are needed.
TollBooths: The Ted WilliamsTunnel travels under the Boston harbor,connecting
East Boston to South Boston. During the course of a day, about 50,000 vehicles go
through the tolls at the entry point to the Tunnel in East Boston. The Massachusetts
5 Little's Law
87
Transit Authority (MTA) tries to modulate the number of toll booths that are open
at any point in time so that the average number of vehicles waiting at the tolls
(including those at the booths) never exceeds 20 vehicles. For instance, all six
booths are open during the peak time in the morning from 6:00 AM to 10:00 AM.
During this morning rush hour, the tunnel handles up to 4,000 cars per hour, and
the MTA estimates that the average number of vehicles waiting at any point of time
is near the target maximum of 20 vehicles.
With the assumption that the alTivalsoccur at a relatively stable rate over the
morning rush hour, we can then use Little's Law to ask what quality of service is
being delivered in terms of average waiting time per vehicle. Suppose that the anival
rate to the toll booths is A.=3,600 vehicles per hour (or I vehicle per second),and the
expected number of vehicles in the system is L =20 vehicles. Thus, on average, the
time a vehicle spends at the toll booths is W = 20/3,600h = 20 s.
Housing Market: The local real estate agent in your community estimates
that it takes 120 days on average to sell a house; whereas this number changes
some with the economy and season, it has been fairly stable over the past decade.
You observe from monitoring the classified ads that over the past year the
number of houses for sale has ranged from 20 to 30 at any point in time, with
an average of 25. What can we say about the number of transactions in the
past year?
From Little's Law we can estimate this by viewing the real estate market as a
queuing system. We regard a house being put up for sale as an arrival to the sys-
tem. We assume that an unsold house remains on the market until it is sold. Thus,
when a house "completes its service" and departs from the market, we infer that it
has been sold. We have estimates of the average time in the system and the average
number in the system, namely, W = 120 days and L = 25 houses. From this, we can
estimate
per year.
rate to the system, A.= 25/120
the arrival
houses
per day ==75 houses
Doughnut Shop: From your daily morning trip to the doughnut shop, you know
they have a healthy business, at least financially speaking. As you might want to
invest in a franchise, you wonder what amount of revenue they generate. Over the
course of several months; you visit the shop at random times between 6:00 AM and
9:00 AM; you observe that the queue averages about 10 customers, and that it takes
you about 3 min to get in and out of the shop.
time in the system is W = 3 min. We can then estimate
If you assume your experience is typical, then you can apply Little's Law
to estimate what.the throughput rate is for the enterprise for the morning peak
period. The expected number in the system is L = 10 customers and the
expected
the arrival
per minute = 200 customers per
rate to the system, namely A.= 10/3 customers
hour. We also term this the throughput
rate as arriving customers become
throughput once served. To get an estimate for the revenue potential from this
shop, we need to estimate how much each customer spends. If you typically
spend $5 per visit, then with the assumption that you are a typical customer,
we have a rough estimate of the shop's revenue during these morning hours,
i.e., $1,000 per hour.
88
lD.C. Little, S.C. Graves
The Robustness and Generality of Little's Law
in Certain Systems
So far we have developed and discussed Little's Law as a relationship among
steady-state stochastic processes. The contexts we have examined have been well-
behaved, stable, and on-going. In particular we assume that the characteristics of
the arrival and service processes are stationary over time. For example, in the case
of the maternity ward, we assume that the average arrival rate of mothers has been
: steady at five per day for some time, and that this rate does not vary with day of
week or season of the year. Similarly, we have regarded the service process as
, beingstationary;for instance,weread andprocessour e-mailat roughlythe same
average rate, day in and day out, independent of the backlog of unread messages.
For some of our examples, we have focused on an interval of time, e.g., the morn-
ing rush hour through the toll booths. However, in these instances due to the huge
volume of arrivals, we contend that the system behavior is virtually equivalent to
that of a steady-state system.
The purpose of this section is to show the great robustness and generality of
Little's Law under certain circumstances. Indeed Little's Law is exact in these
cases even though arrival and service process may be nonstationary. The essential
condition is to have a finite window of observation that starts and stops when
the system is empty. We use an example to motivate and illustrate the validity
of Little's Law in this situation. Consider the Sweet & Sour supermarket, which
opens every day at 7:00 AM and closes 16 h later at 11:00 PM. When S&S opens
at 7 AM, there are no customers in the store. When it closes at 11 PM, all of
the customers depart. Between opening and closing, customers arrive to the
store, do their shopping and leave. The arrivals over the course of the day are
quite varied. They include several customer segments, each with quite distinct
shopping habits. Families with school-age children will shop between 9AM and
2 PM, and tend to have fairly lengthy shopping forays as they stock up for a
week at a time. Seniors will tend to shop at quiet times of the day, like first
thing in the morning, and will also be fairly leisurely in their shopping, taking
up to an hour to complete a visit. Working couples will shop at night after work
or on the weekends; their evening visits are often to run in, grab something and
run out.
'
We propose to model S&S as a queuing system with the arrivals being the
customers as they enter the store and service being the duration of their time in
the store selecting and purchasing their groceries. However, from the above dis-
cussion, we see that this is anything but a stable system. The supermarket is never
in a steady-state. It starts and ends each day with zero customers. Over the course
of the day, customers arrive at varying rates, and the nature of their shopping trips
also varies over the day, due to the different clienteles. Nevertheless, we will
show next that Little's Law applies each and every day to this supermarket in an
exact way.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
