bluuebunny/crossref_metadata_2025 huggingface dataset:
Asymptotic Properties of a Recursive Procedure for Simultaneous Estimation
Authors: Reiman Martin I.
Published: July 2009

In this paper we consider a problem that arises in estimating the heavy traffic limit of a sojourn time distribution in a queueing network during the course of a medium traffic simulation. We need to estimate α =E[f(γ,M)], where γ is an unknown constant andMa random variable. More specifically, we are given an iid sequence of random vectors {(Xi,Mi), 1 ≤ i ≤ n}, with γ =E[Xi] andMihaving the same distribution asM.

For known γ, we have a standard estimation problem, which we describe here. The standard estimate is unbiased and asymptotically (asn→ 8 ) consistent. There is also a central limit theorem for this estimator. For unknown γ, we provide two estimation procedures, one that requires two passes through the data (as well as storage of {Mi, 1 ≤ i ≤ n}), and another one, which is recursive, requiring only one pass through and bounded storage. The estimators obtained from these two procedures are shown to be strongly consistent, and central limit theorems are also proven for them.
On a Result of Aleliunas et al. Concerning Random Walks on Graphs
Authors: Palacios José Luis
Published: July 2009

Aleliunas et al. [3] proved that for a random walk on a connected raph G = (V, E) on N vertices, the expected minimum number of steps to visit all vertices is bounded by 2|E|(N - 1), regardless of the initial state. We give here a simple proof of that result through an equality involving hitting times of vertices that can be extended to an inequality for hitting times of edges, thus obtaining a bound for the expected minimum number of steps to visit all edges exactly once in each direction.
Quicker Convergence for Iterative Numerical Solutions to Stochastic Problems: Probabilistic Interpretations, Ordering Heuristics, and Parallel Processing
Authors: Greenberg Albert G. , Vanderbei Robert J.
Published: July 2009

Gauss-Seidel is a general method for solving a system of equations (possibly nonlinear). It makes repeated sweeps through the variables; within a sweep as each new estimate for a variable is computed, the current estimate for that variable is replaced with the new estimate immediately, instead of on completion of the sweep. The idea is to use new data as soon as it is computed. Gauss- Seidel is often efficient for computing the invariant measure of a Markov chain (especially if the transition matrix is sparse), and for computing the value function in optimal control problems. In many applications the computation can be significantly improved by appropriately ordering the variables within each sweep. A simple heuristic is presented here for computing an ordering that quickens convergence. In parallel processing, several variables must be computed simultaneously, which appears to work against Gauss-Seidel. Simple asynchronous parallel Gauss-Seidel methods are presented here. Experiments indicate that the methods retain the benefit of a good ordering, while further speeding up convergence by a factor of P if P processors participate.

In this paper, we focus on the optimal stopping problem. A probabilistic interpretation of the Gauss-Seidel (and the Jacobi) method for computing the value function is given, which motivates our ordering heuristic. However, the ordering heuristic and parallel processing methods apply in a broader context, in particular, to the important problem of computing the invariant measure of a Markov chain.
Alternative to koehler's Approximation for the Percentiles of the t Distributions
Authors: Lin Jonn-Tyan
Published: July 2009

An alternative to Koehler's approximation for the percentiles of the t distribution is given. The alternative is not only slightly more accurate than Koehler's, but also the former is more convenient than the latter when measured in terms of the number of keystrokes.
Sharp Bounds on the Largest of some Linear Combinations of Random Variables with Given Marginal Distributions
Authors: Meilijson Isaac
Published: July 2009

Let X be a random vector and A a matrix. Let M be the maximal coordinate of the vector AX. For given marginal distributions of the coordinates of X, we present sharp bounds on the expectations of convex increasing functions of M. We derive joint distributions of X that achieve some of these bounds, and under these “worst case” distributions we study the joint distribution of M and the index of the largest coordinate of AX. Some possible applications are PERT network analysis and design of experiments.
Limiting Distributions for Path Lengths in Recursive Trees
Authors: Mahmoud Hosam M.
Published: July 2009

The depth of insertion and the internal path length of recursive trees are studied. Luc Devroye has recently shown that the depth of insertion in recursive trees is asymptotically normal. We give a direct alternative elementary proof of this fact. Furthermore, via the theory of martingales, we show thatIn, the internal path length of a recursive tree of ordern, converges to a limiting distribution. In fact, we show that there exists a random variableIsuch that (In–nIn n)/n→Ialmost surely and in quadratic mean, asn→ α. The method admits, in passing, the calculation of the first two moments ofIn.
On a Simple Numerical Method for Computing Stieltjes Integrals in Reliability Theory
Authors: Boehme T. K. , Preuss W. , Wall V. van der
Published: July 2009

A simple method of calculating Stieltjes integrals is proposed. The method is essentially the two-point (trapezoidal) rule from numerical analysis. Two theorems yielding error bounds are given. When error requirements are modest (two or three significant decimal places) the method is fast and inexpensive. Examples are given solving the Renewal equation from reliability theory. A program for an HP-41C hand calculator is given, which solves the renewal equation.
Bowl Shapes Are Better with Buffers–Sometimes
Authors: Ding Jie , Greenberg Betsy S.
Published: July 2009

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.
A Queueing Network Model for a Communication System with Channel Allocation
Authors: Brandt A. , Sulanke H.
Published: July 2009

A communication system ofnstations is studied. Poisson arrival streams of messages enter the stations and require transmission to a destination station. Each station is equipped withkchannels and has a waiting room for messages. For transmission of a message, one channel is needed both at the arrival and at the destination station. The transmission time is exponentially distributed. Messages are lost (possibly after a waiting time) if, at the destination station, all channels are busy. The queueing network model is of the nonproduct type. Sufficient conditions for the existence of an equilibrium distribution are given. For determining the losses at thenstations, a heuristical approximation that requires us to solve a system of nonlinear equations is developed. For this, an efficient iterative numerical algorithm is given. Simulation studies show that the approximation is accurate enough for largern.
Stochastic Flow-Shop Scheduling with Lateness-Related Performance Measures
Authors: Lee Chung-Yee , Lin Chen-Sin
Published: July 2009

In this paper we consider stochastic flow-shop scheduling with reference to certain lateness-related performance measures. We show that for various assumptions on the distribution of job-processing times of a flow shop, certain scheduling policies following the stochastic analogy of the Earliest Due Date (EDD) rule yield optimal results.
A General Framework for Stochastic One-machine Scheduling Problems with Zero Release Times and No Partial Ordering
Authors: frenk J. B. G.
Published: July 2009

In this paper we present a general framework for stochastic one-machine scheduling problems with zero release times and no partial ordering and review and extend some of the results for nonpreemptive permutation schedules recently obtained for these models.
A Note on One-Machine Scheduling Problems with Imperfect Information
Authors: Frenk J. B. G.
Published: July 2009

In this paper we consider one-machine scheduling problems with or without a perfect machine and random processing times and derive among other results elimination criteria for different classes of cost functions.
Stochastically Minimizing Total Delay of Jobs Subject to Random Deadlines
Authors: Xu Susan H.
Published: July 2009

This paper analyzes a scheduling system where a fixed number of nonpreemptive jobs is to be processed on multiple parallel processors with different processing speeds. Each processor has an exponential processing time distribution and the processors are ordered in ascending order of their mean processing times. Each job has its own deadline that is exponentially distributed with rate ß1, independent of the deadlines of other jobs and also independent of job processing times. A job departs the system as soon as either its processing completes or its deadline occurs. We show that there exists a simple threshold strategy that slochastically minimizes the total delay of all jobs. The policy depends on distributions of processing times and deadlines, but is independent of the rate of deadlines. When the rate of the deadline distribution is 0 (no deadlines), the total delay reduces to the flowtime (the sum of completion times of all jobs). If each job has its own probability of being correctly processed, then an extension of this policy stochastically maximizes the total number of correctly processed, nontardy jobs. We discuss possible generalizations and limitations of this result.
On the Optimality of Trunk Reservation in Overflow Processes
Authors: Nguyen Viên
Published: July 2009

This paper discusses an optimal dynamic policy for a queueing system with M servers, no waiting room, and two types of customers. Customer types differ with respect to the reward that is paid on commencement of service, but service times are exponentially distributed with the same mean for both types of customers. The arrival stream of one customer type is generated by a Poisson process, and the other customer type arrives according to the overflow process of an M/M/m/m queue. The objective is to determine a policy for admitting customers to maximize the expected long-run average reward.

By posing the problem in the framework of Markov decision processes and exploiting properties of submodular functions, the optimal policy is shown to be a “generalized trunk reservation policy”; in other words, the optimal policy accepts higher-paying customers whenever possible and accepts lower-paying customers only if fewer than c1 servers are busy, where i is the number of busy servers in the overflow queue. Computational issues are also discussed. More specifically, approximations of the overflow process by an interrupted Poisson process and a Poisson process are investigated.
Asymptotic Behaviour of an Integrated Video-Data Network
Authors: Hunt P. J.
Published: July 2009

We consider a communication network that can support both wideband video calls and narrowband data traffic. First we consider a single link and prove a weak convergence result to justify a piecewise-deterministic Markov process approximation to the system. We then generalize this approximation to allow priorities and more than one link. This second approximation is a generalization of the Erlang fixed-point approximation for loss networks and is justified via a diverse routing limit theorem.
Stochastic Petri Nets: Modeling Power and Limit Theorems
Authors: Haas Peter J. , Shedler Gerald S.
Published: July 2009

Generalized semi-Markov processes and stochastic Petri nets provide building blocks for specification of discrete event system simulations on a finite or countable state space. The two formal systems differ, however, in the event scheduling (clock-setting) mechanism, the state transition mechanism, and the form of the state space. We have shown previously that stochastic Petri nets have at least the modeling power of generalized semi-Markov processes. In this paper we show that stochastic Petri nets and generalized semi-Markov processes, in fact, have the same modeling power. Combining this result with known results for generalized semi-Markov processes, we also obtain conditions for time-average convergence and convergence in distribution along with a central limit theorem for the marking process of a stochastic Petri net.
Storage-Limited Queues in Heavy Traffic
Authors: Coffman E. G. , Pukhalskii A. A. , Reiman M. I.
Published: July 2009

This paper models primary computer storage in the context of a general (GI/GI/l) queueing system. Queued items are described by sizes, or storage requirements, as well as by arrival and service times; the sum of the sizes of the items in the system is the occupied storage. Capacity constraints are represented by two different protocols for determining whether an arriving item is admitted to the system: (1) an item is accepted if and only if at its arrival time the currently occupied storage does not exceed a given constantC> 0, and (2) an item is accepted if and only if at its arrival time the occupied storage is at mostC, and the occupied storage plus the item's size is at mostC(l + ε) for some given ε > 0. We prove for both systems that in heavy traffic the occupied storage, suitably normalized, converges weakly to reflected Brownian motion with boundaries at 0 and atC. A distinctive feature of the proof is the characterization of reflected Brownian motion as a limit of unrestricted penalized processes.

These results make more plausible an earlier conjecture of the authors, i.e., that one obtains the same heavy traffic limit when the admission rule is: accept an item if and only if at its arrival time the occupied storage plus the item's size is no greater thanC.
Spatiotemporal Convexity of Stochastic Processes and Applications
Authors: Shanthikumar J. George , Yao David D.
Published: July 2009

A stochastic process {Xt(s)} is viewed as a collection of random variables parameterized by time (t) and the initial state (s). {Xt(s)} is termed spatiotemporally increasing and convex if, in a sample-path sense, it is increasing in s and t and satisfies a directional convexity property, which implies that it is increasing and convex in s and in t (individually) and is supermodular in (s, t). Simple sufficient conditions are established for a uniforniizable Markov process to be spatiotemporally increasing and convex. The results are applied to study the convex orderings in GI/M(n)/l and M(n)/G/1 queues and to solve the optimal allocation of a joint setup among several production facilities. For a counting process that possesses a stochastic intensity, we show that its spatiotemporal behavior can be characterized by its conditional intensity via a birth process.
Fluid Models with Burst Arrivals: A Sample Path Analysis
Authors: Sigman Karl , Yamazaki Genji
Published: July 2009

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.
Optimal Scheduling of a Finite Capacity Shuttle under Delayed Information
Authors: Oyen Mark P. Van , Teneketzis Demosthenis
Published: July 2009

We consider the optimal scheduling of a finite capacity shuttle in a two-node network with imperfect information. When shuttle trips do not depend on the number of passengers carried, we prove optimality and monotonicity of threshold policies. We derive conditions for dispatching that reduce the computational effort required to compute an optimal threshold policy. We prove a counter-example to the optimality of threshold policies for finite horizon problems where trip lengths increase stochastically in the number of passengers carried.
Optimal Age and Block Replacement for a General Maintenance Model
Authors: Chen C. S. , Savits Thomas H.
Published: July 2009

We continue the study of our general cost structure for a maintained system. Here we focus on the optimization questions for an age or block policy. The notion of a marginal cost function is rigorously formulated and its utility investigated. Various applications are considered, including a new model in which minimal repairs are performed as long as the total accumulated repair costs do not exceed a fixed amount.
Capacity Expansion in Stochastic Flow Networks
Authors: Alexopoulos Christos , Fishman George S.
Published: July 2009

Sensitivity analysis represents an important aspect of network flow design problems. For example, what is the incremental increase in system flow of increasing the diameters of specified pipes in a water distribution network? Although methods exist for solving this problem in the deterministic case, no comparable methodology has been available when the network's arc capacities are subject to random variation. This paper provides this methodology by describing a Monte Carlo sampling plan that allows one to conduct a sensitivity analysis for a variable upper bound on the flow capacity of a specified arc. The proposed plan has two notable features. It permits estimation of the probabilities of a feasible flow for many values of the upper bound on the arc capacity from a single data set generated by the Monte Carlo method at a single value of this upper bound. Also, the resulting estimators have considerably smaller variancesthan crude Monte Carlo sampling would produce in the same setting. The success of the technique follows from the use of lower and upper bounds on each probability of interest where the bounds are generated from an established method of decomposing the capacity state space.
System Reliability By Simulation: Random Hazards Versus Importance Sampling
Authors: Jun Chi Hyuck , Ross Sheldon M.
Published: July 2009

Two approaches for simulating the reliability function are considered–one using the total hazard estimator and the other using importance sampling. It is shown both for the Wheatstone Bridge System and for a triangular system that the total hazard estimator has significantly smaller variance when compared both to the standard importance sampling estimator and to an improved version of it.
Maximum Queue Length and Waiting Time Revisited: Multserver G/G/c Queue
Authors: Sadowsky John S. , Szpankowski Wojciech
Published: July 2009

We characterize the probabilistic nature of the maximum queue length and the maximum waiting time in a multiserver G/G/c queue. We assume a general i.i.d. interarrival process and a general i.i.d. service time process for each server with the possibility of having different service time distributions for different servers. Under a weak additional condition, we will prove that the maximum queue length and waiting time grow asymptotically in probability as logωn−1 and log n1/θ, respectively, where ω < 1 and θ > 0 are parameters of the queuing system. Furthermore, it is shown that the maximum waiting time – when appropriately normalized – converges in distribution to the extreme distribution Λ(x) = exp(−e−x). The maximum queue length exhibits similar behavior, except that some oscillation caused by the discrete nature of the queue length must be taken into account. The first results of this type were obtained for the G/M/l queue by Heyde and for the G/G/l queue by Iglehart. Our analysis is similar to that of Heyde and Iglehart. The generalization to c > 1 servers is made possible due to the recent characterization of the tail of the stationary queue length and waiting time in a G/G/c queue (cf. Sadowsky and Szpankowski [17]).
Preemptive Scheduling of Stochastic Jobs with a Two-Stage Processing Time Distribution on M + 1 Parallel Machines
Authors: Huang Chueng-Chiu , Weiss Gideon
Published: July 2009

We analyze the optimal preemptive sequencing of n jobs on M + 1 parallel identical machines to minimize expected total flowtime. The running times of the jobs are independent samples from the distribution Pr(X = H) = p, Pr(X = H + T) = 1 − p, where H, T are random variables of general distribution. Preemption of a job is allowed when H is completed. This problem does not have a simple optimal solution. We show that the scheme of shortest expected remaining processing time first (SERPT) is close to optimal in two senses. The expected flowtime under SERPT and under the optimal policy differ by no more than a constant, independent of the number of jobs, and the expected number of optimal decisions that are not according to SERPT is bounded by a constant, independent of the number of jobs.
Loading and Sequencing on Parallel Machines
Authors: Righter Rhonda
Published: July 2009

We consider the problem of scheduling jobs on parallel machines to minimize flowtime, where all decisions about loading and sequencing must be made before any processing is done. We find policies that minimize flowtime stochastically or in the increasing convex sense under various assumptions.
Oil Exploration: Revisited
Authors: Benkherouf Lakdére
Published: July 2009

In this paper we give a short proof of a general version of Theorem 3.3 of Benkherouf [2].
Some Moment Inequalities for the Minimal Repair Process
Authors: Kirmani S. N. U. A. , Gupta Rmaesh C.
Published: July 2009

Some monotonicity properties and bounds on expectations of certain functions of minimal repair times and interminimal repair times are obtained under assumptions on the aging characteristics of the equipment under maintenance.
Two Examples of Physically Realizable Processes Whose Spectral Density Is Not “Physically Realizable”
Authors: Balakrishnan A. V.
Published: July 2009

In this paper we present two examples of physically realizable processes whose spectral density is not “physically realizable.”
Stability of Product Form G-Networks
Authors: Gelenbe Erol , Schassberger Rolf
Published: July 2009

We prove necessary and sufficient conditions for the existence and uniqueness of the stationary solution of the queueing networks (G-networks) with negative and positive customers introduced in Gelenbe [3], which have been shown to have product form. First, the existence of the solution of the nonlinear customer flow equations is established using Brouwer's fixed-point theorem; this result is valid for stable and unstable systems, as well as for certain networks that may not have product form. Then, the result is used to establish general stability related to the usual “load factor less than 1” criterion of queueing systems for G-networks with product form.
Monte Carlo Summation Applied to Product-Form Loss Networks
Authors: Ross Keith W. , Wang Jie
Published: July 2009

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.
Product-Type Probability Bounds of Higher Order
Authors: Block Hentry W. , Costigan Tim , Sampson Allan R.
Published: July 2009

GIaz and Johnson [14] introduce ith-order product-type approximations, βi, i =1,…n − 1, for Pn = P(X1 ≤c1, X2 ≤ c2,…Xn≤ cn) and show that Pn≥ βn−1 ≥ βn−2 ≥… ≥ β2 ≥ β1 when X is MTP2. In this article, it is shown that

under weaker positive dependence conditions. For multivariate normal distributions, these conditions reduce to cov(Xi,Xj) ≥ 0 for 1 ≤ i < j ≤ n and cov(Xi,Xj| Xj−1) ≥ 0 for 1 ≤ i < j − 1, j = 3,…,n. This is applied to group sequential analysis with bivariate normal responses. Conditions for Pn ≥ β3 ≥ β2 ≥β1 are also derived. Bound conditions are also obtained that ensure that product-type approximations are nested lower bounds to upper orthant probabilities P(X1 > C1,…,Xn > cn). It is shown that these conditions are satisfied for the multivariate exponential distribution of Marshall and Olkin [20].
Higher-Order Weak Approximation of Ito Diffusions by Markov Chains
Authors: Platen Eckhaard
Published: July 2009

This paper proposes a method that allows the construction of discrete-state Markov chains approximating an Ito-diffusion process. The transition probabilities of the Markov chains are chosen in such a way that functionals converge with a desired weak order with respect to vanishing step size under sufficient smoothness assumptions.
Least Busy Alternative Routing in Queueing and Loss Networks
Authors: Hunt P. J. , Laws C. N.
Published: July 2009

This paper is divided into two distinct parts: the first considers a loss network, the second a queueing network. In each case, we consider a fully connected network consisting of a large number of links (queues) and operating under a dynamic routing policy known as least busy alternative routing. Using weak convergence results, we can examine the behavior of the networks as the number of links (queues) increases to infinity. We find that, despite the models having similarities and being amenable to the same analytical tools, they exhibit important differences in character.
On Optimal Permutation Scheduling in Stochastic Proportionate Flowshops
Authors: Pinedo Michael , Shaw Dequan , Chao Xiuli
Published: July 2009

Consider m machines in series with unlimited intermediate buffers and n jobs available at time zero. The processing times of job j on all m machines are equal to a random variable Xj with distribution Fj. Various cost functions are analyzed using stochastic order relationships. First, we focus on minimizing where cj is the weight (holding cost) and Tj the completion time of job j. We establish that if are in a class of distributions we define as SIFR, and and are increasing sequences of likelihood ratio-ordered and stochastic-ordered random variables, respectively, the job sequence [1, 2, … n ] is optimal among all static permutation schedules. Second, for arbitrary processing time distributions, if is an increasing sequence of likelihood ratio-ordered (hazard rate-ordered) random variables and the costs are nonincreasing, then a general cost function is minimized by the job sequence [1,2,…, n] in the stochastic ordering (increasing convex ordering) sense.
A Generalized Age-Replacement Model
Authors: Vanneste Stephan G.
Published: July 2009

Four practically important extensions of the classical age-replacement problem are analyzed using Markov decision theory: (1) opportunity maintenance, (2) imperfect repair, (3) non-zero repair times, and (4) Markov degradation of the working unit. For this general model, we show that the optimal maintenance policy is of the control limit type and that the average costs are a unimodal function of the control limit. An efficient optimization procedure is provided to find the optimal policy and its average costs. The analysis extends and unifies existing results.
Rate Conservation Law for Stationary Semimartingales
Authors: Bardhan Indrajit , Sigman Karl
Published: July 2009

The Rate Conservation Law (RCL) of Miyazawa [18] is generalized to what we call a General Rate Conservation Law (GRCL) to cover processes of unbounded variation such as Brownian motion and more general Levy processes. The general setup is that of a time-stationary semimartingale Y = [Yt: t ≥ 0], which is allowed to have jumps. From an elementary application of Ito's formula together with the Palm inversion formula, we obtain a law that includes Miya-zawa's RCL as a special case. A variety of applications and connections with the RCL are given. For example, we show that using the GRCL, one can immediately obtain the noted steady-state decomposition results for vacation queueing models, including those obtained by Kella and Whitt [13] for Jump-Levy processes. Other examples include state-dependent diffusion processes such as the Ornstein-Uhlenbeck process.
Comparison of Two Approximations for the Loss Probability in Finite-Buffer Queues
Authors: Miyazawa Masakiyo , Tijms Henk
Published: July 2009

This paper deals with two related approximations that were recently proposed for the loss probability in finite-buffer queues. The purpose of the paper is twofold: first, to provide better insight and more theoretical support for both approximations, and second, to show by an experimental study how well both approximations perform. An interesting empirical finding is that in many cases of practical interest the two approximations provide upper and lower bounds on the exact value of the loss probability.
On Sequencing Two Types of Tasks on a Single Processor under Incomplete Information
Authors: Burnetas Apostolos N. , Katehakis Michael N.
Published: July 2009

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.
An Improved Lower Bound on the Minimum Expected Number of Binomial Group Tests
Authors: Abrahams Julia
Published: July 2009

The minimum expected number of binomial group tests is lower bounded by the cost of a particular Huffman coding problem whose solution is known. Thus, the information lower bound in binomial group testing is improved when the probability that each item is defective is small.
Some Pitfalls of Black Box Queue Inference: The Case of State-Dependent Server Queues
Authors: Ross Sheldon M. , Shanthikumar J. George , Zhang Xiang
Published: July 2009

In several queueing systems the service rate of a server is affected by the work load present in the system. For example, a teller at a bank or a checker at a check-out counter in a supermarket may change the service rate depending on the number of customers present in the system. But the service rate as a function of the number in the system can rarely be measured. Consequently, in a typical model of such a system it is assumed that the service rate is constant. Hence, such systems with a single stage are often modeled by GI/GI/c queueing systems with mutually independent arrival and service processes. Then the observed service times are used to find a sample distribution that will represent the distribution of the assumed i.i.d. service times. The purpose of this paper is to explore the effect of this black box queue inference (BBQI) in its ability to predict the performance of the actual system. In this regard, we have shown that when the arrival process is Poisson, if the servers react favorably [unfavorably] to higher work loads (i.e., if the server increases [decreases] the service rate as the number of customers in the system increases) then the BBQI predictions will be pessimistic [optimistic]. This result can be used to identify the server's attitude toward higher work load.
Using Distributed-Event Parallel Simulation to Study Departures from Many Queues in Series
Authors: Greenberg Albert G. , Schlunk Otmar , Whitt Ward
Published: July 2009

In this paper we describe an application of distributed-event parallel simulation to study the transient behavior of a large non-Markovian network of queues. In particular, we implemented the parallel-prefix-based algorithm of Greenberg, Lubachevsky, and Mitrani [13,14] on the 8,192-processor CM-2 Connection machine and the 16,384-processor MasPar computer to simulate the departure times D(k, n) of the kth customer from the nth queue in a long series of single-server queues. Each queue has unlimited waiting space and uses the first-in first-out discipline. The service times of all the customers at all the queues are i.i.d. with a general distribution, and the system starts out with k customers in the first queue and all other queues empty. Glynn and Whitt [11] established limit theorems for this model, but very little could be said about the limits themselves. The simulation results presented here describe the limits and the quality of the approximations resulting from using the limits for finite k and n. Indeed, the simulations suggest interesting conjectures. For this model speeding up a single long run is far superior to independent replications, because very long runs are required to obtain unbiased estimates of the desired quantities and the variance of the estimator at the end of the run is small. The achieved simulation rate was about 17 billion service completions per hour, which is a speedup by about a factor of 100 compared to simulation on a conventional single-processor machine. This speedup contributed greatly to performing the desired experiments.
A Globally Gated Polling System with Server Interruptions, and Applications to the Repairman Problem
Authors: Boxma O. J. , Weststrate J. A. , Yechiali U.
Published: July 2009

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.
Asymptotic Normality for Oscillation of Permutation
Authors: Chao Chern-Ching , Bai Zhidong , Liang Wen-Qi
Published: July 2009

Suppose each permutation (πl,…,πn) of ( 1, …,n) has probability 1/n!. The oscillation of (πl; …, πn) is defined asTn=| πk− πk+1|, where πn+1= π1. It is proved that (Tn−ETn)/(varTn)1/2converges in distribution toN(0,1). The connection between the oscillation and the presortedness measure is also discussed.
Large Deviations of Birth Death Markov Fluids
Authors: De Veciana G. , Olivier C. , Walrand J.
Published: July 2009

The asymptotic probability of buffer overflow for a queueing system with a Markov fluid input and deterministic service rate is derived by way of large deviation theory. The equations characterizing the deviant behavior are presented and examples are given for which closed-form solutions may be obtained. An independence result extends the analysis to cases where the input is an aggregate of independent Markov fluids.
Optimal Control Policies for Stochastic Inventory Systems with Endogenous Supply
Authors: Federgruen A. , Zheng Y.-S.
Published: July 2009

We consider an inventory system with compound Poisson demands replenished by discrete production of units on a single-server facility. This facility may start a vacation at any production completion epoch; at the completion of a vacation the inventory level is inspected to decide whether or not to resume production. Unit production and vacation times are independent and identically distributed with general distributions. Under an (s, S) policy, production is terminated when the inventory level reaches a critical level S, and production is resumed when the inventory level, upon completion of a vacation, is at or below a prespecified value s. In this paper we prove that an (s, S) policy is optimal among all possible policies. We also derive a highly efficient algorithm for the determination and evaluation of an optimal (s, S) policy.
Stochastic Scheduling in Priority Queues with Strict Deadlines
Authors: Pandelis Dimitrios G. , Teneketzis Demosthenis
Published: July 2009

Tasks belonging to N priority classes arrive for processing in a single or multiserver facility. If the processing does not begin by a certain time (deterministic or random), the task is lost and a cost is incurred. We determine properties of dynamic, nonidling, nonpreemptive strategies that minimize an infinite horizon expected cost.
On Generalized Networks of Queues with Positive and Negative Arrivals
Authors: Chao Xiuli , Pinedo Michael
Published: July 2009

Consider a generalized queueing network model that is subject to two types of arrivals. The first type represents the regular customers; the second type represents signals. A signal induces a regular customer already present at a node to leave. Gelenbe [5] showed that such a network possesses a product form solution when each node consists of a single exponential server. In this paper we study a number of issues concerning this class of networks. First, we explain why such networks have a product form solution. Second, we generalize existing results to include different service disciplines, state-dependent service rates, multiple job classes, and batch servicing. Finally, we establish the relationship between these networks and networks of quasi-reversible queues. We show that the product form solution of the generalized networks is a consequence of a property of the individual nodes viewed in isolation. This property is similar to the quasi-reversibility property of the nodes of a Jackson network: if the arrivals of the regular customers and of the signals at a node in isolation are independent Poisson, the departure processes of the regular customers and the signals are also independent Poisson, and the current state of the system is independent of the past departure processes.
Some Monotone Almost Balanced Knockout Tournament Plans
Authors: Chen R. W. , Hwang F. K. , Yao Y. C. , Zame A.
Published: July 2009

Knockout tournaments are often used in sports (or experiments where preferences are registered by comparisons instead of measurements) to determine the champion of an event. A knockout tournament plan (KTP) for n players is a rooted binary tree with n leaves to be labeled by the n players. Each subtree of two leaves represents a match between the two players labeling the two leaves; the winner of the match then moves on to label the root of the subtree. While there are many KTPs to choose from for a given number of players, in the real world an almost balanced KTP is usually chosen. One reason could be the perception that a balanced KTP is “fair” to the players, in the sense that, given a random labeling of leaves by players, a stronger player has a better chance to win the tournament. Surprisingly, it has been shown that not all KTPs have this property, and it is difficult to prove this property for any general class of KTPs. So far the property has been shown to hold only for balanced KTPs. In this paper we extend it to some classes of almost balanced KTPs.
Optimal Occupation in the Complete Graph
Authors: Siegrist Kyle
Published: July 2009

We consider N sites (N ≤ ∞), each of which may be either occupied or unoccupied. Time is discrete, and at each time unit a set of occupied sites may attempt to capture a previously unoccupied site. The attempt will be successful with a probability that depends on the number of sites making the attempt, in which case the new site will also be occupied. A benefit is gained when new sites are occupied, but capture attempts are costly. The problem of optimal occupation is formulated as a Markov decision process in which the admissible actions are occupation strategies and the cost is a function of the strategy and the number of occupied sites. A partial order on the state-action pairs is used to obtain a comparison result for stationary policies and qualitative results concerning monotonicity of the value function for the n-stage problem (n ≤ ∞). The optimal policies are partially characterized when the cost depends on the action only through the total number of occupation attempts made.
Optimal Sampling for Identifying a Cluster: An Application in Sorting
Authors: Gal Shmuel , Sheinwald Dafna
Published: July 2009

We consider the following problem. For a given population of m items, we have to make a decision whether or not the population includes a relatively large cluster of identical items. This decision affects the effectiveness of a subsequent computational process, depending on the actual existence of the cluster and its size. To make a good decision, we use a statistical sample which should indicate the existence of a cluster and find a representative thereof. This paper describes the optimal sampling technique to be used in such a case, given the cost of the sampling and the potential gain in speed of the subsequent process. The optimal fixed sample size is specified, as well as the optimal sequential sampling, along with characterizing the dependence of the cost function on the truncation point.

For the case that the a priori distribution of the cluster proportion is known, we present formulae by which the optimal sampling procedures can be easily calculated. For the common situation in which the a priori distribution is not known, we present, in the case of a fixed sample size, a tight upper bound for the sample size, which is independent of the a priori distribution, and for the case of the sequential sampling, we present an approximately optimal truncation point, which is also independent of the a priori distribution.

The situation described arose in connection with choosing the best sorting method, an application that will be described in full detail. The most interesting practical result is that for our application truncating the sequential procedure at 35 observations, out of a population of 25,000–30,000 items, guarantees that in our sorting application we are always within 2.1% of the optimal cost independently of the a priori distribution.
Stochastic Comparison of Some Wear Processes
Authors: Pellerey Franco , Shaked Moshe
Published: July 2009

Let [NA(t), t≥0] and [NB(t), t≥0] be two counting processes with independent interarrivals Ai and Bi, respectively, i ∈ + ≡ [1,2,… ], and let [Xi, i ∈ +] and [Yi, i ∈ +] be two sequences of independent non-negative random variables. Consider the two compound processes [U(t), t ≥ 0] and [V(t), t ≥ 0] defined as U(t) = Xi, t ≥ 0, and V(t) = Yi, t ≥ 0. Then it is well known (and not hard to verify) that if the Ai's are independent of the Xi's, and if the Bi's are independent of the yi's, and if Ai ≥st Bi and Xi ≤st Yi, for all i ∈ +, then [U(t), t ≥ 0] ≤st [V(t), t ≥ 0]. In this paper we provide conditions under which this stochastic order relation holds even if Ai ≤st Bi and/or Xi ≥st Yi for all i ∈ +. In fact, we derive the stochastic order relationships among processes that are much more general than the cumulative ones described above. For example, it is not necessarily assumed that the Ai's are independent of the Xi's or that the Bi's are independent of the Yi's. Examples that illustrate the applications of the theory are included.
Preservation of Some Ageing Properties by Order Statistics
Authors: Misra Neeraj , Manoharan M. , Singh Harshinder
Published: July 2009

Let X be a continuous random variable denoting the lifetime of a unit. Let Xk:n denote the kth order statistic based on n independent random observations on X. It has been shown that if Xk:n has decreasing failure rate (DFR) for some k, 1 ≤ k ≤ n, then X is DFR. For n ≥ 2, if Xk:n has increasing failure rate (IFR), then Xk:n–1 is also IFR, and if Xk:n is DFR, then Xk:n+1 is also DFR. The log concavity of the density, function is shown to be preserved by the kth order statistic. It has been established that if the density function of Xk:n is log convex then the density function of Xk:n+1 is also log convex. Because a k-out-of-n system of i.i.d. components each having a life distribution that of X has lifetime Xn-k+1:n the results have applications in the study of such systems.
A Note on Probabilistic Analysis of a Sparse Matrix Factorization Scheme and Random Graphs
Authors: Aldous David
Published: July 2009

Known results in random graph theory lead easily to a quantitative result on the number of multiplications needed in a matrix factorization algorithm, under the assumption that non-zero entries are randomly distributed.
The Compensation Approach Applied to a 2 × 2 Switch
Authors: Boxma O. J. , van Houtum G. J.
Published: July 2009

In this paper we analyze an asymmetric 2 × 2 buffered switch, fed by two independent Bernoulli input streams. We derive the joint equilibrium distribution of the numbers of messages waiting in the two output buffers. This joint distribution is presented explicitly, without the use of generating functions, in the form of a sum of two alternating series of product-form geometric distributions. The method used is the so-called compensation approach, developed by Adan, Wessels, and Zijm.
On the Problem of Establishing the Existence of Stationary Distributions for Continuous-Time Markov Chains
Authors: Pollett P. K. , Taylor P. G.
Published: July 2009

We consider the problem of establishing the existence of stationary distributions for continuous-time Markov chains directly from the transition rates Q. Given an invariant probability distribution m for Q, we show that a necessary and sufficient condition for m to be a stationary distribution for the minimal process is that Q be regular. We provide sufficient conditions for the regularity of Q that are simple to verify in practice, thus allowing one to easily identify stationary distributions for a variety of models. To illustrate our results, we shall consider three classes of multidimensional Markov chains, namely, networks of queues with batch movements, semireversible queues, and partially balanced Markov processes.