bluuebunny/crossref_metadata_2025 huggingface dataset:
Parameter Imprecision in Finite State, Finite Action Dynamic Programs
Authors: White Chelsea C. , El-Deib Hany K.
Published: November 2008

In order to model parameter imprecision associated with a problem's reward or preference structure, we examine a finite state, finite action dynamic program having a one-step transition value-function that is affine in an imprecisely known parameter. For the finite horizon case, we also assume that the terminal value function is affine in the imprecise parameter. We assume that the parameter of interest has no dynamics, no new information about its value is received once the decision process begins, and its imprecision is described by set inclusion. We seek the set of all parameter-independent strategies that are optimal for some value of the imprecisely known parameter. We present a successive approximations procedure for solving the finite horizon case and a policy iteration procedure for determining the solution of the discounted infinite horizon case. These algorithms are then applied to a decision analysis problem with imprecise utility function and to a Markov decision process with imprecise reward structure. We also present conditions that guarantee the existence of a parameter-independent strategy that maximizes, with respect to all other parameter invariant strategies, the minimum value of its expected reward function over all possible parameter values.
Optimal Lot Sizing, Process Quality Improvement and Setup Cost Reduction
Authors: Porteus Evan L.
Published: November 2008

This paper seeks to demonstrate that lower setup costs can benefit production systems by improving quality control. It does so by introducing a simple model that captures a significant relationship between quality and lot size: while producing a lot, the process can go "out of control" with a given probability each time it produces another item. Once out of control, the process produces defective units throughout its production of the current lot. The system incurs an extra cost for rework and related operations for each defective piece that it produces. Thus, there is an incentive to produce smaller lots, and have a smaller fraction of defective units. The paper also introduces three options for investing in quality improvements: (i) reducing the probability that the process moves out of control (which yields fewer defects, larger lot sizes, fewer setups, and larger holding costs); (ii) reducing setup costs (which yields smaller lot sizes, lower holding costs, and fewer defects); and (iii) simultaneously using the two previous options. By assuming a specific form of the investment cost function for each option, we explicitly obtain the optimal investment strategy. We also briefly discuss the sensitivity of these solutions to changes in underlying parameter values. A numerical example illustrates the results.
A Cross Decomposition Algorithm for Capacitated Facility Location
Authors: Van Roy Tony J.
Published: November 2008

We present an implementation of the Cross Decomposition method to solve the capacitated facility location problem. The method unifies Benders Decomposition and Lagrangean relaxation into a single framework that involves successive solutions to a transportation problem and a simple plant location problem. Computational tests on problems with as many as 100 candidate facility locations and 200 customers provide evidence that the approach is superior to several other methods. The specialized Cross Decomposition program is, on a common set of test problems, about ten times faster than several recently developed programs. We also present a simple algorithm to strengthen Benders cuts.
Technical Note—Renormalization of Seasonals in Winters' Forecasting Systems: Is it Necessary?
Authors: McKenzie Ed
Published: November 2008

Normalizing the initial estimates of the seasonal factors in Winters' seasonal forecasting systems is a universally recommended practice. Once forecasting begins, however, the seasonal factors lose their normalization. It is often recommended that these factors be renormalized either seasonally or continuously, i.e., with every observation. We show that this latter procedure is never necessary in the case of the additive model, since a simple change in the smoothing constants can achieve the same ends. We also give a simpler and more efficient method of obtaining seasonally renormalized forecasts for this model.
Optimal Hydrocarbon Reservoir Production Policies
Authors: Lasdon Leon , Coffman Paul E. , MacDonald Robert , McFarland James W. , Sepehrnoori Kamy
Published: November 2008

This paper describes a methodology for investigating optimal production polices for hydrocarbon reservoirs by an approach that brings together reservoir simulation models and numerical optimization techniques. It describes the results of applying this methodology to a dry gas storage reservoir using a single phase, two-dimensional reservoir simulator. The paper investigates optimal production strategies for several optimization criteria and potential constraints on reservoir operations, and discusses extensions to more complex systems.
Approximation Formulations for the Single-Product Capacitated Lot Size Problem
Authors: Bitran Gabriel R. , Matsuo Hirofumi
Published: November 2008

We consider two approximation formulations for the single-product capacitated lot size problem. One formulation restricts the number of production policies and the other rounds demands up to multiples of a constant. After briefly reviewing the literature within a new framework, we discuss the relations between these approximation formulations. Next, we provide relative error bounds and algorithms for solving the approximation problems. We demonstrate that these approximation formulations require a significantly smaller number of calculations than the original formulation, and that the relative error bounds are satisfactory for practical purposes.
An Allocation and Distribution Model for Perishable Products
Authors: Federgruen Awi , Prastacos Gregory , Zipkin Paul H.
Published: November 2008

This paper presents an allocation model for a perishable product, distributed from a regional center to a given set of locations with random demands. We consider the combined problem of allocating the available inventory at the center while deciding how these deliveries should be performed. Two types of delivery patterns are analyzed: the first pattern assumes that all demand points receive individual deliveries; the second pattern subsumes the frequently occurring case in which deliveries are combined in multistop routes traveled by a fleet of vehicles. Computational experience is reported.
Scarf's State Reduction Method, Flexibility, and a Dependent Demand Inventory Model
Authors: Miller Bruce L.
Published: November 2008

We consider a finite horizon inventory model with linear holding, shortage, and ordering costs. The demand random variables are dependent, and average demand is described by an exponential smoothing formula. This model can be formulated as a two-state variable (inventory level, weighted past demands) dynamic program. Using a procedure first developed by Scarf for a Bayesian inventory model, we are able to reformulate the model as a one-state variable dynamic program, resulting in a considerable computational saving over the two-state variable formulation. We also show that this dependent demand model orders less than or equal the amount ordered by a comparable independent demand model. We establish this result under the assumption that demand represents failures that are repaired by the beginning of the next period.
Models for Design and Control of Stochastic, Multi-Item Batch Production Systems
Authors: Zipkin Paul H.
Published: November 2008

We propose an approach to modeling a production facility that makes many products in large, discrete batches, when demands and the production process are stochastic. This approach combines standard inventory and queueing submodels into classical optimization problems. The models developed in this paper to illustrate the approach represent the production facility by a single-server queueing system or by a network of queues; other systems can also be handled within the approach. The models optimize the approximate operating cost of a given facility over certain simple, plausible control policies; furthermore, the models are tractable enough to be used routinely for design studies.
Clearing Systems and (s, S) Inventory Systems with Nonlinear Costs and Positive Lead Times
Authors: Stidham Shaler
Published: November 2008

Stochastic clearing systems model many different applications, including certain bulk server queues, shuttle buses, and buffers in communication systems. We extend the characterization of the optimal parameters of a generalized stochastic clearing system (Stidham, S., Jr. 1977. Cost models for stochastic clearing systems. Opns. Res. 25 100–127.) from piece-wise linear to general convex cost-rate functions, and discuss applications to continuous-review and periodic-review (s, S) inventory models with nonlinear holding and storage costs and/or nonzero lead times. As in Stidham, we show that log-concavity of the sojourn function associated with the input process guarantees that the necessary conditions are also sufficient for optimality of the clearing parameters, which correspond to s and S in inventory examples. Our conditions are weaker and our model more general than those found in the previous literature on (s, S) inventory models.
Partial Information, Dominance, and Potential Optimality in Multiattribute Utility Theory
Authors: Hazen Gordon B.
Published: November 2008

When a multiattribute utility function is only partially specified by prior preference statements, what can be said about the relative desirability of actual alternatives? This question is addressed for the cases of additively separable cardinal utility with unknown scaling constants; multiplicatively separable cardinal utility with unknown scaling constants; and additively separable ordinal utility. We review previous approaches, and treat issues of consistency (is the prior information consistent?), dominance (does the prior preference information imply that one outcome is preferred to another?) and potential optimality (are there utility functions of the given form, consistent with prior preference information, under which a particular outcome is preference optimal?). In the additive cases, a key relationship between dominance and potential optimality may be derived. The paper concludes by presenting an example application to a well known nuclear siting study.
VARI-METRIC: Improved Approximations for Multi-Indenture, Multi-Echelon Availability Models
Authors: Sherbrooke Craig C.
Published: November 2008

Multi-indenture models for (s − 1, s) inventory policies, such as mod-metric and the Logistics Management Institute (LMI) Aircraft Availability Model, understate the delay in the repair of a higher indenture item caused by backorders on the item's lower indenture components. These models also understate the multi-echelon delay in the resupply of a base from a depot that has backorders. Consequently, the models tend to understate expected backorders and overstate expected availability of repair items. We show that it is possible to improve the accuracy of multi-indenture models in a manner similar to the way in which the metric approximation for multi-echelon availability has been improved. We do so by showing that the multi-indenture improvement for a single echelon is valid for compound Poisson demand and arbitrary repair distributions, and that the new approximation is easy to incorporate. Simulation shows that the new approximation provides a much more accurate estimate of the expected backorders. We then present the improved approximation for the combination of multi-indenture and multi-echelon, using the vari-metric model. The vari-metric estimate of backorders is very close to the “true” value from simulation, and the allocation of investment across one item group consisting of a first indenture item and its second indenture components is better than mod-metric when there is a difference.
Technical Note—A Note on Shot-Noise and Reliability Modeling
Authors: Lemoine Austin J. , Wenocur Michael L.
Published: November 2008

We discuss a reliability model that reflects the dynamic dependency between system failure and system stress. For example, the mortality rate for individuals who have had a heart attack declines with time. In particular, we use a shot-noise process to model “residual system stress,” which in turn drives a doubly stochastic Poisson process model for system failures. Intuitively, residual stress (or susceptibility to failure) may vary in a random manner yet be essentially unobservable, while system failures may be readily detectable and observable. Shot-noise distributions have a richness and subtlety that suggest untapped potential for applications. The doubly stochastic Poisson process provides a reasonable framework for modeling randomly varying rates of occurrence in a broad variety of settings.
Dynamic Nonlinear Pricing in Networks with Interdependent Demand
Authors: Dhebar Anirudh , Oren Shmuel S.
Published: November 2008

We consider the pricing decision for a new product whose consumption value increases as the network of adopters expands. This demand interdependence is a characteristic feature of telecommunications networks. The paper analyzes the case of a single supplier offering the product to a heterogeneous population. Consumers decide on network access and consumption quantity. The pricing decision consists of choosing a pricing schedule (over the dimensions of quantity and time) that maximizes the present value of a weighted sum of total surplus and producer profits, subject to the dynamics of market growth. We find that the decision can be decoupled into two nested optimization problems: (a) given some market size, what should the optimal nonlinear price schedule be? and (b) how should the price schedule be changed optimally over time? This separation enables us to solve the pricing problem. Explicit consideration of the dynamics, the discounting of future surpluses, and the extent of market growth anticipation affect not only the price and network size trajectories, but also their steady-state equilibrium values.
Alternative Models of Spatial Competition
Authors: Harker Patrick T.
Published: November 2008

The concept of a spatial price equilibrium underlies most studies of spatial movement and competition. However, this concept is based upon a notion of perfectly competitive markets that is often unrealistic for many markets, such as the markets for oil and coal, and ignores the existence of local spatial monopolies. This paper presents alternative economic models of spatial competition and shows how all of these models can be solved with essentially the same solution algorithm. Specifically, after reformulating the classical spatial price equilibrium model and two extensions of Takayama and Judge's monopoly model, we state and analyze a Cournot-Nash model and discuss solution algorithms. We then generalize these models and algorithms to multiple commodities and networks with transshipment nodes. We conclude with a brief discussion of possible extensions of this class of models and associated algorithms.
Multivariate Imperfect Repair
Authors: Shaked Moshe , Shanthikumar J. George
Published: November 2008

In this paper, we consider models of systems whose components have dependent lifelengths and are imperfectly repaired upon failure until they are scrapped. First, assuming that no more than one component can fail at a time, we study two models that describe imperfect repairs, and derive the resulting density and other probabilistic quantities of interest. We then generalize the models to cover applications in which more than one component can fail at the same time, and obtain various properties of the resulting distributions. Finally, we illustrate the theory through some examples.
Discrete Search with Directional Information
Authors: Berry Donald A. , Mensch Roy F.
Published: November 2008

An unknown number N of cells are arranged in numerical order. An object is hidden in cell N. The problem is to locate the object—thereby determining N—within n searches. We consider a version of this problem that has applications in several problem settings: locating flaws in a discrete circuit, locating nerve endings, or locating the end of a tree root. A search of a site determines whether a cell is present and contains the object, except that it might overlook, with known probability w, a cell that is present; that is, a cell can “wink.” A search of site i reveals an empty cell if i < N; the cell containing the object if i = N and the cell does not wink; and no cell if i > N or if i ≤ N and the cell winks. Various special cases are considered. We define “bisection strategies” and show that they are optimal when w = 0. When w > 0, we partially characterize optimal strategies when n = 2, and completely characterize optimal strategies when there are at most two cells. For various values of n and w we give tables of the probability of finding the object for three intuitively reasonable strategies.
A Tactical Planning Model for a Job Shop
Authors: Graves Stephen C.
Published: November 2008

We propose and develop a discrete-time, continuous-flow model for studying the operation of a job shop that sees a stationary input mix of job types. We are not concerned with issues of detailed scheduling, but rather hope to develop a tactical planning tool for a job-shop operation. With the model, we are able to characterize the operational behavior of each work center in the job shop for a given control policy. The control rule sets the production rate at a work center as a fixed proportion of its queue level in each time period, and is consistent with the assignment of a planned lead time to each work center. For these control rules, the model gives the steady-state distribution of the production levels at each work center, as well as the distribution of queue lengths. We show how to use the model not only to evaluate a choice of the controls but also to find a good specification that results in acceptable shop behavior. An example for a factory that produces grinding machines illustrates the use of the model.
A Monte Carlo Sampling Plan for Estimating Network Reliability
Authors: Fishman George S.
Published: November 2008

For an undirected network G = (V, E) whose arcs are subject to random failure, we present a relatively complete and comprehensive description of a general class of Monte Carlo sampling plans for estimating g = g(s, T), the probability that a specified node s is connected to all nodes in a node set T. We also provide procedures for implementing these plans. Each plan uses known lower and upper bounds [B, A] on g to produce an estimator of g that has a smaller variance (A − g)(g − B)/K on K independent replications than that obtained for crude Monte Carlo sampling (B = 0, A = 1). We describe worst-case bounds on sample sizes K, in terms of B and A, for meeting absolute and relative error criteria. We also give the worst-case bound on the amount of variance reduction that can be expected when compared with crude Monte Carlo sampling. Two plans arc studied in detail for the case T = {t}. An example illustrates the variance reductions achievable with these plans. We also show how to assess the credibility that a specified error criterion for g is met as the Monte Carlo experiment progresses, and show how confidence intervals can be computed for g. Lastly, we summarize the steps needed to implement the proposed technique.
Stochastic Bounds on Distributions of Optimal Value Functions with Applications to PERT, Network Flows and Reliability
Authors: Weiss Gideon
Published: November 2008

In many classical combinatorial optimization problems, including critical and shortest paths, maximum flow, and network reliability, the introduction of uncertainty considerably complicates the calculation of system performance. In fact, in these contexts, computing system performance exactly can often be an impossible task. Therefore, obtaining (stochastic) bounds on the system's performance becomes an attractive and useful alternative. This paper studies several stochastic bounds that are applicable to these contexts and to a broader set of problems that can be described by the general combinatorial concepts of clutters and blocking clutters. We begin our discussion by defining these unifying concepts and illustrating their specialization in several problem contexts.
A Deterministic Single-Item Inventory Model with Seller Holding Cost and Buyer Holding and Shortage Costs
Authors: Glazer Amihal , Hassin Refael
Published: November 2008

This paper considers the optimal deterministic inventory policy for a monopolist. The novel element concerns the consumers. Each has a time at which he would most prefer to obtain the good; he incurs a shortage cost if he buys it after that time, and a holding cost if he obtains it before. The firm must consider that any change in its policy will affect the quantity of goods it can sell and the maximum price it can charge. We find that the seller's optimal policy can take only one of three possible forms: sell the goods throughout each cycle; sell the goods continuously during an interval that is shorter than an inventory cycle; or sell the goods only at the instant each cycle begins.
D/G/1 Queues with Vacations
Authors: Servi L. D.
Published: November 2008

Many data switching systems have processors with arrival streams of regularly spaced tasks (e.g., individual bytes) requiring attention (e.g., directing the bytes to the appropriate outgoing line). In many of these systems the processor might also be required to handle other jobs (small maintenance routines or secondary tasks that await service in one or more other queues) as well. From the point of view of the primary queue of tasks, the processor ceases its service and takes a vacation. The performance of such a system is determined in part by the processor service schedule. In this paper, we define and analyze a model for investigating the waiting time probability distribution at the primary queue in terms of the primary task arrival rate, the service time distribution for the primary tasks, the probability distribution of the vacation duration, and the processor's service schedule. In addition, we discuss two characteristics of systems of this type that may have important design implications: (i) the steady-state waiting time probability distribution might be dependent upon the initial state of the system; and (ii) the waiting time might not decrease if the service time of the system decreases.
Successive Approximations for Finite Horizon, Semi-Markov Decision Processes with Application to Asset Liquidation
Authors: Mamer John W.
Published: November 2008

This paper presents a simple successive approximation approach to the characterization of optimal policies for finite horizon, semi-Markov decision processes. Optimal policies are nonstationary, for in this setting they depend on both time and state. We illustrate this approach by analyzing the optimal liquidation of an asset; we also show that several aspects of the standard, discrete-time, infinite horizon optimal policy carry over to the continuous-time, finite horizon policy.
A Game Theoretic-Mathematical Programming Analysis of Cooperative Phenomena in Oligopolistic Markets
Authors: Sherali Hanif D. , Rajan Roby
Published: November 2008

This paper investigates cooperative behavior in an industry that supplies a homogeneous product and consists of oligopolistic firms. The analysis is conducted within a game theoretic framework in which each firm is viewed as a player whose strategy is its level of production. By defining a suitable characteristic function that evaluates the worth of each possible coalition, we attempt to quantify the individual and collective bargaining powers of firms in order to predict merger or contractual agreements and production strategies. In particular, we define three games via three characteristic functions, each of which is based upon some assumed market behavior on the part of the players. For each game, we investigate whether the firms would choose to remain separate or form a grand coalition or some other coalition structure. For some insightful special cases, we are able to establish the resulting outcome and assert whether a core allocation of profits among members of an emerging coalition exists and whether the Shapley value allocation belongs to the core. In the more general case, we use the U.S. copper industry as an example to illustrate how Shapley values may be used to determine possible emerging coalition structures.
An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems
Authors: Gavish Bezalel , Srikanth Kizhanathan
Published: November 2008

We develop an efficient branch-and-bound based method for solving the Multiple Traveling Salesman Problem, and develop lower bounds through a Lagrangean relaxation that requires computing a degree-constrained minimal spanning tree. A subgradient optimization procedure updates the Lagrange multipliers. We use fast sensitivity analysis techniques to increase the underlying graph sparsity and reduce the problem size. The algorithm was tested on 416 problems with up to 500 cities and 10 salesmen. We also present computational results on different data sets and parameters in order to identify the major factors that influence the performance of the developed code.
A Progressive Algorithm for Modeling and Solving Multiple-Criteria Decision Problems
Authors: Korhonen Pekka , Moskowitz Herbert , Wallenius Jyrki
Published: November 2008

We consider a decision maker (DM) who has a set of possible decision alternatives, from which one (a “best”) is to be chosen. However, all decision alternatives are not at the DM's disposal initially, nor is full knowledge of his/her utility/value function. Therefore, the DM evaluates only the available subset of all decision alternatives, from which he/she chooses a most preferred one. Obviously, this decision is not necessarily “globally” best. Two natural questions arise: How good is the most preferred solution? What are the chances of finding better solutions by considering additional alternatives? We describe and illustrate a general progressive algorithm and the supporting theory for modeling and solving this problem when alternatives are introduced dynamically.
Optimal Imputation of Erroneous Data: Categorical Data, General Edits
Authors: Garfinkel R. S. , Kunnathur A. S. , Liepins G. E.
Published: November 2008

Responses to surveys often contain large amounts of incorrect information. One option for dealing with the problem is to revise those erroneous responses that can be detected. Fellegi and Holt developed a model in which a response is modified to pass a set of edits with as little change as possible. The model is called Minimum Weighted Fields to Impute (MWFI) and is NP-hard for categorical data and general edits. We develop two algorithms for MWFI, based on set covering, and present computational experience.
Queueing Systems with Service Interruptions
Authors: Federgruen Awi , Green Linda
Published: November 2008

In many queueing systems, the service process is subject to interruptions resulting from breakdowns, scheduled off-periods or the arrival of customers with preemptive priority. We consider a single server, first-come, first-served queueing system that alternates between periods when service is available (“on-periods”) and periods when the server is unavailable (“off-periods”). We consider the case of Poisson arrivals and general service, on- and off-time distributions and derive bounds and approximations for the mean waiting time, probability of delay and steady-state distribution of the number in system. These results are exact for the case of exponentially distributed on-times. Computational results are reported.
Markov and Markov-Regenerative pert Networks
Authors: Kulkarni V. G. , Adlakha V. G.
Published: November 2008

This paper investigates pert networks with independent and exponentially distributed activity durations. We model such networks as finite-state, absorbing, continuous-time Markov chains with upper triangular generator matrices. The state space is related to the network structure. We present simple and computationally stable algorithms to evaluate the usual performance criteria: the distribution and moments of project completion time, the probability that a given path is critical, and other related performance measures. In addition, we algorithmically analyze conditional performance measures—for example, project completion time, given a critical path—and present computational results. We then study extensions both to resource-constrained pert networks and to a special class of nonexponential pert networks.
Technical Note—On the Feasibility of Aggregate Production Plans
Authors: Axsäter Sven
Published: November 2008

We consider a situation in which a hierarchical planning system with two levels is applied to a multistage production process. The higher level aggregate production plan, expressed in terms of product groups, is disaggregated at the lower level into a detailed plan for individual items. We describe constraints imposed upon the aggregate level product groups that will guarantee the existence of a feasible disaggregation at the lower detailed level. The possibility of formulating suitable constraints is closely related to our choice of product groups and the aggregation of product data.
Contingent Claims Contracting for Purchasing Decisions in Inventory Management
Authors: Ritchken Peter H. , Tapiero Charles S.
Published: November 2008

Option pricing is a common and important practice in the financial community, and has become a fundamental theoretical construct in financial economics. The theory is quite rich and has potential uses in many other problem domains. This paper develops a variant of the theory as applied to inventory planning. In particular, we consider a risk management approach that uses negotiated option contracts for hedging against price and quantity uncertainty in inventory procurement. We derive conditions for the inclusion of options in inventory control as a function both of managerial attitudes toward risk and of the correlation between price and demand.
Group Consensus Function Estimation When Preferences are Uncertain
Authors: Zahedi Fatemeh
Published: November 2008

Group decision making usually requires eliciting and then combining and reconciling the preferences of each member of a group. Based on the premise that preference responses are uncertain, this paper presents a weighting scheme for combining multicriteria individual preferences to obtain group preferences, called “consensus points.” The consensus points are “efficient” in that they have minimum variance associated with confidence intervals of assessment. An estimation technique uses the efficient consensus points (as values of the dependent variable) and attribute values of alternatives based on which the consensus is generated (as values of independent variables), to estimate the multicriteria consensus function. This approach is capable of testing both a generalized form of prospect theory and the hypothesis of correlation among group members' preferences. In an expository application of the method, we test these hypotheses and use a decision already made, as well as extreme points on which members unanimously agree, to check the plausibility of results obtained from estimated consensus functions.
OR Forum—The Beginnings of Operations Research: 1934–1941
Authors: McCloskey Joseph F.
Published: November 2008

This paper, the first in a series on the history of operations research and management science, traces the scattered beginnings of operations research from World War I up to the activities in Britain before and during the early months of World War II.
Administrative Days in Acute Care Facilities: A Queueing-Analytic Approach
Authors: Weiss Elliott N. , McClain John O.
Published: November 2008

After acute care services are no longer required, a patient in an acute care hospital often must remain there while he or she awaits the provision of extended care services by a nursing home, through social support services, or by a home health care service. This waiting period is often referred to as “administrative days” because the time is spent in the acute facility not for medical reasons, but rather for administrative reasons. In this paper we use a queueing-analytic approach to describe the process by which patients await placement. We model the situation using a state-dependent placement rate for patients backed up in the acute care facility. We compare our model results with data collected from a convenience sample of 7 hospitals in New York State. We conclude with a discussion of the policy implications of our models.
Solving Mixed Integer Programming Problems Using Automatic Reformulation
Authors: Van Roy Tony J. , Wolsey Laurence A.
Published: November 2008

In this paper we describe computational experience in solving mixed 0-1 programming problems using strong valid inequalities as cutting planes. In particular we report on the solution to optimality of 18 medium- to large-size problems, including production planning problems with setup costs and capacity constraints, multilevel distribution planning problems, drainage and heating system design problems, and electricity generator scheduling problems. The solution approach uses the theory of strong valid inequalities that we developed in a series of earlier papers. Here we report specifically on the implementation of an experimental system, MPSARX, which consists of the SCICONIC mathematical programming system and an automatic reformulation executor (ARX) that use this theory, and on the results obtained with this system.
Derived Demand and Capacity Planning Under Uncertainty
Authors: Modiano Eduardo Marco
Published: November 2008

This paper is concerned with the derivation of demand functions for primary resources in an economic environment with uncertainty. This issue is critical when resource markets must decide, in the face of uncertainty, whether to expand capacity and/or to introduce new technologies. The models proposed are primarily data oriented. They explore two alternative behavioral models of action under uncertainty: here-and-now and wait-and-see. We present an application to the U.S. energy sector's demand for coal and the related expansion of capacity of coal-fired electricity generation plants.
Aggregation in Dynamic Programming
Authors: Bean James C. , Birge John R. , Smith Robert L.
Published: November 2008

Reducing the size of a dynamic program through state aggregation can significantly reduce both the data and the computation time required to solve a problem. We develop a new algorithm that combines state aggregation and disaggregation steps within a single-pass procedure. The solution obtained is automatically feasible for the original problem. By exploiting general conditions on the aggregate structure, we develop bounds for assessing the error from optimality introduced by the aggregation, and we illustrate with an application in infinite horizon optimization.
Multifacility-Type Capacity Expansion Planning: Algorithms and Complexities
Authors: Lee Sang-Bum , Luss Hanan
Published: November 2008

We examine several variations of a capacity expansion model with multiple facility types, and with the flexibility for converting capacity from one facility type to another. Applications can be found in communication networks and production facilities. The models include costs of expansions, conversions, excess capacities and capacity shortages, and assume cost functions that are either linear or concave. We find the optimal solution by exploiting properties of extreme flows in networks and employing a dynamic programming algorithm. Specializing our results permits us to obtain different model variations by imposing certain conditions on the cost functions, and to derive the computational complexities for these variations. Typically, applications require extensive sensitivity studies that may use up substantial computer resources. Our analysis unifies previous work, extends the results, and provides intuition concerning the difficulties involved in applying the models.
Vehicle Routing with Time Windows
Authors: Kolen A. W. J. , Rinnooy Kan A. H. G. , Trienekens H. W. J. M.
Published: November 2008

In vehicle routing problems with time windows, a fixed fleet of vehicles of limited capacity is available at a depot to serve a set of clients with given demands. Each client must be visited within a given time window. We describe a branch-and-bound method that minimizes the total route length, and present some computational results.
An Efficient Decomposition Method for the Approximate Evaluation of Tandem Queues with Finite Storage Space and Blocking
Authors: Gershwin Stanley B.
Published: November 2008

This paper presents an efficient method for evaluating performance measures for a class of tandem queueing systems with finite buffers in which blocking and starvation are important. These systems are difficult to evaluate because they have large state spaces and because they cannot be decomposed exactly. The approximate decomposition approach we describe is based on system characteristics such as conservation of flow. Comparisons with exact and simulation results indicate that the approach is very accurate.
Comparison of Policies for Routing Customers to Parallel Queueing Systems
Authors: Houck D. J.
Published: November 2008

This paper studies a queueing system with two groups of servers, each with a separate queue, and with arriving customers routed irrevocably to one of the two queues. One natural policy for routing arriving customers is to send them to the queue with the shortest expected delay. Although this shortest delay routing policy (SDR) is known to be optimal if each server group has one server and the service time distribution has nondecreasing failure rate, little is known about the general multiserver case, even with exponential service times. In this paper we show, using a theoretical upper bound, that an optimal policy would produce delays that are almost identical to what would result from combining the two groups. In addition, our simulation results show that SDR performs nearly optimally in every case considered.
OR Practice—Determining Lot Sizes and Resource Requirements: A Review
Authors: Bahl Harish C. , Ritzman Larry P. , Gupta Jatinder N. D.
Published: November 2008

Inventory planning can become extremely complicated in situations with nontrivial setup times and/or costs. The pervasiveness of this type of problem in actual practice, combined with its computational complexity, has long attracted researchers' attention. Although the most general model formulations still defy optimization when applied to realistically sized problems, many recent contributions are both innovative and promising. This article concentrates on the lot-sizing and capacity dimensions of production planning. We review selected contributions in four major categories, drawing from both practitioner- and research-based literature. We assess the strengths and weaknesses of these contributions, and suggest promising research avenues. We conclude that capacity limitations, as well as other realities of plant environments, such as scrap, demand uncertainties or inaccurate data, are the Achilles heel of lot-sizing research. Directing attention to these complex environments is a challenge that offers great rewards for actual implementation.
Optimal Selection of Ingot Sizes Via Set Covering
Authors: Vasko F. J. , Wolf F. E. , Stott K. L.
Published: November 2008

In 1984, Bethlehem Steel Corporation installed a new ingot mold stripping facility at its Bethlehem Plant that is capable of handling taller ingots. In order to take maximum advantage of this new facility, we developed a two-phase, computer-based procedure for selecting optimal ingot and internal ingot mold dimensions. Phase I of this procedure generates feasible ingot and internal ingot mold dimensions consistent with both the new stripper's capability and with mill constraints. Phase II then uses a set covering approach to select the optimal ingot and internal ingot mold sizes from among the feasible sizes generated. After analyzing the model, we recommended six new rectangular mold sizes to replace seven existing sizes. To date, implementation of these new ingot and mold sizes is proceeding smoothly and realizing the projected cost reduction benefits.
Modeling the IRS Telephone Taxpayer Information System
Authors: Harris Carl M. , Hoffman Karla L. , Saunders Patsy B.
Published: November 2008

The Internal Revenue Service (IRS) toll-free, nationwide telephone system provides prompt tax-information assistance. In 1986, the IRS processed 37.8 million calls from taxpayers at 32 answering sites. This paper documents a critical review of the IRS approach to allocating its staff and equipment. We built a simulation-based model to test various allocation policies for deploying IRS resources. The simulation study included detailed sensitivity analysis on key network variables, and showed the feasibility of modeling a typical IRS location as a multiserver loss/delay queue with retrial and reneging. The second phase of this effort therefore centered around developing a prototype probabilistic model for determining the most effective way of providing service at reasonable levels and at minimum cost. The resulting model allows the IRS to determine from tables the best configuration of people and telephone lines for any expected levels of incoming traffic. In addition, we provided flow balance analyses of the underlying feedback queues that permit the IRS to separate their caller streams into fresh and repeat callers, and thus to estimate actual demand for service.
Optimal Threats
Authors: Brams Steven J. , Kilgour D. Marc
Published: November 2008

Many conflicts, ranging from biblical strife to modern superpower confrontations, are significantly affected by the threat of retaliation. We analyze the policy of tit-for-tat in a Threat Game based on Chicken, in which each player can initially choose any level of preemption or non-cooperation. If one player is more preemptive than the other, the less preemptive player can retaliate; if the players preempt at the same level, neither can retaliate. After these choices, the game terminates, with the players' payoffs based on both the payoffs of Chicken and their levels of preemption and retaliation. An analysis of Nash equilibria shows the Deterrence Equilibrium (neither player preempts, but both threaten to retaliate if preempted) to be the most compelling solution to this game; a player's choice of his strategy associated with this equilibrium renders any level of preemption by his opponent costly. Deterrence Equilibrium strategies entail, in some cases, more-than-proportionate threats of retaliation against low levels of preemption and less-than-proportionate threats against high levels. We consider the optimality of such threats in light of existing prescriptions and evidence on different conflicts, especially those that occur in the international arena and may involve nuclear threats.
Optimal Terminal Defense Tactics When Several Sequential Engagements are Possible
Authors: Soland Richard M.
Published: November 2008

In this paper we treat a situation in which a terminal defense wishes to minimize the expected fraction of a target destroyed. Attacking reentry vehicles (RVs) arrive simultaneously, and therefore the defense knows the attack size. Several sequential engagements of the RVs by defensive interceptors are possible, and the defense has the capability to shoot-look-shoot between these engagements. Using techniques of stochastic dominance and stochastic dynamic programming, we determine optimal defensive tactics as functions of the numbers of RVs, interceptors, and engagements remaining; the various single-shot kill probabilities are parameters. We examine extensions of the basic model that determine both the expected number of interceptors remaining after the attack and the minimum number of interceptors needed to provide a desired level of protection of the target.
Competitive Location on a Network
Authors: Dobson Gregory , Karmarkar Uday S.
Published: November 2008

In this paper we study the problem of locating facilities on a network in the presence of competition. Customers at each node in the network choose from the available facilities so as to minimize the distance traveled. The problem is to find a set of facilities that is stable in the sense that each facility is economically viable and no competitor can successfully open any facilities. We define several versions of stability and establish certain relationships between them. We then present integer programming formulations that identify stable sets, and describe an enumeration algorithm for constructing a profit-maximizing stable set.
Dynamics of the M/G/1 Vacation Model
Authors: Keilson J. , Servi L. D.
Published: November 2008

An M/G/1 processor schedule attends to auxiliary vacation tasks iteratively. We describe the influence of these tasks on the dynamic behavior of the system and obtain, for several cases of interest, the relaxation time of the vacation system required to validate steady-state approximations. Finally, we find the distribution of the duration of the primary busy period, the vacation busy period, and an associated cycle time.
Stochastic Monotonicity of the Queue Lengths in Closed Queueing Networks
Authors: Shanthikumar J. George , Yao David D.
Published: November 2008

We study a Gordon-Newell type of closed queueing network that frequently arises in modeling manufacturing and computer systems. We are concerned with the transient and equilibrium behavior of the joint and individual queue lengths in the network when the job population increases. We show that increasing the job population will stochastically increase the queue-length vector process, provided that all stations have nondecreasing service rates. Single and multivariate likelihood ratio orderings are also established for the joint queue lengths in equilibrium. Our results extend the applicability of previously known results in the literature.
The Distribution of Maximum Flow with Applications to Multistate Reliability Systems
Authors: Fishman George S.
Published: November 2008

This paper describes an efficient Monte Carlo sampling plan for estimating the distribution of maximum flow in a directed network whose arcs have random capacities. Such a network can be used to represent a multistate system whose multistate components (capacities) are subject to random deterioration. The proposed sampling plan uses an easily computed a priori upper bound on the complementary distribution function to obtain an unbiased point estimator with smaller variance than the estimator obtained by crude Monte Carlo sampling. The paper also describes procedures for interval estimation and for assessing when the sampling experiment has achieved a specified accuracy. To facilitate sampling, we use cumulative processes to characterize deterioration, leading to the treatment of arc capacities as being multinormally distributed. We describe a technique for checking the appropriateness of this model with regard to lower and upper bounds on capacity. We also describe a procedure for deriving a confidence interval on the measure used to assess variance reduction. An example illustrates the sampling plan, and a concise summary gives all steps needed to implement the plan.
Technical Note—On the Convexity of Policy Regions in Partially Observed Systems
Authors: Lovejoy William S.
Published: November 2008

We offer a simple observation that unifies many of the existing convex policy region results for partially observed systems.