bluuebunny/crossref_metadata_2025 huggingface dataset:
An Analytical Evaluation of Alternative Strategies in Steady-State Simulation
Authors: Kelton W. David , Law Averill M.
Published: November 2008

We consider the simple technique of making independent and probabilistically identical simulation replications to estimate the steady-state mean of a stochastic process. For a fixed total sample size, using a first-order autoregressive model with high autocorrelation and time-dependent distributions, we analytically quantify and investigate the effects of the number of replications and of initial deletions of output on several different measures of point estimator and confidence interval quality. This analysis leads to general recommendations on the choice of replications and deletion. In particular, we conclude that deletion of some amount of the initial output in a replication can be an effective and efficient method of dealing with initialization bias; this conclusion differs from several previous studies on the efficacy of deletion.
Quantile Estimation in Dependent Sequences
Authors: Heidelberger P. , Lewis P. A. W.
Published: November 2008

Standard nonparametric estimators of quantiles based on order statistics can be used not only when the data are i.i.d., but also when the data are drawn from a stationary, ϕ-mixing process of continuous random variables. However, when the random variables are highly positively correlated, the sample sizes needed for estimating extreme quantiles become computationally unmanageable. This paper gives a practical scheme, based on a maximum transformation in a two-way layout of the data, that reduces the sample size sufficiently to allow an experimenter to obtain a point estimate of an extreme quantile. The paper gives three schemes that lead to confidence interval estimates for the quantile. One uses a spectral analysis of the reduced sample. The other two, averaged group quantiles and nested group quantiles, are extensions of the method of batched means to quantile estimation. These two schemes give even greater data compaction than the first scheme. None of the schemes requires that the process being simulated is regenerative.
Minimizing Delays in the GI/G/1 Queue
Authors: Whitt Ward
Published: November 2008

What service-time distribution minimizes delays in a GI/G/1 queue with given renewal arrival process and given mean service time? It is natural to conjecture that the deterministic service-time distribution with unit mass on the mean is optimal for all objective functions of the form Ef(W) where f is a nondecreasing function of the steady-state delay W. However, we show that this conjecture is false. In fact, for hyperexponential interarrival-time distributions (mixtures of two exponential distributions), the service-time distribution minimizing the average delay maximizes the proportion of customers delayed.
The Solution of the Chemical Equilibrium Programming Problem with Generalized Benders Decomposition
Authors: Clasen Richard J.
Published: November 2008

This paper deals with an algorithm for the solution of the chemical equilibrium problem that parallels Geoffrion's development of the Generalized Benders Decomposition Algorithm. The unknowns of the problem are decomposed into the phase sums, which are the complicating variables, and normalized variables. The algorithm obtained is an iterative procedure where the master problem computes optimal phase sums and the subproblem computes new dual variables. A numerical study indicates that best results are obtained when the subproblem is suboptimized.
On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals
Authors: Simons Barbara , Sipser Michael
Published: November 2008

We consider the problem of scheduling n unit-time jobs with multiple release time/deadline intervals, which are intervals of time in which the job can be scheduled. A feasible schedule is one in which each job is run in its entirety within one of its release time/deadline intervals. We show that the general problem is NP-complete, but that for a special case one can determine in polynomial time if a feasible schedule exists. If there is a feasible schedule for the special case, then it is possible to obtain both a schedule that minimizes the maximum completion time and also one that minimizes the sum of the completion times of all jobs. If, on the other hand, there is no feasible schedule, then one can determine the minimum number of jobs that must be removed to make the problem instance feasible.
Development Planning and Management of Petroleum Reservoirs Using Tank Models and Nonlinear Programming
Authors: McFarland James W. , Lasdon Leon , Loose Verne
Published: November 2008

This paper demonstrates the feasibility of applying generalized reduced gradient nonlinear programming methods to solve optimal control models for petroleum reservoir development planning and management. The objective of the models is to maximize present value of profits, and their decision variables are how many wells to drill in each time period, the production rates, abandonment time, and platform size. The analysis uses tank-type reservoir models to describe the reservoir dynamics, and models both a gas reservoir with water drive, and a three phase oil reservoir. Results of several case studies on each model are presented. Extensions that consider spatial variation in the reservoir and use grid reservoir models are being investigated.
An Algorithm for the Bottleneck Traveling Salesman Problem
Authors: Carpaneto Giorgio , Martello Silvano , Toth Paolo
Published: November 2008

Given a graph with arc costs, the Bottleneck Traveling Salesman Problem is to find a Hamiltonian circuit that minimizes the largest cost of any of its arcs. Lower bounds for the problem (bottleneck assignment problem, bottleneck paths, bottleneck arborescence, cuts) are analyzed and combined to obtain a bounding procedure for a breadth-first branch and bound algorithm. At each node of the branch-decision tree, the algorithm uses a heuristic search to find a Hamiltonian circuit containing only arcs whose cost is not greater than the current lower bound, the aim being to reduce the number of nodes explored. Extensive computational results are discussed. These show that, unlike the classical Traveling Salesman Problem, the same algorithm can be used successfully for large numbers of vertices both in symmetric and in asymmetric cases. Results for Euclidean graphs are also presented.
Technical Note—There are No Undiscovered Priority Index Sequencing Rules for Minimizing Total Delay Costs
Authors: Rothkopf Michael H. , Smith Stephen A.
Published: November 2008

There are two known priority index rules for minimizing total delay costs in sequencing a finite group of independent tasks on a single processor. One of these rules applies when delay costs are linear and the other when they are restricted to a class of exponential functions. We prove that there are no other classes of delay cost function for which a simple priority index rule is optimal.
Computing Network Reliability in Time Polynomial in the Number of Cuts
Authors: Provan J. Scott , Ball Michael O.
Published: November 2008

We present a new algorithm that computes the probability that there is an operating path from a node s to a node t in a stochastic network. The computation time of this algorithm is bounded by a polynomial in the number of (s, t)-cuts in the network. We also examine the complexity of other connectedness reliability problems with respect to the number of cutsets and pathsets in the network. These problems are distinguished as either having algorithms that are polynomial in the number of such sets, or having no such algorithms unless P = NP.
Effects of False and Incomplete Identification of Defective Items on the Reliability of Acceptance Sampling
Authors: Kotz Samuel , Johnson Norman L.
Published: November 2008

The effects of false and incomplete identification of nonconforming items on the properties of two-stage acceptance sampling procedures are studied. Numerical tables are presented, and there is some discussion of sensitivity to inspection errors. Methods of taking into account extra costs needed to implement better inspection techniques, when initial grading is inconclusive, are described.
A Preventive Replacement Policy for Units Subject to Intermittent Demand
Authors: Berg Menachem
Published: November 2008

We propose a preventive replacement policy for a unit that is in demand only part of the time and is inactive otherwise. Under this policy, called a modified age replacement policy, the unit is replaced preventively at the first no-demand period at which its operational age exceeds some control limit. We use a marginal cost analysis to find the optimal control limit that minimizes the limiting conditional probability that the unit is down when it is demanded. We then compare the optimal limiting conditional probability that the unit is down when it is demanded for the modified age replacement policy and the age replacement policy.
Continuous Multistate Structure Functions
Authors: Block H. W. , Savits T. H.
Published: November 2008

Usually, systems and components are described as being in one of two modes, “on” or “off.” Such systems are described using binary structure functions. More realistically, components can be in more than two states—for example, there can be partially failed or partially operating modes. In fact, the system state can be described by continuously many values if percentage effort or percentage capacity is recorded. This paper discusses the structure functions of such continuous multistate systems and obtains a decomposition of these functions into more elementary functions.
M/G/1/N Queue with Vacation Time and Exhaustive Service Discipline
Authors: Lee Tony T.
Published: November 2008

This paper studies an M/G/1 queueing system with a finite waiting room and with server vacation times consisting of periods of time that the server is away from the queue doing additional work. This model has been used in conjunction with a related model to analyze the performance of a processor with a cyclic scheduling algorithm and where, due to finite queueing capacities, losses are a primary concern. Service at the queue is exhaustive, in that a busy period at the queue ends only when the queue is empty. At each termination of a busy period, the server takes an independent vacation. The queue length process is studied using the embedded Markov chain. Using a combination of the supplementary variable and sample biasing techniques, we derive the general queue length distribution of the time continuous process, as well as the blocking probability of the system, due to the finite waiting room in the queue. We also obtain the busy period and waiting time distributions.
Computational Issues in an Infinite-Horizon, Multiechelon Inventory Model
Authors: Federgruen Awi , Zipkin Paul
Published: November 2008

Clark and Scarf (Clark, A., H. Scarf. 1960. Optimal policies for a multi-echelon inventory problem. Mgmt. Sci. 6 475–490.) characterize optimal policies in a two-echelon, two-location inventory model. We extend their result to the infinite-horizon case (for both discounted and average costs). The computations required are far easier than for the finite horizon problem. Further simplification is achieved for normal demands. We also consider the more interesting case of multiple locations at the lower echelon. We show that, under certain conditions, this problem can be closely approximated by a model with one such location. A rather simple computation thus yields both a near-optimal policy and a good approximation of the cost of the system.
Nonoptimal Edges for the Symmetric Traveling Salesman Problem
Authors: Jonker Roy , Volgenant Ton
Published: November 2008

For the symmetric traveling salesman problem, we identify a set of (undirected) edges that can be eliminated while still retaining at least one optimal solution of the problem. The simple identification rules are based on the fact that a solution can be optimal only if it is 2-optimal. The rules are less stringent than those formulated for nonoptimal arcs (directed), applied to the symmetric case. So, in general, they identify more nonoptimal edges. Application of the theory in a 1-tree based traveling salesman algorithm roughly halves the average computation time for Euclidean problems. We indicate to what extent the theorems presented here can be adapted for variants of the traveling salesman problem.
The Secretary Problem with Optimal Assignment
Authors: Tamaki Mitsushi
Published: November 2008

We consider the secretary problem with assignment of the applicants to m positions to be staffed in order to maximize the probability that we select only the m best, and assign the kth best to the kth position. A simple strategy is proposed. Although the optimal strategies for m = 1, 2 are known to be simple, we show that the optimal strategy for m = 3 is not necessarily simple. However, a simple strategy turns out to be a fairly good suboptimal strategy.
Equity Axioms for Public Risks
Authors: Fishburn Peter C.
Published: November 2008

From the perspective of a two-person society, we explain and analyze six axioms for equity among individuals who are exposed to the possibility of death from a public hazard. The axioms are concerned with how a given total risk (expected fatalities) is distributed over the four possible life/death consequences for the two people. Maximal subsets of mutually compatible equity axioms are identified first for a monotonic ordinal utility function and then for a more restrictive von Neumann-Morgenstern utility function.
Extensions of the Freund Distribution with Applications in Reliability Theory
Authors: Shaked Moshe
Published: November 2008

The Freund distribution models situations in which the exponential residual lifetime of one component depends on the working status of another component. The literature has discussed generalizations and analogs of the Freund distribution. Such generalizations can be obtained by replacing exponential random variables by Weibull or gamma random variables, or by compounding (mixing) Freund distributions. This paper shows how to unify various well-known generalizations of the Freund distribution by using one simple functional representation. This functional representation has a physical meaning that sheds new light on the meaning of some of these generalizations. Furthermore, using this functional representation, we derive various properties of the Freund distribution and its extensions. In particular, we show that some random variables, which have the Freund distribution or one of its extensions, are positively associated and also belong to some classes of multivariate “increasing failure rate average” and “new better than used” distributions. These properties provide bounds for various probabilistic quantities of interest in reliability theory.
A Combined Vehicle Routing and Inventory Allocation Problem
Authors: Federgruen Awi , Zipkin Paul
Published: November 2008

We address the combined problem of allocating a scarce resource among several locations, and planning deliveries using a fleet of vehicles. Demands are random, and holding and shortage costs must be considered in the decision along with transportation costs. We show how to extend some of the available methods for the deterministic vehicle routing problem to this case. Computational results using one such adaptation show that the algorithm is fast enough for practical work, and that substantial cost savings can be achieved with this approach.
Sensitivity Analysis for the General Spatial Economic Equilibrium Problem
Authors: Dafermos Stella , Nagurney Anna
Published: November 2008

We consider the general spatial economic equilibrium problem where the supplies and demands at each market for each commodity may depend on the price on this as well as other prices of other commodities at other markets and the transportation cost on each link for each commodity may depend on the flow on this as well as other flows of other commodities on other links in the network. For this model we perform stability and sensitivity analysis. Assuming that the supply, demand, and transportation cost functions are monotone, we first show that the multicommodity equilibrium price pattern depends continuously upon the market supply and demand functions and the multicommodity equilibrium shipment pattern depends continuously upon the transportation cost functions. We then focus on the delicate question of predicting the direction of the change in the price and shipment pattern and the incurred supplies, demands, and transportation costs resulting from changes in the supply, demand, and transportation cost functions and we demonstrate that certain phenomena may prevail. Our analysis depends crucially on the fact that the governing equilibrium conditions can be formulated as a variational inequality.
Approximating a Point Process by a Renewal Process, II: Superposition Arrival Processes to Queues
Authors: Albin Susan L.
Published: November 2008

We develop an approximation for a queue having an arrival process that is the superposition of independent renewal processes, i.e., ∑GI1/G/1. This model is useful, for example, in analyzing networks of queues where the arrival process to an individual queue is the superposition of departure processes from other queues. If component arrival processes are approximated by renewal processes, the ∑GI1/G/1 model applies. The approximation proposed is a hybrid that combines two basic methods described by Whitt. All these methods approximate the complex superposition process by a renewal process and yield a GI/G/1 queue that can be solved analytically or approximately. In the hybrid method, the moments of the intervals in the approximating renewal process are a convex combination of the moments determined by the basic methods. The weight in the convex combination is identified using the asymptotic properties of the basic methods together with simulation. When compared to simulation estimates, the error in hybrid approximations of the expected number in the queue is 3%; in contrast, the errors of the basic methods are 20–30%. The quality of the approximations suggests that the hybrid approach would be useful in approximating point processes in other contexts.
A Cutting Plane Algorithm for the Linear Ordering Problem
Authors: Grötschel Martin , Jünger Michael , Reinelt Gerhard
Published: November 2008

The linear ordering problem is an NP-hard combinatorial optimization problem with a large number of applications (including triangulation of input-output matrices, archaeological senation, minimizing total weighted completion time in one-machine scheduling, and aggregation of individual preferences). In a former paper, we have investigated the facet structure of the 0/1-polytope associated with the linear ordering problem. Here we report on a new algorithm that is based on these theoretical results. The main part of the algorithm is a cutting plane procedure using facet defining inequalities. This procedure is combined with various heuristics and branch and bound techniques. Our computational results compare favorably with the results of existing codes. In particular, we could triangulate all input-output matrices, of size up to 60 × 60, available to us within acceptable time bounds.
Confidence Intervals for Steady-State Simulations: I. A Survey of Fixed Sample Size Procedures
Authors: Law Averill M. , Kelton W. David
Published: November 2008

We consider the problem of constructing a confidence interval for the steady-state mean of a stochastic process by means of simulation, and study the five main methods which have been proposed (replication, batch means, autoregressive representation, spectrum analysis, and regeneration cycles) for the case when the length of the simulation is fixed in advance. Comparing the performances of these methods on stochastic models with known steady-state means, we find that the simulator should exercise caution in interpreting the results from a simulation of fixed length, and that the length of a simulation adequate for acceptable performance is highly model-dependent. We also investigate possible sources of error for the methods, and conclude that variance estimator bias is more important than point estimator bias in confidence interval coverage degradation.
The Economic Foundation of Generalized Equilibrium Modeling
Authors: Nesbitt Dale M.
Published: November 2008

In 1978 the author and his colleagues built the LEAP model and the Generalized Equilibrium Modeling System (GEMS). Often confused with the SRI-Gulf model, the GEMS/LEAP technique draws from the network modeling philosophy of the SRI-Gulf model. However, the GEMS/LEAP approach is significantly more advanced in its representation of producer and consumer behavior, its representation of market-dynamics, its solution algorithm, and its relationship to accepted economic and mathematical programming theory. This paper describes the methodological foundations of the many GEMS and LEAP models in existence. It also gives illustrative results.
An Efficient Algorithm for Computing Optimal (s, S) Policies
Authors: Federgruen Awi , Zipkin Paul
Published: November 2008

This paper presents an algorithm to compute an optimal (s, S) policy under standard assumptions (stationary data, well-behaved one-period costs, discrete demand, full backlogging, and the average-cost criterion). The method is iterative, starting with an arbitrary, given (s, S) policy and converging to an optimal policy in a finite number of iterations. Any of the available approximations can thus be used as an initial solution. Each iteration requires only modest computations. Also, a lower bound on the true optimal cost can be computed and used in a termination test. Empirical testing suggests very fast convergence.
Technical Note—A Note on the M/G/1 Queue with Server Vacations
Authors: Fuhrmann S. W.
Published: November 2008

Consider an M/G/1 queuing system in which the server begins a vacation of random length each time that the system becomes empty. This model has been analyzed in several papers, which show that the number of customers present in the system at a random point in time is distributed as the sum of two independent random variables: (i) The number of Poisson arrivals during a time interval that is distributed as the forward recurrence time of a vacation, and (ii) the number of customers present in the corresponding standard M/G/1 queuing system (without vacations) at a random point in time. This note gives an intuitive explanation for this result, while simultaneously providing a more simple and elegant method of solution.
Technical Note—Financial Market Approaches to Facility Location under Uncertainty
Authors: Hodder James E.
Published: November 2008

This paper examines financial market approaches for facility location models incorporating uncertainty and risk aversion. As an example, it compares a model based on the Capital Asset Pricing Model with one using a mean-variance objective function. There are dramatically different computational implications; the financial market approach yields simpler procedures and is able to handle more complex problems. However, as discussed in the concluding observations, there are situations where the financial market perspective is less appropriate; consequently, the mean-variance model still has a role in analyzing facility location decisions.
Disappointment in Decision Making Under Uncertainty
Authors: Bell David E.
Published: November 2008

Decision analysis requires that two equally desirable consequences should have the same utility and vice versa. Most analyses of financial decision making presume that two consequences with the same dollar outcome will be equally preferred However, winning the top prize of $10,000 in a lottery may leave one much happier than receiving $10,000 as the lowest prize in a lottery. This paper explores the implications of disappointment, a psychological reaction caused by comparing the actual outcome of a lottery to one's prior expectations, for decision making under uncertainty. Explicit recognition that decision makers may be paying a premium to avoid potential disappointment provides an interpretation for some known behavioral paradoxes, and suggests that decision makers may be sensitive to the manner in which a lottery is resolved. The concept of disappointment is integrated into utility theory in a prescriptive model.
The Comparison of Life Table and Markov Chain Techniques for Follow-up Studies
Authors: Schoenfelder John R. , Shachtman Richard H. , Johnston Gordon J.
Published: November 2008

We examine Markov chain versus life table techniques for comparing cohorts (homogeneous groups) with respect to time to occurrence of specified events. Key results are (i) a theorem showing that, when the underlying process is a stationary Markov chain, the Markov chain estimator of time to occurrence is equivalent to the life table estimator, and (ii) simulation statistics suggesting that the Markov chain estimator has a smaller standard error.
Numerical Comparisons of Inventory Policies for Periodic Review Systems
Authors: Porteus Evan L.
Published: November 2008

This paper studies the numerical computation of the two parameters (the reorder level s and the order up to level S) of inventory policies for discrete time shortage cost systems. Our goal is to obtain approximately optimal policies with little computational effort. The paper introduces three new methods that are designed to achieve this goal. Two of the methods are shortcuts based on the method of Freeland and Porteus and one is a heuristic that makes several modifications to a standard continuous review approximation. The paper provides a fairly detailed survey of other methods for easily computing approximately optimal inventory policies. It then numerically compares all these methods on a reasonably broad range of problems. One of the shortcuts and the new heuristic method performed very well: the percentage error of their average costs was approximately 1%. Some commonly cited competing methods had percentage errors of over 10% and a commonly cited continuous review approximation had a percentage error of over 80%. To study the effect of extreme parameter choices in the test bed, the paper introduces a procedure to determine a subset of the parameter values, called the 1% contiguous test bed, for which each method performed well. The results show that, depending on the range of values that apply in a given practical situation, either (i) any of a large number of methods will yield good performance or (ii) a carefully selected method can achieve superior performance.
Reliability Bounds for Multistate Systems with Multistate Components
Authors: Hudson Joseph C. , Kapur Kailash C.
Published: November 2008

The reliability literature has recently introduced several multistate models. This paper discusses reliability bounds in the most general of these models. It presents inclusion-exclusion bounds and compares them with disjoint subset bounds. The later bounds are based on a generalization of Abraham's recursive disjoint products.
Technical Note—Measuring Equity in Public Risk
Authors: Sarin Rakesh Kumar
Published: November 2008

An equitable distribution of risk is often an important criterion in the evaluation of technological and environmental risks. In this paper, we define the concept of equity precisely, and develop measures for ex-post and ex-ante equity. We then show how these measures, combined with information on the number of possible fatalities, can be used to rank alternatives that involve risks to human life.
Technical Note—A Markov Chain Partitioning Algorithm for Computing Steady State Probabilities
Authors: Sheskin Theodore J.
Published: November 2008

This paper presents a partitioning algorithm for recursively computing the steady state probabilities for a finite, irreducible Markov chain or a Markov process. The algorithm contains a matrix reduction routine, followed by a vector enlargement routine. The matrix reduction routine repeatedly partitions the transition matrix for the Markov chain, creating a sequence of smaller, reduced transition matrices. The vector enlargement routine computes the components of the steady state probability vector by starting with the smallest reduced matrix and working sequentially toward the original transition matrix. This procedure produces an exact solution for the steady state probabilities. No special structure is required for the Markov chain. In theory, the procedure imposes no limit on the size of the largest Markov chain to which the partitioning algorithm can be applied. In practice, roundoff errors may require modifications to the method.
Ranking with Partial Information: A Method and an Application
Authors: Kirkwood Craig W. , Sarin Rakesh K.
Published: November 2008

A method is presented for ranking multiattributed alternatives using a weighted-additive evaluation function with partial information about the weighting (scaling) constants, the method is applied to evaluate materials for use in nuclear waste containment. The paper derives conditions to determine whether a pair of alternatives can be ranked given the partial information about weighting constants, and presents an algorithm that partially rank-orders the complete set of alternatives based on the pairwise ranking information.
An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure
Authors: Beasley J. E.
Published: November 2008

We consider the two-dimensional cutting problem of cutting a number of rectangular pieces from a single large rectangle so as to maximize the value of the pieces cut. We develop a Lagrangean relaxation of a zero-one integer programming formulation of the problem and use it as a bound in a tree search procedure. Subgradient optimization is used to optimize the bound derived from the Lagrangean relaxation. Problem reduction tests derived from both the original problem and the Lagrangean relaxation are given. Incorporating the bound and the reduction tests into a tree search procedure enables moderately sized problems to be solved.
OR Forum—OR and the Airline Overbooking Problem
Authors: Rothstein Marvin
Published: November 2008

This paper surveys the application of operations research to airline overbooking, a distinctive problem of considerable significance to the public as well as the airline industry, and one which has received great attention in the press. The airlines have been overbooking their flights deliberately for decades, while moving gradually from a posture of categorical denial to a disclosure of their practices. Through the years, they have developed and employed a variety of statistical and tactical models to predict and control the consequences of this controversial procedure for increasing load factors. Yet, the situation still has not been resolved satisfactorily. The article analyzes the problems that motivate overbooking, discusses the relevant practices of the air carriers, and describes significant contributions and implementations of operations research.
A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
Authors: Potts Chris N. , Van Wassenhove Luk N.
Published: November 2008

This paper presents a new branch and bound algorithm for the single machine total weighted tardiness problem. It obtains lower bounds using a Lagrangian relaxation approach with subproblems that are total weighted completion time problems. The well-known subgradient optimization technique is replaced by a multiplier adjustment method that leads to an extremely fast bound calculation. The method incorporates various devices for checking dynamic programming dominance in the search tree. Extensive computational results for problems with up to 50 jobs show the superiority of the algorithm over existing methods.
Limits for the Precision and Value of Information from Dependent Sources
Authors: Clemen Robert T. , Winkler Robert L.
Published: November 2008

In many inferential and decision-making situations, information is obtained from a number of information sources, and the separate pieces of information are often not independent. This paper investigates the impact of dependence on the precision and value of information. The results indicate that positive dependence among information sources can have a serious detrimental effect on the precision and value of the information. Differences in precision between the dependent and independent cases can be remarkably large. With dependence, the incremental value of information can decrease very rapidly, and the limiting value of information as more sources are considered can be considerably less than the expected value of perfect information. The results of this paper have implications for the acquisition and use of information in decision-making problems.
Technical Note—On Normalizing Constants in Queueing Networks
Authors: Harrison P. G.
Published: November 2008

We present a method for deriving the normalizing constant for the state space probabilities in a closed Markovian queueing network with constant service rates. Our method produces a much simpler expression than any obtained previously. This expression takes the form of a sum of only M terms (if the visitation rate to service rate ratios are distinct), and is easily generalized to the degenerate case. The expression also yields a closed form solution for time delay distributions in cyclic networks of any length and with any number of customers.
Iterative Aggregation-Disaggregation Procedures for Discounted Semi-Markov Reward Processes
Authors: Schweitzer Paul J. , Puterman Martin L. , Kindle Kyle W.
Published: November 2008

The equation v = q + Mv, where M is a matrix with nonnegative elements and spectral radius less than one, arises in Markovian decision processes and input-output models. In this paper, we solve the equation using an iterative aggregation-disaggregation procedure that alternates between solving an aggregated problem and disaggregating the variables, one block at a time, in terms of the aggregate variables of the other blocks. The disaggregated variables are then used to guide the choice of weights in the subsequent aggregation. Computational experiments on randomly generated and inventory problems indicate that this algorithm is significantly faster than successive approximations when the spectral radius of M is near one, and is slower in unstructured problems with spectral radii in the neighborhood of 0.8. The algorithm appears promising for large structured problems, where it can often reduce computational time and main memory storage requirements and offer greater robustness to initial values.
A Concept of Monotonicity and Its Characterization for Closed Queueing Networks
Authors: Suri Rajan
Published: November 2008

We define a qualitative property, called monotonicity, for a closed queueing network. This property is defined both for a station in the network and for the network as a whole. Several results in this paper relate monotonic behavior to the known parameters of a network and allow us to state a priori, for many practical systems, whether the monotonicity property will apply for a network or a station. Monotonicity thus ensures that the system is well-behaved with respect to a number of parameters. We present diverse examples that demonstrate how knowledge of this property can be useful in network design and performance evaluation.
Efficiency of Multivariate Control Variates in Monte Carlo Simulation
Authors: Rubinstein Reuven Y. , Marcus Ruth
Published: November 2008

This paper considers some statistical aspects of applying control variates to achieve variance reduction in the estimation of a vector of response variables in Monte Carlo simulation. It gives a result that quantifies the loss in variance reduction caused by the estimation of the optimal control matrix. For the one-dimensional case, we derive analytically the optimal size of the vector of control variates under specific assumptions on the covariance matrix. For the multidimensional case, our numerical results show that good variance reduction is achieved when the number of control variates is relatively small (approximately of the same order as the number of unknown parameters). Finally, we give some recommendations for future research.
Technical Note—On the Optimal Choice of Sizes
Authors: Tryfos Peter
Published: November 2008

The paper studies the problem of determining the measurements of a given number of sizes of apparel so as to maximize expected sales or minimize an index of discomfort. It develops general necessary conditions for optimization in one control body dimension and calculates optimal sizes for the special case where the population distribution is normal.
Technical Note—Optimal Scheduling of Periodic Activities
Authors: Park Kyung S. , Yun Doek K.
Published: November 2008

This paper studies the scheduling of multiple activities that require periodic processing on a single facility for an infinite horizon. It first formulates this scheduling problem as an integer linear programming (ILP) model, and then uses the Chinese Remainder Theorem to efficiently partition the original into smaller independent models. For a small problem involving about 10 activities, the solution can be obtained very simply by hand. An example is given to illustrate the approach.
Integer Prim-Read Solutions to a Class of Target Defense Problems
Authors: Burr Stefan A. , Falk James E. , Karr Alan F.
Published: November 2008

We study the choice of a deployment and firing doctrine for defending separated point targets of (potentially) different values against an attack by an unknown number of sequentially arriving missiles. We minimize the total number of defenders, subject to an upper bound on the maximum expected value damage per attacking weapon. We show that the Greedy Algorithm produces an optimal integral solution to this problem.
Solving 0-1 Integer Programming Problems Arising from Large Scale Planning Models
Authors: Johnson Ellis L. , Kostreva Michael M. , Suhl Uwe H.
Published: November 2008

We present methods that are useful in solving some large scale hierarchical planning models involving 0-1 variables. These 0-1 programming problems initially could not be solved with any standard techniques. We employed several approaches to take advantage of the hierarchical structure of variables (ordered by importance) and other structures present in the models. Critical, but not sufficient for success, was a strong linear programming formulation. We describe methods for strengthening the linear programs, as well as other techniques necessary for a commercial branch-and-bound code to be successful in solving these problems.
Technical Note—On Generating Cutting Planes from Combinatorial Disjunctions
Authors: Sherali Hanif D. , Sen Suvrajeet
Published: November 2008

This paper develops a technique for generating deep valid inequalities based on combinatorial disjunctions that state that at least p out of some q(≥p) constraints must be satisfied. This technique provides a general framework, which subsumes existing methods, for generating cutting planes based on such disjunctions. It has potential applications, for example, in multiple choice and generalized lattice point programming problems, including mixed-integer zero-one programming problems and the extreme point mathematical programming problem.
Sensitivity Analysis for Branch and Bound Integer Programming
Authors: Schrage Linus , Wolsey Laurence
Published: November 2008

After an integer program is solved, we may be interested in the effect of small changes in the right-hand side or objective function coefficients. Without modifying the underlying branch and bound or cutting plane algorithm, we show what additional data to collect during the solution of the original integer program to give useful bounds on the solution of the modified problem.
Optimal Routing under Capacity and Distance Restrictions
Authors: Laporte Gilbert , Nobert Yves , Desrochers Martin
Published: November 2008

This paper describes an integer linear programming algorithm for vehicle routing problems involving capacity and distance constraints. The method uses constraint relaxation and a new class of subtour elimination constraints. Two versions of the algorithm are presented, depending upon the nature of the distance matrix. Exact solutions are obtained for problems involving up to sixty cities.
Facilities Layout Adjacency Determination: An Experimental Comparison of Three Graph Theoretic Heuristics
Authors: Foulds L. R. , Gibbons P. B. , Giffin J. W.
Published: November 2008

The facilities layout problem is concerned with laying out facilities on a planar site in order to design systems that are as efficient as possible. One approach to the problem involves the use of REL charts, which are tables that estimate the desirability of locating facilities next to each other, and the construction of a maximum weight planar graph that represents an efficient layout design. This method is not a complete one, however, since it specifies only which facilities are to be adjacent. Nevertheless, whenever the analyst has a great deal of freedom of design, it is a useful tool in the initial stages of laying out a new system. In this paper, we describe three graph theoretic heuristics that attempt to determine an optimal planar adjacency graph from a REL chart. Our computational experience suggests that these methods can provide effective solutions to problems of the size frequently encountered in practice by designers.
Stochastic Decompositions in the M/G/1 Queue with Generalized Vacations
Authors: Fuhrmann S. W. , Cooper Robert B.
Published: November 2008

This paper considers a class of M/G/1 queueing models with a server who is unavailable for occasional intervals of time. As has been noted by other researchers, for several specific models of this type, the stationary number of customers present in the system at a random point in time is distributed as the sum of two or more independent random variables, one of which is the stationary number of customers present in the standard M/G/1 queue (i.e., the server is always available) at a random point in time. In this paper we demonstrate that this type of decomposition holds, in fact, for a very general class of M/G/1 queueing models. The arguments employed are both direct and intuitive. In the course of this work, moreover, we obtain two new results that can lead to remarkable simplifications when solving complex M/G/1 queueing models.
Optimal Policy for a Two-Stage Assembly System under Random Demand
Authors: Schmidt Charles P. , Nahmias Steven
Published: November 2008

This paper considers an inventory system in which an end product is assembled from two components, each of which is ordered from an external supplier. Only the end product has final demand, which is assumed to be random. Using the functional equation approach of dynamic programming, we characterize the forms of both the optimal order policy for the components and the optimal assembly policy of the end product for a multiperiod problem of arbitrary, but finite length. We believe that this work represents the only exact analysis of an MRP-type assembly system when demand is stochastic.
Computing Market Equilibria with Price Regulations Using Mathematical Programming
Authors: Greenberg Harvey J. , Murphy Frederic H.
Published: November 2008

One approach to modeling and solving for economic equilibria relies on mathematical programming. These models solve for competitive equilibria. However, policy analysis often requires measuring the impacts of government price regulations that differ from the competitive equilibrium. In this paper we provide a unified framework for computing market equilibrium in mathematical programming models in the presence of government price regulations. The iterative procedure that we use is essentially a Gauss–Seidel algorithmic strategy. The paper concludes by showing how to represent tax/rebate programs, average-cost pricing, and price ceilings.
Evaluating Decision Strategies for Equity of Public Risks
Authors: Keeney Ralph L. , Winkler Robert L.
Published: November 2008

Many important decisions include the loss of life among their possible consequences. Alternative actions have different implications for the number of possible fatalities, the equity of those eventual fatalities, and the equity of the process resulting in those fatalities. This paper defines a concept of ex ante risk equity to address the equity of the process and distinguishes this concept from the ex post risk equity of the fatalities. The paper indicates that an analysis of decision strategies addresses ex ante equity. In this context, both types of equity as well as loss of life are included in a von Neumann-Morgenstern utility model developed to evaluate public risks. This approach provides a method to investigate the implications of different value judgments in examining alternatives and illustrates an appropriate use of von Neumann-Morgenstern utility for problems involving social consequences such as public risks.
Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs
Authors: Birge John R.
Published: November 2008

Multistage stochastic linear programs model problems in financial planning, dynamic traffic assignment, economic policy analysis, and many other applications. Equivalent representations of such problems as deterministic linear programs are, however, excessively large. This paper develops decomposition and partitioning methods for solving these problems and reports on computational results on a set of practical test problems.
Computational Experience in Solving Equilibrium Models by a Sequence of Linear Complementarity Problems
Authors: Mathiesen Lars
Published: November 2008

This paper presents a modeling format and a solution algorithm for partial and general economic equilibrium problems. It reports on computational experience from a series of small to medium sized problems taken from the literature on computation of economic equilibria. The common characteristic of these models is the presence of weak inequalities and complementary slackness, e.g., a linear technology with alternative activities or various institutional constraints on prices. The algorithm computes the equilibrium by solving a sequence of linear complementarity problems. The iterative (outer) part of this algorithm is a Newton process. For the inner part, we use Lemke's almost complementary pivoting algorithm. Theoretical results for the performance of this algorithm are at present available only for the partial equilibrium cases. Our computational experience with both types of models, however, is encouraging. The algorithm solved all nine test problems when initiated at reasonable starting points. Five of these nine problems are solved for several different starting points, indicating a large region over which the algorithm converges. Our results demonstrate that the algorithm is economical in terms of the number of pivots, function evaluations and CPU time.
Bounds for Assembly Line Balancing Heuristics
Authors: Queyranne Maurice
Published: November 2008

We analyze the asymptotic worst-case performance ratio of polynomial time heuristics for the assembly line balancing problem. Assuming that P ≠ NP, we show that no polynomial heuristic has worst-case ratio less than 1.5. (This ratio is known to be not worse than 2 for any “reasonable” heuristic.) Tighter results are established for problems with only “short” tasks, i.e., when all processing times do not exceed a given fraction of the cycle time. These results apply even to planar, series-parallel precedence constraints, and contrast with known results for situations with an empty precedence relation, i.e., the bin packing problem. In particular, if P ≠ NP, there are no fully polynomial approximation schemes for assembly line balancing, even with “short” tasks and planar, series-parallel precedence constraints.