OU blog

Personal Blogs

Valentin Fadeev

A Small proof for Little's Formula

Visible to anyone in the world
Edited by Valentin Fadeev, Tuesday, 4 Oct 2011, 22:29

Little's formula is one of the cornerstones of the queueing theory, because it applies to a wide class of systems. It states that the number of customers in the system is the product of the average arrival rate and the mean time a customer spends in the system. Like all fundamental things it allows different proofs and interprerations. Some of them are really convincing, involving Kolmogorov-Chapman equations and related apparatus.

I will present a rather "mechanical" approach which gives the result in just three lines, but requires some preparatory discussion. We shall consider a warehouse where unitized (boxes, pallets, containers) cargo is stored. Cargo unit is a "customer" in the queue,storage time is service time.

Warehouse operator charges for (amount of cargo)X(storage time). It is reasonable to call this magnitude "warehouse work": A, (box)X(day). In a similar way "transport work" is introduced as (cargo)X(distance). Consider a limit case of a warehouse X having 1 storage place, say for 1 box, and another warehouse Y capable of storing 2 boxes at the same time.Then amount of work of 2 box-days can be performed by X in 2 days, while Y can do the same in 1 day. It is therefore natural to develop analogues with mechanics and consider capacity E as "power" of the warehouse meaning the amount of work that can be performed in a unit of time.

Now we move on to the proof. Suppose Q units of cargo are brought to the warehouse every t days. Warehouse has capacity of E units and mean dwelling T time is known based on observations. What is the condition for the system to work in a stable way, i.e. to cope with the incoming flow?

Incoming Q units will "create" warehouse work of QT box-days. The warehouse must "process" them in t days (because then the next lot is coming) having at least capacity E, that is it needs to perform work of Et box-days. The balance equation (or "law of conservation", if you like it) then looks like this:

equation left hand side cap e times t equals right hand side cap q times cap t

cap e equals cap q divided by t times cap t

But cap q divided by t equals lamda is the average daily rate of the incoming flow. Therefore:

cap e equals lamda times cap t

Which is the required result. In this interpretation it gives the minimum required capacity to put the cargo flow through the system.

 

Permalink 2 comments (latest comment by Valentin Fadeev, Saturday, 27 Mar 2010, 19:07)
Share post

This blog might contain posts that are only visible to logged-in users, or where only logged-in users can comment. If you have an account on the system, please log in for full access.

Total visits to this blog: 53628