Subjects -> STATISTICS (Total: 130 journals)
 The end of the list has been reached or no journals were found for your choice.
Similar Journals
 Queueing SystemsJournal Prestige (SJR): 0.809 Citation Impact (citeScore): 1Number of Followers: 7      Hybrid journal (It can contain Open Access articles) ISSN (Print) 1572-9443 - ISSN (Online) 0257-0130 Published by Springer-Verlag  [2469 journals]
• A transient symmetry analysis for the M/M/1/k queue

Abstract: Abstract We develop new techniques involving group symmetries and complex analysis to obtain exact solutions for the transition probabilities of the M/M/1/k queueing process. These methods are based on the underlying Markovian structure of these random processes and do not involve any generating functions, Laplace transforms, or advanced special functions. Our techniques exploit the intrinsic group symmetries for both the state spaces and the matrix generators of the Markov processes related to the M/M/1/k queue. These results complement and extend the previous transient solutions given by Takács (Introduction to the theory of queues. University texts in the mathematical sciences, Oxford University Press, New York, 1962). Much of the inspiration for this work comes from viewing this queueing process as a fundamental Markovian model for the dynamics of a bike sharing station. The exact transient analysis for a related stopped version of this process can be used to address fundamental decision-making issues for managing bike-sharing services.
PubDate: 2022-08-07

• Analysis of a tripartite entanglement distribution switch

Abstract: Abstract We study a quantum switch that distributes tripartite entangled states to sets of users. The entanglement switching process requires two steps: First, each user attempts to generate bipartite entanglement between itself and the switch, and second, the switch performs local operations and a measurement to create multipartite entanglement for a set of three users. In this work, we study a simple variant of this system, wherein the switch has infinite memory and the links that connect the users to the switch are identical. This problem formulation is of interest to several distributed quantum applications, while the technical aspects of this work result in new contributions within queueing theory. The state of the system is modeled as continuous-time Markov chain (CTMC), and performance metrics of interest (probability of an empty system, switch capacity, expectation, and variance of the number of qubit-pairs stored) are computed via the solution of a two-dimensional functional equation obtained by reducing it to a boundary value problem on a closed curve. This work is a follow-up of Nain et al. (Proc ACM Measure Anal Comput Syst(POMACS) 4, 2020) where a switch distributing entangled multipartite states to sets of users was studied, but only the switch capacity and the expected number of stored qubits were derived.
PubDate: 2022-08-01

• Regulation of a single-server queue with customers who dynamically choose
their service durations

Abstract: Abstract In recent years, there is a growing attention towards queueing models with customers who choose their service durations. The model assumptions in the existing literature imply that every customer knows his service demand when he enters into the service position. Clearly, this property is not consistent with some real-life situations. Motivated by this issue, the current work includes a single-server queueing model with customers who dynamically choose their service durations. In this setup, the main result is existence of a quadratic price function which (1) implies an optimal resource allocation from a social point of view and (2) internalizes the externalities in the system. In addition, it is explained how to compute its parameters efficiently.
PubDate: 2022-08-01

• Applying optimization theory to study extremal GI/GI/1 transient mean
waiting times

Abstract: Abstract We study the tight upper bound of the transient mean waiting time in the classical GI/GI/1 queue over candidate interarrival-time distributions with finite support, given the first two moments of the interarrival time and the full service-time distribution. We formulate the problem as a non-convex nonlinear program. We derive the gradient of the transient mean waiting time and then show that a stationary point of the optimization can be characterized by a linear program. We develop and apply a stochastic variant of the Frank and Wolfe (Naval Res Logist Q 3:95–110, 1956) algorithm to find a stationary point for any given service-time distribution. We also establish necessary conditions and sufficient conditions for stationary points to be three-point distributions or special two-point distributions. We illustrate by applying simulation together with optimization to analyze several examples.
PubDate: 2022-08-01

• WCFS: a new framework for analyzing multiserver systems

Abstract: Abstract Multiserver queueing systems are found at the core of a wide variety of practical systems. Many important multiserver models have a previously-unexplained similarity: identical mean response time behavior is empirically observed in the heavy traffic limit. We explain this similarity for the first time. We do so by introducing the work-conserving finite-skip (WCFS) framework, which encompasses a broad class of important models. This class includes the heterogeneous M/G/k, the Limited Processor Sharing policy for the M/G/1, the Threshold Parallelism model and the Multiserver-Job model under a novel scheduling algorithm. We prove that for all WCFS models, scaled mean response time $$E[T](1-\rho )$$ converges to the same value, $$E[S^2]/(2E[S])$$ , in the heavy-traffic limit, which is also the heavy traffic limit for the M/G/1/FCFS. Moreover, we prove additively tight bounds on mean response time for the WCFS class, which hold for all load $$\rho$$ . For each of the four models mentioned above, our bounds are the first known bounds on mean response time.
PubDate: 2022-07-28

• Uniform stability of some large-scale parallel server networks

Abstract: Abstract In this paper we study the uniform stability properties of two classes of parallel server networks with multiple classes of jobs and multiple server pools of a tree topology. These include a class of networks with a single nonleaf server pool, such as the ‘N’ and ‘M’ models, and networks of any tree topology with class-dependent service rates. We show that with $$\sqrt{n}$$ safety staffing, and no abandonment, in the Halfin–Whitt regime, the diffusion-scaled controlled queueing processes are exponentially ergodic and their invariant probability distributions are tight, uniformly over all stationary Markov controls. We use a unified approach in which the same Lyapunov function is used in the study of the prelimit and diffusion limit. A parameter called the spare capacity (safety staffing) of the network plays a central role in characterizing the stability results: the parameter being positive is necessary and sufficient that the limiting diffusion is uniformly exponentially ergodic over all stationary Markov controls. We introduce the concept of “system-wide work conserving policies," which are defined as policies that minimize the number of idle servers at all times. This is stronger than the so-called joint work conservation. We show that, provided the spare capacity parameter is positive, the diffusion-scaled processes are geometrically ergodic and the invariant distributions are tight, uniformly over all “system-wide work conserving policies." In addition, when the spare capacity is negative we show that the diffusion-scaled processes are transient under any stationary Markov control, and when it is zero, they cannot be positive recurrent.
PubDate: 2022-07-23

• On the Whittle index of Markov modulated restless bandits

Abstract: Abstract In this paper, we study a Multi-Armed Restless Bandit Problem (MARBP) subject to time fluctuations. This model has numerous applications in practice, like in cloud computing systems or in wireless communications networks. Each bandit is formed by two processes: a controllable process and an environment. The transition rates of the controllable process are determined by the state of the environment, which is an exogenous Markov process. The decision maker has full information on the state of every bandit, and the objective is to determine the optimal policy that minimises the long-run average cost. Given the complexity of the problem, we set out to characterise the Whittle index, which is obtained by solving a relaxed version of the MARBP. As reported in the literature, this heuristic performs extremely well for a wide variety of problems. Assuming that the optimal policy of the relaxed problem is of threshold type, we provide an algorithm that finds Whittle’s index. We then consider a multi-class queue with linear cost and impatient customers. For this model, we show threshold optimality, prove indexability, and obtain Whittle’s index in closed-form. We also study the limiting regimes in which the environment is relatively slower and faster than the controllable process. By numerical simulations, we assess the suboptimality of Whittle’s index policy in a wide variety of scenarios, and the general observation is that, as in the case of standard MARBP, the suboptimality gap of Whittle’s index policy is small.
PubDate: 2022-06-27

• A load balancing system in the many-server heavy-traffic asymptotics

Abstract: Abstract We study a load balancing system in the many-server heavy-traffic regime. We consider a system with N servers, where jobs arrive to the system according to a Poisson process and have an exponentially distributed size with mean 1. We parametrize the arrival rate so that the arrival rate per server is $$1-N^{-\alpha }$$ , where $$\alpha >0$$ is a parameter that represents how fast the load grows with respect to the number of servers. The many-server heavy-traffic regime corresponds to the limit as $$N\rightarrow \infty$$ , and subsumes several regimes, such as the Halfin–Whitt regime ( $$\alpha =1/2$$ ), the NDS regime ( $$\alpha =1$$ ), as $$\alpha \downarrow 0$$ it approximates mean field and as $$\alpha \rightarrow \infty$$ it approximates the classical heavy-traffic regime. Most of the prior work focuses on regimes with $$\alpha \in [0,1]$$ . In this paper, we focus on the case when $$\alpha >1$$ and the routing algorithm is power-of-d choices with $$d=\lceil cN^\beta \rceil$$ for some constants $$c>0$$ and $$\beta \ge 0$$ . We prove that $$\alpha +\beta >3$$ is sufficient to observe that the average queue length scaled by $$N^{1-\alpha }$$ converges to an exponential random variable. In other words, if $$\alpha +\beta >3$$ , the scaled average queue length behaves similarly to the classical heavy-traffic regime. In particular, this result implies that if d is constant, we require $$\alpha >3$$ and if routing occurs according to JSQ we require $$\alpha >2$$ . We provide two proofs to our result: one based on the Transform method introduced in Hurtado-Lange and Maguluri (Stoch Syst 10(4):275–309, 2020) and one based on Stein’s method. In the second proof, we also compute the rate of convergence in Wasserstein’s distance. In both cases, we additionally compute the rate of convergence in expected value. All of our proofs are powered by state space collapse.
PubDate: 2022-06-21

• Fluid limits of a loss storage network

Abstract: Abstract Our goal in this paper is to investigate the fluid picture associated with an open large-scale storage system with infinite size. We consider a large-scale storage network of non-reliable file servers in which new files can be added and a file with only one copy can be lost or duplicated. The Skorokhod problem with oblique reflection in an orthant is used to identify the fluid limits of this system which describe its qualitative behaviour and give an idea about a good choice of parameters that guarantees reliability. The fluctuations around the fluid limits are investigated.
PubDate: 2022-06-01

• Heavy traffic limits for queues with non-stationary path-dependent arrival
processes

Abstract: Abstract In this paper, we develop a diffusion approximation for the transient distribution of the workload process in a standard single-server queue with a non-stationary Polya arrival process, which is a path-dependent Markov point process. The path-dependent arrival process model is useful because it has the arrival rate depending on the history of the arrival process, thus capturing a self-reinforcing property that one might expect in some applications. The workload approximation is based on heavy-traffic limits for (i) a sequence of Polya processes, in which the limit is a Gaussian–Markov process, and (ii) a sequence of P/GI/1 queues in which the arrival rate function approaches a constant service rate uniformly over compact intervals.
PubDate: 2022-06-01

• Instability of SRPT, SERPT and SJF multiclass queueing networks

Abstract: Abstract We provide two examples of strictly subcritical multiclass queueing networks which are unstable under the shortest remaining processing time (SRPT) service protocol. Both of them are reentrant lines with two servers and eight customer classes. The customer service times in our first system are deterministic, yielding an example of an unstable shortest remaining expected processing time (SERPT) network. In the second one, the service times in one customer class are randomized. Both our examples show also system instability under the shortest job first (SJF) discipline. A simulation study of robustness of our results with respect to changes in the customer interarrival and service times is also provided. Our results indicate that size-based service policies may not use the available resources efficiently in a multiserver network setting and in fact cause instability effects. This is in sharp contrast with their satisfactory performance for single-server queues.
PubDate: 2022-06-01

• Appointment-driven queueing systems with non-punctual customers

Abstract: Abstract We consider a single-server queueing system where a finite number of customers arrive over time to receive service. Arrivals are driven by appointments, with a scheduled appointment time associated with each customer. However, customers are not necessarily punctual and may arrive either earlier or later than their scheduled appointment times or may not show up at all. Arrival times relative to scheduled appointments are random. Customers are not homogeneous in their punctuality and show-up behavior. The time between consecutive appointments is allowed to vary from customer to customer. Moreover, service times are assumed to be random with a $$\gamma$$ -Cox distribution, a class of phase-type distributions known to be dense in the field of positive distributions. We develop both exact and approximate approaches for characterizing the distribution of the number of customers seen by each arrival. We show how this can be used to obtain the distribution of waiting time for each customer. We prove that the approximation provides an upper bound for the expected customer waiting time when non-punctuality is uniformly distributed. We also examine the impact of non-punctuality on system performance. In particular, we prove that non-punctuality deteriorates waiting time performance regardless of the distribution of non-punctuality. In addition, we illustrate how our approach can be used to support individualized appointment scheduling.
PubDate: 2022-06-01

• Asymptotics of waiting time distributions in the accumulating priority
queue

Abstract: Abstract We analyze the asymptotics of waiting time distributions in the two-class accumulating priority queue with general service times. The accumulating priority queue was suggested by Kleinrock in the 60s—he coined it time-dependent priority—to diversify waiting time objectives of different classes in a paramaterized way. It also avoids the typical starvation problem of regular priority queues. All customers build up priority linearly while waiting in the queue but at a class-dependent rate. At a service opportunity epoch, the customer with highest priority present is served. Stanford and colleagues recently calculated the Laplace–Stieltjes Transform (LST) of the waiting time distributions of the different classes, but only invert these LSTs numerically. In this paper, we analytically calculate the asymptotics of the corresponding distributions from these LSTs. We show that different singularities of the LST can play a role in the asymptotics, depending on the magnitude of service differentiation between both classes.
PubDate: 2022-05-10
DOI: 10.1007/s11134-022-09839-7

• Infinite-server systems with Hawkes arrivals and Hawkes services

Abstract: Abstract This paper is devoted to the study of the number of customers in infinite-server systems driven by Hawkes processes. In these systems, the self-exciting arrival process is assumed to be represented by a Hawkes process and the self-exciting service process by a state-dependent Hawkes process (sdHawkes process). Under some suitable conditions, for the $$\mathrm{Hawkes/sdHawkes/\infty }$$ system, the Markov property of the system is derived. The joint time-dependent distribution of the number of customers in the system, the arrival intensity and the server intensity is characterized by a system of differential equations. Then, the time-dependent results are also deduced for the $$\mathrm{M/sdHawkes/\infty }$$ system.
PubDate: 2022-04-29

• A general “power-of-d” dispatching framework for heterogeneous
systems

Abstract: Abstract Intelligent dispatching is crucial to obtaining low response times in large-scale systems. One common scalable dispatching paradigm is the “power-of-d,” in which the dispatcher queries d servers at random and assigns the job to a server based only on the state of the queried servers. The bulk of power-of-d policies studied in the literature assume that the system is homogeneous, meaning that all servers have the same speed; meanwhile, real-world systems often exhibit server speed heterogeneity. This paper introduces a general framework for describing and analyzing heterogeneity-aware power-of-d policies. The key idea behind our framework is that dispatching policies can make use of server speed information at two decision points: when choosing which d servers to query and when assigning a job to one of those servers. Our framework explicitly separates the dispatching policy into a querying rule and an assignment rule; we consider general families of both rule types. While the strongest assignment rules incorporate both detailed queue-length information and server speed information, these rules typically are difficult to analyze. We overcome this difficulty by focusing on heterogeneity-aware assignment rules that ignore queue length information beyond idleness status. In this setting, we analyze mean response time and formulate novel optimization problems for the joint optimization of querying and assignment. We build upon our optimized policies to develop heuristic queue length-aware dispatching policies. Our heuristic policies perform well in simulation, relative to policies that have appeared in the literature.
PubDate: 2022-04-28

• Tandem fluid queue with long-range dependent inputs: sticky behaviour and
heavy traffic approximation

Abstract: Abstract Empirical studies have shown that traffic in communication networks exhibits long-range dependence. Cumulative network traffic is often thought to be well modelled by a fractional Brownian motion (fBm). FBm approximations of queueing systems have also been well justified by theoretical results, and most of this achievements are based on one Hurst parameter. However, just as pointed out by Konstantopoulos and Lin (in: Glasserman, Sigman, and Yao (eds) Stochastic Networks: Stability and Rare Events. Lecture Notes in Statistics, Springer-Verlag, New York, 1996), various Hurst parameters may be more appropriate. At the same time, sticky Brownian motions on the half-line have many applications in queueing theory, and could be obtained as heavy traffic limits of queueing systems with exceptional service (arrive) mechanisms. In this paper, reflected operator fractional Brownian motion, sticky operator fractional Brownian motion, and a d-node tandem fluid queue with long-range dependent inputs and sticky boundaries are constructed. Moreover, in heavy traffic environment, it is shown that the scaled buffer-content process of the d-node tandem queue converges weakly to a sticky operator Brownian motion.
PubDate: 2022-04-20

• Correction to: Extremal GI/GI/1 queues given two moments: exploiting
Tchebycheff systems

PubDate: 2022-04-16

• Strategic customer behavior and optimal policies in a passenger–taxi
double-ended queueing system with multiple access points and nonzero
matching times

Abstract: Abstract This paper considers an observable double-ended queueing system of passengers and taxis, where matching times follow an exponential distribution. We assume that passengers are strategic and decide to join the queue only if their expected utility is nonnegative. We show that the strategy of passengers is represented by a unique vector of thresholds corresponding to different cases of the number of taxis observed in the system upon passenger arrival. Furthermore, we develop a heuristic algorithm to find an optimal range of fees to be levied on passengers to maximize social welfare or revenues.
PubDate: 2022-04-13

• On the Gittins index for multistage jobs

Abstract: Abstract Optimal scheduling in single-server queueing systems is a classic problem in queueing theory. The Gittins index policy is known to be the optimal nonanticipating policy minimizing the mean delay in the M/G/1 queue. While the Gittins index is thoroughly characterized for ordinary jobs whose state is described by the attained service, it is not at all the case with jobs that have more complex structure. Recently, a class of such jobs, multistage jobs, were introduced, and it was shown that the computation of Gittins index of a multistage job decomposes into separable computations for the individual stages. The characterization is, however, indirect in the sense that it relies on the recursion for an auxiliary function (the so-called SJP—single-job profit—function) and not for the Gittins index itself. In this paper, we focus on sequential multistage jobs, which have a fixed sequence of stages, and prove that, for them, it is possible to compute the Gittins index directly by recursively combining the Gittins indices of its individual stages. In addition, we give sufficient conditions for the optimality of the FCFS and SERPT disciplines for scheduling sequential multistage jobs. On the other hand, we demonstrate that, for nonsequential multistage jobs, it is better to compute the Gittins index by utilizing the SJP functions.
PubDate: 2022-04-07

• Fluid limits for shortest job first with aging

Abstract: Abstract We investigate fluid scaling of single-server queues operating under a version of shortest job first (SJF) where the priority level undergoes aging. That is, a job’s priority level is initialized by its size and varies smoothly in time according to an ordinary differential equation. Linear and exponential aging rules are special cases of this model. This policy can be regarded as an interpolation between FIFO and SJF. We use the measure-valued Skorokhod map to characterize the fluid model and establish convergence under fluid scale. We treat in detail examples of linear and exponential aging rules and provide a performance criterion based on our main result.
PubDate: 2022-04-04

JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762