bluuebunny/crossref_metadata_2025 huggingface dataset:
Probabilistic Analysis and Practical Algorithms for the Flow Shop Weighted Completion Time Problem
Authors: Kaminsky Philip , Simchi-Levi David
Published: November 2008

In the flow shop weighted completion time problem, a set of jobs has to be processed on m machines. Every machine has to process each one of the jobs, and every job has the same routing through the machines. The objective is to determine a sequence of the jobs on the machines so as to minimize the sum of the weighted completion times of all jobs on the final machine. In this paper, we present a characterization of the asymptotic optimal solution value for general distributions of the job processing times and weights. In particular, we show that the optimal objective value of this problem is asymptotically equivalent to certain single and parallel machine scheduling problems. This characterization leads to a better understanding of the effectiveness of the celebrated weighted shortest processing time algorithm, as well as to the development of an effective algorithm closely related to the profile fitting heuristic, which was previously utilized for flow shop makespan problems. Computational results show the effectiveness of WSPT and this modified profile fitting heuristic on a set of random test problems.
Quantum Mechanical and Human Violations of Compound Probability Principles: Toward a Generalized Heisenberg Uncertainty Principle
Authors: Bordley Robert F.
Published: November 2008

A key central tenet of decision theory is that decomposing an uncertain event into sub-events should not change the overall probability assigned to that uncertain event. As we show, both quantum physics and behavioral decision theory appear to systematically violate this principle in very similar ways. These results suggest that the structuring phase of decision analysis—which specifies how various events are decomposed—helps shape the subjective probabilities which will ultimately be assigned to those events.
Options in the Real World: Lessons Learned in Evaluating Oil and Gas Investments
Authors: Smith James E. , McCardle Kevin F.
Published: November 2008

Many firms in the oil and gas business have long used decision analysis techniques to evaluate exploration and development opportunities and have looked at recent development in option pricing theory as potentially offering improvements over the decision analysis approach. Unfortunately, it is difficult to discern the benefits of the options approach from the literature on the topic: Most of the published examples greatly oversimplify the kinds of projects encountered in practice, and comparisons are typically made to traditional discounted cash flow analysis, which, unlike the option pricing and decision analytic approaches, does not explicitly consider the uncertainty in project cash flows. In this paper, we provide a tutorial introduction to option pricing methods, focusing on how they relate to and can be integrated with decision analysis methods, and describe some lessons learned in using these methods to evaluate some real oil and gas investments.
Spatial Oligopolistic Electricity Models with Cournot Generators and Regulated Transmission Prices
Authors: Jing-Yuan Wei , Smeers Yves
Published: November 2008

An oligopoly with spatially dispersed generators and consumers and with multi-period demand is modeled in this paper. The producers are assumed to behave in a Cournot manner with regulated transmission prices. A (generalized) Nash equilibrium is sought. The story of the game is as follows. Each generator takes its rivals' output (generation, supply, and flows) and the prices for transmission services as fixed when it decides upon its output to maximize its profit; the transmission firm takes the quantities of transmission services demanded by the generators as fixed when it determines the transmission prices according to certain regulatory rules. An equilibrium of the model is a set of generation output at which no generator will obtain more profit if it unilaterally modifies its output from this set, and a set of transmission prices satisfying certain regulatory requirements. A variational inequality approach is used for computing the equilibria of the model. Using the same approach, two variants of the model, respectively based on average-cost and marginal-cost pricing for transmission services, are also formulated. This model is applied to simulate a long-run electricity market where transmission prices are regulated.
Snapshot Estimators of Recent HIV Incidence Rates
Authors: Kaplan Edward H. , Brookmeyer Ron
Published: November 2008

The recent HIV incidence rate (or hazard rate for infection) is an important quantity for use in monitoring the HIV/AIDS epidemic, evaluating HIV prevention programs, and allocating HIV prevention resources. Direct measurement of HIV incidence is difficult and time consuming, while estimating HIV incidence via backcalculation (deconvolution) using AIDS incidence data and the (presumed known) HIV incubation time distribution yields little information about recent infection. We propose a method for estimating recent HIV incidence in a population via a single sample at a single point in time. The method relies on understanding the progression of certain markers such as CD4 counts following infection. The actual formulas derived for the point and interval estimates of HIV incidence are simple and easy to use while the sample sizes needed to implement our approach are reasonable. We present two applications of our approach, comparing our results to those obtained from more conventional methods where possible.
Network-Optimized Road Pricing: Part I: A Parable and a Model
Authors: Dial Robert B.
Published: November 2008

Part I of a two-part series, this paper recites a parable and formulates a stochastic optimization model that determines optimal link tolls on a road network whose users' value of time is a random variable. The parable, introducing the problem, demonstrates the importance of the variability of the value of time. The model, cast as a variational inequality, becomes a specialized form of a bicriterion user-equilibrium traffic assignment. Its solution is a set of efficient tolls for all links in the network. These tolls induce an equilibrium traffic flow that is at once system-optimal and user-optimal—for all trips, regardless of their value of time. Part II develops a solution algorithm, gives examples, and provides performance statistics.
The U.S. Army National Guard's Mobile Training Simulators Location and Routing Problem
Authors: Murty Katta G. , Djang Philipp A.
Published: November 2008

For training National Guard units, the U.S. Army National Guard will field 21 combat vehicle training simulators called mobile trainers. Each National Guard unit must train at a station that is not farther than a specified maximum travel distance from its armory. We address the problem of finding:

• the optimum locations for the home bases for the mobile trainers,

• the locations of secondary training sites to which the mobile trainers will travel to provide training, and

• the actual routes that the mobile trainers will take to cover all these secondary training sites.

The aim is to allocate each National Guard unit to a training site within the maximum travel distance from its armory, while simultaneously minimizing the mobile trainer fleet mileage and the total distance traveled by all units.

The problem is too large and complex to solve as a single model. We apply a heuristic decomposition strategy to break the overall problem into manageable stages, developing suitable substitute objective functions for each. This approach led to a solution in which the mobile trainer fleet mileage is 72,850 miles per year: about 70% smaller than the 231,000 miles per year in the original Army's procurement plan. Our solution has been implemented (with minor modifications) by the Army.
Managing Development Risk in Product Design Processes
Authors: Ahmadi Reza , Wang Robert H.
Published: November 2008

Product development has become the focal point of industrial competition and is the cornerstone of long-term survival for most firms. One of the major management challenges in product development is to deal with development risk in the design process. In this paper we provide a strategic guideline as to how the design process should be managed and controlled. We describe how design reviews and engineering resources can be scheduled as the control mechanisms to operationally manage development risk. The methodologies developed are an integral part of a project to fundamentally restructure product design processes at Rocketdyne Division of Rockwell International, which designs and develops liquid-propellant rocket propulsion systems.
A Column Generation Approach for Large-Scale Aircrew Rostering Problems
Authors: Gamache Michel , Soumis François , Marquis Gérald , Desrosiers Jacques
Published: November 2008

This article describes a method for solving the crew rostering problem in air transportation. This problem consists of constructing personalized schedules that assign pairings, days off, and other activities to airline crew members. A generalized set partitioning model and a method using column generation have been used. This method has been adapted in a number of ways to take advantage of the nature of the problem and to accelerate solution. Numerical tests on problems from Air France have demonstrated that this method is capable of solving very large scale problems with thousands of constraints and hundreds of subproblems. The tests have also shown that these adaptations are capable of reducing solution time by a factor of about a thousand. Finally, results from this method are compared with those obtained with the method currently used at Air France.
Cramér-von Mises Variance Estimators for Simulations
Authors: Goldsman David , Kang Keebom , Seila Andrew F.
Published: November 2008

We study estimators for the variance parameter σ2 of a stationary process. The estimators are based on weighted Cramér-von Mises statistics, and certain weightings yield estimators that are “first-order unbiased” for σ2. We derive an expression for the asymptotic variance of the new estimators; this expression is then used to obtain the first-order unbiased estimator having the smallest variance among fixed-degree polynomial weighting functions. Our work is based on asymptotic theory; however, we present exact and empirical examples to demonstrate the new estimators' small-sample robustness. We use a single batch of observations to derive the estimators' asymptotic properties, and then we compare the new estimators among one another. In real-life applications, one would use more than one batch; we indicate how this generalization can be carried out.
M/M/1 Queues with Switching Costs and Hysteretic Optimal Control
Authors: Kitaev M. Yu. , Serfozo Richard F.
Published: November 2008

This paper considers an M/M/1 queueing system with dynamically controlled arrival and service rates. At each arrival or service completion epoch, a decision maker chooses a pair of arrival and service rates from a finite set, and the system operates under these rates until the next arrival or service completion. There is a switching cost for changing the rates, and there is a cost per unit time of holding customers and using the arrival and service rates. The results describe natural conditions on the costs under which an optimal policy for either the discounted-cost or average-cost criterion is a hysteretic policy. Such a policy increases the service rate and decreases the arrival rate as the queue length increases. Furthermore, the control exhibits a stickiness or resistance to change, called hysteresis, due to the switching costs.
Network-Optimized Road Pricing: Part II: Algorithms and Examples
Authors: Dial Robert B.
Published: November 2008

The conclusion of a two-part series, this paper devises an algorithm that finds a system of optimal tolls in a road network whose trips have a stochastic value of time. As formulated in Part I, the model is a variational inequality, equivalent to a specialized bicriterion equilibrium traffic assignment whose solution reflects a traffic flow simultaneously user- and system-optimal. To compute these optimal tolls, our algorithm uses restricted simplicial decomposition. It solves the subproblem (direction step) with a novel multipath traffic assignment that obviates path enumeration. It solves the master problem (averaging step) using nonlinear complementarity. For real-world applications, where the algorithm's precondition that every congested arc may have a toll is impractical, this paper enhances the model to include link-specific upper and lower bounds on tolls. This more realistic model is solved with an heuristic using the optimization algorithm to its advantage. As our performance statistics show, the algorithm's speed makes it a practical planning tool. Experiments with the heuristic support the welcome hypothesis that a few well placed and properly priced tolls can reduce traffic congestion dramatically.
Maximizing Revenues of Perishable Assets with a Risk Factor
Authors: Feng Youyi , Xiao Baichun
Published: November 2008

This article presents a risk-sensitive pricing model to maximize sales revenue of perishable commodities with fixed capacity and finite sales horizon. The model assumes a pair of predetermined prices and the Poisson demand process whose intensity is a decreasing function of price. When optimizing the expected revenue, management takes business risk into account by adding a penalty (or premium) to the objective function. We solve the continuous-time model with the exact solution in closed form. We further analyze the influence of risk attitude on optimal policies.
A Tactical Planning Model for Mixed-Model Electronics Assembly Operations
Authors: Balakrishnan Anantaram , Vanderbeck François
Published: November 2008

This paper develops an optimization model and methodology to support tactical planning in a high mix, low volume electronics assembly environment. The model assigns product families to parallel surface mount assembly lines to minimize setup cost on the placement machines while ensuring that the facilities are not overloaded. To capture the impact of product assignment decisions on setup cost, we consider a partial setup policy of mounting some components permanently on each placement machine and loading other components as needed for each product. We formulate the tactical planning problem as an integer program, and show that even the special case of minimizing the setup cost on a single placement machine, for a given assignment of products, is NP-hard. Our solution method for the general problem, based on column generation, provides both heuristic solutions and lower bounds. Two subproblems that we solve—a product selection subproblem and a setup optimization subproblem—might be independently useful for short-term production planning. Computational experience shows that the approach is effective, providing solutions that are within 1.5% of optimality on average and reducing setup costs considerably compared to a complete setup policy.
Stochastic Scheduling on Parallel Machines Subject to Random Breakdowns to Minimize Expected Costs for Earliness and Tardy Jobs
Authors: Cai Xiaoqiang , Zhou Sean
Published: November 2008

This paper addresses a stochastic scheduling problem in which a set of independent jobs are to be processed by a number of identical parallel machines under a common deadline. Each job has a processing time, which is a random variable with an arbitrary distribution. Each machine is subject to stochastic breakdowns, which are characterized by a Poisson process. The deadline is an exponentially distributed random variable. The objective is to minimize the expected costs for earliness and tardiness, where the cost for an early job is a general function of its earliness while the cost for a tardy job is a fixed charge. Optimal policies are derived for cases where there is only a single machine or are multiple machines, the decision-maker can take a static policy or a dynamic policy, and job preemptions are allowed or forbidden. In contrast to their deterministic counterparts, which have been known to be NP-hard and are thus intractable from a computational point of view, we find that optimal solutions for many cases of the stochastic problem can be constructed analytically.
An O(nm)-Time Network Simplex Algorithm for the Shortest Path Problem
Authors: Goldfarb Donald , Jin Zhiying
Published: November 2008

We present an O(nm)-time network simplex algorithm for finding a tree of shortest paths from a given node to all other nodes in a network of n nodes and m directed arcs or finding a directed cycle of negative length. The worst-case running time of this algorithm is as fast as that proved for any strongly polynomial algorithm and faster than that proved for any previously proposed simplex algorithm for this problem. We also show that this algorithm can be implemented in O(nlogn) time using O((m/logn) + n) exclusive read–exclusive write processors of a parallel random access machine.
Combined Pricing and Inventory Control Under Uncertainty
Authors: Federgruen Awi , Heching Aliza
Published: November 2008

This paper addresses the simultaneous determination of pricing and inventory replenishment strategies in the face of demand uncertainty. More specifically, we analyze the following single item, periodic review model. Demands in consecutive periods are independent, but their distributions depend on the item's price in accordance with general stochastic demand functions. The price charged in any given period can be specified dynamically as a function of the state of the system. A replenishment order may be placed at the beginning of some or all of the periods. Stockouts are fully backlogged. We address both finite and infinite horizon models, with the objective of maximizing total expected discounted profit or its time average value, assuming that prices can either be adjusted arbitrarily (upward or downward) or that they can only be decreased. We characterize the structure of an optimal combined pricing and inventory strategy for all of the above types of models. We also develop an efficient value iteration method to compute these optimal strategies. Finally, we report on an extensive numerical study that characterizes various qualitative properties of the optimal strategies and corresponding optimal profit values.
Dynamics of Two- and Three-Worker “Bucket Brigade” Production Lines
Authors: Bartholdi John J. , Bunimovich Leonid A. , Eisenstein Donald D.
Published: November 2008

We describe all possible asymptotic behavior of “bucket brigade” production lines with two or three workers, each characterized by a constant work velocity. The results suggest wariness in interpreting simulation results. They also suggest a strategy for partitioning a workforce into effective teams to staff the lines.
Variance Reduction in Simulations of Loss Models
Authors: Srikant Rayadurgam , Whitt Ward
Published: November 2008

We propose a new estimator of steady-state blocking probabilities for simulations of stochastic loss models that can be much more efficient than the natural estimator (ratio of losses to arrivals). The proposed estimator is a convex combination of the natural estimator and an indirect estimator based on the average number of customers in service, obtained from Little's law (L = λW). It exploits the known offered load (product of the arrival rate and the mean service time). The variance reduction is dramatic when the blocking probability is high and the service times are highly variable. The advantage of the combination estimator in this regime is partly due to the indirect estimator, which itself is much more efficient than the natural estimator in this regime, and partly due to strong correlation (most often negative) between the natural and indirect estimators. In general, when the variances of two component estimators are very different, the variance reduction from the optimal convex combination is about 1 − ρ2, where ρ is the correlation between the component estimators. For loss models, the variances of the natural and indirect estimators are very different under both light and heavy loads. The combination estimator is effective for estimating multiple blocking probabilities in loss networks with multiple traffic classes, some of which are in normal loading while others are in light and heavy loading, because the combination estimator does at least as well as either component estimator, and it provides improvement as well.
Rendezvous Search on the Interval and the Circle
Authors: Howard J. V.
Published: November 2008

Two people are placed randomly and independently on a street of unit length. They attempt to find each other in the shortest possible expected time. We solve this problem, assuming each searcher knows where he or she is on the street, for monotonic density functions for the initial placement (this includes the uniform pdf as a special case). This gives an example of a rendezvous search problem where there is no advantage in being allowed to use asymmetric strategies. We also solve some corresponding problems for the circle when asymmetric strategies are permitted: One of these shows that it can sometimes be optimal for one player to wait for the other to find him.
A Simple Heuristic for Computing Nonstationary (s, S) Policies
Authors: Bollapragada Srinivas , Morton Thomas E.
Published: November 2008

Nonstationary inventory problems with set-up costs, proportional ordering costs, and stochastic demands occur in a large number of industrial, distribution, and service contexts. It is well known that nonstationary (s, S) policies are optimal for such problems. In this paper, we propose a simple, myopic heuristic for computing the policies. The heuristic involves approximating the future problem at each period by a stationary one and obtaining the solution to the corresponding stationary problem. We numerically compare our heuristic with an earlier myopic heuristic and the optimal dynamic programming solution procedure. Over all problems tested, the new heuristic averaged 1.7% error, compared with 2.0% error for the old procedure, and is on average 399 times as fast as the D.P. and 2062 as fast as the old heuristic. Moreover, our heuristic, owing to its myopic nature, requires the demand data only a few periods into the future, while the dynamic programming solution needs the demand data for the entire time horizon—which are typically not available in most practical situations.
Multilevel Splitting for Estimating Rare Event Probabilities
Authors: Glasserman Paul , Heidelberger Philip , Shahabuddin Perwez , Zajic Tim
Published: November 2008

We analyze the performance of a splittingtechnique for the estimation of rare event probabilities by simulation. A straightforward estimator of the probability of an event evaluates the proportion of simulated paths on which the event occurs. If the event is rare, even a large number of paths may produce little information about its probability using this approach. The method we study reinforces promising paths at intermediate thresholds by splitting them into subpaths which then evolve independently. If implemented appropriately, this has the effect of dedicating a greater fraction of the computational effort to informative runs. We analyze the method for a class of models in which, roughly speaking, the number of states through which each threshold can be crossed is bounded. Under additional assumptions, we identify the optimal degree of splitting at each threshold as the rarity of the event increases: It should be set so that the expected number of subpaths reaching each threshold remains roughly constant. Thus implemented, the method is provably effective in a sense appropriate to rare event simulations. These results follow from a branching-process analysis of the method. We illustrate our theoretical results with some numerical examples for queueing models.
Poisson-Voronoi Spanning Trees with Applications to the Optimization of Communication Networks
Authors: Baccelli François , Zuyev Sergei
Published: November 2008

We define a family of random trees in the plane. Their nodes of level k, k= 0, …, mare the points of a homogeneous Poisson point process Πk, whereas their arcs connect nodes of level kand k+ 1, according to the least distance principle: If Vdenotes the Voronoi cell w.r.t. Πk+1with nucleus x, where xis a point of Πk+1, then there is an arc connecting xto all the points of Πkthat belong to V. This creates a family of stationary random trees rooted in the points of Πm. These random trees are useful to model the spatial organization of several types of hierarchical communication networks. In relation to these communication networks, it is natural to associate various cost functions with such random trees. Using point process techniques, like the exchange formula between two Palm measures, and integral geometry techniques, we show how to compute these average costs as functions of the intensity parameters of the Poisson processes. The formulas derived for the average value of these cost functions can then be exploited for parametric optimization purposes. Several applications to classical and mobile cellular communication networks are presented.
Routing Through Virtual Paths in Layered Telecommunication Networks
Authors: Dahl Geir , Martin Alexander , Stoer Mechthild
Published: November 2008

We study a network configuration problem in telecommunications where one wants to set up paths in a capacitated network to accommodate given point-to-point traffic demand. The problem is formulated as an integer linear programming model where 0–1 variables represent different paths. An associated integral polytope is studied, and different classes of facets are described. These results are used in a cutting plane algorithm. Computational results for some realistic problems are reported.
Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow
Authors: McCormick S. Thomas
Published: November 2008

Chen (1994) develops an attractive variant of the classical problem of preemptively scheduling independent jobs with release dates and due dates. Chen suggests that in practice one can often pay to reduce the processing requirement of a job. This leads to two parametric max flow problems. Serafini (1996) considers scheduling independent jobs with due dates on multiple machines, where jobs can be split among machines so that pieces of a single job can execute in parallel. Minimizing the maximum tardiness again gives a parametric max flow problem. A third problem of this type is deciding how many more games a baseball team can lose part way through a season without being eliminated from finishing first (assuming a best possible distribution of wins and losses by other teams). A fourth such problem is an extended selection problem of Brumelle et al. (1995a), where we want to discount the costs of “tree-structured” tools as little as possible to be able to process all jobs at a profit.

It is tempting to try to solve these problems with the parametric push-relabel max flow methods of Gallo et al. (GGT) (1989). However, all these applications appear to violate the conditions necessary to apply GGT. We extend GGT in three ways that allow it to be applied to all four of the above applications. We also consider some other applications where these ideas apply. Our extensions to GGT yield faster algorithms for all these applications.
Improved Design of Queueing Simulation Experiments with Highly Heteroscedastic Responses
Authors: Cheng Russell C. H. , Kleijnen Jack P. C.
Published: November 2008

Simulation experiments for analysing the steady-state behaviour of queueing systems over a range of traffic intensities are considered, and a procedure is presented for improving their design. In such simulations the mean and variance of the response output can increase dramatically with traffic intensity; the design has to be able to cope with this complication. A regression metamodel of the likely mean response is used consisting of two factors, namely, a low-degree polynomial and a factor accounting for the exploding mean as the traffic intensity approaches its saturation. The best choice of traffic intensities at which to make simulation runs depends on the variability of the simulation output, and this variability is estimated using analytical heavy traffic results. The optimal numbers of customers simulated at each traffic intensity are built up using a multistage procedure. The asymptotic properties of the procedure are investigated theoretically. The procedure is shown to be robust and to be more efficient than more naive procedures. A result of note is that even when the range of interest includes high traffic intensities, the highest traffic load simulated should remain well away from its upper limit; but the number of customers simulated should be concentrated at the higher traffic intensities used. Empirical results are included for simulations of a single server queue with different priority rules and for a complicated queueing network. These results support the theoretical results, demonstrating that the proposed procedure can increase the accuracy of the estimated metamodel significantly compared with more naive methods.
Inferring Balking Behavior From Transactional Data
Authors: Jones Lee K.
Published: November 2008

Balking is the act of not joining a queue because the prospective arriving customer judges the queue to be too long. We analyze queues in the presence of balking, using only the service start and stop data utilized in Larson's Queue Inference Engine (Q.I.E.). Using an extension of Larson's congestion probability calculation to include balking we present new maximum likelihood, nonparametric, and Bayesian methods for inferring the arrival rate and balking functions. The methodology is applicable to businesses that wish to estimate lost sales because of balking arising from queuing-type congestion. The techniques are applied to a small transactional data set for illustrative purposes.
Parallel Machine Scheduling by Column Generation
Authors: van den Akker J. M. , Hoogeveen J. A. , van de Velde S. L.
Published: November 2008

Parallel machine scheduling problems concern the scheduling of njobs on mmachines to minimize some function of the job completion times. If preemption is not allowed, then most problems are not only 𝒩𝒫-hard, but also very hard from a practical point of view. In this paper, we show that strong and fast linear programming lower bounds can be computed for an important class of machine scheduling problems with additive objective functions. Characteristic of these problems is that on each machine the order of the jobs in the relevant part of the schedule is obtained through some priority rule. To that end, we formulate these parallel machine scheduling problems as a set covering problem with an exponential number of binary variables, ncovering constraints, and a single side constraint. We show that the linear programming relaxation can be solved efficiently by column generation because the pricing problem is solvable in pseudo-polynomial time. We display this approach on the problem of minimizing total weighted completion time on midentical machines. Our computational results show that the lower bound is singularly strong and that the outcome of the linear program is often integral. Moreover, they show that our branch-and-bound algorithm that uses the linear programming lower bound outperforms the previously best algorithm.
A Set Partitioning Approach to the Crew Scheduling Problem
Authors: Mingozzi A. , Boschetti M. A. , Ricciardelli S. , Bianco L.
Published: November 2008

The crew scheduling problem (CSP) appears in many mass transport systems (e.g., airline, bus, and railway industry) and consists of scheduling a number of crews to operate a set of transport tasks satisfying a variety of constraints. This problem is formulated as a set partitioning problem with side constraints (SP), where each column of the SP matrix corresponds to a feasible duty, which is a subset of tasks performed by a crew. We describe a procedure that, without using the SP matrix, computes a lower bound to the CSP by finding a heuristic solution to the dual of the linear relaxation of SP. Such dual solution is obtained by combining a number of different bounding procedures.

The dual solution is used to reduce the number of variables in the SP in such a way that the resulting SP problem can be solved by a branch-and-bound algorithm. Computational results are given for problems derived from the literature and involving from 50 to 500 tasks.
Price-Directed Control of Remnant Inventory Systems
Authors: Adelman Daniel , Nemhauser George L.
Published: November 2008

Motivated by make-to-order cable manufacturing, we describe a remnant inventory system in which orders arrive for units of raw material that are produced-to-stock. As orders are satisfied, the partially consumed units of material, or remnants, are either scrapped or returned to inventory for future allocation to orders. We present a linear program that minimizes the long-run average scrap rate. Its dual prices exhibit many rational properties, including monotonicity and superadditivity. We use these prices in an integer-programming-based control scheme, which we simulate and compare with an existing control scheme previously used in practice.
Too Much of a Good Thing?
Authors: Clyman Dana R. , Walls Michael R. , Dyer James S.
Published: November 2008

This paper explores a seemingly paradoxical phenomenon associated with the use of expected-utility theory in capital-budgeting and risk-sharing decisions under uncertainity. As an investment prospect becomes better and better, decision makers using classic decision-analysis techniques may, in fact, prefer less and less of it. We explore this phenomenon in the very real context of petroleum company drilling-investment decisions and demonstrate that the phenomenon is pervasive. When we examined the prospect inventory of a major oil company, we found that an increase in the upside payoff would lead to a lower optimal working interest for the grand majority of its prospects. We also explore the underlying factors leading to this phenomenon to develop both intuition and understanding. These factors have to do with degree of risk aversion (the more risk averse you are, the less likely you are to increase your holdings of an improving prospect) and managerial perspectives on risk. Once understood, the results no longer seem surprising.
Analysis of a Sampling Control Scheme for a Perishable Inventory System
Authors: Perry David
Published: November 2008

We consider an inventory system in which both the arrival of items and the demand for those items are Poisson processes. The stored items have two phases of shelf-life. If the item has not been taken by a demand during the first phase it is inspected. With probability qit is removed and with probability p= 1 − qit is transferred to the second phase. The blood bank model inspired this study. We compute ergodic limits for the number of items in the system, the lost demands, and the two types of outdating.
The Role of Operational Gaming in Operations Research
Authors: Thomas Clayton J. , Deemer Walter L.
Published: November 2008

The scientific investigation of an actual conflict situation usually leads to the study of a simpler conflict situation that may be formulated as a game a set of rules that govern and fully determine the possible courses of conflict. The study of a game involves its formulation, its solution, and instruction in its implications. The two principal techniques employed in such study of a game are the use of analytic game theory and the use of operational gaming. It has been inadequately recognized that the analytic game-theoretic approach and the operational gaming approach, different as they are, both require the use of a model of reality. Neither deals directly with reality itself. Moreover, once reality is represented by a rigorously formulated game with a complete set of rules, its solution, though unknown, is determinate. In their efforts to find the solution of such a game, users of analytic game-theoretic methods and users of operational gaming must start from the same point, the rules of the game. The process of operational gaming suffers greatly from its lack of a rigorous method for calculating the required size of the sample of plays. This required size, though not known exactly, is far greater than is commonly suspected. Whereas chance effects require a sample of plays to be statistically adequate, competitive effects require a sample of plays to be strategically adequate. It is the latter requirement that is most often overlooked.
Bibliography on Linear Programming
Authors: Rohde F. Virginia
Published: November 2008

Although the earliest discussions of linear programming date back to the 1930's, to the work of German and Austrian mathematicians and economists such as Neisser, von Stackelberg, Schlesinger, Wald and von Neumann, the mathematics has been extensively developed only in the past six or eight years. Because of the relative newness of the subject, the literature is widely scattered, and it is rather difficult for one just starting to learn about linear programming to know where to begin.
The Distribution of the Time Required to Reduce to Some Preassigned Level a Single-Channel Queue Characterized by a Time-Dependent Poisson-Distributed Arrival Rate and a General Class of Holding Times
Authors: Luchak George
Published: November 2008

This paper provides the solution to the problem of the distribution of busy periods of the single-channel queue characterized by a time-dependent Poisson-distributed arrival rate and a general class of holding times. The notation is chosen in such a fashion that the main body of computations and mathematical analysis is identical with what was required in the solution of the general queuing equations considered in a previous paper which should be read first[4]. The solution of the problem for which the traffic intensity is constant and the holding time distribution is Pearson type III is derived in closed form in terms of the Ink functions introduced previously.
Symposium on Modern Techniques for Extremum Problems—Linear and Nonlinear Programming
Authors: Tucker A. W.
Published: November 2008

The linear-programming problem of minimizing a linear objective function subject to linear constraints (inequalities and/or equations, some variables nonnegative) is here embedded in the larger problem of minimizing a convex objective function subject to such linear constraints. The enlarged problem is analyzed by sharpened use of classical Lagrange multipliers. An important case is a quadratic objective function in which the second-degree terms are squares with nonnegative coefficients (or can be so reduced). Linear computation is possible for such quadratic programming, as exemplified classically by the Kirchhoff-Maxwell determination of the distribution of (direct) current in an electrical network. Analogies with potential theory are indicated.
Discrete-Variable Extremum Problems
Authors: Dantzig George B.
Published: November 2008

This paper reviews some recent successes in the use of linear programming methods for the solution of discrete-variable extremum problems. One example of the use of the multistage approach of dynamic programming for this purpose is also discussed.
Some Civil Defense Problems in the Nation's Capital Following Widespread Thermonuclear Attack
Authors: Bentz Richard , Chace William , Doerfer Gordon , Donaldson John , English Thomas , Graves James , Grim Paul , Gunlock David , Horowitz Jerome , Miller Leland , Small Albert
Published: November 2008

The probable conditions in Washington following widespread thermonuclear attack are assessed with respect to (1) radiation conditions in the city itself and in the surrounding areas, and (2) deaths and debris conditions in the Nation's Capital Mock attacks with thermonuclear-size bombs were made on all targets designated as critical by the FCDA within a 300-mile radius of Washington. Appropriate fallout contours were selected and oriented as to wind speed and bearing for each target. The attacks were repeated 36 times using a random sample of actual 60,000-ft wind readings. Radiation levels for the area were then compiled in terms of the per cent of time a given two-day accumulated dose would be exceeded. An attack day was selected at random and the effects of blast heat and local (close-in) fallout in Washington were added to indirect radiation effects. A comparison of the amount of time a rescue worker would have to wait (impeded by debris and radiation) to enter an area with the amount of time left to a survivor in shelter attenuating 0.9 of radiation effects was made. An area exists, in Virginia, where less than 200 r can be expected a large per cent of the time. A very small percentage of the target population will survive to be cared for in this area. It was found that present shelter is not adequate to prevent intolerable numbers of deaths Present “evacuation areas” should be re-evaluated in terms of likely radiation conditions.
Computational Aspects of Dynamic Programming
Authors: Dreyfus Stuart E.
Published: November 2008

Dynamic programming is a method of solving multi-stage decision-process problems. Several computational difficulties are characteristic of all dynamic-programming solutions. This paper will attempt to isolate the most important of these difficulties, to examine present techniques, and to suggest areas in which further developments are required.
Linear Programming Isn't Always the Answer
Authors: Debeau David E.
Published: November 2008

Linear programming has been frequently applied to the problem of finding the best mix of raw material for a particular selection of products. In applications of this type where one or more of the raw materials is nonuniform, application of linear programming can increase the cost of operation Calculation of charge for a metal melting furnace is discussed as an example.
On Warehousing Problems
Authors: Prager William
Published: November 2008

An entrepreneur operates a warehouse of a given capacity for storing a seasonal product. At the beginning of each of a number of consecutive periods (“months”), the product can be bought for storage at a known cost per unit or sold from storage at a known quantity-dependent price per unit. For a given month, the selling price per unit is supposed to have a constant value up to a certain number of units and a lesser constant value for additional units sold. What pattern of buying, storing, and selling should the entrepreneur adopt to maximize his profit?

In this paper, a warehousing problem of this kind is shown to be a generalized Hitchcock distribution problem with mixed boundary conditions and non-positive flows along certain routes. This fact suggests a simple procedure for solving problems of this kind. The procedure readily allows the inclusion of storage costs, which were neglected by Charnes and Cooper.
Digital Simulation of Complex Traffic Problems in Communications Systems
Authors: Brotman Lewis , Minker Jack
Published: November 2008

This is a report on a method that was devised for simulating on a digital computer the performance of a large, complex communications system. The communication system consisted of many interconnected switching centers, each center having a large number of trunk groups attached to it. Each trunk group has access, through the switching centers, to any other trunk group located anywhere in the system. In order to conform as closely as possible to reality, the computer was programmed to simulate the performance of a human operator(s) at each of the switching centers. A method for simulating a completely automatic switch system was also devised. The computer logic was flexible enough to account for (1) any routing doctrine (or operator procedure), (2) any type of traffic distribution (Poisson or otherwise), (3) any configuration with any interconnecting facilities, and (4) a large number of trunk group inputs. Outages of either individual lines or entire switching centers due to equipment failure were treated. For a given traffic input, system configuration, and method of servicing calls, system performance data were taken in terms of the following parameters (1) Per cent completed and lost calls at each center and for the over-all system (2) Per cent of calls lost for various reasons (e.g., excessive waiting, busyness of subscriber facilities) (3) Utilities of operators and trunk lines (4) Distribution of and average waiting time. Successful runs were made on a digital computer whose storage capacity was 1000 words, each word consisting of 12 digits.
A Queuing Model for an Inventory Problem
Authors: Karush William
Published: November 2008

The relation between lost sales and inventory level is an important problem in inventory control. An explicit mathematical solution is obtained by methods of general interest for a probabilistic model that arose in connection with consulting work for an industrial client. Customer demand for a given commodity is a Poisson process with mean rate λ, and replenishment time for restocking is random. At any moment, the constant inventory n is divided between in-stock amount n0, and inreplenishment process amount n − n0. Customer arrival when n0 > 0 results in a unit sale and the initiation of replenishment of that unit. Successive replenishment times are independent. Customer arrival when n0 = 0, results in a lost sale. The unique stationary probabilities p(n0∣n) of the states n0 (fixed n), are obtained, they are given by the Erlang congestion formula, and depend upon the replenishment time only to the extent of its mean value. A generalization is obtained where λ may be a function of the state of the system. The ratio of lost sales to total demand, given by p(0∣n), is shown to be convex decreasing in n. The problem of allocation of inventory dollars among various competing commodities, so as to minimize over-all lost sales dollars, is treated.
Determination of Feasible Shipping Schedules for a Job Shop
Authors: Karush W. , Moody L. A.
Published: November 2008

This paper is concerned with the determination of shipping schedules for commodities that are manufactured by job-shop production processes. Manufacturing requires use of various machine classes (or labor classes), we know by machine class what capacity has already been committed to production plans and, hence, what remaining capacity will be increasingly available as time goes on. The problem then is to determine shipping schedules that can be supported by this available capacity and will make good or best use of this capacity. The type of commodity considered is an end product of an interrelated series of indentured parts and subas-semblies, and the manufacture of each of these consumes machine capacity. Under realistic and simplifying assumptions involving (1) set-backs from shipping date for the manufacturing operations of indentured parts, and (2) lot quantity, the problem emerges mathematically as a linear programming problem of particular form. Exploiting this particular form, several special methods of solution are developed that are computationally much simpler than the standard simplex method, and that are of considerable use in practical problems of determining shipping schedules.