bluuebunny/crossref_metadata_2025 huggingface dataset:
Closure of the Right-Hand-Side Set for Systems of Nonlinear Inequalities
Authors: Gould F. J. , Pashner H.
Published: November 2008

Consider the set of all vectors b such that the system g(x) ≦ b has a solution, where g: D → Rm, D ⊆ Rn. This paper presents necessary and sufficient conditions for this set to be closed, with special results on continuous and convex functions, and gives an application to mathematical programming.
Letter to the Editor—A Comparison of Estimates of Nuclear Bomb Casualties from Two Different Urban Models
Authors: Wilkins C. A. , Shaw J. A. , Keane A.
Published: November 2008

Expected numbers of human casualties in a single-bomb nuclear attack upon a symmetric city are calculated using Sherratt's and Clark's models and for various distances between the city center and ground zero. The calculated results indicate that considerable error may arise in practical cases from the unjustified use of Sherratt's model.
Branch-and-Bound and Approximate Solutions to the Capacitated Plant-Location Problem
Authors: Sá Graciano
Published: November 2008

In the capacitated plant-location problem, a planner is given a set of projects for production expansion and a linear transportation-cost matrix, and is asked to choose the subset of projects that meets demand at several markets, at the least production-distribution cost. The projects are defined a priori by size, location, and cost function, the latter being concave. An exact branch-and-bound treatment for the problem is explained, together with an approximate routine for solving the problem. The approximate routine borrows from the “add” approach of Kuehn-Hamburger and the “drop” approach of Feldman-Lehrer-Ray. Some of its mathematical properties are described, and sufficient conditions for the optimality of the solution obtained are shown. Empirical evidence is provided suggesting that the branch-and-bound method may be useful in problems of around 25 integer variables, perhaps more, depending on how tightly row-constrained the problem at hand is. Evidence is also provided suggesting that the approximate routine is fast and produces good, frequently optimal, results.
A Dynamic Programming Algorithm for Cluster Analysis
Authors: Jensen Robert E.
Published: November 2008

This paper considers the problem of partitioning N entities into M disjoint and nonempty subsets (clusters). Except when both N and N − M are very small, a search for the optimal solution by total enumeration of all clustering alternatives is quite impractical. The paper presents a dynamic programming approach that reduces the amount of redundant transitional calculations implicit in a total enumeration approach. A comparison of the number of calculations required under each approach is presented in Appendix A. Unlike most clustering approaches used in practice, the dynamic programming algorithm will always converge on the best clustering solution. The efficiency of the dynamic programming approach depends upon the rapid-access computer memory available. A numerical example is given in Appendix B.
A Time-Sharing Model with Many Queues
Authors: Adiri I. , Avi-Itzhak B.
Published: November 2008

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.
Production Allocation with Set-Up Penalties and Concave Material Costs
Authors: White Charles H.
Published: November 2008

The problem of allocating known production requirements of several products for several warehouse locations to several different manufacturing plant sites is considered with specific treatment to concave cost structures and to both out-of-pocket and lost-production-time set-up penalties. The objective is to meet these production requirements at minimum total cost, which is the sum of the material costs, the manufacturing costs, the out-of-pocket set-up costs, and the distribution costs. A model is developed that is shown to be a mixed integer linear-programming model. A branch-and-bound solution procedure is then presented, and some computational results are discussed.
Stability in Nonlinear Programming
Authors: Evans J. P. , Gould F. J.
Published: November 2008

This paper establishes necessary and sufficient conditions for constraint set stability requiring neither convex constraint functions not convex constraint sets. These conditions then lead to a sufficiency result for the continuity of the optimal objective values as the right-hand side varies. Applications to quasiconvex functions are presented.
Two-Server Markovian Queues with Balking: Heterogeneous vs. Homogeneous Servers
Authors: Singh Vijendra P.
Published: November 2008

This paper analyses a Markovian queuing system with balking and two heterogeneous servers determines the capacity of the slower server and obtains the optimal service rates that minimize the average characteristics of the heterogeneous system. The heterogeneous system is compared with a corresponding homogeneous system and a condition showing the efficiency of the heterogeneous system is obtained, this condition involving only the traffic intensity and the service rates. A cost model is discussed and various tables and graphs representing the average characteristics of both the systems are given.
Letter to the Editor—An Alternative Proof of a Conservation Law for the Queue G/G/1
Authors: Schrage Linus
Published: November 2008

Kleinrock first showed that, for a multiclass M/G/1 queue, the expected waiting times for all classes satisfy a simple linear equality constraint that is independent of queue discipline for a large class of disciplines. We generalize here the conditions under which this result holds and give a simpler proof.
Letter to the Editor—A Note on Pattern Separation
Authors: Grinold Richard C.
Published: November 2008

This note describes a linear programming method of separating two, not necessarily disjoint convex polyhedral sets in En. If the sets are disjoint, a strictly separating hyperplane is generated that maximizes and equalizes the distance between the sets and the hyperplane. If the sets intersect a hyperplane is generated that minimizes the maximum error.
A Class of General Reliability Growth Prediction Models
Authors: Barr Donald R.
Published: November 2008

In structuring reliability growth prediction models as Markov chains it is seen that the computation of the reliability after n trials and possible associated repairs R, may be accomplished with any of several different methods. This paper considers a class of models that accommodates variations in several important factors, such as the interdependences of assignable cause failure modes, inclusion of an inherent failure mode, the repair policy, and the distribution of initial states of the system.
Mathematical Optimization Techniques for the Simultaneous Apportionments of Reliability and Maintainability
Authors: Shershin Anthony C.
Published: November 2008

This paper sets forth mathematical means for optimizing the simultaneous apportionments of reliability and maintainability by means of two techniques. Lagrange multipliers and dynamic programming. Since one of the constraint equations involves allocating both variables, this simultaneous apportionment problem differs from the usual two-dimensional dynamic programming problems. Two cost problems are treated the first minimizes cost while satisfying availability requirements under the assumption that an unlimited ceiling exists for the cost, and the second maximizes reliability and maintainability given a fixed budget. Although these problems appear closely related, step functions usually preclude considering them together. The paper also considers two numerical examples, an interesting cost model for maintainability, and using computers with its models.
Intransitive Indifference in Preference Theory: A Survey
Authors: Fishburn Peter C.
Published: November 2008

This paper presents a survey of results in preference theory with intransitive indifference and discusses them for the areas of basic preference theory, consumer preference, additive utility, qualitative probability, expected utility, and social choice.
Linear Programming Solutions to Ratio Games
Authors: Schroeder Roger G.
Published: November 2008

This paper develops a method for finding the minimax solutions to a game whose payoff function is of the form XtAY/XtBY, where X, Y are mixed-strategy vectors and A, B > 0 are matrices. Such a payoff function arises in stochastic games, economic models of an expanding economy, and some nonzero-sum game formulations. The game is transformed into a linear program with a parameter in the constraint set. By successive solutions of this program with appropriate values of the parameter, the value and optimal strategies of the game can be approximated to any desired degree of accuracy. A new approach of perturbing linear programs is used to prove convergence of the computational technique and to bound the rate of convergence.
Two Problems in Markov Chains: A Topological Approach
Authors: Guardabassi G. , Rinaldi S.
Published: November 2008

This paper deals with two problems of asymptotic aggregation of an ergodic Markov chain. The first is concerned with the determination of an aggregated Markov chain, the asymptotic probabilities of which are just equal to conditional asymptotic probabilities defined on the original Markov chain. The second one relates to the determination of an aggregated chain, the asymptotic probabilities of which are equal to the asymptotic probabilities of the elements of a given state partition. Both problems are approached from a topological point of view and solutions are given in terms of signal-flow graph techniques. Comments about the main computational features of the method are also included.
Cutting-Plane Methods without Nested Constraint Sets
Authors: Topkis Donald M.
Published: November 2008

This paper gives general conditions for the convergence of a class of cutting-plane algorithms without requiring that the constraint sets for the sub-problems 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 Veinott. 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.
Quadratic Binary Programming with Application to Capital-Budgeting Problems
Authors: Laughhunn D. J.
Published: November 2008

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 σ2 of portfolio returns, his decision requires prior identification of the (μ, σ2) 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.
Optimization of Series-Parallel-Series Networks
Authors: Jensen Paul A.
Published: November 2008

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-parallel-series 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 computer implementation of the algorithm. Problems with as many as 15 serial components and three constraints have been solved with reasonable digital computer computation times.
Effectiveness Determination of Bombers Penetrating Through an Air-to-Air Defense
Authors: Fawcett Clifford D. , Jones Chester G.
Published: November 2008

This model determines the attrition of the forces and the expected value of the number of targets receiving at least one air-to-ground weapon in a conflict between bombers that may carry lethal defense weapons and/or decoys and interceptors, each of which may fly several multiple-pass sorties during the course of the battle. Analytical results are presented for the case where the bomber's supply of defensive weapons can be assumed to be infinite, i.e., each bomber always has a defensive weapon when one is needed. A Monte Carlo model is discussed and some results are given for the case where the bombers may run out of defensive weapons. A rule of thumb is given to determine the required number of defensive weapons per bomber so that the analytical results approximate the Monte Carlo results.
Letter to the Editor—Supplement
Authors: Raghavachari M.
Published: November 2008

Clarifications to the paper: M. Raghavachari, “On Connections Between Zero-One Integer Programming and Concave Programming Under Linear Constraints,” Opns. Res. 17, 680–684 (1969).
Space Applications—Foreword
Authors: Paine Thomas O.
Published: November 2008

Foreword to the issue devoted to space applications.
A Method of Solution for General Machine-Scheduling Problems
Authors: Charlton John M. , Death Carl C.
Published: November 2008

This paper proposes a general method of solution for problems, involving the allocation of jobs to machines and the sequencing of jobs on machines, in which a number of jobs, each consisting of a number of operations that may be performed on a given set of machines, is to be completed in some optimal fashion. Considering constraints on machine availability, job completion dates, and zoning, the paper demonstrates the underlying relation of a wide variety of machine-job problems with reference to their graphical representation, states a branch-and-bound method of solution, solves an illustrative example, and gives the mode of application to specific problems (for several of these the method reduces to methods published elsewhere). The algorithm represents not only a general framework of theoretical interest, but also a practical approach to certain specific problems.
Measuring the Effectiveness of Nondefense Public Programs
Authors: Hatry Harry P.
Published: November 2008

This paper suggests that current public programs have been measured in grossly inadequate ways. It argues against the use at all levels of government of workload measures, physical standards, and cost criteria to represent outputs. It discusses the need for output measurement (1) that uses measures which are directly related to basic governmental objectives, (2) that includes multiple measures (since governmental programs seldom can be adequately evaluated by attempts to compress multiple measures into a single criterion such as a single monetary measure), (3) that identifies the differential effects on different population subgroups, (4) that does not excessively vise “proxy” or “lower-level” criteria without at least briefly examining the relation of the proxies to the basic objectives, and (5) that, where appropriate, uses qualitative, subjective, measures rather than neglecting important effects. Measurability does not require the quantification of absolute numbers, but can make use of many subjective approaches such as ratings, rankings, and the like.
Cost-Effectiveness Analysis of Civil Engineering Systems: New York City's Primary Water Supply
Authors: de Neufville Richard
Published: November 2008

This paper proposes a method for cost-effectiveness studies of civil engineering works and illustrates it by an example of its application to an urban-systems problem. This approach tries to bridge the dichotomy of objectives that often exists between the policy levels of government and the engineering agencies, and that leads to frequent impasses for implementation. The process first broadens the traditional terms of reference for public-works design, which are usually governed by engineering standards only tenuously related to the multiple objectives of a facility. Second, a procedure is suggested for generating alternative configurations for the system and its components. Finally, a means is presented for exploring alternative time-phased strategies of development. The paper presents a case study of the application of this approach to the planning and design of New York City's Third City Water Supply Tunnel, and discusses its lessons.
Sprinter Mod III: A Model for the Analysis of New Frequently Purchased Consumer Products
Authors: Urban Glen L.
Published: November 2008

This paper presents a model-based information system designed to analyze test-market results, to assist decision-making for a new frequently purchased consumer product, and to serve as an adaptive control mechanism during national introduction. The model, called SPRINTER, is based on the behavioral process of the diffusion of innovation and can be used normatively in an interactive search mode to find the best marketing strategy for a new product. The input is obtained from test-market data analyzed by statistics and combined with subjective judgments. A Go, On, or No decision is made on the basis of the estimated profit and risk produced by the best marketing strategy. During national introduction the model serves as a “problem-finding” mechanism. It uses early national sales and micro-level behavioral data to diagnose problems in the introduction. It also can be used to search for solutions to these problems as they are recognized. Finally, an application of this model to a real product is reported, this application using an on-line computer program that allows convenient man-system communication.
A Model of Health-Service Utilization and Resource Allocation
Authors: Zemach Rita
Published: November 2008

This paper presents the initial basis for a descriptive mathematical model of the total utilization of personal health and medical services by the population of a community or region, the allocation of resources used to provide these services, and the cost of health care as derived from the prevailing costs of resources. A simplified illustrative example is presented. The patterns by which resources are allocated to provide services, and the patterns by which the population groups use the total mix of services available, are identified as parameters in the model. On the basis of past data, the model can be used to predict allocation and use of services over time, as a function of population dynamics. Problems of implementation are discussed.
The Role of Operations Research in Population Planning
Authors: Reinke William A.
Published: November 2008

Two features of population planning are of special interest to operations researchers: the important interaction among family planning, health, and economic development, and the substantial but varying impact of social, cultural, political, and economic factors—features that require a multi-disciplinary, flexible approach for which operations research is well suited. In spite of the vast differences among various international settings, three overriding principles should be borne in mind. First, programs of population planning are designed to serve national goals, whereas the ultimate actions concerning family limitation are usually recognized to be private family decisions. Second, one usually faces a rather ill-defined interplay among a great variety of factors. Third, the universal importance of the population problem in developing countries is always coupled with severe limitations of resources to cope with the problem. This paper deals initially with the family decision process and then with the organization of professional activities toward population control. In both cases hypothetical models are developed, information from the field is used to illustrate their significance, and suggestions for further research are offered. The decision model considers the utility of child-bearing for different population groups compared with the subjective valuation these groups give to contraception. Means of measuring these poorly defined values are proposed. In assessing the role of operations research in the organization and delivery of family planning services, the paper directs attention to the allocation problem, which includes concern, on the one hand, for the methods of contraception provided, the manner in which they are offered, and the kinds of personnel employed, and, on the other hand, the attitudes of target populations toward both the services and the providers.
The Traveling-Salesman Problem and Minimum Spanning Trees
Authors: Held Michael , Karp Richard M.
Published: November 2008

This paper explores new approaches to the symmetric traveling-salesman problem in which 1-trees, which are a slight variant of spanning trees, play an essential role. A 1-tree is a tree together with an additional vertex connected to the tree by two edges. We observe that (i) a tour is precisely a 1-tree in which each vertex has degree 2, (ii) a minimum 1-tree is easy to compute, and (iii) the transformation on “intercity distances” cij → Cij + πi + πj leaves the traveling-salesman problem invariant but changes the minimum 1-tree. Using these observations, we define an infinite family of lower bounds w(π) on C*, the cost of an optimum tour. We show that maxπw(π) = C* precisely when a certain well-known linear program has an optimal solution in integers. We give a column-generation method and an ascent method for computing maxπw(π), and construct a branch-and-bound method in which the lower bounds w(π) control the search for an optimum tour.
A Matrix Approach to Nonstationary Chains
Authors: Harary Frank , Lipstein Benjamin , Styan George P. H.
Published: November 2008

A finite discrete nonstationary Markov chain is completely characterized (after the initial probability distribution has taken effect) by its time sequence of transition probability matrices Pi. The ith causative matrix Ci is defined as the product Pi−1 (if it exists) times Pi+1. Thus, the causative matrices are analogous to derivatives in calculus as an indication of rate of change. The eigenvalues and eigenvectors of a constant causative matrix C have been found useful in their connection with the tendency of the chain to be convergent or divergent. Results for two-state chains are presented in some detail. A comprehensive bibliography of papers on non-stationary chains is included.
Simplified Analysis of an Alternating-Priority Queuing Model with Setup Times
Authors: Sykes Jack S.
Published: November 2008

This paper analyzes a single-server queuing system in which service is alternated between two queues. Each queue is assumed to have an independent Poisson input and an independent general service-time distribution. The alternating priority rule is followed. Independent general distributions are assumed for the intervals required to switch service from one queue to the other. The following aspects of the steady-state solution are presented for each queue: average delay of an entering customer, average length, average durations of the busy period, and average rate at which service is offered to a queue. The model has been applied to a generalized data-communications system in which transmission between two data stations is possible in only one direction at a time.
Some Theorems on a Single-Server Queue with Balking
Authors: Dick Ronald Stewart
Published: November 2008

An M/G/1 batched-service queuing model is described for a waiting room of size m. When the waiting room is filled, the arrival rate changes from λ to λp; i.e., 100 (1 − p) per cent of all arrivals balk if the waiting room is full. Since p may be zero, the model includes finite queues as special cases. The special case with m = 0 has been handled by Takács. However, in this paper the steady-state probability formulas for length of queue given by Takács are corrected, and the results extended for m ≧ 1.
Letter to the Editor—A Note on a Distribution Problem
Authors: Charnes A. , Glover Fred , Klingman D.
Published: November 2008

A certain class of distribution problems has been treated incorrectly and ambiguously, respectively, in two major and widely read texts on linear programming. This note traces the nature of this mistreatment to a paradoxical solution property of this class of problems, namely, even if all the shipping costs are nonnegative, an optimal solution may ship more than the minimum demand to a destination.
Letter to the Editor—A Note on Cutting-Plane Methods Without Nested Constraint Sets
Authors: Topkis Donald M.
Published: November 2008

This note shows that a framework I developed earlier can be used to give a simplified proof of conditions given by Eaves and Zangwill (which weaken the uniform concavity requirement on my earlier objective function) under which inactive constraints may be dropped after each subproblem in cutting-plane algorithms. Here the convergence rate I established previously as an extension of the results of Levitin and Polyak is improved and its application extended.
Implementation in Operations Research and R&D in Government and Business Organization
Authors: Radnor Michael , Rubenstein Albert H. , Tansik David A.
Published: November 2008

Many of the organizational problems that are inherent in the integration of innovation-producing activities come to light in the form of difficulties experienced in achieving implementation of output. Such difficulties are common not only in operations research but in most forms of innovative activity, among them R&D. Growing out of the work that has been pursued at Northwestern in research programs on both the R&D process and the management of operations research/management science (OR/MS) activities, this paper examines the systemic causes of such implementation problems. We have hypothesized that the environment in which innovative activity is carried on is an important determinant of the mode and effectiveness of project implementations. Specifically, we have considered how goal operationally differences, such as may be found between government and business organizations, will influence the strategic behavior of the managers of innovative groups. The data in this paper come primarily from our OR/MS studies in approximately one hundred United States business and government organizations.
The Bounding Hyperplane Method of Linear Programming
Authors: Saksena C. P. , Cole A. J.
Published: November 2008

This paper describes a new method for solving a general linear programming problem.
Technical Note—The Optimal Location of New Facilities Using Rectangular Distances
Authors: Wesolowsky G. O. , Love R. F.
Published: November 2008

This note describes a method for locating any number of facilities optimally in relation to any number of existing facilities. The objective is to minimize the total of load-times-distance costs in the system. Any amount of loading may be present between the new facilities and the existing facilities and between the new facilities themselves. Distances are assumed to be rectangular.
The One-Terminal TELPAK Problem
Authors: Rothfarb B. , Goldstein M.
Published: November 2008

To lease long-distance telecommunications facilities, the lessee submits, for billing purposes, a configuration of individual channels and bulk units of channels, called TELPAKS, that implements his requirements. The bulk rate charged for a TELPAK results in the cost being a piecewise linear function of the number of channels. This leads to a network-synthesis problem with a nonlinear cost function that is neither concave nor convex. We give a characterization of an optimal solution and present a method for obtaining a low-cost configuration when all requirements are to a single point.
A Model for Allocating Interceptors from Overlapping Batteries: A Method of Dynamic Programming
Authors: Swinson G. E. , Randolph P. H. , Dunn B. J. , Walker M. E. , Williams R. D.
Published: November 2008

This paper develops a model for the optimum allocation of fixed stockpiles of interceptors. Imbedded dynamic programming and successive approximations serve as the format for the computational scheme. This procedure leads to a local optimum solution in general and to the global optimum in certain instances. A method for determining upper bounds is included in the algorithm so that optimal stopping rules may be used to choose a final solution.
Technical Note—An Algorithm to Find Elementary Negative-Cost Circuits with a Given Number of Arcs—The Traveling-Salesman Problem
Authors: Netter J. P.
Published: November 2008

A theorem on sequences of numbers reduces the amount of tree searching to locate an elementary negative-cost circuit in a network; the search may be restricted to circuits with a given number of arcs. This result leads to a primal algorithm for the traveling-salesman problem.
Technical Note—Minimizing a Function of Permutations of n Integers
Authors: Rau John G.
Published: November 2008

This note discusses sufficient conditions for a function of permutations (j1, …, jn) of the integers 1, 2, …, n to have a minimum at the permutation (j*1, …, j*n) and derives a solution algorithm that is equivalent to the known solution algorithm for special cases involving sequential search and testing.
Dynamic Linear Programs for Production Scheduling
Authors: Glassey C. Roger
Published: November 2008

Deterministic linear scheduling problems can often be formulated as linear programs with staircase coefficient matrix structure in which the linking blocks are identity matrices, since the activities that link successive time periods represent storage of goods. The solution technique proposed in this paper can be viewed as a nested decomposition approach in which primal- as well as dual-variable information is transmitter between master and subproblems.
Quadratic Programming with a Quasiconvex Objective Function
Authors: Martos Béla
Published: November 2008

This paper gives both necessary and sufficient conditions for a quadratic function to be quasiconvex in the nonnegative orthant. Methods of pseudoconvex programming (such as those of Frank and Wolfe) can solve linearly constrained quadratic programming problems with such an objective function.
A Class of Sequential Games
Authors: Kohler David A. , Chandrasekaran R.
Published: November 2008

This paper considers a game between two players who choose from a collection of objects. The players make their choices alternately and Vi,j represents the value or amount that the ith player will gain if he selects the jth object. In relation to these values, the players may have various strategies or approaches to the game, and each of them constitutes a distinct theoretical problem. The paper formulates and solves three of these problems, each one having practical significance (for example, for the draft of professional football players).
Some Inequalities for Parallel-Server Queues
Authors: Brumelle Shelby L.
Published: November 2008

This paper obtains bounds, in terms of the first two moments of the input, on the expected wait in an A/G/k queue with stationary input. To this end, two single-server systems are constructed. The wait in queue for the first single-server system is stochastically larger than the wait in the given multiserver system, and the expected wait in the second single-server system is used to obtain a lower bound on the expected wait in the A/G/k system. The paper also develops, as a consequence of the lower bounds, some results concerning the optimum number of servers, given a fixed work capacity.
An Exact Comparison of the Waiting Times Under Three Priority Rules
Authors: Nair S. Sreekantan , Neuts Marcel F.
Published: November 2008

This paper compares the waiting times of customers under three priority rules: the order-of-arrival rule, the shortest processing time (within a generation) first, and the longest processing time (within a generation) first. In particular, the covariance matrix of the trivariate distribution of the equilibrium waiting times is obtained explicitly.
A Stochastic System with Scheduled Secondary Inputs
Authors: Şahin İzzet , Bhat U. Narayan
Published: November 2008

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.
Bounds for a Dynamic-Priority Queue
Authors: Holtzman J. M.
Published: November 2008

This paper obtains upper and lower bounds on equilibrium mean waiting times for a Poisson-input queue with the nonpreemptive dynamic-priority service discipline studied by Jackson.
Some Multi-Contract Decision-Theoretic Competitive Bidding Models
Authors: Stark Robert M. , Mayer Robert H.
Published: November 2008

This paper reviews the principal public literature concerned with expected-profit decision-theoretic closed-competitive-bidding models. It makes extensions of previous formulations for static multi-contract bidding situations with and without cost dependencies and resource constraints. The same decision model is reformulated to utilize numerical, Lagrange-multiplier, dynamic, and integer linear programming techniques according to the information available to the bidder. A zero-one integer programming formulation is well suited to utilize subjective probabilities of winning estimates. Finally, the paper suggests a format for further development.
Competitive Bidding: A Comprehensive Bibliography
Authors: Stark Robert M.
Published: November 2008

This paper lists, alphabetically by first author, over 100 papers and books dealing with competitive bidding.
Design Commonality to Reduce Multi-Item Inventory: Optimal Depth of a Product Line
Authors: Rutenberg David P.
Published: November 2008

The problem of commonality is posed as a problem of economic balance. It involves the disutility of refusing to provide each segment of customers with an item fitting its exact requirements versus economies of scale achieved in producing and inventorying each item. The depth of the product line (the optimal number of items to produce) is determined by finding the minimum concave cost flow through a network. An efficient dynamic program (developed in production smoothing) is used to find this flow. Many products consist of interacting subassemblies; such multistage problems of finding the number of types of each subassembly can also be solved; a computational procedure is developed and an example presented. Along with modularity and cannibalization, multistage commonality is an essential component of a theory of efficient engineering design.
Errata
Authors: Mitten L. G.
Published: November 2008

In the paper “Branch-and-Bound Methods: General Formulation and Properties,” Opns. Res. 18, 24–34 (1970), the result (R5) is incorrect and (R6) is incorrect as stated.
On the Computation of Hit Probability
Authors: Helgert Hermann Josef
Published: November 2008

Computing the accuracy with which guns and similar weapon systems deliver ordnance is, in its most general context, a problem in the theory of discrete stochastic processes. Thus, the classic methods of computing hit probability by assuming the impact points to be isolated random variables are much too restrictive to be of general use. As a result, there exists in the literature a profusion of formulas, tables, and computational methods whose applications are limited to a variety of special cases. This in itself is no handicap as long as a unifying theory exists from which all these special cases follow. However, it is precisely the lack of such a theory that has made the available results ambiguous, confusing, and generally unsatisfying. The aim of this paper is to remedy this situation by providing a theoretical framework for the concise definition of hit distribution and its computation. The subjects treated are the various types of errors inherent in gun systems, and a general discussion of hit distribution and its computation, as well as a detailed analysis of independent and Markov-dependent rounds and the diffuse-target approximation.
Technical Note—Threshold Probabilities when Searching for a Moving Target
Authors: Schweitzer Paul J.
Published: November 2008

Pollock has examined a model of search for a target whose transitions between two regions are described by a two-state stationary Markov chain. The minimum-search policy is characterized by a threshold probability π* that determines which region to search next. This note presents a simple recursive procedure for calculating π*.
Queuing Problems with Heterogeneous Arrivals and Service
Authors: Yechiali U. , Naor P.
Published: November 2008

This paper studies a two-level modification of the M/M/1 queuing model where the rate of arrival and the service capacity are subject to Poisson alternations. The ensuing “two-dimensional” problem is analyzed by using partial-generating-function techniques, which appear to be essential in the present context. The steady-state probabilities and the expected queue are evaluated, and numerous special and extreme cases are analyzed in detail.
Nonlinear Pricing: Applications to Concave Programming
Authors: Gould F. J.
Published: November 2008

This paper introduces approximation theorems for using nonlinear pricing techniques to solve concave programs, and then proposes an algorithm that is essentially a sequential unconstrained procedure with exponential prices. Then it derives upper bounding estimates and solves several specific problems.
A Branch-and-Bound Algorithm for Zero-One Mixed Integer Programming Problems
Authors: Davis Ronald E. , Kendrick David A. , Weitzman Martin
Published: November 2008

This paper presents the results of experimentation on the development of an efficient branch-and-bound algorithm for the solution of zero-one linear mixed integer programming problems. An implicit enumeration is employed using bounds that are obtained from the fractional variables in the associated linear programming problem. The principal mathematical result used in obtaining these bounds is the piecewise linear convexity of the criterion function with respect to changes of a single variable in the interval [0, 1]. A comparison with the computational experience obtained with several other algorithms on a number of problems is included.
Classical Derivation of the Necessary and Sufficient Conditions for Optimal Linear Programs
Authors: Taha Hamdy A. , Curry Guy L.
Published: November 2008

This paper presents a new derivation of the key ideas of Dantzig's simplex algorithm by using the differential approach to nonlinear programming. Specifically, the necessary condition shows that a candidate for the optimum is a basic feasible solution, while the sufficiency condition indicates that the optimality indicator (cj − zj) for nonbasic variables xj must be nonpositive (nonnegative) in order for a maximization (minimization) linear program to be optimal.
Technical Note—An Improved Branch-and-Bound Method for Integer Programming
Authors: Tomlin J. A.
Published: November 2008

This note proposes two extensions of the successful Beale and Small branch-and-bound mixed-integer algorithm. The integer requirements on nonbasic variables are utilized to calculate stronger “penalties” when searching down the solution tree and to give a stronger criterion for abandoning unprofitable branches of the tree when backtracking. This stronger criterion is obtained by making use of Gomory cutting-plane constraints. These modifications have produced considerable reductions of the searching effort required for pure integer and predominantly integer problems, and have the further advantage of being very easy to incorporate.
Technical Note—On Converse Duality in Nonlinear Programming
Authors: Craven B. D. , Mond B.
Published: November 2008

Huard and Mangasarian have proved the converse duality theorem in mathematical programming by using the Kuhn-Tucker theorem. However, this note points out the advantages of using Fritz John's theorem.
Technical Note—Results in Using Gomory's All-Integer Integer Algorithm to Design Optimum Logic Networks
Authors: Baugh C. R. , Ibaraki T. , Muroga S.
Published: November 2008

The design of optimum networks has for sometime been formulated as an integer programming problem; however, only recently have networks been obtained by using these formulations. This note reports some computational experience on the synthesis of optimum networks using Gomory's all-integer integer method. A typical example has a problem size of 91 unknowns and 240 inequalities. The effects of further restricting the problem by adding additional constraints are also investigated. Some other experiments, such as various ordering of inequalities and convergence characteristics of feasible versus infeasible problems, are described.
Technical Note—Cyclic Dynamic Programming: A Procedure for Problems with Fixed Delay
Authors: Luenberger David G.
Published: November 2008

A dynamic decision problem in which the effect of control action is either delayed for a number of time periods or has an effect that lasts for a fixed period leads, in the conventional formulation, to a high-dimensional dynamic-programming problem. This paper develops a method for exploiting the inherent structure of such problems that leads to low-dimensional “cyclic dynamic programming” problems that are easier to solve than the problem that is obtained by the conventional approach.
Common-Stock Transaction Sequences and the Random-Walk Model
Authors: Simmons Donald M.
Published: November 2008

This paper reviews the current status of the random-walk model as it applies to price-change sequences in common stocks, and examines certain striking dependencies in these sequences at the transaction level. In particular, successive transaction-price changes are seen to be negatively correlated, with each price change projecting its negative influence forward toward its successors in the sequence. The strength of this influence is diminished sharply by each nonzero price change that it is required to “penetrate,” but is only slightly weakened when projected across changes of zero magnitude. In the latter case, in fact, statistical dependency is shown to exist across intervals of as many as ten transactions or more.
Letter to the Editor—The Language of Lot Size
Authors: Crowe Walter R.
Published: November 2008

This communication lists a selection of some fifty differently expressed formulas, all relating to the “Harris” EOQ/lot-size expression, and appeals for efforts toward standardizing terminology in operations research, to reduce the proliferation of symbols.
The Theorem of the Alternative in Social Choice Theory
Authors: Fishburn Peter C.
Published: November 2008

This paper presents two theorems for the existence of solutions for finite systems of linear inequalities and equalities and applies them to three problems in social choice theory. The primary purpose of the paper is to show how the theorems may be used in axiomatic investigations with finite systems.
An Ordering Algorithm for Analysis of Data Arrays
Authors: Deutsch Stephen B. , Martin John J.
Published: November 2008

This paper presents an algorithm for reordering data arrays. The object is to find a one-dimensional ordering of the rows and columns of an array, given no prior information other than the array itself. The algorithm is an iterative one, and, in finding what it considers to be the most satisfactory ordering of an array, it also enables one to determine immediately the most significant underlying variable. The algorithm has been applied to arrays representing data from a variety of fields; examples are presented of political and archaeological data that have been analyzed, and it is shown that meaningful relations can be found directly through use of the algorithm.
Solution Method for a Class of Stochastic Scheduling Problems for the Production of a Single Commodity
Authors: Symonds Gifford H.
Published: November 2008

This paper expresses a solution method for a fairly general class of stochastic scheduling problems for the production of a single nonperishable commodity as a set of differences between the optimal partial differential equations in successive periods. It shows that the recursive stochastic scheduling equation, which is independent of subsequent values, allows an entire stochastic schedule to be generated from an initial inventory x0 and production z1 to meet a set of demand variables s1, …, sn to an extent indicated by F1(y1), …, Fn(yn). An optimal value of z1 is the minimal value that produces a feasible schedule. After the actual inventory xj−1 becomes available each period, then a new stochastic schedule can be prepared for the current optimal value of zj.
The Distribution of the Occupation Time for Single-Server Queues
Authors: Takács Lajos
Published: November 2008

This paper gives a general method for finding the distribution of the occupation time for single-server queues, discusses in detail queues with recurrent input and general service times, and gives some examples in which either the Laplace-Stieltjes transform of the distribution function of the inter-arrival times or the Laplace-Stieltjes transform of the distribution function of the service times is a rational function.
A Model of the ABM-vs.-RV Engagement with Imperfect RV Discrimination
Authors: Layno Salvador B.
Published: November 2008

This paper formulates an expected-value model of the ABM-vs.-RV engagement in which the defense is credited with an imperfect RV-discrimination capability expressed in terms of the Type I and Type II errors familiar in statistics. Since it is further assumed that the defense is conducted optimally within the limits of its resources and RV-discrimination capability, the results obtained from this model tend to be offense-conservative. Calculations made with this model support the final conclusion that the acquisition of even a modest RV-discrimination capability can result in considerable payoffs to the defender in terms of RV-leakage reduction.
Technical Note—A Counterexample to the Rudimentary Primal Integer Programming Algorithm
Authors: Mathis S. J.
Published: November 2008

This note describes the development of a counterexample to the rudimentary primal integer-programming algorithm. Two examples are given. The first shows the particular sequence of cuts that leads to a cycling process. Then, utilizing the algebraic implications of this sequence of cuts, a second example is developed that does not converge using the usual column-selection rule. A geometric interpretation is provided, and some comments are made on a means to force convergence in these two examples.