A double-loop network G(h1, h2) has n nodes represented by the n residues modulo n and 2n links given by i ↦i + h1, i ↦ i + h2, i = 0,1,…,n – 1.We consider the reliability model where each link fails independently with probability p, the nodes always work, and the network fails if it is not strongly connected. There exists no known polynomial time algorithm to compute the reliabilities of general double-loop networks. When p is small, the reliability is dominated by the link connectivity. As all strongly connected double.loop networks have link connectivity exactly 2, a finer measure of reliability is needed. In this paper we give such a measure and show how to use it to obtain the most reliable double-loop networks.

Suppose that you find yourself trapped in a maze about which you know nothing except that it has an exit point. We present an optimal strategy that will lead you to the exit point in minimum expected time. This strategy ensures that the expected total length of the arcs you traverse will not exceed the sum of the lengths of the arcs in the maze.

Motivated by packetwise transmission of data in telecommunications, we introduce a fluid model with a continuous burst arrival process ψ = {(tn, Sn):n ≥ 0}. Each epoch, tn, begins a burst of length Sn that is, a continuous flow of fluid (work, information, etc.) at rate 1 to a system. The system processes fluid at rate 1. The model more generally can be used to approximate a storage system where fluid arrives over time due to many different (unrelated) sources. We analyze the model using sample path techniques (ψ is assumed deterministic, having arisen as a sample path from some underlying probability space) and by doing so obtain a variety of expressions for such quantities as average work inc system and average work in service as well as the empirical distribution for work in service. The expressions are given in terms of familiar quantities (such as customer delay) from the corresponding classic single- and infinite-channel queues that we construct from the same arrival sample path. In particular, we obtain an interesting decomposition of work in terms of the work in these two wellknown queueing models. In our final remarks, we also point out the optimality features of this model when compared to other models having different rules regulating the flow of burst work. In addition, we also give some stochastic ordering results when comparing two burst systems of the M/GI/1 or GI/M/1 type.

We consider a fluid system in which during off-times the buffer content increases as a piecewise linear process according to some general semi-Markov process, and during on-times, it decreases with a state-dependent rate (or remains at zero). The lengths of off-times are exponentially distributed. We show that such a system has a stationary distribution which satisfies a decomposition property where one component in the decomposition is associated with some dam process and the other with a clearing process. For the cases of constant and linear decrease rates, the steady-state Laplace–Stieltjes transform and moments of the buffer content are computed explicitly.

We are interested in E [N], the mean time until the most recent k values of a sequence of independent and identically distributed random variables exceeds a specified constant. Using recent results, we present a simulation procedure for determining E [N]. These results are also used to obtain upper and lower bounds for E [N]. These bounds, however, are in terms of a quantity ω that is not easily calculated. A recursive procedure for evaluating ω when the data distribution is Bernoulli is given. Efficient simulation procedures for estimating ω in the cases of normal and exponential population distributions are also presented, as is a Markov chain monte carlo procedure when the distribution is general.

For non-negative random variables with finite means we introduce an analogous of the equilibrium residual-lifetime distribution based on the quantile function. This allows us to construct new distributions with support (0, 1), and to obtain a new quantile-based version of the probabilistic generalization of Taylor's theorem. Similarly, for pairs of stochastically ordered random variables we come to a new quantile-based form of the probabilistic mean value theorem. The latter involves a distribution that generalizes the Lorenz curve. We investigate the special case of proportional quantile functions and apply the given results to various models based on classes of distributions and measures of risk theory. Motivated by some stochastic comparisons, we also introduce the “expected reversed proportional shortfall order”, and a new characterization of random lifetimes involving the reversed hazard rate function.

We establish functional large deviation principles (FLDPs) for waiting and departure processes in single-server queues with unlimited waiting space and the first-in first-out service discipline. We apply the extended contraction principle to show that these processes obey FLDPs in the function space D with one of the nonuniform Skorohod topologies whenever the arrival and service processes obey FLDPs and the rate function is finite for appropriate discontinuous functions. We apply our previous FLDPs for inverse processes to obtain an FLDP for the waiting times in a queue with a superposition arrival process. We obtain FLDPs for queues within acyclic networks by showing that FLDPs are inherited by processes arising from the network operations of departure, superposition, and random splitting. For this purpose, we also obtain FLDPs for split point processes. For the special cases of deterministic arrival processes and deterministic service processes, we obtain convenient explicit expressions for the rate function of the departure process, but not more generally. In general, the rate function for the departure process evidently must be calculated numerically. We also obtain an FLDP for the departure process of completed work, which has important application to the concept of effective bandwidths for admission control and capacity planning in packet communication networks.

We consider a memoryless Erlang loss system with servers = {1, …, J}, and with customer types = {1, …, I}. Servers are multitype, so that server j can serve a subset of customer types C(j). We show that the probabilities of assigning arriving customers to idle servers can be chosen in such a way that the Markov process describing the system is reversible, with a simple product form stationary distribution. Furthermore, the system is insensitive; these properties are preserved for general service time distributions.

When confronted by a sequence of independent, identical, favorable-though- risky investments, a risk-averse agent will in fact elect to invest as part of a large syndicate even if he or she would not undertake even one of the investments by himself or herself. This willingness to invest emanates from the risk reduction associated with the risk pooling effected by the syndicate. Our first two theorems describe the syndicate size needed to induce the agent's participation.

The consequence of adding risks is considered next. We demonstrate that the agent will undertake a large number of these independent investments by himself or herself even if each investment taken by itself constitutes a poor risk. The conditions needed to ensure this somewhat surprising result are (a) moment bounds on the investments, and (b) either a polynomial or an exponential bound on the lower tail of the agent's utility function. Finally, we draw the connection between this result, proper risk aversion, and monotonicity of the agent's absolute aversion to risk.

This paper studies consecutive-2 systems on trees. We show that given a set of probability values, the optimal assignment for binary trees depends on the particular values, whereas for k−regular trees, which are closely related to binary trees, it depends only on their relative ordering. In our proof, we introduce the notion of first-term-invariance, which might have further applications. We also show that the problem of computing the failure probability of consecutive-2 system is #P-complete in general, though the problem on trees is shown to be strongly polynomial.

This paper is devoted to the analysis of a fluid queue with a buffer content that varies linearly during periods that are governed by a three-state semi-Markov process. Two cases are being distinguished: (i) two upward slopes and one downward slope, and (ii) one upward slope and two downward slopes. In both cases, at least one of the period distributions is allowed to be completely general. We obtain exact results for the buffer content distribution, the busy period distribution, and the distribution of the maximal buffer content during a busy period. The results are obtained by establishing relations between the fluid queues and ordinary queues with instantaneous input and by using level crossing theory.

For a system that is subject to shocks, it is assumed that the distribution of the magnitudes of shocks changes after the first shock of size at least d1, and the system fails upon the occurrence of the first shock above a critical level d2 (> d1). In this paper, the distribution of the lifetime of such a system is studied when the times between successive shocks follow matrix-exponential distribution. In particular, it is shown that the system's lifetime has matrix-exponential distribution when the intershock times follow Erlang distribution. The model is extended to the case when the system fails upon the occurrence of l consecutive critical shocks.

This paper deals with the following discrete-time optimal stopping problem. For fixed search costs, a random offer, w ~ F(w), will be found for each time. This offer is either accepted, rejected, or “reserved” for recall later. The reserving cost for any offer depends on its value, regardless of how long the offer is reserved. The objective is to maximize the expected discounted net profit, provided that an offer must be accepted. The major finding is that no previously reserved offer should be accepted prior to the deadline of the search process.

We consider a Jackson network with two nodes, with no exogenous input, but instead an infinite supply of work at each of the nodes: Whenever a node is empty, it processes a job from this infinite supply. We obtain an explicit expression for the steady state distribution of this system, as an infinite sum of product forms.

Consider the problem in which impatient customers have to be routed to or scheduled from a set of parallel homogeneous service stations with finite buffer capacities. When the service times and the deadlines of customers are exponentially distributed, we identify the control policies that stochastically minimize the total number of losses by any time t. We study systems with deadlines to the beginning or to the end of service. The results regarding the individual types of losses, i.e., losses due to deadline misses and losses due to buffer overflow, vary across different systems. In all cases we state explicitly the properties and the limitations of the optimal control policies.

We study the scheduling of jobs in a system of two interconnected service stations, called Q1 and Q2, on m(m ≥ 2) identical machines available in parallel, so that every machine can process any jobs in Q1 or Q2. Preemption is allowed. Under certain conditions on the arrival, service, and interconnection processes, we determine a scheduling policy that minimizes the expected makespan.

The concept of stochastic precedence between two real-valued random variables has often emerged in different applied frameworks. In this paper, we analyze several aspects of a more general, and completely natural, concept of stochastic precedence that also had appeared in the literature. In particular, we study the relations with the notions of stochastic ordering. Such a study leads us to introducing some special classes of bivariate copulas. Motivations for our study can arise from different fields. In particular, we consider the frame of Target-Based Approach in decisions under risk. This approach has been mainly developed under the assumption of stochastic independence between “Prospects” and “Targets”. Our analysis concerns the case of stochastic dependence.

We analyze optimal replacement and repair problems of semi-Markov missions that are composed of phases with random sequence and durations. The mission process is the minimal semi-Markov process associated with a Markov renewal process. The system is a complex one consisting of non-identical components whose failure properties depend on the mission process. We prove some monotonicity properties for the optimal replacement policy and analyze the optimal repair problem under different cost structures.

Two types of tasks are to be scheduled on a single processor under incomplete information about the task lengths. We derive the structure of optimal scheduling rules w.r.t. flowtime, as well as asymptotic approximations for a large number of tasks, when the length distributions belong to a one-parameter exponential family.

We consider two-stage tandem queuing systems with dedicated servers in each station and flexible servers that can serve in both stations. We assume exponential service times, linear holding costs, and operating costs incurred by the servers at rates proportional to their speeds. Under conditions that ensure the optimality of nonidling policies, we show that the optimal allocation of flexible servers is determined by a transition-monotone policy. Moreover, we present conditions under which the optimal policy can be explicitly determined.