Parallel queues with resequencing

Publisher Website
Google Scholar
Abstract
This paper corrslders a system where Poisson armvals are allocated to K parallel single server queues by a Bernoulli process. Jobs are required to leave the system m their order of arrival. Therefore, after its sojourn tUne T in a queue a job also experiences a resequerzcmg delay R, so that the time in system for a job is ,S = T+R. The distribution functions and the first moments of ~, 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 isgiven tothisopt)mum configuration intherest of the paper. First, itis shown that T is stochastically decreasing and integer convex in hr. and that S is decreasing in K". Then, asymptotic expressions forthedlstributlons of T. R, and S are provided as K increases toinfmity when the arrival rate to the system is held constant. These expressions show that the distributions of T, R, and S converge in l/K to the corresponding distributions m the M/GI/x system with resequencmg. They also provide asyrnptot~c stochastic monotoniclty and integer convexity results in A'. 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 limding behavior emerges: Both ER and ESgrowmlogK,while IT remains constant. Categories and Subject Descriptors: C.2.4 (Computer-Communication Networks) Distributed

This publication has 3 references indexed in Scilit: