The interchangeability of tandem queues with heterogeneous customers and dependent service times

R.R. Weber, J. Appl. Prob. 24 727-737, 1992.


Consider $m$ queueing stations in tandem, with infinite buffers between
stations, all initially empty, and an arbitrary arrival process at the first
station.  The service time of customer $j$ at station $i$ is geometrically
distributed with parameter $p_i$, but this is conditioned on the fact that the
sum of the $m$ service times for customer $j$ is $c_j$.  Service times of
distinct customers are independent.  We show that for any arrival process to the
first station the departure process from the last station is statistically
unaltered by interchanging any of the $p_i$s.  This remains true for two
stations in tandem even if there is only a buffer of finite size between them.
The well-known {\em interchangeability of $\cdot/M/1$ queues} is a special case
of this result.  Other special cases provide interesting new results.

back to list of papers