A discounted-cost, continuous-time, infinite-horizon version of a flexible manufacturing and operator scheduling model is solved. The solution procedure is to convexify the discrete operator-assignment constraints to obtain a linear program and then to regain the discreteness and obtain an approximate manufacturing schedule by deconvexification of the solution of the linear program over time. The strong features of the model are the accommodation of linear inequality relations among the manufacturing activities and the discrete manufacturing scheduling, whereas the weak features are intra-period relaxation of inventory availability constraints and the absence of inventory costs, setup times, and setup charges.

Monte Carlo simulation is one alternative for analyzing options markets when the assumptions of simpler analytical models are violated. We introduce techniques for the sensitivity analysis of option pricing, which can be efficiently carried out in the simulation. In particular, using these techniques, a single run of the simulation would often provide not only an estimate of the option value but also estimates of the sensitivities of the option value to various parameters of the model. Both European and American options are considered, starting with simple analytically tractable models to present the idea and proceeding to more complicated examples. We then propose an approach for the pricing of options with early exercise features by incorporating the gradient estimates in an iterative stochastic approximation algorithm. The procedure is illustrated in a simple example estimating the option value of an American call. Numerical results indicate that the additional computational effort required over that required to estimate a European option is relatively small.

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.

We prove Hwang and Yao's conjecture about failure of consecutive-k-out-of-n systems whose components have independent and identically distributed increasing failure rate (IFR) lifetimes, namely, that for each k ≥ 2 there exists nk such that for every n ≥ nk the system does not preserve IFR. For the cases k = 4 and 5, we present complete solutions. We present further conjectures.

In this paper we consider scheduling n tasks on m parallel machines where the task processing times are i.i.d. random variables with a common distribution function F. Scheduling is done by an a priori assignment of tasks to machines. We show that if the distribution function F is a Pólya frequency function of order 2 (decreasing reverse hazard rate) then the assignment that attempts to place an equal number of tasks on each machine achieves the stochastically smallest makespan among all assignments. The condition embraces many important distributions, such as the gamma and truncated normal distributions. Assuming that the task processing times have a common density that is a Pólya frequency function of order 2 (increasing likelihood ratio), then we find that flatter schedules have stochastically smaller makespans in the sense of the “joint” likelihood ratio.

Let (X1, X2) and (Y1, Y2) be bivariate random vectors with a common marginal distribution (X1, X2) is said to be more positively dependent than (Y1, Y2) if E[h(X1)h(X2)] ≥ E[h(Y1)h(Y2)] for all functions h for which the expectations exist. The purpose of this paper is to study the monotonicity of positive dependence with time for a stationary reversible Markov chain [X1]; that is, (Xs, Xl+s) is less positively dependent as t increases. Both discrete and continuous time and both a denumerable set and a subset of the real line for the state space are considered. Some examples are given to show that the assertions established for reversible Markov chains are not true for nonreversible chains.

Open Jackson networks are studied in which departures can be blocked such as due to a breakdown of an output channel. A simple performance estimate is provided along with an explicit error bound.

Finite-state-and-action Markov branching decision chains are studied with bounded endogenous expected population sizes and interest-rate-dependent one-period rewards that are analytic in the interest rate at zero. The existence of a stationary strong-maximum-present-value policy is established. Miller and Veinott's [1969] strong policy-improvement method is generalized to find in finite time a stationary n-present-value optimal policy and, when the one-period rewards are rational in the interest rate, a stationary strong-maximum-present-value policy. This extends previous studies of Blackwell [1962], Miller and Veinott [1969], Veinott [1974], and Rothblum [1974, 1975], in which the one-period rewards are independent of the interest rate, and Denardo [1971] in which semi-Markov decision chains with small interest rates are studied. The problem of finding a stationary n-present-value optimal policy is also formulated as a staircase linear program in which the objective function and right-hand sides, but not the constraint matrix, depend on the interest rate, and solutions for all small enough positive interest rates are sought. The optimal solutions of the primal and dual are polynomials in the reciprocal of the interest rate. A constructive rule is given for finding a stationary n-present-value optimal policy from an optimal solution of the asymptotic linear program. This generalizes the linear programming approaches for finding maximum-reward-rate and maximum-present-value policies for Markov decision chains studied by Manne [1960], d'Epenoux [1960, 1963], Balinski [1961], Derman [1962], Denardo and Fox [1968], Denardo [1970], Derman and Veinott [1972], Veinott [1973], and Hordijk and Kallenberg [1979, 1984].

We study tandem ordering of constant-service stations with unlimited buffers where service at each station adds a certain value to the job. With the goal of minimizing the total expect value of the jobs in the system, we provide conditions under which some particular orderings are optimal and describe a heuristic that finds a near-optimal order for stations of arbitrary service lengths and added values.

The standard regenerative method for estimating steady-state parameters is extended to permit cycles that begin and end in different states. This result is established using the Dynkin martingale and a related solution to Poisson's equation. We compare the variance constant that appears in the associated central limit theorem with that arising from cycles that begin and end in the same state. The standard regenerative method has a smaller variance constant than does the alternative.

We study a globally gated polling system with a dormant server, which makes a halt at its home base when there are no customers present in the system. We derive an explicit expression for the cycle time distribution as well as for the waiting-time distribution at each of the queues. As a justification of the dormant server policy, we show the waiting time at each of the queues to be smaller (in the increasing-convex-ordering sense) than in the ordinary nondormant server case.

For each n ≥ 1, let Πn = (π1, π2, …, πn) be a random permutation of the integers 1,2, …, n. The quantity Bn = Σ measures the degree of oscillation of Πn and is an important measure in the study of sorting algorithms. In this work the asymptotic normality of Bn is derived under the assumption that, for each n ≥ 1, Πn is uniformly distributed over the n! permutations of 1,2, …, n. The proof relies on coupling (π1, π2, …, πn) with a sequence of independent and identically distributed U(0,1) random variables and offers a more probabilistic and computationally simpler alternative to the method of moments proof of Chao, Bai, and Liang (1993, Probability in the Engineering and Informational Sciences 7: 227–235).

In this paper we present a simple method to fit a discrete distribution on the first two moments of a given random variable. With the Fitted distribution we solve approximately Lindley's equation for the D/G/1 queue with discrete service-time distribution using a moment-iteration method. Numerical results show excellent performance of the method.

This work studies sequential assignment match processes, in which random offers arrive sequentially according to a renewal process, and when an offer arrives it must be assigned to one of given waiting candidates or rejected. Each candidate as well as each offer is characterized by an attribute. If the offer is assigned to a candidate that it matches, a reward R is received; if it is assigned to a candidate that it does not match, a reward r ≤ R is received; and if it is rejected, there is no reward. There is an arbitrary discount function, which corresponds to the process terminating after a random lifetime. Using continuoustime dynamic programming, we show that if this lifetime is decreasing in failure rate and candidates have distinct attributes, then the policy that maximizes total expected discounted reward is of a very simple form that is easily determined from the optimal single-candidate policy. If the lifetime is increasing in failure rate, the optimal policy can be recursively determined: a solution algorithm is presented that involves scalar rather than functional equations. The model originated in the study of optimal donor-recipient assignment in live-organ transplants. Some other applications are mentioned as well.

We consider a queueing system where arriving customers join the queue at some random position. This constitutes an impolite arrival discipline because customers do not necessarily go to the end of the line upon arrival. Although mean performance measures like the average waiting time and average number of customers in the queue are the same for all such disciplines, we show that the variance of the waiting time increases as the arrival discipline becomes more impolite, in the sense that a customer is more likely to choose a position closer to the server. For the M/G/1 model, we also provide an iterative procedure for computing the moments of the waiting time distribution. Explicit computational formulas are derived for an interesting special model where a customer joins the queue either at the head or at the end of the line.

It has long been observed that independent laboratories differ in reporting the results of repeated experiments. The problem is to detect those laboratories that might be considered aberrant. Previous analyses have been based on an analysis of variance framework or on subset selection for the detection of aberrant laboratories. The present procedure is also based on an ANOVA model but uses a Bayesian estimate of the number of aberrant laboratories. Subsequent to the determination of the aberrant laboratories, a linear model is used to separate sampling and laboratory effects.

A stochastic scheduling model with linear waiting costs and unknown routing probabilities is considered. Using a Bayesian approach and methods of Bayesian dynamic programming, we investigate the finite-horizon stochastic scheduling problem with incomplete information. In particular, we study an equivalent nonstationary bandit model and show the monotonicity of the total expected reward and of the Gittins index. We derive the monotonicity and well-known structural properties of the (greatest) maximizers, the so-called stay-on-a-winnerproperty and the stopping-property. The monotonicity results are based on a special partial ordering on .

In a job-shop manufacturing environment, consider a model in which the “job” is processed at several stages with random yields. Nondefective items move through the stages to supply a possibly random demand. At each stage there are linear costs of processing and work-in-process inventories and there are convex costs of end-item inventory. Decisions specify the lot sizes that are processed at the various stages. Easy computations specify a simply structured decision rule that minimizes the expected total cost.

We extend a recent strengthening of Azuma's inequality to allow for a non symmetric bound on the martingale differences.

We consider N unreliable machines that are maintained by M repairmen. The time until failure of machine i, and its repair by repairman j, are exponentially distributed random variable with parameters λi, and μj, respectively. All failure times and repair times are independent. Machine i earns ci, per unit time, while it is working. We wish to maximize the expected total discounted reward. It is shown that when the following conditions are satisfied — c1 ≥ … ≥ cN and c1/λ1≥…≥cN/λN, the policy that assigns the fastest repairman to the machine with the lowest index is optimal. Moreover, it is shown that when the second condition is replaced by λ≤ … ≤λN, then this policy maximizes, stochastically, the number of the most reliable machines at every time t.