Queue Length From Arrival And Service Rates

Why Queue Length Needs a Constraint

A queue grows when work arrives faster than it can be served and shrinks when service capacity exceeds arrivals. A first calculation might subtract the service rate from the arrival rate and integrate the result. That works only while the queue is positive. If the queue empties, service cannot remove jobs that are not there.

We will use a fluid model: the queue length is allowed to be a nonnegative real number, rather than only a whole number. This approximation is useful when describing aggregate flow over time. It also makes the rate balance explicit. A prediction from the balance must still satisfy the physical condition that the queue cannot be negative.

Rates and the Queue Balance

Let \(q(t)\) be the amount of work waiting in the queue at time \(t\), measured in jobs. Let \(\lambda(t)\) be the arrival rate and \(\mu(t)\) the service capacity, both measured in jobs per unit time. The actual departure rate may be less than the capacity: if the queue is empty and arrivals are slow, the system cannot serve jobs that have not arrived.

Write \(d(t)\) for the actual departure rate. The conservation balance is that the change in queue equals arrivals minus departures. Thus, wherever the rates and derivative are defined,

When the queue is positive, \(d(t)=\mu(t)\), so \(q'(t)=\lambda(t)-\mu(t)\). At an empty queue, actual departures are limited to the available arrivals: \(d(t)=\min\{\lambda(t),\mu(t)\}\). Consequently, the rate of change can be written as

This is a work-conserving model: available service capacity is used whenever there is work to serve. The formula at \(q(t)=0\) prevents the queue from decreasing below zero. If arrivals exceed capacity at an empty queue, the excess starts to build a queue. If capacity exceeds arrivals, all arrivals can be served immediately, and the queue stays empty.

Using Net Rates While the Queue Is Positive

On an interval where the queue remains positive, the queue change is the integral of the net rate \(\lambda(t)-\mu(t)\). If the rates are constant on an interval of length \(T\), this reduces to multiplying the net rate by \(T\). A positive net rate means buildup; a negative net rate means reduction. These conclusions apply only as long as the queue does not empty during the interval.

When rates change over time, the same balance uses an integral rather than a single rate multiplied by a duration. As long as \(q(t)>0\) throughout the interval from \(a\) to \(b\),

The condition that the queue stays positive matters. If this expression predicts a negative queue at some time, the unrestricted balance has been used beyond its valid interval and must be corrected at the point the queue empties.

What Changes When the Queue Empties?

If the queue reaches zero, one must stop subtracting the full service capacity from arrivals. After that point, some capacity may be unused. The queue stays at zero for as long as capacity is at least as large as the arrival rate. If arrivals later exceed capacity, the queue starts to grow again.

For constant rates with \(\mu>\lambda\) and a positive initial queue \(q_0\), the net reduction rate is \(\mu-\lambda\). If that rate continues, the queue empties after \(q_0/(\mu-\lambda)\) units of time. This calculation identifies when the positive-queue balance stops applying. The queue cannot be allowed to continue decreasing after that time.

A General Nonnegative Queue Formula

There is a concise way to describe the correction for time-varying rates. Suppose the rates are integrable and the initial queue is \(q_0\ge 0\). First calculate the queue that would result if the full capacity were always used, even when no work remained. Call this unrestricted balance \(x(t)\):

This balance may become negative, so it is not always a physically valid queue. Define the cumulative unused capacity needed to keep it nonnegative by

Then the constrained queue is \(q(t)=x(t)+L(t)\). The correction \(L(t)\) is nondecreasing: once capacity has gone unused, its cumulative total cannot decrease. It grows only as needed to offset a negative unrestricted balance. In the fluid queue, this corresponds to capacity that cannot be used because the queue is empty.

To justify the formula, first observe that for every \(s\le t\), \(L(t)\ge -x(s)\), and \(L(t)\ge0\). In particular, taking \(s=t\) gives \(x(t)+L(t)\ge0\), so the proposed queue never becomes negative. The supremum records the largest deficit encountered up to time \(t\); if that deficit increases, the correction increases just enough to offset it. This increase can occur only when \(x(t)+L(t)=0\), because a new largest deficit means \(L(t)=-x(t)\).

For minimality, let \(R(t)\) be any nondecreasing correction with \(R(t)\ge0\) and \(x(s)+R(s)\ge0\) for all \(s\). Then \(R(s)\ge -x(s)\) at every \(s\), and monotonicity gives \(R(t)\ge R(s)\) whenever \(s\le t\). Therefore \(R(t)\) is at least every value \(-x(s)\) for \(s\le t\), and it is also at least zero. It follows that \(R(t)\ge L(t)\). Thus \(L\) is the smallest cumulative correction that keeps the queue nonnegative. In queue terms, it is precisely the amount of service capacity left unused to avoid serving nonexistent work.

A Common Mistake: Subtracting Capacity After Emptying

A frequent error is to apply \(q_0+(\lambda-\mu)T\) over an entire interval without checking whether the queue stays positive. For the one-hour example above, that calculation gives

This result is impossible: it violates \(q(t)\ge0\). The rate calculation is valid only until the queue empties, which occurs after \(2/3\) hour. After that, actual departures equal arrivals at \(1\) job per hour, rather than continuing at the \(4\)-job-per-hour capacity. The corrected ending queue is zero, with \(1\) job of unused capacity over the hour.

Another way to catch this mistake is to check conservation using actual departures, not capacity. Capacity is a maximum possible departure rate; it is not necessarily the number of jobs served when the queue empties during the interval.

Practical Checks for a Queue Model

Before accepting a queue prediction, check the following:

• Units: Rates have units such as jobs per hour; integrating a rate over hours gives jobs.
• Sign: A positive arrival-minus-capacity rate grows a positive queue; a negative one reduces it.
• Empty intervals: Once the queue reaches zero, do not subtract unused capacity from it.
• Conservation: Ending queue equals starting queue plus arrivals minus actual departures.
• Nonnegativity: Every predicted queue length must be at least zero.

These checks distinguish a meaningful queue model from an unrestricted rate calculation. The key idea is to use the net rate while work is waiting, then respect the boundary at zero when no work remains.