Dispatching to parallel servers. Solutions of Poisson's equation for first-policy improvement

DOI10.1007/S11134-021-09713-YMaRDI QIDQ2070675zbMATH OpenOpenAlexFDO

Authors Olivier Bilenne

Publication date 24 January 2022

Published in Queueing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.10688

zbMATH Keywords

\(M/G/1\) queuedispatchingfirst-policy improvementPoisson equationpolicy iteration

Mathematics Subject Classification ID

Applications of Markov renewal processes (reliability, queueing networks, etc.) (60K20) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Asymptotic distribution theory in statistics (62E20) Queues and service in operations research (90B22)

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 towards the computation of interval bounds for the relative value functions and the exact implementation of the first-policy improvement step.

Recommendations

• On the value function of the M/G/1 FCFS and LCFS queues
• On the structure of value functions for threshold policies in queueing models
• General dynamic programming algorithms applied to polling systems
• On the value function of the M/Cox(r)/1 queue
• Open-loop routing of N arrivals to M parallel queues

Cites work

• A first course in stochastic models.
• A heuristic rule for routing customers to parallel servers
• A Liapounov bound for solutions of the Poisson equation
• A New Approach to the Limit Theory of Recurrent Markov Chains
• Average Cost Optimal Stationary Policies in Infinite State Markov Decision Processes with Unbounded Costs
• Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey
• scientific article; zbMATH DE number 3148886 (Why is no real title available?)
• scientific article; zbMATH DE number 3869671 (Why is no real title available?)
• scientific article; zbMATH DE number 3009452 (Why is no real title available?)
• scientific article; zbMATH DE number 936511 (Why is no real title available?)
• scientific article; zbMATH DE number 1416627 (Why is no real title available?)
• scientific article; zbMATH DE number 3301601 (Why is no real title available?)
• Neuro-Dynamic Programming: An Overview and Recent Results
• On a Generalized M/G/1 Queuing Process in Which the First Customer of Each Busy Period Receives Exceptional Service
• On the Lambert \(w\) function
• On the Poisson equation in the potential theory of a single kernel.
• On the uniqueness of solutions to the Poisson equations for average cost Markov chains with unbounded cost functions
• On the value function of the M/Cox(r)/1 queue
• On the value function of the M/G/1 FCFS and LCFS queues
• Poisson's equation for the recurrent M/G/1 queue
• Potentiel markovien récurrent des chaînes de Harris. (Recurrent Markov potential of Harris chains)
• Separable routing: A scheme for state-dependent routing of circuit switched telephone traffic
• Size- and state-aware dispatching problem with queue-specific job sizes
• Stochastic processes. Theory for applications.
• The policy iteration algorithm for average reward Markov decision processes with general state space
• Theory of probability and random processes.
• Transform-domain solutions of Poisson's equation with applications to the asymptotic variance

Cited in

(2)

• poisson
• On the value function of the M/G/1 FCFS and LCFS queues

Describes a project that uses

Uses Software

• MCQueue
• GitHub

This page was built for publication: Dispatching to parallel servers. Solutions of Poisson's equation for first-policy improvement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2070675)