Finding the K best policies in a finite-horizon Markov decision process

Directed hypergraphs represent a general modelling and algorithmic tool, which have been successfully used in many different research areas such as artificial intelligence, database systems, fuzzy systems, propositional logic and transportation networks. However, modelling Markov decision processes using directed hypergraphs has not yet been considered.In this paper we consider finite-horizon Markov decision processes (MDPs) with finite state and action space and present an algorithm for finding the K best deterministic Markov policies. That is, we are interested in ranking the first K deterministic Markov policies in non-decreasing order using an additive criterion of optimality. The algorithm uses a directed hypergraph to model the finite-horizon MDP. It is shown that the problem of finding the optimal policy can be formulated as a minimum weight hyperpath problem and be solved in linear time, with respect to the input data representing the MDP, using different additive optimality criteria.     

Optimal ergodic control of Markov diffusion processes with minimum variance

In this paper, we study the optimal ergodic control problem with minimum variance for a general class of controlled Markov diffusion processes. To this end, we follow a lexicographical approach. Namely, we first identify the class of average optimal control policies, and then within this class, we search policies that minimize the limiting average variance. To do this, a key intermediate step is to show that the limiting average variance is a constant independent of the initial state. Our proof of this latter fact gives a result stronger than the central limit theorem for diffusions. An application to manufacturing systems illustrates our results.     

Controlled Markov Chains with Weak and Strong Interactions: Asymptotic Optimality and Applications to Manufacturing

This paper deals with the asymptotic optimality of a stochastic dynamic system driven by a singularly perturbed Markov chain with finite state space. The states of the Markov chain belong to several groups such that transitions among the states within each group occur much more frequently than transitions among the states in different groups. Aggregating the states of the Markov chain leads to a limit control problem, which is obtained by replacing the states in each group by the corresponding average distribution. The limit control problem is simpler to solve as compared with the original one. A nearly-optimal solution for the original problem is constructed by using the optimal solution to the limit problem. To demonstrate, the suggested approach of asymptotic optimal control is applied to examples of manufacturing systems of production planning.     

Optimal recruitment strategies in a multi-level manpower planning model

Markov manpower planning models have extensively been analysed in the past in order to find an optimal personnel strategy for which the stocks of the manpower system evolve towards desirable ones. So far, those models do not take into account interactions among different organizational decision levels. In this paper, a multi-level manpower planning model is presented that considers, besides the desirable stock vector at overall level, proposals for the departmental stocks from lower organizational levels. Attainability of the stock vectors at departmental level is examined under control by recruitment and interdepartmental transitions. A multi-level optimization algorithm is presented to determine an optimal recruitment strategy resulting in attainable and acceptable stocks that are a compromise between the proposal from the top and the proposals from the departments.     

Exact filtering in conditionally Markov switching hidden linear models

In the classical setup of Markov switching hidden linear systems, the exact evaluation of optimal filters requires computations with complexity increasing exponentially with respect to the number of observations. In the present article, we propose a new family of models which overcome this difficulty, and render practically feasible these calculations.     

A statistical Markov chain approximation of transient hospital inpatient inventory

Inventory levels are critical to the operations, management, and capacity decisions of inventory systems but can be difficult to model in heterogeneous, non-stationary throughput systems. The inpatient hospital is a complicated throughput system and, like most inventory systems, hospitals dynamically make managerial decisions based on short term subjective demand predictions. Specifically, short term hospital staffing, resource capacity, and finance decisions are made according to hospital inpatient inventory predictions. Inpatient inventory systems have non-stationary patient arrival and service processes. Previously developed models present poor inventory predictions due to model subjectivity, high model complexity, solely expected value predictions, and assumed stationary arrival and service processes. Also, no models present statistical testing for model significance and quality-of-fit. This paper presents a Markov chain probability model that uses maximum likelihood regression to predict the expectations and discrete distributions of transient inpatient inventories. The approach has a foundation in throughput theory, has low model complexity, and provides statistical significance and quality-of-fit tests unique to this Markov chain. The Markov chain is shown to have superior predictability over Seasonal ARIMA models.     

Optimal inspection and replacement policies for multi-state deteriorating systems

In this paper, a phase-type approach is proposed to derive optimal inspection and replacement policies for semi-Markovian deteriorating systems. In this approach, the general sojourn time distributions of a semi-Markovian maintenance model are approximated by acyclic phase-type distributions. Using the approximation, a semi-Markovian maintenance model can be transformed into a Markovian maintenance model such that the analytical tractability of Markov processes can be preserved. Based on the Markovian model, algorithms are provided to derive the optimal state-dependent and state-age-dependent inspection and replacement policies such that the expected long-run cost rate is minimized. Furthermore, procedures are developed to implement the optimal policies on semi-Markovian deteriorating systems. The implementation of the optimal policies are illustrated by numerical examples.     

The existence of good Markov strategies for decision processes with general payoffs

For countable-state decision processes (dynamic programming problems), a general class of objective functions is identified for which it is shown that good Markov strategies always exist. This class includes product and lim inf rewards, as well as practically all the classical dynamic programming expected payoff functions.     

Recruitment Effects on Manpower Structures

Recruitment is one of the dynamics of manpower systems that can usually be most effectively controlled, always assuming that there is at any time an adequate supply of recruits to a system. In this situation, recruitment can be fixed to meet immediate demands, or it can be part of long-term planning programmes designed perhaps to alleviate a skewness in the length of service profile without reducing the strength of the system greatly. In general, recruitment levels will necessarily be connected with wastage and promotion in a system as well as with the desired growth of the system. The process of determining manpower-planning policies, hereunder recruitment levels, is open to a variety of options with regard to the underlying assumptions that are made: observed experience can be assumed to continue; promotion policies can be adjusted and the consequences estimated; recruitment levels can be allowed to meet immediate demands but with the restriction of some maximum level; or recruitment levels are pre-fixed on the basis of some perhaps even arbitrary management desires. Each of these options and each accompanying recruitment policy will affect the internal structure of the system, with regard to both rank and length of service profiles. This paper employs established projection and promotion models for hierarchical manpower systems to consider recruitment policies and their effects on internal structures. Various policy models are outlined and results presented for a particular application.     

Queueing systems with leadtime constraints: A fluid-model approach for admission and sequencing control

We study how multi-product queueing systems should be controlled so that sojourn times (or end-to-end delays) do not exceed specified leadtimes. The network dynamically decides when to admit new arrivals and how to sequence the jobs in the system. To analyze this difficult problem, we propose an approach based on fluid-model analysis that translates the leadtime specifications into deterministic constraints on the queue length vector. The main benefit of this approach is that it is possible (and relatively easy) to construct scheduling and multi-product admission policies for leadtime control. Additional results are: (a) While this approach is simpler than a heavy-traffic approach, the admission policies that emerge from it are also more specific than, but consistent with, those from heavy-traffic analysis. (b) A simulation study gives a first indication that the policies also perform well in stochastic systems. (c) Our approach specifies a “tailored” admission region for any given sequencing policy. Such joint admission and sequencing control is “robust” in the following sense: system performance is relatively insensitive to the particular choice of sequencing rule when used in conjunction with tailored admission control. As an example, we discuss the tailored admission regions for two well-known sequencing policies: Generalized Processor Sharing and Generalized Longest Queue. (d) While we first focus on the multi-product single server system, we do extend to networks and identify some subtleties.     

Digital idle speed control of automotive engines: A safety problem for hybrid systems

We address the idle speed control problem in automotive electronics using hybrid methods to derive a digital control law with guaranteed properties. Associating a switching system with the hybrid system that describes the engine operation is crucial to developing a computationally feasible approach. For switching systems with minimum and maximum dwell times and controlled resets, we are able to derive digital control strategies with guaranteed properties that ensure safety. The proposed methodology, while motivated by the idle control problem, is of general interest for hybrid systems for which minimum and maximum dwell times can be established. In our modeling approach, we do not assume synchronization between sampling time and switching time. This is an important technical aspect in general, and in particular for our application, where there is no reason why sampling and switching should be synchronized. Some simulation results are included to demonstrate the effectiveness of the approach.     

Bounds and approximations for continuous-time Markovian transition probabilities and large systems

We propose new bounds and approximations for the transition probabilities of a continuous-time Markov process with finite but large state-space. The bounding and approximating procedures have been exposed in another paper [S. Mercier, Numerical bounds for semi-Markovian quantities and applications to reliability, in revision for Methodology and Computing in Applied Probability] in the more general context of a continuous-time semi-Markov process with countable state-space. Such procedures are here specialized to the Markovian finite case, leading to much simpler algorithms. The aim of this paper is to test such algorithms versus other algorithms from the literature near from ours, such as forward Euler approximation, external uniformization and a finite volume method from [C. Cocozza-Thivent, R. Eymard, Approximation of the marginal distributions of a semi-Markov process using a finite volume scheme, ESAIM: M2AN 38(5) (2004) 853–875].     

A stochastic multiscale model for electricity generation capacity expansion

Long-term planning for electric power systems, or capacity expansion, has traditionally been modeled using simplified models or heuristics to approximate the short-term dynamics. However, current trends such as increasing penetration of intermittent renewable generation and increased demand response requires a coupling of both the long and short term dynamics. We present an efficient method for coupling multiple temporal scales using the framework of singular perturbation theory for the control of Markov processes in continuous time. We show that the uncertainties that exist in many energy planning problems, in particular load demand uncertainty and uncertainties in generation availability, can be captured with a multiscale model. We then use a dimensionality reduction technique, which is valid if the scale separation present in the model is large enough, to derive a computationally tractable model. We show that both wind data and electricity demand data do exhibit sufficient scale separation. A numerical example using real data and a finite difference approximation of the Hamilton–Jacobi–Bellman equation is used to illustrate the proposed method. We compare the results of our approximate model with those of the exact model. We also show that the proposed approximation outperforms a commonly used heuristic used in capacity expansion models.     

Turnpike properties for a class of piecewise deterministic systems arising in manufacturing flow control

This paper deals with a general class of piecewise deterministic control systems that encompasses FMS flow control models. One uses the Markov renewal decision process formalism to characterize optimal policies via a discrete event dynamic programming approach. A family of control problems with a random stopping time is associated with these optimality conditions. These problems can be reformulated as infinite horizon deterministic control problems. It is then shown how the so-calledturnpike property should hold for these deterministic control problems under classical convexity assumptions. These turnpikes have the same generic properties as the attractors obtained via a problem specific approach in FMS flow control models and production planning and are calledhedging points in this literature.This research has been supported by NSERC-Canada, Grants No. A4952 by FCAR-Québec, Grant No. 88EQ3528, Actions Structurantes, MESS-Québec, Grant No. 6.1/7.4(28), and FNRS-Switzerland.     

An EM Algorithm for Batch Markovian Arrival Processes and its Comparison to a Simpler Estimation Procedure

Although the concept of Batch Markovian Arrival Processes (BMAPs) has gained widespread use in stochastic modelling of communication systems and other application areas, there are few statistical methods of parameter estimation proposed yet. However, in order to practically use BMAPs for modelling, statistical model fitting from empirical time series is an essential task. The present paper contains a specification of the classical EM algorithm for MAPs and BMAPs as well as a performance comparison to the computationally simpler estimation procedure recently proposed by Breuer and Gilbert. Furthermore, it is shown how to adapt the latter to become an estimator for hidden Markov models.     

Numerical investigation of finite-source multiserver systems with different vacation policies

Systems with vacations are usually modeled and analyzed by queueing theory, and almost all works assume that the customer source is infinite and the arrival process is Poisson. This paper aims to present an approach for modeling and analyzing finite-source multiserver systems with single and multiple vacations of servers or all stations, using the Generalized Stochastic Petri nets model. We show how this high level formalism, allows a simple construction of detailed and compact models for such systems and to obtain easily the underlying Markov chains. However, for real vacation systems, the models may have a huge state space. To overcome this problem, we give the algorithms for automatically computing the infinitesimal generator, for the different vacation policies. In addition, we develop the formulas of the main exact stationary performance indices. Through numerical examples, we discuss the effect of server number, vacation rate and vacation policy on the system’s performances.     

On dispatching unequally capable service technicians

A common problem that faces many high-tech electronic productcompanies is how to effectively provide systems support fortheir products/machines/systems installed at various customersites using different levels of technical personnel. The problemcan be viewed as a model with multiple level servers and multiplevolume demands. In this paper, a semi-Markov decision processwith average criterion has been employed to formulate the dynamicsof the system. Optimal policies for human resource allocationdecision with minimum costs have been derived and the loss ratefor customer requests has been considered. We prove that theembedding Markov chain is ergodic, induced by any stationarydeterministic policy. We obtain some related parameters whichcan answer questions from managers. We also provide some numericalexamples.     

Interdisciplinary education – a predator–prey model for developing a skill set in mathematics,biology and technology

The science of biology has been transforming dramatically and so the need for a stronger mathematical background for biology students has increased. Biological students reaching the senior or post-graduate level often come to realize that their mathematical background is insufficient. Similarly, students in a mathematics programme, interested in biological phenomena, find it difficult to master the complex systems encountered in biology. In short, the biologists do not have enough mathematics and the mathematicians are not being taught enough biology. The need for interdisciplinary curricula that includes disciplines such as biology, physical science, and mathematics is widely recognized, but has not been widely implemented. In this paper, it is suggested that students develop a skill set of ecology, mathematics and technology to encourage working across disciplinary boundaries. To illustrate such a skill set, a predator–prey model that contains self-limiting factors for both predator and prey is suggested. The general idea of dynamics, is introduced and students are encouraged to discover the applicability of this approach to more complex biological systems. The level of mathematics and technology required is not advanced; therefore, it is ideal for inclusion in a senior-level or introductory graduate-level course for students interested in mathematical biology.     

Large deviations of Markov chains with multiple time-scales

For Markov processes evolving on multiple time-scales a combination of large component scalings and averaging of rapid fluctuations can lead to useful limits for model approximation. A general approach to proving a law of large numbers to a deterministic limit and a central limit theorem around it have already been proven in Kang and Kurtz (2013) and Kang et al. (2014). We present here a general approach to proving a large deviation principle in path space for such multi-scale Markov processes. Motivated by models arising in systems biology, we apply these large deviation results to general chemical reaction systems which exhibit multiple time-scales, and provide explicit calculations for several relevant examples.     

Cyclic Markov equilibria in stochastic games

We examine a three-person stochastic game where the only existing equilibria consist of cyclic Markov strategies. Unlike in two-person games of a similar type, stationary ε-equilibria (ε > 0) do not exist for this game. Besides we characterize the set of feasible equilibrium rewards.