  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.
