Approximations for the mean sojourn time in a parallel queue

This paper considers a parallel queue, which is two-queue network, where any arrival generates a job at both queues. The focus is on methods to quantify the mean value of the `system's sojourn time' S: with Si denoting a job's sojourn time in queue i, S is defined as max(S1; S2). It is noted that earlier work has revealed that this class of models is notoriously hard to analyze. We first evaluate a number of bounds developed in the literature, and observe that under fairly broad circumstances these can be rather inaccurate. We distinguish between the homogeneous case, in which the jobs generated at both queue stem from the same distribution, and the heterogeneous case. For the former case we present a number of approximations, that are extensively tested by simulation, and turn out to perform remarkably well. For the latter case, we identify conditions under which S can be accurately approximated by the sojourn time of the queue with the highest load.