A survey of Markov decision models for control of networks of queues
---
paper_title: Controlled Markov Chains and Stochastic Networks

paper_content:

Controlled Markov chains with average cost criterion and with special cost and transition structures are studied. Existence of optimal stationary strategies is established for the average cost criterion. Corresponding dynamic programming equations are derived. A stochastic network problem that includes interconnected queues as a special case is described and studied within this framework.
---
paper_title: Discrete-time controlled Markov processes with average cost criterion: a survey

paper_content:

This work is a survey of the average cost control problem for discrete-time Markov processes. The authors have attempted to put together a comprehensive account of the considerable research on this problem over the past three decades. The exposition ranges from finite to Borel state and action spaces and includes a variety of methodologies to find and characterize optimal policies. The authors have included a brief historical perspective of the research efforts in this area and have compiled a substantial yet not exhaustive bibliography. The authors have also identified several important questions that are still open to investigation.
---
paper_title: Recent results on conditions for the existence of average optimal stationary policies

paper_content:

This paper concerns countable state space Markov decision processes endowed with a (long-run expected)average reward criterion. For these models we summarize and, in some cases,extend some recent results on sufficient conditions to establish the existence of optimal stationary policies. The topics considered are the following: (i) the new assumptions introduced by Sennott in [20–23], (ii)necessary and sufficient conditions for the existence of a bounded solution to the optimality equation, and (iii) equivalence of average optimality criteria. Some problems are posed.
---
paper_title: Control of Markov Chains with Long-Run Average Cost Criterion: The Dynamic Programming Equations

paper_content:

The long-run average cost control problem for discrete time Markov chains on a countable state space is studied in a very general framework. Necessary and sufficient conditions for optimality in terms of the dynamic programming equations are given when an optimal stable stationary strategy is known to exist (e.g., for the situations studied in [Stochastic Differential Systems, Stochastic Control Theory and Applications, IMA Vol. Math. App. 10, Springer-Verlag, New York, Berlin, 1988, pp. 57–77]). A characterization of the desired solution of the dynamic programming equations is given in a special case. Also included is a novel convex analytic argument for deducing the existence of an optimal stable stationary.strategy when that of a randomized one is known.
---
paper_title: Control of Markov Chains with Long-Run Average Cost Criterion

paper_content:

The long-run average cost control problem for discrete time Markov chains is studied in an extremely general framework. Existence of stable stationary strategies which are optimal in the appropriate sense is established and these are characterized via the dynamic programming equations. The approach here differs from the conventional approach via the discounted cost problem and covers situations not covered by the latter.
---
paper_title: Necessary conditions for the optimality equation in average-reward Markov decision processes

paper_content:

An average-reward Markov decision process (MDP) with discretetime parameter, denumerable state space, and bounded reward function is considered. With such a model, we associate a family of MDPs. Then, we determinenecessary conditions for the existence of a bounded solution to the optimality equation for each one of the models in the family. Moreover,necessary andsufficient conditions are given so that the optimality equations have a bounded solution with an additional property.
---
paper_title: Scheduling, Routing, and Flow Control in Stochastic Networks

paper_content:

Queueing models are frequently helpful in the analysis and control of communication, manufacturing, and transportation systems. The theory of Markov decision processes and the inductive techniques of dynamic programming have been used to develop normative models for optimal control of admission, servicing, routing, and scheduling of jobs in queues and networks of queues. We review some of these models, beginning with single-facility models and then progressing to models for networks of queues. We emphasize the use of induction on a sequence of successive approximations of the optimal value function (value iteration) to establish the form of optimal control policies.
---
paper_title: Monotone Control of Queueing and Production/Inventory Systems

paper_content:

Weber and Stidham (1987) used submodularity to establish transition monotonicity (a service completion at one station cannot reduce the service rate at another station) for Markovian queueing networks that meet certain regularity conditions and are controlled to minimize service and queueing costs. We give an extension of monotonicity to other directions in the state space, such as arrival transitions, and to arrival routing problems. The conditions used to establish monotonicity, which deal with the boundary of the state space, are easily verified for many queueing systems. We also show that, without service costs, transition-monotone controls can be described by simple control regions and switching functions, extending earlier results. The theory is applied to production/inventory systems with holding costs at each stage and finished goods backorder costs.
---
paper_title: Monotone Optimal Control of Permutable GSMPs

paper_content:

We consider Markovian GSMPs (generalized semi-Markov processes) in which the rates of events are subject to control. A control is monotone if the rate of one event is increasing or decreasing in the number of occurrences of other events. We give general conditions for the existence of monotone optimal controls. The conditions are functional properties for the one-step cost functions and, more importantly, structural properties for the GSMP. The main conditions on costs are submodularity or supermodularity with respect to pairs of events. The key structural condition is strong permutability , requiring that the state at any time be determined by the number of events of each type that have occurred, regardless of their order. This permits a reformulation of the original control problem into one based only on event counting processes. This reformulation leads to a unified treatment of a broad class of models and to meaningful generality beyond existing results.
---
paper_title: Extremal Splittings of Point Processes

paper_content:

The sequence with nth term defined by [(n + 1)p] − [np] is an extremal zero-one valued sequence of asymptotic mean p in the following sense (for example): if a fraction p of customers from a point process with iid interarrival times is sent to an exponential server queue according to a prespecified splitting sequence, then the long-term average queue size is minimized when the above sequence is used. The proof involves consideration of the lower convex envelope J (which is a function on Rm) of a function J on Zm. An explicit representation is given for J in terms of J, for J in a broad class of functions, which we call “multimodular.” The expected queue size just before an arrival, considered as a function of the zero-one splitting sequence, is shown to belong to this class.
---
paper_title: Monotone Control of Queueing and Production/Inventory Systems

paper_content:

Weber and Stidham (1987) used submodularity to establish transition monotonicity (a service completion at one station cannot reduce the service rate at another station) for Markovian queueing networks that meet certain regularity conditions and are controlled to minimize service and queueing costs. We give an extension of monotonicity to other directions in the state space, such as arrival transitions, and to arrival routing problems. The conditions used to establish monotonicity, which deal with the boundary of the state space, are easily verified for many queueing systems. We also show that, without service costs, transition-monotone controls can be described by simple control regions and switching functions, extending earlier results. The theory is applied to production/inventory systems with holding costs at each stage and finished goods backorder costs.
---
paper_title: Minimizing a Submodular Function on a Lattice

paper_content:

This paper gives general conditions under which a collection of optimization problems, with the objective function and the constraint set depending on a parameter, has optimal solutions that are an isotone function of the parameter. Relating to this, we present a theory that explores and elaborates on the problem of minimizing a submodular function on a lattice.
---
paper_title: Optimal control of two interacting service stations

paper_content:

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.
---
paper_title: On the Optimality of the Generalized Shortest Queue Policy

paper_content:

Consider a queueing model in which arriving customers have to choose between m parallel servers, each with its own queue. We prove for general arrival streams that the policy which assigns to the shortest queue is stochastically optimal for models with finite buffers and batch arrivals.
---
paper_title: On the Optimality of the Generalized Shortest Queue Policy

paper_content:

Consider a queueing model in which arriving customers have to choose between m parallel servers, each with its own queue. We prove for general arrival streams that the policy which assigns to the shortest queue is stochastically optimal for models with finite buffers and batch arrivals.
---
paper_title: Optimal control of two interacting service stations

paper_content:

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.
---
paper_title: Optimal control of a queueing system with two heterogeneous servers

paper_content:

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.
---
paper_title: On decentralized dynamic routing for congested traffic networks

paper_content:

The problem of routing traffic through single destination congested networks is considered, when the network has deterministic inputs and may contain looping paths. A decentralized dynamic routing strategy is proposed which assures that no traffic is directed around loops.
---
paper_title: The optimal control of heterogeneous queueing systems: a paradigm for load-sharing and routing

paper_content:

The essence of the basic control decisions implicit in load-sharing and routing algorithms is captured in a simple model of heterogeneous queue control. The authors solve for the optimal control policy and investigate the performance of previously proposed policies in a tractable limit of this model. Using their understanding of this solvable limit, the authors propose heuristic policies for the general model. Simulation data for these policies suggest that they perform well over a wide range of system parameters. >
---
paper_title: Martingale dynamics and optimal routing in a network

paper_content:

In this paper, we consider a dynamic routing problem in a store-and-forward computer-communication network which consists of l parallel channels connected between the source and the destination. We prove that if messages arrive at the network in accordance with a Poisson process and all nodes have an exponential service rate, then the routing strategy that minimizes the total expected time in transmitting all messages that arrive before T>0 is to route the arriving message to the channel along which the sum of all queue sizes is minimum. Techniques of martingale and dynamic programming are used in obtaining the result.
---
paper_title: The Join-Biased-Queue Rule and Its Application to Routing in Computer Communication Networks

paper_content:

A routing rule similar in nature to delta-routing [8] is studied in this paper. The approach is to superimpose, local adaptivity on top of a fixed traffic flow distribution. The fixed flow distribution we choose is obtained from the best stochastic (BS) rule [3]. The adaptive part is called the join-biased-queue (JBQ) rule. The resultant JBQ-BS rule is analyzed on small networks and is shown to provide 10-27 percent delay improvement over the BS rule.
---
paper_title: Optimal control of two interacting service stations

paper_content:

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.
---
paper_title: Dynamic Scheduling of a Multiclass Queue: Discount Optimality

paper_content:

We consider a single-server queuing system with several classes of customers who arrive according to independent Poisson processes. The service time distributions are arbitrary, and we assume a linear cost structure. The problem is to decide, at the completion of each service and given the state of the system, which class (if any) to admit next into service. The objective is to maximize the expected net present value of service rewards received minus holding costs incurred over an infinite planning horizon, the interest rate being positive. One very special type of scheduling rule, called a modified static policy, simply enforces a (nonpreemptive) priority ranking except that certain classes are never served. It is shown that there is a modified static policy that is optimal, and a simple algorithm for its computation is presented.
---
paper_title: Interchange arguments for classical scheduling problems in queues

paper_content:

Abstract Simple interchange arguments are applied for solving classical scheduling problems in queues. We first show that the μc- rule minimizes a fairly general cost function in a multiclass ·/M/1 queue. Then, we address the same problem when partial feedback and change of class are allowed. Finally, we consider two ·/M/1 queues in series and we show that the μc-rule is always optimal in the second node.
---
paper_title: Interchange Arguments in Stochastic Scheduling.

paper_content:

Interchange arguments are applied to establish the optimality of priority list policies in three problems. First, we prove that in a multiclass tandem of two · /M/1 queues it is always optimal in the second node to serve according to the cp rule. The result holds more generally if the first node is replaced by a multiclass network consisting of ·/M/1 queues with Bernoulli routing. Next, for scheduling a single server in a multiclass node with feedback, a simplified proof of Klimov's result is given. From it follows the optimality of the index rule among idling policies for general service time distributions, and among pre-emptive policies when the service time distributions are exponential. Lastly, we consider the problem of minimizing the blocking in a communication link with lossy channels and exponential holding times.
---
paper_title: A Priority Queue with Discounted Linear Costs

paper_content:

We consider a nonpreemptive priority queue with a finite number of priority classes, Poisson arrival processes, and general service time distributions. It is not required that the system be stable or even that the mean service times be finite. The economic framework is linear, consisting of a holding cost per unit time and fixed service reward for each customer class. Future costs and rewards are continuously discounted with a positive interest rate. Allowing general initial queue sizes, we develop an expression for the expected present value of rewards received minus costs incurred over an infinite horizon. From this we obtain the Laplace transform of the time-dependent expected queue length for each customer class.
---
paper_title: Optimal scheduling in some multi-queue single-server systems

paper_content:

The server visits N queues in an arbitrary manner. Each queue is visited for a random period of time whose duration is sampled in advance. At the end of a visit period, either all customers of the attended queue leave the system (variant I) or only customers that were present in the queue upon the arrival of the server leave the system (variant II). A scheduling policy is a rule that selects the next queue to be visited by the server. When the controller has no information on the state of the system, it is shown, under homogeneous arrival assumptions, that a cyclic policy minimizes the expected number of customers in the system. When the controller knows the number of customers in each queue, it is shown that the so-called most-customers-first (MCF) policy minimizes, in the sense of strong stochastic ordering, the vector of the number of customers in each queue whose components are arranged in decreasing order. These results hold for variants I and II and are obtained under fairly weak statistical assumptions. This model has potential applications in videotex and time-division multiple-access systems. >
---
paper_title: Recent results on conditions for the existence of average optimal stationary policies

paper_content:

This paper concerns countable state space Markov decision processes endowed with a (long-run expected)average reward criterion. For these models we summarize and, in some cases,extend some recent results on sufficient conditions to establish the existence of optimal stationary policies. The topics considered are the following: (i) the new assumptions introduced by Sennott in [20–23], (ii)necessary and sufficient conditions for the existence of a bounded solution to the optimality equation, and (iii) equivalence of average optimality criteria. Some problems are posed.
---
paper_title: Necessary conditions for the optimality equation in average-reward Markov decision processes

paper_content:

An average-reward Markov decision process (MDP) with discretetime parameter, denumerable state space, and bounded reward function is considered. With such a model, we associate a family of MDPs. Then, we determinenecessary conditions for the existence of a bounded solution to the optimality equation for each one of the models in the family. Moreover,necessary andsufficient conditions are given so that the optimality equations have a bounded solution with an additional property.
---

Title: A Survey of Markov Decision Models for Control of Networks of Queues

Section 1: Introduction
Description 1: Introduce the context and importance of using Markov decision models for the control of networks of queues. Discuss the focus of the survey, including the types of control (service rates, admission, routing, and scheduling).

Section 2: Control of transitions in a Markov process: A general model
Description 2: Present a general model for controlling the transition rates in a continuous-time Markov chain. Explain the framework and its applications to queue networks.

Section 3: Control of service rates in a network of queues
Description 3: Apply the general model to the control of service rates at the nodes of a network of queues, illustrating with specific structures like cycles and series of queues. Discuss optimal policies such as bang-bang controls and kanban policies.

Section 4: Control of admission to the first queue
Description 4: Explore the structure of optimal policies for the control of arrivals to the first node in a series of queues, including admission/rejection decisions.

Section 5: Control of arrivals to each of two queues in series
Description 5: Discuss models and results for controlling arrivals to two queues in series, highlighting the structure of optimal policies and its practical implications.

Section 6: Control of admission, routing, and server allocation in parallel queues
Description 6: Examine the control of admission, routing, and server allocation in systems with parallel queues, including symmetric cases and optimal policies like the join-the-shortest-queue rule.

Section 7: Routing to parallel servers from a common queue
Description 7: Investigate optimal routing strategies when customers enter a common buffer and are subsequently assigned to parallel servers, compared to separate queue models.

Section 8: Other routing models
Description 8: Review additional routing models, including the join-biased-shortest-queue rule and numerical approaches for optimal routing and flow-control policies.

Section 9: Scheduling in networks of queues
Description 9: Discuss scheduling problems in networked queues, where decisions about which class of customers to process are made dynamically. Highlight key results and optimal policies, including index rules and Brownian network approximations.

Section 10: Scheduling a series system with constant service times
Description 10: Conclude the survey by illustrating a scheduling problem in a series system with constant service times, detailing the optimal scheduling rules and their derivations.