We consider queueing networks containing customers and signals that were recently introduced in Gelenbe [4]. Both customers and signals can be exogenous or can be obtained by a Markovian transition of a customer after service. A signal entering a queue forces a customer to move on to another queue according to a Markovian routing rule or to leave the network in batch mode. This synchronized or triggered motion is useful in representing the effect of tokens in Petri-nets, for systems in which customers and work can be instantaneously moved from one queue to the other on the arrival of a signal as well as for other network behaviors that are encountered in parallel computer system modelling. We show that this network has product form stationary solution and establish the non-linear customer flow equations that govern it. Network stability is discussed in this new context.

A sequential procedure to select optimal prices based on maximum likelihood estimation is considered. Asymptotic properties of the pricing scheme and the concommitant estimation problem are examined. For small sample sizes, simulation results show that the proposed procedure has high efficiency relative to the best procedure when the parameter is known.

We study the problem of scheduling multiclass parallel server queues where the cost for each job is a general class-dependent function of the job's completion time and a second random variable. We characterize the structure of the optimal policy under fairly general conditions on the random variables.

Consider the problem of searching for a leprechaun that moves randomly between two sites. The movement is modelled with a two-state Markov chain. One of the sites is searched at each time t = 1,2,…, until the leprechaun is found. Associated with each search of site i is an overlook probability αi and a cost Ci Our aim is to determine the policy that will find the leprechaun with the minimal average cost. Let p denote the probability that the leprechaun is at site 1. Ross conjectured that an optimal policy can be defined in terms of a threshold probability P* such that site 1 is searched if and only if p ≥ P*. We show this conjecture to be correct (i) when α1 = α2 and C1 = C2, (ii) for general Ci when the overlook probabilities α, are small, and (iii) for general αi and Ci for a large range of transition laws for the movement. We also derive some properties of the optimal policy for the problem on n sites in the no-overlook case and for the case where each site has the same αi, and Ci.

Limit theorems are established and relatively simple closed-form approximations are developed for the busy-period distribution in single-server queues. For the M/G/l queue, the complementary busy-period c.d.f. is shown to be asymptotically equivalent as t → ∞ to a scaled version of the heavy-traffic limit (obtained as p → 1), where the scaling parameters are based on the asymptotics as t → ∞. We call this the asymptotic normal approximation, because it involves the standard normal c.d.f. and density. The asymptotic normal approximation is asymptotically correct as t → ∞ for each fixed p and as p → 1 for each fixed t and yields remarkably good approximations for times not too small, whereas the direct heavy-traffic (p → 1) and asymptotic (t → ∞) limits do not yield such good approximations. Indeed, even the approximation based on three terms of the standard asymptotic expansion does not perform well unless t is very large. As a basis for generating corresponding approximations for the busy-period distribution in more general models, we also establish a more general heavy-traffic limit theorem.

Semi-Markov decision processes underlie the control of many queueing systems. In this paper, we deal with infinite state semi-Markov decision processes with nonnegative, unbounded costs and finite action sets. Axioms for the existence of an expected average cost optimal stationary policy are presented. These conditions generalize the work in Sennott [22] for Markov decision processes. Verifiable conditions for the axioms to hold are obtained. The theory is applied to control of the M/G/l queue with variable service parameter, with on-off server, and with batch processing, and to control of the G/M/m queue with variable arrival parameter and customer rejection. It is applied to a timesharing network of queues with a single server and finally to optimal routing of Poisson arrivals to parallel exponential servers. The final section extends the existence result to compact action spaces.

We consider tandem queueing systems with a general arrival process and exponential service distribution. The queueing system consists of several stations with finite intermediate buffer capacity between the stations. We address the problem of determining the optimal arrangement for the stations. We find that considering the last two stations, the departure process is stochastically faster if the slower station is last. Our results are consistent with the “bowl shape” phenomenon that has been observed in serial queueing systems with zero buffer capacity.

Recently, some authors have suggested usage models of Markov type as a technique of specifying the estimated operational use distribution of a given program. A main purpose of such models is the derivation of random test cases allowing unbiased estimates on the (un)reliability of the program in its intended environment. In this article, we show that by a shift of the transition probabilities of the Markov chain corresponding to such a model, prior information on the errorjproneness of single-program operations can be taken into account. An unbiased unreliability estimator with reduced variance is obtained. Furthermore, it is shown that minimization of the variance leads to a special stochastic optimization problem that can be demonstrated to be convex, such that efficient solution techniques apply. Some related questions are also treated in a more general, non-Markovian framework.

A repair crew is responsible for the maintenance and operation of N installations. The crew has to perform a collection of preventive maintenance tasks at the various installations. The installations may break down from time to time, generating corrective maintenance requests which have priority over the preventive maintenance tasks. We formulate and analyze this real-world problem as a single-server multi-queue polling model with Globally Gated service discipline and with server interruptions. We derive closed-form expressions for the Laplace-Stieltjes Transform and the first moment of the waiting time distributions of the preventive and corrective maintenance requests at the various installations, and obtain simple and easily implementable static and dynamic rules for optimal operation of the system. We further show that, for the socalled elevator-type polling scheme, mean waiting times of preventive maintenance jobs at all installations are equal.

In this short note, we give a counterexample to a conjecture of Koole (1995, Stochastic scheduling and dynamic programming) concerning the equivalence of two orderings arising in the context of a customer assignment model with asymmetric service times.

We consider the group testing problem for a set of independent items I = [I1,… In] where Ii, has probability pi, of being defective and probability qi = 1 – pi of being good. The problem is to classify all items as good or defective with a minimum expected number of group tests where a group test is a test on a subset S of I with two possible outcomes: either S is pure (contains no defective) or S is contaminated (contains at least one defective, with no information provided about which or how many). No polynomial-time algorithm is known for the group testing problem even for the special case pi = p for all i. Hence, any method that reduces the size of the problem is very helpful. In this paper, we give such a method by providing a simple condition to screen items that should be tested (only) individually. This condition leads to a necessary and sufficient condition for the individual testing algorithm to be optimal, generalizing a result of Unger [1] for the special case of identical pi.

The concept of rainflow cycles is often used in fatigue of materials for analyzing load processes. Methods are developed for computation of the rainflow matrix for a random load that is changing properties over time due to changes of the system dynamics; for example, for a random vehicle load it could reflect different driving conditions. The random load is modeled by a switching process with Markov regime; that is, the random load changes properties according to a hidden (not observed) Markov chain.

An algorithm is developed for a switching process where each part of the load is modeled by a Markov chain. As only the local extremes are of importance for rainflow analysis, another approach is to model the sequence of turning points by a Markov chain. The main result of this paper is an algorithm for computation of the rainflow matrix for a switching process where each part is described by a Markov chain of turning points. The algorithms are illustrated by numerical examples.

Efficiently computable bounds are developed for the time to first failure in a communications network with renewable links. The bounds approximate a network with bidirectional or unidirectional links by acyclic networks with unidirectional links.

Loss networks with direct routing have a product-form solution for their equilibrium probabilities. The product-form solution typically involves a normalization constant calling for a multidimensional summation over an astronomical number of states. We propose the application of Monte Carlo summation in order to determine the normalization constant, the blocking probabilities, and the revenue sensitivities. We show that if the proper sampling technique is employed, then the computational effort of Monte Carlo summation is independent of link capacities. We also discuss the application of importance sampling, antithetic variates, and indirect estimation via Little's formula. The method is illustrated with a four-leaf star network supporting multirate traffic.

Consider the standard network reliability model in which each edge of a given (n, m)-graph G is deleted, independently of all others, with probability q = 1– p (0 <p < 1). The pair-connectivity random variable X is defined to be the number of connected pairs of vertices that remain in G. The mean of X has been proposed as a measure of reliability for failure-prone communications networks in which the edge deletions correspond to failures of the communications links. We consider deviations from the mean, the law of large numbers, and the central limit theorem for X as n → ∞. Some explicit results are obtained when G is a tree using martingale difference sequences. Stars and paths are treated in detail.

The burn-in problem is reframed in a decision-making context. The role of the predictive life distribution in the burn-in decision problem is highlighted. The case in which the predictive distribution is a mixture of exponentials is discussed extensively.