This article presents a novel approach for the dynamic control of a signalized intersection. At the intersection, there is a number of arrival flows of cars, each having a single queue (lane). The set of all flows is partitioned into disjoint combinations of nonconflicting flows that will receive green together. The dynamic control of the traffic lights is based on the numbers of cars waiting in the queues. The problem concerning when to switch (and which combination to serve next) is modeled as a Markovian decision process in discrete time. For large intersections (i.e., intersections with a large number of flows), the number of states becomes tremendously large, prohibiting straightforward optimization using value iteration or policy iteration. Starting from an optimal (or nearly optimal) fixed-cycle strategy, a one-step policy improvement is proposed that is easy to compute and is shown to give a close to optimal strategy for the dynamic problem.

The blood bank system is a typical example of a perishable inventory system. The commodity arrival and customer demand processes are stochastic. However, the stored items have a constant lifetime. In this study, we introduce a diffusion approximation to this system. The stock level is represented by the amount of items arriving during the age of the oldest item; it is assumed to fluctuate as an alternating two-sided regulated Brownian motion between barriers 0 and 1. Hittings of level 0 are outdatings and hittings of level 1 are unsatisfied demands. Also, there are two predetermined switchover levels, a and b, with 0 ≤ a < b ≤ 1. Whenever the stock level process upcrosses level b, the controller generates a switch in the drift from γ = γ0 to γ = γ1, while downcrossings of level a generate switches from γ1 to γ0. A useful martingale is introduced for analyzing the stationary law of the controlled process as well as the total expected discounted cost.

We study a stochastic scheduling problem with a single machine subject to random breakdowns. We address the preemptive-repeat model; that is, if a breakdown occurs during the processing of a job, the work done on this job is completely lost and the job has to be processed from the beginning when the machine resumes its work. The objective is to complete all jobs so that the the expected weighted flow time is minimized. Limited results have been published in the literature on this problem, all with the assumption that the machine uptimes are exponentially distributed. This article generalizes the study to allow that (1) the uptimes and downtimes of the machine follow general probability distributions, (2) the breakdown patterns of the machine may be affected by the job being processed and are thus job dependent; (3) the processing times of the jobs are random variables following arbitrary distributions, and (4) after a breakdown, the processing time of a job may either remain a same but unknown amount, or be resampled according to its probability distribution. We derive the necessary and sufficient condition that ensures the problem with the flow-time criterion to be well posed under the preemptive-repeat breakdown model. We then develop an index policy that is optimal for the problem. Several important situations are further considered and their optimal solutions are obtained.

In this article, we study a method to compare queueing systems and their fluid limits. For a certain class of queueing systems, it is shown that the expected workload (and certain functions of the workload) is higher in the queueing system than in the fluid approximation. This class is characterized by convexity of the value function in the state component(s) where external arrivals occur. The main example that we consider is a tandem of multiserver queues with general service times and Markov-modulated arrivals. The analysis is based on dynamic programming and the use of phase-type distributions. Numerical examples to illustrate the results are also given.

Sequential order statistics describe the ordered failure times in a k-out-of-n system, where the failures of components might affect the performance of remaining working components. In this article aging properties of sequential order statistics are examined and conditions are given such that the distribution of a sequential order statistic is ILR, IFR, IFRA, or NBU. Moreover, conditions for aging properties of spacings of sequential order statistics are obtained.

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.

We consider a two-queue model with state-dependent setups, in which a single server alternately serves the two queues. The high-priority queue is served exhaustively, whereas the low-priority queue is served according to the k-limited strategy. A setup at a queue is incurred only if there are customers waiting at the polled queue. We obtain the transforms of the queue length and sojourn time distributions under the assumption of Poisson arrivals, generally distributed service times, and generally distributed setup times. The interest for this model is fueled by an application in the field of logistics. It is shown how the results of this analysis can be applied in the evaluation of a stochastic two-item single-capacity production system. From these results we can conclude that significant cost reductions are possible by bounding the production runs of the low-priority item, which indicates the potential of the k-limited service discipline as priority rule in production environments.

We study systems of parallel queues with finite buffers, a single server with random connectivity to each queue, and arriving job flows with random or class-dependent accessibility to the queues. Only currently connected queues may receive (preemptive) service at any given time, whereas an arriving job can only join one of its accessible queues. Using the coupling method, we study three key models, progressively building from simpler to more complicated structures.

In the first model, there are only random server connectivities. It is shown that allocating the server to the Connected queue with the Fewest Empty Spaces (C-FES) stochastically minimizes the number of lost jobs due to buffer overflows, under conditions of independence and symmetry.

In the second model, we additionally consider random accessibility of queues by arriving jobs. It is shown that allocating the server to the C-FES and routing each arriving job to the currently Accessible queue with the Most Empty Spaces (C-FES/A-MES) minimizes the loss flow stochastically, under similar assumptions.

In the third model (addressing a target application), we consider multiple classes of arriving job flows, each allowed access to a deterministic subset of the queues. Under analogous assumptions, it is again shown that the C-FES/A-MES policy minimizes the loss flow stochastically.

The random connectivity/accessibility aspect enhances significantly the structure and application scope of the classical parallel queuing model. On the other hand, it introduces essential additional dynamics and considerable complications. It is interesting that a simple policy like FES/MES, known to be optimal for the classical model, extends to the C-FES/A-MES in our case.

We investigate the dependence induced among multiple Markov chains when they are simulated in parallel using a shared Poisson stream of potential event occurrences. One expects this dependence to facilitate comparisons among systems; our results support this intuition. We give conditions on the transition structure of the individual chains implying that the coupled process is an associated Markov chain. Association implies that variance is reduced in comparing increasing functions of the chains, relative to independent simulations, through a routine argument. We also give an apparently new application of association to the problem of selecting the better of two systems from limited data. Under conditions, the probability of incorrect selection is asymptotically smaller when the systems compared are associated than when they are independent. This suggests a further advantage to linking multiple systems through parallel simulation.

The probabilistic distance clustering method of works well if the cluster sizes are approximately equal. We modify that method to deal with clusters of arbitrary size and for problems where the cluster sizes are themselves unknowns that need to be estimated. In the latter case, our method is a viable alternative to the expectation-maximization (EM) method.

This paper describes a highly efficient Monte Carlo sampling plan for evaluating the probability that the flow value in a stochastic flow network is greater than or equal to a prespecified level d. A stochastic flow network can characterize communication, transportation, and water or oil distribution systems. The paper first derives lower and upper bounds on the probability of interest and then describes how one can concentrate sampling in a specialized region of the arc capacity state space to increase the statistical efficiency of the resulting estimate. The paper also gives expressions for worst-case sample sizes needed to meet specified bounds on variances and coefficients of variation and illustrates the proposed sampling plan with an example.

We consider a memoryless loss system with servers = {1, …, J}, and with customer types = {1, …, I}. Servers are multi-type: server j works at rate μj, and can serve a subset of customer types C(j). An arriving customer will go to the longest idling server which can serve him, or be lost. We obtain a simple explicit steady-state distribution for this system, and calculate various performance measures of this system in steady state. We provide some illustrative examples. We compare this system with a similar system discussed recently by Adan, Hurkens, and Weiss [1]. We also show that this system is insensitive, the results hold also for general service time distributions.

This paper focuses on an infinite-server queue modulated by an independently evolving finite-state Markovian background process, with transition rate matrix Q≡(qij)i,j=1d. Both arrival rates and service rates are depending on the state of the background process. The main contribution concerns the derivation of central limit theorems (CLTs) for the number of customers in the system at time t≥0, in the asymptotic regime in which the arrival rates λi are scaled by a factor N, and the transition rates qij by a factor Nα, with α∈ℝ+. The specific value of α has a crucial impact on the result: (i) for α>1 the system essentially behaves as an M/M/∞ queue, and in the CLT the centered process has to be normalized by √N; (ii) for α<1, the centered process has to be normalized by N1−α/2, with the deviation matrix appearing in the expression for the variance.

Some class properties of the used better (worse) than aged [UBA (UWA)] and the used better (worse) than aged in expectation [UBAE (UWAE)] classes of lifetime distributions are considered. Relationships with the decreasing (increasing) mean residual lifetime [DMRL (IMRL)] class and the decreasing (increasing) variance residual lifetime [DVRL (IVRL)] class are established. Discrete UBA and UWA distributions are introduced and studied. Characterizations of UBA and UWA distributions are derived by using discrete aging properties of mixed Poisson distributions. Applications of these results to queueing theory and ruin are then considered. In particular, preservation of UBA (UWA) and UBAE (UWAE) under a transform of life distributions is given.

Server farms, consisting of a collection of hosts and a front-end router that dispatches incoming jobs to hosts, are now commonplace. It is well known that when job service requirements (job sizes) are highly variable, then the Size-Interval task assignment policy is an excellent rule for assigning jobs to hosts, since it provides isolation for short jobs by directing short jobs to one host's queue and long jobs to another host's queue. What is not understood is how to classify a “short” job versus a “long” job. For a long time it was believed that the size cutoff separating “short” jobs from “long” ones should be chosen to balance the load at the hosts in the server farm. However, recent literature has provided empirical evidence that load balancing is not always optimal for minimizing mean response time. This article provides the first analytical criteria for when it is preferable to unbalance load between two hosts using Size-Interval task assignment and in which direction the load should be unbalanced. Some very simple sufficient criteria are provided under which we prove that the short job host should be underloaded, and likewise for the long job host. These criteria are then used to prove that the direction of load imbalance depends on moment index properties related to the job size distribution. For example, under the Bounded Pareto (BP) job size distribution with parameter α and a sufficiently high upper bound (the BP is well known to be a good model of empirical computer system workloads), we show that α determines the direction of load imbalance. For α<1, the short job host should be underloaded; for α=1, load should be balanced; and for α>1, the long job host should be underloaded. Many other job size distributions are considered as well. We end by showing that load unbalancing can have a dramatic impact on performance, reducing mean response time by an order of magnitude compared to load balancing in many common cases.

Results and conditions which quantify the decrease in dependence with lag for a stationary Markov process and enable one to compare the dependence for two stationary Markov processes are obtained. The notions of dependence used in this article are the supermodular ordering and the concordance ordering. Both discrete-time and continuous-time Markov processes are considered. Some applications of the main results are given. In queueing theory, the monotonicity results of the waiting time of the nth customer as well as the stationary waiting time in an MR/GI/1 queue and the stationary workload in a Markov-modulated queue are established, thus strengthening previous results while simplifying their derivation. This article is a continuation of those by Fang et al. [7] and Hu and Joe [10].

We consider a multiserver delay queue with finite additional waiting spaces and time-varying arrival rates, where the customers waiting in the buffer may abandon. These are features that arise naturally from the study of service systems such as call centers. Moreover, we assume rewards for successful service completions and cost rates for service resources. Finally, we consider service-level agreements that constrain both the fractions of callers who abandon and the ones who are blocked.

Applying the theory of Lagrangian mechanics to the fluid limit of a related Markovian service network model, we obtain near-profit-optimal staffing and provisioning schedules. The nature of this solution consists of three modes of operation. A key step in deriving this solution is combining the modified offered load approximation for loss systems with our fluid model. We use them to estimate effectively both our service-level agreement metrics and the profit for the original queuing model. Second-order profit improvements are achieved through a modified offered load version of the conventional square root safety rule.

In this paper, we present a pricing model for vulnerable options in discrete time. A Generalized Autoregressive Conditional Heteroscedasticity process is used to describe the variance of the underlying asset, which is correlated with the returns of the asset. As for counterparty default risk, we study it in a reduced form model and the proposed model allows for the correlation between the intensity of default and the variance of the underlying asset. In this framework, we derive a closed-form solution for vulnerable options and investigate quantitative impacts of counterparty default risk on option prices.

This paper examines the availability of an inspected system where the rate of deterioration is governed by an exogenous random environment. We develop a qualitative result that exposes the relationship among remaining life, deterioration, and repairs. This result requires no specific distributional assumptions. We use this result in developing a simple bound on stationary availability. We investigate these relationships numerically for a Markovian system and provide insights useful to practitioners in selecting an inspection process that guarantees a target availability.

The purpose of this work is to construct a bridge between two classical topics in applied probability: the finite-time ruin probability in insurance and the final outcome distribution in epidemics. The two risk problems are reformulated in terms of the joint right-tail and left-tail distributions of order statistics for a sample of uniforms. This allows us to show that the hidden algebraic structures are of polynomial type, namely Appell in insurance and Abel–Gontcharoff in epidemics. These polynomials are defined with random parameters, which makes their mathematical study interesting in itself.