Multi-layered round robin routing for parallel servers

We study a system of several identical servers in parallel, where a routing decision must be made immediately on a job’s arrival. Jobs arrive according to a Poisson process, with their processing times following a discrete distribution with finite support. The processing time of a job is known on arrival and may be used in the routing decision. We propose a policy consisting of multi-layered round robin routing followed by shortest remaining processing time scheduling at the servers. This policy is shown to have a heavy traffic limit that is identical to one in which there is a single queue (no routing) and optimal heavy traffic scheduling. In light traffic, we show that the performance of this policy is worse than round robin routing followed by shortest remaining processing time scheduling. We also quantify the difference between round robin and multi-layered round robin routing, which in turn yields insights on the relative importance of routing versus (local) scheduling in such systems. AMS subject classifications: 68M20 · 60K25 (Work done while both authors were visitors at EURANDOM, P.O. Box 513, 5600 MB Eindhoven, The Netherlands.)     

Heavy traffic resource pooling in parallel‐server systems

We consider a queueing system with r non‐identical servers working in parallel, exogenous arrivals into m different job classes, and linear holding costs for each class. Each arrival requires a single service, which may be provided by any of several different servers in our general formulation; the service time distribution depends on both the job class being processed and the server selected. The system manager seeks to minimize holding costs by dynamically scheduling waiting jobs onto available servers. A linear program involving only first‐moment data (average arrival rates and mean service times) is used to define heavy traffic for a system of this form, and also to articulate a condition of overlapping server capabilities which leads to resource pooling in the heavy traffic limit. Assuming that the latter condition holds, we rescale time and state space in standard fashion, then identify a Brownian control problem that is the formal heavy traffic limit of our rescaled scheduling problem. Because of the assumed overlap in server capabilities, the limiting Brownian control problem is effectively one‐dimensional, and it admits a pathwise optimal solution. That is, in the limiting Brownian control problem the multiple servers of our original model merge to form a single pool of service capacity, and there exists a dynamic control policy which minimizes cumulative cost incurred up to any time t with probability one. Interpreted in our original problem context, the Brownian solution suggests the following: virtually all backlogged work should be held in one particular job class, and all servers can and should be productively employed except when the total backlog is small. It is conjectured that such ideal system behavior can be approached using a family of relatively simple scheduling policies related to the cμ rule. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Performance-based routing

In many-server systems with heterogeneous servers, the Fastest-Server-First (FSF) policy is known for its excellent performance. However, when service rates are unknown and/or time-varying, implementing FSF routing is not straightforward. We analyze an algorithm that approximates FSF routing: servers are ranked in a dynamic list, where the shorter the actual service times that a server exhibits—the closer the server is to the head of the list; a customer is then routed to the lowest-index (highest-in-the-list) idle server.     

Critical Thresholds for Dynamic Routing in Queueing Networks

This paper studies dynamic routing in a parallel server queueing network with a single Poisson arrival process and two servers with exponential processing times of different rates. Each customer must be routed at the time of arrival to one of the two queues in the network. We establish that this system operating under a threshold policy can be well approximated by a one-dimensional reflected Brownian motion when the arrival rate to the network is close to the processing capacity of the two servers. As the heavy traffic limit is approached, thresholds which grow at a logarithmic rate are critical in determining the behavior of the limiting system. We provide necessary and sufficient conditions on the growth rate of the threshold for (i) approximation of the network by a reflected Brownian motion (ii) positive recurrence of the limiting Brownian diffusion and (iii) asymptotic optimality of the threshold policy.     

Dynamic scheduling for minimum delay in tandem and parallel constrained queueing models

The optimal scheduling problem in two queueing models arising in multihop radio networks with scheduled link activation is investigated. A tandem radio network is considered. Each node receives exogenous arriving packets which are stored in its unlimited capacity buffer. Links adjacent to the same node cannot transmit simultaneously because of radio interference constraints. The problem of link activation scheduling for minimum delay is studied for two different traffic types. In the first type all packets have a common destination that is one end-node of the tandem. In this case the system is modeled by a tandem queueing network with dependent servers. The server scheduling policy that minimizes the delay is obtained. In the second type of traffic, the destination of each packet is an immediate neighbor of the node at which the packet enters the network. In this case the system corresponds to a set of parallel queues with dependent servers. It is shown that the optimal policy activates the servers so that the maximum number of packets are served at each slot.     

An analysis of Klimov's problem with parallel servers

We introduce a family of undiscounted branching bandits on parallel servers under controls which can impose priorities between customer classes. This family can be used to model a wide range of multi-class queueing scheduling problems, with the capacity to incorporate problem features such as machine breakdowns, complex patterns of preemption/non-preemption and semi-Markov extensions. An index policy (which we call Klimov's rule) is developed which is optimal in the particular case of a single server. An expression for its cost suboptimality is given for parallel servers. Under additional conditions on the nature of the stochastic evolution of the systems concerned, the policy is shown to be asymptotically optimal in a heavy traffic limit. These general results are utilised to develop an analysis of the index policy for a parallel server version of Klimov's classical M/GI/1 system with Bernoulli feedback. This work was supported by the Engineering and Physical Research Council through the award of grant GR/M09308. The author would also like to express his appreciation to Professor I. C. Paschalidis for helpful discussions on Klimov's problem and to Professors J. Niño-Mora and G. Weiss for many discussions and much encouragement     

Optimal assignment of servers to tasks when collaboration is inefficient

Consider a Markovian system of two stations in tandem with finite intermediate buffer and two servers. The servers are heterogeneous, flexible, and more efficient when they work on their own than when they collaborate. We determine how the servers should be assigned dynamically to the stations with the goal of maximizing the system throughput. We show that the optimal policy depends on whether or not one server is dominant (i.e., faster at both stations) and on the magnitude of the efficiency loss of collaborating servers. In particular, if one server is dominant then he must divide his time between the two stations, and we identify the threshold policy the dominant server should use; otherwise each server should focus on the station where he is the faster server. In all cases, servers only collaborate to avoid idleness when the first station is blocked or the second station is starved, and we determine when collaboration is preferable to idleness as a function of the efficiency loss of collaborating servers.     

Flexible servers in tandem lines with setup costs

We study the dynamic assignment of flexible servers to stations in the presence of setup costs that are incurred when servers move between stations. The goal is to maximize the long-run average profit. We provide a general problem formulation and some structural results, and then concentrate on tandem lines with two stations, two servers, and a finite buffer between the stations. We investigate how the optimal server assignment policy for such systems depends on the magnitude of the setup costs, as well as on the homogeneity of servers and tasks. More specifically, for systems with either homogeneous servers or homogeneous tasks, small buffer sizes, and constant setup cost, we prove the optimality of “multiple threshold” policies (where servers’ movement between stations depends on both the number of jobs in the system and the locations of the servers) and determine the values of the thresholds. For systems with heterogeneous servers and tasks, small buffers, and constant setup cost, we provide results that partially characterize the optimal server assignment policy. Finally, for systems with larger buffer sizes and various service rate and setup cost configurations, we present structural results for the optimal policy and provide numerical results that strongly support the optimality of multiple threshold policies.     

Dynamic scheduling of a single-server two-class queue with constant retrial policy

We analyze the non-preemptive assignment of a single server to two infinite-capacity retrial queues. Customers arrive at both queues according to Poisson processes. They are served on first-come-first-served basis following a cost-optimal routing policy. The customer at the head of a queue generates a Poisson stream of repeated requests for service, that is, we have a constant retrial policy. All service times are exponential, with rates depending on the queues. The costs to be minimized consist of costs per unit time that a customer spends in the system. In case of a scheduling problem that arise when no new customers arrive an explicit condition for server allocation to the first or the second queue is given. The condition presented covers all possible parameter choices. For scheduling that also considers new arrivals, we present the conditions under which server assignment to either queue 1 or queue 2 is cost-optimal.     

Analysis of job assignment with batch arrivals among heterogeneous servers

We revisit the problem of job assignment to multiple heterogeneous servers in parallel. The system under consideration, however, has a few unique features. Specifically, repair jobs arrive to the queueing system in batches according to a Poisson process. In addition, servers are heterogeneous and the service time distributions of the individual servers are general. The objective is to optimally assign each job within a batch arrival to minimize the long-run average number of jobs in the entire system. We focus on the class of static assignment policies where jobs are routed to servers upon arrival according to pre-determined probabilities. We solve the model analytically and derive the structural properties of the optimal static assignment. We show that when the traffic is below a certain threshold, it is better to not assign any jobs to slower servers. As traffic increases (either due to an increase in job arrival rate or batch size), more slower servers will be utilized. We give an explicit formula for computing the threshold. Finally we compare and evaluate the performance of the static assignment policy to two dynamic policies, specifically the shortest expected completion policy and the shortest queue policy.     

A blind policy for equalizing cumulative idleness

We consider a system with a single queue and multiple server pools of heterogeneous exponential servers. The system operates under a policy that always routes a job to the pool with longest cumulative idleness among pools with available servers, in an attempt to achieve fairness toward servers. It is easy to find examples of a system with a fixed number of servers, for which fairness is not achieved by this policy in any reasonable sense. Our main result shows that in the many-server regime of Halfin and Whitt, the policy does attain equalization of cumulative idleness, and that the equalization time, defined within any given precision level, remains bounded in the limit. An important feature of this policy is that it acts ‘blindly’, in that it requires no information on the service or arrival rates.     

Towards minimum loss job routing to parallel heterogeneous multiserver queues via index policies

This paper considers a Markovian model for the optimal dynamic routing of homogeneous traffic to parallel heterogeneous queues, each having its own finite input buffer and server pool, where buffer and server-pool sizes, as well as service rates, may differ across queues. The main goal is to identify a heuristic index-based routing policy with low complexity that consistently attains a nearly minimum average loss rate (or, equivalently, maximum throughput rate). A second goal is to compare alternative policies, with respect to computational demands and empirical performance. A novel routing policy that can be efficiently computed is developed based on a second-order extension to Whittle’s restless bandit (RB) index, since the latter is constant for this model. New results are also given for the more computationally demanding index policy obtained via policy improvement (PI), including that it reduces to shortest queue routing under symmetric buffer and server-pool sizes. A numerical study shows that the proposed RB index policy is nearly optimal across the instances considered, and substantially outperforms several previously proposed index policies.     

On optimal polling policies

In a single-server polling system, the server visits the queues according to a routing policy and while at a queue, serves some or all of the customers there according to a service policy. A polling (or scheduling) policy is a sequence of decisions on whether to serve a customer, idle the server, or switch the server to another queue. The goal of this paper is to find polling policies that stochastically minimize the unfinished work and the number of customers in the system at all times. This optimization problem is decomposed into three subproblems: determine the optimal action (i.e., serve, switch, idle) when the server is at a nonempty queue; determine the optimal action (i.e., switch, idle) when the server empties a queue; determine the optimal routing (i.e., choice of the queue) when the server decides to switch. Under fairly general assumptions, we show for the first subproblem that optimal policies are greedy and exhaustive, i.e., the server should neither idle nor switch when it is at a nonempty queue. For the second subproblem, we prove that in symmetric polling systems patient policies are optimal, i.e., the server should stay idling at the last visited queue whenever the system is empty. When the system is slotted, we further prove that non-idling and impatient policies are optimal. For the third subproblem, we establish that in symmetric polling systems optimal policies belong to the class of Stochastically Largest Queue (SLQ) policies. An SLQ policy is one that never routes the server to a queue known to have a queue length that is stochastically smaller than that of another queue. This result implies, in particular, that the policy that routes the server to the queue with the largest queue length is optimal when all queue lengths are known and that the cyclic routing policy is optimal in the case that the only information available is the previous decisions.This work was supported in part by NSF under Contract ASC-8802764.     

A stochastic and dynamic routing policy using branching processes with state dependent immigration

A stochastic and dynamic vehicle routing problem called the Dynamic Traveling Repairman Problem (DTRP) was introduced by Bertsimas and van Ryzin. Several routing policies were analyzed in light traffic and in heavy traffic conditions. But, the good light traffic policies become very quickly unstable with increasing traffic intensity, and the good heavy traffic policies are inefficient in light traffic conditions. In this paper, a new routing policy is defined and analyzed, using results from branching processes with state dependent immigration. This policy not only performs optimally in light traffic, but also performs very well in heavy traffic. This is important to the designer of a service system because the traffic conditions may be variable and/or be unpredictable, and having to switch routing policies could prove to be costly and difficult to implement.     

Asymptotic optimality of the Round–Robin policy in multipath routing with resequencing

We consider a model of a multipath routing system where arriving customers are routed to a set of identical, parallel, single server queues according to balancing policies operating without state information. After completion of service, customers are required to leave the system in their order of arrival, thus incurring an additional resequencing delay. We are interested in minimizing the end-to-end delay (including time at the resequencing buffer) experienced by arriving customers. To that end we establish the optimality of the Round–Robin routing assignment in two asymptotic regimes, namely heavy and light traffic: In heavy traffic, the Round–Robin customer assignment is shown to achieve the smallest (in the increasing convex stochastic ordering) end-to-end delay amongst all routing policies operating without queue state information. In light traffic, and for the special case of Poisson arrivals, we show that Round–Robin is again an optimal (in the strong stochastic ordering) routing policy. We illustrate the stochastic comparison results by several simulation examples. The work of the first author was supported through an ARCHIMEDES grant by the Greek Ministry of Education. The work of the second author was prepared through collaborative participation in the Communications and Networks Consortium sponsored by the U.S. Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-01-2-0011. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation thereon. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government.     

An assignment problem for a parallel queueing system with two heterogeneous servers

In this paper, we consider an optimization problem for a parallel queueing system with two heterogeneous servers. Each server has its own queue and customers arrive at each queue according to independent Poisson processes. Each service time is independent and exponentially distributed. When a customer arrives at queue 1, the customers in queue 1 can be transferred to queue 2 by paying an assignment cost which is proportional to the number of moved customers. Holding cost is a function of the pair of queue lengths of the two servers. Our objective is to minimize the expected total discounted cost. We use the dynamic programming approach for this problem. Considering the pair of queue lengths as a state space, we show that the optimal policy has a switch over structure under some conditions on the holding cost.     

On the incomplete results for the heterogeneous server problem

In this article, we show that the arguments in Rykov [9] on the optimality of a threshold routing policy when there are more than two heterogeneous servers are incomplete. AMS Subject Classifications: 93E20, 60K25, 90B22     

Throughput and delay optimality of power-of-d choices in inhomogeneous load balancing systems

It is well-known that the power-of-d choices routing algorithm maximizes throughput and is heavy-traffic optimal in load balancing systems with homogeneous servers. However, if the servers are heterogeneous, throughput optimality does not hold in general. We find necessary and sufficient conditions for throughput optimality of power-of-d choices when the servers are heterogeneous, and we prove that almost the same conditions are sufficient to show heavy-traffic optimality. Additionally, we generalize the sufficient condition for throughput optimality to a larger class of routing policies.