Stability conditions of the N N -model with a waiting time dependent threshold on the diagonal
Sanne van Kempen, Elene Anton, Fiona Sloothaak · 2025
Read Stability conditions of the N N -model with a waiting time dependent threshold on the diagonal by Sanne van Kempen, Elene Anton, Fiona Sloothaak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-11488.txt.
Introduction
Sanne van Kempen, Elene Anton, and Fiona Sloothaak settle a stability question for skill-based queues where some service options open only after a customer has waited past a fixed threshold. Service otherwise follows first-come, first-served order, as in call centers where only trained staff may handle certain requests after a delay.
Surprisingly, the thresholds turn out not to affect stability at all, a fact suspected but never proved before. Necessity follows from a coupling argument, while sufficiency needs a piecewise deterministic Markov process model and a carefully built Lyapunov function with negative drift. Queue designers can now set waiting thresholds without fearing hidden instability.
Catalog record
| CREATOR | Sanne van Kempen, Elene Anton, Fiona Sloothaak |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-11488
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stability conditions of the N N -model with a waiting time dependent threshold on the diagonal Sanne van Kempen, Elene Anton, Fiona Sloothaak Abstract We consider the N N -model queueing system with a waiting time dependent threshold on the diagonal: the service discipline is First–Come–First–Served, but type-1 jobs can only be served by server 2 if their waiting time exceeds a deterministic threshold. We prove the necessary and sufficient stability conditions for this model—an intuitive result that has not been established in literature up to this point. Our proof relies on coupling the queue length process to a carefully constructed upper (and lower) bound system, and establishing stochastic dominance for the queue length process. 1 Introduction We consider a queueing system with two job types, two servers, and skill-based service: type-1 jobs can be processed by both servers while type-2 jobs can only be processed by server 2. Due to its layout, see Figure 1(a) , this model is also known as the N -model [ 7 ] . We are interested in the stability of the N -model under a waiting time dependent service policy: the service discipline is First–Come–First–Served (FCFS) , but a type-1 job can only be processed by server 2 if its waiting time exceeds a deterministic threshold T\in\mathbb{R}_{>0} . The stability region, i.e., the set of arrival rates for which the queue length process is positive recurrent, is well-established in the case of T=0 . In particular, the authors of [ 1 ] show that the stability region for T=0 is defined by the following set of conditions, \displaystyle\lambda_{1}+\lambda_{2} \displaystyle<\mu_{1}+\mu_{2}, (1a) \displaystyle\lambda_{2} \displaystyle<\mu_{2}, (1b) where \lambda_{i} and \mu_{i} denote the arrival rate of type- i jobs and the service rate of server i , respectively. In case of a positive threshold ( T>0 ), we note that when queue lengths grow large, the waiting time of the First–In–Line (FIL) type-1 job would typically exceed T . As the system then behaves as a regular N -model with service discipline FCFS , it should come as no surprise that the stability conditions should coincide with ( 1 ) for any T\geq 0 . Yet, this result has not been rigorously proven before in the literature. In fact, despite the widespread use of waiting time dependent thresholds in skill-based queues in practice [ 7 ] , this service discipline is not well-studied in literature due to its complexity. The queue length process, which is often used for system analysis in literature, is not Markovian since the service discipline depends on job waiting times. The waiting time process of the FIL jobs can be shown to have negative drift when the values are sufficiently large. However, due to the deterministic threshold, the drift is discontinuous. To show positive recurrence, one would need to prove the existence of a continuous Lyapunov function that can deal with the discontinuities. The authors of [ 8 ] tackle this by considering a collection of different functions and applying a smoothing function. However, their result only holds for a countable state space Birth–Death (BD) process with a finite number of discontinuities. To the best of our knowledge, no extensions of the result of [ 8 ] exist for uncountably infinite state spaces. Lastly, it is non-trivial to prove stability using fluid scalings. Depending on the buildup of waiting times, the system may alternate between stable and unstable phases, with unpredictable switching points. It is therefore difficult to analyze the shift in departure rate for type-1 jobs from \mu_{1} to \mu_{1}+\mu_{2} , which depends on whether a job has waited at least T time units. In this paper, we prove the necessary and sufficient stability conditions for the N -model with a waiting time dependent threshold on the diagonal ( Theorem 1 ). The most challenging aspect regards proving sufficiency, which we do by considering a model with an altered service discipline: type-1 jobs cannot be served by either server until their waiting time exceeds T . This can be considered as introducing an infinite-server queue with deterministic service time T in tandem fashion, as shown in Figure 1(b) . We refer to this system as the upper bound (UB) system. We couple the arrival and service processes between the two systems in an appropriate way and show that the number of waiting jobs in the original (OR) system is always upper bounded by the number of jobs in the UB system. The analysis is delicate due to the service discipline: for example, it is not true that any job departs later in the UB system than in the OR system. \downarrow\lambda_{1} \downarrow\lambda_{2} \mu_{1} \mu_{2} T (a) OR system with deterministic waiting time threshold T on the diagonal. \infty \downarrow\lambda_{1} \downarrow\lambda_{2} \mu_{1} \mu_{2} (b) UB system with an additional infinite-server queue with a deterministic service time of T time units for type-1 jobs. Service is FCFS . Figure 1 : Schematic overview of the N -model under two service disciplines. Here, the \lambda_{i} denote the arrival rates, \mu_{j} the service rates, and T the deterministic threshold. 1.1 Literature overview The literature on skill-based queueing systems is extensive, although service disciplines with deterministic waiting time thresholds are not considered often. Broadly speaking, the literature can be categorized as follows. • The service discipline is fully determined by the number of jobs in the system and, in some cases, their arrival order. For these disciplines, the queue length process is a countable Markov process and therefore methods for countable state space Markov processes can be applied. For example, the authors of [ 1 , 11 , 2 ] exploit a carefully chosen representation of the state space to derive a product-form expression for the stationary distribution of the queue length process of various skill-based queueing systems with FCFS service. In our model however, the queue length process is not Markovian since the service discipline depends on the waiting time of the FIL type-1 job. Hence, such methods cannot be applied directly. • A discretized Markov chain is used as approximation of the continuous waiting time process. For the N -model with waiting time threshold on the diagonal, the authors of [ 9 , 10 ] apply the Erlang Approximation method to discretize the waiting time of the FIL job and find the approximated stationary distribution of the queue length process by solving a set of balance equations. • Studies of systems with only one job type and/or a single server. The authors of [ 3 ] consider a queueing system with a single job type and two servers with waiting time dependent overflow to the secondary server. The authors derive the steady-state waiting-time distribution of jobs using level-crossing equations. This method does not easily extend to models with more than one job type, due to dependences between waiting time processes of different job types. Since the techniques in the aforementioned works do not naturally extend to the N -model with a deterministic waiting time threshold on the diagonal, we develop an alternative approach based on coupling arguments to establish stability conditions. 2 Model description We consider a continuous-time queueing system with two job types and two servers. Type- i jobs arrive according to an independent