Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract A new approach is developed for the joint queue-length distribution of the two-level non-pre-emptive M/M/c (i.e. Markovian) priority queue that allows explicit and exact results to be obtained. Marginal distributions are derived for the general multi-level problem. The results are based on a representation of the joint queue-length probability mass function as a single-variable complex contour integral, which reduces to a real integral on a finite interval arising from a cut on the real axis. Both numerical quadrature rules and exact finite sums, involving Legendre polynomials and their generalization, are presented for the joint and marginal distributions. A high level of accuracy is demonstrated across the entire ergodic region. Relationships are established with the waiting-time distributions. Asymptotic behaviour in the large queue-length regime is extracted. PubDate: 2024-06-03

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We study in this paper a variation of the acclaimed carrier sense multiple access (CSMA) protocol. A random access algorithm is where back-off rates depend on the state of the network through queue lengths. We provide the first case where full proof of convergence to fluid limits can be obtained. Although this has been often justified informally, this is the first proof dedicated to obtaining this result formally. We then outline the difficulties arising when queues reach zero and solve them in the case of a complete interference graph. The main contribution of this paper is to provide a formal justification of the fluid limits for a complete interference graph in the case where some initial queue lengths are zero. This is done with a coupling argument. This paper also proves convergence to the fluid limits in the general case up to the time a queue reaches 0 on the fluid scale. PubDate: 2024-05-30

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract This paper studies a diffusion control problem motivated by challenges faced by public health agencies who run clinics to serve the public. A key challenge for these agencies is to motivate individuals to participate in the services provided. They must manage the flow of (voluntary) participants so that the clinic capacity is highly utilized, but not overwhelmed. The organization can deploy costly promotion activities to increase the inflow of participants. Ideally, the system manager would like to have enough participants waiting in a queue to serve as many individuals as possible and efficiently use clinic capacity. However, if too many participants sign up, resulting in a long wait, participants may become irritated and hesitate to participate again in future. We develop a diffusion model of managing participant inflow mechanisms. Each mechanism corresponds to choosing a particular drift rate parameter for the diffusion model. The system manager seeks to balance three different costs optimally: (i) a linear holding cost that captures the congestion concerns, (ii) an idleness penalty corresponding to wasted clinic capacity and negative impact on public health, and (iii) costs of promotion activities. We show that a nested-threshold policy for deployment of participant inflow mechanisms is optimal under the long-run average cost criterion. In this policy, the system manager progressively deploys mechanisms in increasing order of cost, as the number of participants in the queue decreases. We derive explicit formulas for the queue length thresholds that trigger each promotion activity, providing the system manager with guidance on when to use each mechanism. PubDate: 2024-05-18

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Motivated by applications in queueing theory, we consider a class of singular stochastic control problems whose state space is the d-dimensional positive orthant. The original problem is approximated by a drift control problem, to which we apply a recently developed computational method that is feasible for dimensions up to \(d=30\) or more. To show that nearly optimal solutions are obtainable using this method, we present computational results for a variety of examples, including queueing network examples that have appeared previously in the literature. PubDate: 2024-05-17

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We consider multi-component matching systems in heavy traffic consisting of \(K\ge 2\) distinct perishable components which arrive randomly over time at high speed at the assemble-to-order station, and they wait in their respective queues according to their categories until matched or their “patience" runs out. An instantaneous match occurs if all categories are available, and the matched components leave immediately thereafter. For a sequence of such systems parameterized by n, we establish an explicit definition for the matching completion process, and when all the arrival rates tend to infinity in concert as \(n\rightarrow \infty \) , we obtain a heavy traffic limit of the appropriately scaled queue lengths under mild assumptions, which is characterized by a coupled stochastic integral equation with a scalar-valued nonlinear term. We demonstrate some crucial properties for certain coupled equations and exhibit numerical case studies. Moreover, we establish an asymptotic Little’s law, which reveals the asymptotic relationship between the queue length and its virtual waiting time. Motivated by the cost structure of blood bank drives, we formulate an infinite-horizon discounted cost functional and show that the expected value of this cost functional for the nth system converges to that of the heavy traffic limiting process as n tends to infinity. PubDate: 2024-04-02 DOI: 10.1007/s11134-024-09907-0

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Exact explicit results are derived for the distribution of the partial busy period of the M/M/c multi-server queue for a general number of servers. A rudimentary spectral method leads to a representation that is amenable to efficient numerical computation across the entire ergodic region. An alternative algebraic approach yields a representation as a finite sum of Marcum Q-functions depending on the roots of certain polynomials that are explicitly determined for an arbitrary number of servers. Asymptotic forms are derived in the limit of a large number of servers under two scaling regimes, and also for the large-time limit. Connections are made with previous work. The present work is the first to offer tangible exact results for the distribution when the number of servers is greater than two. PubDate: 2024-04-02 DOI: 10.1007/s11134-024-09906-1

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Motivated by a service platform, we study a two-sided network where heterogeneous demand (customers) and heterogeneous supply (workers) arrive randomly over time to get matched. Customers and workers arrive with a randomly sampled patience time (also known as reneging time in the literature) and are lost if forced to wait longer than that time to be matched. The system dynamics depend on the matching policy, which determines when to match a particular customer class with a particular worker class. Matches between classes use the head-of-line customer and worker from each class. Since customer and worker arrival processes can be very general counting processes, and the reneging times can be sampled from any finite mean distribution that is absolutely continuous, the state descriptor must track the age-in-system for every customer and worker waiting in order to be Markovian, as well as the time elapsed since the last arrival for every class. We develop a measure-valued fluid model that approximates the evolution of the discrete-event stochastic matching model and prove its solution is unique under a fixed matching policy. For a sequence of matching models, we establish a tightness result for the associated sequence of fluid-scaled state descriptors and show that any distributional limit point is a fluid model solution almost surely. When arrival rates are constant, we characterize the invariant states of the fluid model solution and show convergence to these invariant states as time becomes large. Finally, again when arrival rates are constant, we establish another tightness result for the sequence of fluid-scaled state descriptors distributed according to a stationary distribution and show that any subsequence converges to an invariant state. As a consequence, the fluid and time limits can be interchanged, which justifies regarding invariant states as first order approximations to stationary distributions. PubDate: 2024-04-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We characterize the impact of scheduling policies on the mean response time in nested systems with cancel-on-complete redundancy. We consider not only class- and state-oblivious policies such as FCFS and ROS, but also class-based, and, in particular, redundancy-aware policies of the form \(\Pi _1-\Pi _2\) , where \(\Pi _1\) discriminates among job classes based on their degree of redundancy (e.g., Least-Redundant-First (LRF), Most-Redundant-First (MRF)) and \(\Pi _2\) discriminates among jobs of the same class. Assuming that jobs have independent and identically distributed (i.i.d.) copies we prove the following: (i) When jobs have exponential service times, LRF policies outperform any other policy. (ii) When service times are New-Worse-than-Used, MRF-FCFS outperforms LRF-FCFS as the variability of the service time grows infinitely large. (iii) When service times are New-Better-than-Used, LRF-ROS (resp. MRF-ROS) outperforms LRF-FCFS (resp. MRF-FCFS) in a two-server system. Statement (iii) also holds when job sizes follow a general distribution and have identical copies (all the copies of a job have the same size). Moreover, we show via simulation that, for a large class of redundancy systems, class-based (and, in particular, redundancy-aware) policies can considerably improve the mean response time compared to policies that ignore the class. We also explore the effect of redundancy on the stability region. PubDate: 2024-03-22 DOI: 10.1007/s11134-024-09904-3

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We present a detailed study of the time-dependent behavior of both the queue-length process and the workload process of various types of preemptive Last-Come-First-Served queueing systems, such as the preemptive repeat different and preemptive repeat identical models recently studied in Asmussen and Glynn (Queue Syst 87:1–22, 2017) and Bergquist and Sigman (Stoch Models 38:515–544, 2022). Our main results show that various quantities that provide information about the time-dependent behavior of these processes can be expressed in terms of the Laplace-Stieltjes transform of the busy period, and we show how a natural coupling procedure can be used to establish, for each preemptive queue we consider, a recursive procedure for calculating these busy period transforms on the set of all complex numbers having positive real part. PubDate: 2024-03-14 DOI: 10.1007/s11134-024-09905-2

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract This paper examines the performance of multi-class, multi-server bipartite queueing systems, where each arriving customer is compatible with only a subset of servers. We focus on the system’s performance under a first-come, first-served-assign longest idle server service discipline. In this discipline, an idle server is matched with the compatible customer who has been waiting the longest, and a customer who can be served by multiple idle servers is routed to the server that has been idle for the longest period. We analyse the system under conventional heavy-traffic conditions, where the traffic intensity approaches one from below. Building upon the formulation and results of Afèche et al. (Oper Res 70(1):363–401, 2022), we generalize the model by allowing the vector of arrival rates to approach the heavy-traffic limit from an arbitrary direction. We characterize the steady-state waiting times of the various customer classes and demonstrate that a much wider range of waiting time outcomes is achievable. Furthermore, we establish that the matching probabilities, i.e. the probabilities of different customer classes being served by different servers, do not depend on the direction along which the system approaches heavy traffic. We also investigate the design of compatibility between customer classes and servers, finding that a service provider who has complete control over the matching can design a delay-minimizing matching by considering only the limiting arrival rates. When some constraints on the compatibility structure exist, the direction of convergence to heavy-traffic affects which compatibility structure minimizes delay. Additionally, we discover that the bipartite matching queueing system exhibits a form of Braess’s paradox, where adding more connectivity to an existing system can lead to higher average waiting times, despite the fact that neither customers nor servers act strategically. PubDate: 2024-03-02 DOI: 10.1007/s11134-024-09903-4

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We consider the optimal scheduling problem in a multiserver queue with impatient customers belonging to multiple classes. We assume that each customer has a random abandonment time, after which the customer leaves the system if its service has not been completed before that. In addition, we assume that the scheduler is not able to anticipate the expiration of the abandonment times but only knows their distributions and how long each customer has been in the system. Many papers consider this scheduling problem under Poisson arrivals and linear holding costs assuming further that both the service times and the abandonment times have exponential distributions. Even with these additional assumptions, the exact solution is known only in very few special cases. To tackle this tricky problem, we apply the Whittle index approach. Unlike the earlier papers, which were restricted to exponential service times, we allow the service time distributions for which the hazard rate is decreasing. The Whittle index approach is applied to the discrete-time multiserver queueing problem with discounted costs. As our main theoretical result, we prove that the related relaxed optimization problem is indexable and derive the corresponding Whittle index explicitly. Based on this discrete-time result, we develop a reasonable heuristic for the original continuous-time multiserver scheduling problem. The performance of the resulting policy is evaluated in the M/G/M setup by numerical simulations, which demonstrate that it, indeed, gives better performance than the other policies included in the comparison. PubDate: 2024-02-19 DOI: 10.1007/s11134-024-09902-5

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract A system manager makes dynamic pricing and dispatch control decisions in a queueing network model motivated by ride hailing applications. A novel feature of the model is that it incorporates travel times. Unfortunately, this renders the exact analysis of the problem intractable. Therefore, we study this problem in the heavy traffic regime. Under the assumptions of complete resource pooling and common travel time and routing distributions, we solve the problem in closed form by analyzing the corresponding Bellman equation. Using this solution, we propose a policy for the queueing system and illustrate its effectiveness in a simulation study. PubDate: 2024-02-04 DOI: 10.1007/s11134-023-09901-y

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We study service rate control problems for an M/M/1 queue with server breakdowns in which the breakdown rate is assumed to be a function of the service rate. Assuming that the queue has infinite capacity, we first establish the optimality equations for the discounted cost problem and characterize the optimal rate control policies. Then, we characterize the ergodicity of the controlled queue and establish the optimality conditions for the average-cost (ergodic) control problem using the vanishing discounted method. We next study the ergodic control problem when the queue has a finite capacity and establish a verification theorem by directly involving the stationary distribution of the controlled Markov process. For practical applications, we consider the adaptive service rate control problem for the model with finite capacity. Studying this problem is useful because the relationship between the server breakdown rate and the service rate is costly to observe in practice. We propose an adaptive (self-tuning) control algorithm, assuming that the relationship between the server breakdown rate and the service rate is linear with unknown parameters. We prove that the regret vanishes under the algorithm and the proposed policies are asymptotically optimal. In addition, numerical experiments are conducted to validate the algorithm. PubDate: 2024-01-05 DOI: 10.1007/s11134-023-09900-z

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Batch service queueing systems are basically classified into two types: a time-based system in which the service facilities depart according to inter-departure times that follows a given distribution, such as the conventional bus system, and a demand-responsive system in which the vehicles start traveling provided that a certain number of customers gather at the waiting space, such as ride-sharing and on-demand bus. Motivated by the recent spreading of demand-responsive transportation, this study examines the M/M \(^{\textit{X}}\) / \(\infty \) queue. In this model, whenever the number of waiting customers reaches a capacity set by a discrete random variable \(\textit{X}\) , customers are served by a group. We formulate the M/M \(^{\textit{X}}\) / \(\infty \) queue as a three-dimensional Markov chain whose dimensions are all unbounded and depict a book-type transition diagram. The joint stationary distribution for the number of busy servers, number of waiting customers, and batch size is derived by applying the method of factorial moment generating function. The central limit theorem is proved for the case that \(\textit{X}\) has finite support under heavy traffic using the exact expressions of the first two moments of the number of busy servers. Moreover, we show that the M/M \(^\textit{X}\) / \(\infty \) queue encompasses the time-based infinite server batch service queue (M/M \(^{G(x)}\) / \(\infty \) queue), which corresponds to the conventional bus system, under a specific heavy traffic regime. In this model, the transportation facility departs periodically according to a given distribution, \(\textit{G(x)}\) , and collects all the waiting customers for a batch service for an exponentially distributed time corresponding to the traveling time on the road. We show a random variable version of Little’s law for the number of waiting customers for the M/M \(^{G(x)}\) / \(\infty \) queue. Furthermore, we present a moment approach to obtain the distribution and moments of the number of busy servers in a GI/M/ \(\infty \) queue by utilizing the M/M \(^{G(x)}\) / \(\infty \) queue. Finally, we provide some numerical results and discuss their possible applications on transportation systems. PubDate: 2023-12-16 DOI: 10.1007/s11134-023-09898-4

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Motivated by queueing applications, we study various reflected autoregressive processes with dependencies. Among others, we study cases where the interarrival and service times are proportionally dependent on additive and/or subtracting delay, as well as cases where interarrival times depend on whether the service duration of the previous arrival exceeds or not a random threshold. Moreover, we study cases where the autoregressive parameter is constant as well as a discrete or a continuous random variable. More general dependence structures are also discussed. Our primary aim is to investigate a broad class of recursions of autoregressive type for which several independence assumptions are lifted and for which a detailed exact analysis is provided. We provide expressions for the Laplace transform of the waiting time distribution of a customer in the system in terms of an infinite sum of products of known Laplace transforms. An integer-valued reflected autoregressive process that can be used to model a novel retrial queueing system with impatient customers and a general dependence structure is also considered. For such a model, we provide expressions for the probability generating function of the stationary orbit queue length distribution in terms of an infinite sum of products of known generating functions. A first attempt towards a multidimensional setting is also considered. PubDate: 2023-12-14 DOI: 10.1007/s11134-023-09899-3

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Various load balancing policies are known to achieve vanishing waiting times in the large-scale limit, that is, when the number of servers tends to infinity. These policies either require a communication overhead of one message per job or require job size information. Load balancing policies with an overhead below one message per job are called hyperscalable policies. While these policies often have bounded queue length in the large-scale limit and work well when the overhead is somewhat below one, they show poor performance when the communication overhead becomes small, that is, the mean response time tends to infinity when the overhead tends to zero even at low loads. In this paper, we introduce a hyperscalable load balancing policy, called Join-Up-To(m), that remains effective even when the communication overhead tends to zero. To study its performance under general job size distributions, we make use of the “queue at the cavity" approach. We provide explicit results for the first two moments of the response time, the generating function of the queue length distribution and the Laplace transform of the response time. These results show that the mean response time only depends on the first two moments of the job size distribution. PubDate: 2023-11-15 DOI: 10.1007/s11134-023-09897-5

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We study reflecting Brownian motion with drift constrained to a wedge in the plane. Our first set of results provides necessary and sufficient conditions for existence and uniqueness of a solution to the corresponding submartingale problem with drift, and show that its solution possesses the Markov and Feller properties. Next, we study a version of the problem with absorption at the vertex of the wedge. In this case, we provide a condition for existence and uniqueness of a solution to the problem and some results on the probability of the vertex being reached. PubDate: 2023-10-24 DOI: 10.1007/s11134-023-09893-9

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We consider a system of two parallel discrete-time single-server queues, queue 1 and queue 2. The service time of any customer in either queue is equal to 1 time slot. Arrivals during consecutive slots occur independently from slot to slot. However, the arrival streams into both queues are possibly mutually interdependent, i.e., during any slot, the numbers of arrivals in queue 1 and queue 2 need not be statistically independent. Their joint probability generating function (pgf) A(x, y) fully characterizes the queueing model. As a consequence of the possible intra-slot correlation in the arrival process, the numbers of customers present (“system contents”) in queues 1 and 2, at any given slot boundary, are not necessarily independent either. In a previous paper, we have already discussed the mathematical difficulty of computing their steady-state joint pgf \(U(z_1,z_2)\) ; explicit closed-form results can only be obtained for specific choices of A(x, y). In this paper, we therefore look at the problem from an other angle. Specifically, we study the (asymptotic) conditional steady-state behavior of the system under the condition that the content of queue 1 is (temporarily) very high (goes to infinity). For ease of terminology, we refer to the system as the “asymptotic system” in these circumstances. We prove that the asymptotic system is nearly identical to the original (unconditional) system, but with a modified joint arrival pgf \(A^*(x,y)\) that can be computed explicitly from A(x, y). This fundamental result allows us to determine the stability condition of queue 2 in the asymptotic system, and explicitly compute the classical queueing performance metrics of queue 2, such as the pgf, the moments and the approximate tail distribution of its system content, when this condition is fulfilled. It also leads to accurate approximative closed-form expressions for the joint tail distribution of the system contents in both queues, in the original (unconditional) system. We extensively illustrate our methodology by means of various specific (popular) choices of A(x, y). In some examples, where an explicit solution for \(U(z_1,z_2)\) or for the (approximative) joint tail distribution is known, we retrieve the known results easily. In other cases, new results are found for arrival pgfs A(x, y) for which no explicit results were known until now. PubDate: 2023-10-17 DOI: 10.1007/s11134-023-09894-8

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract This paper concerns a modified version of the Lindley recursion, where the recursion equation is given by \(W_{i+1} = [V_{i} W_{i} + Y_{i}]^{+}\) , with \(\{V_i\}_{i=0}^{\infty }\) and \(\{Y_i\}_{i=0}^{\infty }\) being two independent sequences of i.i.d. random variables. Additionally, we assume that the \(V_i\) take values in \((-\infty , 1]\) and the \(Y_i\) have a rational Laplace–Stieltjes transform. Under these assumptions, we investigate the transient and steady-state behaviors of the process \(\{W_i\}_{i=0}^{\infty }\) by deriving an expression for the generating function of the Laplace–Stieltjes transform of the \(W_i\) . PubDate: 2023-08-17 DOI: 10.1007/s11134-023-09886-8