Parallel machine replacement

We consider the parallel replacement problem in which there are both fixed and variable costs associated with replacing machines. Increasing maintenance costs motivate replacements, and the fixed replacement cost provides incentive for replacing machines of different ages together in “clusters.” We prove two intuitive results for this problem. First, it is never optimal to split a cluster of like-aged machines, and second, it is never optimal to replace newer clusters before older clusters. By incorporating these two results into an algorithmic approach, we vastly reduce the amount of computation required to identify an optimal replacement policy.     

Estimating a survival curve when new is better than used in expectation

Let X be a positive random variable. The distribution F of X is said to be “new better than used in expectation,” or “NBUE,” if E(X) ⩾ E(X – t|X > t) for all t ⩾ 0. Suppose X₁, …, X_n, is a random sample from an NBUE distribution F. The problem of estimating F by a distribution which is itself NBUE is considered. The estimator G_n, defined as the NBUE distribution supported on the sample which minimizes the (sup norm) distance between the NBUE class and the empirical distribution function, is studied. The strong uniform consistency of G_n, is proven, and a numerical algorithm for obtaining G_n, is given. Our approach is applied to provide an estimate of the distribution of lifetime following the diagnosis of chronic granulocytic leukemia based on data from a National Cancer Institute study.     

A one-dimensional helicopter-submarine game

The article considers a two-person zero-sum game in which a searcher with b bombs wishes to destroy a mobile hider. The players are restricted to move on a straight line with maximum speeds v and u satisfying v > u > 0; neither player can see the other but each knows the other's initial position. The bombs all have destructive radius R and there is a time lag T between the release of a bomb and the bomb exploding. The searcher gets 1 unit if the hider is destroyed and 0 if he survives. A solution is given for b = 1, and extended to b > 1 when the time lag is small. Various applications of the game are discussed.     

The shortest queue model with jockeying

In this article we deal with the shortest queue model with jockeying. We assume that the arrivals are Poisson, each of the exponential servers has his own queue, and jockeying among the queues is permitted. Explicit solutions of the equilibrium probabilities, the expected customers, and the expected waiting time of a customer in the system are given, which only depend on the traffic intensity. Numerical results can be easily obtained from our solutions. Several examples are provided in the article.     

A fast infiltration game on n arcs

Starting from a safe base, an Infiltrator tries to reach a sensitive zone within a given time limit without being detected by a Guard. The Infiltrator can move with speed at most u, while the Guard can only perform a restricted number of searches. A discrete variant of this zero-sum game played on a graph consisting of two vertices joined by n nonintersecting arcs is investigated. Optimal strategies and an explicit expression for its value are obtained. © 1996 John Wiley & Sons, Inc.     

On the set of (perfect) equilibria of a bimatrix game

This article provides a new approach to the set of (perfect) equilibria. With the help of an equivalence relation on the strategy space of each player. Nash sets and Selten sets are introduced. The number of these sets is finite and each of these sets is a polytope. As a consequence the set of (perfect) equilibria is a finite union of polytopes. © 1994 John Wiley & Sons. Inc.     

Printed circuit board family grouping and component allocation for a multimachine,open-shop assembly cell

This article considers a particular printed circuit board (PCB) assembly system employing surface mount technology. Multiple, identical automatic placement machines, a variety of board types, and a large number of component types characterize the environment studied. The problem addressed is that of minimizing the makespan for assembling a batch of boards with a secondary objective of reducing the mean flow time. The approach adopted is that of grouping boards into production families, allocating component types to placement machines for each family, dividing of families into board groups with similar processing times, and the scheduling of groups. A complete setup is incurred only when changing over between board families. For the environment studied, precedence constraints on the order of component placement do not exist, and placement times are independent of feeder location. Heuristic solution procedures are proposed to create board subfamilies (groups) for which the component mounting times are nearly identical within a subfamily. Assignment of the same component type to multiple machines is avoided. The procedures use results from the theory of open-shop scheduling and parallel processor scheduling to sequence boards on machines. Note that we do not impose an open-shop environment but rather model the problem in the context of an open shop, because the order of component mountings is immaterial. Three procedures are proposed for allocating components to machines and subsequently scheduling boards on the machines. The first two procedures assign components to machines to balance total work load. For scheduling purposes, the first method groups boards into subfamilies to adhere to the assumptions of the open-shop model, and the second procedure assumes that each board is a subfamily and these are scheduled in order of shortest total processing time. The third procedure starts by forming board subfamilies based on total component similarity and then assigns components to validate the open-shop model. We compare the performance of the three procedures using estimated daily, two-day, and weekly production requirements by averaging quarterly production data for an actual cell consisting of five decoupled machines. © 1994 John Wiley & Sons, Inc.     

On the design of a tandem queue with blocking: Modeling,analysis, and gradient estimation

We demonstrate here how recent advances in the study of discrete-event stochastic systems provide fruitful results for the modeling, analysis, and design of manufacturing systems. We consider a multistage make-to-stock system where outputs from the final stage are used to satisfy customer demands. We address the problem of finding the appropriate trade-off between reduced order waiting time and increased process speeds. Using the idea of infinitesimal perturbation analysis (IPA), we establish a simple procedure where sample-path derivatives can be obtained along an arbitrary sample path. Under suitable conditions, we demonstrate that these derivative estimators are unbiased and strongly consistent and can be used in a classical stochastic optimization scheme to solve the problem. The role of continuity and convexity on the validity of the estimator is also addressed. Although the focus of this article is not to solve for the optimal solution, we provide a theoretical justification for such a pursuit. The approach is appealing as it is numerically stable, easy to implement, and can be extended to other system performance measures. © 1994 John Wiley & Sons, Inc.     

Minimax resource allocation problems with ordering constraints

Resource allocation problems consider the allocation of limited resources among numerous competing activities. We address an allocation problem with multiple knapsack resource constraints. The activities are grouped into disjoint sets. Ordering constraints are imposed on the activities within each set, so that the level of one activity cannot exceed the level of another activity in the same set. The objective function is of the minimax type and each performance function is a nonlinear, strictly decreasing and continuous function of a single variable. Applications for such resource allocation problems are found, for example, in high-tech industries confronted with large-scale and complex production planning problems. We present two algorithms to solve the allocation problem with ordering constraints. The first one uses characterization of the optimal decision variables to apply a search method. The second algorithm solves a sequence of problems, each in the format of the original problem without ordering constraints. Whereas the computational effort of the first algorithm depends on the desired degree of accuracy even for linear performance functions, the effort of the latter algorithm is polynomial for certain classes of performance functions. © 1994 John Wiley & Sons, Inc.     

A parametric-based heuristic program for the quadratic assignment problem

In this article we study the quadratic assignment problem by embedding the actual data in a data space which satisfies an extension of the metric triangle property. This leads to simpler computations for the determination of heuristic solutions. Bounds are given for the loss of optimality which such heuristic solutions would involve in any specific instance. © 1993 John Wiley & Sons, Inc.