Search

We investigate the tail asymptotics of the response time distribution for the cancel-on-start (c.o.s.) and cancel-on-completion (c.o.c.) variants of redundancy-d scheduling and the fork–join model with heavy-tailed job sizes. We present bounds, which only differ in the pre-factor, for the tail probability of the response time in the case of the first-come first-served discipline. For the c.o.s. variant, we restrict ourselves to redundancy-d scheduling, which is a special case of the fork–join model. In particular, for regularly varying job sizes with tail index-$$\nu $$ ν the tail index of the response time for the c.o.s. variant of redundancy-d equals -$$\min \{d_{\mathrm {cap}}(\nu -1),\nu \}$$ min { d cap ( ν - 1 ) , ν } , where $$d_{\mathrm {cap}} = \min \{d,N-k\}$$ d cap = min { d , N - k } , N is the number of servers and k is the integer part of the load. This result indicates that for $$d_{\mathrm {cap}} < \frac{\nu }{\nu -1}$$ d cap < ν ν - 1 the waiting time component is dominant, whereas for $$d_{\mathrm {cap}} > \frac{\nu }{\nu -1}$$ d cap > ν ν - 1 the job size component is dominant. Thus, having $$d = \lceil \min \{\frac{\nu }{\nu -1},N-k\} \rceil $$ d = ⌈ min { ν ν - 1 , N - k } ⌉ replicas is sufficient to achieve the optimal asymptotic tail behavior of the response time. For the c.o.c. variant of the fork–join ($$n_{\mathrm {F}},n_{\mathrm {J}}$$ n F , n J ) model, the tail index of the response time, under some assumptions on the load, equals $$1-\nu $$ 1 - ν and $$1-(n_{\mathrm {F}}+1-n_{\mathrm {J}})\nu $$ 1 - ( n F + 1 - n J ) ν , for identical and i.i.d. replicas, respectively; here, the waiting time component is always dominant.

We consider a stochastic EOQ-type model, with demand operating in a two-state random environment. This environment alternates between exponentially distributed periods of high demand and generally distributed periods of low demand. The inventory level starts at some level q, and decreases according to different compound Poisson processes during the periods of high demand and of low demand. Refilling of the inventory level to level q is required when level 0 is hit or when an expiration date is reached, whichever comes first. If such an event occurs during a high demand period, an order is instantaneously placed; otherwise, ordering is postponed until the beginning of the next high demand period. We determine various performance measures of interest, like the distribution of the inventory level at time t and of the inventory demand up to time t, the distribution of the time until refilling is required, the expected time between two refillings, the expected amount of discarded material and the expected total amount of material held in between two refillings, and the expected values of various kinds of shortages. For a given cost/revenue structure, we can thus determine the long-run average profit.

The aim of this paper is to analyze a general class of storage processes, in which the rate at which the storage level increases or decreases is assumed to be an affine function of the current storage level, and, in addition, both upward and downward jumps are allowed. To do so, we first focus on a related insurance risk model, for which we determine the ruin probability at an exponentially distributed epoch jointly with the corresponding undershoot and overshoot, given that the capital level at time 0 is exponentially distributed as well. The obtained results for this insurance risk model can be translated in terms of two types of storage models, in one of those two cases by exploiting a duality relation. Many well-studied models are shown to be special cases of our insurance risk and storage models. We conclude by showing how the exponentiality assumptions can be greatly relaxed.

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)$$ f ( z ) = g ( z ) ∑ i = 1 M p i f ( α 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)$$ α i ( z ) are commutative contraction mappings. The results are applied to a wide range of queueing, autoregressive and branching processes.

This paper presents an analysis of the stochastic recursion $$W_{i+1} = [V_iW_i+Y_i]^+$$ W i + 1 = [ V i W i + Y i ] + that can be interpreted as an autoregressive process of order 1, reflected at 0. We start our exposition by a discussion of the model’s stability condition. Writing $$Y_i=B_i-A_i$$ Y i = B i - A i , for independent sequences of nonnegative i.i.d. random variables $$\{A_i\}_{i\in {\mathbb N}_0}$$ { A i } i ∈ N 0 and $$\{B_i\}_{i\in {\mathbb N}_0}$$ { B i } i ∈ N 0 , and assuming $$\{V_i\}_{i\in {\mathbb N}_0}$$ { V i } i ∈ N 0 is an i.i.d. sequence as well (independent of $$\{A_i\}_{i\in {\mathbb N}_0}$$ { A i } i ∈ N 0 and $$\{B_i\}_{i\in {\mathbb N}_0}$$ { B i } i ∈ N 0 ), we then consider three special cases (i) $$V_i$$ V i equals a positive value a with certain probability $$p\in (0,1)$$ p ∈ ( 0 , 1 ) and is negative otherwise, and both $$A_i$$ A i and $$B_i$$ B i have a rational LST, (ii) $$V_i$$ V i attains negative values only and $$B_i$$ B i has a rational LST, (iii) $$V_i$$ V i is uniformly distributed on [0, 1], and $$A_i$$ A i is exponentially distributed. In all three cases, we derive transient and stationary results, where the transient results are in terms of the transform at a geometrically distributed epoch.

Motivated by the trade-off issue between delay performance and energy consumption in modern computer and communication systems, we consider a single-server queue with phase-type service requirements and with the following two special features: Firstly, the service speed is a piecewise constant function of the workload. Secondly, the server switches off when the system becomes empty, only to be activated again when the workload reaches a certain threshold. For this system, we obtain the steady-state workload distribution and its moments of any order. We use this result to choose the activation threshold such that a certain cost function, involving processing costs, activation costs and mean workload, is minimized.

We consider a general class of closed product-form queueing networks, consisting of single-server queues and infinite-server queues. Even if a network is of product-form type, performance evaluation tends to be difficult due to the potentially large state space and the dependence between the individual queues. To remedy this, we analyze the model in a Halfin–Whitt inspired scaling regime, where we jointly blow up the traffic loads of all queues and the number of customers in the network. This leads to a closed-form limiting stationary distribution, which provides intuition on the impact of the dependence between the queues on the network’s behavior. We assess the practical applicability of our results through a series of numerical experiments, which illustrate the convergence and show how the scaling parameters can be chosen to obtain accurate approximations.

We provide a survey of so-called shot-noise queues: queueing models with the special feature that the server speed is proportional to the amount of work it faces. Several results are derived for the workload in an M/G/1 shot-noise queue and some of its variants. Furthermore, we give some attention to queues with general workload-dependent service speed. We also discuss linear stochastic fluid networks, and queues in which the input process is a shot-noise process.

We study a single server queue, where a certain type of dependence is introduced between the service times, or between the inter-arrival times, or both between the service times and the inter-arrival times. This dependence arises via mixing, i.e., a parameter pertaining to the distribution of the service times, or of the inter-arrival times, is itself considered to be a random variable. We give a duality result between such queueing models and the corresponding insurance risk models, for which the respective dependence structures have been studied before. For a number of examples we provide exact expressions for the waiting time distribution, and compare these to the ones for the standard M/M/1 queue. We also investigate the effect of dependence and derive first order asymptotics for some of the obtained waiting time tails. Finally, we discuss this dependence concept for the waiting time tail of the G/M/1 queue.

We explore the relationship between the ( S − 1 , S ) inventory model and three well-known queueing models: the Erlang loss system, the machine-repair model and a two-node Jackson network. Exploiting this relationship allows us to obtain key performance measures of the ( S − 1 , S ) model, like the so-called virtual outdating time, the number of items on the shelf in steady state, the long-run rate of unsatisfied demands and the distribution of the empty shelf period.

This paper aims at semi-parametrically estimating the input process to a Lévy-driven queue by sampling the workload process at Poisson times. We construct a method-of-moments based estimator for the Lévy process' characteristic exponent. This method exploits the known distribution of the workload sampled at an exponential time, thus taking into account the dependence between subsequent samples. Verifiable conditions for consistency and asymptotic normality are provided, along with explicit expressions for the asymptotic variance. The method requires an intermediate estimation step of estimating a constant (related to both the input distribution and the sampling rate); this constant also features in the asymptotic analysis. For subordinator Lévy input, a partial MLE is constructed for the intermediate step and we show that it satisfies the consistency and asymptotic normality conditions. For general spectrally-positive Lévy input a biased estimator is proposed that only uses workload observations above some threshold; the bias can be made arbitrarily small by appropriately choosing the threshold.

We present a model of parallel Levy-driven queues that mix their output into a final product; whatever cannot be mixed is sold on the open market for a lower price. The queues incur holding and capacity costs and can choose their processing rates. We solve the ensuing centralized (system optimal) and decentralized (individual station optimal) profit optimization problems. In equilibrium the queues process work faster than desirable from a system point of view. Several model extensions are also discussed.

Motivated by emerging Internet-of-Things (IoT) applications and smart building environments, we analyze the performance of large-scale symmetric polling systems where the number of queues grows large. We consider a scenario in which the total arrival rate is kept fixed and the individual switch-over time and service time distributions remain the same. This asymptotic regime leads to cycles of infinite length and queue lengths with non-trivial distributions. We show that for most traditional service policies the scaled cycle times converge to a deterministic value in the limit, which in turn implies that the queue lengths at the various nodes become asymptotically independent. Using these insights, we find that the behavior of individual queues simplifies to that of a discrete-time bulk service queue in the limit, so that the marginal queue length and waiting-time distributions become considerably easier to analyze. Additionally, we propose a new flexible k -limited service discipline aimed at striking a good balance between short mean queue lengths and predictable cycle times for deadline-critical applications.

Redundancy scheduling has emerged as a powerful strategy for improving response times in parallel-server systems. The key feature in redundancy scheduling is replication of a job upon arrival by dispatching replicas to different servers. Redundant copies are abandoned as soon as the first of these replicas finishes service. By creating multiple service opportunities, redundancy scheduling increases the chance of a fast response from a server that is quick to provide service and mitigates the risk of a long delay incurred when a single selected server turns out to be slow. The diversity enabled by redundant requests has been found to strongly improve the response time performance, especially in the case of highly variable service requirements. Analytical results for redundancy scheduling are unfortunately scarce however, and even the stability condition has largely remained elusive so far, except for exponentially distributed service requirements. In order to gain further insight in the role of the service requirement distribution, we explore the behavior of redundancy scheduling for scaled Bernoulli service requirements. We establish a sufficient stability condition for generally distributed service requirements, and we show that, for scaled Bernoulli service requirements, this condition is also asymptotically nearly necessary. This stability condition differs drastically from the exponential case, indicating that the stability condition depends on the service requirements in a sensitive and intricate manner.

We consider a linear stochastic fluid network under Markov modulation, with a focus on the probability that the joint storage level attains a value in a rare set at a given point in time. The main objective is to develop efficient importance sampling algorithms with provable performance guarantees. For linear stochastic fluid networks without modulation, we prove that the number of runs needed (so as to obtain an estimate with a given precision) increases polynomially (whereas the probability under consideration decays essentially exponentially); for networks operating in the slow modulation regime, our algorithm is asymptotically efficient. Our techniques are in the tradition of the rare-event simulation procedures that were developed for the sample-mean of i.i.d. one-dimensional light-tailed random variables, and intensively use the idea of exponential twisting. In passing, we also point out how to set up a recursion to evaluate the (transient and stationary) moments of the joint storage level in Markov-modulated linear stochastic fluid networks.

We investigate the stability condition for redundancy- d systems where each of the servers follows a processor-sharing (PS) discipline. We allow for generally distributed job sizes, with possible dependence among the d replica sizes being governed by an arbitrary joint distribution. We establish that for homogeneous servers the stability condition for the associated fluid-limit model is characterized by the expectation of the minimum of d replica sizes being less than the mean interarrival time per server. In the special case of identical replicas, the stability condition is insensitive to the job size distribution given its mean, and the stability threshold is inversely proportional to the number of replicas. In the special case of i.i.d. replicas, the stability threshold decreases (increases) in the number of replicas for job size distributions that are NBU (NWU). We also discuss the extension to heterogeneous servers. For heavy-tailed job sizes we characterize the tail behavior of the response time distribution. In particular, for regularly varying job sizes with tail index − ν it is shown that the tail index of the response time equals − ν and − d ν for identical and i.i.d. replicas, respectively.

In this paper, we study a single-server polling model with two queues. Customers arrive at the queues according to two independent Poisson processes. The server spends random amounts of time in each queue, regardless of the amounts of work present at the queues. The service speed is not constant; it is assumed that the server works at speed (Formula presented.) at queue i when its current workload equals xi, i = 1, 2. We first focus on the case that all visit times are constant. In the two-queue case, we then compute the Laplace–Stieltjes transform (LST) of the steady-state joint workload distribution. Using a different method in which we exploit the independence of the workloads at visit endings, we compute the joint LST of workloads in the case of an arbitrary number of queues with constant visit times. Next, we consider a two-queue polling model with constant visit times at the first queue and general visit times at the second, and we derive the marginal workload distribution at the first queue. We also investigate the case of a two-queue polling model with exponentially distributed visit times. We determine the steady-state marginal workload distributions, and we formulate a two-dimensional Volterra integral equation for the LST of the steady-state joint workload distribution. We finally show that this equation can be solved by a fixed-point iteration.

The workload of a generalized n-site asymmetric simple inclusion process (ASIP) is investigated. Three models are analyzed. The first model is a serial network for which the steady-state Laplace–Stieltjes transform (LST) of the total workload in the first k sites ( $$k\le n$$ ) just after gate openings and at arbitrary epochs is derived. In a special case, the former (just after gate openings) turns out to be an LST of the sum of k independent random variables. The second model is a 2-site ASIP with leakage from the first queue. Gate openings occur at exponentially distributed intervals, and the external input processes to the stations are two independent subordinator Levy processes. The steady-state joint workload distribution right after gate openings, right before gate openings and at arbitrary epochs is derived. The third model is a shot-noise counterpart of the second model where the workload at the first queue behaves like a shot-noise process. The steady-state total amount of work just before a gate opening turns out to be a sum of two independent random variables.

Nous considérons deux modèles de files d’attente à serveur infini avec un processus d’arrivée de Poisson. La particularité est que l’intensité de l’arrivée est rééchantillonnée à des intervalles de temps exponentiels (modèle 1) ou à l’époque du changement d’état du processus de Markov (modèle 2). Nos principaux résultats incluent les instants en régime transitoire et en régime permanent du nombre de clients.

We consider a multivariate L\'evy process where the first coordinate is a L\'evy process with no negative jumps which is not a subordinator and the others are nondecreasing. We determine the Laplace-Stieltjes transform of the steady-state buffer content vector of an associated system of parallel queues. The special structure of this transform allows us to rewrite it as a product of joint Laplace-Stieltjes transforms. We are thus able to interpret the buffer content vector as a sum of independent random vectors., Comment: 14 pages

We consider a sequence of age-replacement problems with a general lifetime distribution parametrized by an a-priori unknown parameter. There is a trade-off: Preventive replacements are censored but cheap, whereas corrective replacements are uncensored but costly observations of the lifetime distribution. We first analyze the optimal policy for a finite sequence and establish some properties. We then propose a myopic Bayesian policy that almost surely learns the unknown parameter and converges to the optimal policy with full knowledge of the parameter.

We consider the tail behavior of the response time distribution in an M/G/1 queue with heavy-tailed job sizes, specifically those with intermediately regularly varying tails. In this setting, the response time tail of many individual policies has been characterized, and it is known that policies such as Shortest Remaining Processing Time (SRPT) and Foreground-Background (FB) have response time tails of the same order as the job size tail, and thus such policies are tail-optimal. Our goal in this work is to move beyond individual policies and characterize the set of policies that are tail-optimal. Toward that end, we use the recently introduced SOAP framework to derive sufficient conditions on the form of prioritization used by a scheduling policy that ensure the policy is tail-optimal. These conditions are general and lead to new results for important policies that have previously resisted analysis, including the Gittins policy, which minimizes mean response time among policies that do not have access to job size information. As a by-product of our analysis, we derive a general upper bound for fractional moments of M/G/1 busy periods, which is of independent interest.

In this paper, a few models for optical router nodes are considered. The stations (ports) of such a node try to transmit packets. Successful transmission of a packet of type j at station i gives a profit γ i j , but there is also a positive probability that such a packet is dropped, causing a penalty θ i j . Consider one fixed cycle (frame), in which each station is assigned some visit time. The goal is to choose the visit times in such a way that the revenue is maximized. In our first model there is only one wavelength, and we take the finiteness of buffers into account. The revenue maximization problem is shown to be separable concave, thus allowing application of a very efficient algorithm. In our second model we allow multiple wavelengths. We aim to maximize the revenue by optimally assigning stations to wavelengths and, for each wavelength, by optimally choosing the visit times of the allocated stations within the cycle. This gives rise to a mixed integer linear programming problem (MILP) which is NP-hard. To solve this problem fast and efficiently we provide a three-step heuristic. It consists of (i) solving a separable concave optimization problem, then (ii) allocating the stations to wavelengths using a simple bin packing algorithm, and finally (iii) solving another set of separable concave optimization problems. We present numerical results to investigate the effectiveness of the heuristic and the advantages of having multiple wavelengths. Finally, some model variants are briefly discussed.

We introduce two general classes of reflected autoregressive processes, INGAR+ and GAR+. Here, INGAR+ can be seen as the counterpart of INAR(1) with general thinning and reflection being imposed to keep the process non-negative; GAR+ relates to AR(1) in an analogous manner. The two processes INGAR+ and GAR+ are shown to be connected via a duality relation. We proceed by presenting a detailed analysis of the time-dependent and stationary behavior of the INGAR+ process, and then exploit the duality relation to obtain the time-dependent and stationary behavior of the GAR+ process.

We consider a system with several job types and two parallel server pools. Within the pools the servers are homogeneous, but across pools possibly not in the sense that the service speed of a job may depend on its type as well as the server pool. Immediately upon arrival, jobs are assigned to a server pool, possibly based on (partial) knowledge of their type. In case such knowledge is not available upon arrival, it can however be obtained while the job is in service; as the service progresses, the likelihood that the service speed of this job type is low increases, creating an incentive to execute the job on different, possibly faster, server(s). Two policies are considered: reroute the job to the other server pool, or replicate it there.We determine the effective load per server under both the rerouting and replication policy for completely unknown as well as partly known job types. We also examine the impact of these policies on the stability bound, which is defined as the maximum arrival rate of jobs for which the effective load per server is smaller than one. We demonstrate that the uncertainty in job types may significantly reduce the stability bound, and that for (highly) unbalanced service speeds full replication achieves the largest stability bound. Finally, we discuss how the use of threshold-based policies can help improve the expected latency for completely or partly unknown job types.

We consider a dual risk model with constant expense rate and i.i.d. exponentially distributed gains $C_i$ ( $i=1,2,\dots$ ) that arrive according to a renewal process with general interarrival times. We add to this classical dual risk model the proportional gain feature; that is, if the surplus process just before the ith arrival is at level u, then for $a>0$ the capital jumps up to the level $(1+a)u+C_i$ . The ruin probability and the distribution of the time to ruin are determined. We furthermore identify the value of discounted cumulative dividend payments, for the case of a Poisson arrival process of proportional gains. In the dividend calculations, we also consider a random perturbation of our basic risk process modeled by an independent Brownian motion with drift.

We consider an extension of the classic machine-repair model, where we explicitly model the fact that machines, apart from requiring service from a single repairer, also supply service themselves to products. Due to this dual role of the machines, the system exhibits an intricate relation between the processing rate of products and the performance of the repairer. To characterize this relation, we analyze this model under a Halfin-Whitt inspired scaling regime, where we amplify the arrival rate of products, the repair speed of the repairer and the number of machines appropriately. The resulting limiting stationary distribution is elegant, allows for a closed-form expression and provides intuition on the system's behavior resulting from the machines' dual role. With numerical results we illustrate the convergence, and assess under which conditions the limiting distributions lead to accurate approximations. Next to this valuable insight, the analysis in this paper can be viewed as a first step towards a unifying scaling analysis for general closed queueing networks.

We consider the dual risk model with special dividend or tax payments: If an arriving gain finds the surplus above a barrier b or if it would bring the surplus above that level, a certain part of the gain is paid as dividends or taxes. We obtain expressions for the joint Laplace–Stieltjes transform of the time to ruin and the amount of dividends paid until ruin, and for the expected discounted dividend paid until ruin. We consider the case where the dividend paid from each gain is a general function of the gain. More explicit results are obtained when the dividend is a given percentage of the gain amount.

We consider job dispatching in systems with N parallel servers. In redundancy- d policies, replicas of an arriving job are assigned to d ≤ N servers selected uniformly at random (without replacement) with the objective to reduce the delay. We introduce a quite general workload model, in which job sizes have some probability distribution while the speeds (slowdown factors) of the various servers for a given job are allowed to be inter-dependent and non-identically distributed. This allows not only for inherent speed differences among different servers, but also for affinity relations. We further propose two novel redundancy policies, so-called delta-probe- d policies, where d probes of a fixed, small, size Δ are created for each incoming job, and assigned to d servers selected uniformly at random. As soon as the first of these d probe tasks finishes, the actual job is assigned for execution – with the same speed – to the corresponding server and the other probe tasks are abandoned. We also consider a delta-probe- d policy in which the probes receive preemptive-resume priority over regular jobs. The aim of these policies is to retain the benefits of redundancy- d policies while accounting for systematic speed differences and mitigating the risks of running replicas of the full job simultaneously for long periods of time. Analytical and numerical results are presented to evaluate the effect of both probing policies on the job latency, and to illustrate the potential performance improvements.

This is a survey on polling systems, focussing on the basic single-server multi-queue polling system in which the server visits the queues in cyclic order. The main goals of the paper are: (i) to discuss a number of the key methodologies in analyzing polling models; (ii) to give an overview of recent polling developments; and (iii) to present a number of challenging open problems.

This paper is devoted to the performance analysis and optimization of blood testing procedures. We present a queueing model of two queues in series, representing the two stages of a blood-testing procedure. Service (testing) in stage 1 is performed in batches, whereas it is done individually in stage 2. Since particular elements of blood can only be stored and used within a finite time window, the sojourn time of blood units in the system of two queues in series is an important performance measure, which we study in detail. We also introduce a profit objective function, taking into account blood acquisition and screening costs as well as profits for blood units, which were found uncontaminated and were tested fast enough. We optimize that profit objective function w.r.t. the batch size and the length of the time window.

We consider the surplus of an insurance company that employs reinsurance. The reinsurer covers part of the claims, but in return it receives a certain part of the income from premiums of the insurance company. In addition, the reinsurer receives some of the dividends that are withdrawn when a certain surplus level b is reached. A special feature of our model is that both the fraction of the premium that goes to the reinsurer and the fraction of the claims covered by the reinsurer are state-dependent. We focus on five performance measures, viz., time to ruin, deficit at ruin, the dividend withdrawn until ruin, and the amount of money transferred to the reinsurer, respectively covered by the reinsurer.

We study infinite-server queues in which the arrival process is a Cox process (or doubly stochastic Poisson process), of which the arrival rate is given by a shot-noise process. A shot-noise rate emerges naturally in cases where the arrival rate tends to exhibit sudden increases (or shots) at random epochs, after which the rate is inclined to revert to lower values. Exponential decay of the shot noise is assumed, so that the queueing systems are amenable to analysis. In particular, we perform transient analysis on the number of jobs in the queue jointly with the value of the driving shot-noise process. Additionally, we derive heavy-traffic asymptotics for the number of jobs in the system by using a linear scaling of the shot intensity. First we focus on a one-dimensional setting in which there is a single infinite-server queue, which we then extend to a network setting.

We consider a Cramér–Lundberg insurance risk process with the added feature of reinsurance. If an arriving claim finds the reserve below a certain threshold γ, or if it would bring the reserve below that level, then a reinsurer pays part of the claim. Using fluctuation theory and the theory of scale functions of spectrally negative Lévy processes, we derive expressions for the Laplace transform of the time to ruin and of the joint distribution of the deficit at ruin and the surplus before ruin. We specify these results in much more detail for the threshold set-up in the case of proportional reinsurance.

In this paper, we study an M/M/1 queue, where the server continues to work during idle periods and builds up inventory. This inventory is used for new arriving service requirements, but it is completely emptied at random epochs of a non-homogeneous Poisson process, whose rate depends on the current level of the acquired inventory. For several shapes of depletion rates, we derive differential equations for the stationary density of the workload and the inventory level and solve them explicitly. Finally, numerical illustrations are given for some particular examples, and the effects of this depletion mechanism are discussed.

This paper addresses the analysis of the queue-length process of single-server queues under overdispersion, i.e., queues fed by an arrival process for which the variance of the number of arrivals in a given time window exceeds the corresponding mean. Several variants are considered, using concepts as mixing and Markov modulation, resulting in different models with either endogenously triggered or exogenously triggered random environments. Only in special cases explicit expressions can be obtained, e.g. when the random arrival and/or service rate can attain just finitely many values. While for more general model variants exact analysis is challenging, one ${\it can}$ derive limit theorems in the heavy-traffic regime. In some of our derivations we rely on evaluating the relevant Laplace transform in the heavy-traffic scaling using Taylor expansions, whereas other results are obtained by applying the continuous mapping theorem.

We investigate the stability condition for redundancy-d systems where each of the servers follows a processor-sharing (PS) discipline. We allow for generally distributed job sizes, with possible dependence among the d replica sizes being governed by an arbitrary joint distribution. We establish that the stability condition is characterized by the expectation of the minimum of d replica sizes being less than the mean interarrival time per server. In the special case of identical replicas, the stability condition is insensitive to the job size distribution given its mean, and the stability condition is inversely proportional to the number of replicas. In the special case of i.i.d. replicas, the stability threshold decreases (increases) in the number of replicas for job size distributions that are NBU (NWU). We also discuss extensions to scenarios with heterogeneous servers., To appear in proceedings of ValueTools 2020

In early queueing models the characteristics of the arrival and service time distributions are constant over time. This chapter shows how a Markov Modulated Queueing System can be used to model queueing systems with the latter dependence structure. It describes how the Batch Markovian Arrival Process (BMAP) can be used to model queueing systems with correlation between the interarrival and service time of a customer. The chapter illustrates the modelling technique with a number of examples. It examines the potential of the modelling technique to obtain performance measures and insights for queueing systems with dependence between interarrival and service times. The chapter considers queueing models in which various dependence structures occur simultaneously. It focuses on modelling correlation between interarrival and service times of customers with the use of the BMAP. The chapter utilizes the BMAP for modelling a number of variants of the collector model.

We consider a network of infinite-server queues where the input process is a Cox process of the following form: The arrival rate is a vector-valued linear transform of a multivariate generalized (i.e., being driven by a subordinator rather than a compound Poisson process) shot-noise process. We first derive some distributional properties of the multivariate generalized shot-noise process. Then these are exploited to obtain the joint transform of the numbers of customers, at various time epochs, in a single infinite-server queue fed by the above-mentioned Cox process. We also obtain transforms pertaining to the joint stationary arrival rate and queue length processes (thus facilitating the analysis of the corresponding departure process), as well as their means and covariance structure. Finally, we extend to the setting of a network of infinite-server queues.

We study an M/G/1-type queueing model with the following additional feature. The server works continuously, at fixed speed, even if there are no service requirements. In the latter case, it is building up inventory, which can be interpreted as negative workload. At random times, with an intensity ω(x) when the inventory is at level x>0, the present inventory is removed, instantaneously reducing the inventory to 0. We study the steady-state distribution of the (positive and negative) workload levels for the cases ω(x) is constant and ω(x) = ax. The key tool is the Wiener–Hopf factorization technique. When ω(x) is constant, no specific assumptions will be made on the service requirement distribution. However, in the linear case, we need some algebraic hypotheses concerning the Laplace–Stieltjes transform of the service requirement distribution. Throughout the paper, we also study a closely related model arising from insurance risk theory.

We consider an asymmetric inclusion process, which can also be viewed as a model of n queues in series. Each queue has a gate behind it, which can be seen as a server. When a gate opens, all customers in the corresponding queue instantaneously move to the next queue and form a cluster with the customers there. When the nth gate opens, all customers in the nth site leave the system. For the case where the gate openings are determined by a Markov renewal process, and for a quite general arrival process of customers at the various queues during intervals between successive gate openings, we obtain the following results: (i) steady-state distribution of the total number of customers in the first k queues, $$k=1,\dots ,n$$k=1,ź,n; (ii) steady-state joint queue length distributions for the two-queue case. In addition to the case that the numbers of arrivals in successive gate opening intervals are independent, we also obtain explicit results for a two-queue model with renewal arrivals.

We investigate the transient and stationary queue-length distributions of a class of service systems with correlated service times. The classical MX/G/1 queue with semi-Markov service times is the most prominent example in this class and serves as a vehicle to display our results. The sequence of service times is governed by a modulating process J(t). The state of J(⋅) at a service initiation time determines the joint distribution of the subsequent service duration and the state of J(⋅) at the next service initiation. Several earlier works have imposed technical conditions on the zeros of a matrix determinant arising in the analysis, that are required in the computation of the stationary queue length probabilities. The imposed conditions in several of these articles, are difficult or impossible to verify. Without such assumptions, we determine both the transient and the steady-state joint distribution of the number of customers immediately after a departure and the state of the process J(t) at the start of the next service. We numerically investigate how the mean queue length is affected by variability in the number of customers that arrive during a single service time. Our main observations here are that increasing variability may reduce the mean queue length, and that the Markovian dependence of service times can lead to large queue lengths, even if the system is not in heavy traffic.

This paper considers an M/G/1 queue with the following vacation discipline. The server takes a vacation as soon as it has served a certain amount of work since the end of the previous vacation. If the system becomes empty before the server has completed this amount of work, then it stays idle until the next customer arrival and then becomes active again. Such a vacation discipline arises, for example, in the maintenance of production systems, where machines or equipment mainly degrade while being operational. We derive an explicit expression for the distribution of the time it takes until the prespecified amount of work has been served. For the case the total amount of work till vacation is exponentially distributed, we derive the transforms of the steady-state workload at various epochs, busy period, waiting time, sojourn time, and queue length distributions.