Index Heuristics for Multiclass M/G/1 Systems with Nonpreemptive Service and Convex Holding Costs

We consider the optimal service control of a multiclass M/G/1 queueing system in which customers are served nonpreemptively and the system cost rate is additive across classes and increasing convex in the numbers present in each class. Following Whittle's approach to a class of restless bandit problems, we develop a Langrangian relaxation of the service control problem which serves to motivate the development of a class of index heuristics. The index for a particular customer class is characterised as a fair charge for service of that class. The paper develops these indices and reports an extensive numerical investigation which exhibits strong performance of the index heuristics for both discounted and average costs.     

Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach

 This paper develops a polyhedral approach to the design, analysis, and computation of dynamic allocation indices for scheduling binary-action (engage/rest) Markovian stochastic projects which can change state when rested (restless bandits (RBs)), based on partial conservation laws (PCLs). This extends previous work by the author [J. Ni?o-Mora (2001): Restless bandits, partial conservation laws and indexability. Adv. Appl. Probab. 33, 76–98], where PCLs were shown to imply the optimality of index policies with a postulated structure in stochastic scheduling problems, under admissible linear objectives, and they were deployed to obtain simple sufficient conditions for the existence of Whittle's (1988) RB index (indexability), along with an adaptive-greedy index algorithm. The new contributions include: (i) we develop the polyhedral foundation of the PCL framework, based on the structural and algorithmic properties of a new polytope associated with an accessible set system -extended polymatroid}); (ii) we present new dynamic allocation indices for RBs, motivated by an admission control model, which extend Whittle's and have a significantly increased scope; (iii) we deploy PCLs to obtain both sufficient conditions for the existence of the new indices (PCL-indexability), and a new adaptive-greedy index algorithm; (iv) we interpret PCL-indexability as a form of the classic economics law of diminishing marginal returns, and characterize the index as an optimal marginal cost rate; we further solve a related optimal constrained control problem; (v) we carry out a PCL-indexability analysis of the motivating admission control model, under time-discounted and long-run average criteria; this gives, under mild conditions, a new index characterization of optimal threshold policies; and (vi) we apply the latter to present new heuristic index policies for two hard queueing control problems: admission control and routing to parallel queues; and scheduling a multiclass make-to-stock queue with lost sales, both under state-dependent holding cost rates and birth-death dynamics. Received: April 2000 / Accepted: October 2002 Published online: December 9, 2002 RID="★" ID="★" Work partly supported by the Spanish Ministry of Science and Technology (grant BEC2000-1027), NATO (Collaborative Linkage Grant PST.CLG.976568), and the Joint Spanish-US (Fulbright) Commission for Scientific and Technical Exchange (project 2000-20132) Key words. Markov decision process – restless bandits – polyhedral combinatorics – extended polymatroid – adaptive-greedy algorithm – dynamic allocation index – stochastic scheduling – threshold policy – index policy – Gittins index – Klimov index – Whittle index – control of queues – admission control – routing – make-to-stock – multiclass queue – finite buffers – conservation laws – achievable performance Mathematics Subject Classification (1991): (AMS 2000 Subject Classification): 90B36, 90B22, 90C40, 90C57, 90C08     

Review of Some Functionals of Compound Poisson Processes and Related Stopping Times

The paper reviews recent results of D. Perry, W. Stadje and S. Zacks, on functionals of stopping times and the associated compound Poisson process with lower and upper linear boundaries. In particular, formulae of these functionals are explicitly developed for the total expected discounted cost of discarded service in an M/G/1 queue with restricted accessibility; for the expected total discounted waiting cost in an M/G/1 restricted queue; for the shortage, holding and clearing costs in an inventory system with continuous input; for the risk in sequential estimation and for the transform of the busy period when the upper boundary is random.      

The minimum of quadratic functionals of the gradient on the set of convex functions

We study the infimum of functionals of the form among all convex functions such that . ( is a convex open subset of , and M is a given symmetric matrix.) We prove that this infimum is the smallest eigenvalue of M if is . Otherwise the picture is more complicated. We also study the case of an x-dependent matrix M. Received: 23 February 2000/Accepted: 4 December 2000 / Published online: 5 September 2002     

An analysis of Klimov's problem with parallel servers

We introduce a family of undiscounted branching bandits on parallel servers under controls which can impose priorities between customer classes. This family can be used to model a wide range of multi-class queueing scheduling problems, with the capacity to incorporate problem features such as machine breakdowns, complex patterns of preemption/non-preemption and semi-Markov extensions. An index policy (which we call Klimov's rule) is developed which is optimal in the particular case of a single server. An expression for its cost suboptimality is given for parallel servers. Under additional conditions on the nature of the stochastic evolution of the systems concerned, the policy is shown to be asymptotically optimal in a heavy traffic limit. These general results are utilised to develop an analysis of the index policy for a parallel server version of Klimov's classical M/GI/1 system with Bernoulli feedback. This work was supported by the Engineering and Physical Research Council through the award of grant GR/M09308. The author would also like to express his appreciation to Professor I. C. Paschalidis for helpful discussions on Klimov's problem and to Professors J. Niño-Mora and G. Weiss for many discussions and much encouragement     

The second twisted Betti number and the convergence of collapsing Riemannian manifolds

Let M _i X denote a sequence of n-manifolds converging to a compact metric space, X, in the Gromov-Hausdorff topology such that the sectional curvature is bounded in absolute value and dim(X)<n. We prove the following stability result: If the fundamental groups of M _i are torsion groups of uniformly bounded exponents and the second twisted Betti numbers of M _i vanish, then there is a manifold, M, and a sequence of diffeomorphisms from M to a subsequence of {M _i } such that the distance functions of the pullback metrics converge to a pseudo-metric in C ⁰-norm. Furthermore, M admits a foliation with leaves diffeomorphic to flat manifolds (not necessarily compact) such that a vector is tangent to a leaf if and only if its norm converges to zero with respect to the pullback metrics. These results lead to a few interesting applications. Oblatum 17-I-2002 & 27-II-2002?Published online: 29 April 2002     

The reconstruction theorem for endomorphisms

The reconstruction theorem deals with dynamical systems which are given by a map ψ : M → M together with a read out function 𝒻 : M → ℝ. Restricting to the cases where ψ is a diffeomorphism, it states that for generic (ψ, 𝒻 ) there is a bijection between elements x ∈ M and corresponding sequences (𝒻(x), 𝒻 (ψ(x)), . . . , 𝒻 (ψ ^{k -1}(x))) of k successive observations, at least for k sufficiently big. This statement turns out to be wrong in cases where ψ is an endomorphism. In the present paper we derive a version of this theorem for endomorphisms (and which is equivalent to the original theorem in the case of diffeomorphisms). It justifies, also for dynamical systems given by endomorphisms, the algorithms for estimating dimensions and entropies of attractors from obervations. Received: 20 June 2002     

A critically loaded multiclass Erlang loss system

We consider a generalization of the classical Erlang loss model to multiple classes of customers. Each of the J customer classes has an associated Poisson arrival process and an arbitrary holding time distribution. Classj customers requireM _j servers simultaneously. We determine the asymptotic form of the blocking probabilities for all customer classes in the regime known as critical loading, where both the number of servers and offered load are large and almost equal. Asymptotically, the blocking probability of classj customers is proportional toM _j . This asymptotic result provides an approximation for the blocking probabilities which is reasonably accurate. We also consider the behavior of the Erlang fixed point (reduced load approximation) for this model under critical loading. Although the blocking probability of classj customers given by the Erlang fixed point is again asymptotically proportional toM _j , the Erlang fixed point typically gives the wrong limit. Next we show that under critical loading the throughputs have a pleasingly simple form of monotonicity with respect to arrival rates: the throughput of classi is increasing in the arrival rate of classi and decreasing in the arrival rate of classj forji. Finally, we compare two simple control policies for this system under critical loading.     

An obstruction to the positivity of relative Yamabe invariants

For a supergroup , we describe an obstruction to the existence of positive scalar curvature metrics with minimal boundary condition on a compact n-dimensional -manifold W with nonempty boundary M, , in terms of the bordism class [M] in the Stolz obstruction group associated to [St2]. In par ticular, when W is a 5-dimensional spin manifold and the -invariant of a connected component of M is nonzero, we prove that W does not admit a positive scalar curvature metric with minimal boundary condition. Received: 4 July 2001; in final form: 5 February 2002 / Published online: 8 November 2002 RID="*" ID="*" Partially supported by the Grants-in-Aid for Scientific Research (C), Japan Society for the Promotion of Science, No. 11640070.     

The projective rank of a Hermitian symmetric space: a geometric approach and consequences

The “Projective Rank” of a compact connected irreducible Hermitian symmetric space M has been defined as the maximal complex dimension of the compact totally geodesic complex submanifolds having positive holomorphic bisectional curvature with the induced K?hler metric. We present a geometric way to compute this invariant for the space M based on ideas developed in [1], [13] and [14]. As a consequence we obtain the following inequality relating the Projective Rank, Pr(M), the usual rank,rk(M), and the 2-number # (which is known to be equal to the Euler-Poincare characteristic in these spaces). Received: 6 June 2000 / Published online: 1 February 2002     

Conservation Laws for Single-Server Fluid Networks

We consider single-server fluid networks with feedback and arbitrary input processes. The server has to be scheduled in order to minimize a linear holding cost. This model is the fluid analogue of the so-called Klimov problem. Using the achievable-region approach, we show that the Gittins index rule is optimal in a strong sense: it minimizes the linear holding cost for arbitrary input processes and for all time points t0.     

Diophantine approximation for negatively curved manifolds

Let M be a geometrically finite pinched negatively curved Riemannian manifold with at least one cusp. Inspired by the theory of Diophantine approximation of a real (or complex) number by rational ones, we develop a theory of approximation of geodesic lines starting from a given cusp by ones returning to it. We define a new invariant for M, theHurwitz constant of M. It measures how well all geodesic lines starting from the cusp are approximated by ones returning to it. In the case of constant curvature, we express the Hurwitz constant in terms of lengths of closed geodesics and their depths outside the cusp neighborhood. Using the cut locus of the cusp, we define an explicit approximation sequence for a geodesic line starting from the cusp and explore its properties. We prove that the modular once-punctured hyperbolic torus has the minimum Hurwitz constant in its moduli space. Received: 24 October 2000; in final form: 10 November 2001 / Published online: 17 June 2002     

Index Theorem for Equivariant Dirac Operators on Noncompact Manifolds

Let D be a (generalized) Dirac operator on a noncompact complete Riemannian manifold M acted on by a compact Lie group G. Let v: M g = Lie G be an equivariant map, such that the corresponding vector field on M does not vanish outside of a compact subset. These data define an element of K-theory of the transversal cotangent bundle to M. Hence, by embedding of M into a compact manifold, one can define a topological index of the pair (D,v) as an element of the completed ring of characters of G. We define an analytic index of (D,v) as an index space of certain deformation of D and we prove that the analytic and topological indexes coincide. As a main step of the proof, we show that index is an invariant of a certain class of cobordisms, similar to the one considered by Ginzburg, Guillemin and Karshon. In particular, this means that the topological index of Atiyah is also invariant under this class of noncompact cobordisms. As an application, we extend the Atiyah–Segal–Singer equivariant index theorem to our noncompact setting. In particular, we obtain a new proof of this theorem for compact manifolds.