An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Multi-Server Queues <s> We consider the problem of maximizing the long-run average expected reward per unit time in a queuing-reward system, which we formulate as a semi-Markov decision process. Control of the system is effected by increasing or decreasing the price charged for the facility's service in order to discourage or encourage the arrival of customers. We assume that the arrival process is Poisson with arrival rate a strictly decreasing function of the currently advertized price, and that the service times are independent exponentially distributed random variables. The reward structure consists of customer payments and holding costs possibly nonlinear. At each transition customer arrival or service completion, the manager of the facility must choose one of a finite number of prices to advertize until the next transition. We show that there exist optimal stationary policies and that each possesses the monotonicity property: the optimal price to advertize is a nondecreasing function of the number of customers in the system. An efficient computational algorithm is developed that, in a finite number of steps, produces a stationary policy that is optimal. <s> BIB001 </s> An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Multi-Server Queues <s> Optimal controls described by switching curves in the two dimensional state space are shown to exist for the optimal control of a Markov network with two service stations and linear cost. The controls govern routing and service priorities. Finite horizon and long run average cost problems are considered. An example is given which shows that nonconvex value functions can arise for slightly more general networks. A single station control problem with nonconvex value functions is then considered to indicate how switch structure might be established more generally. <s> BIB002 </s> An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Multi-Server Queues <s> In this article we consider the optimal control of an M[X]/M/s queue, s ≧ 1. In addition to Poisson bulk arrivals we incorporate a reneging function. Subject to control are an admission price p and the service rate μ. Thus, through p, balking response is induced. When i customers are present a cost h(i,μ,p) per unit time is incurred, discounted continuously. Formulated as a continuous time Markov decision process, conditions are given under which the optimal admission price and optimal service rate are each nondecreasing functions of i. In Section 4 we indicate how the infinite state space may be truncated to a finite state space for computational purposes. <s> BIB003 </s> An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Multi-Server Queues <s> We consider a GI/M/s queuing system that is controlled by either accepting or rejecting arriving customers. Under weak conditions on the cost structure, Stidham Stidham, S., Jr., 1978. Socially and individually optimal control of arrivals to a GI/M/1 queue. Management Sci.24 1598-1610. showed that a control limit policy is optimal. In this paper we show how the special structure of this queuing system can be exploited to develop efficient procedures to determine an optimal control limit. An explicit algorithm for computing the optimal control as well as an example and some computational results are included. <s> BIB004 </s> An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Multi-Server Queues <s> A dynamic control policy known as "threshold queueing" is defined for scheduling customers from a Poisson source on a set of two exponential servers with dissimilar service rates. The slower server is invoked in response to instantaneous system loading as measured by the length of the queue of waiting customers. In a threshold queueing policy, a specific queue length is identified as a "threshold," beyond which the slower server is invoked. The slower server remains busy until it completes service on a customer and the queue length is less than its invocation threshold. Markov chain analysis is employed to analyze the performance of the threshold queueing policy and to develop optimality criteria. It is shown that probabilistic control is sub-optimal to minimize the mean number of customers in the system. An approximation to the optimum policy is analyzed which is computationally simple and suffices for most operational applications. <s> BIB005 </s> An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Multi-Server Queues <s> The problem considered is that of optimally controlling a queueing system which consists of a common buffer or queue served by two servers. The arrivals to the buffer are Poisson and the servers are both exponential, but with different mean service times. It is shown that the optimal policy which minimizes the mean sojourn time of customers in the system is of threshold type. The faster server should be fed a customer from the buffer whenever it becomes available for service, but the slower server should be utilized if and only if the queue length exceeds a readily computed threshold value. <s> BIB006 </s> An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Multi-Server Queues <s> The author deals with the problem of optimal allocation of customers in a two-server queue with heterogeneous service rates and resequencing. The resequencing constraint ensures that the customers leave the system in the order in which they entered it. It is shown that the optimal policy that minimizes the average end-to-end delay of customers in the system is independent of the number of customers in the resequencing buffer. Moreover, it is also shown that the faster server should be kept busy whenever possible and that the optimal control of the slower server is of the threshold type in the number of customers in the main queue buffer. > <s> BIB007 </s> An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Multi-Server Queues <s> Consider a two-station queueing network with two types of jobs: type 1 jobs visit station 1 only, while type 2 jobs visit both stations in sequence. Each station has a single server. Arrival and service processes are modeled as counting processes with controllable stochastic intensities. The problem is to control the arrival and service processes, and in particular to schedule the server in station 1 among the two job types, in order to minimize a discounted cost function over an infinite time horizon. Using a stochastic intensity control approach, we establish the optimality of a specific stationary policy, and show that its value function satisfies certain properties, which lead to a switching-curve structure. We further classify the problem into six parametric cases. Based on the structural properties of the stationary policy, we establish the optimality of some simple priority rules for three of the six cases, and develop heuristic policies for the other three cases. <s> BIB008 </s> An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Multi-Server Queues <s> This paper studies optimal routing and jockeying policies in a two-station parallel queueing system. It is assumed that jobs arrive to the system in a Poisson stream with rate A and are routed to one of two parallel stations. Each station has a single server and a buffer of infinite capacity. The service times are exponential with server-dependent rates, μ 1 and μ 2 . Jockeying between stations is permitted. The jockeying cost is c ij when a job in station i jockeys to station j, i¬=j. There is no cost when a new job joins either station. The holding cost in station j is h j , h 1 ≤ h 2 , per job per unit time. We characterize the structure of the dynamic routing and jockeying policies that minimize the expected total (holding plus jockeying) cost, for both discounted and long-run average cost criteria. We show that the optimal routing and jockeying controls are described by three monotonically non-decreasing functions. We study the properties of these control functions, their relationships, and their asymptotic behavior. We show that some well-known queueing control models, such as optimal routing to symmetric and asymmetric queues, preemptive or non-preemptive scheduling on homogeneous or heterogeneous servers, are special cases of our system. <s> BIB009 </s> An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Multi-Server Queues <s> We study a system where the service provider offers priority options. We identify the optimal option pricing policy, by deriving the optimal number a customer would buy and the customer's exercise policy as a function of system congestion, options remaining, time to expiration and possibility of balking. <s> BIB010 </s> An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Multi-Server Queues <s> We consider an M/M/k/N queue with m customer types, where m ≥ 1. Customers of type j, j = 1, 2, . . . ,m, arrive at the system according to independent Poisson processes with rates λj , where 0 r1 > r2 > ... > rm > 0. Moreover, we assume that the system manager is aware of these rewards in the market and no customer in the market is willing to pay more than r1 for service. When there are n customers in the system, the system manager posts a price pn, 0 r1 and all arrivals are rejected. In addition, the system manager may reject all arrivals before the system is full by posting the price r0. The objective is to maximize the revenue of the system under average reward criterion. We call a policy that maximizes the revenue an optimal policy. In addition to op- <s> BIB011 </s> An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Multi-Server Queues <s> This paper studies optimal pricing for a GI/M/k/N queueing system with several types of customers. An arrival joins the queue if the price of service is not higher than the maximum amount that the arrival is willing to pay, and this maximum amount is defined by the customer type. A system manager chooses a price depending on the number of customers in the system. In addition, the system incurs holding costs when there are customers waiting in the queue for their services. Service times and holding costs do not depend on customer types. The holding costs are nondecreasing and convex with respect to the number of customers in the queue. This paper describes average reward optimal, canonical, bias optimal, and Blackwell optimal policies for this pricing problem. <s> BIB012
In this section, we provide an overview for MDPs of multi-server queues, which are another important research direction. (1) MDPs of M/M/c queues Low BIB001 , Anderson BIB003 , Printezis and Burnetas BIB010 and Feinber and Yang BIB011 . (2) MDPs of GI/M/c queues Yechiali  , Van Nunen and Puterman BIB004 and Feinberg and Yang BIB012 . (3) MDPs of two-server queues Larsen and Agrawala BIB005 , Lin and Kumar BIB006 , Hajek BIB002 , Varma BIB007 , Chen et al. BIB008 and Xu and Zhao BIB009 .