We consider a single server queue where the arrival process is a Markov-modulated Poisson process and service times are independent and identically distributed and independent from arrivals. The underlying intensity process is assumed ergodic with generator cQ, c > 0. We prove under some monotonicity assumptions on Q that the stationary workload W(c) is decreasing in c with respect to the increasing convex ordering.

A simple queueing system, known as the fork-join queue, is considered with basic performance measure defined as the delay between the fork and join dates. Simple lower and upper bounds are derived for some of the statistics of this quantity. They are obtained, in both transient and steady-state regimes, by stochastically comparing the original system to other queueing systems with a structure simpler than the original system, yet with identical stability characteristics. In steady-state, under renewal assumptions, the computation reduces to standard GI/GI/1 calculations and the bounds constitute a first sizing-up of system performance. These bounds can also be used to show that for homogeneous fork-join queue system under assumptions, the moments of the system response time grow logarithmically in the number of parallel processors provided the service time distribution has rational Laplace–Stieltjes transform. The bounding arguments combine ideas from the theory of stochastic ordering with the notion of associated random variables, and are of independent interest to study various other queueing systems with synchronization constraints. The paper is an abridged version of a more complete report on the matter [6].

In this paper, the extremal properties of the ergodic sojourn times in G/G/1queues under various service disciplines are studied in terms of the convex ordering. It is shown that among work-conserving non-preemptive service disciplines that are service time independent, the FIFO and the LIFO service disciplines provide the minima and the maxima, respectively, of the ergodic sojourn times for any G/G/1 queue. For G/M/1 queues, this class of work-conserving service disciplines is extended to include preemptive/resume disciplines. In this case the FIFO and LIFO-P (preemptive/resume LIFO) service disciplines attain the minima and maxima, respectively. These extend results of Durr (1971), Kingman (1962) and a recent result of Ramaswami (1984). Further results are obtained for G/Em/1 and G/D/1 queues.