bluuebunny/crossref_metadata_2025 huggingface dataset:
OR Practice—Playing the Turn-of-the-Year Effect with Index Futures
Authors: Clark Ross , Ziemba William T.
Published: November 2008

The “turn-of-the-year” effect is a well-documented stock market phenomenon in which low capitalization “small stocks” receive relatively higher returns than high capitalization “big stocks” on the last trading day of December and the first 8 trading days of January. The difference in returns during this period is of the order of 10%. Strategies for buying and selling these small stocks may be profitable, but may also incur large transaction costs that eliminate most or all of the projected gains. In this paper, we show a preferable way to invest in order to exploit this anomaly: use a futures spread that is long in the small stocks and short in the big stocks. The optimal investment, which uses a modification of the capital growth criterion, is large and has a substantial expected gain with minimal risk. We have used this analysis successfully in managing investment accounts.
Improving on Bold Play at Craps
Authors: Ethier S. N.
Published: November 2008

We derive heuristically a strategy we believe to be nearly optimal at craps (in the sense of maximizing the probability of reaching a specified goal). We then prove rigorously (with the aid of a computer) that this strategy is superior to bold play on “don't pass,” regardless of the ratio of one's initial fortune to one's goal.
An Interval Arithmetic Approach to Sensitivity Analysis in Geometric Programming
Authors: Dinkel John J. , Tretter Marietta J.
Published: November 2008

Geometric programming has been an important optimization approach in several engineering design areas. In this paper, we present an approach to sensitivity analysis in geometric programming using interval arithmetic. The study of the effect of changes in the problem parameters is important for theoretical as well as for practical reasons. To date, most of the numerical approaches to sensitivity analysis have characterized the solution in terms of differential changes in the parameters. We use interval arithmetic to generate an interval of solution values associated with an interval of parameter values. These results indicate a new approach to characterizing solutions to geometric programs in terms of changes in the problem parameters.
Ergodicity in Parametric Nonstationary Markov Chains: An Application to Simulated Annealing Methods
Authors: Anily Shoshana , Federgruen Awi
Published: November 2008

A nonstationary Markov chain is weakly ergodic if the dependence of the state distribution on the starting state vanishes as time tends to infinity. A chain is strongly ergodic if it is weakly ergodic and converges in distribution. In this paper we show that the two ergodicity concepts are equivalent for finite chains under rather general (and widely verifiable) conditions. We discuss applications to probabilistic analyses of general search methods for combinatorial optimization problems (simulated annealing).
Perspectives on Queues: Combining Queues is Not Always Beneficial
Authors: Rothkopf Michael H. , Rech Paul
Published: November 2008

Contrary to common calculation, there are reasons for believing that combining queues, especially queues of people, may at times be counterproductive. These reasons include customer reaction, jockeying between separate queues, increased costs and service times for combined queues, and the absence of published before-and-after studies.
Presidents' Symposium: The Current Missionary Role of OR/MS
Authors: Blumstein Alfred
Published: November 2008

A major role of operations research and management science has always been to provide “missionaries” to bring system perspectives, modeling, and analysis to those “heathen” professions that have not yet been “converted.” Since many of our traditional fields have already become self-sufficient, in the future our future attention should be directed at the more complex fields of organization theory and public policy, which have considerable needs and thus offer rich opportunities.
The Cost of Delayed Lottery Resolution
Authors: Bordley Robert F.
Published: November 2008

When an individual is given a lottery, he usually must wait some time interval before that lottery is resolved. Previous work from the literature has shown that if the individual has to make consumption decisions during that time interval, the lottery's utility will not equal the expected utility of its consequences. In this paper, we derive a formula for the utility of the lottery for situations with relatively small gambles. Our formula is consistent with many of D. Kahneman and A. Tversky's observations. It also is similar, in some ways, to Bell's notion of elation and disappointment.
Boole-Bonferroni Inequalities and Linear Programming
Authors: Prékopa András
Published: November 2008

We present a method to obtain sharp lower and upper bounds for the probability that at least one out of a number of events in an arbitrary probability space will occur. The input data are some of the binomial moments of the occurrences, such as the sum of the probabilities of the individual events, or the sum of the joint probabilities of all pairs of events. We develop a special, very simple linear programming algorithm to obtain these bounds. The method allows us to compute good bounds in an optimal way, utilizing only the first few terms in the inclusion-exclusion formula. Possible applications include obtaining bounds for the reliability of a stochastic system, solving algorithmically some stochastic programming problems, and approximating multivariate probabilities in statistics. In a numerical example we approximate the probability that a Gaussian process runs below a given level in a number of consecutive epochs.
Optimal Obnoxious Paths on a Network: Transportation of Hazardous Materials
Authors: Batta Rajan , Chiu Samuel S.
Published: November 2008

This paper considers the problem of determining optimal paths for routing an undesirable vehicle on a network embedded on an Euclidean plane. A typical application is the transporting of hazardous materials. Demand points, or population centers, are discretely distributed at nodes and continuously distributed on straight-line links of the network. The objective is to find, without incorporating the probability of accidental leakage of hazardous material, a path that minimizes the weighted sum of lengths over which this vehicle is within a threshold distance λ of population centers. By appropriately redefining link lengths, we can use a shortest-path algorithm to solve the problem. Special properties of the objective function allow us to efficiently calculate the modified link lengths. We discuss the properties of the optimal routing strategy and the objective value, and offer an economic interpretation of the case when λ varies. Operating within the framework of risk analysis, we integrate the probability of accidental release of hazardous material into our basic model. The routing objective becomes the minimization of expected damage, where accidental leakage of hazardous materials can inflict damage within a neighborhood λ of the accident site. We also discuss our computational experience in using the model.
The Weighted Total Tardiness Problem with Fixed Shipping Times and Overtime Utilization
Authors: Matsuo Hirofumi
Published: November 2008

This paper addresses the problem of simultaneously determining overtime utilization and job sequencing over a finite planning horizon in a single machine job shop environment. Shipping times are assumed to occur at fixed and specified points in time, and their number is much smaller than the number of jobs. The goal is to find an overtime utilization level and job sequence that yields a “good” tradeoff between overtime cost and tardiness penalties. We begin by showing that the problem in its simplest form is NP-hard. We then present an approximate algorithm based on a capacitated transshipment formulation. This approximation provides a feasible solution along with its error bound. The algorithm is refined by incorporating the dominance relations of jobs. Extensive computational experience indicates that the algorithm is implementable in terms of both speed and accuracy.
Estimating Average Production Intervals Using Inventory Measurements: Little's Law for Partially Observable Processes
Authors: Nozari Ardavan , Whitt Ward
Published: November 2008

This paper proposes an indirect approach to estimate average production intervals (the length of time between starting and finishing work on each product) using work-in-process inventory measurements. The idea is to apply a modified version of Little's law (L = λW) from queueing theory to cope with stochastic processes that are not directly observable. When the actual amount of completed product to be produced from the current work-in-process is not known, we suggest working with an appropriate expected amount of completed product associated with current work-in-process, taking care to properly account for such features as partial yields, changing lot sizes and reconstituted lots. This indirect estimation procedure can be applied to computer simulation as well as direct system measurement. The approach also can be used to calculate expected values of steady-state random variables in mathematical models.
A Max-Min Allocation Problem: Its Solutions and Applications
Authors: Tang Christopher S.
Published: November 2008

This paper describes a max-min allocation problem that has M constraints and N nonnegative integer variables. By exploring the structure of the optimal solution to this max-min allocation problem, we develop a nonsimplex-based algorithm that finds an optimal solution within O(MN2) operations. In addition, we show that a space allocation problem for a flexible component insertion machine can be formulated as a special case of this max-min allocation problem with one constraint. Furthermore, we present some manufacturing and production problems that can he formulated as max-min allocation problems, and hence, can be solved efficiently.
OR Practice—Development and Implementation of a Scheduling System for a Wafer Fabrication Facility
Authors: Bitran Gabriel R. , Tirupati Devanath
Published: November 2008

This paper describes a scheduling system developed and implemented at a semiconductor company that manufactures specialty epitaxial wafers. We discuss implementation issues and describe the algorithms that form the basis of the scheduling system. We present computational results with representative data, and illustrate that scheduling procedures can be simplified considerably when they are preceded by a planning stage. The authors learned this fact through interaction with managers of the firm, and this changed the preconceived direction of the work in this application. The result is a formalization of the planning and scheduling problems.
Structuring Objectives for Problems of Public Interest
Authors: Keeney Ralph L.
Published: November 2008

The analysis of problems of public interest requires a broad range of objectives. This paper outlines and illustrates a procedure to constructively involve stakeholders in the process of identifying these objectives. The illustration concerns the evaluation of alternatives to ship spent nuclear fuel from power plants to a repository. Objectives were developed from group discussions with individuals in the nuclear industry, in state governments, and in environmental and public interest organizations. Using guidelines outlined in the paper, hierarchies of objectives were structured to represent each of these stakeholders. From these, a combined hierarchy was structured that addressed health and safety; economics; equity; environmental, social, and political impacts; flexibility; and scheduling.
Modeling and Forecasting Energy Markets with the Intermediate Future Forecasting System
Authors: Murphy Frederic H. , Conti John J. , Shaw Susan H. , Sanders Reginald
Published: November 2008

This paper describes the Intermediate Future Forecasting System (IFFS), which is the model used to forecast integrated energy markets by the U.S. Energy Information Administration. The model contains representations of supply and demand for all of the major fuels consumed in the United States, and is a partial equilibrium model containing a large number of equations and inequalities. We discuss methods for solving the models, as well as the convergence properties of the solution procedure. We also present issues associated with managing large models.
Modeling the Performance of Organizational Structures
Authors: Malone Thomas W. , Smith Stephen A.
Published: November 2008

We develop models for comparing the performance of coordination structures that appear in a wide variety of systems, including human organizations and computer systems. First, we define four generic structures: product hierarchies, functional hierarchies, centralized markets, and decentralized markets. Then, drawing primarily on queueing models, we rank these structures in terms of three performance measures: production costs, coordination costs, and vulnerability costs. The models show how changes in the values of these performance measures affect the desirabilities of the different structures. Then, we show how these simple relationships between performance measures and the desirabilities of structures are consistent with a surprising range of phenomena, including; (1) major historical shifts in the dominant organizational forms used by American businesses, and (2) the evolution of computing system architectures. Finally, we use the models to suggest the possible future evolution of both human and computer systems.
The Deadline Constrained Weighted Completion Time Problem: Analysis of a Heuristic
Authors: Posner Marc E.
Published: November 2008

A greedy heuristic that schedules jobs on one machine is examined. The problem considered is to minimize the sum of weighted completion times subject to deadline constraints. Both theoretical and empirical evidence are presented to suggest that this method finds solutions that are near optimal. Optimality conditions are developed. Also, an analysis of the relative error is presented. Worst case bounds are found that are based on the problem parameters. In addition, we show that the relative error goes to zero as the problem size goes to infinity.
Introduction—Special Focus and Decision Support Systems (DSS)
Authors: Gray Paul , Lenstra Jan Karel
Published: November 2008

The history of Operations Research has been intertwined with computation and decision making. If we examine the fundamental methodologies that have become associated with operations research, we see that each has resulted from the need to make decisions, and that many of them require considerable numerical computation to obtain results that can support decision makers. Notice the phrasing that is almost ingrained in the way we think of operations research work: support decision making. We do not, as a profession, claim that we are the decision makers but we believe the importance of our work comes from helping, or supporting decision makers, in making the best choice based on the information available.
Computer-Aided Deliberation: Model Management and Group Decision Support
Authors: Nunamaker J. F. , Applegate Lynda M. , Konsynski Benn R.
Published: November 2008

The paper highlights principles of group process as an important component of group activities in planning and policy making. The management of a variety of models utilized in organizational planning is discussed. Descriptions of the features and functions of the hardware and software environment, along with scenarios for use of the environment, illustrate critical issues in group deliberation. A particular model, stakeholder identification and assumption surfacing, is used to illustrate aspects of model management and planning process implementation. Findings of the group decision support system (GDSS) research are discussed in terms of anonymity of participation, facility design, need for multiple public screens, use of knowledge and data bases, communication network speed, methodological approach, software design, mixing of manual and electronic sessions, group size, composition, satisfaction of the users and model management systems. In general, the research results from experiments and case studies reflect our findings from observation of 40 groups.
The Three-Dimensional Gantt Chart
Authors: Jones Christopher V.
Published: November 2008

Developing useful models can be thought of as a process that produces more and more precise representations of the problem at hand. In particular, a problem solving project often involves successively developing a problem statement, formal model, model instance, algorithm output, and final presentation. Yet the field of operations research has traditionally concentrated only on developing the models and algorithms. The representations used for the other project phases have usually been ad hoc. When well done, however, e.g., in spreadsheets, representations can both significantly aid the decision maker and expand the use of OR techniques. One of the principal contributions of the research in Decision Support Systems has been its emphasis on tools to support the development of these representations. OR has both a challenge and an opportunity to move from the art of representation to a science of representation. This paper illustrates this point with an example. The example presents a new representation for a widely studied class of problems, machine scheduling problems, which demonstrates the potential of emerging hardware and software to support the kinds of representations that are required in the modeling process. The representation extends the well known Gantt chart for machine scheduling into a three-dimensional representation. The representation unifies several of the representations that have been developed for these problems. Furthermore, the technology that facilitates the three-dimensional representation also facilitates animation of the machine schedule.
Descriptive Analysis for Computer-Based Decision Support
Authors: Silver Mark S.
Published: November 2008

This article studies the issue of descriptive analysis for Decision Support Systems (DSS). Much of the DSS research literature concentrates on the procedural aspects of building support systems rather than on the substantive issues of their content. If we are to expand our knowledge of DSS, however, it is important to complement our understanding of the process of their development with a means for describing and differentiating DSS. In particular, a descriptive mechanism should pay careful attention to those features of DSS that determine the effects a support system has on the decision making processes of its users. A three-tiered approach to describing DSS is proposed, consisting of the following sequence of analytical levels: functional capabilities, user views of system components, and system attributes (restrictiveness, guidance, and focus). Moving from the first through the third tiers, increasing attention is paid to examining DSS in their entirety and to considering their effects on decision making processes.
Stability Conditions for Multidimensional Queueing Systems with Computer Applications
Authors: Szpankowski Wojciech
Published: November 2008

A fundamental question arising in the analysis of queueing systems is whether a system is stable or unstable. For systems modeled by infinite Markov chains, we may study the ergodicity and nonergodicity of the chains. Foster showed that sufficient conditions for ergodicity are linked with the average drift. However, complications arise when multidimensional Markov chains are analyzed. We present three methods that provide sufficient conditions for ergodicity and nonergodicity of a multidimensional Markov chain. These methods are next applied to two multidimensional queueing systems: buffered contention packet broadcast systems and coupled processor systems.
Some Theorems on Instability with Applications to Multiaccess Protocols
Authors: Szpankowski Wojciech , Rego Vernon
Published: November 2008

An important question in stochastic modeling is whether a denumerable state Markov chain describing a system is stable or not. Adopting a general definition of stability, we discuss some conditions for instability. We extend slightly previous results on nonergodicity, and we present new criteria for moments of a chain to be infinite. Finally, we apply these instability conditions to study some multidimensional Markov chains that describe multiaccess protocols in a broadcast environment. In particular, we prove that the exponential backoff algorithm is unstable for λ > 0.461, and the decentralized dynamic control algorithm is unstable for λ > e−1 = 0.368.
Simultaneous Minimization of Mean and Variation of Flow Time and Waiting Time in Single Machine Systems
Authors: Bagchi Uttarayan
Published: November 2008

In this paper, we consider bicriterion scheduling problems involving job completion times and job waiting times in a nonpreemptive single machine environment. As an example, we seek to determine a schedule that yields both a low mean and a low variation of completion time. Such a schedule is attractive when the system has the dual objectives of minimizing in-process inventory and providing different jobs the same quality of service. Similarly, we seek a schedule that performs well on both the mean and variation of waiting time. As the measure of variation, we use the sum of absolute pairwise differences. We present an efficient algorithm for minimizing the variation of waiting time. Next, we assume that the total scheduling cost is a function of the mean and variation of completion time alone, and is linear. We give an efficient algorithm for minimizing this total cost. Finally, we consider parametric analysis of this cost function and present simple procedures for generating all or some of the optimal schedules. All the results are extended to the case where job waiting times are substituted for job completion times.
Dual Algorithms for Pure Network Problems
Authors: Ali Agha Iqbal , Padman Rema , Thiagarajan Hemalatha
Published: November 2008

This paper reports the development of a new algorithmic implementation of the dual algorithm for the capacitated minimum cost network flow problem. Furthermore, it introduces dual reoptimization procedures and compares primal and dual algorithms for the optimization and reoptimization of network problems. The implementation makes use of cut-sets for the efficient execution of the entering variable selection and the selection of the leaving variable is tied to the basis structure at an iteration. Empirical testing of the dual algorithm for optimization shows that it dominates the primal procedure for assignment problems with 400 nodes, transportation problems with more than 600 nodes, and transshipment problems with more than 1500 nodes. Computational testing with typical changes found in decomposition and relaxation procedures indicates the superiority of dual reoptimization over primal reoptimization. For a sequence of parametric changes, as would be typical in large-scale programming techniques, on the average, dual reoptimization is found to require between 75 and 93% fewer pivots and between 20 and 50% less time than primal reoptimization depending on the type of change.
A Method for Repricing Aircraft Procurement Programs
Authors: Balut Stephen J. , Gulledge Thomas R. , Womer Norman Keith
Published: November 2008

Planned annual procurement quantities for defense weapon systems are often altered after production starts. Department of Defense analysts support the decision process by providing cost estimates for alternatives to ongoing procurement programs. This paper presents a method for repricing aircraft programs under a proposed change in quantity. The method is an extension of the standard learning curve model that accommodates the redistribution of fixed costs at the contractor's plant.
Preemptive Scheduling of Hybrid Parallel Machines
Authors: Balakrishnan Anantaram
Published: November 2008

Multioperation production facilities are often segmented into independent workcells that handle different subsets of operations. We refer to a cell that consists of several groups of uniform special purpose machines, each capable of performing only one particular operation, and one group of identical general purpose machines, that can perform all the required operations at a slower rate, as a hybrid parallel machine environment. This paper focuses on deterministic, preemptive scheduling in such an environment. We first analyze the minimum makespan for a preemptive schedule when all jobs arrive simultaneously at a hybrid machine facility. For the more general situation where jobs have arbitrary release and due dates, we adapt a network flow formulation, originally proposed for the uniform machines case, to determine whether all jobs can be completed feasibly before their respective due dates.
OR Forum—The Keynote Speech
Authors: Woolsey Robert E. D.
Published: November 2008

This note records the substance of a keynote speech recently given to a conference of people dealing with modeling problems and building systems to solve them, primarily in the military-industrial sector.
Generating the Discrete Efficient Frontier to the Capital Budgeting Problem
Authors: Rosenblatt Meir J. , Sinuany-Stern Zilla
Published: November 2008

In this paper, we characterize the capital budgeting problem by two objective functions. One is maximizing the present value of accepted projects and the other is minimizing their risk. As we assume that the weights assigned to these objectives are unspecified, we utilize a Discrete Efficient Frontier (DEF) approach to represent all the efficient combinations. We found an optimality range for each efficient combination covering the entire possible range of weights (zero to one). Furthermore, we present different properties and characteristics of the DEF, and develop two algorithms for constructing the DEF. The first one is a simple heuristic and the second one is an optimal algorithm. We conducted experiments measuring the effectiveness of the heuristic algorithm and the effect of terminating the optimal algorithm before its completion. We have shown that the heuristic algorithm, which is the first phase of the branch-and-bound algorithm, has an average error of about 2%. Furthermore, we have shown that this average error can be reduced by applying only part of the optimal algorithm and terminating it before its actual completion.
The Fixed Job Schedule Problem with Working-Time Constraints
Authors: Fischetti Matteo , Martello Silvano , Toth Paolo
Published: November 2008

We consider a generalization of the fixed job schedule problem where a bound is imposed on the total working time of each processor. It is shown that the problem is NP-hard but polynomially solvable in the preemptive case. We introduce several lower bounds. One is determined through definition of a special class of graphs, for which the maximum clique problem is shown to be polynomial. Lower bounds and dominance criteria are exploited in a branch-and-bound algorithm for optimal solution of the problem. The effectiveness of the algorithm is analyzed through computational experiments.
Optimal Scheduling of Products with Two Subassemblies on a Single Machine
Authors: Coffman Edward G. , Nozari Ardavan , Yannakakis Mihalis
Published: November 2008

We consider a single machine job shop in which subassemblies of two different types are made and then assembled into products. The time required for each type is known. A fixed changeover cost is incurred whenever the machine is switched over from one type to the other. We describe and analyze an efficient algorithm for minimizing the total flow time of the products. Applications to the automated manufacture of circuit boards are noted.
On Modeling the Store of an Assembly Shop by Due Date Processes
Authors: Sengupta Bhaskar
Published: November 2008

This paper concerns modeling the store of an assembly shop which is required to collect the components for an assembly and deliver them to the shop floor for fabrication. The production schedule consists of fabricating one assembly per unit time and the deliveries of the components from the vendors need to be timed to this production schedule. We model the arrival streams by due date processes and find the transient and steady state behavior of an assembly queue. We comment on the feasibility of using this modeling methodology for the store of an assembly shop, and show that a problem of determining optimum safety stocks can be solved easily by using this methodology.
Equivalent Mathematical Programming Formulations of Monotonic Tree Network Location Problems
Authors: Erkut E. , Francis R. L. , Lowe T. J. , Tamir A.
Published: November 2008

We consider the optimization problem of locating several new facilities on a tree network, with respect to existing facilities, and to each other. The new facilities are not restricted to be at vertices of the network, but the locations are subject to constraints. Each constraint function, and the objective function, is an arbitrary, nondecreasing function of any finite collection of tree distances between new and existing facilities, and/or between distinct pairs of new facilities, and represents some sort of transport or travel cost. The new facilities are to be located so as to minimize the objective function subject to upper bounds on the constraint functions. We show that such problems are equivalent to mathematical programming problems which, when each function is expressed using only maximization and summation operations on nonnegatively weighted arguments, are linear programming problems of polynomial dimensions. The latter problems can be solved using duality theory with special purpose column generation and shortest path algorithms for column pricing.
Randomized and Past-Dependent Policies for Markov Decision Processes with Multiple Constraints
Authors: Ross Keith W.
Published: November 2008

The Markov decision problem of locating a policy to maximize the long-run average reward subject to K long-run average cost constraints is considered. It is assumed that the state and action spaces are finite and the law of motion is unichain, that is, every pure policy gives rise to a Markov chain with one recurrent class. It is first proved that there exists an optimal stationary policy with a degree of randomization no greater than K; consequently, it is never necessary to randomize in more than K states. A linear program produces the optimal policy with limited randomization. For the special case of a single constraint, we also address the problem of finding optimal nonrandomized, but nonstationary, policies. We show that a round-robin type policy is optimal, and conjecture the same for a steering policy that depends on the entire past history of the process, but whose implementation requires essentially no more storage than that of a pure policy.
Multidimensional Stochastic Ordering and Associated Random Variables
Authors: Baccelli François , Makowski Armand M.
Published: November 2008

This paper presents several relationships between the concept of associated random variables (RVs) and notions of stochastic ordering. The question that provides the impetus for this work is whether the association of the ℝ-valued RVs {X1, …, Xn} implies a possible stochastic ordering between the ℝn-valued RV X ≔ (X1, …, Xn) and its independent version X̄ ≔ (X̄1, …, X̄n). This leads to results on how multidimensional probability distributions are determined by conditions on their one-dimensional marginal distributions in the event of comparison under the stochastic orderings ≤st, ≤c1, ≤cv, ≤D and ≤K. Such results have direct implications for the comparison of bounds for Fork-Join queues and for the structure of monotone functions of several variables.
Technical Note—On Rothkopf and Smith's Statement Regarding Optimal Priority Assignment
Authors: Veklerov Eugene
Published: November 2008

A limitation is established to the equivalence of solutions to problems of sequencing a finite number of jobs, and assigning priorities in a queue. It is shown that for exponential delay costs, the optimal priority assignment in a nonpreemptive multiclass queue is not described by an index rule that is independent of the arrival rates.
Fire Company Relocation and the Future of Applied Operations Research
Authors: Walker Warren E.
Published: November 2008

This article is based on a talk given at the 1988 TIMS/ORSA meeting in Washington, D.C., about developments since the 1974 Lanchester Prize was awarded to P. J. Kolesar and W. E. Walker in 1974, for a paper that described an algorithm for dynamically repositioning available fire companies in response to changing patterns of availabilities. The life history of that algorithm motivates a vision for the future of the applied side of the OR profession.
OR Practice—A Scenario Approach to Capacity Planning
Authors: Eppen Gary D. , Martin R. Kipp , Schrage Linus
Published: November 2008

Production capacity has always been one of the most important strategic variables for the major automobile companies. Decisions by individual companies concerning the overall level of capacity, the type of facility (e.g., the level of flexibility), and the location of that capacity (e.g., in the United States or abroad) are discussed in great detail in the popular business press. In this paper, we describe a model developed for General Motors to aid in making decisions about capacity for four of their auto lines. The model incorporates elements of scenario planning, integer programming, and risk analysis. All the input and output is done using Lotus 1-2-3. Although the presentation is motivated by the particular application in the auto industry, the model represents a general purpose approach that is applicable to a wide variety of decisions under risk. An example in this paper uses actual data, appropriately transformed to ensure confidentiality.
Simultaneous Resource Scheduling to Minimize Weighted Flow Times
Authors: Dobson Gregory , Karmarkar Uday S.
Published: November 2008

Many scheduling problems in manufacturing and service firms involve tasks that require more than one resource to be used simultaneously to execute the task. Two formulations of this scheduling problem are given. We develop a Lagrangian relaxation for the problem that has an intuitive interpretation. The relaxation suggests heuristics and provides a lower bound on the optimal solution. Next a surrogate relaxation is developed that provides a second bound and a heuristic solution. An enumeration procedure to determine the optimal solution is described, and computational results on the effectiveness of the bounds and the heuristics are presented. The Lagrangian relaxation performs better on problems with a low degree of simultaneity, and the surrogate relaxation does better with a high degree of simultaneity.
Average Cost Optimal Stationary Policies in Infinite State Markov Decision Processes with Unbounded Costs
Authors: Sennott Linn I.
Published: November 2008

We deal with infinite state Markov decision processes with unbounded costs. Three simple conditions, based on the optimal discounted value function, guarantee the existence of an expected average cost optimal stationary policy. Sufficient conditions are the existence of a distinguished state of smallest discounted value and a single stationary policy inducing an irreducible, ergodic Markov chain for which the average cost of a first passage from any state to the distinguished state is finite. A result to verify this is also given. Two examples illustrate the ease of applying the criteria.
Extensions of the Queueing Relations L = λW and H = λG
Authors: Glynn Peter W. , Whitt Ward
Published: November 2008

This paper extends the fundamental queueing relations L = λW and H = λG that relate customer averages (the customer-average waiting time W or cost G) to associated time averages (the time-average queue length L or cost H) given an arrival process with arrival rate λ. These relations can be established by focusing on a two-dimensional cumulative input process that has the two one-dimensional cumulative input processes of interest as marginals. Relations between the marginal averages are established for cumulative input processes that may not be representable as integrals or sums. The general framework includes the continuous versions of L = λW and H = λG due to T. Rolski and S. Stidham as well as the standard version of H = λG, and can be extended to higher dimensions. Inequalities are also established when some of the conditions for equality do not hold. Moreover, central limit theorem versions of H = λG are established, extending our recent results for L = λW.
A Simple Proof of the Equivalence of Input and Output Intervals in Jackson Networks of Single Server Nodes
Authors: Kiessler Peter C.
Published: November 2008

In this paper, we provide a simple proof that the distributions of an input and an output interval in a stationary Jackson network of single server nodes are equivalent. The proof also applies to Gordon and Newell networks of single server nodes. The proof's key idea is that the reverse process of a Jackson network's stationary queue length process is also a Jackson network's stationary queue length process.
Technical Note—The Stochastic Queue Median Over a Finite Discrete Set
Authors: Batta Rajan
Published: November 2008

Many practical location decision problems require facility locations to be restricted to a finite set of points. Quite often such restrictions arise from natural constraints that are specific to the application setting. Motivated by such situations, this paper examines the Stochastic Queue Median (SQM) model of Berman, Larson and Chiu, where potential facility locations are restricted to a finite set of discrete points. An efficient algorithm is presented to solve for the optimal facility location parametrically in the systemwide arrival rate of calls. The complexity of the algorithm and a worst case analysis for the model formulation are also discussed.
Markov Decision Processes with Sample Path Constraints: The Communicating Case
Authors: Ross Keith W. , Varadarajan Ravi
Published: November 2008

We consider time-average Markov Decision Processes (MDPs), which accumulate a reward and cost at each decision epoch. A policy meets the sample-path constraint if the time-average cost is below a specified value with probability one. The optimization problem is to maximize the expected average reward over all policies that meet the sample-path constraint. The sample-path constraint is compared with the more commonly studied constraint of requiring the average expected cost to be less than a specified value. Although the two criteria are equivalent for certain classes of MDPs, their feasible and optimal policies differ for many nontrivial problems. In general, there does not exist optimal or nearly optimal stationary policies when the expected average-cost constraint is employed. Assuming that a policy exists that meets the sample-path constraint, we establish that there exist nearly optimal stationary policies for communicating MDPs. A parametric linear programming algorithm is given to construct nearly optimal stationary policies. The discussion relies on well known results from the theory of stochastic processes and linear programming. The techniques lead to simple proofs of the existence of optimal and nearly optimal stationary policies for unichain and deterministic MDPs, respectively.
Solution Procedures for Partially Observed Markov Decision Processes
Authors: White Chelsea C. , Scherer William T.
Published: November 2008

We present three algorithms to solve the infinite horizon, expected discounted total reward partially observed Markov decision process (POMDP). Each algorithm integrates a successive approximations algorithm for the POMDP due to A. Smallwood and E. Sondik with an appropriately generalized numerical technique that has been shown to reduce CPU time until convergence for the completely observed case. The first technique is reward revision. The second technique is reward revision integrated with modified policy iteration. The third is a standard extrapolation. A numerical study indicates the potentially significant computational value of these algorithms.
Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
Authors: Johnson David S. , Aragon Cecilia R. , McGeoch Lyle A. , Schevon Catherine
Published: November 2008

In this and two companion papers, we report on an extended empirical study of the simulated annealing approach to combinatorial optimization proposed by S. Kirkpatrick et al. That study investigated how best to adapt simulated annealing to particular problems and compared its performance to that of more traditional algorithms. This paper (Part I) discusses annealing and our parameterized generic implementation of it, describes how we adapted this generic algorithm to the graph partitioning problem, and reports how well it compared to standard algorithms like the Kernighan-Lin algorithm. (For sparse random graphs, it tended to outperform Kernighan-Lin as the number of vertices become large, even when its much greater running time was taken into account. It did not perform nearly so well, however, on graphs generated with a built-in geometric structure.) We also discuss how we went about optimizing our implementation, and describe the effects of changing the various annealing parameters or varying the basic annealing algorithm itself.
The Constrained Bottleneck Problem in Networks
Authors: Berman O. , Einav D. , Handler G.
Published: November 2008

We consider problems on networks that are captured by two performance measures. One performance measure is any general cost function of a solution; the other is a bottleneck measure that describes the worst (maximum cost) component of the solution. The paper contains algorithms to solve three problems. In one problem, we minimize the bottleneck subject to a constraint on the generalized cost. In the second problem, we minimize the generalized cost subject to a constraint on the bottleneck. In the third problem, we consider the two criteria simultaneously and find all the Pareto optimum solutions. The major result is that the introduction of the bottleneck measure changes the complexity of the original (general cost) problem by a factor which is at most linear in the number of links.
Inventory Models with Cost Changes
Authors: Lev Benjamin , Weiss Howard J.
Published: November 2008

Two of the basic assumptions of economic order quantity models are an infinite horizon and static costs. In this paper, both assumptions are relaxed and results on the form of the optimal inventory policy are developed for both finite and infinite horizon models with changes in any or all costs. These results are used to develop short procedures for the computation of the optimal policy.
A Fully Polynomial Approximation Scheme for Single-Product Scheduling in a Finite Capacity Facility
Authors: Gavish Bezalel , Johnson Robert E.
Published: November 2008

This paper considers a version of the economic lot sizing problem for a single product produced in a facility of finite capacity over a finite time horizon with specifiable start and end conditions. A set of algorithms is presented that will approximate the optimal production schedule to a given allowable error (ε). Algorithms with computation time bounds of O(1/ε2) are presented which allow for setups of finite length, setups with or without direct cash flow, quite general cost and demand functions, and a wide variety of production policy constraints. The procedures make no a priori assumptions about the form of the optimal solution. Numerical results are included.
OR/MS Support to Senior Managers in the Public Sector: Two Cases
Authors: Waks Norman
Published: November 2008

Through two case examples this paper illustrates that senior public managers at even the highest levels can be, and regularly are, helped by OR/MS people and/or their tools, approaches, and ways of thinking. Thus, it questions the continuing belief evidently held by some in the OR/MS community that it does not, or cannot, happen for a variety of reasons, which they then proceed to spell out.
Graphs, Maneuvers and Turnpikes
Authors: Benjamin Arthur T.
Published: November 2008

We address the problem of moving a collection of objects from one subset of Zm to another at minimum cost. We show that under fairly natural rules for movement assumptions, if the origin and destination are far enough apart, then a near optimal solution with special structure exists: Our trajectory from the origin to the destination accrues almost all of its cost repeating at most m different patterns of movement. Directions for related research are identified.
Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems
Authors: Adams Warren P. , Sherali Hanif D.
Published: November 2008

This paper is concerned with a new linearization strategy for a class of zero-one mixed integer programming problems that contains quadratic cross-product terms between continuous and binary variables, and between the binary variables themselves. This linearization scheme provides an equivalent mixed integer linear programming problem which yields a tighter continuous relaxation than that obtainable via the alternative linearization techniques available in the literature. Moreover, the proposed technique provides a unifying framework in the sense that all the alternate methods lead to formulations that are accessible through appropriate surrogates of the constraints of the new linearized formulation. Extensions to various other types of mixed integer nonlinear programming problems are also discussed.
Annual Scheduling of Atlantic Fleet Naval Combatants
Authors: Brown Gerald G. , Goodman Clark E. , Wood R. Kevin
Published: November 2008

Employment scheduling is the process whereby U. S. Navy ships, submarines, aircraft and other units are assigned to major operations, exercises, maintenance periods, inspections and other events; the employment schedule directly influences fleet combat readiness. Currently, this process is largely manual requiring several full-time scheduling officers and additional personnel at various levels of management. We introduce an optimization model that automates a substantial part of the employment scheduling problem. The model is formulated as a generalized set partitioning problem and is applied to the annual planning schedule for naval surface combatants of the Atlantic Fleet. For the calendar year 1983, 111 ships engage in 19 primary events yielding a model with 228 constraints and 10,723 binary variables. This model is solved optimally in about 1.6 minutes producing a schedule that is significantly better than the corresponding published schedule.

The optimized peacetime employment schedule which has as its objective maximizing combat readiness should always be the goal and guide.

U.S. Navy, NWP − 1

He knew the things that were, the things that would be, and the things that had come before.

Homer, The Iliad