An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Queueing Networks <s> Abstract We deal with an optimal control problem in a queuing network system. The system consists of the first stage with a server and the second stage with two servers each having its finite queue. Two types of customers are first served at the first stage server and subsequently proceed to the queue at the server corresponding to their types in the second stage. When the first stage server completes a service, he determines the type of customer to be next served. The optimal control problem is to select the type of customer to be next served in order to minimize the expected cost per hour. The problem is formulated as an undiscounted semi-Markov decision process. The monotonicity of the optimal policy is shown. <s> BIB001 </s> An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Queueing Networks <s> Laboratory for Information and Decision SystemsandOperations Research CenterMassachusetts Institute of TechnologyCambridge, MA 02139December 19921A preliminary version of this paper [BPT1] appeared in the proceedings of the "Work-shop on hierarchical control for real-time scheduling of manufacturing systems", Lincoln,New Hampshire, October 16-18, 1992. The full paper was presented in the ORSA/TIMSconference [BPT2] on November 2, 1992.Research supported by the National Science Foundation under Grant ECS-8552419, by aPresidential Young Investigator award DDM-9158118 with matching funds from DraperLaboratory, by the Leaders for Manufacturing Program at MIT, and by the ARO undergrand DAAL03-92-G0309. <s> BIB002 </s> An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Queueing Networks <s> This paper considers in parallel the scheduling problem for multiclass queueing networks, and optimization of Markov decision processes. It is shown that the value iteration algorithm may perform poorly when the algorithm is not initialized properly. The algorithm is initialized with a stochastic Lyapunov function, then convergence is guaranteed, and each policy is stabilized. For the network scheduling problem it is argued that a natural choice for the initial value function is the value function for the associated deterministic control problem based upon a fluid model, or the approximate solution to Poisson's equation obtained from the LP of Kumar and Meyn (1996). Numerical studies show that either choice may lead to fast convergence to an optimal policy. <s> BIB003 </s> An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Queueing Networks <s> We consider a general control problem for networks with linear dynamics which includes the special cases of scheduling in multiclass queueing networks and routeing problems. The fluid approximation of the network is used to derive new results about the optimal control for the stochastic network. The main emphasis lies on the average-cost criterion; however, the 0f-discounted as well as the finite-cost problems are also investigated. One of our main results states that the fluid problem provides a lower bound to the stochastic network problem. For scheduling problems in multiclass queueing networks we show the existence of an average-cost optimal decision rule, if the usual traffic conditions are satisfied. Moreover, we give under the same conditions a simple stabilizing scheduling policy. Another important issue that we address is the construction of simple asymptotically optimal decision rules. Asymptotic optimality is here seen with respect to fluid scaling. We show that every minimizer of the optimality equation is asymptotically optimal and, what is more important for practical purposes, we outline a general way to identify fluid optimal feedback rules as asymptotically optimal. Last, but not least, for routeing problems an asymptotically optimal decision rule is given explicitly, namely a so-called least-loaded-routeing rule. <s> BIB004 </s> An Overview for Markov Decision Processes in Queues and Networks <s> MDPs of Queueing Networks <s> It is well known that the $$c\mu $$cμ-rule is optimal for serving multiple types of customers to minimize the expected total waiting cost. What happens when less valuable customers (those with lower $$c\mu $$cμ) can change to valuable ones? In this paper, we study this problem by considering two types of customers. The first type of customers is less valuable, but it may change to the second type (i.e., more valuable customers) after a random amount of time. The resulting problem is a continuous-time Markov decision process with countable state space and unbounded transition rates, which is known to be technically challenging. We first prove the existence of optimal non-idling stationary policies. Based on the smoothed rate truncation, we derive conditions under which a modified $$c\mu $$cμ-rule remains optimal. For other cases, we develop a simple heuristic policy for serving customers. Our numerical study shows that the heuristic policy performs close to the optimal, with the worst case within 2.47 % of the optimal solution and 95 % of the examples within 1 % of the optimal solution. <s> BIB005
In this section, we provide an overview for MDPs of queueing networks. Note that the MDPs of queueing networks have been an interesting research direction for many years, and they have also established key applications in many practical areas. (1) MDPs of queueing networks  BIB004 and Solodyannikov  . (2) MDPs of queueing networks with multiple classes of customers Shioyama BIB001 , Bertsimas et al. BIB002 , Maglaras  , Chen and Meyn BIB003 and Cao and Xie BIB005 .