bluuebunny/crossref_metadata_2025 huggingface dataset:
Design and Implementation of an Interactive Optimization System for Telephone Network Planning
Authors: Jack Carolyn , Kai Sheng-Roan , Shulman Alexander
Published: November 2008

We describe an interactive optimization system for multiperiod exhaust relief planning in the local loop of a public telephone network. In exhaust relief planning in the local loop one seeks the minimum cost capacity expansion plan that meets projected demand over a given planning horizon. The problem can be modeled as an integer programming problem. However, due to cost structures and varying transmission technologies, the single-period exhaust relief planning problem is NP-complete. The size of the problem precludes the use of general purpose integer programming. Based on the mathematical structure and complexity of the problem, we decompose the optimization problem into a single-period dynamic programming problem, and a multiperiod greedy heuristic. A software system surrounds the optimization algorithm and provides interactive planning capabilities, before and after creation of the optimized plan. Important aspects of the system are the model assumptions made to keep the problem tractable, and their effect on the standardization of input data and methodology. The system is in use by several hundred outside plant planners in a major U.S. telephone company. An overview of major elements of the package is given as well as a summary of important implementation issues that arose during the first three years of the on-going project.
On the Convergence of Miehle's Algorithm for the Euclidean Multifacility Location Problem
Authors: Rosen J. B. , Xue G. L.
Published: November 2008

For the Euclidean single facility location problem, E. Weiszfeld proposed a simple iterative algorithm in 1937. Later, it was proved by numerous authors that it is a convergent descent algorithm. W. Miehle extended Weiszfeld's algorithm to solve the Euclidean multifacility location problem. Then, L. M. Ostresh proved that Miehle's algorithm is a descent algorithm. Recently, F. Rado modified Miehle's algorithm and provided several sets of sufficient conditions for the modified algorithm to converge. He also indicated that the convergence of Miehle's algorithm was an open problem. In this paper, the relationship between Miehle's multifacility location algorithm and Weiszfeld's single facility location algorithm is analyzed. Counterexamples show that Miehle's algorithm may converge to nonoptimal points for well structured problems.
The Structure of Structured Bond Portfolio Models
Authors: Zipkin Paul
Published: November 2008

Over the past decade, optimization models have been widely used to help select bond portfolios. Several different formulations are popular. The purposes of this paper are to clarify the basic structures of the models, to explain the relationships among them, and to assess their strengths and weaknesses.
A Multiplier Adjustment Approach for the Set Partitioning Problem
Authors: Chan Thomas Justin , Yano Candace Arai
Published: November 2008

We introduce an effective branch-and-bound algorithm for solving the set partitioning problem. The new algorithm employs a new multiplier-adjustment-based bounding procedure, and a complementary branching strategy which results in relatively small search trees. Computational results based on 20 moderately sized crew scheduling problems indicate that our new algorithm is on average 16.6 times faster than the popular code, SETPAR. The improvements are mainly due to the bounding procedure, which is fast, easy to use, and provides tight lower bounds. On average, the bounds are 97.6% of the optimal objective value of the linear programming relaxation after only five iterations, and 98.5% after ten iterations. Moreover, the lower bounds are observed to be monotonically nondecreasing. We also apply the technique of variable elimination, which is very effective in reducing the size of the problems. On average, 89% of the variables are eliminated from the problem at the root node.
The Scaling Network Simplex Algorithm
Authors: Ahuja Ravindra K. , Orlin James B.
Published: November 2008

In this paper, we present a new primal simplex pivot rule and analyze the worst case complexity of the resulting simplex algorithm for the minimum cost flow, the assignment, and the shortest path problems. We consider networks with n nodes, m arcs, integral arc capacities bounded by an integer number U, and integral arc costs whose magnitudes are bounded by an integer number C. Our pivot rule may be regarded as a scaling version of Dantzig's pivot rule. Our pivot rule defines a threshold value Δ, which is initially at most 2C, and the rule permits any arc with a violation of at least Δ/2 to be the editing variable. We select the leaving arc so that strong feasibility of the basis is maintained. When there is no arc satisfying this rule, then we replace Δ by Δ/2 and repeat the process. The algorithm terminates when Δ < 1. We show that the simplex algorithm using this rule performs O(nmU log C) pivots and can be implemented to run in O(m2U log C) time. Specializing these results for the assignment and shortest path problems we show that the simplex algorithm solves these problems in O(n2 log C) pivots and O(nm log C) time.
Approximation Algorithms for Fixed Job Schedule Problems
Authors: Fischetti Matteo , Martello Silvano , Toth Paolo
Published: November 2008

We consider two generalizations of the fixed job schedule problem, obtained by imposing a bound on the spread-time or on the working time of each processor. These NP-hard problems, studied by the authors in previous works, can arise in bus driver scheduling. We introduce several polynomial-time approximation algorithms, give efficient implementations for them, and analyze their complexity and worst case performance. The average behavior is also investigated through extensive computational experiments.
Balanced Loading
Authors: Amiouny Samir V. , Bartholdi John J. , Vande Vate John H. , Zhang Jixian
Published: November 2008

We develop a heuristic for a problem motivated by the loading of aircraft or trucks: pack blocks into a bin so that their center-of-gravity is as close as possible to a target point. Our heuristic either produces good solutions or else signals that none is possible. It also works when loading nonhomogeneous blocks into a bin of nonzero and possibly nonhomogeneous mass.
Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints
Authors: Grötschel Martin , Monma Clyde L. , Stoer Mechthild
Published: November 2008

We describe a cutting plane approach to the problem of designing survivable fiber optic communication networks. This problem can be formulated as a minimum cost network design problem with certain low-connectivity constraints. Computational results on real-world telephone network design problems demonstrate the effectiveness of our cutting plane method. The facet-inducing inequalities for the convex hull of the solutions to this problem on which our algorithm is based are studied in detail in a companion paper.
Socially and Individually Optimal Routing of Stochastic Jobs in Parallel Processor Systems
Authors: Xu Susan H.
Published: November 2008

This paper considers a stochastic system where a fixed number of nonpreemptive jobs (no new jobs arrive) are to be processed on multiple nonidentical processors. Each processor has an increasing hazard rate processing time distribution and the processors are ordered in ascending order of their expected processing times. It is shown that the policy which minimizes the total expected delay of all the jobs (flowtime) has a threshold structure. This policy would utilize the fastest available processor only if its mean processing time is less than a critical number. Furthermore, a previously rejected processor must never be utilized at later times. This policy is also individually optimal in the sense that it minimizes the delay of each job subject to the constraint that processor preference is given to jobs at the head of the buffer. This result proves the conjecture of P. R. Kumar and J. Walrand regarding socially and individually optimal policies in parallel routing systems.
Reservation Prices in Optimal Stopping
Authors: Seierstad Atle
Published: November 2008

In an optimal stopping problem where bids on an asset are received, conditions are given that ensure the so-called reservation price property, namely, if a certain price is accepted, then any higher price would also have been accepted at that point in time. The approach followed in this paper is similar to that pursued by D. B. Rosenfield and R. D. Shapiro in 1981.
A Dual-Based Procedure for Stochastic Facility Location
Authors: Louveaux François V. , Peeters D.
Published: November 2008

In this paper, we study how the uncapacitated facility location problem is transformed into a two-stage stochastic program with recourse when uncertainty on demand, selling prices, production and transportation costs are introduced. We then present a dual-based procedure and indicate how the dual-descent and primal-dual adjustment procedures proposed by D. Erlenkotter (1978) in the static case can be made monotonically improving in the stochastic case. Results of computer experiments are reported.
Constant Access Systems: A General Framework for Greedy Optimization on Stochastic Networks
Authors: Bailey Michael Page
Published: November 2008

We consider network optimization problems in which the weights of the edges are random variables. We develop conditions on the combinatorial structure of the problem which guarantee that the objective function value is a first passage time in an appropriately constructed continuous time Markov chain. The arc weights must be distributed exponentially, the method of solution of the deterministic problem must be greedy in a general sense, and the accumulation of objective function value during the greedy procedure must occur at a constant rate. We call these structures constant access systems after the third property. Examples of constant access systems include the shortest path system, the longest path system, the time until disconnection in a network of failing components, and some bottleneck optimization problems. For each system, we give the distribution of the objective function, the distribution of the solution of the problem, and the probability that a given arc is a member of the optimal solution. We also provide easily implementable formulas for the moments of each optimal objective function value, as well as criticality indices for each arc.
Capacity Expansion Under Stochastic Demands
Authors: Bean James C. , Higle Julia L. , Smith Robert L.
Published: November 2008

We consider the problem of optimally meeting a stochastically growing demand for capacity over an infinite horizon. Under the assumption that demand for product follows either a nonlinear Brownian motion or a non-Markovian birth and death process, we show that this stochastic problem can be transformed into an equivalent deterministic problem. Consistent with earlier work by A. Manne, the equivalent problem is formed by replacing the stochastic demand by its deterministic trend and discounting all costs by a new interest rate that is smaller than the original, in approximate proportion to the uncertainty in the demand.
Calculation of Steady-State Probabilities for Repair Facilities with Multiple Sources and Dynamic Return Priorities
Authors: Daryanani Sikander , Miller Douglas R.
Published: November 2008

We develop iterative computational formulas for the steady-state probabilities of an exponential single-channel repair facility with multiple Poisson sources and a dynamic return policy. Such facilities occur as part of multi-echelon repairable item provisioning systems in which backorders are filled according to need instead of FIFO or SIRO policies. Some computational examples are given which show the difference in system performance. Our analysis is an example of the state-reduction computational method for Markov chains. Our implementation makes use of taboo sets and taboo probabilities which have physically meaningful interpretations.
A Storage Model with a Two-State Random Environment
Authors: Kella Offer , Whitt Ward
Published: November 2008

Motivated by queues with service interruptions, we consider an infinite-capacity storage model with a two-state random environment. The environment alternates between “up” and “down” states. In the down state, the content increases according to one stochastic process; in the up state, the content decreases according to another stochastic process. We describe the steady-state behavior of this system under assumptions on the component stochastic elements. For the special case of deterministic linear flow during the up and down states, we show that the steady-state content is directly related to the steady-state workload or virtual waiting time in an associated G/G/1 queue, thus supplementing the results of D. P. Gaver, Jr., and R. G. Miller, Jr. (1962), R. G. Miller, Jr. (1963) and H. Chen and D. D. Yao (1992).
A Note on a Continuous-Time Search Model with Several Offer Streams
Authors: Stadje Wolfgang
Published: November 2008

We consider a continuous-time search model with n random offer streams forming independent renewal processes. The distribution of the offer size may depend on the arrival time and the type of the offer, and there is a constant search cost per unit time. The searcher wants to select an offer such that the expected discounted reward is maximized. We present a method for computing such a strategy and apply it to some numerical examples. In the case of Poisson offer streams a more direct approach is also given.
Military Operations Research: Presentations at ORSA/TIMS Meetings
Authors: Hartley Dean S.
Published: November 2008

This paper highlights the methodologies, organizations, and applications of military operations research in practice as evidenced by presentations at ORSA/TIMS meetings over the last seven and a half years. Cross-tabulations address the questions of who does what kind of military OR, what methodologies are used in what applications, and what trends are evident.
Simterpolation: A Simulation based Interpolation Approximation for Queueing Systems
Authors: Reiman Martin I. , Simon Burton , Willie J. Stanford
Published: November 2008

In this paper, we approximate moments of the sojourn time distribution in open networks of priority queues via an interpolation approximation. The interpolation is constructed from five random variables (and their covariance matrix) that are simultaneously estimated from a single regenerative simulation of the system at any arrival rate. The random variables are consistent estimates of the zeroth and first-order light traffic limits, the heavy traffic limit, and the value of the function and its derivative at the arrival rate of the simulation. The data yield a least squares estimate of a normalized version of the original function, which, in turn, yields an estimate of the function of interest. This procedure is useful for complex systems because the light and heavy traffic limits needed for an interpolation are not easy to calculate analytically in those cases.
Efficient Algorithms for Scheduling Semiconductor Burn-In Operations
Authors: Lee Chung-Yee , Uzsoy Reha , Martin-Vega Louis A.
Published: November 2008

In this paper, we study the problem of scheduling semiconductor burn-in operations, where burn-in ovens are modeled as batch processing machines. A batch processing machine is one that can process up to B jobs simultaneously. The processing time of a batch is equal to the largest processing time among all jobs in the batch. We present efficient dynamic programming-based algorithms for minimizing a number of different performance measures on a single batch processing machine. We also present heuristics for a number of problems concerning parallel identical batch processing machines and we provide worst case error bounds.
On Constrained Bottleneck Extrema
Authors: Lee Jon
Published: November 2008

This note treats optimization problems that involve two criteria on set systems. One is a bottleneck criterion, and the other is general. In particular, recent algorithms for such problems on the edge-sets of networks are related to the fundamental work of J. Edmonds and D. R. Fulkerson involving more general set systems.
America's Vietnam Casualties: Victims of a Class War?
Authors: Barnett Arnold , Stanley Timothy , Shore Michael
Published: November 2008

Analysis of data about the 58,000 Americans killed in Vietnam implies that affluent U.S. communities had only marginally lower casualty rates than the nation as a whole. Poor communities had only marginally higher rates. Data about the residential addresses of war casualties suggest that, within both large heterogeneous cities and wealthy suburbs, there was little relationship between neighborhood incomes and per capita Vietnam death rates. Such outcomes call into question a widespread belief that continues to influence U.S. policy discussions, namely, that American war deaths in Vietnam were overwhelmingly concentrated among the poor and working class.
Automatic Learning for Dynamic Markov Fields with Application to Epidemiology
Authors: Yakowitz S. , Hayes R. , Gani J.
Published: November 2008

Following an outline of dynamic Markov fields, we briefly describe some spatial models for contagious diseases and pose a prototype epidemic control problem. The notion of automatic learning is then introduced, and its relevance to epidemic control is described. In essence, once a contagion model is adopted and a domain of controls has been selected, learning can be used to obtain asymptotically optimal performance. (The learning algorithm is a synthesis of simulation and optimization, and is a suitable alternative to response surface methodology, in many applications.) The end product is the same optimal control as would be obtained by a conventional analysis. The point is that our current understanding of dynamic Markov fields does not permit conventional analysis; automatic learning has no computationally competitive alternative. The theory is illustrated by application to a spatial epidemic control problem.
A Tchebysheff-Type Bound on the Expectation of Sublinear Polyhedral Functions
Authors: Dulá José H. , Murthy Rajluxmi V.
Published: November 2008

This work presents an upper bound on the expectation of sublinear polyhedral functions of multivariate random variables based on an inner linearization and domination by a quadratic function. The problem is formulated as a semi-infinite program which requires information on the first and second moments of the distribution, but without the need of an independence assumption. Existence of a solution and stability of this semi-infinite program are discussed. We show that an equivalent optimization problem with a nonlinear objective function and a set of linear constraints may be used to generate solutions.
Tandem Queues with Planned Inventories
Authors: Lee Yong-Joo , Zipkin Paul
Published: November 2008

This paper explores a natural generalization of the classic tandem-queue model, designed specifically to represent make- to-stock production processes. In such systems, intermediate and finished goods can be produced and stored in advance of demand. We consider the simplest version of the model, where demand is a Poisson process, and the unit production times are exponentially distributed. We propose and test a tractable approximation scheme. The approximation appears to be quite accurate.
Preference Assessment by Imprecise Ratio Statements
Authors: Salo Ahti A. , Hämäläinen Raimo P.
Published: November 2008

The PAIRS method developed in this paper introduces imprecise preference statements into value trees. The assessment of attribute weights in PAIRS extends the well known SMART technique so that in addition to exact statements the decision maker can enter interval judgments which indicate ranges for the relative importance of the attributes. The interval judgments and the possibly range-valued information about the outcomes of the alternatives are processed with linear programming into value intervals and dominance relations. As the decision maker refines the description of his preferences, either by entering new statements or by tightening his earlier judgments, these results become more detailed and convey more information about which alternatives are preferred. Throughout the interactive refinement process PAIRS supports the decision maker by deriving and displaying the consequences of his earlier judgments.
File Allocation Problem: Comparison of Models with Worst Case and Average Communication Delays
Authors: Ghosh Deb , Murthy Ishwar , Moffett Allen
Published: November 2008

A major design issue facing the designer of a distributed computing system involves the determination of the number of file copies and their locations in the distributed environment. This problem is commonly referred to as the file allocation problem (FAP). This paper considers two FAP models that seek to minimize operating costs (i.e., the total cost of file storage and query/update communication). The first model ensures the attainment of acceptable levels of communication delay during peak network traffic periods (worst-case scenario). The second model considers average communication delay. Unlike previous FAP research, the proposed models treat communication delay on a query-by-query basis, and not as a single, system-wide average delay constraint. For both models, a Lagrangian relaxation-based solution procedure is proposed for the resulting 0/1 integer programming problem. In the case of average delays, we utilize a hybrid model combining analytic and simulation procedures. The results of computational experiments with the proposed solution techniques are reported.
New Insertion and Postoptimization Procedures for the Traveling Salesman Problem
Authors: Gendreau Michel , Hertz Alain , Laporte Gilbert
Published: November 2008

This paper describes a new insertion procedure and a new postoptimization routine for the traveling salesman problem. The combination of the two methods results in an efficient algorithm (GENIUS) which outperforms known alternative heuristics in terms of solution quality and computing time.
Perturbation Analysis for the Design of Flexible Manufacturing System Flow Controllers
Authors: Caramanis Michael , Liberopoulos George
Published: November 2008

Dynamic allocation of stochastic capacity among competing activities in a just in time manufacturing environment is addressed by optimal flow control. Optimal policies are characterized by generally intractable Bellman equations. A near-optimal controller design technique is proposed. It provides an approximate numerical solution to the Bellman equation, a tight lower bound for the optimality gap of tractable, near-optimal controller designs, and a building block for improved, near-optimal controller designs that rely on the decomposition of a multiple part-type problem to smaller (two or three part-type) problems. Computational experience is reported for two and three part-type problems.
Numerical Methods in Markov Chain Modeling
Authors: Philippe Bernard , Saad Youcef , Stewart William J.
Published: November 2008

This paper describes and compares several methods for computing stationary probability distributions of Markov chains. The main linear algebra problem consists of computing an eigenvector of a sparse, nonsymmetric matrix associated with a known eigenvalue. It can also be cast as a problem of solving a homogeneous, singular linear system. We present several methods based on combinations of Krylov subspace techniques, single vector power iteration/relaxation procedures and acceleration techniques. We compare the performance of these methods on some realistic problems.
A Multicriteria Optimization Approach to Aircraft Loading
Authors: Ng Kevin Y. K.
Published: November 2008

This note reports a multicriteria optimization approach to aircraft loading. Only cargo manifests or “standard loads” provided (or approved) by experienced loadmasters are employed in the optimization procedure. The familiarity of the load manifests that comprise the solution makes the model truly operable. In testing with actual data, the model reduced the number of aircraft loads required to complete an airlift by 9%, as compared to the traditional, manual method presently used. More importantly, the model provides timely planning and improves airlift support of combat operations.
Demand Driven Dispatch: A Method for Dynamic Aircraft Capacity Assignment, Models and Algorithms
Authors: Berge Matthew E. , Hopperstad Craig A.
Published: November 2008

A major problem for the airline industry is the assignment of airplane capacity to flight schedules to meet fluctuating market needs. Demand Driven Dispatch (D3) is an operating concept that addresses this problem. Utilizing a demand forecast which improves as flight departure approaches, aircraft are dynamically assigned to flights to better match the predicted final demands. The result, demonstrated in studies of actual airline systems, is an increase in passenger loads and revenues with simultaneously reduced costs for a net of 1–5% improvement in operating profits. Concept implementation is simplified by the prevalence of yield management systems which provide the forecasting capability, and the emergence of airplane families which provide the necessary operational flexibility. Implementation also requires frequent solution of extremely large aircraft assignment problems. These problems, which can be formulated in terms of a multicommodity network flow, can be solved with heuristic algorithms shown to exhibit an accuracy and efficiency essential to successful concept implementation.
A Variational Inequality Formulation of the Dynamic Network User Equilibrium Problem
Authors: Friesz Terry L. , Bernstein David , Smith Tony E. , Tobin Roger L. , Wie B. W.
Published: November 2008

In the present paper we are concerned with developing more realistic dynamic models of route choice and departure time decisions of transportation network users than have been proposed in the literature heretofore. We briefly review one class of models that is a dynamic generalization of the static Wardropian user equilibrium, the so-called Boston traffic equilibrium. In contrast, we then propose a new class of models that is also a dynamic generalization of the static Wardropian user equilibrium. In particular, we show for the first time that there is a variational inequality formulation of dynamic user equilibrium with simultaneous route choice and departure time decisions which, when appropriate regularity conditions hold, preserves the first in, first out queue discipline.
A Reliability Model Applied to Emergency Service Vehicle Location
Authors: Ball Michael O. , Lin Feng L.
Published: November 2008

This article proposes a reliability model for emergency service vehicle location. Emergency services planners must solve the strategic problem of where to locate emergency services stations and the tactical problem of the number of vehicles to place in each station. We view the problem from a system reliability perspective, where system failure is interpreted as the inability of a vehicle to respond to a demand call within an acceptable amount of time. Our model handles the stochastic problem aspects in a more explicit way than previous models in the literature. Based on a reliability bound on the probability of system failure, we derive a 0-1 integer programming (IP) optimization model. We propose the augmentation of the IP using certain valid inequalities as a preprocessing technique, and solve the IP using a branch-and-bound procedure. Our computational results show that the preprocessing technique is highly effective. Also, sensitivity studies show that the planner can produce a variety of different desired solution characteristics by appropriate manipulation of parameters. We feel that the reliability perspective should have applications beyond this context and hope that it will lead to ideas for similar optimization models in the context of designing reliable systems.
A New Class of Instantaneous Dynamic User-Optimal Traffic Assignment Models
Authors: Ran Bin , Boyce David E. , LeBlanc Larry J.
Published: November 2008

The instantaneous dynamic user-optimal (DUO) traffic assignment problem is to determine vehicle flows on each link at each instant of time resulting from drivers using instantaneous minimal-time routes. Instantaneous route time is the travel time incurred if traffic conditions remain unchanged while driving along the route. In this paper, we introduce a different definition of an instantaneous DUO state. Using the optimal control theory approach, we formulate two new DUO traffic assignment models for a congested transportation network. These models include new formulations of the objective function and flow propagation constraints, and are dynamic generalizations of the static user-optimal model. The equivalence of the solutions of the two optimal control programs with DUO traffic flows is demonstrated by proving the equivalence of the first-order necessary conditions of the two programs with the instantaneous DUO conditions. Since these optimal control problems are convex programs with linear constraints, they have unique solutions. A numerical example is presented indicating that this class of models yields realistic results.
Optimal Flows in Stochastic Dynamic Networks with Congestion
Authors: Birge John R. , Ho James K.
Published: November 2008

This paper presents a method for finding optimal flows in a dynamic network with random inputs into the system and congestion limits on flow. This model has been used in deterministic settings to represent dynamic traffic assignment and job shop routing. This paper builds on the deterministic results to show that a globally optimal solution in the stochastic problem may be obtained by a sequence of linear optimizations. A decomposition algorithm for this procedure is presented that efficiently solves problems with large-scale deterministic equivalents of up to 66,000 variables.
Two-Echelon Distribution Systems with Vehicle Routing Costs and Central Inventories
Authors: Anily S. , Federgruen A.
Published: November 2008

We consider distribution systems with a single depot and many retailers each of which faces external demands for a single item that occurs at a specific deterministic demand rate. All stock enters the systems through the depot where it can be stored and then picked up and distributed to the retailers by a fleet of vehicles, combining deliveries into efficient routes. We extend earlier methods for obtaining low complexity lower bounds and heuristics for systems without central stock. We show under mild probabilistic assumptions that the generated solutions and bounds come asymptotically within a few percentage points of optimality (within the considered class of strategies). A numerical study exhibits the performance of these heuristics and bounds for problems of moderate size.
A Markov Decision Model and Decomposition Heuristic for Dynamic Vehicle Dispatching
Authors: Minkoff Alan S.
Published: November 2008

We describe a dynamic and stochastic vehicle dispatching problem called the delivery dispatching problem. This problem is modeled as a Markov decision process. Because exact solution of this model is impractical, we adopt a heuristic approach for handling the problem. The heuristic is based in part on a decomposition of the problem by customer, where customer subproblems generate penalty functions that are applied in a master dispatching problem. We describe how to compute bounds on the algorithm's performance, and apply it to several examples with good results.
Inventory Control in a Fluctuating Demand Environment
Authors: Song Jing-Sheng , Zipkin Paul
Published: November 2008

We present an inventory model, where the demand rate varies with an underlying state-of-the-world variable. This variable can represent economic fluctuations, or stages in the product life-cycle, for example. We derive some basic characteristics of optimal policies and develop algorithms for computing them. In addition, we show that certain monotonicity patterns in the problem data are reflected in the optimal policies.
Estimating Customer and Time Averages
Authors: Glynn Peter W. , Melamed Benjamin , Whitt Ward
Published: November 2008

In this paper we establish a joint central limit theorem for customer and time averages by applying a martingale central limit theorem in a Markov framework. The limiting values of the two averages appear in the translation terms. This central limit theorem helps to construct confidence intervals for estimators and perform statistical tests. It thus helps determine which finite average is a more asymptotically efficient estimator of its limit. As a basis for testing for PASTA (Poisson arrivals see time averages), we determine the variance constant associated with the central limit theorem for the difference between the two averages when PASTA holds.
Exploratory Modeling for Policy Analysis
Authors: Bankes Steve
Published: November 2008

Exploratory modeling is using computational experiments to assist in reasoning about systems where there is significant uncertainty. While frequently confused with the use of models to consolidate knowledge into a package that is used to predict system behavior, exploratory modeling is a very different kind of use, requiring a different methodology for model development. This paper distinguishes these two broad classes of model use describes some of the approaches used in exploratory modeling, and suggests some technological innovations needed to facilitate it.
Measuring Performance in a Multiproduct Firm: An Application to the U.S. Postal Service
Authors: Bradley Michael D. , Baron Donald M.
Published: November 2008

Measuring performance in a multiproduct firm is difficult because of the complex nature of the firm's output. We present an approach to measuring performance, called operating efficiency which is the ratio of aggregate output to aggregate resource use. We describe how to calculate operating efficiency for a multiproduct organization and demonstrate how it can be used to understand why performance varies across plants and/or through time. Our application of operating efficiency to the U.S. Postal Service is discussed along with the reactions of potential users.
Shadow Prices for Measures of Effectiveness, II: General Model
Authors: Robinson Stephen M.
Published: November 2008

This is the second of a pair of papers describing a two-sided game model of combat. In this paper, each side attempts to develop a force structure attaining the maximum of a prescribed merit function, subject to certain constraints expressed by a set of prescribed measures of effectiveness. These measures can be different for the two sides: furthermore, those of each side can depend on the other side's actions. A solution of the model is a generalized Nash equilibrium of this game, and such a solution also yields shadow prices that reveal the cost in merit paid by each side for requiring the specified level of performance on each measure of effectiveness. The first paper examines a special case in which the model has a linear structure, and shows that in a restricted case the shadow prices produced by that model are the classical eigenvalue weights familiar from Lanchester theory.
A Direct Approach to the GI/G/1 Queueing System with Finite Capacity
Authors: Stadje Wolfgang
Published: November 2008

For the GI/G/1 queue with finite capacity we derive the time-dependent distributions of the number of customers in the system and of the duration of a busy period and a busy cycle under an arbitrary initial condition at time zero.
BPSS: A Scheduling Support System for the Packaging Industry
Authors: Adler Leonard , Fraiman Nelson , Kobacker Edward , Pinedo Michael , Plotnicoff Juan Carlos , Wu Tso Pang
Published: November 2008

This paper describes a scheduling support system for plants that produce multiply paper bags. The machine environment in these plants may be described as a flexible flow shop. That is, there are a number of stages in series with a number of machines in parallel at each stage. The jobs have specified shipping dates as well as priorities; their processing times and setup times are known in advance. We developed a five-step algorithm that schedules all the jobs at the various stages. This algorithm has been incorporated in a system, the Bagpak Production Scheduling System (BPSS), which also contains a data base management module and a user interface module. The system has been implemented in two plants, and is used on a regular basis. It has increased considerably the accuracy of the available information regarding the production process. The scheduler, in conjunction with the system, is able to produce better schedules; he now always knows where given performance measures stand. In addition, the available information enables the scheduler to provide better service to customers.
Allocating Games for the NHL Using Integer Programming
Authors: Fleurent Charles , Ferland Jacques A.
Published: November 2008

In recent years, the National Hockey League (NHL) expanded from 21 to 24 teams. In order to accommodate its scheduling process, the league had to determine new game allocations, that is, the number of times the teams play against each other. This paper introduces a procedure based on integer linear programming that generates several game allocation scenarios that have been presented to the league managers. The model takes into account the constraints specified by the NHL, and the objective function allows the league managers to specify their preference on the distribution of the games.
The Physics of the Mt/G/∞ Queue
Authors: Eick Stephen G. , Massey William A. , Whitt Ward
Published: November 2008

We establish some general structural results and derive some simple formulas describing the time-dependent performance of the Mt/G/∞ queue (with a nonhomogeneous Poisson arrival process). We know that, for appropriate initial conditions, the number of busy servers at time t has a Poisson distribution for each t. Our results show how the time-dependent mean function m depends on the time-dependent arrival-rate function λ and the service-time distribution. For example, when λ is quadratic, the mean m(t) coincides with the pointwise stationary approximation λ(t)E[S], where S is a service time, except for a time lag and a space shift. It is significant that the well known insensitivity property of the stationary M/G/∞ model does not hold for the nonstationary Mt/G/∞ model; the time-dependent mean function m depends on the service-time distribution beyond its mean. The service-time stationary-excess distribution plays an important role. When λ is decreasing before time t, m(t) is increasing in the service-time variability, but when λ is increasing before time t, m(t) is decreasing in service-time variability. We suggest using these infinite-server results to approximately describe the time-dependent behavior of multiserver systems in which some arrivals are lost or delayed.
Best-First Search Methods for Constrained Two-Dimensional Cutting Stock Problems
Authors: Viswanathan K. V. , Bagchi A.
Published: November 2008

Best-first search is a widely used problem solving technique in the field of artificial intelligence. The method has useful applications in operations research as well. Here we describe an application to constrained two-dimensional cutting stock problems of the following type: A stock rectangle S of dimensions (L, W) is supplied. There are n types of demanded rectangles r1, r2, …, rn, with the ith type having length li, width wi, value vi, and demand constraint bi. It is required to produce, from the stock rectangle S, ai copies of ri, 1 ≤ i ≤ n, to maximize a1v1 + a2v2 + · + anvn subject to the constraints ai ≤ bi. Only orthogonal guillotine cuts are permitted. All parameters are integers. A best-first tree search algorithm based on Wang's bottom-up approach is described that guarantees optimal solutions and is more efficient than existing methods.
Material Management in Decentralized Supply Chains
Authors: Lee Hau L. , Billington Corey
Published: November 2008

A supply chain is a network of facilities that performs the functions of procurement of material, transformation of material to intermediate and finished products, and distribution of finished products to customers. Often, organizational barriers between these facilities exist, and information flows can be restricted such that complete centralized control of material flows in a supply chain may not be feasible or desirable. Consequently, most companies use decentralized control in managing the different facilities at a supply chain. In this paper, we describe what manufacturing managers at Hewlett-Packard Company (HP) see as the needs for model support in managing material flows in their supply chains. These needs motivate our initial development of such a model for supply chains that are not under complete centralized control. We report on our experiences of applying such a model in a new product development project of the DeskJet printer supply chain at HP. Finally, we discuss avenues to develop better models, as well as to fully exploit the power of such models in application.
Decision Analysis with Incomplete Utility and Probability Information
Authors: Moskowitz Herbert , Preckel Paul V. , Yang Aynang
Published: November 2008

An approach to the solution of decision analysis problems under uncertainty with imprecise and incomplete information is presented. The methodology is designed for cases in which payoffs (conditional on the state of nature) are known precisely, but only limited or imprecise probability and utility information is available regarding a decision maker's beliefs and tastes. A decision maker provides: conditional payoffs, (optionally) bounds on state probabilities, bounds on the certainty equivalent for a simple lottery, any known relationships between probabilities of states of nature, and a series of strict preferences between pairs of vectors of conditional payoffs. We assume an exponential utility function with unknown parameter. The method proceeds by sequentially eliciting preferences, new bounds on probabilities and/or the certainty equivalent, and new relationships among probabilities until the problem is solved. The methodology is demonstrated through a two-state and a three-state example which illustrate the effects of the progressive elicitation of additional information.
Simulation Designs and Correlation Induction for Reducing Second-Order Bias in First-Order Response Surfaces
Authors: Donohue Joan M. , Houck Ernest C. , Myers Raymond H.
Published: November 2008

Construction of simulation designs for the estimation of response surface metamodels is often based on optimal design theory. Underlying such designs is the assumption that the postulated model provides the correct representation of the simulated response. As a result, the location of design points and the assignment of pseudorandom number streams to these experiments are determined through the minimization of some function of the covariance matrix of the model coefficient estimators. In contrast, we assume that the postulated model may be incorrect. Attention is therefore directed to the development of simulation designs that offer protection against the bias due to possible model misspecification as well as error variance. The particular situation examined is the estimation of first-order response surface models in the presence of polynomials of order two. Traditional two-level factorial plans combined with one of three pseudorandom number assignment strategies define the simulation designs. Specification of the factor settings for these experimental plans are based on two integrated mean squared error criteria of particular interest in response surface studies. For both design criteria, comparisons of the optimal designs across the three assignment strategies are presented to assist experimenters in the selection of an appropriate simulation design.
Approximating Nonrenewal Processes by Markov Chains: Use of Super-Erlang (SE) Chains
Authors: Bitran Gabriel R. , Dasu Sriram
Published: November 2008

We study a class of point processes generated by transitions in Markov chains. We are primarily concerned with approximating superposed phase renewal processes by these point processes. We identify a subclass of Markov chains that we call Super-Erlang chains. These chains have special properties that facilitate the development of approximations. We outline an approximation procedure and provide computational results that demonstrate the potential of the approach. The primary motivation for this study is the analysis of open queueing networks.
A Bayesian Sequential Single Machine Scheduling Problem to Minimize the Expected Weighted Sum of Flowtimes of Jobs with Exponential Processing Times
Authors: Hamada Toshio , Glazebrook Kevin D.
Published: November 2008

In this paper, we consider a scheduling problem in which m classes, J1, J2, …, Jm, of independent jobs with ready time 0 are to be processed by a single machine. The number of jobs of class Ji is ni and the processing times of these ni jobs are independent and identically distributed exponentially distributed with unknown parameter θi, which has a conjugate gamma prior. The objective is to minimize the expected (weighted) sum of flowtimes of all the jobs, where Ri is the weight for a job of class Ji. The problem is formulated as a dynamic program and optimal strategies are derived.
Analysis of Heuristics for Preemptive Parallel Machine Scheduling with Batch Setup Times
Authors: Monma Clyde L. , Potts Chris N.
Published: November 2008

The problem of preemptively scheduling N jobs on M identical parallel machines to minimize the maximum completion time is considered. Jobs are divided into B batches and a setup time on a machine is necessary whenever there is a switch from processing a job in one batch to a job in another batch. Setup times are assumed to depend only on the batch of the job to be scheduled next. Two types of heuristics are proposed and analyzed. The first type uses list scheduling for complete batches and then splits batches between selected pairs of machines. It has a time requirement of O(N + (M + B) log(M + B)). Furthermore, for a certain class of problems which includes the case that each batch contains a single job, it has a worst-case performance ratio of 3/2 − 1/(4M − 4) when M ≤ 4 and of 5/3 − 1/M when M is a multiple of 3 and M > 3. The second type of heuristic uses a procedure which resembles McNaughton's preemptive scheduling algorithm. It requires O(N) time and has a worst-case performance ratio of [Formula: see text].
The Repair Kit Problem Revisited
Authors: Brumelle Shelby , Granot Daniel
Published: November 2008

The repair kit problem is concerned with finding an optimal kit of parts and tools to carry for on-site repairs. The choice of a kit involves evaluating two attributes—an annual holding cost and a penalty for failing to complete repairs. We present a unifying approach for the repair kit problem which demonstrates that a monotone sequence of optimal kits exists for several parameterizations of the objective function combining the two attributes. We analyze the structure of the Pareto set of the convex hull of the kits in the attribute space and show the relationship between the extreme points of these Pareto sets and the optimal kits. Decomposition and various monotonicity properties of the repair kit problem yield some computational simplifications in generating optimal kits.
Formulating a Mixed Integer Programming Problem to Improve Solvability
Authors: Barnhart Cynthia , Johnson Ellis L. , Nemhauser George L. , Sigismondi Gabriele , Vance Pamela
Published: November 2008

A standard formulation of a real-world distribution problem could not be solved, even for a good solution, by a commercial mixed integer programming code. However, after reformulating it by reducing the number of 0-1 variables and tightening the linear programming relaxation, an optimal solution could be found efficiently. The purpose of this paper is to demonstrate, with a real application, the practical importance of the need for good formulations in solving mixed integer programming problems.