An Overview for Markov Decision Processes in Queues and Networks <s> (4) MDPs of multi-server queues <s> Summary An MIM/s queueing system with a simple cost structure is considered, under the assumption that the system will close in a finite time after which any remaining customers will require extra overtime service costs. We determine the optimal policy for admitting customers to the queue, as a function of the time, t, to closing and the current queue length, i. It is shown to have the form: admit if and only if fl(t) ? i ? f2(t). The bounds f,(t) and f2(t) are specified, and it is shown under what conditions fl(t) = 0 (a control limit rule) or f2(t) = oo (an inverse control limit rule). <s> BIB001 </s> An Overview for Markov Decision Processes in Queues and Networks <s> (4) MDPs of multi-server queues <s> We study the problem of optimal customer admission to multiserver queues. These queues are assumed to live in an extraneous environment which changes in a semi-Markovian way. Arrivals, service mechanism and random reward/cost structure may all depend on these surroundings. Included as special cases are SM/M/c queues, in particular G/M/c queues, in a random environment. By a direct inductive approach we establish optimality of a generalized control-limit rule depending on the actual environment. Particular emphasis is laid on different applications that show the versatility of the proposed setup. <s> BIB002 </s> An Overview for Markov Decision Processes in Queues and Networks <s> (4) MDPs of multi-server queues <s> The problem of finding an optimal admission policy to an M/M/c queue with one controlled and one uncontrolled arrival stream is addressed There are two streams of customers that are generated according to independent Poisson processes with constant arrival rates. The service time probability distribution is exponential and does not depend on the class of the customers. Upon arrival a class 1 customer may be admitted or rejected, while incoming class 2 customers are always admitted. A state-dependent reward is earned each time a new class 1 customer enters the system. When the discount factor is small, there exists a stationary admission policy of a threshold type that maximizes the expected total discounted reward over an infinite horizon. A similar result is also obtained when considering the long-run average reward criterion. The proof relies on a new device that consists of a partial construction of the solution of the dynamic programming equation. Applications arising from teletraffic analysis are proposed. > <s> BIB003 </s> An Overview for Markov Decision Processes in Queues and Networks <s> (4) MDPs of multi-server queues <s> Abstract This paper studies pricing and incentive issues in the assignment of customers to servers in a system that suffers congestion effects. When customers have private information about their waiting costs, a system administrator who wishes to maximize steady-sate net benefits per unit of time (i.e. total benefits from service minus total waiting costs) may do so using a pricing and routing scheme that is incentive compatible; that is, no customer has any incentive to reveal his private information untruthfully. When the system administrator wants to maximize toll revenue, the optimal scheme involves higher tolls, and hence lower congestion, than is socially optimal. <s> BIB004 </s> An Overview for Markov Decision Processes in Queues and Networks <s> (4) MDPs of multi-server queues <s> In a M/M/N+M queue, when there are many customers waiting, it may be preferable to reject a new arrival rather than risk that arrival later abandoning without receiving service. On the other hand, rejecting new arrivals increases the percentage of time servers are idle, which also may not be desirable. We address these trade-offs by considering an admission control problem for a M/M/N+M queue when there are costs associated with customer abandonment, server idleness, and turning away customers. First, we formulate the relevant Markov decision process (MDP), show that the optimal policy is of threshold form, and provide a simple and efficient iterative algorithm that does not presuppose a bounded state space to compute the minimum infinite horizon expected average cost and associated threshold level. Under certain conditions we can guarantee that the algorithm provides an exact optimal solution when it stops; otherwise, the algorithm stops when a provided bound on the optimality gap is reached. Next, we solve the approximating diffusion control problem (DCP) that arises in the Halfin---Whitt many-server limit regime. This allows us to establish that the parameter space has a sharp division. Specifically, there is an optimal solution with a finite threshold level when the cost of an abandonment exceeds the cost of rejecting a customer; otherwise, there is an optimal solution that exercises no control. This analysis also yields a convenient analytic expression for the infinite horizon expected average cost as a function of the threshold level. Finally, we propose a policy for the original system that is based on the DCP solution, and show that this policy is asymptotically optimal. Our extensive numerical study shows that the control that arises from solving the DCP achieves a very similar cost to the control that arises from solving the MDP, even when the number of servers is small. <s> BIB005 </s> An Overview for Markov Decision Processes in Queues and Networks <s> (4) MDPs of multi-server queues <s> We consider the problem of optimal control of a multi-server queue with controllable arrival and service rates. This study is motivated by its potential application to the design and control of data centers. The cost structure includes customer holding cost which is a non-decreasing convex function of the number of customers in the system, server operating cost which is a non-decreasing convex function of the chosen service rate, and system operating reward which is a non-decreasing concave function of the chosen arrival rate. We formulate the problem as a continuous-time Markov decision process and derive structural properties of the optimal control policies under both discounted cost and average cost criterions. <s> BIB006
Emmons BIB001 , Helm and Waldmann BIB002 , Blanc et al. BIB003 , Bradford BIB004 , Koçaǧa and Ward BIB005 and Lee and Kulkarni BIB006 .