bluuebunny/crossref_metadata_2025 huggingface dataset:
Assembly-Line Balancing—Dynamic Programming with Precedence Constraints
Authors: Held Michael , Karp Richard M. , Shareshian Richard
Published: November 2008

This paper approaches the assembly-line balancing problem as a sequencing problem involving precedence constraints that prohibit the occurrence of certain orderings. This approach permits the formulation of a dynamic programming algorithm for the exact solution of small assembly-line balancing problems. A generalization of this algorithm combined with a successive approximations technique is used for the solution of large problems. In addition, certain combinatorial problems associated with partially ordered sets are formulated and discussed in detail. These problems arise whenever sequencing problems with precedence constraints are treated by dynamic programming techniques.
An Investigation of Strategies in Baseball
Authors: Lindsey George R.
Published: November 2008

The advisability of a particular strategy must be judged not only in terms of the situation on the bases and the number of men out, but also with regard to the inning and the score. Two sets of data taken from a large number of major league games are used to give (1) the dependence of the probability of winning the game on the score and inning, and (2) the distribution of runs scored between the arrival of a new batter at the plate in each of twenty-four situations and the end of the half-inning. The first shows that the runs adding most to the probability of winning are the one tying the score and the one putting the batting team one ahead. All other runs are slightly less valuable early in the game, and become increasingly less valuable as the game proceeds. By combining the two sets of data, the situations are determined in which an intentional base on balls, a double play allowing a run to score, a sacrifice, and an attempted steal are advisable strategies, if average players are concerned. An index of batting effectiveness based on the contribution to run production in average situations is developed.
Sensitivity of Decisions to Probability Estimation Errors
Authors: Isaacs Herbert H.
Published: November 2008

In making decisions on the basis of maximum expected utility, the decision maker is required to analyze the sensitivity of his decision to variability in probability estimation. This paper explores the general question of sensitivity to subjective probability estimates and derives an analytical representation of sensitivity. Some of the problems of applying sensitivity analyses are explored and a method suggested for resolving conflict of choice under conditions of high sensitivity. A sample problem is provided to illustrate application of the analytical techniques.
Letter to the Editor—A Note on Conditional Probability of Failure When Hazards are Proportional
Authors: Allen W. R.
Published: November 2008

The following result is of some interest to people studying equipment failure models [Barlow, R. E., L. Hunter, F. Proschan. 1963. Optimum redundancy when components are subject to open and short circuit failures. J. Soc. Indust. Appl. Math. 11 64–73.], and I shall state it in those terms. The result and the proof are of the type that make one think that this is probably a folk theorem but none of the folks I know, or that have reviewed the paper, seem to know the result.
The Economics of Nonfunctional Variety
Authors: Schaffir Kurt H.
Published: November 2008

The economic theory of the firm provides a substantial basis for management decisions regarding the level at which production or merchandising activities are to be carried out. The basic criteria for such decisions are generally found in marginal profits to be gained or marginal return of investment to be achieved. The present study extends the application of marginal analysis to that area of decision making which is concerned not with volume or quantity, but with the amount of variety that is to be provided. For this purpose, variety is measurable in terms of the number of varieties or subclasses existing of a given commodity or product group, and in terms of the distribution among the different subclasses of total units of the commodity produced or sold over an appropriate time period. The relations that have been developed can be demonstrated, for the moment, to apply only in areas where variety is predominantly of a nonfunctional nature—that is, pertaining to appearance or style rather than functional performance. They may be presumed to apply in other areas of variegation also, but tend to be obscured where technological, functional, or market factors play an important part.
On Sensitivity Analysis in Convex Quadratic Programming Problems
Authors: Boot J. C. G.
Published: November 2008

The present paper consists of three clearly distinct sections. In the first section we discuss the problem of how the solution vector of a quadratic programming problem changes in case of infinitesimal changes in the data of the problem. In the second section we apply these results to a numerical example that arose in a practical application of programming. In the third section we ask for the changes in the solution vector when some parameter (s) of the problem change (s) persistently rather than infinitesimally. This leads to a class of algorithms to solve quadratic programming problems of which the Houthakker capacity method and the Markowitz portfolio procedure are members.
An Optimum Allocation of Different Weapons to a Target Complex
Authors: Lemus F. , David K. H.
Published: November 2008

How best to allocate offensive weapons of various types to a group of targets in order to maximize the payoff constitutes a very important problem for optimizing strategies of defense. Solutions to the allocation problem, for the case where one type of weapon is involved, exist in the literature. Essentially these solutions fall into two categories digital solutions which yield integral results, and analytical solutions, based on the Lagrange Multipliers, which treat the number of weapons as a continuous variable and thus produce fractional answers. Whenever the number of weapons is large compared with the number of targets, analytical methods are preferred to digital ones because they achieve a saving in computer time at a negligible loss of accuracy. On the other hand, if the number of weapons is of the same order of magnitude as the number of targets, digital methods are preferable because they yield exact answers, as opposed to analytical solutions that produce rounding errors too large to render the results useful. The object of this paper is to generalize an analytical solution to the case where the attacker has more than one type of weapon available for assignment to an undefended or virtually undefended target complex. Defense strategies are not included. The paper presents a computational example where three types of weapons, each with a different number of attacking vehicles, are allocated to twenty targets. This example also permits a comparison between the fractional results of an analytical solution and the integral values obtained by a computer-oriented algorithm.
An Algorithm for Computing Interzonal Transfers Using the Gravity Model
Authors: D'Esopo D. A. , Lefkowitz B.
Published: November 2008

The gravity model is applied frequently to the problem of estimating the number of automobile trips between pairs of points (zones) of a highway network given the number of trips that arrive and depart each point. In this paper, the gravity model is formulated, and an algorithm for solving it is described. Problems associated with using the model also are discussed. A simple numerical example is presented.
Some Queuing Problems with Balking and Reneging—II
Authors: Ancker C. J. , Gafarian A. V.
Published: November 2008

This is the second of two papers in which balking (refusing to join the queue) and reneging (leaving the queue after joining) are considered. The new element here is that the balking behavior is drastically altered The model assumes (1) Customers arrive from a single infinite source in a Poisson stream (2) Arriving customers join the system if it is empty or balk with probability 1 − β/n, n = 1, 2, … where n is the number in system. Thus β is a measure of customer willingness to join the queue (3) Joining customers renege if service does not begin within a certain time. This time is a, random variable whose density function is negative exponential with parameter α (4) A single-service facility operates on a first-come, first-served basis with negative exponential service time distribution. For the steady state, the following are obtained the state probabilities, mean number in queue and system, the probability of R or more in system, the probabilities of balking, waiting, reneging, and acquiring service, the customer loss rate, the distribution and mean value of time in queue for customers who acquire service, and the corresponding results for those who renege. All of these results are also obtained for a pure balking system (no reneging) by setting the reneging parameter a equal to zero.
An Algorithm for the Traveling Salesman Problem
Authors: Little John D. C. , Murty Katta G. , Sweeney Dura W. , Karel Caroline
Published: November 2008

A “branch and bound” algorithm is presented for solving the traveling salesman problem. The set of all tours (feasible solutions) is broken up into increasingly small subsets by a procedure called branching. For each subset a lower bound on the length of the tours therein is calculated. Eventually, a subset is found that contains a single tour whose length is less than or equal to some lower bound for every tour. The motivation of the branching and the calculation of the lower bounds are based on ideas frequently used in solving assignment problems. Computationally, the algorithm extends the size of problem that can reasonably be solved without using methods special to the particular problem.
Multiple Choice Programming (A Procedure for Linear Programming with Zero-One Variables)
Authors: Healy W. C.
Published: November 2008

A new procedure for mixed integer programming is presented. It is applicable where the integer variables must be either zero or one, and where the integer variables are divided into sets such that the variables in each set sum to unity. Numerous practical applications fit this formulation. A justification for the algorithm is given, but proof of convergence is not known. The procedure has solved all test problems so far, and this computational experience is discussed along with some applications.
Inequalities for Stochastic Nonlinear Programming Problems
Authors: Mangasarian O. L. , Rosen J. B.
Published: November 2008

Many actual situations can be represented in a realistic manner by the two-stage stochastic nonlinear programming problem MinxEminy[φ(x) + ψ(y)] subject to g(x) + h(y) ≧ b, where b is a random vector with a known distribution, and E denotes expectation taken with respect to the distribution of b. Madansky has obtained upper and lower bounds on the optimum solution to this two-stage problem for the completely linear case. In the present paper these results are extended, under appropriate convexity, concavity, and continuity conditions, to the two-stage nonlinear problem. In many cases of practical interest the calculation of these bounds will require only slightly more effort than two solutions of a deterministic problem of the same size, that is, a problem with a known constant value for the vector b. A small nonlinear numerical example illustrates the calculation of these bounds. For this example the bounds closely bracket the optimum solution to the two-stage problem.
Letter to the Editor—Examples Relating to the Simplex Method
Authors: Goldman A. J. , Kleinman Daniel
Published: November 2008

An example is given showing that the most common variant of the simplex algorithm does not satisfy a condition conjectured by Saaty in an analysis of the maximum possible number of iterations. Situations are exhibited in which the simplex method encounters all vertices of the constraint polyhedron.
An Analytical Study of the PERT Assumptions
Authors: MacCrimmon Kenneth R. , Ryavec Charles A.
Published: November 2008

This paper presents the results of a mathematical analysis of the standard assumptions used in PERT calculations. The objectives of this analysis were four-fold: (1) to pull together the mathematical aspects of the PERT model, (2) to suggest relevant analytic techniques, (3) to obtain an indication of the magnitude and direction of errors introduced by the assumptions, and (4) to suggest possible modifications and improvements in the model. The first part of the paper analyzes those assumptions relevant to the individual activities. Three possible sources of error are considered here: (1) the beta distribution assumption, (2) the standard deviation assumption and the approximation formula for the mean, and (3) the imprecise time estimates. The second part of the paper deals with the PERT network as a whole and analyzes the calculations underlying the project mean, standard deviation, and probability statements. The concept of relative criticalness is explored for the PERT stochastic model. Techniques for network reduction are outlined.
Letter to the Editor—On Upper Bounds for the Number of Iterations in Solving Linear Programs
Authors: Quandt Richard E. , Kuhn Harold W.
Published: November 2008

Comments on a note by T. L. Saaty (“A Conjecture Concerning the Smallest Bound on the Iterations in Linear Programming,” Opns. Res., 11, 151–153 (1963).
Stochastic Duels with Limited Ammunition Supply
Authors: Ancker C. J.
Published: November 2008

In a previous paper the ground work was laid for a new theoretical model of combat called the “stochastic duel.” The principal elements of the model were fixed kill probabilities on each round fired, a random time between rounds fired, and unlimited ammunition supply. This paper extends the solution to those more realistic cases of limited ammunition supply. The general solution (as a quadrature) is obtained and it is applied to several specific examples. The special case of finite, fixed ammunition supply is treated separately.
Priority Queues
Authors: Takács Lajos
Published: November 2008

Customers of different priorities are arriving at a counter in accordance with a Poisson process. The customers are served by a single server in order of priority and for each priority in order of arrival. Two cases are considered: (i) service with privileged interruptions and (ii) service without interruption. It is supposed that the service times are mutually independent random variables having a prescribed distribution for each priority and independent of the arrival times. In both cases (i) and (ii) a simple method is given for finding the Laplace-Stieltjes transform and the moments of the stationary distribution of the waiting time for each priority level.
Queues with Poisson Input and Hyper-Exponential Output with Finite Waiting Space
Authors: Gupta S. K. , Goyal J. K.
Published: November 2008

The present paper deals with the steady-state solution of the queuing system in which (i) units arrive according to a Poisson distribution; (ii) the queue discipline is first-come, first-served; and (iii) the service time distribution is hyper-exponential with n branches. Assuming a finite waiting space, we derive the system-size distribution and the mean number of units in the system therefrom. Results are also deduced when an infinite waiting space is allowed. Another interesting case is discussed when only the mean service rate over all the n branches is assigned. In the end we study the case when no queue is allowed.
Maximum Payloads Per Unit Time Delivered Through an Air Network
Authors: Dantzig George B. , Johnson David L.
Published: November 2008

Because the payload that an airplane can carry is a function of the longest segment of its route and differs from route to route, the usual algorithms of network flow theory will not yield the optimum flow of payload. In this paper two network algorithms are described. They determine the route of maximum payload flow per hour of flight time and the maximum steady-state payload flow through a network with capacity constraints on the nodes.
On an Integer Program for a Delivery Problem
Authors: Balinski M. L. , Quandt R. E.
Published: November 2008

An actual truck delivery problem of general applicability is stated as an integer program. The successful computational performance of Gomory's “cutting plane” algorithm for a set of nine particular problems is discussed. Finally, the structure of the general problem is shown to be a natural generalization of covering problems of graph theory.
The Use of Cumulative Sum (Cusum) Techniques for the Control of Routine Forecasts of Product Demand
Authors: Harrison P. J. , Davies O. L.
Published: November 2008

The cumulative sum technique has proved its value in process control and this paper discusses its use when applied to sales forecasting systems. The two main applications of cusum are (i) to detect when the pattern of customer demand changes, and (ii) to detect when a forecasting system is no longer adequate. The former use generally applies when demand is reasonably steady and the latter when changes are more frequent. The question of re-estimating the parameters used in the forecasting system is considered and, in particular, the problem of differentiating between a change in trend and a change in the mean level of demand is studied. Finally, it is shown how, the cusum control scheme can be simplified so that its operation is suitable for a computer.
Present State of the Lanchester Theory of Combat
Authors: Dolanský Ladislav
Published: November 2008

The mathematical models and methods of analysis of opposing forces, stemming from the original Lanchester equations are summarized in terms of two broad categories: (a) deterministic models, (b) stochastic models. The present limitations of previous methods are used to identify topics that require attention in the future.
Some Properties of Schedules for Large Projects with Limited Resources
Authors: Wiest Jerome D.
Published: November 2008

The Critical Path Method, PERT, and related techniques that make use of arrow diagrams for scheduling large projects implicitly assume that unlimited resources are available for assignment to project activities. When resources are limited, however, the usual concepts of “critical path” and “job slack” basic to these methods lose their normal meaning. Jobs may be delayed by the unavailability of resources as well as by technological orderings. A scheme for analyzing project schedules in the limited resource case is developed in this paper, with the intent of preserving for the project scheduler the operational utility of the slack concept. A new procedure for calculating slack values leads to the identification of a “critical sequence” of jobs in a certain class of project schedules—a notion analogous to that of a critical path in the unlimited resource case. Some properties of project schedules when resources are limited are explored and suggestions are made for utilizing the revised concept of slack in scheduling large projects.
Compact Book Storage in Libraries
Authors: Leimkuhler Ferdinand F. , Cox J. Grady
Published: November 2008

A method is developed for optimally shelving inventory items by size, with particular reference to large library collections. The area presented by n + 1 distinct shelf heights is minimized for any collection that can be characterized by an item-height distribution. When item-height is continuous, the necessary conditions for the extremum are recursive in the optimal shelf heights, and the solution reduces to a simple computational search. For certain distribution functions, as demonstrated in the example, an additional recursive relation between the solutions for different n further simplified the computation considerably. Geometrical representations of both the model and the solution method are presented. The maximum increase in storage capacity can be expressed generally as a simple function of the mean and the maximum item-height.
Batched Queuing Processes
Authors: Foster F. G.
Published: November 2008

General single server queues are considered with (i) arrivals in single units and batched departures, (ii) batched arrivals and departures in single units. Queue sizes at the following instants are compared: (1) just before arrivals; (2) just after departures; (3) through time. It is shown how formulas for batched queues are related to those for certain associated unit queues.
Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
Authors: Hakimi S. L.
Published: November 2008

The concepts of the “center” and the “median vertex” of a graph are generalized to the “absolute center” and the “absolute median” of a weighted graph (a graph with weights attached to its vertices as well as to its branches). These results are used to find the optimum location of a “switching center” in a communication network and to locate the best place to build a “police station” in a highway system. It is shown that the optimum location of a switching center is always at a vertex of the communication network while the best location for the police station is not necessarily at an intersection. Procedures for finding these locations are given.
Random Walks, Fire Damage Amount and Other Paretian Risk Phenomena
Authors: Mandelbrot Benoit
Published: November 2008

Being one of the oldest branches of operations research, actuarial science has accumulated a substantial store of knowledge about the risks associated with living. The present paper will discuss one such question. Although it is relative to a specific problem of fire casualty, it illustrates more generally why the Paretian distribution of incomes and fortunes should constitute “a source of anxiety for the risk theory of insurance.” Very similar mechanisms apply in many other problems.
Composition Principles for Synthesis of Optimal Multistage Processes
Authors: Mitten L. G.
Published: November 2008

Any multistage process may be constructed by a sequence of serial and/or parallel compositions. With certain restrictions on the form of the return composition function, optimal processes may be constructed in an efficient manner from optimal subprocesses. A number of simple sufficient conditions on the return functions are given and several approximation procedures are outlined.
Letter to the Editor—A Search Problem
Authors: Cameron Scott H. , Narayanamurthy S. G.
Published: November 2008

Efficient policies are discussed for a search in which it is desired to locate a point in an interval with uniform a priori probability density by repeated application of a test to determine whether the point lies to the left or right (with different associated costs) of the test point.
Letter to the Editor—A Modification of Fulkerson's PERT Algorithm
Authors: Clingen C. T.
Published: November 2008

Fulkerson has described a method for approximating expected earliest start times in a pert network in which activity durations are discrete random variables. This letter describes an extension of Fulkerson's algorithm to include the continuous case and derives a computationally feasible form for this algorithm.
Optimum Test Procedure Under Stress
Authors: Greenberg Harold
Published: November 2008

A means of scheduling a test procedure is presented when one component, for example, out of n has failed. Each component has a given probability of failure. The time to examine each component is a random variable with known probability distribution. However, there is only a limited amount of time available for search. What test procedure should be utilized to maximize the probability of locating the failed component within the given time? The problem is solved using some renewal theory results and the functional equation approach of dynamic programming.
Time Dependent Solutions to the (s, S) Inventory Problem
Authors: Greenberg Harold
Published: November 2008

The transient solution for the probability density of the stock level is found for the (s, S) inventory model. The density is found at the end of each demand period and thus the solution is for discrete time. Results are obtained for general demand where there is zero delay in delivery of orders and where there is a λ-period delay in delivery. Examples are given for exponential demand and for gamma distributed demand.
On a Generalized M/G/1 Queuing Process in Which the First Customer of Each Busy Period Receives Exceptional Service
Authors: Welch Peter D.
Published: November 2008

The following generalization of the M/G/1 queue is considered. If a customer arrives when the server is busy, his service time has a distribution function, Gb(x); while if he arrives when the server is idle, his service time has a different distribution function, Ge(x). Results are obtained that characterize the transient and asymptotic distributions of the queue size, waiting time, and waiting-plus-service time. These results are then applied to the special case of a queue with a single service time distribution function, but with additional independent delay times that have one distribution function for the customers arriving when the server is idle and another for the customers arriving when the server is busy.
Optimum Control of a System of Oversaturated Intersections
Authors: Gazis Denos C.
Published: November 2008

The problem of optimizing the control of two oversaturated traffic intersections is solved by using the semi-graphical methods employed in a previous paper for an isolated intersection. As in the case of a single intersection the optimum control involves values of the control variables that lie along edges of the control region, which in this case is defined by the permissible ranges of the green phase splits. An analytical formulation of the method using Pontryagin’s control theory is also given.
Queues for a Vehicle-Actuated Traffic Light
Authors: Darroch J. N. , Newell G. F. , Morris R. W. J.
Published: November 2008

A vehicle-actuated traffic light controls two intersecting traffic streams keeping the light green for lane i, i = 1 or 2 until any existing queue has been discharged and a headway of duration at least βı, is detected in the subsequent arrivals. The object of this paper is to investigate how one should choose the βi so as to minimize the average delay per vehicle at the intersection. A model is considered in which the arrival headways are exponentially distributed random variables, departure headways have any specified distribution, and there is a random lost time for each switch of the traffic light. Formulas are derived for the moments of the cycle times, the average wait per vehicle, and the optimal βi.
Synchronizing Traffic Signals for Maximal Bandwidth
Authors: Morgan John T. , Little John D. C.
Published: November 2008

Traffic signals can be synchronized so that a car, starting at one end of a street and traveling at preassigned speeds, can go to the other end without stopping for a red light. The portion of a signal cycle for which this is possible is called the bandwidth for that direction. Ordinarily the bandwidth in each direction is single, i.e., is not split into two or more intervals within a cycle. We solve two problems for this case: (1) Given an arbitrary number of signals along a street, a common signal period, the green and red times for each signal, and specified vehicle speeds in each direction between adjacent signals, synchronize the signals to produce bandwidths that are equal in each direction and as large as possible. (2) Adjust the synchronization to increase one bandwidth to some specified, feasible value and maintain the other as large as is then possible. The method of calculation has been programmed for a digital computer and results have been used to synchronize signals on a street in Cleveland.
Analysis of Experiments on Single-Lane Bus Flow
Authors: Rothery R. , Silver R. , Herman R. , Torner C.
Published: November 2008

The results of a series of experiments carried out to determine the characteristics of single-lane bus flow are reported. Using pairs of buses theoretical “car-following” models of single-lane traffic flow, which had been shown by previous work to be valid for automobiles, are examined for this type of heavy vehicle and found to provide a good representation of the detailed manner in which one bus follows another. Flow characteristics of buses were also determined by using platoons of up to ten buses. Both of these approaches, which can be termed microscopic and macroscopic, respectively, indicated that a single lane of buses form a stable stream of traffic and have an optimal flow of about 1,450 buses/hour at a speed of 33 miles/ hour for an expressway type facility.
Priority Rules for Runway Use
Authors: Pestalozzi Gerold
Published: November 2008

An airport runway is regarded as the service facility in a queuing mechanism, used by both landing and departing aircraft. The usual order of service gives priority to landings over departures; here service disciplines are considered assigning priorities to different classes of aircraft grouped according to required runway time. Several such priority rules are compared numerically by means of a steady-state queuing model with non-preemptive priorities. The effect of such rules on average waiting time is found to be small, but average delay cost can be reduced appreciably.
Some Problems Involving Circular and Spherical Targets
Authors: Marsaglia George
Published: November 2008

This article is concerned with some problems that occur in certain tactical considerations: how should one place k circles [spheres] in the plane [3-space] so that their union has the greatest standard normal probability measure, that is, so as to maximize the probability that a random normal point will fall in one or more of the circles [spheres]. For k > 3 the problem seems hopeless, (except for certain special situations); the case for k = 3 is still unresolved and is being worked on by a number of investigators, and the case for k = 2 is solved completely in this paper. The results for k = 2 have some practical value when applied to actual problems arising in tactical considerations, and some theoretical value, as a method of attacking the problem for k ≧ 3.
Independence in Utility Theory with Whole Product Sets
Authors: Fishburn Peter C.
Published: November 2008

One of the most important concepts in value theory or utility theory is the notion of independence among variables or additivity of values. Its importance stems from numerous multiple-criteria procedures used for rating people, products, and other things. Most of these rating procedures rely on the notion of independence (often implicitly) for their validity. However, a satisfactory definition of independence (additivity), based on multi-dimensional consequences and hypothetical gambles composed of such consequences, has not appeared. This paper therefore presents a definition of independence for cases where the set of consequences X is a product set X1 × X2 × ⋯ × Xn, each element in X being an ordered n-tuple (x1, x2, …, xn). The definition is stated in terms of indifference between special pairs of gambles formed from X. It is then shown that if the condition of the definition holds, the utility of each (x1, x2, …, xn) in X can be written in the additive form φ(x1, x2, …, xn) = φ1(x1) + φ2(x2) + ⋯ + φn(xn), where φi is a real-valued function defined on the set Xi, i = 1, 2, …, n. The development is free of any specific assumptions about φ (e.g., continuity, differentiability) except that it be a von Neumann-Morgenstern utility function, and places no restrictions on the natures of the Xi.
Distribution of the Time Through a Directed, Acyclic Network
Authors: Martin J. J.
Published: November 2008

Let there be associated with each arc of a directed, acyclic network a random variable, conveniently referred to as the arc passage time. It is assumed that the arc passage times are independent and have a finite range. A method is presented for the efficient computation of the density function of the passage time from source to sink of this network, under the restriction that the arc density functions are polynomials. In particular, an algorithm is described that reduces a series-parallel network to a single arc whose density function is that of the time through the original network. The specialization of this algorithm to the class of polynomial density functions leads to a detailed examination of the convolution operation for polynomials. Finally, a method is presented whereby any directed, acyclic network can be transformed to series-parallel form, permitting application of a modified version of the series-parallel algorithm. These techniques are used to find the probability that an arc is on the critical path and a numerical example is presented.
Solution of Large-Scale Transportation Problems Through Aggregation
Authors: Balas Egon
Published: November 2008

From a large-scale transportation problem (I) a smaller one (II) is derived by the aggregation of origins (destinations). A procedure is given to find an optimal solution X to problem I, starting from an optimal solution Y to problem II, and considering at each step only a small part of the orginal problem's data. While the proposed method is applicable to any transportation problem, its efficiency increases with (a) the size of the problem, and (b) the unevenness of the territorial distribution of origins (destinations).
Analysis of Decisions with Incomplete Knowledge of Probabilities
Authors: Fishburn Peter C.
Published: November 2008

This paper discusses the application of personalistic decision theory in a typical setting of decision making under uncertainty. The criterion for choice of strategy is maximization of expected utility. In this setting it is often difficult to obtain very precise measurements of the decision maker's probabilities on the states of nature. We therefore pay particular attention to several “imprecise” measures of probability, including sets of inequalities and bounds, and see how this information may be used in trying to determine an ordering or partial ordering of the expected utilities of the alternative strategies. At the end of the paper we note how, in practice, one may try to obtain the measures of probability presented herein.
Markovian Dependence in Utility Theory with Whole Product Sets
Authors: Fishburn Peter C.
Published: November 2008

This paper takes the notion of Markovian dependence, so well-known in the study of stochastic processes, and uses it in a study of utility theory for sequential processes. Markovian dependence in the utility sense is defined on the basis of indifference between special types of gambles for several sequential processes. Theorems that state how the basic utility function may be broken up into an additive form under Markovian dependence are presented. In addition, the notion of stationary transition value mechanisms is explored in the context of completely homogeneous sequential decision processes.
Clustering of Stock Prices
Authors: Niederhoffer Victor
Published: November 2008

This study contains data that throw substantial doubt upon the applicability of the random walk model to stock prices. Samples of the books of the specialist indicate that stock market decision makers place their limit and stop orders at numbers with which they are accustomed to deal. Congestion of limit orders, in combination with the specialist's reluctance to trade for his own account, creates a situation where higher priced issues trade mainly at the integers. Six samples of two hundred low priced issues unchanged for the day, and two samples of issues stationary until noon, indicate that these prices settle at the round numbers. Intelligent trading of floor traders and specialists causes the ratio of highs to lows to be greater than 1 at 7/8 and less than 1 at 1/8.
Application of the Branch and Bound Technique to Some Flow-Shop Scheduling Problems
Authors: Ignall Edward , Schrage Linus
Published: November 2008

The branch-and-bound technique of Little, et al. and Land and Doig is presented and then applied to two flow-shop scheduling problems. Computational results for up to 9 jobs are given for the 2-machine problem when the objective is minimizing the mean completion time. This problem was previously untreated. Results for up to 10 jobs, including comparisons with other techniques, are given for the 3-machine problem when the objective is minimizing the makespan.
An Additive Algorithm for Solving Linear Programs with Zero-One Variables
Authors: Balas Egon
Published: November 2008

An algorithm is proposed for solving linear programs with variables constrained to take only one of the values 0 or 1. It starts by setting all the n variables equal to 0, and consists of a systematic procedure of successively assigning to certain variables the value 1, in such a way that after trying a (small) part of all the 2n possible combinations, one obtains either an optimal solution, or evidence of the fact that no feasible solution exists. The only operations required under the algorithm are additions and subtractions; thus round-off errors are excluded. Problems involving up to 15 variables can be solved with this algorithm by hand in not more than 3–4 hours. An extension of the algorithm to integer linear programming and to nonlinear programming is available, but not dealt with in this article.
Queuing Models with Balking, Reneging, and Interruptions
Authors: Rao S. Subba
Published: November 2008

A queuing process of the type M/G/1 is considered where units balk (refuse to join) as well as renege (depart without being serviced). The servicing of the units is subject to breakdowns caused by the arrival of “interruptions” that have to be cleared on a priority basis. Four models, models I, II, III, and IV, have been postulated and the detailed formulation and solution of one of the models is given while the results for the remaining models are quoted. The supplementary variable technique and discrete transforms have been employed in the formulation and the solution of the problem.
Optimal Policy in a Dynamic, Single Product, Nonstationary Inventory Model with Several Demand Classes
Authors: Veinott Arthur F.
Published: November 2008

A multiperiod single product nonstationary inventory problem is studied in which the system is reviewed at the beginning of each of a sequence of periods of equal length. The model has the following features. There are several classes of demand for the product in each period. The demands in different periods are independent but not necessarily identically distributed. The cost structure is nonstationary with the ordering cost being proportional to the amount ordered. Conditions are given that ensure that the base stock ordering policy is optimal and that the base stock levels in each period are easy to calculate. The results are based on the work given in the literature and on properties of stochastically ordered distributions that are developed in the paper. The case of a linear holding cost and a linear shortage cost is studied in detail.
The Busy Period of a Queue with Batch Service
Authors: Neuts M. F.
Published: November 2008

In this paper, we study the distribution of the busy period for a queue with Poisson input, in which the customers are served m at the time if there are m or more present and all at once if there are less than m present. We show that the busy period is equal to the time between successive visits to the state 0 in an imbedded semi-Markov process, associated with the queuing process. Extending an argument of L. Takács for the M/G/1 queue, we obtain the transform of the distribution of the busy period. Explicit expressions in real time may in principle be obtained, using Lagrange's expansion.
Discounted Markov Programming in a Periodic Process
Authors: Riis Jens Ove
Published: November 2008

This paper deals with a nonstationary discrete-time Markov process whose transition probabilities vary periodically in time. Each transition results in a reward that varies within the same cycle as the transition matrix. For infinite processes a policy-iteration algorithm is developed that effectively determines an optimal policy maximizing the total discounted reward. The paper represents an extension of R. A. Howard's policy-iteration technique for stationary Markov processes. A numerical example is given in which the developed iteration algorithm is demonstrated.
Nonpartisan Political Redistricting by Computer
Authors: Hess S. W. , Weaver J. B. , Siegfeldt H. J. , Whelan J. N. , Zitlau P. A.
Published: November 2008

OR volunteers developed a compart ness measure and a “warehouse-location” heuristic to draw nonpartisan, Constitutional political districts. The heuristic maps compact and contiguous districts of equal population. The minimization criterion and compactness measure is population moment of inertia—the summed squared distances from each person to his district's center. The districting method is particularly useful when legislative impasse or indifference forces courts to intervene. Federal Courts have received a computer plan for possible use in Delaware and have asked for computer districts in Connecticut.
Waiting-Time Distribution of a Multi-Server, Priority Queuing System
Authors: Davis Richard H.
Published: November 2008

An explicit formula is given for the waiting-time distribution of any number of parallel, negative-exponential servers subject to Poisson demands from any number of priority classes. The demand rates may be different for the priority classes, but the service rate is the same for all classes. The queue discipline is first-come-within-priority class sequence.
A Gradient Inequality for a Class of Nondifferentiable Functions
Authors: Eisenberg Edmund
Published: November 2008

A well known gradient inequality for differentiable convex minimands and their minima over convex sets is discussed. An analogous type of result is obtained for the class of non-differentiable convex functions of the form f(x) = atx + (xtCx)1/2 over convex polyhedral sets K = {x∣Ax ≤ b} in Euclidean n-space.
Minimum-Cost Multicommodity Network Flows
Authors: Tomlin J. A.
Published: November 2008

The minimum-cost multicommodity network flow problem is formulated in both node-arc and arc-chain form, leading to very large linear programs. The special structure of these programs is utilized in algorithms for their solution.
Scheduling to Minimize Interaction Cost
Authors: Carlson R. C. , Nemhauser G. L.
Published: November 2008

A model is developed for a scheduling problem in which several activities are competing for a limited number of facilities. It is assumed that any number of activities may be scheduled on any single facility; however there is an interaction cost corresponding to every combination of two activities scheduled on the same facility. This problem is a quadratic program with a rather special structure. An efficient algorithm is developed for determining feasible schedules that are local minima. The nonconvexity of the objective function prevents the identification of a global minimum.
Exploration for Natural Resources
Authors: Griffiths John C.
Published: November 2008

Exploration for natural resources has followed traditional trial-and-error procedures from the original prospector and burro to the latest airborne detection devices and each kind of resource tends to be associated with an individual type of search program. If the real-world objective of “making a profit” is substituted for the resource as the ultimate target of endeavor then a systems approach, in which the kind of target is immaterial and all targets are equally welcome, appears to be most efficacious. Under these circumstances systematic grid drilling is a financially feasible search program, and this conclusion is borne out by two independent simulation procedures. Drilling on a systematic grid across areas such as Kansas, or Pennsylvania and Ohio, leads to returns that appear ample to pay for both search and development costs, and to include a profit. Similarly, using the “Engel Model” for search and varying the parameter values over ranges such that some “real-world” situations must be included, also indicates that a reasonable profit is assured. Given a systematic search procedure, such as a drilling grid, then the geological information that accrues would form a sound basis for development of all the resources of an area.
The Optimal Assignment of Facilities to Locations by Branch and Bound
Authors: Gavett J. W. , Plyter Norman V.
Published: November 2008

The problem of assigning facilities to locations consists of the following: in the general case there are n fixed locations to which n facilities must be assigned. Each facility may be assigned to one and only one location. There are n! feasible assignments. The “distance” between any pair of locations is the cost of transporting a unit of material between the locations. The “traffic intensity” is the rate at which units of material are transferred between a given pair of facilities in both directions. An optimal assignment is one in which the sum of the product of distance times traffic intensity for all pairs of facility-location assignments is a minimum. The branch-and-bound technique with modifications is used to give an optimal assignment.
Reliability Considerations for a Two Element Redundant System with Generalized Repair Times
Authors: Liebowitz Burt H.
Published: November 2008

The mean time to failure for a two element, redundant repairable system is derived. The system consists of identical elements each having a constant failure rate λ and a general repair time distribution, fR(x). The increase in expected time to failure of the system over a single nonrepairable element is calculated and found to be: [Formula: see text] where LR(λ) is the Laplace transform of the probability density function of fR(x), with s equal to λ. M is plotted for elements having several different repair time distributions. For these cases M is found to be relatively independent of the distributions and primarily a function of the product λR (where R is the mean time to repair for a single element). The conclusion is drawn that redundancy and repair can greatly increase the operating time of the system described in this paper.
A Decomposition Algorithm for the Shortest-Route Problem
Authors: Mills G.
Published: November 2008

There are a number of methods for finding the shortest routes between all pairs of points in a network; even with the aid of modern electronic computers; however, it is difficult to apply these methods to large networks, partly because such an application requires a large amount of computer time but especially because it requires a very large amount of fast-access storage, capacity. The decomposition algorithm presented here is designed to facilitate the analysis of such networks; the basic idea is to decompose the network into parts, apply one of the existing (matrix) methods to each part separately, and then to reunite the parts. In addition to reducing greatly the required amount of fast-access storage that is required, the algorithm generally appreciably reduces the required computer time, provided the network is not too small.