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: This paper aims to provide several further results for a queueing model recently discussed by Chen et al. (Queueing Syst 95:331–378, 2020), i.e. the Markovian bulk-arrival and bulk-service queue incorporating the general state-dependent control. We use an alternative method which is based on the resolvent decomposition theorem to obtain the important results for this model in this paper, including the important questions regarding equilibrium behaviour, queue length behaviour, hitting time and busy period distributions. Furthermore, a set of interesting examples are also provided in the last section. PubDate: 2023-01-05

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: 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-12-01 DOI: 10.1007/s11134-022-09736-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: 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-12-01 DOI: 10.1007/s11134-022-09786-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: 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-12-01 DOI: 10.1007/s11134-022-09760-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: 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-12-01 DOI: 10.1007/s11134-022-09737-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: 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-12-01 DOI: 10.1007/s11134-022-09850-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: We consider open multi-class queueing networks with general arrival processes, general processing time sequences and Bernoulli routing. The network is assumed to be operating under an arbitrary work-conserving scheduling policy that makes the system stable. We study the variability of flows within the network. Computable expressions for quantifying flow variability have previously been discussed in the literature. However, in this paper, we shed more light on such analysis to justify the use of these expressions in the asymptotic analysis of network flows. Toward that end, we find a simple diffusion limit for the inter-class flows and establish the relation to asymptotic (co-)variance rates. PubDate: 2022-11-24

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: A single server commences its service at time zero every day. A random number of customers decide when to arrive to the system so as to minimize the waiting time and tardiness costs. The costs are proportional to the waiting time and the tardiness with rates \(\alpha \) and \(\beta \) , respectively. Each customer’s optimal arrival time depends on the others’ decisions; thus, the resulting strategy is a Nash equilibrium. This work considers the estimation of the ratio \(\displaystyle \theta \equiv \beta /(\alpha +\beta )\) from queue length data observed daily at discrete time points, given that customers use a Nash equilibrium arrival strategy. A method of moments estimator is constructed from the equilibrium conditions. Remarkably, the method does not require estimation of the Nash equilibrium arrival strategy itself, or even an accurate estimate of its support. The estimator is strongly consistent, and the estimation error is asymptotically normal. Moreover, the asymptotic variance of the estimation error as a function of the queue length covariance matrix (at sampling times) is derived. The estimator performance is demonstrated through simulations and is shown to be robust to the number of sampling instants each day. PubDate: 2022-11-10 DOI: 10.1007/s11134-022-09867-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: The service sector is an indisputable and fundamental pillar of today’s business world, encompassing nearly 80 percent of the workforce in the USA. Service operations management has been a fertile research area addressing strategic, tactical and operational challenges related to service systems. Such problems usually have a complex, dynamic stochastic nature, often leading to models that are both analytically and computationally complicated. In such cases, fluid deterministic models that approximate the dynamics of stochastic/queueing systems can yield accurate and tractable optimization formulations. These formulations enable the construction of intuitive, insightful policies that are implementable in practice, even in time-varying systems. This paper focuses on the applicative aspects of fluid models in addressing various problems in service and healthcare operations management. We review the literature on fluid model applications, discuss the situations in which fluid models are less adequate as well as the implementation of a fluid-based policy into a stochastic discrete system. Lastly, we identify future research opportunities and challenges that have yet to be addressed. PubDate: 2022-11-05 DOI: 10.1007/s11134-022-09868-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: We consider the M/D/1 retrial queueing system with constant retrial times, which makes up a natural abstraction for optical fibre delay line buffers. Drawing on a time-discretisation approach and on an equivalence with polling systems, we find explicit expressions for the distribution of the number of retrials, and the probability generating function of the number of customers in orbit. While the state space of the queueing system at hand is complicated, the results are strikingly simple. The number of retrials follows a geometric distribution, while the orbit size decomposes into two independent random variables: the system content of the M/D/1 queue at departure times and the orbit size of the M/D/1 retrial queue when the server is idle. We finally obtain explicit expressions for the retrial rate after a departure and for the distribution of the time until the nth retrial after a departure. PubDate: 2022-10-29 DOI: 10.1007/s11134-022-09866-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: We consider a stochastic fluid network where the external input processes are compound Poisson with heavy-tailed Weibullian jumps. Our results comprise of large deviations estimates for the buffer content process in the vector-valued Skorokhod space which is endowed with the product \(J_1\) topology. To illustrate our framework, we provide explicit results for a tandem queue. At the heart of our proof is a recent sample-path large deviations result, and a novel continuity result for the Skorokhod reflection map in the product \(J_1\) topology. PubDate: 2022-09-27 DOI: 10.1007/s11134-022-09865-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: In this paper, we study a functional equation for generating functions of the form \(f(z) = g(z) \sum _{i=1}^M p_i f(\alpha _i(z)) + K(z)\) , viz. a recursion with multiple recursive terms. We derive and analyze the solution of this equation for the case that the \(\alpha _i(z)\) are commutative contraction mappings. The results are applied to a wide range of queueing, autoregressive and branching processes. PubDate: 2022-09-04 DOI: 10.1007/s11134-022-09861-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: We consider a discrete-time two-dimensional quasi-birth-and-death process (2d-QBD process for short) \(\{(\varvec{X}_n,J_n)\}\) on \(\mathbb {Z}_+^2\times S_0\) , where \(\varvec{X}_n=(X_{1,n},X_{2,n})\) is the level state, \(J_n\) the phase state (background state) and \(S_0\) a finite set, and study asymptotic properties of the stationary tail distribution. The 2d-QBD process is an extension of usual one-dimensional QBD process. By using the matrix analytic method of the queueing theory and the complex analytic method, we obtain the asymptotic decay rate of the stationary tail distribution in an arbitrary direction. This result is an extension of the corresponding result for a certain two-dimensional reflecting random work without background processes, obtained by using the large deviation techniques and the singularity analysis methods. We also present a condition ensuring the sequence of the stationary probabilities geometrically decays without power terms, asymptotically. Asymptotic properties of the stationary tail distribution in the coordinate directions in a 2d-QBD process have already been studied in the literature. The results of this paper are also important complements to those results. PubDate: 2022-08-30 DOI: 10.1007/s11134-022-09860-w

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: The H-derivative of the expected supremum of fractional Brownian motion \(\{B_H(t),t\in {\mathbb {R}}_+\}\) with drift \(a\in {\mathbb {R}}\) over time interval [0, T] $$\begin{aligned} \frac{\partial }{\partial H} {\mathbb {E}}\Big (\sup _{t\in [0,T]} B_H(t) - at\Big ) \end{aligned}$$ at \(H=1\) is found. This formula depends on the quantity \({\mathscr {I}}\) , which has a probabilistic form. The numerical value of \({\mathscr {I}}\) is unknown; however, Monte Carlo experiments suggest \({\mathscr {I}}\approx 0.95\) . As a by-product we establish a weak limit theorem in C[0, 1] for the fractional Brownian bridge, as \(H\uparrow 1\) . PubDate: 2022-08-30 DOI: 10.1007/s11134-022-09859-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: This paper studies the subexponential asymptotics of the stationary distribution vector of an asymptotically block-Toeplitz and upper block-Hessenberg (atUBH) Markov chain in discrete time. The atUBH Markov chain is a kind of the upper block-Hessenberg (UBH) one and is a generalization of the M/G/1-type one. The atUBH Markov chain typically arises from semi-Markovian retrial queues, as the queue-length process, its embedded process, or appropriately time-scaled versions of these processes. In this paper, we present subexponential and locally subexponential asymptotic formulas for the stationary distribution vector. We then extend the locally subexponential asymptotic formula to a continuous-time version of the atUBH Markov chain by uniformization and change of time scale. This extension expands the applicability of the locally subexponential asymptotic formula. PubDate: 2022-08-30 DOI: 10.1007/s11134-022-09857-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: This paper analyzes various stochastic recursions that arise in queueing and insurance risk models with a ‘semi-linear’ dependence structure. For example, an interarrival time depends on the workload, or the capital, immediately after the previous arrival; or the service time of a customer depends on her waiting time. In each case, we derive and solve a fixed-point equation for the Laplace–Stieltjes transform of a key performance measure of the model, like waiting time or ruin time. PubDate: 2022-08-29 DOI: 10.1007/s11134-022-09863-7

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: Ticket queues are popular in many service systems. Upon arrival, each customer is issued a numbered ticket and receives service on a first-come-first-served basis according to the ticket number. There is no physical queue; customers may choose to walk away and return later (before their numbers are called) to receive service. We study the problem of optimal staffing in such a system with two capacity levels, where the staffing decision can only be based on ticket numbers, as opposed to the physical queue length in a traditional system. Using renewal reward theorem, we first derive the long-run average total cost (including customer delay and abandonment costs, operating cost and cost for changing staffing levels) and then obtain the optimal solution using fractional programming. In addition, we pursue a random-walk analysis, which leads to some highly accurate approximations. PubDate: 2022-08-26 DOI: 10.1007/s11134-022-09854-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: We introduce a transient reflected Brownian motion in a multidimensional orthant, which is either absorbed at the apex of the cone or escapes to infinity. We address the question of computing the absorption probability, as a function of the starting point of the process. We provide a necessary and sufficient condition for the absorption probability to admit an exponential product form, namely that the determinant of the reflection matrix is zero. We call this condition a dual skew symmetry. It recalls the famous skew symmetry introduced by Harrison (Adv Appl Probab 10:886–905, 1978), which characterizes the exponential stationary distributions in the recurrent case. The duality comes from that the partial differential equation satisfied by the absorption probability is dual to the one associated with the stationary distribution in the recurrent case. PubDate: 2022-08-13 DOI: 10.1007/s11134-022-09853-9