Interconnected networks of queues with randomized arrival and departure blocking

In this paper, we study two interconnected multiclass non-exponential queueing networks. Jobs can jump from one cluster to another, but subject to randomized blocking depending on the class occupancies. Such systems naturally arise in communication networks, like Metropolitan Area Networks. We present sufficient conditions for the existence of a product form equilibrium distribution under both the recirculate and the stop blocking protocol. A number of examples are given.     

Asymptotics for M/G/1 low-priority waiting-time tail probabilities

We consider the classical M/G/1 queue with two priority classes and the nonpreemptive and preemptive-resume disciplines. We show that the low-priority steady-state waiting-time can be expressed as a geometric random sum of i.i.d. random variables, just like the M/G/1 FIFO waiting-time distribution. We exploit this structures to determine the asymptotic behavior of the tail probabilities. Unlike the FIFO case, there is routinely a region of the parameters such that the tail probabilities have non-exponential asymptotics. This phenomenon even occurs when both service-time distributions are exponential. When non-exponential asymptotics holds, the asymptotic form tends to be determined by the non-exponential asymptotics for the high-priority busy-period distribution. We obtain asymptotic expansions for the low-priority waiting-time distribution by obtaining an asymptotic expansion for the busy-period transform from Kendall's functional equation. We identify the boundary between the exponential and non-exponential asymptotic regions. For the special cases of an exponential high-priority service-time distribution and of common general service-time distributions, we obtain convenient explicit forms for the low-priority waiting-time transform. We also establish asymptotic results for cases with long-tail service-time distributions. As with FIFO, the exponential asymptotics tend to provide excellent approximations, while the non-exponential asymptotics do not, but the asymptotic relations indicate the general form. In all cases, exact results can be obtained by numerically inverting the waiting-time transform. This revised version was published online in June 2006 with corrections to the Cover Date.     

Local balance in queueing networks with positive and negative customers

This paper investigates to what extent a recently developed new product form result for queueing networks with positive and negative customers fits into the class of product form queueing networks that satisfy a notion of partial or local balance. As such, this paper investigates whether this new product form is still a consequence of an appropriate notion of local balance. To this end, a new and non-standard type of local balance is introduced as an extension of standard local balance. This new type of local balance appears more restrictive and is no longer directly sufficient for global balance. Nevertheless, based on this new type of local balance, some extensions such as blocking phenomena for queueing networks with positive and negative customers can be concluded.     

Exact analysis of queueing networks with multiple job classes and blocking-after-service

Two models of closed queueing networks with blocking-after-service and multiple job classes are analyzed. The first model is a network withN stations and each station has either type II or type III. The second model is a star-like queueing network, also called a central server model, in which the stations may have either type I or type IV, with the condition that the neighbors of these stations must be of type II or type III such that blocking will be caused only by this set of station types. Exact product form solutions are obtained for the equilibrium state probabilities in both models. Formulae for performance measures such as throughput and the mean number of jobs are also derived.This work was supported by the National Science Foundation (NSF) under Grant No. CCR-90-11981.     

On product form tandem structures

This paper is written in honour to A. Hordijk. It establishes product form results for a generic and instructive multi-class tandem queue with blocking, to which A. Hordijk has directly and indirectly contributed. First, a sufficient and necessary product form characterization is provided. Next, three special cases are briefly presented. These illustrate the possibility of product forms despite finite capacity constraints (blocking), unproportional processor sharing mechanisms and resource contentions (such as for access control). The results are partially new and of interest for present-day applications. In essence these rely upon the pioneering work by A. Hordijk     

Asset allocation,sustainable withdrawal,longevity risk and non-exponential discounting

The present paper studies an optimal withdrawal and investment problem for a retiree who is interested in sustaining her retirement consumption above a pre-specified minimum consumption level. Apparently, the withdrawal and investment policy depends substantially on the retiree’s health condition and her time preferences (subjective discount factor). We assume that the health of the retiree can worsen or improve in an unpredictable way over her lifetime and model the retiree’s mortality intensity by a stochastic process. In order to make the decision about the consumption and investment policy more realistic, we assume that the retiree applies a non-exponential discount factor (an exponential discount factor with a small amount of hyperbolic discounting) to value her future income. In other words, we consider an optimization problem by combining four important aspects: asset allocation, sustainable withdrawal, longevity risk and non-exponential discounting. Due to the non-exponential discount factor, we have to solve a time-inconsistent optimization problem. We derive a non-local HJB equation which characterizes the equilibrium optimal investment and consumption strategy. We establish the first-order expansions of the equilibrium value function and the equilibrium strategies by applying expansion techniques. The expansion is performed on the parameter controlling the degree of discounting in the hyperbolic discounting that is added to the exponential discount factors. The first-order equilibrium investment and consumption strategies can be calculated in a feasible way by solving PDEs.     

A survey of product form queueing networks with blocking and their equivalences

Queueing network models have been extensively used to represent and analyze resource sharing systems, such as production, communication and information systems. Queueing networks with blocking are used to represent systems with finite capacity resources and with resource constraints. Different blocking mechanisms have been defined and analyzed in the literature to represent distinct behaviors of real systems with limited resources. Exact product form solutions of queueing networks with blocking have been derived, under special constraints, for different blocking mechanisms. In this paper we present a survey of product form solutions of queueing networks with blocking and equivalence properties among different blocking network models. By using such equivalences we can extend product form solutions to queueing network models with different blocking mechanisms. The equivalence properties include relationships between open and closed product form queueing networks with different blocking mechanisms.This work has been partially supported by CNR Project Research Funds Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo and by MURST Project Research Funds Performability hw/sw di sistemi distribuiti e paralleli.     

On Jackson's product form with ‘jump-over’ blocking

It is shown that Jackson's product form is retained for queueing networks with capacity constraints under the assumption of a ‘jump-over’ blocking protocol.     

Mixed integer programming for scheduling flexible flow lines with limited intermediate buffers

This paper presents new mixed integer programming formulations for scheduling of a flexible flow line with blocking. The flexible flow line consists of several processing stages in series, separated by finite intermediate buffers, where each stage has one or more identical parallel machines. The line produces several different product types and each product must be processed by, at most, one machine in each stage. A product which has completed processing on a machine may remain there and block the machine until a downstream machine becomes available for processing. The objective is to determine a production schedule for all products so as to complete the products in a minimum time. The basic mixed integer programming formulations have been enhanced to model blocking scheduling with alternative processing routes where for each product a set of routes is available for processing. A reentrant flow line where a product visits a set of stages more than once is also considered. Numerical examples are presented to illustrate applications of the various models proposed.     

On a family of distributions attaining the Bhattacharyya bound

A family of distributions for which an unbiased estimator of a functiong(θ) of a real parameter θ can attain the second order Bhattacharyya lower bound is derived. Indeed, we obtain a necessary and sufficient condition for the attainment of the second order Bhattacharyya bound for a family of mixtures of distributions which belong to the exponential family. Furthermore, we give an example which does not satisfy this condition, but where the Bhattacharyya bound is attainable for a non-exponential family of distributions.     

Product form stationary distributions for queueing networks with blocking and rerouting

In this paper we study Markovian queueing networks in which the service and the routing characteristics have a particular form which leads to a product form stationary distribution for the number of customers in the various queues of the network. We show that if certain transitions are prohibited due to blocking conditions, then the form of the stationary distribution is preserved under a certain rerouting protocol. Several examples are presented which illustrate the wide applicability of the model. This revised version was published online in June 2006 with corrections to the Cover Date.     

Out-patient Queues at the Ibn-Rochd Health Centre

An arbitrary policy of fixing the number of outpatient appointments specifying the dates (and not the exact times) of appointments created long queues and large waiting times in some departments of the Ibn-Rochd health centre, but considerable idle time for the consulting doctors in others. After narrating in detail these circumstances and examining a number of possible options, this paper describes the scientific approaches made to determine the number of appointments, the corresponding parameters of the queue and the system and the service per cent occupation.Finite source size, a random number of initial patients, group arrivals, non-exponential service time distribution, late start-up of the servicing unit and many other factors combined to render available theoretical results difficult to apply and results obtained by applying approximately equivalent theoretical models unreliable as compared with those observed in real life. It is shown that simulation could be more profitably applied in such situations.     

Simple bounds and monotonicity results for finite multi-server exponential tandem queues

Simple and computationally attractive lower and upper bounds are presented for the call congestion such as those representing multi-server loss or delay stations. Numerical computations indicate a potential usefulness of the bounds for quick engineering purposes. The bounds correspond to product-form modifications and are intuitively appealing. A formal proof of the bounds and related monotonicity results will be presented. The technique of this proof, which is based on Markov reward theory, is of interest in itself and seems promising for further application. The extension to the non-exponential case is discussed. For multiserver loss stations the bounds are argued to be insensitive.     

On the blocking process in queue networks

The blocking process in some particular exponential open queue networks is studied. The networks are in the form of two-stage and three-stage queue networks with finite intermediate waitingroom. FIFO scheduling is assumed. Blocking occurs when the flow of units through one queue is momentarily stopped owing to a capacity limitation of another queue have been reached. Exact and approximate bounds for the mean blocking time in these networks are obtained. The condition for stability in the two-stage networks is also derived. Finally the applicability of the results obtained is demonstrated through a case study.     

Markov network processes with product form stationary distributions

This study concerns the equilibrium behavior of a general class of Markov network processes that includes a variety of queueing networks and networks with interacting components or populations. The focus is on determining when these processes have product form stationary distributions. The approach is to relate the marginal distributions of the process to the stationary distributions of “node transition functions” that represent the nodes in isolation operating under certain fictitious environments. The main result gives necessary and sufficient conditions on the node transition functions for the network process to have a product form stationary distribution. This result yields a procedure for checking for a product form distribution and obtaining such a distribution when it exits. An important subclass of networks are those in which the node transition rates have Poisson arrival components. In this setting, we show that the network process has a product form distribution and is “biased locally balanced” if and only if the network is “quasi-reversible” and certain traffic equations are satisfied. Another subclass of networks are those with reversible routing. We weaken the known sufficient condition for such networks to be product form. We also discuss modeling issues related to queueing networks including time reversals and reversals of the roles of arrivals and departures. The study ends by describing how the results extend to networks with multi-class transitions. This revised version was published online in June 2006 with corrections to the Cover Date.     

交叉余积上的Hopf代数结构

本文给出了Ｓｍａｓｈ积代数结构和交叉余积余代数结构构成双代数的一个充分必要条件．另外,还给出了这一新的双代数成为Ｈｏｐｆ代数的一个充分条件．     

Decomposition of ideals into pseudo-irreducible ideals

A proper ideal of a commutative ring is called pseudo-irreducible if it cannot be written as a product of two comaximal proper ideals. In this paper, we give a necessary and su?cient condition for every proper ideal of a commutative ring to be a product of pairwise comaximal pseudo-irreducible ideals. Examples of such rings include Laskerian rings, or more generally J-Noetherian rings and ZD-rings. We study when certain classes of rings satisfy this condition.     

Tail probabilities of low-priority waiting times and queue lengths in MAP/GI/1 queues

We consider the problem of estimating tail probabilities of waiting times in statistical multiplexing systems with two classes of sources – one with high priority and the other with low priority. The priority discipline is assumed to be nonpreemptive. Exact expressions for the transforms of these quantities are derived assuming that packet or cell streams are generated by Markovian Arrival Processes (MAPs). Then a numerical investigation of the large-buffer asymptotic behavior of the the waiting-time distribution for low-priority sources shows that these asymptotics are often non-exponential.     

Splitting trees with neutral mutations at birth

We consider a population model where individuals behave independently from each other and whose genealogy is described by a chronological tree called splitting tree. The individuals have i.i.d. (non-exponential) lifetime durations and give birth at constant rate to clonal or mutant children in an infinitely many alleles model with neutral mutations.     

Source identification for the heat equation

The problem of determining an unknown heat source in a homogeneous, semi-infinite slab from measured temperature and flux data is examined. When the source is separable into a product of temporal and spatial components, a functional relationship is derived that relates the Laplace transforms of these components. Examples considered include a point source with oscillating intensity and a spatial layer undergoing exponential decay. A source of non-separable type in the form of a moving front is alsotreated.