Search

A generalized n-site Asymmetric Simple Inclusion Process (ASIP) network is studied, where gate-opening instants are determined by a renewal process and arrivals occur to all sites. Various types of batch particle movements between sites are analyzed: (i) unidirectional probabilistic forward movements; (ii) probabilistic forward movements combined with feedback to the first site; and (iii) general probabilistic multidirectional movements. In contrast to the tedious successive substitution method used in previous ASIP studies, an efficient matrix approach is applied to derive the multidimensional probability generating function (PGF) of site occupancies right after gate opening instants. The complexity of the ASIP processes allows us to obtain explicit PGF results for small-size networks only, while for larger networks, a formula to calculate the mean site occupancies is derived for all types of movements. In movement case (i) the means are directly and explicitly calculated. For movement case (ii), where the network is homogeneous with equal probabilities of forward movements from site i to downstream sites j ≥ i , we show that the ratio between the mean occupancies of consecutive sites approaches a constant when the network becomes large, and calculate this ratio. Finally, we investigate an n-site network where at gate opening instants all gates open simultaneously, and particles move in all directions. Numerical examples are presented. [ABSTRACT FROM AUTHOR]

The Asymmetric Simple Inclusion Process (ASIP) is an n-site tandem stochastic network with a Poisson arrival influx into the first site. Each site has an unlimited buffer with a gate in front of it. Each gate opens, independently of all other gates, following a site-dependent Exponential inter-opening time. When a site's gate opens, all particles occupying the site move simultaneously to the next site. In this paper, a Generalized ASIP network is analyzed where the influx is to all sites, while gate openings are determined by a general renewal process. A compact matrix approach—instead of the conventional (and tedious) successive substitution method—is constructed for the derivation of the multidimensional probability-generating function (PGF) of the site occupancies. It is shown that the set of ( 2 n n ) linear equations required to obtain the PGF of an n-site network can be first cut by half into a set of 2 n − 1 n equations, and then further reduced to a set of 2 n − n + 1 equations. The latter set can be additionally split into several smaller triangular subsets. It is also shown how the PGF of an n + 1 -site network can be derived from the corresponding PGF of an n-site system. Explicit results for networks with n = 3 and n = 4 sites are obtained. The matrix approach is utilized to explicitly calculate the probability that site k   k = 1 , 2 , ... , n is occupied. We show that, in the case where arrivals occur to the first site only, these probabilities are functions of both the site's index and the arrival flux and not solely of the site's index. Consequently, refined formulas for the latter probabilities and for the mean conditional site occupancies are derived. We further show that in the case where the arrival process to the first site is Poisson with rate λ , the following interesting property holds: P s i t e   k   i s   o c c u p i e d   |   λ = 1 = P s i t e   k + 1   i s   o c c u p i e d   |   λ → ∞ . The case where the inter-gate opening intervals are Gamma distributed is investigated and explicit formulas are obtained. Mean site occupancy and mean total load of the first k sites are calculated. Numerical results are presented. [ABSTRACT FROM AUTHOR]

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$$ ; (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. [ABSTRACT FROM AUTHOR]

The so-called 'Israeli queue' (Boxma et al. in Stoch Model 24(4):604-625, ; Perel and Yechiali in Probab Eng Inf Sci, ; Perel and Yechiali in Stoch Model 29(3):353-379, ) is a multi-queue polling-type system with a single server. Service is given in batches, where the batch sizes are unlimited and the service time of a batch does not depend on its size. After completing service, the next queue to be visited by the server is the one with the most senior customer. In this paper, we study the Israeli queue with retrials, where the system is comprised of a 'main' queue and an orbit queue. The main queue consists of at most $$M$$ groups, where a new arrival enters the main queue either by joining one of the existing groups, or by creating a new group. If an arrival cannot join one of the groups in the main queue, he goes to a retrial (orbit) queue. The orbit queue dispatches orbiting customers back to the main queue at a constant rate. We analyze the system via both probability generating functions and matrix geometric methods, and calculate analytically various performance measures and present numerical results. [ABSTRACT FROM AUTHOR]

We study a M/M/1 queue in a multi-phase random environment, where the system occasionally suffers a disastrous failure, causing all present jobs to be lost. The system then moves to a repair phase. As soon as the system is repaired, it moves to phase i with probability qi ≥ 0. We use two methods of analysis to study the probabilistic behavior of the system in steady state: (i) via probability generating functions, and (ii) via matrix geometric approach. Due to the special structure of the Markov process describing the disaster model, both methods lead to explicit results, which are related to each other. We derive various performance measures such as mean queue sizes, mean waiting times, and fraction of lost customers. Two special cases are further discussed. [ABSTRACT FROM AUTHOR]

Two independent Poisson streams of jobs flow into a single-server service system having a limited common buffer that can hold at most one job. If a type- $$i$$ job ( $$i=1,2$$ ) finds the server busy, it is blocked and routed to a separate type- $$i$$ retrial (orbit) queue that attempts to re-dispatch its jobs at its specific Poisson rate. This creates a system with three dependent queues. Such a queueing system serves as a model for two competing job streams in a carrier sensing multiple access system. We study the queueing system using multi-dimensional probability generating functions, and derive its necessary and sufficient stability conditions while solving a Riemann-Hilbert boundary value problem. Various performance measures are calculated and numerical results are presented. In particular, numerical results demonstrate that the proposed multiple access system with two types of jobs and constant retrial rates provides incentives for the users to respect their contracts. [ABSTRACT FROM AUTHOR]

We consider systems comprised of two interlacing M/M/ • /• type queues, where customers of each queue are the servers of the other queue. Such systems can be found for example in file sharing programs, SETI@home project, and other applications [Arazi, A, E Ben-Jacob and U Yechiali (2005). Controlling an oscillating Jackson-type network having state-dependant service rates. Mathematical Methods of Operations Research, 62, 453-466]. Denoting by Li the number of customers in queue i(Qi), i = 1, 2, we assume that Q1 is a multi-server finite-buffer system with an overall capacity of size N, where the customers there are served by the L2 customers present in Q2. Regarding Q2, we study two different scenarios described as follows: (i) All customers present in Q1 join hands together to form a single server for the customers in Q2, with service time exponentially distributed with an overall intensity μ2L1. That is, the service rate of the customers in Q2 changes dynamically, following the state of Q1. (ii) Each of the customers present in Q1 individually acts as a server for the customers in Q2, with service time exponentially distributed with mean 1/μ2. In other words, the number of servers at Q2 changes according to the queue size fluctuations of Q1. We present a probabilistic analysis of such systems, applying both Matrix Geometric method and Probability Generating Functions (PGFs) approach, and derive the stability condition for each model, along with its two-dimensional stationary distribution function. We reveal a relationship between the roots of a given matrix, related to the PGFs, and the stability condition of the systems. In addition, we calculate the means of Li, i = 1, 2, along with their correlation coefficient, and obtain the probability of blocking at Q1. Finally, we present numerical examples and compare between the two models. [ABSTRACT FROM AUTHOR]

We consider a 2-class, single-server, preemptive priority queueing model in which the high-priority customers form a classicalM/M/1 queue, while the low-priority customers form the so-calledIsraeli Queuewith at mostNdifferent groups and unlimited-size batch service. We provide an extensive probabilistic analysis and calculate key performance measures. Special cases are analyzed and numerical examples are presented and discussed. [ABSTRACT FROM AUTHOR]

We study N-queues single-server fluid polling systems, where a fluid is continuously flowing into the queues at queue-dependent rates. When visiting and serving a queue, the server reduces the amount of fluid in the queue at a queue-dependent rate. Switching from queue i to queue j requires two random-duration steps: (i) departing queue i, and (ii) reaching queue j. The length of time the server resides in a queue depends on the service regime. We consider three main regimes: Exhaustive, Gated, and Globally-Gated. Two polling procedures are analyzed: (i) cyclic and (ii) probabilistic. Under steady-state, we derive the Laplace–Stieltjes transform (LST), mean, and second moment of the amount of flow at each queue at polling instants, as well as at an arbitrary moment. We further calculate the LST and mean of the “waiting time” of a drop at each queue and derive expressions for the mean total load in the system for the various service regimes. Finally, we explore optimal switching procedures. [ABSTRACT FROM AUTHOR]

Performance measures are studied for a generalized n-site asymmetric simple inclusion process (G-ASIP), where a general process controls intervals between gate-opening instants. General formulae are obtained for the Laplace–Stieltjes transform, as well as the means, of the (i) traversal time, (ii) busy period, and (iii) draining time. The PGF and mean of (iv) the system's overall load are calculated, as well as the probability of an empty system, along with (v) the probability that the first occupied site is site k (k = 1, 2, ..., n). Explicit results are derived for the wide family of gamma-distributed gate inter-opening intervals (which span the range between the exponential and the deterministic probability distributions), as well as for the uniform distribution. It is further shown that a homogeneous system, where at gate-opening instants gate j opens with probability p j = 1 n , is optimal with regard to (i) minimizing mean traversal time, (ii) minimizing the system's load, (iii) maximizing the probability of an empty system, (iv) minimizing the mean draining time, and (v) minimizing the load variance. Furthermore, results for these performance measures are derived for a homogeneous G-ASIP in the asymptotic cases of (i) heavy traffic, (ii) large systems, and (iii) balanced systems. [ABSTRACT FROM AUTHOR]

We consider a system comprised of two connected M/ M/•/• type queues, where customers of one queue act as servers for the other queue. One queue, Q 1, operates as a limited-buffer M/ M/1/ N−1 system. The other queue, Q 2, has an unlimited-buffer and receives service from the customers of Q 1. Such analytic models may represent applications like SETI@home, where idle computers of users are used to process data collected by space radio telescopes. Let L 1 denote the number of customers in Q 1. Then, two models are studied, distinguished by their service discipline in Q 2: In Model 1, Q 2 operates as an unlimited-buffer, single-server M/ M/1/∞ queue with Poisson arrival rate λ 2 and dynamically changing service rate μ 2 L 1. In Model 2, Q 2 operates as a multi-server M/ M/ L 1/∞ queue with varying number of servers, L 1, each serving at a Poisson rate of μ 2. We analyze both models and derive the Probability Generating Functions of the system’s steady-state probabilities. We then calculate the mean total number of customers present in each queue. Extreme cases are indicated. [ABSTRACT FROM AUTHOR]

We consider a sequential matching problem where M offers arrive in a random stream and are to he sequentially assigned to N waiting candidates. Each candidate, as well as each offer, is characterized by a random attribute drawn from a known discrete-valued probability distribution function. An assignment of an offer to a candidate yields a (nominal) reward R > 0 if they match, and a smaller reward r &les R if they do not. Future rewards are discounted at a rate 0 ⩽ α1. We study several cases with various assumptions on the problem parameters and on the assignment regime and derive optimal policies that maximize the total (discounted) reward. The model is related to the problem of donor-recipient assignment in live organ transplants, studied in an earlier work. [ABSTRACT FROM AUTHOR]

We consider a time-dependent stopping problem and its application to the decision-making process associated with transplanting a live organ. "Offers" (e.g., kidneys for transplant) become available from time to time. The values of the offers constitute a sequence of independent identically distributed positive random variables. When an offer arrives, a decision is made whether to accept it. If it is accepted, the process terminates. Otherwise, the offer is lost and the process continues until the next arrival, or until a moment when the process terminates by itself. Self-termination depends on an underlying lifetime distribution (which in the application corresponds to that of the candidate for a transplant). When the underlying process has an increasing failure rate, and the arrivals form a renewal process, we show that the control-limit type policy that maximizes the expected reward is a nonincreasing function of time. For nonhomogeneous Poisson arrivals, we derive a first-order differential equation for the control-limit function. This equation is explicitly solved for the case of discrete-valued offers, homogeneous Poisson arrivals, and Gamma distributed lifetime. We use the solution to analyze a detailed numerical example based on actual kidney transplant data. [ABSTRACT FROM AUTHOR]

A power system for a private automatic branch exchange (PABX) consists of n independent and identical rectifiers hooked up in parallel. The lifetime of each component is an exponential random variable with a known mean (MTBF). The system fails when the number of operating rectifiers is less than m(m * (This character cannot be converted in ASCII text) n). Rectifiers are distinguished by two main characteristics: the current they carry and their MTBF. The minimal number of units, m, is determined by technological considerations: for each type of rectifier, m is calculated so that the system can carry a given maximal current. This maximal current is specified for each PABX. The system is maintained by a technician who may visit the exchange regularly every v units of time or when it fails. Several maintenance policies are considered. For each type of exchange and for each form of maintenance policy, we determine the optimal set of parameters, {m, n, MTBF, and v}, to minimize the operating cost for a required level of reliability. These results are then used as guidelines for standardizing PABX power systems. [ABSTRACT FROM AUTHOR]

This paper studies an M/G/1 queue where the idle time of the server is utilized for additional work in a secondary system. As usual, the server is busy as long as there are units in the main system. However, as soon as the server becomes idle he leaves for a "vacation." The duration of a vacation is a random variable with a known distribution function. Two models are considered. In the first, upon termination of a vacation the server returns to the main queue and begins to serve those units, if any, that have arrived during the vacation. If no units have arrived the server waits for the first arrival when an ordinary M/G/1 busy period is initiated. In the second model, if the server finds the system empty at the end of a vacation, he immediately takes another vacation, etc. For both models Laplace-Stieltjes transforms of the occupation period, vacation period and waiting time are derived and generating functions of the number of units in the system are calculated. The two models are then compared to each other, and for some special cases the optimal mean vacation times are found. [ABSTRACT FROM AUTHOR]

The Asymmetric Inclusion Process (ASIP) is a unidirectional lattice-gas flow model which was recently introduced as an exactly solvable 'Bosonic' counterpart of the 'Fermionic' asymmetric exclusion process. An iterative algorithm that allows the computation of the probability generating function (PGF) of the ASIP's steady state exists but practical considerations limit its applicability to small ASIP lattices. Large lattices, on the other hand, have been studied primarily via Monte Carlo simulations and were shown to display a wide spectrum of intriguing statistical phenomena. In this paper we bypass the need for direct computation of the PGF and explore the ASIP's asymptotic statistical behavior. We consider three different limiting regimes: heavy-traffic regime, large-system regime, and balanced-system regime. In each of these regimes we obtain--analytically and in closed form--stochastic limit laws for five key ASIP observables: traversal time, overall load, busy period, first occupied site, and draining time. The results obtained yield a detailed limit-laws perspective of the ASIP, numerical simulations demonstrate the applicability of these laws as useful approximations. [ABSTRACT FROM AUTHOR]

The asymmetric inclusion process is a lattice-gas model which replaces the "fermionic" exclusion interactions of the asymmetric exclusion process by "bosonic" inclusion interactions. Combining together probabilistic and Monte Carlo analyses, we showcase the model's rich statistical complexity--which ranges from "mild" to "wild" displays of randomness: Gaussian load and draining, Rayleigh outflow with linear aging, inverse-Gaussian coalescence, intrinsic power-law scalings and power-law fluctuations and condensation. [ABSTRACT FROM AUTHOR]