Queueing systems with
leadtime constraints: a fluid model approach for admission and sequencing
control
Costis Maglaras and Jan Van Mieghem, Submitted January 2001, last revision December 2002.
To appear in
European Journal of Operations Research
Abstract:
We
study how multi-product queueing systems should be controlled so that sojourn
times (or end-to-end delays) do not exceed specified leadtimes. The network
dynamically decides when to admit new arrivals and how to sequence the jobs in
the system. To analyze this difficult problem, we propose an approach based on
fluid model analysis that translates the leadtime specifications into
deterministic constraints on the queue length vector. The main benefit of this
approach is that it is possible (and relatively easy) to construct scheduling
and multi-product admission policies for leadtime control. Additional results
are: (a) While this approach is simpler than a heavy-traffic approach, the
admission policies that emerge from it are also more specific than, but
consistent with, those from heavy-traffic analysis. (b) A simulation study
gives a first indication that the policies also perform well in stochastic
systems. (c) Our approach specifies a ``tailored'' admission region for any
given sequencing policy. Such joint admission and sequencing control is
``robust'' in the following sense: system performance is relatively insensitive
to the particular choice of sequencing rule when used in conjunction with
tailored admission control.
As an example, we discuss the
tailored admission regions for two well-known sequencing policies: Generalized
Processor Sharing and Generalized Longest Queue. (d) While we first
focus on the multi-product single server system, we do extend to networks and
identify some subtleties.
Download: qos.pdf (644KB)