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.     

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.     

Due-date assignment and early/tardy scheduling on identical parallel machines

This article examines the problem of simultaneously assigning a common due date to a set of independent jobs and scheduling them on identical parallel machines in such a way that the costs associated with the due date and with the earliness or tardiness of the jobs are minimized. We establish that, for certain values of the due-date cost, an optimal schedule for this problem is also optimal for an early/tardy scheduling problem studied by Emmons. We discuss the solution properties for the two problems, and show that both problems are NP-hard even for two machines. We further show that these problems become strongly NP-hard if the number of machines is allowed to be arbitrary. We provide a dynamic programming solution for the problems, the complexity of which indicates that the problems can be solved in pseudopolynomial time as long as the number of machines remains fixed. Finally, we present the results of a limited computational study. © 1994 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.     

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.     

Composite unimodality

This article defines a class of univariate functions termed composite unimodal, and shows how their minimization admits an effective search procedure, albeit one not as efficient as is Fibonacci search for unimodal functions. An approximate Lagrangian approach to an important real-world logistics problem is seen to yield a surrogate problem whose objective function is composite unimodal. The mathematical form of this objective function is likely to be encountered in solving future real-world problems. © 1993 John Wiley & Sons, Inc.