bluuebunny/crossref_metadata_2025 huggingface dataset:
An Integrated Budget Model for Medical School Financial Planning
Authors: Brandeau Margaret L. , Hopkins David S. P. , Melmon Kenneth L.
Published: November 2008

This paper presents a financial planning model for medical school departments that integrates manpower and funding elements with the school's teaching, research, and patient care activities. The model tracks revenue, expense, and faculty effort in each of the three primary medical school activities and estimates, for any given change in the amount or configuration of faculty effort among these activities, the associated financial effects on both the institution and the individuals themselves over a one- to five-year planning horizon. One innovative feature of the model is that it incorporates economically based functions that capture the effect on revenue of factors such as faculty “effort,” price increases, demand elasticity, market saturation, and changes in number of faculty members. We describe the implementation of the model for a major department at Stanford University Medical School (SUMS), and explore a number of sample policy issues, using data from that department as well as from another department at SUMS. We also describe the implementation of the model in evaluating the financial effects of a proposed organ transplantation program at SUMS.
Using Expert Advice on a Skew Judgmental Distribution
Authors: Lindley Dennis V.
Published: November 2008

A decision maker is interested in a quantity θ. He consults an expert who provides three fractiles of her probability distribution for θ. The problem discussed in this paper is how the decision maker should use the expert's fractiles to produce his distribution for θ. A key ingredient has to be the decision maker's opinion of the expert. Our analysis shows how the Bayesian approach clearly incorporates this feature. With three fractiles provided, information about the skewness of the distribution of θ is available, in addition to location and scale. Our development uses the skew logistic to accommodate this additional feature, and much of the paper is concerned with skewness, extending the methods of Lindley for the symmetric case. The ideas easily extend to several experts if the unrealistic assumption is made that the decision maker regards them as independent.
The Product Matrix Traveling Salesman Problem: An Application and Solution Heuristic
Authors: Plante Robert D. , Lowe Timothy J. , Chandrasekaran R.
Published: November 2008

In this paper we analyze an optimization problem that arises in the overhaul of a gas turbine engine. This problem involves the placement of nozzle guide vanes in the nozzle of the engine. The objective of the vane placement is to attain “uniform” flow (equalized distribution of hot fuel gases) about the circumference of the engine nozzle. We show that this placement problem is equivalent to a traveling salesman problem (TSP) whose cost matrix is a product matrix. Exploiting properties of the special form of the cost matrix, we give a heuristic algorithm for solving the problem, and derive a posteriori lower bounds for the heuristic. We show that the heuristic performs extremely well on both real and simulated data. Finally, we present and develop the theoretical results that are the foundation of the proposed heuristic.
OR Forum—Presidents' Symposium: Reflections on OR/MS Education
Authors: Borsting Jack R.
Published: November 2008

This essay compares OR/MS education with educational programs for two other professions—medicine and statistics. It urges an overall review of OR/MS curricula and makes recommendations for changing the profession's education.
Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition
Authors: Martin R. Kipp
Published: November 2008

Dropping the “complicating” constraints in a mixed-integer linear program often yields a “special structure subproblem” that can be reformulated using a different set of decision variables. Once the new variables have been identified, the entire problem can be reformulated in terms of the new variables. We develop a theory of variable redefinition based on relating the two sets of decision variables by a linear transformation, and describe methods for reformulating the special structure problem. The reformulated models have a more accurate linear relaxation than the problems from which they were derived, an important property within the context of linear programming-based branch-and-bound modeling approaches.
A New Optimality Criterion for Nonhomogeneous Markov Decision Processes
Authors: Hopp Wallace J. , Bean James C. , Smith Robert L.
Published: November 2008

We propose a new definition of optimality for nonhomogeneous Markov decision processes called periodic forecast horizon (PFH) optimality. Using measures of discounting and ergodicity, we establish conditions under which PFH-optimal strategies exist and PFH optimality implies the more conventional notions of α-optimality and average optimality. Finally, we use this definition of optimality as the basis for a direct development of forecast horizon results for discounted and undiscounted nonhomogeneous Markov decision processes.
Technical Note—Variate Generation for Accelerated Life and Proportional Hazards Models
Authors: Leemis Lawrence M.
Published: November 2008

We use accelerated life and proportional hazards lifetime models to account for the effects of covariates on a random lifetime. We find that variate generation algorithms for Monte Carlo simulation in both the renewal and nonhomogeneous Poisson process cases are a simple extension of the inverse cumulative distribution function (cdf) technique.
OR Forum—Perspectives on Queues: Social Justice and the Psychology of Queueing
Authors: Larson Richard C.
Published: November 2008

Queues involve waiting, to be sure, but one's attitudes toward queues may be influenced more strongly by other factors. For instance, customers may become infuriated if they experience social injustice, defined as violation of first in, first out. Queueing environment and feedback regarding the likely magnitude of the delay can also influence customer attitudes and ultimately, in many instances, a firm's market share. Even if we focus on the wait itself, the “outcome” of the queueing experience may vary nonlinearly with the delay, thus reducing the importance of average time in queue, the traditional measure of queueing performance. This speculative paper uses personal experiences, published and unpublished cases, and occasionally “the literature” to begin to organize our thoughts on the important attributes of queueing. To flesh out more of these issues, the author asks for your cards and letters.
A Sample Performance Function of Closed Jackson Queueing Networks
Authors: Cao Xi-Ren
Published: November 2008

A stochastic system such as a queueing network can be specified by system parameters and a set of sequences of random variables that represents the randomness in the system. A “sample performance function” is a measure of system performance as a function of system parameters, for each realization of the random sequences. Although the average of N sample performance functions converges to the expected value of the performance with probability one when N goes to infinity, the average of the derivatives of these N sample performance functions with respect to a parameter may not converge to the derivative of the expected value. In this paper, we study a sample performance function of a closed Jackson queueing network; specifically, the time required by a server to serve a finite number of customers. We show that this sample performance function is a continuous, piecewise linear function of the mean service time. We prove that the average of derivatives of this sample performance function with a given initial state does converge, with probability one, to the derivative of the conditional mean value, given the same initial state. The result shows that the estimate of the derivative of a server's mean throughput in a finite time period with respect to the mean service time obtained by infinitesimal perturbation analysis is strongly consistent.
A Simple and Efficient Algorithm to Compute Tail Probabilities from Transforms
Authors: Platzman Loren K. , Ammons Jane C. , Bartholdi John J.
Published: November 2008

We present an algorithm to approximately compute the “tail” probability that a random variable exceeds a specified number, given only an expression for its transform. We also show that the problem is #P-hard (more difficult than NP-hard), suggesting that no efficient procedure can solve it exactly. Our method consists essentially of summing a power series, and thus is easy to perform and requires little memory. Furthermore, its computational effort is nearly linear in the reciprocal of a prespecified worst-case error bound.
Technical Note—An Improved Transformation of the Symmetric Multiple Traveling Salesman Problem
Authors: Jonker Roy , Volgenant Ton
Published: November 2008

We improve the standard transformation of the symmetric, single-depot, multiple traveling salesman problem (MTSP) to one on a sparser edge configuration. The improvement tends to suppress, to a large extent, the degeneracy of the resulting symmetric traveling salesman problem (TSP). As a result, a 1-tree based TSP algorithm solves large MTSPs of the type we consider as easily as it solves standard TSPs. We demonstrate the improvement by presenting computational results that are currently the best available.
The Nozzle Guide Vane Problem
Authors: Plante Robert D.
Published: November 2008

The nozzle guide vane problem addresses the issue of maximizing the number of aircraft gas turbine engine nozzles that can be assembled, within strict specifications, from an inventory of nozzle guide vanes. Past research efforts have decomposed this problem into two related problems: (1) the assignment of nozzle guide vanes in inventory to a nozzle, and (2) the uniform sequencing of the vanes that have been assigned to a nozzle. Both of these problems have been shown to be NP-hard. Consequently, to obtain an efficient system that may be used effectively in a real-time manufacturing environment, we developed heuristic procedures and showed them to be effective in solving these problems. We describe the nozzle guide vane problem in detail and trace some of the developments in measurement technology that fostered the realization of the problem and facilitated the use of operations research techniques to solve it. We then develop a procedure for the uniform sequencing of a heterogeneous set of vanes within a nozzle. Empirically, the procedure is shown to be effective and requires a computational effort that is acceptable for practical implementation in a real-time manufacturing environment. This procedure, combined with those from past research, has been designed into a system that has been successfully implemented in practice. We use an actual vane inventory to demonstrate the use of the system, and discuss some short term benefits and expected long term benefits that have been and may be realized through the use of the system.
OR Practice—The Army Manpower Long-Range Planning System
Authors: Gass Saul I. , Collins Roger W. , Meinhardt Craig W. , Lemon Douglas M. , Gillette Marcia D.
Published: November 2008

The Army Manpower Long-Range Planning System (MLRPS) provides the analytical capability to project the strength of the active U.S. Army for 20 years, thus allowing for the development of long-range manpower plans. The system's models simulate the interaction of gains, losses, promotions and reclassifications to enable the analyst to determine the impact of existing policies over the long term, and to determine changes that might be required to reach a desired force. The MLRPS currently supports the personnel planning requirements of the Army Office of the Deputy Chief of Staff for Personnel in long-range planning, policy planning and force structure analysis, and cost analysis. This article describes the system's main elements and component subsystems.
Estimating the Performance of Multi-Level Inventory Systems
Authors: Svoronos Antony , Zipkin Paul
Published: November 2008

B. Deuermeyer and L. B. Schwarz have developed a very simple approximation of a complex multi-echelon system. Here we propose several refinements of their technique, leading to models nearly as simple and considerably more robust. Our analysis suggests guidelines for the design of large-scale logistics systems, differing markedly from those of earlier studies.
An Approximation Method for Tandem Queues with Blocking
Authors: Brandwajn Alexandre , Jow Yung-Li Lily
Published: November 2008

We propose an approximate analysis of open systems of tandem queues with blocking caused by finite buffers between servers. Our approach relies on the use of marginal probability distributions (“state equivalence”) coupled with an approximate evaluation of the conditional probabilities introduced through the equivalence. The method iterates over consecutive pairs of servers using the solution of a two-queue system as a building block. It produces performance measures for individual servers as well as an approximation to joint queue-length probability distributions for pairs of neighboring stations. Experience indicates that the number of iterations required for the method grows moderately with the number of nodes in the network. We give examples to demonstrate the accuracy and the convergence properties of the proposed approximation.
Empirical Evaluation of a Queueing Network Model for Semiconductor Wafer Fabrication
Authors: Chen Hong , Harrison J. Michael , Mandelbaum Avi , Van Ackere Ann , Wein Lawrence M.
Published: November 2008

This paper concerns performance modeling of semiconductor manufacturing operations. More specifically, it focuses on queueing network models for an analysis of wafer fabrication facilities. The congestion problems that plague wafer fabrication facilities are described in general terms, and several years' operating data from one particular facility are summarized. A simple queueing network model of that facility is constructed, and the model is used to predict certain key system performance measures. The values predicted by the model are found to be within about 10% of those actually observed. These results suggest that queueing network models can provide useful quantitative guidance to designers of wafer fabrication facilities, and we discuss refinements and extensions of our elementary model that are likely to be important in other settings. However, an even more important benefit to be gained from queueing theory is the simple qualitative point that congestion and delay in wafer fabrication are caused by variability in the operating environment. To significantly reduce manufacturing cycle times, one must reduce that variability.
The Role of Work-in-Process Inventory in Serial Production Lines
Authors: Conway Richard , Maxwell William , McClain John O. , Thomas L. Joseph
Published: November 2008

In serial production systems, storage may be provided between processes to avoid interference due to lack of synchronization. This paper investigates the behavior of lines buffered in this way and explores the distribution and quantity of work-in-process (WIP) inventory that accumulates. We study simple, generic production systems to gain insight into the behavior of more complex systems. The authors are surprised by the sometimes counterintuitive results, but are joined in this surprise by both academics and practitioners with whom the study has been discussed. Results are presented for: identical workstations with and without buffers; balanced lines in which variability of processing times differs between stations; unbalanced lines; and lines with unreliable workstations. In general, buffers between workstations increase system capacity but with sharply diminishing returns. Position as well as capacity of the buffers are important. These results are preliminary, to be confirmed and extended by further study—indeed, a primary purpose of this paper is to stimulate such study. However, even these preliminary results yield design guidelines that should be useful in industrial practice.
Dynamic Scheduling and Routing for Flexible Manufacturing Systems that Have Unreliable Machines
Authors: Maimon Oded Z. , Gershwin Stanley B.
Published: November 2008

This paper presents a method for real-time scheduling and routing of material in a Flexible Manufacturing System (FMS). It extends the earlier scheduling work of Kimemia and Gershwin in which the FMS model includes machines that fail at random times and stay down for random lengths of time. The new element is the capability of different machines to perform some of the same operations. The times that different machines require to perform the same operation may differ. This paper includes a model, its analysis, a real-time algorithm, and examples.
On Server Allocation in Multiple Center Manufacturing Systems
Authors: Shanthikumar J. George , Yao David D.
Published: November 2008

We study the problem of allocating a given number of identical servers among the work centers of a manufacturing system. The problem is formulated as a nonlinear integer program of allocating servers in a closed queueing network to maximize throughput. We show that the throughput of the closed queueing network has a monotonicity property, such that any optimal allocation must give more servers to stations with a higher workload. The number of allocations that satisfy this property is much smaller than the total number of feasible allocations. This property and a bounding technique for the throughput of the closed queueing network are combined to develop a search algorithm to obtain an optimal allocation of servers. A greedy heuristic is also developed, and its optimality proven in the special case of a two-center system (in the general case, its optimality remains a conjecture).
Buffer Space Allocation in Automated Assembly Lines
Authors: Smith J. MacGregor , Daskalaki Sophia
Published: November 2008

Automated assembly lines are modeled as finite open queueing networks and a heuristic for buffer space allocation within these lines is presented. The Expansion Method, an analytical technique for modeling finite open queueing networks and Powell's unconstrained optimization procedure are integrated in a design methodology, which evaluates alternative line topologies, system throughputs, and their optimal buffer sizes. The resulting design methodology is demonstrated for series, merging and splitting topologies of automated assembly lines with balanced and unbalanced service rates.
An Adaptable Scheduling Algorithm for Flexible Flow Lines
Authors: Wittrock Robert J.
Published: November 2008

Consider a manufacturing line that produces parts of several types. Each part must be processed by at most one machine in each of several banks of machines. This paper presents an algorithm that schedules the loading of parts into such a line. The objective is primarily to minimize the makespan and secondarily to minimize queueing. The problem is decomposed into three subproblems and each of these is solved using a fast heuristic. The most challenging subproblem is that of finding a good loading sequence, and this is addressed using workload concepts and an approximation to dynamic programming. We make several extensions to the algorithm in order to handle limited storage capacity, expediting, and reactions to system dynamics. The algorithm was tested by computing schedules for a real production line, and the results are discussed.
An Interpolation Approximation for Queueing Systems with Poisson Input
Authors: Reiman Martin I. , Simon Burton
Published: November 2008

For many queueing systems of practical interest, it is difficult to obtain exact analytical results. It is, however, often possible to obtain asymptotic results for light and heavy traffic. Heavy traffic limit theorems yield expressions for normalized quantities of interest. In light traffic, we can obtain, in addition to limits, more sensitive information by calculating what are effectively derivatives (of the quantity of interest) with respect to the arrival rate. We can then combine the light and heavy traffic results to yield a polynomial (in the arrival rate) as an approximation to the normalized quantity of interest. For instance, by utilizing the heavy traffic limit, the light traffic limit, and the first derivative, we can obtain a quadratic approximation. Then, by reversing the normalization process, we can obtain an approximation for the original quantity of interest. In this paper we present the details of the above approximation, focusing, via several examples, on applications of the method. We then compare the results of the approximation, for the examples considered, with exact and simulation results. In addition, we compare our results to some related approximations. For the examples considered, the approximation works extremely well.
A Heuristic Algorithm for the Traveling Salesman Location Problem on Networks
Authors: Simchi-Levi David , Berman Oded
Published: November 2008

In this paper, we present a heuristic for the traveling salesman location problem on a network. Each day the salesman (e.g., a repair vehicle) must visit all the calls that are registered in a service list. Each call is generated with a given probability and the service list contains at most n calls. The heuristic requires O(n3) time to find the location that “minimizes” the expected distance traveled. A worst case analysis of the heuristic indicates that it will produce a solution which is at most 50% worse than the optimal solution. The paper also contains several asymptotic results for the problem in the plane.
The Euclidean Multifacility Location Problem
Authors: Radó Francisc
Published: November 2008

To solve the Euclidean multifacility location problem, W. Miehle extended the Weiszfeld algorithm from one to several facilities. L. M. Ostresh established that the objective function for the iterates of Miehle's algorithm decreases in value, but his results do not give a convergence proof. In this paper we give a new extension of the Weiszfeld algorithm and by generalizing the Kuhn-Ostresh convergence theorem, prove separate results for convergence and for optimality, both under mild hypotheses.
On Stochastic Decomposition in M/G/1 Type Queues with Generalized Server Vacations
Authors: Shanthikumar J. George
Published: November 2008

Recently, S. W. Fuhrmann and R. B. Cooper showed that the stationary distribution of the number of customers in an M/G/1 queueing system with generalized server vacation is a convolution of the distribution functions of two independent positive random variables. One of these is the stationary distribution of the number of customers in an ordinary M/G/1 queueing system without server vacations. They use an elegant, intuitive approach to establish this result. In this paper, a mechanistic (analytic) proof of this result is given for systems more general than that discussed in Fuhrmann and Cooper. Such systems allow customer arrivals in bulk and some variations with reneging, balking, and in arrival rate that is dependent on system state.
Sensitivity of the EOQ Model to Parameter Estimates
Authors: Dobson Gregory
Published: November 2008

The Economic Order Quantity (EOQ) model for independent demand is well known to be somewhat insensitive to the choice of order quantity. The cost goes up as the square root of the ratio of the actual order quantity to that of the optimal order quantity. The question arises as to how sensitive this cost is to parameter estimates. This paper extends the work by T. J. Lowe and L. B. Schwarz to show that under minimax and expected value criteria, the sensitivity of the cost to the parameters of the model grows as the fourth root of the uncertainty in the values of the parameters. Furthermore, for a wide class of distributions, including the beta (hence, uniform) and the gamma (hence, exponentials), a tight bound exists for the expected error.
Probabilistic Inference and Influence Diagrams
Authors: Shachter Ross D.
Published: November 2008

An influence diagram is a network representation for probabilistic and decision analysis models. The nodes correspond to variables which can be constants, uncertain quantities, decisions, or objectives. The arcs reveal the probabilistic dependence of the uncertain quantities and the information available at the time of the decisions. The detailed data about the variables are stored within the nodes, so the diagram graph is compact and focuses attention on the relationships among the variables. Influence diagrams are effective communication tools and recent developments also allow them to be used for analysis. We develop algorithms to address questions of inference within a probabilistic model represented as an influence diagram. We use the conditional independence implied by the diagram's structure to determine the information needed to solve a given problem. When there is enough information we can solve it, exploiting that conditional independence. These same results are applied to problems of decision analysis. This methodology allows the construction of computer tools to maintain and evaluate complex models.
Bargaining Under Two-Sided Incomplete Information: The Unrestricted Offers Case
Authors: Chatterjee Kalyan , Samuelson Larry
Published: November 2008

Chatterjee and Samuelson (Chatterjee, K., L. Samuelson. 1987. Bargaining with two-sided incomplete information: An infinite horizon model with alternating offers. Rev. Econ. Stud. 54 175–192.) recently examined a noncooperative game-theoretic bargaining model with two-sided incomplete information and an infinite horizon. Results were obtained from the model with the help of restrictions on agents' strategies. This paper examines the model without these restrictions. By doing so, we will gain some insight into whether these results are robust, in the sense that they do not depend upon the special structure of the model, and hence, might provide useful theoretical foundations for applied work. We find that the basic results generalize. As with the restricted model, we find an equilibrium in which bargaining will proceed for a finite but endogeneously determined number of stages. A terminal condition on the equilibrium sequence of agents' beliefs determines the properties of the equilibrium and allows comparative static results to be obtained. These include the finding that agents are more likely to capture a large share of the potential gains from bargaining if they exhibit characteristics that can be readily interpreted as giving them more bargaining power. Unlike the restricted model, this equilibrium is not unique, though we argue that it is plausible.
OR Practice—Estimating Visual Detection Performance at Sea
Authors: Engel D. D. , Weisinger J. R.
Published: November 2008

This paper discusses the problem of estimating lateral range functions and sweep widths from data collected during visual detection experiments. We report a physical model for visual detection and the results of applying this methodology to data collected by the U.S. Coast Guard. These results are being incorporated in an updated version of the National Search and Rescue Manual.
Disjoint Products and Efficient Computation of Reliability
Authors: Ball Michael O. , Provan J. Scott
Published: November 2008

In this paper, we analyze the problem of computing the probability of the union of a set of events, where each event is given as the product of a set of Boolean variables. Each Boolean variable represents the operation or failure of a particular component. The problem has direct applications to the reliability analysis of complex systems as well as more general applications. After showing that the problem is NP-hard in general, we define simple, computationally efficient procedures for generating upper and lower bounds on the required probability. We show that these procedures produce the exact answer, i.e., the upper bound equals the lower bounds, for two classes of systems, matroids and threshold systems. These results draw on the relationship between this problem and the notion of shellability studied in the context of simplicial polytopes. Shellability is shown to have a very interesting and useful interpretation in this problem setting.
The Analysis of Random Polling Systems
Authors: Kleinrock Leonard , Levy Hanoch
Published: November 2008

In this paper, we analyze the behavior of random polling systems. The polling systems we consider consist of N stations, each equipped with an infinite buffer and a single server who serves them in some order. In contrast to previously studied polling systems, where the order of service used by the server is periodic (and usually cyclic), in the systems we consider the next station to be served after station i is determined by probabilistic means. More specifically, according to the model we consider in this paper, after serving station i, the server will poll (i.e., serve) station j (j = 1, 2, …, N) with probability pj. The main results of this paper are expressions for the expected response time in a random polling system operated under a variety of service disciplines. The results are compared to the response time in the equivalent cyclic polling systems. Also in this paper, we analyze the cycle time and the number of customers found in the system.
Multi-Item Inventory Systems with a Service Objective
Authors: Mitchell J. Christopher
Published: November 2008

In this paper, we examine the problem of specifying single-item service objectives in a multi-item inventory system subject to a system wide service level constraint. We develop a computationally efficient algorithm, the Generalized Knapsack Duality (GKD) Algorithm, to find approximately optimal policies for such a system. Our computational experience with inventory systems, typical of many found in the real world, indicates that operating costs can be reduced significantly when this model is used rather than the simpler uniform service model often used in practice.
Models Arising from a Flexible Manufacturing Machine, Part I: Minimization of the Number of Tool Switches
Authors: Tang Christopher S. , Denardo Eric V.
Published: November 2008

This paper considers a job scheduling problem for a flexible manufacturing machine. This problem arises in the metal working industry when numerical controlled (N/C) machines are used to manufacture parts (jobs). Assume that each of N jobs must be processed on a machine that has positions for C tools, but no job requires more than C tools. If the requisite tools are not on the machine, then one or more tool switches must occur before the job can be processed. The problem consists of finding the sequence in which to process the jobs and the tools to place on the machine before each job is processed. This paper considers one performance criterion: minimize the total number of tool switches. This criterion is adequate for situations where the tool switching time is proportional to the number of tool switches. In our model, we assume that the time needed to switch tools is significant relative to the job processing time. A feasible solution is in “equilibrium” if better performance cannot be attained by changing either the job sequence or the tool placement specified by the solution unilaterally. Procedures that find an equilibrium are presented in this paper.
Models Arising from a Flexible Manufacturing Machine, Part II: Minimization of the Number of Switching Instants
Authors: Tang Christopher S. , Denardo Eric V.
Published: November 2008

This paper deals with a job scheduling problem for a flexible manufacturing machine. We consider the same manufacturing environment described in a companion study (Part I), but we use a different performance criterion: to minimize the total number of instants at which tools are switched. This performance criterion is appropriate when the switching time is roughly constant and independent of the number of tool switches. We show that this scheduling problem generalizes the classical bin packing problem, and we present a non-LP-based branch-and-bound procedure that terminates with an optimal solution. We extend this procedure to the case of K machines in sequence.
OR Practice—A Logistics Planning System at W. R. Grace
Authors: Klingman Darwin , Mote John , Phillips Nancy V.
Published: November 2008

This paper describes an optimization-based logistics planning system developed for W. R. Grace Company, one of the nation's largest suppliers of phosphate-based chemical products. The mathematical model underlying this system includes production, distribution, multiple time periods, and multiple commodities. W. R. Grace initially formulated the model as a linear programming problem with 3,696 constraints and 21,564 variables. We developed an innovative modeling/solution approach to enhance top management's understanding of the model and to make the problem more tractable for the company's DEC 20/60 computer. The key features of this modeling/solution approach are: decomposition of the problem into a generalized network component and a small linear nonnetwork component, transformation of the generalized network component into a pure network, incorporation of most of the nonnetwork component into the pure network via an innovative relaxation approach, and incorporation of the remainder into the objective function via Lagrangian procedures. We solve the resulting model relaxation using highly efficient pure network solution techniques to obtain an advanced starting basis for a basis partitioning algorithm. This approach reduces solution time approximately 10-fold. In addition, W. R. Grace used insights gleaned from the solutions to make multimillion dollar decisions.
A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited
Authors: Jaillet Patrick
Published: November 2008

Consider a problem of routing through a set of n points. On any given instance of the problem, only a subset consisting of k out of n points (0 ≤ k ≤ n) has to be visited, with the number k random with known probability distribution. We wish to find a priori a tour through all n points. On any given instance, the k points present will then be visited in the same order as they appear in the a priori tour. The problem of finding such a tour of minimum length in the expected value sense is defined as a Probabilistic Traveling Salesman Problem (PTSP). What distinguishes one PTSP from another is the probability distribution (or more generally, the probability “law”) that specifies the number k and the identity of the points that need to be visited on any given instance of the problem. After motivating the problem by applications, we first derive closed form expressions for computing efficiently the expected length of any given tour under very general probabilistic assumptions. We then provide, in a unified way, an analysis of these expressions and derive several interesting properties of the problem.
Blocking Probability for M/G/1 Vacation Systems with Occupancy Level Dependent Schedules
Authors: Keilson J. , Servi L. D.
Published: November 2008

An M/G/1 queue with finite buffer capacity and server vacation schedules dependent on occupancy level is studied. The blocking probability is expressed simply in terms of the ergodic queue length probabilities for the infinite buffer case.
Numerical Solutions of the Waiting Time Distribution and Idle Time Distribution of the Arithmetic GI/G/1 Queue
Authors: Grassmann Winfried K. , Jain Joti L.
Published: November 2008

In this paper, we present an efficient numerical method for calculating the waiting time and idle time distributions of the arithmetic GI/G/1 queue. Our method is based on the Wiener-Hopf factorization, which is briefly reviewed. Compared to the related methods suggested in the literature, our method seems to perform very well, and it is often faster by several orders of magnitude. A number of numerical examples conclude the paper.
A New Class of Multivariate Phase Type Distributions
Authors: Kulkarni V. G.
Published: November 2008

A new class of multivariate phase type distributions (denoted by MPH*) is defined, based upon the total accumulated reward until absorption in a finite state, continuous time Markov chain. This new class is shown to be a strict superset of the class of multivariate phase type distributions MPH introduced by Assaf, Langberg, Savits and Shaked. A conjectured property (viz, closure under finite convolutions) of the class MPH is proved using the class MPH* defined here. Computational techniques for the distributions in MPH* are discussed. Closure properties of MPH* are stated and an open problem is discussed.
Technical Note—Optimal Pole-Vaulting Strategy
Authors: Hersh Marvin , Ladany Shaul P.
Published: November 2008

Under present international track and field rules, a participant in a pole-vaulting competition is entitled to select the heights of his vaulting attempts at all stages of the contest. The restrictions imposed are that sequential vaulting attempts should not be at decreasing bar heights, and that three unsuccessful attempts in succession—at any height—terminates participation in the contest. The last successful vault is the height scored by that participant in the competition. A dynamic programming model has been constructed to provide the optimal set of heights which the competitor should attempt to vault. These will depend on the last height cleared successfully, the total number of previous attempts, and the number of failed attempts since the last success. The strategy is directed at achieving the maximum expected height scored in the competition using readily available experimental data. A numerical example is provided, demonstrating the advantages gained in using the optimal strategy versus traditional patterns.
The Formal Aspects of Structured Modeling
Authors: Geoffrion Arthur M.
Published: November 2008

Structured modeling is an approach to the development of a new generation of computer-based modeling environments. This paper, which is part of a series, presents a formal development of the definitions and theory of structured modeling.
Restricted Subset Selection Procedures for Simulation
Authors: Sullivan David W. , Wilson James R.
Published: November 2008

This paper develops two procedures for screening a set of normal populations with unknown moments in order that the final subset of selected populations satisfies the following requirements involving the user specified parameters P*, δ, and m: With probability at least P*, the selected subset will contain a population whose mean lies less than the distance δ from the largest mean. Although the size of the selected subset is random, at most m populations will finally be chosen, where m is usually taken small enough to reserve adequate resources for a more intensive follow-up study. The exact procedure VE is a two-stage random sampling scheme that is designed to compare transient or steady-state simulation models based on independent replications of each model. The heuristic procedure VS is a modification of VE that is designed to compare steady-state simulation models based on a single prolonged run of each model. A complete justification is given for VE together with tables of the constants required by both procedures and an algorithm for computing these constants. Experimental results are summarized to gauge the robustness of VE against departures from normality and to evaluate the performance of VS on several types of stationary stochastic processes.
Indirect Estimation Via L = λW
Authors: Glynn Peter W. , Whitt Ward
Published: November 2008

For a large class of queueing systems, Little's law (L = λW) helps provide a variety of statistical estimators for the long-run time-average queue length L and the long-run customer-average waiting time W. We apply central limit theorem versions of Little's law to investigate the asymptotic efficiency of these estimators. We show that an indirect estimator for L using the natural estimator for W plus the known arrival rate λ is more efficient than a direct estimator for L, provided that the interarrival and waiting times are negatively correlated, thus extending a variance-reduction principle for the GI/G/s model due to A. M. Law and J. S. Carson. We also introduce a general framework for indirect estimation which can be applied to other problems besides L = λW. We show that the issue of indirect-versus-direct estimation is related to estimation using nonlinear control variables. We also show, under mild regularity conditions, that any nonlinear control-variable scheme is equivalent to a linear control-variable scheme from the point of view of asymptotic efficiency. Finally, we show that asymptotic bias is typically asymptotically negligible compared to asymptotic efficiency.
OR Practice—Application of a Probabilistic Decision Model to Airline Seat Inventory Control
Authors: Belobaba Peter P.
Published: November 2008

The application of booking limits on the number of seats available at different prices on the same flight allows airlines to increase revenues. Effective seat inventory control by an airline depends on forecasts of future bookings, the revenue values associated with each fare type, and an ability to make systematic tradeoffs between booking requests so as to maximize total flight revenues. This article describes the implementation of a computerized system for making these tradeoffs and setting booking limits on future flights at Western Airlines in early 1987. The Expected Marginal Seat Revenue (EMSR) decision model developed for this application takes account of the uncertainty associated with estimates of future demand as well as the nested structure of booking limits in airline reservations systems. The Automated Booking Limit System implemented at Western made use of the EMSR model to set and revise booking limits periodically prior to flight departure. Although the system did not take into account several important components of the seat inventory control problem, a revenue impact test on a sample of actual flights showed a significant revenue improvement over the judgmental methods used previously.
The Confidence Profile Method: A Bayesian Method for Assessing Health Technologies
Authors: Eddy David M.
Published: November 2008

The Confidence Profile Method is a Bayesian method for adjusting and combining pieces of evidence to estimate parameters, such as the effect of health technologies on health outcomes. The information in each piece of evidence is captured in a likelihood function that gives the likelihood of the observed results of the evidence as a function of possible values of the parameter. A posterior distribution is calculated from Bayes formula as the product of the likelihood function and a prior distribution. Multiple pieces of evidence are incorporated by successive applications of Bayes' formula. Pieces of evidence are adjusted for biases to internal or external validity by modeling the biases and deriving “adjusted” likelihood functions that incorporate the models. Likelihood functions have been derived for one-, two- and multi-arm prospective studies; 2 × 2, 2 × n and matched case-control studies, and cross-sectional studies. Biases that can be incorporated in likelihood functions include crossover in controlled trials, error in measurement outcomes, patient selection biases, differences in technologies, and differences in length of follow-up. Effect measures include differences of rates, ratios of rates, and odds ratios. The elements of the method are illustrated with an analysis of the effect of a thrombolytic agent on the difference in probability of 1-year survival after a heart attack.
Equity Considerations in Public Risks Evaluation
Authors: Fishburn Peter C. , Straffin Philip D.
Published: November 2008

Recent contributions by R. K. Sarin, and R. L. Keeney and R. L. Winkler, approach the problem of public risks evaluation from a multiattribute perspective in which fatalities, ex ante equity, and ex post equity play leading roles. The present paper considers the same problem from the perspective of holistic comparisons between potential fatality distributions. We consider a number of axioms for such comparisons, identify maximally compatible sets of axioms, and relate our approach to the multiattribute approach. We also identify a form of dispersive equity that is not discussed in recent work but deserves further consideration.
Approximate Order Quantities and Reorder Points for Inventory Systems Where Orders Arrive in Two Shipments
Authors: Moinzadeh Kamran , Lee Hau L.
Published: November 2008

In this paper, we consider an inventory system where orders may arrive in two shipments, that is, the first shipment of the order may contain only part of the items ordered, while the rest of the items arrive in a second shipment. However, the amount of the first shipment is random. Such situations arise when the supplier partially fills an order if it does not have sufficient stock to satisfy the amount demanded in an order, or when an arriving order contains defective items that can be returned to and replaced by the supplier at some later date. We present the operating characteristics and an approximate cost function for such a system. The properties of the approximate cost function are exploited to bound the search for the order quantity and reorder point that minimize it. Finally, the effectiveness of the approximate cost function in providing near-optimal solutions is evaluated by means of numerical examples.
An Additive Bounding Procedure for Combinatorial Optimization Problems
Authors: Fischetti Matteo , Toth Paolo
Published: November 2008

We know that the effectiveness of the branch-and-bound algorithms proposed for the solution of combinatorial optimization problems greatly depends on the tightness of the available bounds. In this paper, we consider optimization problems with a linear objective function. We propose an additive approach for computing lower bounds that yields an increasing sequence of values. An application to the traveling salesman problem with precedence constraints is presented to exemplify the technique.
A Resource Allocation Problem in a Random Environment
Authors: Righter Rhonda
Published: November 2008

We consider a resource allocation problem in which various parameters of the model change according to independent random environment Markov processes. There are a finite number of activities that each require a resource, and resources arrive according to a Poisson process. Both activities and resources have values associated with them and the return from allocating a resource to an activity is the product of the activity value and the resource value. Activity values are known ahead of time but the values of resources are independent random variables from a common distribution and are known only after the arrival of the resource. We wish to assign arriving resources to available activities so as to maximize our total expected return. It is assumed that either there is a single random deadline for all activities, which is the same as discounting the returns, or the activities have independent random deadlines. The model has applications to processor scheduling, selling of assets, and kidney allocation for transplant. We consider the effects on the structure of the optimal policy of allowing parameters to be determined by independent Markov processes. In particular, we permit the resource arrival rate, the activity values, the deadline rates, and the variability of the resource distribution to change. We give conditions under which the total optimal expected return is monotone in the states of the Markov processes. We also show that the total optimal return is increasing and convex in the activity values, decreasing and convex in the deadline rates, and increasing if the variability of the distribution of resource values is increasing.
Technical Note—Identifying Forecast Horizons in Nonhomogeneous Markov Decision Processes
Authors: Hopp Wallace J.
Published: November 2008

A procedure for identifying forecast horizons in nonhomogeneous Markov decision processes, based on convergence results for relative value functions, is developed. Two different algorithmic implementations of this procedure are discussed, and a closed form expression for computing sufficiently long horizons to guarantee epsilon optimality is presented.