29 December 2010 in Queueing Systems
9 February 2011 in Queueing Systems
24 March 2011 in Queueing Systems
1 May 2018 in Mathematics of Operations Research
Scheduling control for a single-server queue with I customer classes and reneging is considered, with linear holding or reneging cost. An asymptotically optimal (AO) policy in heavy traffic is identified where classes are prioritized according to a workload-dependent dynamic index rule. Denote by ci, μi, and θi, i ∈ ℐ := {1, …, I} the queue length cost, service rate, and reneging rate, for class-i customers. Then, a relabeling of the classes and a partition 0 = w0 < w1 < ⋯ < wK = ∞, K ≤ I are identified such that the policy acts to always assign least priority to the class i when the rescaled workload is in the interval [wi−1, wi). The relabeling is such that when workload is withing the lowest [resp., highest] interval [wi−1, wi), the least priority class is the one with smallest cμ [resp., greatest θ] value. This result stands in sharp contrast to known fluid-scale results where it is AO to prioritize by the fixed cμ/θ index. One of the technical challenges is the discontinuity of the limiting queue length process under optimality. Discontinuities occur whenever the workload reaches one of the levels wi.
1 June 2020 in Stochastic Systems
A parallel server system is considered in which a dispatcher routes incoming jobs to a fixed number of heterogeneous servers, each with its own queue. Much effort has been previously made to design policies that use limited state information (e.g., the queue lengths in a small subset of the set of servers, or the identity of the idle servers). However, existing policies either do not achieve the stability region or perform poorly in terms of job completion time. We introduce Persistent-Idle (PI), a new, perhaps counterintuitive, load-distribution policy that is designed to work with limited state information. Roughly speaking, PI always routes to the server that has last been idle. Our main result is that this policy achieves the stability region. Because it operates quite differently from existing policies, our proof method differs from standard arguments in the literature. Specifically, large time properties of reflected random walk, along with a careful choice of a Lyapunov function, are combined to obtain a Lyapunov condition over sufficiently long-time intervals. We also provide simulation results that indicate that job completion times under PI are low for different choices of system parameters, compared with several state-of-the-art load-distribution schemes.
7 November 2023 in SIAM Journal on Mathematical Analysis
The large-time behavior of a nonlinearly coupled pair of measure-valued transport equations with discontinuous boundary conditions, parameterized by a positive real-valued parameter [Formula: see text], is considered. These equations describe the hydrodynamic or fluid limit of many-server queues with reneging (with traffic intensity [Formula: see text]), which model phenomena in diverse disciplines, including biology and operations research. For a broad class of reneging distributions with finite mean, and service distributions with finite mean and hazard rate function that is either nonincreasing or bounded away from zero and infinity, it is shown that if the fluid equations have a unique invariant state, then the Dirac measure at this invariant state is the unique invariant distribution of the fluid equations. In particular, this implies that the stationary distributions of scaled [Formula: see text]-server systems converge to the unique invariant state of the corresponding fluid equations. Moreover, when the mean arrival rate is not equal to the mean service rate, that is, when [Formula: see text], it is shown that the solution to the fluid equation starting from any initial condition converges to this unique invariant state in the large-time limit. The proof techniques are different under the two sets of assumptions on the service distribution, as well as under the two regimes [Formula: see text] and [Formula: see text]. When the hazard rate function is nonincreasing, a reformulation of the dynamics in terms of a certain renewal equation is used, in conjunction with recursive asymptotic estimates. When the hazard rate function is bounded away from zero and infinity, the proof uses an extended relative entropy functional as a Lyapunov function. Analogous large-time convergence results are also established for a system of coupled measure-valued equations modeling a multiclass queue.