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.

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 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 consider the buffer content of a fluid queue or storage process. The buffer content varies in a way that depends on the state of an underlying three-state Markov process. In state 0 the buffer content increases at a rate a(x) that is a function of the current buffer level x; in states 1 and 2 it decreases linearly, with different speeds. We study the steady-state buffer content, by using level crossing theory and by exploiting relations between the fluid queue and queues with instantaneous input and/or output.

We consider a closed queueing network, consisting of two FCFS single server queues in series: a queue with general service times and a queue with exponential service times. A fixed number $$N$$ N of customers cycle through this network. We determine the joint sojourn time distribution of a tagged customer in, first, the general queue and, then, the exponential queue. Subsequently, we indicate how the approach toward this closed system also allows us to study the joint sojourn time distribution of a tagged customer in the equivalent open two-queue system, consisting of FCFS single server queues with general and exponential service times, respectively, in the case that the input process to the first queue is a Poisson process.

We consider a broad class of queueing models with random state-dependent vacation periods, which arise in the analysis of queue-based back-off algorithms in wireless random-access networks. In contrast to conventional models, the vacation periods may be initiated after each service completion, and can be randomly terminated with certain probabilities that depend on the queue length. We first present exact queue-length and delay results for some specific cases and we derive stochastic bounds for a much richer set of scenarios. Using these, together with stochastic relations between systems with different vacation disciplines, we examine the scaled queue length and delay in a heavy-traffic regime, and demonstrate a sharp trichotomy, depending on how the activation rate and vacation probability behave as function of the queue length. In particular, the effect of the vacation periods may either (i) completely vanish in heavy-traffic conditions, (ii) contribute an additional term to the queue lengths and delays of similar magnitude, or even (iii) give rise to an order-of-magnitude increase. The heavy-traffic trichotomy provides valuable insight into the impact of the back-off algorithms on the delay performance in wireless random-access networks. Keywords: Vacation queue; State-dependent vacations; Heavy-traffic analysis; CSMA protocol; Delay performance

We consider a repair facility consisting of one repairman and two arrival streams of failed items, from bases 1 and 2. The arrival processes are independent Poisson processes, and the repair times are independent and identically exponentially distributed. The item types are exchangeable, and a failed item from base 1 could just as well be returned to base 2, and vice versa. The rule according to which backorders are satisfied by repaired items is the longest queue rule: At the completion of a service (repair), the repaired item is delivered to the base that has the largest number of failed items. We point out a direct relation between our model and the classical longer queue model. We obtain simple expressions for several probabilities of interest, and show how all two-dimensional queue length probabilities may be obtained. Finally, we derive the sojourn time distributions.

We study a blood testing procedure for detecting viruses like HIV, HBV and HCV. In this procedure, blood samples go through two screening steps. The first test is ELISA (antibody Enzyme Linked Immuno-Sorbent Assay). The portions of blood which are found not contaminated in this first phase are tested in groups through PCR (Polymerase Chain Reaction). The ELISA test is less sensitive than the PCR test and the PCR tests are considerably more expensive. We model the two test phases of blood samples as services in two queues in series; service in the second queue is in batches, as PCR tests are done in groups. The fact that blood can only be used for transfusions until a certain expiration date leads, in the tandem queue, to the feature of customer impatience. Since the first queue basically is an infinite server queue, we mainly focus on the second queue, which in its most general form is an S-server M/G[k, K]/S + G queue, with batches of sizes which are bounded by k and K. Our objective is to maximize the expected profit of the system, which is composed of the amount earned for items which pass the test (and before their patience runs out), minus costs. This is done by an appropriate choice of the decision variables, namely, the batch sizes and the number of servers at the second service station. As will be seen, even the simplest version of the batch queue, the M/M[k, K]/1 + M queue, already gives rise to serious analytical complications for any batch size larger than 1. These complications are discussed in detail, and handled for K = 2. In view of the fact that we aim to solve realistic optimization problems for blood screening procedures, these analytical complications force us to take recourse to either a numerical approach or approximations. We present a numerical solution for the queue length distribution in the M/M[k, K]/S + M queue and then formulate and solve several optimization problems. The power-series algorithm, which is a numerical-analytic method, is also discussed.

In this paper we compare several service disciplines commonly used in polling systems. We present a sample path comparison which allows us to evaluate the efficiency of the different policies based on thetotal amount of work found in the systemat any time. The analysis is carried out for a large variety of polling schemes under fairly general conditions and can be used to construct a hierarchy of the different service schemes.