The cafeteria process, tandem queues with dependent 0-1 service times and the bowl shape phenomenon

R.R. Weber and G. Weiss, Operations Research 42 895-912, 1994.

Abstract

Customers move through a series of $M$ service stations.  Each customer,
independent of all the others, requires service from only one of the stations,
for a duration of 1 time unit, this being station $i$ with probability $p_i$.
The customer has zero service time at all the other stations, but there is no
overtaking between the customers, and so queueing occurs.  In the case where
there is unlimited waiting room between servers, we show that the system is
interchangeable --- permuting the order of the stations has no effect on the
distribution of the output stream.  When there is no waiting room between the
stations we investigate optimal loads on the servers in terms of optimal $p_i$'s
for up to 10 stations, and observe that optimal loads exhibit the {\em bowl
phenomenon}.  We also obtain some bound on the throughput for equal loads as a
function of $M$.

back to list of papers