bluuebunny/crossref_metadata_2025 huggingface dataset:
Dynamic Capacity Expansion Problem with Multiple Products: Technology Selection and Timing of Capacity Additions
Authors: Li Shanling , Tirupati Devanath
Published: November 2008

This paper examines a multiproduct dynamic investment model for making technology choices and expansion decisions over a finite planning horizon. The motivation for our problem comes from recent developments in the field of flexible technology such as CAD, CAM, and CIM that permit firms to invest in these more expensive, flexible technologies to provide a competitive edge in the form of an ability to respond rapidly to changing product mix. On the other hand, more specialized (dedicated) equipment may be less costly. The decisions on appropriate mixes of dedicated and flexible capacity involve many complex considerations such as economies of scale, demand patterns, and mix flexibility. We formulate the problem as a mathematical program with the objective of minimizing total investment cost. Since the problem is difficult to solve optimally, we develop a two-phased approach and present heuristics to obtain good expansion schedules. These procedures are based on an easily solvable sequence of subproblems derived from the planning problem. Our computational results suggest that these methods work well and provide acceptable solutions with reasonable effort.
Parallel Branch-and-Branch Algorithms: Survey and Synthesis
Authors: Gendron Bernard , Crainic Teodor Gabriel
Published: November 2008

We present a detailed and up-to-date survey of the literature on parallel branch-and-bound algorithms. We synthesize previous work in this area and propose a new classification of parallel branch-and-bound algorithms. This classification is used to analyze the methods proposed in the literature. To facilitate our analysis, we give a new characterization of branch-and-bound algorithms, which consists of isolating the performed operations without specifying any particular order for their execution.
Day-To-Day Dynamic Network Disequilibria and Idealized Traveler Information Systems
Authors: Friesz Terry L. , Bernstein David , Mehta Nihal J. , Tobin Roger L. , Ganjalizadeh Saiid
Published: November 2008

In this paper we present tatonnement models for calculating static Wardropian user equilibria on congested networks with fully general demand and cost structures. We present both a qualitative analysis of stability and numerical studies which show that such an approach provides a reliable means for determining static user equilibria. We also describe circumstances for which these models depict day-to-day adjustments from one realizable disequilibrium state to another and how these adjustment processes differ depending on the “quality” of the information being provided by (abstract) traveler information systems. Specifically, we demonstrate that such dynamic adjustment processes settle down to equilibria both when information is complete and when it is incomplete.
A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem
Authors: Gouveia Luis
Published: November 2008

In this paper we present a new formulation for the Capacitated Minimal Spanning Tree (CMST) problem. One advantage of the new formulation is that it is more compact (in the number of constraints) than a well-known formulation. Additionally, we show that the linear programming relaxation of both formulations produces optimal solutions with the same cost. We present a brief discussion concerning valid inequalities for the (CMST) which are directly derived from the new formulation. We show that some of the new inequalities are not dominated by some sets of facet-inducing inequalities for the (CMST). We derive some Lagrangian relaxation-based methods from the new formulation and present computational evidence showing that reasonable improvements on the original linear programming bounds can be obtained if these methods are strengthened by the use of cutting planes. The reported computational results indicate that one of the methods presented in this paper dominates, in most of the cases, the previous best methods reported in the literature. The most significant improvements are obtained in the instances with the root in the corner.
Modeling and Solving the Two-Facility Capacitated Network Loading Problem
Authors: Magnanti Thomas L. , Mirchandani Prakash , Vachani Rita
Published: November 2008

This paper studies a topical and economically significant capacitated network design problem that arises in the telecommunications industry. In this problem, given point-to-point communication demand in a network must be met by installing (loading) capacitated facilities on the arcs: Loading a facility incurs an arc specific and facility dependent cost. This paper develops modeling and solution approaches for loading facilities to satisfy the given demand at minimum cost. We consider two approaches for solving the underlying mixed integer program: a Lagrangian relaxation strategy, and a cutting plane approach that uses three classes of valid inequalities that we identify for the problem. We show that a linear programming formulation that includes these inequalities always approximates the value of the mixed integer program at least as well as the Lagrangian relaxation bound. Our computational results on a set of prototypical telecommunication data show that including these inequalities considerably improves the gap between the integer programming formulation and its linear programming relaxation: from an average of 25% to an average of 8%. These results show that strong cutting planes can be an effective modeling and algorithmic tool for solving problems of the size that arise in the telecommunications industry.
Modeling Handovers in Cellular Mobile Networks with Dynamic Channel Allocation
Authors: Pallant D. L. , Taylor P. G.
Published: November 2008

A model for a cellular mobile network is given which uses the dynamic channel allocation strategy proposed by Everitt and Macfadyen (Everitt, D. E., N. W. Macfadyen. 1983. Analysis of multicellular mobile radiotelephone systems with loss. British Telecom. Tech. J. 137–45.). In this model, handovers of calls from one cell to another are explicitly included. The equilibrium distribution of this network is shown to have product form under certain reversibility conditions. The conditions are restrictive and are, perhaps, unlikely to hold in practical models. However, their study does provide insight into the behavior of cellular systems with dynamic channel allocation. Using the product-form equilibrium distribution we are able to express the blocking probability for new calls, and the blocking probability for handover calls in terms of appropriate normalizing constants. The model is also extended to allow directed retry for handovers in which blocked handover attempts may try to gain access via another cell. This provides differential service for handovers. Again, some reversibility conditions ensure product form, and the blocking probabilities for both new and handover calls are given in terms of normalizing constants.
Facility-Wide Planning and Scheduling of Printed Wiring Board Assembly
Authors: Feo Thomas A. , Bard Jonathan F. , Holland Scott D.
Published: November 2008

In the last decade, the U.S. electronics industry has experienced a 10% annual growth rate in the assembly of printed wiring boards (PWBs). For many companies, this activity represents the most profitable component of their business with revenues in the billions for the industry as a whole. The basic functions associated with PWB assembly include inventory management, materials handling, production scheduling, and quality control, all of which are subject to a host of system-wide constraints. For the Texas Instruments facility in Austin, Texas, planning and scheduling is further complicated by the need to deal with over 10,000 different components and up to 400 different board types, each with their individual routing and bill of materials. This paper describes a decision support system known as Insites designed to assist Texas Instruments in the day-to-day assembly operations of their PWB facilities. The emphasis is on the heuristic techniques used to solve the underlying multiple machine scheduling problem and the efforts undertaken to validate and deploy the system. The identified benefits, coupled with the acceptance of Insites by both shop floor personnel and management, led the way to full system integration in early 1992.
Arc Routing Problems, Part I: The Chinese Postman Problem
Authors: Eiselt H. A. , Gendreau Michel , Laporte Gilbert
Published: November 2008

Arc routing problems arise in several areas of distribution management and have long been the object of study by mathematicians and operations researchers. In the first of a two-part survey, the Chinese postman problem (CPP) is considered. The main algorithmic results for the CPP are reviewed in five main sections: the undirected CPP, the directed CPP, the windy postman problem, the mixed CPP, and the hierarchical CPP.
Mean-Square Consistency of the Variance Estimator in Steady-State Simulation Output Analysis
Authors: Damerdji Halim
Published: November 2008

In steady-state simulation output analysis, mean-square consistency of the process-variance estimator is important for a number of reasons. One way to construct an asymptotically valid confidence interval around a sample mean is via construction of a consistent estimator of the process variance and a central limit theorem. Also, if an estimator is consistent in the mean-square sense, a mean-square error analysis is theoretically justified. Finally, batch-size selection is an open research problem in steady-state output analysis, and a mean-square error analysis approach has been proposed in the literature; to be valid, the process-variance estimators constructed must be consistent in the mean-square sense. In this paper, we prove mean-square consistency of the process-variance estimator for the methods of batch means, overlapping batch means, standardized time series (area), and spaced batch means, by rigorously computing the rate of decay of the variance of the process-variance estimators. Asymptotic results for third and higher centered moments of the batch means and area variance estimators are also given, along with central limit theorems.
Lot Sizing with Random Yields: A Review
Authors: Yano Candace Arai , Lee Hau L.
Published: November 2008

This paper reviews the literature on quantitatively-oriented approaches for determining lot sizes when production or procurement yields are random. We discuss issues related to the modeling of costs, yield uncertainty, and performance in the context of systems with random yields. We provide a review of the existing literature, concentrating on descriptions of the types of problems that have been solved and important structural results. We identify a variety of shortcomings of the literature in addressing problems encountered in practice, and suggest directions for future research.
Dispatching Petroleum Products
Authors: Ronen David
Published: November 2008

Petroleum products are distributed worldwide from refineries and lube plants to retail outlets and industrial customers. Proper dispatching of shipments of such products, packaged and in bulk, may result in significant transportation and inventory cost savings. This work examines the variety of operational environments which exist in dispatching petroleum products, and the operations research tools used by oil companies to dispatch such products. In addition, it identifies gaps where additional research is needed.
Arc Routing Problems, Part II: The Rural Postman Problem
Authors: Eiselt H. A. , Gendreau Michel , Laporte Gilbert
Published: November 2008

This is the second half of a two-part survey on arc routing problems. The first part appeared in the March–April 1995 issue of this journal. Here, the rural postman problem (RPP) is reviewed. The paper is organized as follows: applications, the undirected RPP, the directed RPP, the stacker crane problem, and the capacitated arc routing problem.
Component Fixture Positioning/Sequencing for Printed Circuit Board Assembly with Concurrent Operations
Authors: Ahmadi Javad , Ahmadi Reza , Matsuo Hirofumi , Tirupati Devanath
Published: November 2008

This paper considers the problem of positioning component fixtures on the carriers of computer, numerically controlled dual delivery machines used for populating printed circuit boards with surface mounted technology. This reel positioning problem (RPP) is one of a series of optimization problems that are critical for improving system productivity and realizing the full potential of concurrent operations. We formulate the RPP as a mathematical program and establish its complexity. Since the problem is NP-complete we focus on the development of heuristics. Our solution procedure was prompted by engineering considerations that included concerns for minimizing the changes in the carrier direction and total movement. We also present encouraging results with test problems. The method has been implemented and achieved 7 to 8% reductions in cycle time.
Bayesian Group Replacement Policies
Authors: Wilson John G. , Benmerzouga Ali
Published: November 2008

Much research has been performed in finding optimal group replacement policies for production systems consisting of parallel components, where the failure times of the components are independent identically distributed exponential random variables with a common parameter λ. This paper introduces a class of decision rules that utilizes the statistical information obtained during operation of the components. Two forms of statistical input are allowed. We assume that a prior distribution over the possible values of λ is available. It is not required that this prior distribution be in conjugate form. Statistical information that is provided by the actual failure times of the components is incorporated into the decision rule via the sufficient statistics for the problem. This results in group replacement policies that are intuitively attractive, easy to implement, and mathematically tractable.
Deadhead Selection for the Long-Haul Crew Pairing Problem
Authors: Barnhart Cynthia , Hatay Levent , Johnson Ellis L.
Published: November 2008

The long-haul crew pairing problem involves the assignment of crews to scheduled flights such that overall costs are minimized and crew availability and work rule restrictions are satisfied. These problems are characterized by international flights that typically do not operate on a daily schedule, resulting in a sparsity of flights and extended periods of inactivity for crews at some stations. To eliminate these extended rest periods and reduce overall costs, it is advantageous in some cases to deadhead crews, that is, to assign crews to flights as passengers for repositioning and better utilization. In this paper, a heuristic methodology is developed to improve crew pairing solutions through the efficient selection and utilization of deadhead flights. The methodology uses the dual solutions determined in solving the linear programming relaxation of the crew pairing problem to build arrival and departure profiles at each station. These profiles provide a mechanism to price-out potential deadhead flights. Flights that price-out favorably may be used to build improved solutions to the crew pairing problem. The Deadhead Selection Procedure is tested using data provided by a long-haul airline and is shown to achieve significant improvement in crew costs by reducing the total number of deadhead hours flown and by reducing the total duration of rest periods.
Optimal Partitioning Which Maximizes the Sum of the Weighted Averages
Authors: Gal Shmuel , Klots Boris
Published: November 2008

We consider an optimal partitioning problem that occurs in the assignment of computer jobs to a multiple cache and in other combinatorial optimization problems: For a given set of n elements, where each element i has a given frequency pi and a specific weight wi, we would like to divide the elements into m mutually exclusive groups such that the sum over all the groups of the average group weight is maximal. We characterize the optimal solution and present an algorithm which is polynomial in n for obtaining the optimal partitioning. Optimal partitioning policies for two groups has an especially simple characterization: There exist two numbers α and β, with minwi < α < β ≤ maxwi, such that all the elements with weight wi satisfying α ≤ wi ≤ β belong to one group and all other elements belong to the other group. A modification of this policy gives the optimal partitioning for an arbitrary number of groups.
On the Choice of Alternative Measures in Importance Sampling with Markov Chains
Authors: Andradóttir Sigrún , Heyman Daniel P. , Ott Teunis J.
Published: November 2008

In the simulation of Markov chains, importance sampling involves replacing the original transition matrix, say P, with a suitably chosen transition matrix Q that tends to visit the states of interest more frequently. The likelihood ratio of P relative to Q is an important random variable in the importance sampling method. It always has expectation one, and for any interesting pair of transition matrices P and Q, there is a sample path length that causes the likelihood ratio to be close to zero with probability close to one. This may cause the variance of the importance sampling estimator to be larger than the variance of the traditional estimator. We develop sufficient conditions for ensuring the tightness of the distribution of the logarithm of the likelihood ratio for all sample path lengths, and we show that when these conditions are satisfied, the likelihood ratio is approximately lognormally distributed with expected value one. These conditions can be used to eliminate some choices of the alternative transition matrix Q that are likely to result in a variance increase. We also show that if the likelihood ratio is to remain well behaved for all sample path lengths, the alternative transition matrix Q has to approach the original transition matrix P as the sample path length increases. The practical significance of this result is that importance sampling can be difficult to apply successfully in simulations that involve long sample paths.
Queueing Analysis of a Jockeying Model
Authors: Zhao Yiqiang , Grassmann Winfried K.
Published: November 2008

In this paper, we solve a type of shortest queue problem, which is related to multibeam satellite systems. We assume that the packet interarrival times are independently distributed according to an arbitrary distribution function, that the service times are Markovian with possibly different service rates, that each server has its own buffer for packet waiting, and that jockeying among buffers is permitted. Packets always join the shortest buffer(s). Jockeying takes place as soon as the difference between the longest and shortest buffers exceeds a preset number (not necessarily 1). In this case, the last packet in a longest buffer jockeys instantaneously to the shortest buffer(s). We prove that the equilibrium distribution of packets in the system is modified vector geometric. Expressions of main performance measures, including the average number of packets in the system, the average packet waiting time in the system, and the average number of jockeying, are given. Based on these solutions, numerical results are computed. By comparing the results for jockeying and nonjockeying models, we show that a significant improvement of the system performance is achieved for the jockeying model.
The Life Cycle of Goal Programming Research as Recorded in Journal Articles
Authors: Schniederjans Marc J.
Published: November 2008

This paper applies the concept of a life cycle to the subject of goal programming. The results suggest that journal article productivity in goal programming exhibits life cycle behavior, and that its life cycle is now in decline. The implications are a portent not only for goal programming research but also for other OR fields.
Locating Discretionary Service Facilities, II: Maximizing Market Size, Minimizing Inconvenience
Authors: Berman Oded , Bertsimas Dimitris , Larson Richard C.
Published: November 2008

Discretionary service facilities are providers of products and/or services that are purchased by customers who are traveling on otherwise preplanned trips such as the daily commute. Optimum location of such facilities requires them to be at or near points in the transportation network having sizable flows of different potential customers. N. Fouska (Fouska, N. 1988. Optimal Location of Discretionary Service Facilities. MS Thesis, Operations Research Center, MIT, Cambridge, Mass.) and O. Berman, R. Larson and N. Fouska (BLF [Berman, O., R. C. Larson, N. Fouska. 1992. Optimal location of discretionary service facilities. Trans. Sci. 26(3) 201–211.]) formulate a first version of this problem, assuming that customers would make no deviations, no matter how small, from the preplanned route to visit a discretionary service facility. Here the model is generalized in a number of directions, all sharing the property that the customer may deviate from the preplanned route to visit a discretionary service facility. Three different generalizations are offered, two of which can be solved approximately by greedy heuristics and the third by any approximate or exact method used to solve the p-median problem. We show for those formulations yielding to a greedy heuristic approximate solution, including the formulation in BLF, that the problems are examples of optimizing submodular functions for which the G. Nemhauser, L. Wolsey and M. Fisher (Nemhauser, G. L., L. A. Wolsey, M. L. Fisher. 1978. An analysis of approximations for maximizing sub-modular set functions, I. Math. Prog. 14 265–294.) bound on the performance of a greedy algorithm holds. In particular, the greedy solution is always within 37% of optimal, and for one of the formulations we prove that the bound is tight.
Two-Stage Multiple Comparisons with the Best for Computer Simulation
Authors: Matejcik Frank J. , Nelson Barry L.
Published: November 2008

We consider the problem of comparing a small number of stochastic systems via computer simulation when the basis for comparison is the expected value of some system performance measure. To solve this problem we develop two-stage sampling procedures that provide confidence intervals for the difference between the expected performance of each system and the best of the others. These confidence intervals are valid under mild conditions, and the procedures allow the experimenter to specify the desired precision in advance. Special cases of our results include standard indifference-zone selection procedures. The paper includes guidelines for experiment design and an illustrative example.
A Location Based Heuristic for General Routing Problems
Authors: Bramel Julien , Simchi-Levi David
Published: November 2008

We present a general framework for modeling routing problems based on formulating them as a traditional location problem called the capacitated concentrator location problem. We apply this framework to two classical routing problems: the capacitated vehicle routing problem and the inventory routing problem. In the former case, the heuristic is proven to be asymptotically optimal for any distribution of customer demands and locations. Computational experiments show that the heuristic performs well for both problems and, in most cases, outperforms all published heuristics on a set of standard test problems.
Specially Structured Uncapacitated Facility Location Problems
Authors: Jones Philip C. , Lowe Timothy J. , Muller Georg , Xu Ning , Ye Yinyu , Zydiak James L.
Published: November 2008

This paper considers a specially structured uncapacitated facility location problem. We show that several problems, including certain tool selection problems, substitutable inventory problems, supplier sourcing problems, discrete lot sizing problems, and capacity expansion problems, can be formulated as instances of the problem. We also show that the problem with m facilities and n customers can be solved in O(mn), as a shortest path problem on a directed graph.
The Nonlinear Resource Allocation Problem
Authors: Bretthauer Kurt M. , Shetty Bala
Published: November 2008

In this paper we study the nonlinear resource allocation problem, defined as the minimization of a convex function over one convex constraint and bounded integer variables. This problem is encountered in a variety of applications, including capacity planning in manufacturing and computer networks, production planning, capital budgeting, and stratified sampling. Despite its importance to these and other applications, the nonlinear resource allocation problem has received little attention in the literature. Therefore, we develop a branch-and-bound algorithm to solve this class of problems. First we present a general framework for solving the continuous-variable problem. Then we use this framework as the basis for our branch-and-bound method. We also develop reoptimization procedures and a heuristic that significantly improve the performance of the branch-and-bound algorithm. In addition, we show how the algorithm can be modified to solve nonconvex problems so that a concave objective function can be handled. The general algorithm is specialized for the applications mentioned above and computational results are reported for problems with up to 200 integer variables. A computational comparison with a 0, 1 linearization approach is also provided.
Scheduling Groups of Jobs on a Single Machine
Authors: Webster Scott , Baker Kenneth R.
Published: November 2008

Economies of scale are fundamental to manufacturing operations. With respect to scheduling, this phenomenon manifests itself in efficiencies gained from grouping similar jobs together. This paper reviews the rapidly growing literature on single-machine scheduling models that incorporate benefits from job grouping. We focus on three basic models known as family scheduling with item availability, family scheduling with batch availability, and batch processing. We present known results and introduce new results, and we pay special attention to key theoretical properties and the use of these properties in optimization procedures.
Improving Personnel Scheduling at Airline Stations
Authors: Brusco Michael J. , Jacobs Larry W. , Bongiorno Robert J. , Lyons Duane V. , Tang Baoxing
Published: November 2008

Many service organizations encounter personnel tour-scheduling problems which focus on the efficient assignment of daily shift schedules and work days to employees across a weekly planning horizon. The airline Industry, in particular, faces a highly complex and difficult tour-scheduling environment for their ground station personnel, During the past twenty years, the airlines have worked to improve continuously their abilities to effectively schedule personnel working at planesides, counters, and gates in airline stations. Substantial reductions in labor costs have resulted from the use of efficient tour-scheduling methods for such workers. We report on the development and implementation of two modules designed to enhance the tour-scheduling process associated with United Airlines’ Pegasys Manpower Planning System. The first module uses column generation to improve the selection of employee shifts. The second module, a local search heuristic based on simulated annealing, enables initial feasible tour-scheduling solutions to rapidly improve. Using data collected from all 119 United Airlines stations across the U.S., we find that the incorporation of the modules results in a potential annual cost savings of more than $8 million. We conclude with a discussion of notable implementation issues and extensions.
Exact and Approximate Solutions of Affine Reservoir Models
Authors: Lamond Bernard F. , Sobel Matthew J.
Published: November 2008

We formulate an optimization model of a multiple reservoir water resource system that encompasses interbasin transfers among two or more river basins. Autocorrelated inflows are modeled with a linear autoregressive stochastic process. Benefits for each period are assumed to depend separably on storage levels and discharges with the dependence on discharges being linear. For the important special case of a single river basin, a myopic policy (hence, computed easily) is optimal. When the model includes the possibility of interbasin transfers, a myopic policy is optimal if the deterministic and stochastic portions of the inflow process are always nonnegative. Even if this assumption is not valid, myopic policies yield useful bounds.
Computing Lower Bounds for the Quadratic Assignment Problem with an Interior Point Algorithm for Linear Programming
Authors: Resende Mauricio G. C. , Ramakrishnan K. G. , Drezner Zvi
Published: November 2008

An example of the quadratic assignment problem (QAP) is the facility location problem, in which n facilities are assigned, at minimum cost, to n sites. Between each pair of facilities, there is a given amount of flow, contributing a cost equal to the product of the flow and the distance between sites to which the facilities are assigned. Proving optimality of QAPs has been limited to instances having fewer than 20 facilities, largely because known lower bounds are weak. We compute lower bounds for a wide range of QAPs using a linear programming-based lower bound studied by Z. Drezner (1995). On the majority of QAPs tested, a new best known lower bound is computed. On 87% of the instances, we produced the best known lower bound. On several instances, including some having more the 20 facilities, the lower bound is tight. The linear programs, which can be large even for small QAPs, are solved with an interior point code that uses a preconditioned conjugate gradient algorithm to compute the interior point directions. Attempts to solve these instances using the CPLEX primal simplex algorithm as well as the CPLEX barrier (primal-dual interior point) method were successful only for the smallest instances.
Generalized Chebychev Inequalities: Theory and Applications in Decision Analysis
Authors: Smith James E.
Published: November 2008

In many decision analysis problems, we have only limited information about the relevant probability distributions. In problems like these, it is natural to ask what conclusions can be drawn on the basis of this limited information. For example, in the early stages of analysis of a complex problem, we may have only limited fractile information for the distributions in the problem; what can we say about the optimal strategy or certainty equivalents given these few fractiles? This paper describes a very general framework for analyzing these kinds of problems where, given certain “moments” of a distribution, we can compute bounds on the expected value of an arbitrary “objective” function. By suitable choice of moment and objective functions we can formulate and solve many practical decision analysis problems. We describe the general framework and theoretical results, discuss computational strategies, and provide specific results for examples in dynamic programming, decision analysis with incomplete information, Bayesian statistics, and option pricing.
Exponential Approximations for Tail Probabilities in Queues, I: Waiting Times
Authors: Abate Joseph , Choudhury Gagan L. , Whitt Ward
Published: November 2008

This paper focuses on simple exponential approximations for tail probabilities of the steady-state waiting time in infinite-capacity multiserver queues based on small-tail asymptotics. For the GI/GI/s model, we develop a heavy-traffic asymptotic expansion in powers of one minus the traffic intensity for the waiting-time asymptotic decay rate. We propose a two-term approximation for the asymptotic decay rate based on the first three moments of the interarrival-time and service-time distributions. We also suggest approximating the asymptotic constant by the product of the mean and the asymptotic decay rate. We evaluate the exponential approximations based on the exact asymptotic parameters and their approximations by making comparisons with exact results obtained numerically for the BMAP/GI/1 queue, which has a batch Markovian arrival process, and the GI/GI/s queue. Numerical examples show that the exponential approximations are remarkably accurate, especially for higher percentiles, such as the 90th percentile and beyond.
Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements
Authors: Grötschel M. , Monma C. L. , Stoer M.
Published: November 2008

We consider the important practical and theoretical problem of designing a low-cost communications network which can survive failures of certain network components. Our initial interest in this area was motivated by the need to design certain “two-connected” survivable topologies for fiber optic communication networks of interest to the regional telephone companies. In this paper, we describe some polyhedral results for network design problems with higher connectivity requirements. We also report on some preliminary computational results for a cutting plane algorithm for various real-world and random problems with high connectivity requirements, which shows promise for providing good solutions to these difficult problems.
A Stochastic Approximation Algorithm with Varying Bounds
Authors: Andradóttir Sigrún
Published: November 2008

Many optimization problems that are intractable with conventional approaches will yield to stochastic approximation algorithms. This is because these algorithms can be used to optimize functions that cannot be evaluated analytically, but have to be estimated (for instance, through simulation) or measured. Thus, stochastic approximation algorithms can be used for optimization in simulation. Unfortunately, the classical stochastic approximation algorithm sometimes diverges because of unboundedness problems. We study the convergence of a variant of stochastic approximation defined over a growing sequence of compact sets. We show that this variant converges under more general conditions on the objective function than the classical algorithm, while maintaining the same asymptotic convergence rate. We also present empirical evidence that shows that this algorithm sometimes converges much faster than the classical algorithm.
An Effective Tour Construction and Improvement Procedure for the Traveling Salesman Problem
Authors: Zweig Geoffrey
Published: November 2008

This paper presents an effective neighborhood structure for the traveling salesman problem. The neighbors of a tour are defined as the tours that can be produced by breaking the initial tour into two closed subtours, rejoining the subtours in a new configuration, and finally performing local optimization around all the changed edges. This process of generating a neighbor is termed divide and merge. Neighbor lists are used to develop variants of divide and merge that require linear and constant time per iteration, as well as an O(Nln(N)) tour construction algorithm based on insertion into the convex hull.
Evaluating Improvements in Electric Utility Reliability at British Columbia Hydro
Authors: Keeney Ralph L. , McDaniels Timothy L. , Swoveland Cary
Published: November 2008

This paper employs multiattribute value assessment and risk analysis to evaluate the benefits of four alternatives to improve electrical system reliability in British Columbia. A multiattribute value model is constructed as a cost-equivalent function, based on value judgments provided by a group of senior system planners and two senior vice presidents from BC Hydro. Using data drawn from the utility's service records and probabilities elicited from the utility's technical specialists, a risk analysis is developed to estimate the magnitude and duration of outages associated with the various alternatives. The value model and probabilities are combined to estimate the expected equivalent costs of outages over time, for the four alternatives. The influence of this analysis on BC Hydro's transmission system planning is also discussed.
Valuing Operational Flexibility Under Exchange Rate Risk
Authors: Huchzermeier Arnd , Cohen Morris A.
Published: November 2008

In this paper, we develop a stochastic dynamic programming formulation for the valuation of global manufacturing strategy options with switching costs. Overall, we adopt a hierarchical approach. First, exchange rates are modeled as stochastic diffusion processes that exhibit intercountry correlation. Second, the firm's global manufacturing strategy determines options for alternative product designs as well as supply chain network designs. Product options introduce international supply flexibility. Supply chain network options determine the firm's manufacturing flexibility through production capacity and supply chain network linkages. Third, switching costs determine the cost of operational hedging, i.e., the costs associated with reducing downside risks. Overall, the firm maximizes its expected, discounted, global, after-tax value through the exercise of product and supply chain network options and/or through exploitation of operational flexibility contingent on exchange rate realizations. In this environment, the firm must trade off fixed operating costs, switching costs, and the economic benefits derived from exploiting differentials in factor costs and corporate tax rates. A multinomial approximation of correlated exchange rate processes is proposed that leads to a consistent and tractable lattice model for this compound option valuation problem. We then demonstrate how the global manufacturing strategy planning model framework can be utilized to analyze financial and operational hedging strategies.
Effective Inventory and Service Management Through Product and Process Redesign
Authors: Lee Hau L.
Published: November 2008

One of the major challenges to operational managers is product proliferation. Product proliferation makes it difficult to forecast demands accurately, and consequently, leads to high inventory investment and poor customer service. Such proliferation is often a result of the global nature of the market place. Different markets may have different requirements for the product, due to differences in taste, language, geographical environment, or government regulations. Another reason for product proliferation is the expansion of the customer base. Different product versions are often developed for different market segments (e.g., education, personal, business, or government users may have different needs of a product). To gain control of inventory and service, significant benefits can be obtained by properly exploring the opportunities in the design of the product or the process by which the product is made. Logistic issues like inventory and service are thus important dimensions that design engineers should consider, in addition to measures like functionality, performance, and manufacturability. This paper describes how some simple inventory models can be used to support the logistic dimensions of product/process design. Actual examples are used for illustration.
The Service Facility Startup and Capacity Model and its Application to the National Cranberry Case
Authors: Li Lode , Wang Xin
Published: November 2008

This paper provides formal modeling for and analytical aid to the startup and capacity problem facing Receiving Plant #1 of National Cranberry Cooperative. The analysis is based on a finite-horizon, single-facility queueing system with general variability. Using marginal analysis, we derive simple formulas that the optimal starting time and processing capacity should satisfy. These formulas lead to the comparative statics results showing that the starting time should be optimally delayed or the processing capacity optimally decreased when the operating cost increases, when the waiting cost decreases, when the cumulative arrival process decreases, or when the capacity of storage increases. We then demonstrate that three important performance measures, the expected waiting, tardiness, and operating costs, are jointly convex with respect to two control variables, starting time and processing capacity, in a generalized version of the model. Therefore, in the applications that involve minimizing these measures, the simple formulas derived from first-order conditions are necessary and sufficient for optimality. The applications of the model in service and manufacturing operations are numerous.
Learning from Mistakes: A Note on Just-in-Time Systems
Authors: Ocaña Carlos , Zemel Eitan
Published: November 2008

In this paper we seek to reconcile two competing frameworks for inventory management, namely the classical “optimization” framework and JIT. While the first is predicated on the premise that the optimal level of inventory is obtained by balancing the costs and benefits of inventory, the latter claims that inventory is a form of waste and thus should be eliminated completely (but gradually). We show that some of the operational characteristics of JIT, as opposed to its rhetoric, can be obtained within the optimization framework provided that the relevant factors are taken into account. In particular, we show that in an environment which is subject to “learning from mistakes,” it is better to carry inventory levels which are lower than what is “operationally optimal.” We also study the (complex) relation between variability reduction, inventory levels, and overall cost. In general, reducing the variability of a system (in the sense of first or second-order stochastic dominance) will not necessarily result in a lower level of inventory, although optimal cost will be reduced. We study conditions on variability improvement that guarantee that variability reductions will always result in reduced levels of optimal inventory.
A Production Line that Balances Itself
Authors: Bartholdi John J. , Eisenstein Donald D.
Published: November 2008

In “bucket brigade” manufacturing, such as recently introduced to the apparel industry, a production line has n workers moving among m stations, where each worker independently follows a simple rule that determines what to do next. Our analysis suggests and experiments confirm that if the workers are sequenced from slowest to fastest then, independently of the stations at which they begin, a stable partition of work will spontaneously emerge. Furthermore, the production rate will converge to a value that, for typical production lines, is the maximum possible among all ways of organizing the workers and stations.
Managing Inventory with the Prospect of Obsolescence
Authors: Song Jing-Sheng , Zipkin Paul H.
Published: November 2008

How should inventory management respond when there is a possibility of imminent obsolescence (or, more generally, deteriorating demand)? We use an inventory-control model to address this question. The model incorporates a Markovian submodel to describe the uncertain events leading to obsolescence. These events and their uncertainties come in a variety of patterns. We devote considerable attention to specifying the submodel, and we compare a few alternatives numerically. Also, we compare optimal policies to simpler alternatives, and we investigate the response of the model to parameter changes. Generally, we find that obsolescence does (or should) have a substantial impact in the way inventories are managed. The nature of these effects, moreover, is fairly intricate. It appears that obsolescence cannot be captured in a simpler model through parameter adjustments. These conclusions presume that we cannot dispose of excess stock, either directly or through price promotions; we show also that the disposal option can make the problems of obsolescence more manageable.
An Analytical Method for Performance Evaluation of Kanban Controlled Production Systems
Authors: Mascolo Maria Di , Frein Yannick , Dallery Yves
Published: November 2008

The aim of this paper is to develop a general purpose analytical method for performance evaluation of multistage kanban controlled production systems. We consider a single-part type production system decomposed into stages in series. Each stage consists of a manufacturing cell and an output buffer. With each stage is associated a given number of kanbans. The kanban controlled production system is modeled as a queueing network with synchronization mechanisms. The basic principle of the proposed approximation method is to decompose the original kanban system into a set of subsystems, each subsystem being associated with a particular stage. Each subsystem is analyzed in isolation using a product-form approximation technique. An iterative procedure is then used to determine the unknown parameters of each subsystem. Numerical results show that the method is fairly accurate.
An Empirical Investigation of the Microstructure of Knowledge Acquisition and Transfer Through Learning by Doing
Authors: Epple Dennis , Argote Linda , Murphy Kenneth
Published: November 2008

Does knowledge acquired through learning by doing on one shift transfer to a second shift when it is introduced at a manufacturing plant? The answer to this question has important theoretical implications about where knowledge is embedded in organizations and about sources of productivity growth. The answer also has important practical implications for managers planning to introduce additional facilities. This paper analyzes the amount of transfer across shifts at a manufacturing facility. Specifically, we analyze the amount of knowledge that is carried forward when the plant makes the transition from one to two shifts. We also investigate whether the rate of knowledge acquisition differs by shift, and we estimate the amount of transfer that occurs across shifts once both are in operation. In addition, we study transfer over time by analyzing whether knowledge acquired through learning by doing is cumulative and persists through time or whether it depreciates.
Reducing the Cost of Demand Uncertainty Through Accurate Response to Early Sales
Authors: Fisher Marshall , Raman Ananth
Published: November 2008

Traditionally, fashion products have incurred high losses due to stockouts and inventory obsolence because long lead times coupled with a concentrated selling season force all or at least most production to be committed before demand information is available. Under a Quick Response system, lead times are shortened sufficiently to allow a greater portion of production to be scheduled in response to initial demand. We model and analyze the decisions required under Quick Response and give a method for estimating the demand probability distributions needed in our model. We applied these procedures with a major fashion skiwear firm and found that cost relative to the current informal response system was reduced by enough to increase profits by 60%. Relative to the cost that would have been incurred if no response were used, optimized response reduces cost by enough to roughly quadruple profits.
Separating Logistics Flows in the Chicago Public School System
Authors: Eisenstein Donald D. , Iyer Ananth V.
Published: November 2008

The central Chicago Public School warehouse was responsible for the distribution of supplies to 600 schools, including over $10 million annually of engineering and educational supplies. The system was fraught with problems—deliveries were not made according to schedule, schools were hoarding inventories, and some schools were paying a premium for reliable service from third party suppliers. This paper reports how we improved this logistics system. We built a mathematical model of the system, validated our model using historical data, and used the model to evaluate the impact of potential changes to the system. Our recommended changes were implemented throughout the system. We report the impact on system performance. The redesigned system shows a dramatic reduction in lead times, a reduction in capacity requirements, and an overall reduction in system costs.