Linear programming in tector criterion markov and semi-Markov decision processes

Optimality problems in infinite horizon, discrete time, vector criterion Markov and semi-Markov decision processes are expressed as standard problems of multiobjective linear programming. Processes with discounting, absorbing processes and completely ergodie processes without discounting are investigated. The common properties and special structure of derived multiobjective linear programming problems are overviewed. Computational simplicities associated with these problems in comparison with general multiobjective linear programming problems are discussed. Methods for solving these problems are overviewed and simple numerical examples are given.     

Optimal server assignment in a two-stage tandem queueing system

We study Markovian queueing systems consisting of two stations in tandem. There is a dedicated server in each station and an additional server that can be assigned to any station. Assuming that linear holding costs are incurred by jobs in the system and two servers can collaborate to work on the same job, we determine structural properties of optimal server assignment policies under the discounted and the average cost criteria.     

Maximizing throughput in finite-source parallel queue systems

Motivated by the dispatching of trucks to shovels in surface mines, we study optimal routing in a Markovian finite-source, multi-server queueing system with heterogeneous servers, each with a separate queue. We formulate the problem of routing customers to servers to maximize the system throughput as a Markov Decision Process. When the servers are homogeneous, we demonstrate that the Shortest Queue policy is optimal, and when the servers are heterogeneous, we partially characterize the optimal policy and present a near-optimal and simple-to-implement policy. We use the model to illustrate the substantial benefits of pooling, by comparing it to the permanent assignment of customers to servers.     

A survey of Markov decision models for control of networks of queues

We review models for the optimal control of networks of queues. Our main emphasis is on models based on Markov decision theory and the characterization of the structure of optimal control policies.This research was partially supported by the National Science Foundation under Grant No. DDM-8719825. The Government has certain rights in this material. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. The research was also partially supported by the C.I.E.S. (France), while the author was on leave at INRIA, Sophia-Antipolis, 1991–92.     

Admission control and pricing in a queue with batch arrivals

We investigate a problem of admission control in a queue with batch arrivals. We consider a single server with exponential service times and a compound Poisson arrival process. Each arriving batch computes its expected benefit and decides whether or not to enter the system. The controller’s problem is to set state dependent prices for arriving batches. Once prices have been set we formulate the admission control problem, derive properties of the value function, and obtain the optimal admission policy.     

Suboptimal policy determination for large-scale Markov decision processes,part 2: Implementation and numerical evaluation

We present an implementation of the procedure for determining a suboptimal policy for a large-scale Markov decision process (MDP) presented in Part 1. An operation count analysis illuminates the significant computational benefits of this procedure for determining an optimal policy relative to a procedure for determining a suboptimal policy based on state and action space aggregation. Results of a preliminary numerical study indicate that the quality of the suboptimal policy produced by the 3MDP approach shows promise.This research has been supported by NSF Grants Nos. ECS-80-18266 and ECS-83-19355.     

Identities for stopped markov chains and their applications

In this paper we obtain identities for some stopped Markov chains. These identities give a unified approach to many problems in optimal stopping of a Markovian sequence, extinction probability of a Markovian branching process and martingale theory.     

Optimality of a Threshold Policy in theM/M/ queue with repeated vacations

Consider anM/M/1 queueing system with server vacations where the server is turned off as soon as the queue gets empty. We assume that the vacation durations form a sequence of i.i.d. random variables with exponential distribution. At the end of a vacation period, the server may either be turned on if the queue is non empty or take another vacation. The following costs are incurred: a holding cost ofh per unit of time and per customer in the system and a fixed cost of each time the server is turned on. We show that there exists a threshold policy that minimizes the long-run average cost criterion. The approach we use was first proposed in Blanc et al. (1990) and enables us to determine explicitly the optimal threshold and the optimal long-run average cost in terms of the model parameters.     

Analysis of IEEE 802.11 non-saturated DCF by matrix analytic methods

In the IEEE 802.11 MAC layer protocol, the basic access method is the Distributed Coordination Function based on the CSMA/CA. In this paper, we investigate the analytic performance of IEEE 802.11 DCF in the non-saturation mode. We assume that there is a fixed number n of competing stations and the packet arrival process to each station is a Poisson process. We model IEEE 802.11 DCF in non-saturation mode by a 3-dimensional Markov chain and derive the steady state probability of the Markov chain by applying the matrix analytic method. We obtain the probability generating function of Head-of-Line delay (HoL-delay), non-saturation throughput and packet loss probability. Our results can be used for finding the optimal number of stations that can be accommodated while satisfying a given QoS requirement. This research is supported by the MIC (Ministry of Information and Communication), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Assessment).     

Optimal threshold policies in a two-class preemptive priority queue with admission and termination control

We consider a two-class 1 preemptive priority queue in which there are two essential, on-line decisions that have to be taken. The first is the decision to either accept or reject new type-1 or type-2 jobs. The second is the decision to abort jobs, i.e., to remove any type-1 or type-2 jobs from the system. We show that there exist optimal threshold policies for these two types of, decisions.     

Semi-Markovian decision models with vector-valued reward

The paper deals with vector-valued semi-Markovian decision process (VSMDP). Thereby we derive a suitable definition of the optimal average reward of a VSMDP. We construct an algorithm for improving policies in the vector-valued case.     

Traffic processes in a class of finite Markovian queues

This paper exposes the stochastic structure of traffic processes in a class of finite state queueing systems which are modeled in continuous time as Markov processes. The theory is presented for theM/E _k /φ/L class under a wide range of queue disciplines. Particular traffic processes of interest include the arrival, input, output, departure and overflow processes. Several examples are given which demonstrate that the theory unifies many earlier works, as well as providing some new results. Several extensions to the model are discussed.     

One-armed bandit models with continuous and delayed responses

One-armed bandit processes with continuous delayed responses are formulated as controlled stochastic processes following the Bayesian approach. It is shown that under some regularity conditions, a Gittins-like index exists which is the limit of a monotonic sequence of break-even values characterizing optimal initial selections of arms for finite horizon bandit processes. Furthermore, there is an optimal stopping solution when all observations on the unknown arm are complete. Results are illustrated with a bandit model having exponentially distributed responses, in which case the controlled stochastic process becomes a Markov decision process, the Gittins-like index is the Gittins index and the Gittins index strategy is optimal. Acknowledgement.We thank an anonymous referee for constructive and insightful comments, especially those related to the notion of the Gittins index.Both authors are funded by the Natural Sciences and Engineering Research Council (NSERC) of Canada.     

A useful technique for piecewise deterministic Markov decision processes

This note presents a technique that is useful for the study of piecewise deterministic Markov decision processes (PDMDPs) with general policies and unbounded transition intensities. This technique produces an auxiliary PDMDP from the original one. The auxiliary PDMDP possesses certain desired properties, which may not be possessed by the original PDMDP. We apply this technique to risk-sensitive PDMDPs with total cost criteria, and comment on its connection with the uniformization technique.     

Numerical methods for controlled and uncontrolled multiplexing and queueing systems

We deal with a very useful numerical method for both controlled and uncontrolled queuing and multiplexing type systems. The basic idea starts with a heavy traffic approximation, but it is shown that the results are very good even when working far from the heavy traffic regime. The underlying numerical method is a version of what is known as the Markov chain approximation method. It is a powerful methodology for controlled and uncontrolled stochastic systems, which can be approximated by diffusion or reflected diffusion type systems, and has been used with success on many other problems in stochastic control. We give a complete development of the relevant details, with an emphasis on multiplexing and particular queueing systems. The approximating process is a controlled or uncontrolled Markov chain which retains certain essential features of the original problem. This problem is generally substantially simpler than the original physical problem, and there are associated convergence theorems. The non-classical associated ergodic cost problem is derived, and put into a form such that reliable and good numerical algorithms, based on multigrid type ideas, can be used. Data for both controlled and uncontrolled problems shows the value of the method.Supported by ARO contract DAAL-03-92-G-0115, AFOSR contract F49620-92-J-0081, and DARPA contract AFOSR-91-0375.Formerly at Brown University. Supported by DARPA contract AFOSR-91-0375.     

Decomposition approximation of queueing-network control models with tree structures

We devise a decomposition approximation method for a general branching queueing network with service-rate controls. The decomposition method, which reduces and simplifies computation routines considerably, results from the conditions for monotone optimal control policies in induction arguments. We first isolate each branch of connected queues as a subnetwork and then link the subnetworks through branching nodes to approximate the optimal control policies for the global network. The numerical results for a wide class of cost models show that the approximated optimal policies from the decomposed problems are sufficiently close to the optimal policies of the global problem.     

Optimal control of a production-inventory system with customer impatience

We consider the control of a production-inventory system with impatient customers. We show that the optimal policy can be described using two thresholds: a production base-stock level that determines when production takes place and an admission threshold that determines when orders should be accepted. We describe an algorithm for computing the performance of the system for any choice of base-stock level and admission threshold. In a numerical study, we compare the performance of the optimal policy against several other policies.     

Controlled and optimally controlled multiplexing systems: A numerical exploration

Large controlled multiplexing systems are approximated by diffusion type processes yielding a very efficient way of approximation and good numerical methods. The limit equations are an efficient aggregation of the original system, and provide the basis of the actual numerical approximation to the control problem. The numerical approximations have the structure of the original problem, but are generally much simpler. The control can occur in a variety of places; e.g., leaky bucket controllers, control of marked cells at the transmitter buffer, or control of the transmitter speed. From the point of view of the limit equations, those are equivalent. Various forms of the optimal control problem are explored, where the main aim is to control or balance the losses at the control with those due to buffer overflow. It is shown that much can be saved via the use of optimal controls or reasonable approximations to them. We discuss systems with one to three classes of sources, various aggregation methods and control approximation schemes. There are qualitative comparisons of various systems with and without control and a discussion of the variations of control and performance as the systems data and control bounds vary. The approach is a very useful tool for providing both qualitative and quantitative information which would be hard to get otherwise. The results have applications to various forms of the ATM and broadband integrated data networks.The work was partially supported by AFOSR-91-0375 and (AFOSR) F49620-92-J-088-1DEF.The work was partially supported by grants (AFOSR) F49620-92-J-008-1DEF, AFOSR-91-03750.This work was partially supported by DAAH04-93-0070 (ARO) and AFOSR-91-0375.     

Optimal integrated production and inventory control of an assemble-to-order system with multiple non-unitary demand classes

We study a pure assemble-to-order system subject to multiple demand classes where customer orders arrive according to a compound Poisson process. The finished product is assembled from m different components that are produced on m distinct production facilities in a make-to-stock fashion. We show that the optimal production policy of each component is a state-dependent base-stock policy and the optimal inventory allocation policy is a multi-level state-dependent rationing policy. Using numerical experimentation, we first study the system behavior as a function of order size variability and order size. We show that the optimal average cost rate is more sensitive to order size variability than to order size. We also compare the optimal policy to the first-come first-serve policy and show that there is great benefit to inventory rationing. We also propose two simple heuristics and show that these can effectively mimic the optimal policy which is generally much more difficult to determine and, especially, to implement.     

Monotonicity in multidimensional Markov decision processes for the batch dispatch problem

Structural properties of stochastic dynamic programs are essential to understanding the nature of the solutions and in deriving appropriate approximation techniques. We concentrate on a class of multidimensional Markov decision processes and derive sufficient conditions for the monotonicity of the value functions. We illustrate our result in the case of the multiproduct batch dispatch (MBD) problem.