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 requi red to leave the system in their order of arrival. Therefore, after it s sojourn time T in a queue a job also experiences a resequencing dela y R, so that the time in system for a job is S = T + R. The distributi on functions and the first moments of T, R, and S are first obtained b y sample path arguments. The sojourn time T is shown to be convex in t he load allocation vector in a strong stochastic sense defined in [21] . It is also shown that, in a homogeneous system, equal load allocatio n 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, i t 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 w hen 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 cor responding distributions in the M/GI/infinity system with resequencing . They also provide asymptotic stochastic monotonicity and integer con vexity results in K. Although the behavior of R, in general, depends o n the load of the system, T and S always have similar structural chara cteristics, When the arrival rate grows linearly with K, a totally dif ferent limiting behavior emerges: Both ER and ES grow in log K, while ET remains constant.