PARALLEL QUEUES WITH RESEQUENCING

This paper considers a system where Poisson arrivals are allocated to K parallel single server queues by a Bernoulli process. Jobs are required to leave the system in their order of arrival. Therefore, after its sojourn time T in a queue a job also experiences a resequencing delay R, so that the time in system for a job is S = T + R. The distribution functions and the first moments of T, R, and S are first obtained by sample path arguments. The sojourn time T is shown to be convex in the load allocation vector in a strong stochastic sense defined in [21]. It is also shown that, in a homogeneous system, equal load allocation minimizes both the random variable T (in the usual stochastic order) and the system time S (in the increasing convex order). Attention is given to this optimum configuration in the rest of the paper. First, it is shown that T is stochastically decreasing and integer convex in K, and that S is decreasing in K. Then, asymptotic expressions for the distributions of T, R, and S are provided as K increases to infinity when the arrival rate to the system is held constant. These expressions show that the distributions of T, R, and S converge in 1/K to the corresponding distributions in the M/GI/infinity system with resequencing. They also provide asymptotic stochastic monotonicity and integer convexity results in K. Although the behavior of R, in general, depends on the load of the system, T and S always have similar structural characteristics, When the arrival rate grows linearly with K, a totally different limiting behavior emerges: Both ER and ES grow in log K, while ET remains constant.