bluuebunny/crossref_metadata_2025 huggingface dataset:
Development and Use of a Modeling System to Aid a Major Oil Company in Allocating Bidding Capital
Authors: Keefer Donald L. , Smith F. Beckley , Back Harry B.
Published: November 2008

Bidding at U.S. offshore oil and gas lease sales is characterized by high stakes, enormous uncertainties, and many interrelated decisions. The Lease Bidding Strategy System combined techniques from decision analysis, statistics, and nonlinear optimization to provide information and insights to management responsible for bidding at Gulf Oil Corporation. It was used prior to every major federal lease sale from September 1980 until Gulf was acquired in 1984, during which time Gulf's bids exceeded $1.5 billion. This paper describes the evolution and use of this system, emphasizing its impact on the organization. It describes efforts that gained acceptance for this system under difficult circumstances, and illustrates the importance of adapting methodology to problem changes over time. To our knowledge, this is the first public documentation of the long-term use by a major oil company of a system for constrained multiblock optimization of its bids and partnership shares at U.S. offshore lease sales.
Computing Optimal Lot Sizes in the Economic Lot Scheduling Problem
Authors: Zipkin Paul H.
Published: November 2008

This paper treats a version of the Economic Lot Scheduling Problem (ELSP) in which items may be produced several times in different amounts during a cycle. We show how to compute the optimal lot sizes and cycle length, given the sequence of items in a cycle. This requires solving a parametric quadratic program, plus a few EOQ calculations. Our procedure is designed to be used along with a heuristic for selecting the sequence of items in a cycle, such as the one proposed in 1987 by G. Dobson. The two algorithms together comprise a simple, plausible heuristic for the ELSP as a whole.
Weighted-Tardiness Scheduling on Parallel Machines with Proportional Weights
Authors: Arkin Esther M. , Roundy Robin O.
Published: November 2008

In this paper, we address the problem of scheduling a number of jobs on a bank of parallel machines to minimize the total weighted tardiness, under the assumption that the weight of each job is proportional to its processing time. The version of the problem that has general weights has been shown to be strongly NP-complete. We prove this version of the problem to be NP-complete, and give a pseudopolynomial time algorithm for solving it. We study a family of simple sequencing rules in which the jobs are sequenced in increasing order of γi = di − θpi, where di is the due date of job i, pi its processing time, wi its weight, and 0 ≤ θ ≤ 1. This family of sequencing rules generalizes the earliest due date sequencing rule. We obtain bounds on the ratio [Cγ · C*]/[Σiwipi], where Cγ and C* are the costs of the heuristic and optimal schedules, respectively. The denominator is the cost of having each job be late by its own processing time. It is intended to measure what is or is not a large deviation from optimality, in absolute rather than relative terms, for the problem at hand. We also report on the results of computational experiments.
Equilibrium Modeling, Analysis and Computation: The Contributions of Stella Dafermos
Authors: Nagurney Anna
Published: November 2008

This memorial tribute to the late Stella Dafermos summarizes her contributions to equilibrium modeling, analysis, and computation, and provides a list of her published papers.
The Application of Operations Research in the Optimization of Agricultural Production
Authors: Qingzhen Zhao , Changyu Wang , Zhimin Zhang , Yunxiang Zhang , Chuanjiang Wang
Published: November 2008

This paper describes a project to develop on optimal production plan for crops and livestock in Chang Qing County, People's Republic of China. The production plan was to increase net profit without adverse effects on the environment. We set up four large-scale linear programming models, each having more than 3,000 variables and 100 constraints, for different weather conditions and combinations of crops and livestock production. We obtained optimal solutions using computers. We used game theory to work out an optimal plan least sensitive to weather variations. We used sensitivity analysis to obtain the information for production planning as a function of market prices. The project took 1 year; 20 people were involved. More than 3 million data items were used in the development of the models. The optimal production plan involved a 2-year cycle that began in September 1983. By September 1985, the net profit from crops in the county increased by 12.33% and that from livestock by 53.77%. This success opened up the study of production planning and control of the macroscopic economy in agriculture in China. Optimal production plans are being developed and improved in many parts of China.
Multi-Item Replenishment and Storage Problem (MIRSP): Heuristics and Bounds
Authors: Anily Shoshana
Published: November 2008

Automated warehouses are often faced with the problem of smoothing their stock volume over time in order to minimize the cost due to space acquisition. In this paper, we consider an infinite-horizon, multi-item replenishment problem: In addition to the usual setup and holding costs incurred by each item, an extra charge proportional to the peak stock volume at the warehouse is due. This last cost raises the need for careful coordination while making decisions on the individual item order policies. We restrict ourselves to the class of policies that follows a stationary rule for each item separately. We derive a lower bound on the optimal average cost over all policies in this class. Then we investigate the worst case of the Rotation Cycle policy. We show that depending on the problem's parameters, the Rotation Cycle policy may yield an extremely good solution but in other settings this heuristic may generate an extremely poor policy. We also develop a new heuristic whose performance is at least as good as that of the Rotation Cycle procedure, and moreover, it is guaranteed to come, independently of the problem's parameters, within no more than 41% of the optimal solution!
An (S − 1, S) Inventory System with Emergency Orders
Authors: Moinzadeh Kamran , Schmidt Charles P.
Published: November 2008

In this paper, we develop an approximate model of an inventory control system in which there exist two options for resupply, with one having a shorter lead-time. We assume that demand and the fixed ordering costs are small relative to the holding cost so that a one-for-one ordering policy is appropriate. We consider a policy for placing emergency orders that uses information about the age of outstanding orders. We derive the steady-state behavior of this policy and present some computational results.
Six (Or So) Things You Can Do with a Bad Model
Authors: Hodges James S.
Published: November 2008

Many models used in policy or systems analysis either cannot be validated in any fully adequate sense, such as by comparing them with actual data, or could adequately be validated but have not been. For example, in the area of combat analysis, the central models are arguably almost entirely unvalidated and most will never be susceptible to adequate validation. Nevertheless, such models are often used and can be used fruitfully, even though we have no theory for how to use them or how to interpret and place value on the results they produce. This paper takes a step toward providing such a theory by focusing on the logic that should govern the use of inadequately validated models and the costs and benefits of using them. To this end, it identifies and evaluates six legitimate uses to which such models can be put.
Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
Authors: Johnson David S. , Aragon Cecilia R. , McGeoch Lyle A. , Schevon Catherine
Published: November 2008

This is the second in a series of three papers that empirically examine the competitiveness of simulated annealing in certain well-studied domains of combinatorial optimization. Simulated annealing is a randomized technique proposed by S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi for improving local optimization algorithms. Here we report on experiments at adapting simulated annealing to graph coloring and number partitioning, two problems for which local optimization had not previously been thought suitable. For graph coloring, we report on three simulated annealing schemes, all of which can dominate traditional techniques for certain types of graphs, at least when large amounts of computing time are available. For number partitioning, simulated annealing is not competitive with the differencing algorithm of N. Karmarkar and R. M. Karp, except on relatively small instances. Moreover, if running time is taken into account, natural annealing schemes cannot even outperform multiple random runs of the local optimization algorithms on which they are based, in sharp contrast to the observed performance of annealing on other problems.
Optimal Assignment of Components to Parallel-Series and Series-Parallel Systems
Authors: Prasad V. Rajendra , Nair K. P. K. , Aneja Y. P.
Published: November 2008

This paper deals with the problem of assigning components to parallel-series (PS) and series-parallel (SP) systems so as to maximize the system's reliability. We assume that any component can be assigned to any position of the system and the reliability of component j is ripj if it is assigned to position i. Exploiting the nature of Schur-convex functions, an algorithm is developed to obtain an optimal assignment for PS systems. Also, a simple optimal assignment rule is derived for SP systems with only two positions in each minimal cutset and with component reliabilities invariant of positions.
Dynamic Search Games
Authors: Thomas Lyn C. , Washburn Alan R.
Published: November 2008

In these games the searcher has a sequence of looks in which to detect the target, while the target chooses a new cell after each look in the knowledge of what cells have been searched so far. Since time is of the essence and the searcher's speed is bounded, the target has a tendency to choose cells far away from the most recent look. A theory for such games is developed and used to approximate a game involving a dipping sonar.
Matchup Scheduling with Multiple Resources, Release Dates and Disruptions
Authors: Bean James C. , Birge John R. , Mittenthal John , Noon Charles E.
Published: November 2008

This paper considers the rescheduling of operations with release dates and multiple resources when disruptions prevent the use of a preplanned schedule. The overall strategy is to follow the preschedule until a disruption occurs. After a disruption, part of the schedule is reconstructed to match up with the preschedule at some future time. Conditions are given for the optimality of this approach. A practical implementation is compared with the alternatives of preplanned static scheduling and myopic dynamic scheduling. A set of practical test problems demonstrates the advantages of the matchup approach. We also explore the solution of the matchup scheduling problem and show the advantages of an integer programming approach for allocating resources to jobs.
Some Effects of Nonstationarity on Multiserver Markovian Queueing Systems
Authors: Green Linda , Kolesar Peter , Svoronos Anthony
Published: November 2008

We examine the effects of nonstationarity on the performance of multiserver queueing systems with exponential service times and sinusoidal Poisson input streams. Our primary objective is to determine when and how a stationary model may be used as an approximation for a nonstationary system. We focus on a particular question: How nonstationary can an arrival process be before a simple stationary approximation fails? Our analysis reveals that stationary models can seriously underestimate delays when the actual system is only modestly nonstationary. Other findings include confirmation and elaboration of S. M. Ross's conjecture that expected delays increase with nonstationarity, and the identification of easily computed and tight lower and upper bounds for expected delay and the probability of delay. These empirical results are based on a series of computer experiments in which the differential equations governing system behavior are solved numerically.
Operations Research in Industry: New Opportunities in a Changing World
Authors: Little John D. C.
Published: November 2008

During the birth of operations research in World War II, some of the greatest OR successes occurred when events were happening so fast that people did not have time to learn from experience. Then skilled scientific analysis often provided a critical advantage. Today an analogous situation is unfolding on a society-wide scale. Rapid technological advances are shrinking the globe, speeding social change, and offering the prospect of an improved quality of life. The potential for increased effectiveness arises amid stiff global competition. Opportunities for OR analyses that will produce organizational and societal benefits are everywhere evident. Indeed, the complexity of today's industry virtually requires OR/MS models. This paper, based on the Morse Lecture given in October 1990 at the ORSA/TIMS meeting in Philadelphia, maintains that the challenge of contributing to industrial productivity will lead OR/MS in new directions. These will include: finding methods for extracting decision making information out of massive amounts of automatically collected data; helping to shrink the time required to develop and install new products and processes; and empowering front-line workers in organizations to improve their effectiveness.
A Multilevel Analysis of Production Capabilities of the National Forest System
Authors: Hof John , Baltic Tony
Published: November 2008

This paper reports an analysis of multiresource production capabilities of the National Forest System for the purpose of national planning in the USDA Forest Service. The analysis identifies previously unrecognized limits to the productive capabilities of the National Forest System. The analysis was used by Forest Service planners to define the long-run planning problem and to develop alternative strategies for addressing that problem. We test a multilevel optimization approach and apply it to all forest system regions of the coterminous United States. We conclude that it is not feasible for the National Forest System to supply a constant proportion of all projected resource needs. Furthermore, we found that even more conservative levels of outputs require significant increases in investment and management intensity. These results have led to Forest Service program alternatives involving more reliance on other forest and rangelands and more intense multiresource management of the National Forest System. Finally, these conclusions are limited by the range of alternatives generated and outputs modeled in the National Forest planning effort.
Aggregation and Disaggregation Techniques and Methodology in Optimization
Authors: Rogers David F. , Plante Robert D. , Wong Richard T. , Evans James R.
Published: November 2008

A fundamental issue in the use of optimization models is the tradeoff between the level of detail and the ease of using and solving the model. Aggregation and disaggregation techniques have proven to be valuable tools for manipulating data and determining the appropriate policies to employ for this tradeoff. Furthermore, aggregation and disaggregation techniques offer promise for solving large-scale optimization models, supply a set of promising methodologies for studying the underlying structure of both univariate and multivariate data sets, and provide a set of tools for manipulating data for different levels of decision makers. In this paper, we develop a general framework for aggregation and disaggregation methodology, survey previous work regarding aggregation and disaggregation techniques for optimization problems, illuminate the appropriate role of aggregation and disaggregation methodology for optimization applications, and propose future research directions.
Using Common Random Numbers and Control Variates in Multiple-Comparison Procedures
Authors: Yang Wei-Ning , Nelson Barry L.
Published: November 2008

This paper considers the determination of the relative merits of two or more system designs via stochastic simulation experiments by constructing simultaneous interval estimates of certain differences in expected performance. Tukey's all-pairwise-comparisons procedure, Hsu's multiple-comparisons-with-the-best procedure, and Dunnett's multiple-comparisons-with-a-control procedure are standard methods for making such comparisons. We propose refinements for all three procedures through the use of two variance reduction techniques: common random numbers and control variates. We show that the proposed procedures are better than the standard multiple-comparison procedures in the sense that they have a larger probability of containing the true difference and, at the same time, not containing zero when a difference exists.
A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane
Authors: Bertsimas Dimitris J. , van Ryzin Garrett
Published: November 2008

We propose and analyze a generic mathematical model for dynamic, stochastic vehicle routing problems, the dynamic traveling repairman problem (DTRP). The model is motivated by applications in which the objective is to minimize the wait for service in a stochastic and dynamically changing environment. This is a departure from classical vehicle routing problems where one seeks to minimize total travel time in a static, deterministic environment. Potential areas of application include repair, inventory, emergency service and scheduling problems. The DTRP is defined as follows: Demands for service arrive in time according to a Poisson process, are independent and uniformly distributed in a Euclidean service region, and require an independent and identically distributed amount of on-site service by a vehicle. The problem is to find a policy for routing the service vehicle that minimizes the average time demands spent in the system. We propose and analyze several policies for the DTRP. We find a provably optimal policy in light traffic and several policies with system times within a constant factor of the optimal policy in heavy traffic. We also show that the waiting time grows much faster than in traditional queues as the traffic intensity increases, yet the stability condition does not depend on the system geometry.
Capacitated Vehicle Routing on Trees
Authors: Labbé Martine , Laporte Gilbert , Mercure Hélène
Published: November 2008

T = (V, E) is a tree with nonnegative weights associated with each of its vertices. A fleet of vehicles of capacity Q is located at the depot represented by vertex v1. The Capacitated Vehicle Routing Problem on Trees (TCVRP) consists of determining vehicle collection routes starting and ending at the depot such that: the weight associated with any given vertex is collected by exactly one vehicle; the sum of all weights collected by a vehicle does not exceed Q; a linear combination of the number of vehicles and of the total distance traveled by these vehicles is minimized. The TCVRP is shown to be NP-hard. This paper presents lower bounds for the TCVRP based on the solutions of associated bin packing problems. We develop a linear time heuristic (upper bound) procedure and present a bound on its worst case performance. These lower and upper bounds are then embedded in an enumerative algorithm. Numerical results follow.
Stationary Waiting Time Distribution of a Queue in Which Customers Require a Random Number of Servers
Authors: Ittimakin Prawit , Kao Edward P. C.
Published: November 2008

We consider the multiserver queueing system studied originally by L. Green (1980) in which customers request service from a random number of identical servers. We provide a matrix-geometric formulation of the problem, present a simple means for computing the stationary probability vector, and propose an algorithm based on randomization for computing the waiting time distribution. We also give a numerical example and discuss issues involved in extending the formulation to include customer priority classes.
Dominance and Decomposition Heuristics for Single Machine Scheduling
Authors: Chambers Robert J. , Carraway Robert L. , Lowe Timothy J. , Morin Thomas L.
Published: November 2008

New heuristic dominance rules and a flexible decomposition heuristic are developed for the problem of minimizing weighted tardiness on a single processor. Extensive computational experience demonstrates that, when our new heuristic dominance rules were incorporated into an optimal algorithm, optimal or nearly optimal solutions were obtained quickly. In fact, solution times were orders of magnitude faster than those using the optimal algorithm alone. On larger problems, our decomposition heuristic obtained better solutions than previous heuristics. Furthermore, on 50-job problems our decomposition heuristic obtained an optimal solution over ten times more often on the average than the best competing heuristic (22% versus 2% of the time). Since both our approaches are basically relaxations of optimal solution algorithms, they could easily be adapted for use in the solution of other scheduling problems.
Block Angular Structures and the Loading Problem in Flexible Manufacturing Systems
Authors: Kouvelis Panagiotis , Lee Hau L.
Published: November 2008

Loading problems of Flexible Manufacturing Systems (FMSs) have usually been formulated as an integer program with nonlinear constraints for tool magazine capacities. The nonlinearity and integer nature of the problem results in the loading problem being difficult to solve. Conventional branch-and-bound methods have been proposed, but again the solution time can easily be excessive for moderate sized problems. In this paper, we present an alternative formulation of the FMS loading problem. Such a formulation defines more decision variables, but is able to avoid nonlinearity of the constraints. It also includes the time availabilities of the machines as additional constraints. The main feature of the formulation is that it exhibits a block angular structure. By exploiting this special structure, an efficient branch-and-bound algorithm can be developed. This algorithm has the attractive feature that the bounds of the branches can be computed through simple procedures based on the solution of linear knapsack problems. Some computational results of the algorithm are also presented.
Market and Locational Equilibrium for Two Competitors
Authors: Labbé Martine , Hakimi S. Louis
Published: November 2008

We consider a two-stage location and allocation game involving two competing firms. The firms first select the location of their facility on a network. Then the firms optimally select the quantities each wishes to supply to the markets, which are located at the vertices of the network. The criterion for optimality for each firm is maximizing its profit, which is the total revenue minus the production and transportation costs. Under reasonable assumptions regarding the revenue, the production cost and the transportation cost functions, we show that there is a Nash equilibrium for the quantities offered at the markets by each firm. Furthermore, if the quantities supplied (at the equilibrium) by each firm at each market are positive, then there is also a Nash locational equilibrium, i.e., no firm finds it advantageous to change its location.
Formulating Two-Stage Stochastic Programs for Interior Point Methods
Authors: Lustig Irvin J. , Mulvey John M. , Carpenter Tamra J.
Published: November 2008

This paper describes an approach for modeling two-stage stochastic programs that yields a form suitable for interior point algorithms. A staircase constraint structure is created by replacing first stage variables with sparse “split variables” in conjunction with side-constraints. Dense columns are thereby eliminated. The resulting model is larger than traditional stochastic programs, but computational savings are substantial—over a tenfold improvement for the problems tested. A series of experiments with stochastic networks drawn from financial planning demonstrates the attained efficiencies. Comparisons with MINOS and the dual block angular stochastic programming model are provided as benchmarks. The split variable approach is applicable to general two-stage stochastic programs and other dual block angular models.
Decentralization for Multidivision Enterprises
Authors: van de Panne Cornelis
Published: November 2008

The paper deals with the organization of decision making for multidivision enterprises. If decisions can be represented by linear programming models with divisions sharing resources, an organization is proposed with one division or a combination of these setting resource prices, while the remaining ones determine quantities. The role of each division is determined by the numerical coefficient values as well as the models' structure. This approach is related to, but quite different from, the Dantzig–Wolfe decomposition principle. Interactions between divisions are like ordinary commercial transactions with one party setting the price and the other the quantity traded. The usefulness of this organizational structure depends on its stability for expected variations of model data, which can be determined by parametric variations and simulations. These concepts are applied to a model by R. M. Burton and B. Obel to decide whether the M-form or the U-form organization is preferable. For central values of the model data the M-form turns out to be appropriate, and remains valid for large variations of the coefficients. A comparison with Dantzig–Wolfe decomposition indicates that the proposed approach has significant advantages.
Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date
Authors: Hall Nicholas G. , Kubiak Wieslaw , Sethi Suresh P.
Published: November 2008

A companion paper (Part I) considers the problem of minimizing the weighted earliness and tardiness of jobs scheduled on a single machine around a common due date, d, which is unrestrictively late. This paper (Part II) considers the problem of minimizing the unweighted earliness and tardiness of jobs, allowing the possibility that d is early enough to constrain the scheduling decision. We describe several optimality conditions. The recognition version of the problem is shown to be NP-complete in the ordinary sense, confirming a well known conjecture. Moreover, this complexity definition is precise, since we describe a dynamic programming algorithm which runs in pseudopolynomial time. This algorithm is also extremely efficient computationally, providing an improvement over earlier procedures, of almost two orders of magnitude in the size of instance that can be solved. Finally, we describe a special case of the problem which is polynomially solvable.
Truncation of Markov Chains with Applications to Queueing
Authors: van Dijk Nico M.
Published: November 2008

State-space truncation is frequently demanded for computation of large or infinite Markov chains. Conditions are given that guarantee an error bound or rate of convergence. Roughly, these conditions apply either when probabilities of large states are sufficiently small, or when transition probabilities (rates) for state increases become small in sufficiently large states. The verification of these conditions is based on establishing bounds for bias terms of reward structures. The conditions and their verification are illustrated by two nonproduct form queueing examples: an overflow model and a tandem queue with blocking. A concrete truncation and explicit error bound are obtained. Some numerical support is provided.
Methods for Solving Nonlinear Equations Used in Evaluating Emergency Vehicle Busy Probabilities
Authors: Goldberg Jeffrey , Szidarovszky Ferenc
Published: November 2008

In this paper we present two iterative methods for solving a model to evaluate busy probabilities for Emergency Medical Service (EMS) vehicles. The model considers location dependent service times and is an alternative to the mean service calibration method; a procedure, used with the Hypercube Model, to accommodate travel times and location-dependent service times. We use monotonicity arguments to prove that one iterative method always converges to a solution. A large computational experiment suggests that both methods work satisfactorily in EMS systems with low ambulance busy probabilities and the method that always converges to a solution performs significantly better in EMS systems with high busy probabilities.
Sensitivity Analysis in Minisum Facility Location Problems
Authors: Labbé Martine , Thisse Jacques-François , Wendell Richard E.
Published: November 2008

This paper considers tradeoffs between cost and perturbations of the weights in a single facility, minisum location problem over a finite set of feasible points. Specifically, the paper characterizes a tradeoff curve of variability in the weights versus the degree of optimality of a solution. The general theoretical framework includes problems of location on a tree network and location using block norms; special results are given for these cases.
V-Shaped Policies for Scheduling Deteriorating Jobs
Authors: Mosheiov Gur
Published: November 2008

A set of N jobs has to be processed on a single machine. Jobs have the same basic processing time, but the actual processing time of each job grows linearly with its starting time. A (possibly) different rate of growth is associated with each job. We show that the optimal sequence to minimize flow time is V-shaped: Jobs are arranged in descending order of growth rate if they are placed before the minimal growth rate job, and in ascending order if placed after it. Efficient (0(N log N)) asymptotically optimal heuristics are developed. Their average performance is shown to be extremely good: The average relative error over a set of 20-job problems is on the order of 10−5.
Machine Repair as a Priority Waiting-Line Problem
Authors: Phipps Thomas E.
Published: November 2008

A paper by Cobham (Cobham, A. 1954. J. Opns. Res. Soc. Am. 2 70.) in this Journal, dealing with the assignment of priorities in waiting-line problems, is taken as the basis for treatment of a particular variety of machine-repair problem in which shortest jobs, rather than first arrivals, receive highest priority. Cobham's results for the single channel case are found to be easily applicable to this type of priority assignment. These results take a particularly simple form when the priority-labeling index is allowed to assume continuous, rather than discrete, values. They apply to any case in which a one-channel facility repairs random failures from a very large population of machines.
Comments
Authors: van Voorhis W. R.
Published: November 2008

Comments on Phipps, Thomas E., Jr. 1956. Machine repair as a priority waiting-line problem. Oper. Res. 4 76–85.
A Polar-Planimeter Method for Determining the Probability of Hitting a Target
Authors: VanBrocklin G. R. , Murray P. G.
Published: November 2008

This paper presents a method of determining by means of a polar planimeter the probability of falling inside a plane area when the distribution of “hits” in the plane of this area is a normal bivariate distribution centered at some fixed point in the plane. The method presented is especially useful when the area involved is irregular.
Of Horseless Carriages, Flying Machines, and Operations Research
Authors: McCloskey Joseph F.
Published: November 2008

A Tribute to Frederick William Lanchester (1868–1946).
Optimum Ammunition Properties for Salvos
Authors: Walsh John E.
Published: November 2008

Calculation of the probability of kill from firing a salvo of ammunition rounds often is a very complicated and time-consuming problem. Thus there is a tendency to sacrifice realism to obtain greater mathematical simplicity. There are, however, some worthwhile salvo-firing problems where realism and mathematical simplicity are both attainable. Let the salvo size, the lethality properties of the ammunition, the shape and vulnerability properties of the target, and the probability properties of the salvo-aiming system against this target all be arbitrary but given. Consider determination of the maximum salvo kill-probability value obtainable through use of the optimum hit-location probability distribution for the ammunition rounds. Evaluation of this maximum salvo kill probability, and of the corresponding optimum round-hit-location probability distribution, is the problem analyzed in this paper. Although this problem is solved for a very general class of situations, the computations required are not extensive. The results derived also can be used to indicate the effects on salvo kill probability of salvo size, target shape and vulnerability distribution, target maneuver, fire-control-system properties, etc.
Queuing with Special Service
Authors: Koenigsberg Ernest
Published: November 2008

Queuing with special service is defined as queuing where there are several types of units to be serviced, some of which may only be serviced at certain service points while others may be serviced at all points. The simplest system of this type (only one type of special service is offered at m of the a service points) is discussed. It is shown that service is poorer (as measured by delay time and delay probabilities) for both normal and special units than that obtained in the ordinary queue situation. Methods for formulating the equations for exponential and constant holding times are discussed and two rough approximations that yield reasonable values for the delays and delay probabilities of the special units are described. An example of the rough approximations is illustrated.
The Development of Operations Research as a Science
Authors: Ackoff Russell L.
Published: November 2008

The development (rather than the history) of operations research as a science consists of the development of its methods, concepts, and techniques. Operations research is neither a method nor a technique, it is or is becoming a science and as such is defined by a combination of the phenomena it studies, its methods, and its techniques. Invited paper given at the Eighth National Meeting of the Society in Ottawa, Canada, on January 9, 1956.
Fallacies in Operations Research
Authors: Koopman B. O.
Published: November 2008

Address presented to the Fourth Annual Meeting of the Operations Research Society of America on May 10, 1956. Prepared comments to this address were made by Charles Hitch and Glen Camp. Hitch's comments are printed at the end of this paper.
The Design of Military Supply Tables for Spare Parts
Authors: Geisler M. A. , Karr H. W.
Published: November 2008

This paper presents a technique for designing supply tables of spare parts which differs appreciably from those methods historically used in the military services. For a given size of table, the technique seeks that supply table which will minimize the expected number of shortages to be encountered during a given period of supply activity. A supply table is a pre-assembled group of spare parts to be used for a specified period without outside support. The proposed method makes use of probability distributions to represent future demand for spare parts, and considers the per-unit size of each part explicitly in designing the table. The computations give the quantity of each part to be included in the table, consistent with the specified size of the table. It also discusses how to compute follow-on supply tables. These are also pre-assembled, and are intended to support supply activity for a period following the use of the initial supply tables. The technique given for follow-on tables is very similar to that used for initial tables.
The Theory of Search. II. Target Detection
Authors: Koopman B. O.
Published: November 2008

“Kinematic bases,” the first paper of this series, discussed the geometric and kinematic factors involved in search—the positions, motions, and contacts of observers and targets. Probability was introduced only in assuming specific relative positions for the observer and target.

The present paper discusses the uncertainties inherent in the act of detection under various specific conditions of contact. In the course of the discussion a body of methods for applying probability to problems of detection is developed. It must be emphasized, however, that these methods are conditioned by the particular situation in the case of visual detection because the different elementary acts of looking or “glimpses” are essentially independent trials. The reason for the distinction follows.
Allocation of Sales Effort in the Lamp Division of the General Electric Company
Authors: Waid Clark , Clark Donald F. , Ackoff Russell L.
Published: November 2008

One of the authors of this paper was requested by the editor of Operations Research to prepare a more technical presentation of a case study he had published in 1955 (Russell L. Ackoff, “The Allocation of Sales Effort,” Proceedings of the Conference on What Is Operations Research Accomplishing in Industry? Case Institute of Technology, April, 1955.). This request came shortly after the Conference on Operations-Research Education at The Johns Hopkins University in March of 1956. At this conference the need for detailed case histories, rather than highly rational reconstructions of OR projects, was recognized as serious in the field of education. Consequently, at the risk of boring professional analysts, but with the hope of assisting the novice, a detailed case history is presented here. It records the false starts, the blind alleys, and the tentativeness of the conclusions eventually reached. Not even those who worked on the project would do it over in the same way, knowing what they now know. The project raised more questions than it put to rest, but this, we believe, is the essence of scientific progress. Yet it should be pointed out, by way of anticipation, that even the tentative results were better than anything then available to management as a basis for decision making in the area involved. The results were used as recommended and the outcome that was forecast has occurred in the eighteen months during which they have been used.
Job Shop Scheduling by Simulated Annealing
Authors: van Laarhoven Peter J. M. , Aarts Emile H. L. , Lenstra Jan Karel
Published: November 2008

We describe an approximation algorithm for the problem of finding the minimum makespan in a job shop. The algorithm is based on simulated annealing, a generalization of the well known iterative improvement approach to combinatorial optimization problems. The generalization involves the acceptance of cost-increasing transitions with a nonzero probability to avoid getting stuck in local minima. We prove that our algorithm asymptotically converges in probability to a globally minimal solution, despite the fact that the Markov chains generated by the algorithm are generally not irreducible. Computational experiments show that our algorithm can find shorter makespans than two recent approximation approaches that are more tailored to the job shop scheduling problem. This is, however, at the cost of large running times.
On a “No Arrivals” Heuristic for Single Machine Stochastic Scheduling
Authors: Fay N. A. , Glazebrook K. D.
Published: November 2008

In many contexts in which resource allocation takes place in a stochastic environment, new jobs arrive over time. Incorporation of an arrivals process into the scheduling model significantly complicates the problem of determining optimal strategies. Earlier computational studies suggest that for a large class of single machine problems often little is lost by adopting a heuristic that (essentially) ignores the arrivals process. Cases are described in which the heuristic yields an optimal strategy and analytical tools are developed that enable its evaluation. The heuristic performs well, both when arrivals are rare and when arrivals of good jobs are frequent.
A Shortest Augmenting Path Algorithm for the Semi-Assignment Problem
Authors: Kennington J. , Wang Z.
Published: November 2008

The objective of this study is to develop a shortest augmenting path algorithm for solving the semi-assignment problem and conduct an extensive computational comparison with the best alternative approaches. The algorithm maintains dual feasibility and complementary slackness and works toward satisfying primal feasibility. Effective heuristics arc used to achieve an excellent advanced start, and convergence is assured via the use of the shortest augmenting path procedure using reduced costs for arc lengths. Unlike other algorithms, such as the primal simplex or the auction algorithm, each iteration during the final phase of the procedure (also known as the end-game) achieves one additional assignment. The software implementations of our algorithm are fastest for the semi-assignment problems that we tested. Our dense code is also faster than the best software for assignment problems. In addition, the algorithm has the best polynomial worst-case running time bound that we have seen; and the memory requirements are relatively small.
An Airline Seat Management Model for a Single Leg Route When Lower Fare Classes Book First
Authors: Wollmer Richard D.
Published: November 2008

It is common practice for airlines to charge several different fares for a common pool of seats. This paper presents a model that has been used to address the problem of when to refuse booking requests for a given fare level to save the seat for a potential request at a higher fare level. This model assumes that lower fare passengers book before higher fare passengers book. This occurs quite frequently in practice, where lower fare passengers are usually vacationers and higher fare passengers are usually business travelers. In fact, many airlines mandate this practice by imposing advance booking requirements on lower fare classes to prevent business travelers from using them. We present an algorithm that finds a seat management policy that maximizes mean revenue by establishing a critical value for each fare class. Booking requests for a particular fare level are accepted if the number of empty seats is strictly greater than its critical value and rejected otherwise. This critical value is a decreasing function of the fare price and is equal to zero for the class with the highest fare.
The SML Language for Structured Modeling: Levels 1 and 2
Authors: Geoffrion Arthur M.
Published: November 2008

This is the first of two articles on the principal features of SML, a language for expressing structured models. SML is presented in terms of four “levels” of increasing expressive power; this article covers the first two levels, while the sequel covers levels 3 and 4. The lower levels, at least, are easy to learn. Both articles rely entirely on examples and give special attention to the characteristics of SML that, collectively, make it unique. The intended audience includes evaluators of other modeling languages, designers of modeling languages and systems, and those who follow the development of structured modeling.
The SML Language for Structured Modeling: Levels 3 and 4
Authors: Geoffrion Arthur M.
Published: November 2008

This is the second of two articles on the principal features of SML, a language for expressing structured models. The prior article covered levels 1 and 2. The present article covers the remaining levels, with special attention to the characteristics of SML that, collectively, make it unique. The intended audience includes evaluators of other modeling languages, designers of modeling languages and systems, and those following the development of structured modeling.
The Lessons of Flowshop Scheduling Research
Authors: Dudek R. A. , Panwalkar S. S. , Smith M. L.
Published: November 2008

This paper reviews the flowshop-sequencing research since 1954 that has been devoted to the static deterministic case in which n jobs are to be processed through a shop in which the processing times at each stage are fixed. The paper then comments on NP-completeness, the selection of criteria for optimization, and the lack of applications of this work in industry. Finally, it draws some conclusions about the possible future of sequencing research and the lessons that this area's work has to teach the rest of operations research.
A Tie-Breaking Rule for Discrete Infinite Horizon Optimization
Authors: Ryan Sarah M. , Bean James C. , Smith Robert L.
Published: November 2008

We study discrete infinite horizon optimization problems without the common assumption of a unique optimum. A method based on solution set convergence is employed for finding optimal initial decisions by solving finite horizon problems. This method is applicable to general discrete decision models that satisfy a weak reachability condition. The algorithm, together with a stopping rule, is applied to production planning and capacity expansion, and computational results are reported.
Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case
Authors: Wagelmans Albert , van Hoesel Stan , Kolen Antoon
Published: November 2008

We consider the n-period economic lot sizing problem, where the cost coefficients are not restricted in sign. In their seminal paper, H. M. Wagner and T. M. Whitin proposed an O(n2) algorithm for the special case of this problem, where the marginal production costs are equal in all periods and the unit holding costs are nonnegative. It is well known that their approach can also be used to solve the general problem, without affecting the complexity of the algorithm. In this paper, we present an algorithm to solve the economic lot sizing problem in O(n log n) time, and we show how the Wagner-Whitin case can even be solved in linear time. Our algorithm can easily be explained by a geometrical interpretation and the time bounds are obtained without the use of any complicated data structure. Furthermore, we show how Wagner and Whitin's and our algorithm are related to algorithms that solve the dual of the simple plant location formulation of the economic lot sizing problem.
A Fuel Management Model for the Airline Industry
Authors: Stroup John S. , Wollmer Richard D.
Published: November 2008

This model finds a minimum cost fuel tankering policy for an airline flight schedule based on fuel prices, station constraints and supplier constraints. A station constraint is an upper or lower bound on the amount of fuel that may be purchased at a particular station for all flights. A supplier constraint is an upper or lower bound on the amount of fuel that may be purchased from a particular supplier at all stations. The problem formulates as a linear program. However, if there are no station or supplier constraints it can be reduced to a pure network problem by a series of transformations on the constraints and variables. If there are either station or supplier constraints, but not both, it can be reduced to a generalized network problem. If both are present, the program is not a generalized network. However, the number of supplier constraints is likely to be small. When this is the case, other techniques may be used to decrease computation time. McDonnell Douglas uses this model to estimate the profit potential of various aircraft types under optimal fuel management policies. Cost savings of 5 to 6% are common.