Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 38 · Finite Capacity and Priorities

The Machine Repair Problem: Finite Source Queues

Model N machines that break down and are fixed by repair crews: the finite-source queue, its state probabilities, throughput, and how many repairers to hire.

So far arrivals came from an endless crowd, so the arrival rate never depended on how many people were already in the system. Many real systems are different. A factory has N machines. Each working machine breaks down at some rate, and every machine that is already broken cannot break again. The more machines are in the repair queue, the fewer machines remain to generate new breakdowns. The arrival rate falls as the queue grows.

This is the machine repair problem, also called a finite-source or closed queue. Computer labs, taxi fleets, and a set of N terminals sending requests to one server all follow the same model.

The model

  • N machines, each either up (working) or down (waiting or being repaired).
  • Each working machine fails after an exponential time with rate λ (mean 1/λ).
  • There are s repairers; each repairs one machine at exponential rate μ.
  • Let n be the number of machines down. Then the failure rate of the whole fleet is (N - n)λ, and the repair rate is min(n, s) μ.

This is a birth-death chain on 0..N. For a single repairer (s = 1) the balance equations give:

Text
p_n ∝ N! / (N - n)! · (λ/μ)^n

Normalize so the probabilities sum to 1. For several repairers, use birth = (N - n)λ and death = min(n, s)μ, and the general rule p_n = p_0 · Π (birth_{k-1} / death_k).

Python Machine repair solver for any number of repairers

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each row reports the average number of broken machines, the average number working, and the long-run rate at which machines are repaired. The last column is the fraction of time at least one repairer is idle, which is the probability that fewer than s machines are down.

Little's Law in a closed system

Little's Law still applies. The rate at which machines enter repair is the throughput X = λ · (mean number up), and the mean number down is L = X · W, where W is the mean time a machine spends down (waiting plus repair). So:

Text
W = L / X,   mean number up = N - L,   X = λ (N - L)

For s = 1 there is also a neat identity: the repairer is busy a fraction 1 - p_0 of the time and completes μ(1 - p_0) repairs per unit time, so X = μ(1 - p_0).

Python Check Little's Law and the single-repairer identity

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two throughput numbers agree, which confirms the model is balanced.

How many repairers?

Each extra repairer costs wages, but each broken machine costs lost production. Define a cost per repairer per hour c_r and a cost per down-machine per hour c_d. Total cost is c_r · s + c_d · L(s). Because L(s) decreases with diminishing returns, the cost curve has a minimum. Compute L(s) for s = 1, 2, ... and pick the best s.

Do not model a small fleet with the infinite-source M/M/s formulas. If N is small, treating arrivals as Poisson with rate Nλ overstates the queue, because it ignores that broken machines cannot break again.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In the machine repair model with n machines down, what is the total failure rate?

    Only the N - n working machines can fail, each at rate λ.
  2. 2. With one repairer, the throughput equals

    The repairer is busy with probability 1 - p_0 and completes repairs at rate μ while busy.
  3. 3. Why is the finite-source model different from M/M/1?

    Machines in repair cannot fail again, so the arrival rate falls as the queue grows.
  4. 4. For N = 3, λ/μ = 1 and one repairer, the weights p_n ∝ N!/(N-n)! (λ/μ)^n for n = 0..3 are

    3!/3! = 1, 3!/2! = 3, 3!/1! = 6, 3!/0! = 6.

Summary

  • A finite-source queue has N customers; arrivals come from those not already in the system.
  • Birth rate (N - n)λ, death rate min(n, s)μ.
  • Little's Law holds: L = X · W with X = λ(N - L).
  • Choose the number of repairers by minimizing total labor plus downtime cost.

Next: Priority Queues: Preemptive and Non-Preemptive