Dynamic Routing in Large-Scale Service Systems with Heterogeneous Servers

Motivated by modern call centers, we consider large-scale service systems with multiple server pools and a single customer class. For such systems, we propose a simple routing rule which asymptotically minimizes the steady-state queue length and virtual waiting time. The proposed routing scheme is FSF which assigns customers to the Fastest Servers First. The asymptotic regime considered is the Halfin-Whitt many-server heavy-traffic regime, which we refer to as the Quality and Efficiency Driven (QED) regime; it achieves high levels of both service quality and system efficiency by carefully balancing between the two. Additionally, expressions are provided for system limiting performance measures based on diffusion approximations. Our analysis shows that in the QED regime this heterogeneous server system outperforms its homogeneous server counterpart. AMS subject classification: 60K25, 68M20, 90B22     

Open queueing networks in discrete time-some limit theorems

A finite number of nodes, each with a single server and infinite buffers, is considered in discrete time. The service may be FIFO and the service times are constant. The external arrivals and the routing decision variables form a general stationary sequence. Stability of the system is proved under these assumptions. Extension to multiple servers at a node and general stationary distributions holds. If the external input is i.i.d. and the routing is Markovian then stochastic ordering, continuity of stationary distributions, rates of convergence, a functional CLT and a functional LIL and various other limit theorems for the queue length process are also proved. Generalizations to multiple servers at nodes, customers with priority, multiple customer classes, general service length and Markov modulated external arrival cases are discussed.     

Round robin scheduling of heterogeneous parallel servers in heavy traffic

We consider scheduling for heterogeneous server systems, where tasks arrive according to a Poisson process, with their processing requirements following a discrete distribution with finite support. For a system with a dispatcher and several heterogeneous servers, we propose an optimized multi-layered round robin routing policy followed by shortest remaining processing time scheduling at each server. Using a heavy traffic approximation, we show that the proposed policy performs as well as the optimal scheduling policy for a heterogeneous servers system with a single queue (no routing) in heavy traffic. Additional simulation results suggest that such policies will be effective in more general settings.     

The BMAP/PH/N retrial queue with Markovian flow of breakdowns

We consider a multi-server retrial queue with the Batch Markovian Arrival Process (BMAP). The servers are identical and independent of each other. The service time distribution of a customer by a server is of the phase (PH) type. If a group of primary calls meets idle servers the primary calls occupy the corresponding number of servers. If the number of idle servers is insufficient the rest of calls go to the orbit of unlimited size and repeat their attempts to get service after exponential amount of time independently of each other. Busy servers are subject to breakdowns and repairs. The common flow of breakdowns is the MAP. An event of this flow causes a failure of any busy server with equal probability. When a server fails the repair period starts immediately. This period has PH type distribution and does not depend on the repair time of other broken-down servers and the service time of customers occupying the working servers. A customer whose service was interrupted goes to the orbit with some probability and leaves the system with the supplementary probability. We derive the ergodicity condition and calculate the stationary distribution and the main performance characteristics of the system. Illustrative numerical examples are presented.     

Workforce cross-training decisions in field service systems with two job types

When job types are heterogeneous in a multi-server service system, pooling servers to reduce system delay requires cross-training. Managers should balance a reduction in customer waiting time with high service costs and possibly reduced server efficiency due to cross-training. In a field service system with two job types and a fixed number of servers, the determination of the mix of dedicated and cross-trained servers is a critical managerial decision. We were motivated by a real field service situation to study a model where the objective is to minimize the sum of the average service costs and the customer delay costs per unit time. We use simulation to investigate the impact of various system parameters such as the number of servers, server utilization, and server efficiency on the optimal workforce mix.     

Performance analysis of a constrained resource sharing system

We consider a queueing system where the servers are arranged in a circle, and each arriving customer requires a pair of resources that is shared by its server with the respective neighbors on either side. If either resource is being used, the customer is denied service. Customers arrive at each server according to independent Poisson processes, and lengths of service times at each server have an exponential distribution. We derive a closed-form formula for the expected fraction of busy servers at any time in terms of the number of servers and the utilization factor (defined as the arrival rate times the mean service-time duration). This allows us to evaluate system performance when these parameters are varied, and to determine whether denying service to arrivals at alternate servers improves performance. We relate the system to Dijkstra's dining philosophers problem, which is an abstraction for resource sharing in an operating system. This revised version was published online in June 2006 with corrections to the Cover Date.     

Queueing systems on a circle

Consider a ring on which customers arrive according to a Poisson process. Arriving customers drop somewhere on the circle and wait there for a server who travels on the ring. Whenever this server encounters a customer, he stops and serves the customer according to an arbitrary service time distribution. After the service is completed, the server removes the client from the circle and resumes his journey.We are interested in the number and the locations of customers that are waiting for service. These locations are modeled as random counting measures on the circle. Two different types of servers are considered: The polling server and the Brownian (or drunken) server. It is shown that under both server motions the system is stable if the traffic intensity is less than 1. Furthermore, several earlier results on the configuration of waiting customers are extended, by combining results from random measure theory, stochastic integration and renewal theory.     

Optimal order for two servers in tandem

We consider two servers (serveri, i=1, 2) in tandem for which the order of servers can be changed. Server 1 has a general service time distribution and server 2 has either its shifted or truncated distribution. This permits that the service times at the two servers are overlapping. An unlimited queue is allowed in front of the first server. For the systems having zero buffer capacity between the servers, we show that the sojourn time of every customer is stochastically minimized under any arrival process if server 2 is first. For the systems with infinite buffer capacity and a Poisson arrivals, we show that this order of servers minimizes mean customer delay when traffic is light. Several numerical examples are presented to demonstrate that this optimal order is invariant under any arrival process (the interarrival times are i.i.d. r.v.'s) and mild traffic condition.Research funded by NEC Corporation C & C Laboratory.     

Understanding the marginal impact of customer flexibility

We study the marginal impact of customer flexibility in service systems. We consider a queueing system with multiple parallel servers, in which a proportion of customers are flexible and can go to any server, while the remainder require service at a particular server. We show that the stationary expected waiting time is decreasing and convex in the proportion of flexible customers. We also show, for a related Inventory Model, in which servers are never idle and can build up inventory, that convexity holds in a strong sample-path sense. Our results reinforce the idea that a little flexibility goes a long way.     

Transient analysis of a two-heterogeneous servers queue with system disaster,server repair and customers’ impatience

A two-heterogeneous servers queue with system disaster, server failure and repair is considered. In addition, the customers become impatient when the system is down. The customers arrive according to a Poisson process and service time follows exponential distribution. Each customer requires exactly one server for its service and the customers select the servers on fastest server first basis. Explicit expressions are derived for the time-dependent system size probabilities in terms of the modified Bessel function, by employing the generating function along with continued fraction and the identity of the confluent hypergeometric function. Further, the steady-state probabilities of the number of customers in the system are deduced and finally some important performance measures are obtained.     

On the order of tandem queues

We consider the optimal order of servers in a tandem queueing system withm stages, an unlimited supply of customers in front of the first stage, and a service buffer of size 1 but no intermediate storage buffers between the first and second stages. Service times depend on the servers but not the customers, and the blocking mechanism at the first two stages is manufacturing blocking. Using a new characterization of reversed hazard rate order, we show that if the service times for two servers are comparable in the reversed hazard rate sense, then the departure process is stochastically earlier if the slower server is first and the faster server is second than if the reverse is true. This strengthens earlier results that considered individual departure times marginally. We show similar results for the last two stages and for other blocking mechanisms. We also show that although individual departure times for a system with servers in a given order are stochastically identical to those when the order of servers is reversed, this reversibility property does not hold for the entire departure process.     

Two approaches to optimal routing and admission control in systems with real-time traffic

This paper addresses the problem of routing and admission control of real-time traffic in a queueing system where customers must begin service within given deadlines (or complete service within given deadlines), otherwise they are considered lost. Performance in such systems is measured by the probability a customer is lost. For a system ofK parallel servers with a probabilistic routing and admission control scheme, the problem of the optimal routing and admission control is considered and two approaches are presented. Assuming the availability of a closed-form expression for the probability of loss at each server, the problem is solved under general conditions and properties of the optimal flow allocation are given. However, such closed-form expressions are often unavailable. This motivates a second approach, which involves a gradient-based stochastic optimization algorithm with on-line gradient estimation. The gradient estimation problem for loss probabilities is solved through a recently-developed smoothed perturbation analysis (SPA) technique. The effectiveness of on-line stochastic optimization using this type of gradient estimator is demonstrated by combining the SPA algorithm with a sampling-controlled stochastic optimization algorithm for the aforementioned routing and admission control problem.This work was supported in part by the Office of Naval Research under Contract N00014-87-K-0304, by the Rome Air Development Center under Contract F30602-88-D-0027, by NASA under Contract NAG 2-595, and by the National Science Foundation under Grant EID-92-12122.The authors are grateful to Don Towsley for several contributions to Section 2 and to an anonymous reviewer for pointing out a redundant assumption in the proof of Lemma 2.1.     

Heavy-traffic limits for server idle times with customary server-assignment rules

Sun and Whitt (2017) developed a class of server-assignment rules that can help create effective breaks for servers from naturally available idleness. They found that the standard longest-idle-server-first rule and the alternative random routing generate breaks too infrequently. This paper provides theoretical justifications for these empirical findings by establishing the many-server heavy-traffic limits for server idle times with customary assignment rules. We gain insights into the server idle–busy activity patterns resulting from the server-assignment schemes in the system.     

Emergency path restoration problems

We consider the problem of optimally scheduling the restoration of edges of a transportation network destroyed/damaged by a disaster. The restoration is performed by service units (servers) which have fixed restoration speeds. If several servers work simultaneously at the same point of the network, their collective restoration speed is the sum of their individual restoration speeds. The servers are initially located at some nodes. Each server can travel within the already restored part of the network with infinite speed, that is, at any time can immediately relocate to another point of the same connected component of the already restored part of the network. It is required to minimize a scheduling objective that can be expressed as the maximum or the sum of nondecreasing functions of the recovery times of the nodes, where the recovery time of a node is the time when the node is reached for the first time by a server. We present polynomial-time algorithms on path networks for problems with fixed initial locations of the servers. For problems with flexible locations that should also be optimized, we present polynomial-time algorithms for the case of equal restoration speeds of the servers, and prove that the problems are strongly NP-hard if the restoration speeds of the servers can be different.     

Convexity properties of the overflow in an ordered-entry system with heterogeneous servers

The overflow probability in an Erlang loss system is known to be decreasing convex in the number of servers. Here we consider the GI/M/m loss system with ordered entry and heterogeneous servers. We show that adding a sequence of servers with non-increasing (non-decreasing) service rates will yield a decreasing convex (log-concave) sequence of overflow probabilities. An optimal server allocation problem is solved as a direct application of these results.     

Profit maximization in flexible serial queueing networks

We analyze the tradeoff between efficiency and service quality in tandem systems with flexible servers and finite buffers. We reward efficiency by assuming that a revenue is earned each time a job is completed, and penalize poor service quality by incorporating positive holding costs. We study the dynamic assignment of servers to tasks with the objective of maximizing the long-run average profit. For systems of arbitrary size, structured service rates, and linear or nonlinear holding costs, we determine the server assignment policy that maximizes the profit. For systems with two stations, two servers with arbitrary service rates, and linear holding costs, we show that the optimal server assignment policy is of threshold type and determine the value of this threshold as a function of the revenue and holding cost. The threshold can be interpreted as the best possible buffer size, and hence our results prove the equivalence of addressing service quality via a holding cost and via limiting the buffer size. Furthermore, we identify the optimal buffer size when each buffer space comes at a cost. We provide numerical results that suggest that the optimal policy also has a threshold structure for nonlinear holding costs. Finally, for larger systems with arbitrary service rates, we propose effective server assignment heuristics.     

Cost analysis of the M/M/R machine repair problem with balking,reneging, and server breakdowns

We consider the machine repair problem in which failed machines balk (do not enter) with a constant probability (1 – b) and renege (leave the queue after entering) according to a negative exponential distribution. A group of identical automatic machines are maintained by R servers which themselves are subject to breakdowns. Failure and service times of the machines, and breakdown and repair times of the servers, are assumed to follow a negative exponential distribution. Each server is subject to breakdown even if no failed machines are in the system. This paper presents a matrix geometric method for deriving the steady-state probabilities, using which various system performance measures that can be obtained. A cost model is developed to determine the optimum number of servers. The minimum expected cost, the optimal number of servers, and various system performance measures are provided based on assumed numerical values given to the system parameters. Also the sensitivity analysis is investigated.     

相依修理的可修排队系统 MAP/PH(M/PH)/2

系统地研究了两个不同并行服务台的可修排队系统MAP/PH(M/PH)/2,其中两个不同的服务台拥有一个修理工.若其中一台处于修理状态,则另一台失效后就处于待修状态.利用拟生灭过程理论,我们首先讨论了两个服务台的广义服务时间的相依性,然后给出了系统的稳态可用度和稳态故障度,最后得到了系统首次失效前的时间分布及其均值.     

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.     

Location-allocation on congested networks

This paper deals with location-allocation decisions in networks under conditions of congestion, i.e. taking into consideration the possible arrival of calls for service while no server is available. The problem is to find simultaneously the optimal districting policy which determines how a region should be partitioned into separate service areas, and the optimal locations of facilities to house the service units. An alternate location and allocation solution improvement procedure is developed to combine an existing location algorithm of a single mobile service unit [3] with an existing districting heuristic for two servers [5]. The 2-server districting heuristic is further extended to treat the general case of m servers, and combined with the location algorithm for a single server it forms a general location-allocation heuristic for n nodes and m servers.