Explore the vast range of titles available.

Extending the results of Kruk (Queueing theory and network applications. QTNA 2019. Lecture notes in computer science, vol 11688. Springer, Cham, pp 263–275, 2019), we derive heavy traffic limit theorems for a single server, single customer class queue in which the server uses the Shortest Remaining Processing Time (SRPT) policy from heavy traffic limits for the corresponding Earliest Deadline First queueing systems. Our analysis allows for correlated customer inter-arrival and service times and heavy-tailed inter-arrival and service time distributions, as long as the corresponding stochastic primitive processes converge weakly to continuous limits under heavy traffic scaling. Our approach yields simple, concise justifications and new insights for SRPT heavy traffic limit theorems of Gromoll et al. (Stoch Syst 1(1):1–16, 2011). Corresponding results for the longest remaining processing time policy are also provided.

We consider a queueing network in which there are constraints on which queues may be served simultaneously; such networks may be used to model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time. We consider a family of scheduling policies, related to the maximum-weight policy of Tassiulas and Ephremides [IEEE Trans. Automat. Control 37 (1992) 1936-1948], for single-hop and multihop networks. We specify a fluid model and show that fluid-scaled performance processes can be approximated by fluid model solutions. We study the behavior of fluid model solutions under critical load, and characterize invariant states as those states which solve a certain network-wide optimization problem. We use fluid model results to prove multiplicative state space collapse. A notable feature of our results is that they do not assume complete resource pooling.

We introduce a family of heavy-traffic regimes for large-scale service systems, presenting a range of scalings that include both moderate and extreme heavy traffic, as compared to classical heavy traffic. The heavy-traffic regimes can be translated into capacity sizing rules that lead to economies-of-scales, so that the system utilization approaches 100% while congestion remains limited. We obtain heavy-traffic approximations for stationary performance measures in terms of asymptotic expansions, using a nonstandard saddle point method, tailored to the specific form of integral expressions for the performance measures, in combination with the heavy-traffic regimes.

To provide useful practical insight into the performance of service-oriented (non-revenue-generating) call centers, which often provide low-to-moderate quality of service, this paper investigates the efficiency-driven (ED), many-server heavy-traffic limiting regime for queues with abandonments. Attention is focused on the M/M/s/r + M model, having a Poisson arrival process, exponential service times, s servers, r extra waiting spaces, exponential abandon times (the final + M ), and the first-come–first-served service discipline. Both the number of servers and the arrival rate are allowed to increase, while the individual service and abandonment rates are held fixed. The key is how the two limits are related: In the now common quality-and-efficiency-driven (QED) or Halfin-Whitt limiting regime, the probability of initially being delayed approaches a limit strictly between 0 and 1, while the probability of eventually being served (not abandoning) approaches 1. In contrast, in the ED limiting regime, the probability of eventually being served approaches a limit strictly between 0 and 1, while the probability of initially being delayed approaches 1. To obtain the ED regime, it suffices to let the arrival rate and the number of servers increase with the traffic intensity held fixed with > 1 (so that the arrival rate exceeds the maximum possible service rate). The ED regime can be realistic because with the abandonments, the delays need not be extraordinarily large. When the ED appropriations are appropriate, they are appealing because they are remarkably simple.

In this paper we study the number of customers in infinite-server queues with a self-exciting (Hawkes) arrival process. Initially we assume that service requirements are exponentially distributed and that the Hawkes arrival process is of a Markovian nature. We obtain a system of differential equations that characterizes the joint distribution of the arrival intensity and the number of customers. Moreover, we provide a recursive procedure that explicitly identifies (transient and stationary) moments. Subsequently, we allow for non-Markovian Hawkes arrival processes and nonexponential service times. By viewing the Hawkes process as a branching process, we find that the probability generating function of the number of customers in the system can be expressed in terms of the solution of a fixed-point equation. We also include various asymptotic results: we derive the tail of the distribution of the number of customers for the case that the intensity jumps of the Hawkes process are heavy tailed, and we consider a heavy-traffic regime. We conclude by discussing how our results can be used computationally and by verifying the numerical results via simulations.

In highly congested networks, is selfishness the problem? Empirical studies in road networks reveal a fairly surprising property of congestion: when there is too much (or too little) traffic in the network, there is no difference between the best and the fairest traffic allocations (i.e., between the traffic assignment that optimizes the commuters' average travel time versus the one that no commuter would have any incentive to deviate from). In “When is Selfish Routing Bad? The Price of Anarchy in Light and Heavy Traffic”, the authors give a theoretical justification to this empirical observation: for a large class of traffic inflow patterns and cost functions (including all polynomials), the gap between social optimality and equilibrium—the network’s price of anarchy—converges to 1 in both heavy and light traffic, irrespective of the network topology and the number of origin/destination pairs in the network. This paper examines the behavior of the price of anarchy as a function of the traffic inflow in nonatomic congestion games with multiple origin/destination (O/D) pairs. Empirical studies in real-world networks show that the price of anarchy is close to 1 in both light and heavy traffic, thus raising the following question: can these observations be justified theoretically? We first show that this is not always the case: the price of anarchy may remain a positive distance away from 1 for all values of the traffic inflow, even in simple three-link networks with a single O/D pair and smooth, convex costs. On the other hand, for a large class of cost functions (including all polynomials) and inflow patterns, the price of anarchy does converge to 1 in both heavy and light traffic, irrespective of the network topology and the number of O/D pairs in the network. We also examine the rate of convergence of the price of anarchy, and we show that it follows a power law whose degree can be computed explicitly when the network’s cost functions are polynomials.

We provide an example of a feedforward first-in-system, first-out (FISFO) queueing network with unconventional, i.e., non-Brownian, heavy traffic diffusion approximation. We also prove that fluid models of subcritical feedforward earliest-deadline-first (EDF) queueing networks are asymptotically stable.

Semimartingale reflecting Brownian motions (SRBMs) are diffusion processes with state space the d-dimensional nonnegative orthant, in the interior of which the processes evolve according to a Brownian motion, and that reflect against the boundary in a specified manner. The data for such a process are a drift vector θ, a nonsingular d × d covariance matrix Σ, and a d × d reflection matrix R. A standard problem is to determine under what conditions the process is positive recurrent. Necessary and sufficient conditions for positive recurrence are easy to formulate for d = 2, but not for d > 2. Associated with the pair (θ, R) are fluid paths, which are solutions of deterministic equations corresponding to the random equations of the SRBM. A standard result of Dupuis and Williams [Ann. Probab. 22 (1994) 680–702] states that when every fluid path associated with the SRBM is attracted to the origin, the SRBM is positive recurrent. Employing this result, El Kharroubi, Ben Tahar and Yaacoubi [Stochastics Stochastics Rep. 68 (2000) 229–253, Math. Methods Oper. Res. 56 (2002) 243–258] gave sufficient conditions on (θ, Σ, R) for positive recurrence for d = 3; Bramson, Dai and Harrison [Ann. Appl. Probab. 20 (2009) 753–783] showed that these conditions are, in fact, necessary. Relatively little is known about the recurrence behavior of SRBMs for d > 3. This pertains, in particular, to necessary conditions for positive recurrence. Here, we provide a family of examples, in d = 6, with θ = (−1, −1,..., −1) T , Σ = I and appropriate R, that are positive recurrent, but for which a linear fluid path diverges to infinity. These examples show in particular that, for d ≥ 6, the converse of the Dupuis—Williams result does not hold.

Multiserver queueing systems describe situations in which users require service from multiple parallel servers. Examples include check-in lines at airports, waiting rooms in hospitals, queues in contact centers, data buffers in wireless networks, and delayed service in cloud data centers. These are all situations with jobs (clients, patients, tasks) and servers (agents, beds, processors) that have large capacity levels, ranging from the order of tens (checkouts) to thousands (processors). This survey investigates how to design such systems to exploit resource pooling and economies-of-scale. In particular, we review the mathematics behind the quality- and efficiency-driven (QED) regime, which lets the system operate close to full utilization, while the number of servers grows simultaneously large and delays remain manageable. Aimed at a broad audience, we describe in detail the mathematical concepts for the basic Markovian many-server system, and we provide only sketches or references for more advanced settings related to, e.g., load balancing, overdispersion, parameter uncertainty, general service requirements, and queueing networks. While serving as a partial survey of a massive body of work, the tutorial is not meant to be exhaustive.

As a model of make-to-order production, we consider an admission control problem for a multiclass, single-server queue. The production system serves multiple demand streams, each having a rigid due-date lead time. To meet the due-date constraints, a system manager may reject orders when a backlog of work is judged to be excessive, thereby incurring lost revenues. The system manager strives to minimize long-run average lost revenues by dynamically making admission control and sequencing decisions. Under heavy-traffic conditions the scheduling problem is approximated by a Brownian control problem, which is solved explicitly. Interpreting this solution in the context of the original queueing system, a nested threshold policy is proposed. A simulation experiment is performed to demonstrate the effectiveness of this policy.