Dispatching to parallel servers

Olivier Bilenne ()
Additional contact information
Olivier Bilenne: Inria, Grenoble INP, LIG

Queueing Systems: Theory and Applications, 2021, vol. 99, issue 3, No 1, 199-230

Abstract: Abstract Policy iteration techniques for multiple-server dispatching rely on the computation of value functions. In this context, we consider the continuous-space M/G/1-FCFS queue endowed with an arbitrarily designed cost function for the waiting times of the incoming jobs. The associated relative value function is a solution of Poisson’s equation for Markov chains, which in this work we solve in the Laplace transform domain by considering an ancillary, underlying stochastic process extended to (imaginary) negative backlog states. This construction enables us to issue closed-form relative value functions for polynomial and exponential cost functions and for piecewise compositions of the latter, in turn permitting the derivation of interval bounds for the relative value function in the form of power series or trigonometric sums. We review various cost approximation schemes and assess the convergence of the interval bounds these induce on the relative value function, namely Taylor expansions (divergent, except for a narrow class of entire functions with low orders of growth) and uniform approximation schemes (polynomials, trigonometric), which achieve optimal convergence rates over finite intervals. This study addresses all the steps to implementing dispatching policies for systems of parallel servers, from the specification of general cost functions toward the computation of interval bounds for the relative value functions and the exact implementation of the first-policy improvement step.

Keywords: Dispatching; Policy iteration; First-policy improvement; Poisson equation; M/G/1 queue; 40A30; 41A25; 41A50; 41A10; 42A10; 44A10; 60K20; 60K30; 62E20; 90B22 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11134-021-09713-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:99:y:2021:i:3:d:10.1007_s11134-021-09713-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-021-09713-y

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().