On the structure of the optimal server control for fluid networks

This paper derives the optimal trajectories in a general fluid network with server control. The stationary optimal policy in the complete state space is constructed. The optimal policy is constant on polyhedral convex cones. An algorithm is derived that computes these cones and the optimal policy. Generalized Klimov indices are introduced, they are used for characterizing myopic and time-uniformly optimal policies.Received: November 2004 / Revised: February 2005The research of this author has been supported by the project ‘‘Stochastic Networks’’ of the Netherlands Organisation for Scientific Research NWO.     

Optimal service control against worst case admission policies: A multichained stochastic game

In this paper we will consider two-person zero-sum games and derive a general approach for solving them. We apply this approach to a queueing problem. In section 1 we will introduce the model and formulate the Key-theorem. In section 2 we develop the theory that we will use in section 3 to prove the Key-theorem. This includes a general and useful result in Lemma 2.1 on the sufficiency of stationary policies.     

Denumerable state semi-Markov decision processes with unbounded costs,average cost criterion

This paper establishes a rather complete optimality theory for the average cost semi-Markov decision model with a denumerable state space, compact metric action sets and unbounded one-step costs for the case where the underlying Markov chains have a single ergotic set. Under a condition which, roughly speaking, requires the existence of a finite set such that the supremum over all stationary policies of the expected time and the total expected absolute cost incurred until the first return to this set are finite for any starting state, we shall verify the existence of a finite solution to the average costs optimality equation and the existence of an average cost optimal stationary policy.     

The footprint sorting problem

Phylogenetic footprints are short pieces of noncoding DNA sequence in the vicinity of a gene that are conserved between evolutionary distant species. A seemingly simple problem is to sort footprints in their order along the genomes. It is complicated by the fact that not all footprints are collinear: they may cross each other. The problem thus becomes the identification of the crossing footprints, the sorting of the remaining collinear cliques, and finally the insertion of the noncollinear ones at "reasonable" positions. We show that solving the footprint sorting problem requires the solution of the "Minimum Weight Vertex Feedback Set Problem", which is known to be NP-complete and APX-hard. Nevertheless good approximations can be obtained for data sets of interest. The remaining steps of the sorting process are straightforward: computation of the transitive closure of an acyclic graph, linear extension of the resulting partial order, and finally sorting w.r.t. the linear extension. Alternatively, the footprint sorting problem can be rephrased as a combinatorial optimization problem for which approximate solutions can be obtained by means of general purpose heuristics. Footprint sortings obtained with different methods can be compared using a version of multiple sequence alignment that allows the identification of unambiguously ordered sublists. As an application we show that the rat has a slightly increased insertion/deletion rate in comparison to the mouse genome.     

Undiscounted Markov decision chains with partial information; an algorithm for computing a locally optimal periodic policy

In this paper we construct an algorithm of successive approximation type that computes a locally optimal periodic policy for a Markov decision chain with partial state information. The algorithm is applied to a queueing network with server control.The research of this author has been supported by the Netherlands Organization for Scientific Research (N.W.O.).     

Thermal stability of tert-butyl peroxypivalate

The thermal stability of tert-butyl peroxypivalate (TBPP) has been investigated in relation to peroxide—diluent compositions in the range 100—10% by weight of peroxide. TBPP was selected because the simple decomposition pattern of the pure product facilitates an interpretation of the concentration dependence. Differential thermal analyses, isothermal and adiabatic storage tests have been used analysis of the decomposition. From the experimental results it is found that the total heat of decomposition is proportional to the peroxide concentration, the activation energy is independent of concentration, and the reaction order varies slightly with concentration. The type of diluent influences the reaction rate. The results are applicable in the 290—360 K temperature range. For the determination of decomposition characteristics, a modified first order equation which takes into account the fraction of diluent can bew used for TBPP—diluent compositions.     

Weak convergence for generalized semi-Markov processes

Generalized semi-Markov schemes were introduced by Matthes in 1962 under the designation ‘Bedienungsschemata’ (service schemes). They include a large variety of familiar stochastic models. It is shown in this paper that under appropriate regularity conditions the associated stochastic process describing the state at timet,t≥0, and the stationary distribution are continuous functions of the life-times of the active components. The supplementary-variable Markov process is shown to be the limit process of a sequence of discrete-state-process obtained through approximating the life-time distributions by mixtures of Erlang distributions and measuring ages and residual life-times in phases. This approach supplements the phase method.     

Linear programming formulation of MDPs in countable state space: The multichain case

We present an Linear Programming formulation of MDPs with countable state and action spaces and no unichain assumption. This is an extension of the Hordijk and Kallenberg (1979) formulation in finite state and action spaces. We provide sufficient conditions for both existence of optimal solutions to the primal LP program and absence of duality gap. Then, existence of a (possibly randomized) average optimal policy is also guaranteed. Existence of a stationary average optimal deterministic policy is also investigated.