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.     

Reflections on a New Approach to Gittins Indexation

Traditional approaches to stochastic resource allocation problems (including the classical multi-armed bandit problems) have usually made use of dynamic programming (DP) methodology, perhaps buttressed by further ad hoc arguments. While such approaches seem ‘natural’ they have usually proved technically very difficult. Bertsimas and Niño-Mora have recently given a radically new account of many important results in this area which relate to Gittins indices. The key to their approach is in the characterisation of the region of achievable performance. The optimisation problems of interest are then solved as linear programs over this region. Here we exploit elements within the Bertsimas and Niño-Mora framework (in particular, its capacity to give formulae for the total return of a given policy in closed form) to obtain (i) a simple dynamic programming proof of the optimality of Gittins index policies and (ii) a range of index-based suboptimality bounds for general policies for a variety of stochastic models for resource allocation.     

A semidefinite programming approach to the optimal control of a single server queueing system with imposed second moment constraints

Classical analyses of the dynamic control of multi-class queueing systems frequently yield simple priority policies as optimal. However, such policies can often result in excessive queue lengths for the low priority jobs/customers. We propose a stochastic optimisation problem in the context of a two class M/M/1 system which seeks to mitigate this through the imposition of constraints on the second moments of queue lengths. We analyse the performance of two families of parametrised heuristic policies for this problem. To evaluate these policies we develop lower bounds on the optimum cost through the achievable region approach. A numerical study points to the strength of performance of threshold policies and to directions for future research.     

Submanifolds of the Cayley projective plane with bounded second fundamental form

We consider totally complex submanifolds of the Cayley projective plane with estimates on the length squared of the second fundamental form. We determine those bounds for which the second fundamental form is parallel and for which the submanifold is totally geodesic. The case of totally real submanifolds is also included.     

On the evaluation of strategies for branching bandit processes

Glazebrook [1] has given an account of improved procedures for strategy evaluation for resource allocation in a stochastic environment. These methods are extended in the paper in such a way that they can be applied to problems which, for example, have precedence constraints and/or an arrivals process of new jobs. Theoretical results, backed up by numerical studies, show that quasi-myopic heuristics often perform well.     

Holomorphic maps of Kähler manifolds with constrained energy density

We consider holomorphic and antiholomorphic maps of Kähler manifoldsM andN withM compact. In view of bounds on the Ricci curvature ofM and the holomorphic bisectional curvature ofN, the energy density of the map is constrained to satisfy certain inequalities. One inequality implies that the map is constant. Another specifies the image ofM as a totally geodesic real surface of constant Gaussian curvature inN.     

On the evaluation of fixed permutations as strategies in stochastic scheduling

A general model is proposed for the stochastic version of the single-machine allocation problem. Sufficient conditions are given to ensure that there is an optimal strategy given by a fixed permutation of the job set. Additional results are given for an important special case of the general model involving simple jobs. The paper concludes with material concerning the evaluation of fixed permutations as strategies under conditions more general than the sufficient conditions mentioned above.     

Differential Algebras with Banach-Algebra Coefficients II: The Operator Cross-Ratio Tau-Function and the Schwarzian Derivative

Several features of an analytic (infinite-dimensional) Grassmannian of (commensurable) subspaces of a Hilbert space were developed in the context of integrable PDEs (KP hierarchy). We extended some of those features when polarized separable Hilbert spaces are generalized to a class of polarized Hilbert modules and then consider the classical Baker and τ-functions as operator-valued. Following from Part I we produce a pre-determinant structure for a class of τ-functions defined in the setting of the similarity class of projections of a certain Banach *-algebra. This structure is explicitly derived from the transition map of a corresponding principal bundle. The determinant of this map leads to an operator τ-function. We extend to this setting the operator cross-ratio which had previously been used to produce the scalar-valued τ-function, as well as the associated notion of a Schwarzian derivative along curves inside the space of similarity classes of a given projection. We link directly this cross-ratio with Fay’s trisecant identity for the τ-function. By restriction to the image of the Krichever map, we use the Schwarzian to introduce the notion of an operator-valued projective structure on a compact Riemann surface: this allows a deformation inside the Grassmannian (as it varies its complex structure). Lastly, we use our identification of the Jacobian of the Riemann surface in terms of extensions of the Burchnall–Chaundy C*-algebra (Part I) provides a link to the study of the KP hierarchy.     

On spectral flow of transversal dirac operators and a theorem of Vafa-Witten

We outline the proof of a theorem of Vafa-Witten type on uniform bounds for the eigenvalues of a family of transversal Dirac operators relative to a Riemannian foliation. The family in question is parameterized by a moduli space of basic connections with respect to the foliation modulo a suitable group of foliation preserving gauge transformations. The proof is based on the concept of spectral flow, applied to the suspension of suitable gauge transformations to periodic families of Dirac operators. Work supported in part by a grant from the National Science Foundation.     

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