Search

This note presents some comments on BONDER'S paper on the Lanchester attrition-rate coefficient, which indicate that a valid prediction of average attrition is obtained by using the harmonic mean of the variable attrition rates rather than the arithmetic mean. This change results in a constant Lanchester attrition-rate coefficient being defined as the reciprocal of the expected time to kill a target. An alternate and more general method for obtaining the constant coefficient is presented and some comparative results are displayed. An appendix indicates the conditions for which it is appropriate to use the harmonic and arithmetic means of rates in general. [ABSTRACT FROM AUTHOR]

Some discrepancies in an earlier paper describing a bulk service queuing situation with customer balking or reneging are pointed out. Necessary modifications to make the model more valid are incorporated in a reformulation and an approach for developing the state-time probabilities of the system is suggested. [ABSTRACT FROM AUTHOR]

The article presents the report of the president of the Operations Research Society of America (ORSA) in the U.S. to the membership. He outlines the problems and activities of the society including the amendment to eliminate associate membership, affiliation with the division of mathematics of the national research council, commemorative plaque for the Lanchester prize, consideration of employment of full-time staff member, quality of presentations at ORSA meetings, plans for an international conference on operations research and management sciences and participation in management of the society by members from industry.

This paper considers the case of a product consisting of several components, each of which is batch manufactured. It assumes that the product demands occur singly, and that the components are manufactured in equal-batch quantities in a reorder level-batch quantity system. The paper is concerned with the optimal phasing of the components in order to minimize the variance of holding cost for the product. It shows that the optimal policy is independent of the order of sequencing of the components and is given when the phase lag between consecutive components in the cycle is equal to [(Ai+Aj)/∑all i Ai. (q/2), where Ai, Aj are the unit values of the components, and q is the batch quantity. A specific example is included to illustrate the three-component case and the discrete practical solution for any number of components is indicated. [ABSTRACT FROM AUTHOR]

Assignment problems arise whenever elements of a finite set have to be paired with elements of another finite set in such a way as to maximize a certain function of the pairing. In this paper three different formulations of such a problem are given. They are analyzed and a method for obtaining a low-cost solution is developed. [ABSTRACT FROM AUTHOR]

This paper contains a brief résumé of a mathematical foundation for construction and analysis of accelerated life tests The effects, on distribution of time to failure, of several special methods of accelerating life are studied A special type of accelerated life test for capacitors is examined in detail Three methods for estimating the parameter of the original distribution, from data gathered from the accelerated tests, are indicated if the original distribution is negative exponential [ABSTRACT FROM AUTHOR]

This paper applies residual analysis to build up improved forecasts from exponential smoothing models. The resulting model is not unknown, but the method of achieving it is more straightforward and intuitive than existing methods. The paper also shows that the model is identical to IMA(k, k) forecasting models. [ABSTRACT FROM AUTHOR]

This paper develops solutions to extensions of F. W. LANCHESTER'S classical equations of 'modern warfare' (frequently referred to as aimed-fire equations) for combat between two homogeneous forces. In these extensions the lethality of the fire (as expressed by the Lanchester attrition-rate coefficient) depends on time. When the dependence is arbitrary, the solution is an infinite series of recursively related integrals; in special cases, more convenient representations (including representation in terms of tabulated functions) are available. Solutions are obtained in the following cases: (1) the lethality of each side's fire proportional to a power of time and both lethalities initially zero, and (2) the lethality of each side's fire linear with time, but only one side's lethality initially zero. The latter case models the constant-speed approach between forces whose weapons have different maximum effective ranges. [ABSTRACT FROM AUTHOR]

This paper presents an approach, similar to penalty functions, for solving arbitrary mathematical programs. The surrogate mathematical program is a lesser constrained problem that, in some cases, may be solved with dynamic programming. The paper deals with the theoretical development of this surrogate approach. [ABSTRACT FROM AUTHOR]

This paper introduces a generalization of the frequently discussed problem of finding the optimum redundancy that maximizes the reliability of a network of components. Past work has restricted consideration to arrangements of redundant components called series-parallel networks. This paper allows a much broader class of arrangements called series-parallelseries networks. It is important to consider such arrangements for realistic situations in which components have more than one failure mode, or the combination of parallel paths introduces a failure probability. A dynamic programming algorithm is used to solve the more general problem for the case in which there are no constraints on the optimum solution. The algorithm is extended to handle multiple constraints using dominance and a variety of elimination methods to reduce the storage required in a compurer implementation of the algorithm. Problems with as many as 15 serial components and three constraints have been solved with reasonable digital computer computation times. [ABSTRACT FROM AUTHOR]

This paper gives general conditions for the convergence of a class of cutting-plane algorithms without requiring that the constraint sets for the subproblems be sequentially nested. Conditions are given under which inactive constraints may be dropped after each subproblem. Procedures for generating cutting-planes include those of KELLEY, CHENEY AND GOLDSTEIN, and a generalization of the one used by both ZOUTENDIJK and VEXNoTT. For algorithms with nested constraint sets, these conditions reduce to a special case of those of ZANGWILL for such problems and include as special cases the algorithms of Kelley, Cheney and Goldstein, and Veinott. Finally, the paper gives an arithmetic convergence rate. [ABSTRACT FROM AUTHOR]

A simple extension of the Lagrange optimization method is valuable in allocating defense resources among a large number of independent defense locations. This kind of allocation problem is complicated by the fact that the attacker can optimize his attack against whatever defense is chosen. This paper describes an extended or double Lagrange method, which provides strictly optimal allocations for the attacker, but not necessarily for the defender. Nevertheless, by careful use of the method, it is possible to obtain defense allocations that are at least approximately optimum. The major part of the paper provides a technique for verifying results and computing bounds for the error—a technique that is necessary because the uncritical application of the method can occasionally give results that are far from optimum. [ABSTRACT FROM AUTHOR]

For solving the flow-shop scheduling problem, this paper examines elimination techniques that reduce the set of solutions to a subset that must contain the optimal solution being sought. The paper shows (1) that the elimination method of SZWAKC [Naval Res. Log. Quart. 18, 295–305(1971)] removes at least as many solutions as any other method, and is therefore optimal, and (2) how to construct a general counterexample to any procedure that removes more sequences than this optimal method. [ABSTRACT FROM AUTHOR]

This paper describes and discusses some search problems, starting with the case of no false contacts, to provide a foundation for developing a search theory in the presence of false contacts. Important properties of the search plan are defined and illustrated by examples. After a general description of false-contact generators and alternative actions that may be used when contacts are made, the problem is formulated for the case in which false contacts are generated by real stationary objects that are investigated when contacted. It is shown that the formulation and solution of the standard optimization functionals are contingent on the number of false targets found, in general, and possibly on the locations and times of contact as well. The optimization functional is difficult to write and more difficult to solve. The formulation is made for the expected-time functional when the number of false targets is bounded. Finally, the paper outlines a procedure for ending the solution and illustrates it with an example. [ABSTRACT FROM AUTHOR]

This paper considers an n-phase generalization of the typical M/M/1 queuing model, where the queuing-type birth-and-death process is defined on a continuous-time n-state Markov chain. It shows that many models analyzed in the literature can be considered special cases of this framework. The paper focuses on the steady-state regime, and observes that, in general, closed-form results for the limiting probabilities are circuit to obtain, if at all possible. Hence, numerical methods should be employed. For an interesting special case, explicit results are obtained that are analagous to the classical solutions for the simple M/M/1 queue. [ABSTRACT FROM AUTHOR]

This paper treats the problem of project (or machine) scheduling with resource constraints to achieve minimum total duration time as a disjunctive graph. The prospective advantage of this approach is the elimination of the need to consider individual time periods over the program horizon; a feasibility check determines whether the resource constraints can be met by any particular network representation of the project. The paper gives an algorithm that uses partial enumeration for what is essentially a mixed integer program. The algorithm employs a maximum-flow computation as a check for feasibility with respect to available resources. [ABSTRACT FROM AUTHOR]

This paper uses a first-order autoregressive scheme to investigate the effects of initial conditions in a simulation on the estimation of the population mean of a process of interest. The effects are measured by bias and variance. The results show that the elimination of observations near the beginning of the simulation reduces bias, as intended, but increases the variance, sometimes significantly. [ABSTRACT FROM AUTHOR]

This paper considers the problem of optimal search for a stationary target when the detection capability of the search sensor, as characterized by its sweep width, is fixed but not known in advance. Most of the results are confined to the assumption of a gamma prior sweep-width distribution and to the cases of normal and uniform prior target-location distributions. Explicit formulas are obtained for the optimal search plans, the probability of detection versus time, the expected time to detection, and the posterior marginal distributions for target location and sweep width. In the case of a normal prior target-location distribution, expected time to detection is compared for the optimal plan and search plans based on the assumption of a known value for sweep width; this includes a sensitivity analysis treating actual sweep width as a parameter. For a target of value, the search plan that maximizes expected net return is determined. This plan requires specification of a rule for terminating an unsuccessful search. Explicit results are given assuming a nonincreasing target value and a nondecreasing search-cost rate. [ABSTRACT FROM AUTHOR]

A mathematical programming problem P: minimize z=d[supT]x+e[supT]u+f[supT]v subject to Ax+Bu+Cv≥g, x, u, v≥0, u[supT]v=0, is called a complementary programming (CP) problem. The condition u[supT]v=0 distinguishes CP problems from ordinary LP problems. A variety of nonlinear programming problems can be formulated in this form, including absolute-value programming problems, 0-1 mixed-integer-programming problems, quadratic-programming problems, and so forth. This paper proposes a branch-and-bound algorithm for CP problems and reports some computational results. [ABSTRACT FROM AUTHOR]

Stochastic systems with multiple inputs are common in practice. This paper investigates such a system with random and scheduled inputs, and determines the equilibrium behavior of the basic process (a waiting-time process if the system is a queue, or a storage process if it is a storage system) by reducing the problem to the solution of an integral equation, which is solved by the method of factorization. [ABSTRACT FROM AUTHOR]

This paper derives explicit solutions for a class of linear (inequality) economic models heretofore treated by linear programming. These solutions are quite elementary and the decision criteria given are easily interpreted. The explicit solutions may involve the inversion of a single matrix, but even this is not necessary for the three applications in capital budgeting, production planning, and input-output analysis given in the paper. [ABSTRACT FROM AUTHOR]

This paper analyzes the problem of air interdiction in a simplified 'hostile country' in which the flow of interdicted material is entirely unidirectional. The action is assumed to be constrained by a minimum tour-survival probability. Results are presented that permit the existence of feasible solutions of the constrained problem to be determined, that solve the problem completely in the unconstrained case, and that enable optimal solutions to be determined in the constrained case (but only when the probability-of-loss function p(x) is a step function). [ABSTRACT FROM AUTHOR]

This paper analyzes priority rules that are mixtures of preemption and postponable rules. Whether a preemption occurs is made to depend on some factor in addition to priority class; dependence on the completed portion of service (age) of the lower-priority customer in service and the number of prior preemptions of the lower-priority customer in service are each considered. The stochastic model (without priorities) is that of the M/G/1 queue. The paper obtains first-moment expressions (e.g., expected number of customers in the system) in the steady-state case for each priority class as a function of the particular factor being considered. It then introduces a linear cost model that is a function of expected waiting time and expected number of preemptions, and formulates the problem of finding an optimal rule from each class by considering a parametric class of rules determined by each factor. In each case, conditions are sought for the global optimality of a rule over a class of rules, but results are obtained only after restrictions (e.g., monotone failure rates) on service distributions are imposed. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to present an algorithm for solving the quadratic binary programming problem. Although a problem with this structure may arise in many situations, it is particularly common in capital budgeting when a decision-maker is confronted with a set of investment proposals from which he must select a portfolio. If returns of proposals are intercorrelated random variables and if the decision-maker uses as his criterion for selection the mean μ and variance σ[sups] of portfolio returns, his decision requires prior identification of the (μ, σ²) efficient set. The algorithm developed to solve the problem and hence necessary to generate the efficient set is based on the concept of implicit enumeration recently introduced by EGON BALAS for solution of the binary linear programming problem. [ABSTRACT FROM AUTHOR]

A certain class of integer programming problems, called asymptotic or steady-state, has been shown by GOMORY to be cost equivalent to a group-optimization problem. This paper extends the algebraic characterization by demonstrating that there are cost-equivalent group problems for all integer programming problems. Finally, the result is interpreted from the viewpoint of dynamic programming, and this provides the turnpike theorem. [ABSTRACT FROM AUTHOR]

This paper presents a mathematical study of a time-sharing system with a single server and many queues. In each queue a customer receives one quantum of service and is then sent to the end of the next queue, provided his service demand has not been completely satisfied. When a quantum of service is completed, the server attends to the first customer in the lowest index nonempty queue. The discipline of the highest indexed queue is 'round-robin,' while all other queues obey the FIFO rule. Newly arrived customers join the end of the first queue. The paper derives mathematical expressions for the main performance measures and illustrates them by graphical means. [ABSTRACT FROM AUTHOR]

In this paper, exact, recursive, and asymptotic formulas' are derived for a queuing system in which access to the servers takes place at regular intervals. Steady-state results, already known, are extended and utilized to construct delay distributions that are adaptable to computer work. [ABSTRACT FROM AUTHOR]

This paper considers a two-sided war game in which one side (the defender) must first deploy its defenses, consisting of both a passive defense (shelters), and an active defense (anti-missile missiles); the other side (the attacker) then decides how to aim its missiles. The defender is constrained by budget limitations, while the attacker is constrained by the number of missiles available. The payoff is in term of fatalities. The paper uses a convex duality theorem to change the min-max problem to a pure minimization problem, and obtains a solution that obeys the no-soft-spot rule. An example shows the effects of attack and budget sizes, as well as of the costs of ABM defense. [ABSTRACT FROM AUTHOR]

This paper shows that the Lagrange multiplier method suggested by H. Everett does not have 'Fail-Safe' properties when applied to simple situations with nonconvexity only in the functional. Although each Lagrange multiplier problem for these situations has immediate solutions no means of combining them to obtain a solution to any reasonable approximation appears to be visible. [ABSTRACT FROM AUTHOR]

Traditionally the probability of killing a point target is analyzed by means of employing a lethal circle (in two dimensions) or a lethal sphere (in three dimensions). The concept of a lethal circle or sphere is based on the assumption of a `kill-no kill' situation in which a target anywhere within the circle (sphere) is killed and a target anywhere outside of the lethal region is not killed. Another aspect of the `kill-no kill' approach is that it combines all lethal effects (heat, shock, x-rays, etc.) in one parameter-the radius R of the lethal circle (sphere). In many problems of weapon systems effectiveness this approach is extremely useful, but in other areas the attendant assumptions are unrealistic and the purpose of this paper is to present a useful alternative methodology. All of the formulas derived are amenable to desk-calculator computation. [ABSTRACT FROM AUTHOR]

In earlier papers [Opns. Res. 9, 849-859 (1961), and 11, 863-888 (1963)] the one-dimensional cutting stock problem was discussed as a linear programming problem. There it was shown how the difficulty of the enormous number of columns occurring in the linear programming formulation could be overcome by solving a knapsack problem at every pivot step. In this paper higher dimensional cutting stock problems are discussed as linear programming problems. The corresponding difficulty of the number of columns cannot in general be overcome for there is no efficient method for solving the generalized knapsack problem of the higher dimensional problem. However a wide class of cutting stock problems of industry have restrictions that permit their generalized knapsack problem to be efficiently solved. All of the cutting stock problems that yield to this treatment are ones in which the cutting is done in stages. In treating these practical cutting problems, one often encounters additional conditions that affect the solution. An example of this occurs in the cutting of corrugated boxes, which involves an auxiliary sequencing problem. This problem is discussed in some detail, and a solution described for the sequencing problem under given simplifying assumptions. [ABSTRACT FROM AUTHOR]

In this paper, treating time as a discrete variable, we study the transient behavior of a bulk-service queuing system in which the number of customers arriving within a fixed time interval follows a binomial probability distribution. The service times are assumed to be identically distributed and statistically independent. The busy period and queue length distributions have been obtained in terms of probability generating functions. [ABSTRACT FROM AUTHOR]

The paper considers two-person zero-sum game. Let B be an arbitrary positive real number and let &b.Theta; be a real number between zero and one. First player chooses a number, t1, with t1 ranging between 0 to B+1. Second player chooses a number, t2, with t2 ranging between 0 to B. The pay-off function, &b.Theta, which specifies the amount the first player receives from second player, is given in the article. If &b.Theta; were continuous, it would be known that these two numbers are equal and hence the game would have a well-determined value. However, the pay-off function considered here is not continuous and this standard theorem cannot be applied. It should be clear that the optimal strategies for first player and second player are not unique.

This paper shows that seemingly different 'adjustment' procedures are equivalent, if viewed in appropriate coordinate systems. It extends previous results concerning sequential adjustments that are constrained to be linear functions of observed impact points to the class of translation-invariant procedures. It also reviews properties of the optimal sequential adjustment procedure, including some related to stochastic approximation. [ABSTRACT FROM AUTHOR]

In this paper the theorem of the alternative is used to show the equivalence between transitive majority rule and the problem of finding positive solutions to a certain set of linear inequalities. A system of linear inequalities is derived whose possession of a strictly positive solution for every triple of alternatives is both necessary and sufficient for the transitivity of majority rule, The consequence of this is that we can consider not only restrictions on admissible individual preference patterns but also restrictions on the distribution of votes over these patterns to ensure transitivity. [ABSTRACT FROM AUTHOR]

The DANTZIG-WOLFE decomposition procedure for concave programs can be viewed as inner linearization followed by restriction. This paper presents an approach that allows selective inner linearization of functions and utilizes a generalized pricing problem. It allows considerable flexibility in the choice of functions to be approximated using inner linearization. Use of the generalized pricing problem guarantees that strict improvement in the value of the objective function is achieved at each iteration and provides a termination criterion that is both necessary and sufficient for optimality. A specialization of this procedure results in an algorithm that is a direct extension of the Dantzig-Wolfe decomposition algorithm. [ABSTRACT FROM AUTHOR]

A new cluster-analysis method, the bond energy algorithm, has been developed recently; it operates upon a raw input object-object or object-attribute data array by permuting its rows and columns in order to find informative variable groups and their interrelations. This paper describes the algorithm and illustrates by several examples its use for both problem decomposition and data reorganization. [ABSTRACT FROM AUTHOR]

This paper discusses a model for the stochastic motion of the slow-down points of cars behind a bottleneck. The model considered assumes cars to have non-zero length, and employs a simple ‘car-following-slowdown rule.’ The case where ‘gaps’ between cars form a stationary reversible sequence of random variables is discussed, and the main result consists of an explicit expression for the steady-state distribution of the physical length of the stream of cars behind the bottleneck when ‘gaps’ are independent and identically distributed (iid) with exponential tail and atom at the origin. When this atom has zero mass (i.e., the gaps are lid exponential) it turns out that the result yields the steady-state distribution of waiting time in an M/D/1 queue and agrees with the known result. When this atom is nonzero, the main result in the queuing context yields the steady-state distribution of waiting time in an M′/D/1 queue, where M′ denotes an arrival stream with interarrival times being iid with exponential tail and atom at the origin. [ABSTRACT FROM AUTHOR]

This note discusses a problem of scheduling jobs on a machine using various machine tools in which considerable changing of the tools is necessary, and the changeover time depends critically on the previous jobs. It derives a branch-and-bound algorithm, which has been shown to be computationally restrictive at the present time. Various heuristic methods have been tried and the computational results are very promising. [ABSTRACT FROM AUTHOR]

This paper is concerned with determining the various probability generating functions and moments associated with the number of tasks performed by a machine subject to breakdown. The running time, waiting time before repair, and the repair time are independent random variables with general probability density functions. The generating function of the number of tasks for a given uninterrupted running time is assumed to be known. Some special cases are considered. [ABSTRACT FROM AUTHOR]

The estimate of expected critical-path length in PERT networks in this paper is usually better than the FULKERSON estimate because of greeter flexibility in choosing a path whose length approximates the length of the critical path. As the calculations are based on a model approximating the actual network, the new estimate may fall on either side of the expected critical path, even though the Fulkerson estimate never exceeded the expected critical-path length. A Fortran program was written to calculate the new estimate, whose calculation is more complicated than Fulkerson's estimate. The new estimate, Fulkerson's estimate, and the expected critical-path length are compared in several examples. [ABSTRACT FROM AUTHOR]

Efficient search of items in a store of information, such as books in a library, abstracts of articles, information in a computer data bank or the like, requires that the items most closely connected in content be dose together, in order that a person looking for some particular information may concentrate his search on as small a part of the store as possible. The degree of ‘connectedness‘ between two items i and j can be expressed in terms of a correlation index nij. This paper discusses methods of estimating these indices. Once the correlation indices are known for each pair of items in the store, it is possible to assign a position xi for each item i, along a linear classification scale, such that the larger the nij between items i and j the closer the two items are on the scale. Such a scale indicates the optimal ordering of books on library shelves or of items in any other data collection. It also provides means for optimal subject descriptors for a computer-based information store. A procedure is described whereby the values of the xi's may be determined in terms of the nij's. When the items in the store tend to ‘clump together’ in classes, with much smaller correlation between items of different classes than those between items of the same class, an approximation technique may be used to locate the relative positions of the classes along the scale, as well as the distribution of the x's within each particular class. An example is given of these techniques. [ABSTRACT FROM AUTHOR]

Given the operating costs, usage function, and planning horizon of a bulk service system, say a common-carrier transportation system, the objective is to determine the number and the starting times of the services so that the total profit is maximized. For such problems, this paper studies the existence and computability of optimal schedules. It shows that an ∈-optimal schedule can be found by a discrete optimization on a sufficiently fine grid. It then makes more specific assumptions regarding the dependence of usage on the schedule and presents a dynamic-programming algorithm for the discrete optimization. Finally, an analytic solution is given for a simple case. [ABSTRACT FROM AUTHOR]

A basic model for air-pollution control is a semi-infinite program that minimizes the sum of individual polluter's control costs while ensuring that ambient pollution concentrations are within air-quality standards. This paper is an extension that includes the effects of pollution-control-device breakdowns and shutdowns for planned maintenance. We use the fact that days characterized by good dispersion of pollution emissions occur periodically and can be accurately forecast for shutdown periods. A stochastic process of breakdown arrivals and servicing, and appropriate extensions of diffusion models give rise to a model for additional concentrations due to downtime. Parameters of the stochastic process are included as decision variables in a chance-constrained semi-infinite program allowing for tradeoffs between collection efficiency and various reliability characteristics. A practical implementation model and solution techniques are given for possible use in the present clean-air program. [ABSTRACT FROM AUTHOR]