Determining adjacent vertices on assignment polytopes

To rank the solutions to the assignment problem using an extreme point method, it is necessary to be able to find all extreme points which are adjacent to a given extreme solution. Recent work has shown a procedure for determining adjacent vertices on transportation polytopes using a modification of the Chernikova Algorithm. We present here a procedure for assignment polytopes which is a simplification of the more general procedure for transportation polytopes and which also allows for implicit enumeration of adjacent vertices.     

Optimal replacement of parts having observable correlated stages of deterioration

A single component system is assumed to progress through a finite number of increasingly bad levels of deterioration. The system with level i (0 ≤ i ≤ n) starts in state 0 when new, and is definitely replaced upon reaching the worthless state n. It is assumed that the transition times are directly monitored and the admissible class of strategies allows substitution of a new component only at such transition times. The durations in various deterioration levels are dependent random variables with exponential marginal distributions and a particularly convenient joint distribution. Strategies are chosen to maximize the average rewards per unit time. For some reward functions (with the reward rate depending on the state and the duration in this state) the knowledge of previous state duration provides useful information about the rate of deterioration.     

A queuing process with bilevel hysteretic service-rate control

The purpose of this paper is to analyze the effect of a particular control doctrine applied to the service mechanism of a queuing process. A bilevel hysteretic control based on queue length control levels is employed in an M/M/1 queuing system. Expressions are obtained for queue length probabilities, the first two factorial moments of queue length and two figures of merit for describing control performance under the assumption of statistical equilibrium. Computational examples illustrate the effects on queuing processes subject to this type of control. Several cost formulae are considered for comparison of costs when the queue control doctrine is varied. Situations in which hysteretic control is useful are discussed.     

An application of statistical techniques to estimate engineering man-hours on major aircraft programs

Data on 23 lots of various aircraft programs were gathered. Total engineering man-hours, and information on performance, weight, area, avionics systems, data, and schedule were subjected to least squares analysis. An equation is presented which indicates a relationship between total engineering manhours and a set of seven predictor variables. While the equation derived could only be used with confidence by the manufacturer whose data was analyzed, this article should be looked upon as demonstrating a method of data analysis which others may also find useful, not only for predicting engineering manhours in major aircraft programs, but also in other situations where there is an abundance of possible predictor variables, and the problem is to sort out a meaningful subset of these variables. In order to demonstrate the viability of the formula obtained, comparisons were made with various bid programs.     

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.     

Application of the GLM technique to a production planning problem

Generalized Lagrange Multipliers (GLM) are used to develop an algorithm for a type of multiproduct single period production planning problem which involves discontinuities of the fixed charge variety. Several properties of the GLM technique are developed for this class of problems and from these properties an algorithm is obtained. The problem of resolving the gaps which are exposed by the GLM procedure is considered, and an example involving a quadratic cost function is explored in detail.     

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.