bluuebunny/crossref_metadata_2025 huggingface dataset:
First Emptiness in the Spare Parts Problem for Reparable Components
Authors: Srinivasan V. S.
Published: November 2008

This paper investigates the probability distribution of time to first emptiness in the spare parts problem for repairable components, where “r” spares are provided initially. Two cases are considered, namely, (i) when the component is constantly used, and (ii) when it is intermittently used. Expressions for the Laplace Transforms and the first two moments of the probability density functions of time to first emptiness are derived.
Letter to the Editor—Stopping Rules for Queuing Simulations
Authors: Kabak Irwin W.
Published: November 2008

In queuing simulations when service times and/or inter-arrival times are exponentially distributed it is possible to obtain independent estimates of the quantities of interest, such as the probability of a request being served immediately or the proportion of requests that are delayed more than (say) t time units. It is shown that a weighted average of estimates of the probability of being served immediately is asymptotically unbiased for two simple queuing systems; it is also shown that an unweighted average is biased for one of these systems. Because the estimates are independent, the calculation of the variance of the weighted average is simplified. Expressions are presented for the calculation of the mean and variance of the estimate of interest. This paper presents only the nucleus of an idea and indicates several areas where research should prove useful.
Lanchester Models of Guerrilla Engagements
Authors: Schaffer Marvin B.
Published: November 2008

This paper develops a set of Lanchester-type equations modeling small-force guerrilla engagements that are typical of the early stages of insurgency. These equations include the effects of supporting weapons and the discipline or morale of the troops involved. The novelty of this treatment from the mathematical point of view is the use of time-dependent weapon-efficiency coefficients. Although the models and theory are not adequate to predict the outcome of an insurgency, they should prove useful for examining the credibility of casualty claims associated with such conflict. In addition, the models provide useful insight regarding the important attack parameters of guerrilla warfare. In some cases, notably those concerning ambushes, the theory suggests new military hardware that in the past has been difficult to justify on analytical grounds.
A Helicopter Versus Submarine Search Game
Authors: Danskin John M.
Published: November 2008

How should helicopters use their dipping sonar so as to search for a submarine now submerged and attempting to escape, which had been sighted a short time before? By some approximations to reality and a shift in the point of view the problem is brought to a simple two-person zero-sum game in which one side juggles areas and the other probability distributions. The solutions are exhibited and proved to be solutions by direct application of the definition of optimal strategies for a game. The solution may be understood with very little mathematical knowledge. It turns out that the helicopters should, generally speaking, spiral inward in the relative speed circle.
A Many-Server Queue with Service Interruptions
Authors: Mitrany I. L. , Avi-Itzhak B.
Published: November 2008

A steady-state M/M/N queuing system where each server is subject to random breakdowns of exponentially distributed duration is studied and analyzed. The moment generating function of the queue size is obtained in explicit form for N≦ 2. For larger values of N a numerical method is suggested.
Some Inequalities in Queuing
Authors: Marshall K. T.
Published: November 2008

Bounds are found for various measures of performance in certain classes of the GI//G1 queue. First, the mean wait in queue is found in terms of the mean and variance of the interarrival, service, and idle distributions. Bounds on the idle time moments lead to bounds on the mean wait and number in queue. The interarrival time distribution is then assumed to have mean residual life bounded above by 1/λ (λ = arrival rate); i.e., given a time t since the last arrival, the expected time to the next arrival is no more than 1/λ. With this assumption the mean number in queue (and hence system) is bounded to within (1 + p)/2 customers. Both upper and lower bounds are tight. The stronger assumption that, given time t since the last arrival, the probability an arrival occurs in the next ▵ t is nondecreasing in t, leads to bounds on the mean queue length to within (c2a+p)/2, where ca is the coefficient of variation of the arrival distribution. Again the bounds are tight. Specializing to the D/G/1 queue the mean queue length is found to within p/2 < 1/2 customer.
An Ordering Policy for Repairable Stock Items
Authors: Allen Stephen G. , D'Esopo Donato A.
Published: November 2008

When a stock item fails, it is assumed to be repairable with a known positive probability less than one. In this case stock must be replenished on occasion with new supplies. An ordering policy of the familiar reorder point-order quantity type is considered, and expressions developed for expected shortages, inventory, and number of orders per unit of time. Because shortages within a replenishment cycle can decrease because of returns from repair, the derivation of expected shortages is of particular interest.
Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
Authors: Murty Katta G.
Published: November 2008

The Hungarian method gives an efficient algorithm for finding the minimal cost assignment. However, in some cases it may be useful to determine the second minimal assignment (i.e., the best assignment after excluding the minimal cost assignment) and in general the kth minimal assignment for k = 1, 2, …. These things can easily be determined if all the assignments can be arranged as a sequence in increasing order of cost. This paper describes an efficient algorithm for such a ranking of all the assignments. The maximum computational effort required to generate an additional assignment in the sequence is that of solving at most (n − 1) different assignment problems, one each of sizes 2, 3, …, n.
The Role of Research in Underdeveloped Countries
Authors: Ackoff Russell L.
Published: November 2008

An analysis is made of the means by which an underdeveloped country can accelerate its development. Some of the problems associated with the effective use of these means are identified and discussed. Two suggestions are made as to how these countries can be assisted by universities in developed countries and by IFORS.
Surrogate Constraints
Authors: Glover Fred
Published: November 2008

A surrogate constraint is an inequality implied by the constraints of an integer program, and designed to capture useful information that cannot be extracted from the parent constraints individually but is nevertheless a consequence of their conjunction. The use of such constraints as originally proposed by the author has recently been extended in an important way by Egon Balas and Arthur Geoffion. Motivated to take advantage of information disregarded in previous definitions of surrogate constraint strength, we build upon the results of Balas and Geoffrion to show how to obtain surrogate constraints that are strongest according to more general criteria. We also propose definitions of surrogate constraint strength that further extend the ideas of the author in 1965 by means of “normalizations,” and show how to obtain strongest surrogate constraints by reference to these definitions also.
The Use of Order Statistics in Estimation
Authors: Harter H. Leon
Published: November 2008

A survey is given of recent advances, including a number of original contributions by the author, in the use of order statistics to obtain point and interval estimates of the parameters of various statistical populations from complete and from censored samples. In a few cases estimators based on order statistics are the efficient estimators, but more often they are substitute estimators that sacrifice some efficiency in the interest of computational simplicity and/or robustness in the presence of outliers. In life testing, they are often used to obtain estimates of the parameters of the life distribution before all of the items placed on test have failed. Point estimators based on order statistics may be either best linear unbiased estimators, based on all available observations from complete or censored samples or on one or more observations chosen in some optimal manner, or maximum-likelihood estimators, based on censored samples, of a single parameter or of two or more parameters jointly. Interval estimators may be based on percentage points of order statistics or of functions of order statistics, or they may be based on asymptotic variances and covariances of maximum-likelihood estimators. A summary is given of available results, together with a list of references and examples of applications to such problems as estimating the scatter of bullets aimed at a target and the reliability of an electronic device.
Stochastic Optimization of Production Planning
Authors: Beebe J. H. , Beightler C. S. , Stark J. P.
Published: November 2008

A multistage decision problem is optimized using a new formulation of stochastic dynamic programming. The problem optimized in this paper concerns a semiconductor production process where the transitions at each work station are stochastic. The mathematical model employs at one stage a Markov decision process with an infinite number of substages and shows how this process may be compressed and handled as one stage in the larger problem.
Sufficient Conditions for Positive Recurrence and Recurrence of Specially Structured Markov Chains
Authors: Crabill Thomas B.
Published: November 2008

This paper considers a specially structured Markov chain that arises naturally in certain queuing problems. Sufficient conditions for positive recurrence and recurrence are obtained using the concept of conditional expected one-step displacement of the chain. The proof makes use of the fundamental dual theorem of linear programming. A numerical example is given showing that the sufficient conditions are not necessary. The results of this paper apply to certain aspects of previous work by Harris on “Queues with State Dependent Stochastic Service Rates,” (1967) in this Journal. Specifically, the results of this paper generalize the sufficient conditions for recurrence given by Theorems 1 and 2 of that paper.
Letter to the Editor—An Ordering Policy for Stock Items when Delivery Can be Expedited
Authors: Allen S. G. , D'Esopo D. A.
Published: November 2008

The ordering policy considered for a stock item is of the familiar reorder-point-order-quantity type, except that an additional quantity called an expediting level may be specified. When stock on hand is reduced to this level, then an outstanding order will be expedited and received in a time period R, called the expedited leadtime, which is less than the normal procurement leadtime L. Even though R and L are assumed constant, the effective leadtime becomes a random variable distributed over the interval (R, L). Expressions are given for the expected inventory, shortages, number of orders, number of expedited orders, and number of expedited units ordered, all per unit of time.
Expected Target Damage for a Salvo of Rounds with Elliptical Normal Delivery and Damage Functions
Authors: Grubbs Frank E.
Published: November 2008

In this paper we obtain a series expansion for the expected fraction of damage to a circular target when it is assumed that a salvo of n rounds is delivered onto the target area with a noncircular normal or gaussian distribution and the damage function for each round can be represented by a noncircular exponential square fall-off law. The results are easily extended to an elliptical-shaped target. The aim of the paper is to obtain explicit approximations for target damage.
Expected Coverage for Targets of Nonuniform Density
Authors: McNolty Frank
Published: November 2008

This paper presents derivations of expressions for the probability of killing a randomly located point target and for the expected coverage of an area target of variable density. Particular emphasis is placed upon a general situation in which the phase distribution is not necessarily uniform. General distributions are employed to describe the phase, radial, and component behavior of the target and from these functions the distribution of a quadratic form is derived that provides the expected coverage or kill probability. The targeting conditions include a fixed lethal radius (kill-no-kill) when the center of gravity of the weapon impact points coincides with the center of the target density and a variable lethal radius when a weapon bias is present.
Optimum Maintenance with Incomplete Information
Authors: Eckles James E.
Published: November 2008

The maintenance of a system characterized by a discrete-parameter, non-stationary, finite-state Markov process is considered. Prior to each transition the decision maker selects one of a finite number of available actions (replacements, repairs, inspections, etc.) on the basis of a time sequence of noisy state measurements. The action selected and the system's age determine the subsequent one-step transition probabilities and the conditional (on the system states) distributions of the next measurement. Costs dependent on the action selected, the system's state, and age are assigned to each possible transition. It is shown that the action that minimizes the discounted value of expected immediate and future costs (assuming optimum future actions) is determined by the system's age and the posterior distribution over the states. With this result a dynamic-programming method is presented for the calculation of optimum maintenance policies.
Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph
Authors: Teitz Michael B. , Bart Polly
Published: November 2008

The generalized vertex median of a weighted graph may be found by complete enumeration or by some heuristic method. This paper investigates alternatives and proposes a method that seems to perform well in comparison with others found in the literature.
Closed Finite Queuing Networks with Time Lags and with Several Classes of Units
Authors: Posner M. , Bernholtz B.
Published: November 2008

The authors have previously investigated a broad class of closed, finite queuing networks with time lags, in which all units were considered to be identical. In this paper, that work is extended to the treatment of systems having several classes of units in which units belonging to different classes may have different sets of service parameters at the stations, different sets of travel-time distributions between stations, and different routing procedures through the system.
Reducing the Memory Requirements of Dynamic Programming
Authors: Wong Peter J. , Luenberger David G.
Published: November 2008

This paper presents a decomposition procedure for extending the size of problems that can be solved using dynamic programming. It essentially consists of decomposing the tabular arrays of data into blocks of data, and then performing the dynamic programming calculations over the whole tabular array by calculating on each block separately.
An Approach to Zero-One Integer Programming
Authors: Cabot A. Victor , Hurter Arthur P.
Published: November 2008

By starting with an all-integer zero-one linear programming problem, it is possible to develop a modified, possibly linear, programming problem that provides a characterization of the basis corresponding to a feasible zero-one solution to the integer problem. This characterization is based on the number of variables equal to one in the feasible solution. This paper develops an approach to zero-one programming based on this characterization. The method uses the criterion function of the original problem as a constraint, and then generates a sequence of feasible zero-one solutions, each with a greater value of the objective function. The solution technique is terminated when no more feasible solutions can be found, indicating that the last feasible solution determined is the optimum.
A Note on Linear Programming and Integer Feasibility
Authors: Glover Fred
Published: November 2008

This paper proves a theorem that provides new strategies for solving integer programming problems, based on finding certain types of basic solutions to linear programs. The theorem is motivated by and extends ideas of Cabot and Hurter. An integer programming method based on the theorem is outlined.
Letter to the Editor—Comments on a Paper By Romesh Saigal: “A Constrained Shortest Route Problem”
Authors: Rosseel Marc
Published: November 2008

Romesh Saigal presents a zero-one linear program and a dynamic programming algorithm for finding the shortest route containing exactly q arcs from node 1 to node n in a network (N, A) with distances c(i,j). This note shows that the linear programming formulation and his extension based on it are defective, and that the dynamic programming algorithm can lead to suboptimal solutions, but a minor change in the dynamic programming formulation relieves the difficulty.
Letter to the Editor—A Multicommodity Max-Flow Algorithm
Authors: Grinold Richard C.
Published: November 2008

Some simplifications occur when the theory of Kornai and Liptak is applied to the multicommodity max-flow problem. This note describes the resulting algorithm and comments on some of its properties; it is flexible, easy to code, and involves simple computations. However, the technique is recommended for suboptimization because of its poor convergence properties.
Safety-First Rules under Chance-Constrained Linear Programming
Authors: Sengupta J. K.
Published: November 2008

The approach of chance-constrained linear programming is analyzed here in the context of safety-first principles based on Tchebycheff-type inequalities. The analysis attempts to define relatively distribution-free tolerance levels and the incidence of nonnormality in chance-constrained linear programming.
An Approximation for the Moments of Waiting Times
Authors: Heathcote C. R. , Winer P.
Published: November 2008

Methods are available for computing properties of the waiting time associated with a variety of single-server queuing models in the equilibrium state. Since these calculations are more difficult in the time-dependent case, this paper develops an approximation procedure applicable to a wide class of single-server queues. Specifically, it considers the moments of the waiting time Wn of the nth arriving customer of the system GI/G/1 and (given certain conditions) uses an expansion related to the central limit theorem to derive approximations to these moments. The expectation EWn is treated in some detail, particularly for the Erlang system Ek/Em/1, and numerical illustrations are given. The same arguments apply to higher moments, but the calculations become tedious and details are not given.
Letters to the Editor—Extension of Dantzig's Algorithm to Finding an Initial Near-Optimal Basis for the Transportation Problem
Authors: Russell Edward J.
Published: November 2008

This note presents a new method for finding a starting basis for transportation problems; it produces a near-optimal basis, and appears to be superior to present methods.
A Class of Discrete-Time Models for the Study of Hospital Admission Systems
Authors: Bithell J. F.
Published: November 2008

This paper presents a class of discrete-time models for the study of the control of hospital in-patient admissions. It contends that the use of non-homogeneous Markov chains is appropriate to the problem and allows a wide choice of possibilities to suit many different situations. The restrictions imposed by the Markov property are discussed and methods of generalizing the process are suggested. In particular, the way is opened for models based on a length of stay with Pascal distribution and on scheduling patients with several days' notice.
Pseudo-Boolean Programming
Authors: Hammer Peter L. , Rudeanu Sergiu
Published: November 2008

Many a problem in combinatorial operations research (including, in particular, linear and nonlinear integer programming), can be formulated with the aid of real-valued functions with bivalent (0, 1) variables. This paper surveys the methods originated and developed by the authors for solving such problems. The procedures are presented here in an improved version; the most important improvements refer to linear bivalent programming, to the determination of the “basic solutions,” etc. No proofs are given; for these as well as for various applications, the reader is referred to the authors' Boolean Methods in Operations Research and Related Areas.
Minimum Concave-Cost Solution of Leontief Substitution Models of Multi-Facility Inventory Systems
Authors: Veinott Arthur F.
Published: November 2008

The paper shows that a broad class of problems can be formulated as minimizing a concave function over the solution set of a Leontief substitution system. The class includes deterministic single- and multi-facility economic lot size, lot-size smoothing, warehousing, product-assortment, batch-queuing, capacity-expansion, investment consumption, and reservoir-control problems with concave cost functions. Because in such problems an optimum occurs at an extreme point of the solution set, we can utilize the characterization of the extreme points given in a companion paper to obtain most existing qualitative characterizations of optimal policies for inventory models with concave costs in a unified manner. Dynamic programming recursions for searching the extreme points to find an optimal point are given in a number of cases. We only give algorithms whose computational effort increases algebraically (instead of exponentially) with the size of the problem.
Maintenance and Operating Characteristics of Communication Networks
Authors: Onaga Kenji
Published: November 2008

The communication facilities of a communication network constitute a stochastic service system. To maintain such a network, an optimal distribution of the given manpower to stations is desirable, and this paper considers such a distribution under the assumption that the maintenance capability of an m-man team is mr (O ≦ r ≦ 1) times the maintenance capability of a single-man team. The method employed is the Lagrange multiplier, which, aided by charts, produces optimal numbers of service windows as well as numbers of men to be assigned. Finally, for known statistical maintenance data, the paper considers operating characteristics of the network such as average up time and down time, average number of renewals (ups or downs) in an interval [0, T], availability, restoration rate, failure rate of a connection, etc.
Optimum Allocation of Stand-by Systems
Authors: Bhattacharyya M. N.
Published: November 2008

With a view to ascertaining the optimum number of stand-by systems, this paper derives the expected cost function for operating n independent systems for a time period of length t, with s spare systems available.
Sensitivity of Bayes Procedures to the Prior Distribution
Authors: Pierce Donald A. , Folks J. Leroy
Published: November 2008

In the statistical decision problem, let p0 be a given prior probability distribution and d0 be the Bayes decision function under p0. Our basic approach is to find the nearest distribution to p0 for which the optimal decision function would lead to an expected saving of some fixed amount ϵ over using d0. Hence, for any prior distribution nearer to p0 than this one, do is ϵ-Bayes. This sensitivity analysis is considered from two viewpoints, before and after performing the experiment. These results constitute a modification and extension of some recent results by Fishburn, Murphy, and Isaacs, and we make use of their basic approach and computing algorithm. Our modifications are applicable to their problem as well.
Letter to the Editor—Toward a Unifying Theory for Integer Linear Programming
Authors: Zionts Stanley
Published: November 2008

During the last decade a great number of approaches and schemes have been proposed for solving integer linear programming problems. These range from the implicit enumeration schemes including, for example, the additive algorithm of Balas to schemes that proceed in a simplicial fashion to an optimal solution as does, for example, the All-Integer Method of Gomory. Still other approaches have been heuristic in nature and strive to achieve so-called good (not necessarily optimal) solutions. The purpose of this paper is to discuss a framework that appears to offer some potential for devising new algorithms, and, at the same time, provides a theory that helps to unify some of the previously advanced methods for solving integer linear programming problems. The framework involves the use of bounds on variables and is related to some of the author's earlier work on the Geometric Definition Method of linear programming.
Cost-Effectiveness in Urban Transportation
Authors: Dodson Edward N.
Published: November 2008

This essay is a report of a cost-effectiveness study of urban transportation that was conducted as a part of a large systems-analysis effort to investigate present and future modes of transportation within selected cities. The paper gives a comprehensive array of socio-economic cost and effectiveness measures, and presents summary procedures for the full range of investment and operating costs, social impacts, and special factors affecting the quality of urban living.
An Improved Implicit Enumeration Approach for Integer Programming
Authors: Geoffrion A. M.
Published: November 2008

This paper synthesizes the Balasian implicit enumeration approach to integer linear programming with the approach typified by Land and Doig and by Roy, Bertier, and Nghiem. The synthesis results from the use of an imbedded linear program to compute surrogate constraints that are as “strong” as possible in a sense slightly different from that originally used by Glover. A simple implicit enumeration algorithm fitted with optional imbedded linear programming machinery was implemented and tested extensively on an IBM 7044. Use of the imbedded linear program greatly reduced solution times in virtually every case, and seemed to render the tested algorithm superior to the five other implicit enumeration algorithms for which comparable published experience was available. The crucial issue of the sensitivity of solution time to the number of integer variables was given special attention. Sequences were run of set-covering, optimal-routing, and knapsack problems with multiple constraints of varying sizes up to 90 variables. The results suggest that use of the imbedded linear program in the prescribed way may mitigate solution-time dependence on the number of variables from an exponential to a low-order polynomial increase. The dependence appeared to be approximately linear for the first two problem classes, with 90-variable problems typically being solved in about 15 seconds; and approximately cubic for the third class, with 80-variable problems typically solved in less than 2 minutes. In the 35-variable range for all three classes, use of the imbedded linear program reduced solution times by a factor of about 100.
Preemptive Priority Assignment in Multichannel Systems
Authors: Brosh Israel
Published: November 2008

Customers of different priorities arrive at a system in accordance with a Poisson process. The customers are serviced by c service stations using a preemptive priority discipline. When the servicing times are exponentially distributed, this paper derives expressions for the expected waiting time for inception of service, as well as the lower and upper bounds for the expected staying time and expected number of customers of each priority class (1 ≦ p ≦ r) in the system and in the line.
Medium-Range Scheduling for a Freighter Fleet
Authors: Olson C. A. , Sorenson E. E. , Sullivan W. J.
Published: November 2008

A model of Matson Navigation Company's freighter movements has been created to schedule voyages between the West Coast and Hawaii for periods of three months. The model describes the ships and port facilities; it regards the West Coast as consisting of three port areas. Ship timings are based on average values; no stochastic variables are used. Inputs to a run include cargo forecasts and initial positions of the ships in the fleet. Decisions on ship movements are made sequentially on the basis of calculated voyage profit and service requirements. Twelve cargo classes and six port pairs are considered, but of 72 possible combinations of cargoes and port pairs, only 29 actually occur. Programming is in GPSS-III for the IBM 7094. IBM 360/30 programs were written to facilitate entry of data and also to tabulate the output in several types of management reports for easier analysis of results. A three-month period, in one-hour increments, takes six minutes to run on the 7094. The model utilizes the computer to obtain schedules in the region of optimum profit, consistent with certain rules laid down by management. The model has been used in planning activities of the current fleet and in studying requirements for the future fleet. It offers the following advantages: computational accuracy in production of medium-range schedules; incorporation of profit criteria in many schedule decisions; speed of testing many alternatives; and consequently, more responsive and satisfactory fleet scheduling than could be done by normal manual methods.
On Connections Between Zero-One Integer Programming and Concave Programming Under Linear Constraints
Authors: Raghavachari M.
Published: November 2008

Consider the zero-one integer programming problem P1i:minimize Z = c′x subject to Ax ≦ b, 0 ≦ xi ≦ 1, xj = 0 or 1, j = 1, 2, …, n, where A is an m × n matrix, c′ = (c1, …, cn), x′ = (x1, …, xn), and b is an m × 1 vector with b′ = (b1, …, bm). Assume the elements of A, b, c are all rational. This paper characterizes the feasible solutions of P1, shows that P1 is equivalent to a problem of minimizing a concave quadratic objective function over a convex set, and applies a method developed by Tul to solve such a problem to yield a procedure for the zero-one integer programming problem.
One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
Authors: Emmons Hamilton
Published: November 2008

This paper first considers the problem of sequencing n jobs on one machine to minimize total tardiness. It proves theorems that establish the relative order in which pairs of jobs are processed in an optimal schedule; frequently they permit the jobs to be completely ordered, thus solving the problem without any searching. In particular, corollaries establish more general conditions than are currently recognized under which sequencing in order of nondecreasing processing times and sequencing in order of nondecreasing due dates are optimal. In general, even large problems may be at least partially ordered to the point that very few schedules remain to be searched. These results are then partly extended to the more general criterion of minimizing a sum of identical, convex, nondecreasing functions of job tardiness, and an efficient algorithm is proposed.
Macro-Analysis of the American Educational System
Authors: Mood Alex M.
Published: November 2008

This paper presents a rudimentary model of the public school system as an input-output process. The inputs are students' own abilities and attitudes, parental support, peer support, quality of the school system, community support, and society's posture with respect to education. Outputs are various categories of academic achievement as well as social competence, responsibility, self confidence, creativeness, ethics, and ambition. All these factors must be measured by index numbers or simple indicators. The model is a set of regression equations relating outputs to inputs. Some implementation of the model has been made possible by means of data gathered in the U.S. Office of Education's Equality-of-Educational-Opportunity Survey.
GI/M/1 Priority Queue
Authors: Henderson W.
Published: November 2008

We consider customers arriving at a service facility from a finite number of priority classes and being served according to a common negative exponential distribution with mean 1/μ. The priority discipline is preemptive, i.e., an arriving customer of higher priority than the customer currently being served displaces the latter and begins service himself. Taking the interarrival times to be independent, identically distributed, positive random variables with distribution function G(x), we consider the equilibrium queue-length distribution.
Letter to the Editor—A Simpler Proof of L = λW
Authors: Eilon Samuel
Published: November 2008

The relation L = λW has been shown to hold for particular queuing systems (L = average number of customers in the system, λ = mean arrival rate, W = mean customer waiting time) and Jewell published a general proof in 1967. This note presents a simple proof that does not depend on arrival-or service-time distributions, on the number of servers in the system, or on the queuing discipline.
Letter to the Editor—Criterion Equivalence in Discrete Dynamic Programming
Authors: Lippman Steven A.
Published: November 2008

This note shows that for finite state-and-action-space Markovian decision processes, a policy is 1-optimal if and only if it is average overtaking optimal, so the two criteria are equivalent.
A Graph-Theoretic Approach to a Class of Integer-Programming Problems
Authors: Desler J. F. , Hakimi S. L.
Published: November 2008

This paper presents an efficient algorithm for finding a minimum-weight generalized matching in a weighted bipartite graph. Computational evidence is given that indicates that the time required to find a least-cost assignment of n jobs to n workers goes roughly as n2 for 10 ≦ n ≦ 50. It is shown that this algorithm can be used to solve effectively the well known transportation problem of integer programming where the objective function is convex-separable. Finally, the paper gives an algorithm that applies the same concept to a graph that is not necessarily bipartite.
Some Conditions for Ergodicity and Recurrence of Markov Chains
Authors: Pakes A. G.
Published: November 2008

This paper finds sufficient conditions for the ergodicity and recurrence of irreducible and aperiodic Markov chains. They extend some of the ones commonly used. The paper also indicates their use in discussing a certain class of queuing problem with state dependent service times.
Letter to the Editor—On the Generality of the Equation L = λW
Authors: Maxwell William L.
Published: November 2008

This note shows the general utility of this fundamental queuing relation by exploiting the basic premise used in its proof. Weighted time in system averages are related to similarly weighted system-count averages. The implications of the result for simulation use are explained.
Letter to the Editor—A Note on the Analysis of Peak-Demand Forecasts of an Electrical Utility
Authors: Lev Baruch
Published: November 2008

This note analyzes the peak-demand predictions of the Commonwealth Edison Company of Illinois in order to detect and isolate the effects of systematic factors on the distribution of prediction errors. The results show that the major factor affecting the distribution is the month for which peak demand is predicted but that the time interval between prediction and realization has only a slight effect on the prediction errors.
Letter to the Editor—The Mean Lanchester Attrition Rate
Authors: Bonder Seth
Published: November 2008

This note describes a method for obtaining the Lanchester attrition rate when, as suggested by Barfoot, it is defined as the harmonic mean of attrition rates, or, equivalently, the reciprocal of the expected time to defeat a single target.
Branch-and-Bound Methods: General Formulation and Properties
Authors: Mitten L. G.
Published: November 2008

The branch-and-bound procedure is formulated in rather general terms and necessary conditions for the branching and bounding functions are precisely specified. Results include the standard properties for finite procedures, plus several convergence conditions for infinite procedures. Discrete programming which includes integer programming and combinatorial optimization problems, is discussed and Fibonacci search is presented as an example of a nonfinite branch-and-bound procedure employing an optimal convergence rule.
Solving Certain Nonconvex Quadratic Minimization Problems by Ranking the Extreme Points
Authors: Cabot A. Victor , Francis Richard L.
Published: November 2008

Certain types of quadratic programs with linear constraints have the property that an extreme point of the convex set of feasible solutions is an optimal solution. This paper presents a procedure for solving these problems, it involves determining a related linear program having the same constraints, the extreme-point-ranking approach of Murty is then applied to this linear program to obtain an optimum solution to the quadratic program.
On a Class of Directed Graphs—With an Application to Traffic-Flow Problems
Authors: Hooi-Tong Loh
Published: November 2008

Let G be a directed graph such that even edge e of G is associated with a positive integer, called the index of e. Then G is called a network graph if, at every vertex v of G, the sum of the indices of the edges terminating at v is equal to that of the edges incident from v. This paper obtains several theorems giving necessary and sufficient conditions for v directed graph to be a network graph, and applies the results to solving some problems of smoothing traffic flow.
A Constant-Work Model for Student Attendance and Enrollment
Authors: Marshall Kneale T. , Oliver Robert M.
Published: November 2008

This paper develops a model of undergraduate student attendance that relies on five parameters, one of these being a parameter of total work, w, required to complete the degree. An enrollment forecasting method consistent with these attendance patterns is developed and compared with data for the period 1961–1966 and a cohort of 2,126 and 3,298 freshmen entering in the Fall semesters of 1955 and 1960, respectively. Under the assumptions of the model, the probability of graduation is shown to be the wth power of the conditional probability of successful completion of a unit of work, given that a student drops out or attends and successfully completes a unit of work.
Generalized Penalty-Function Concepts in Mathematical Optimization
Authors: Bellmore M. , Greenberg H. J. , Jarvis J. J.
Published: November 2008

Given a mathematical program, this paper constructs an alternate problem with its feasibility region a superset of the original mathematical program. The objective function of this new problem is constructed so that a penalty is imposed for solutions outside the original feasibility region. One attempts to choose an objective function that makes the optimal solutions to the new problem the same as the optimal solutions to the original mathematical program.
Searching for the Multiplier in One-Constraint Optimization Problems
Authors: Fox B. L. , Landi D. M.
Published: November 2008

One-constraint optimization problems are approached via Lagrange multipliers. Sequential search schemes for generating suitable trial multiplier values are compared, and it is shown that, in general, the minimax sequential search is bisection. For certain applications, it pays to design search procedures that take advantage of special structure, such as recursively defined functions. An efficient, one-pass search procedure based on bisection for a multi-item, multi-echelon inventory problem is also presented.
Computing a Bias-Optimal Policy in a Discrete-Time Markov Decision Problem
Authors: Denardo Eric V.
Published: November 2008

This paper treats a discrete-time Markov decision model with an infinite planning horizon and no discounting. A “bias-optimal” policy for this decision problem satisfies a criterion that is more selective than maximizing the gain rate. The problem of computing a bias-optimal policy, also treated by Veinott in 1966, is here parsed into a sequence of three simple Markov decision problems, each of which can be solved by linear programming or policy iteration.
An Enumeration Algorithm for Knapsack Problems
Authors: Cabot A. Victor
Published: November 2008

Enumeration techniques have been shown to be successful for solving integer linear programming problems. The purpose of this paper is to apply the enumeration philosophy to the classical knapsack problem; it shows that this approach applies quite naturally to this type of integer linear program when combined with the Fourier-Motzkin elimination method for solving linear inequalities. Some computational results are reported.
A Review of the Literature on the Missile-Allocation Problem
Authors: Matlin Samuel
Published: November 2008

This paper reviews the missile-allocation-problem literature. The problem considered is: given an existing weapon force and a set of targets, what is the optimal allocation of weapons to targets? References are organized by type, characterized by submodel, discussed, and annotated. It is proposed that this review methodology by applied to other appropriate areas.
Primal Resource-Directive Approaches for Optimizing Nonlinear Decomposable Systems
Authors: Geoffrion Arthur M.
Published: November 2008

This study presents some new results on three primal-feasible computational approaches for optimizing a system composed of interrelated subsystems. The general structure treated is the same as the principal one of the classic paper by Dantzig and Wolfe, except that convex nonlinearities are permitted, provided that the overall criterion function and coupling constraints are separable by subsystem. Each approach decentralizes the optimization by iteratively allocating system resources to the subsystems, with each subsystem computing its own optimal utilization of the given resources at each iteration. The chief obstacle to directing the resource allocation centrally toward an overall optimum is that the optimal response of each subsystem, as a function of its allowed resources, is not available explicitly. All three procedures therefore approximate or generate the optimal response functions “as needed.”
Computational Algorithms for Convex Stochastic Programs with Simple Recourse
Authors: Ziemba William T.
Published: November 2008

This paper presents computational algorithms for the solution of a class of stochastic programming problems. Let x and y represent the decision and state vectors, and suppose that x must be chosen from some set K and that y is a linear function of both x and an additive random vector ξ. If y is uniquely determined once x is chosen and ξ is observed, we say that the problem has simple recourse. The algorithms presented apply, e.g., when the preference functions h(x) and g(y) are convex, and continuously differentiable, k is a convex polytope, ξ has a distribution that satisfies mild convergence conditions, and the objective is to minimize the expectation of the sum of the two preference functions. An illustrative example of an inventory problem is formulated, and the special case when g is asymmetric, quadratic, and separable is presented in detail to illustrate the calculations involved.
Turnpike Theorems for Integer Programming Problems
Authors: Shapiro Jeremy F.
Published: November 2008

A certain class of integer programming problems, called asymptotic or steady-state, has been shown by Gomory to be cost equivalent to a group-optimization problem. This paper extends the algebraic characterization by demonstrating that there are cost-equivalent group problems for all integer programming problems. Finally, the result is interpreted from the viewpoint of dynamic programming, and this provides the turnpike theorem.
Letter to the Editor—An Experimental Investigation and Comparative Evaluation of Flow-Shop Scheduling Techniques
Authors: Ashour Said
Published: November 2008

This note is concerned with the solution of the flow-shop scheduling problem where all jobs have the same machine ordering. Because of the combinatorial nature of this problem, most practical situations remain unsolved. Various techniques such as switch and check, branch and bound with and without backtracking, modified decomposition, and rounded linear programming have been proposed by several investigators. However, no comparative evaluation of these procedures has been previously made. This note investigates the solutions obtained by these procedures considering both the quality of the solutions and the computational efficiency. Extensive experimentation has been conducted and significant results are reported. The effects of changes in the size of problems on the above criteria are also included.
How Can We Improve Operations Research?
Authors: Caywood Thomas E.
Published: November 2008

Retiring Presidential Address given at the 37th National Meeting of the Society, Washington, D.C., April 20, 1970.
Linear-Programming Solutions for Orbital-Transfer Trajectories
Authors: Waespy Charles M.
Published: November 2008

This paper describes how the relatively efficient computational techniques of linear programming can be used to obtain near-minimum fuel solutions to the problem of controlling spacecraft midcourse or terminal homing trajectories. These “orbital-transfer” maneuvers are required (a) to bring a spacecraft to a prespecified position, velocity, and time state so that its subsequent free-fall trajectory follows a desired path, or (b) to match the position and velocity of another orbiting spacecraft in order to achieve a rendezvous or station-keeping condition. Modern optimal control theory has provided means by which the necessary (and in some cases, sufficient) conditions for the optimal control function for this problem can be derived. However, each method leads to subsidiary computational requirements that have proved troublesome in practice. In view of the computational demands of optimal control theory, it appears worthwhile to study how the computational power of linear programming can be brought to bear. Therefore, this paper applies linear programming (LP) methods to the terminal guidance of an orbiting spacecraft. Typical trajectories based on linearized equations of motion are calculated. Under the assumptions made, the LP solutions minimize fuel consumption. Attention is also called to current research that is beginning to provide a more profound interconnection between optimal control theory and the mathematical programming techniques familiar to operations research and management science.
On the Optimality of Single-Server Queuing Systems
Authors: Stidham Shaler
Published: November 2008

This paper considers optimal design models for queuing systems in which the decision variables are the number of servers and the mean rate at which each serves, the total cost per unit time of operating the system is the sum of a service cost per unit time and a waiting cost per unit time, and the optimality criterion is long-run expected average cost per unit time. It is shown that a single-server system is optimal for a wide class of arrival processes and service-time distributions, and for a wide variety of waiting-cost functions.