Imagine a large factory with a few stations, where each item the factory produces must go through all stations in order. Each station processes items at a fixed rate, say $\lambda_i$, and there's some delay involved in moving each items between stations, say $\Delta t_i$.
I'm wondering how I can calculate:
- The expected "dead time" - The time each station is waiting for new items to come in.
- The total rate for processing items in the factory.
Clearly, we must have that $\lambda_{i+1}\ge\lambda_i$, otherwise we run into the "I Love Lucy" infamous chocolate scene. But assuming that's the case, how do I go about calculating this? I've been reading up about continuous time Markov chains which seem to be related, where for this problem the transition matrix would only have a non-zero super-diagonal, but I'm not quite sure how to adapt them to this problem.
Let's assume you have a tandem of $k$ deterministic service time queues with service times $T_i$ seconds, for $i \in \{1, \ldots, k\}$. For each $i \in \{1, ..., k-1\}$, the departures of queue $i$ go to the input of queue $i+1$. Let $P_i$ be the fixed propagation delay experienced after service at queue $i$. Let $N(t)$ be the stochastic arrival process to queue 1, where (for $t \geq 0$) $N(t)$ represents the total number of arrivals during the interval $[0,t]$. Assume $N(t)$ has rate $\lambda$ arrivals/sec, in the sense that: $$ \lim_{t\rightarrow \infty} \frac{N(t)}{t} = \lambda \quad \mbox{ with prob 1} $$ An example arrival process $N(t)$ is a Poisson process of rate $\lambda$. Assume that $\lambda < 1/T_i$ for all $i \in \{1, \ldots, k\}$.
Since the departures of queue $i$ are spaced at least $T_i$ seconds apart, and the propagation delay $P_i$ does not disturb the relative spacing between jobs, if $T_{i+1}\leq T_i$ then queue $i+1$ just acts as a pure delay line with delay $D_{i+1}=T_{i+1}$. You can replace all such queues with pure delay lines with delay equal to their service time, and the only remaining queues form a tandem with non-decreasing service times.
This is a special case of a problem I looked at a few years ago in: "Equivalent Models for Queueing Analysis of Deterministic Service Time Tree Networks" (Trans Information Theory 2005):
http://www-bcf.usc.edu/~mjneely/pdf_papers/equiv_revise_it.pdf
As in that paper, the output process of the system is equivalent to a system where the first "bottleneck queue" $b$ (the one with the largest service time $T_b=T_{max}$) is isolated and all other queues $i \neq b$ are replaced by pure delay lines of duration $D_i=T_i$. In particular, the average delay in the total system is equal to: $$ \mbox{Total avg delay} = \sum_{i=1}^k P_i + \sum_{i \in \{1, ..., k\}, i \neq b} T_i + \overline{W} $$ where $\overline{W}$ is the average delay in a single queue with deterministic service time $T_{max}$ and with input process $N(t)$. In particular, if $N(t)$ is Poisson of rate $\lambda$ and $\lambda T_{max} < 1$ then: $$ \mbox{Total avg delay} = \sum_{i=1}^k P_i + \sum_{i=1}^k T_i + \frac{\lambda T_{max}^2}{2(1-\lambda T_{max})}$$ where the above uses the standard M/D/1 queue formula $\overline{W} = T_{max} + \frac{\lambda T_{max}^2}{2(1-\lambda T_{max})}$. Of course, Little's theorem also ensures that $\rho_i = \lambda T_i$, where $\rho_i$ is the fraction of time that queue $i$ is nonempty.
The above paper also gives average queue sizes at each queue in a bit more general situation of a tree network with multiple source processes.