Computational results for a stopping rule problem on averages

Suppose x₁, x₂, … are independently distributed random variables with Pr (x_i = 1) = Pr(x_i = ?1) = 1/2, and let s_n =

     

Optimal multicommodity network flows with resource allocation

The problem of determining multicommodity flows over a capacitated network subject to resource constraints may be solved by linear programming; however, the number of potential vectors in most applications is such that the standard arc-chain formulation becomes impractical. This paper describes an approach—an extension of the column generation technique used in the multicommodity network flow problem—that simultaneously considers network chain selection and resource allocation, thus making the problem both manageable and optimal. The flow attained is constrained by resource availability and network capacity. A minimum-cost formulation is described and an extension to permit the substitution of resources is developed. Computational experience with the model is discussed.     

A network isolation algorithm

A set of edges D called an isolation set, is said to isolate a set of nodes R from an undirected network if every chain between the nodes in R contains at least one edge from the set D. Associated with each edge of the network is a positive cost. The isolation problem is concerned with finding an isolation set such that the sum of its edge costs is a minimum. This paper formulates the problem of determining the minimal cost isolation as a 0–1 integer linear programming problem. An algorithm is presented which applies a branch and bound enumerative scheme to a decomposed linear program whose dual subproblems are minimal cost network flow problems. Computational results are given. The problem is also formulated as a special quadratic assignment problem and an algorithm is presented that finds a local optimal solution. This local solution is used for an initial bound.     

A model for manpower productivity during organization growth

A mathematical model is developed that enables organization and manpower planners to quantify the inefficiencies involved in rapid buildups of organizations, such as is frequently found in the aerospace industry shortly after the award of a major contract. Consideration is given to the time required to train, indoctrinate, and familiarize new workers with their jobs and the general program aspects. Once trained, workers are assumed to be productive. If the ratio of untrained to trained workers exceeds a critical value, called the buildup threshold, then the performance of the trained workers is degraded to the extent that they are no longer 100 percent efficient until this ratio returns to a value less than the threshold. The model is sufficiently general to consider an arbitrary manpower plan with more than one peak or valley. The model outputs are functions of real time and consist of the fraction of the total labor force which is productive, the fraction of the total labor units expended for nonproductive effort, the cumulative labor costs for productive effort, and the cumulative labor cost for all effort.     

A proportional defense model

This paper considers the problem of defending a set of point targets of differing values. The defense is proportional in that it forces the offense to pay a price, in terms of reentry vehicles expended, that is proportional to the value of the target. The objective of the defense is to balance its resources so that no matter what attack is launched, the offense will have to pay a price greater than or equal to some fixed value for every unit of damage inflicted. The analysis determines which targets should be defended and determines the optimal firing doctrine for interceptors at defended targets. A numerical example is included showing the relationship between the total target damage and the size of the interceptor force for different values of p, the interceptor single shot kill probability. Some generalizations are discussed.     

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.     

Optimal inspection and repair of renewable coherent systems with independent components and constant failure rates

Suppose that a multicomponent reliability system earns revenue while it is working and that it has a finite number of possible failure states (defined as states in which it ceases to work), each with a known prior probability. When the system stops working its components can be inspected one at a time, and, if necessary, replaced or repaired, until the system is restored to its original (operating) state. Inspections (as well as replacements or repairs) are time consuming and expensive. An optimal adaptive inspection strategy for examining and fixing the components of a failed system restores it as efficiently as possible, taking into account the opportunity costs due to lost revenue while the system remains failed as well as the costs and times required for inspections. This article presents exact and heuristic procedures for constructing optimal adaptive strategies for k-out-of-n and general coherent systems. Average revenue per unit time is taken as the maximand for most of the article, but characterizations of optimality are also obtained for series systems in the case of discounted return over an infinite planning horizon. © 1994 John Wiley & Sons, Inc.     

A sampling procedure and public policy

This paper describes the background of the Office of Management Budget Circular A-21, “Principles for Determining Costs Applicable to Grants, Contracts, and Other Agreements with Educational Institutions,” that describes the requirement for effort reporting. A sampling procedure is proposed as an alternative to 100% reporting.     

The traveling salesman problem: An update of research

During the course of the last few years, attacks on the traveling salesman problem have resulted in a variety of often innovative and rather powerful computational procedures. In this article, we present a review of these results for problems defined on weighted and unweighted graphs. Some account of computational behavior for exact algorithms is provided; however, the primary coverage deals with the strategy of particular procedures. In addition, we include some aspects of nonexact algorithms with major interest confined to the establishment of worst-case bounds.