bluuebunny/crossref_metadata_2025 huggingface dataset:
Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems
Authors: Martello Silvano , Toth Paolo
Published: November 2008

It is well-known that many instances of the 0-1 knapsack problem can be effectively solved to optimality also for very large values of n (the number of binary variables), while other instances cannot be solved for n equal to only a few hundreds. We propose upper bounds obtained from the mathematical model of the problem by adding valid inequalities on the cardinality of an optimal solution, and relaxing it in a Lagrangian fashion. We then introduce a specialized iterative technique for determining the optimal Lagrangian multipliers in polynomial time. A branch-and-bound algorithm is finally developed. Computational experiments prove that several classes of hard instances are effectively solved even for large values of n.
Ready-Time Scheduling with Stochastic Service Times
Authors: Hodgson Thom J. , King Russell E. , Stanfield Paul M.
Published: November 2008

A frequently encountered scheduling problem is to determine simultaneously a material and job ready time and production sequence based on customer-specified due dates. Each job has a stochastic production time and a deterministic due date. The ready time is constrained in that the probability that each job will be complete by its due date must meet some minimum level of confidence. The objective in such an instance is to postpone the ready time as late as possible without violating these constraints. The steps and effort necessary to determine the maximum ready time and optimal production sequence, and cases in which this effort may be significantly reduced are presented. The resulting model is applied directly to single-facility and flow-shop production environments. Methods are shown for scheduling in a dynamic environment.
Modeling in Performance-Enhancing Processes
Authors: Pritsker A. Alan B.
Published: November 2008

The original concept for this paper comes from my 1994 Omega Rho lecture in which I described the concept of a Factory-in-the-Computer© as a set of models, primarily simulation-based, that could be embedded in a manufacturing system and be a part of an executive decision support system. In attempting to write a paper based on this Omega Rho presentation, it became evident that it was necessary to include information on basic processes related to the use of modeling and simulation. The end result was the writing of a paper which addresses the process for enhancing performance and issues related to the use of modeling in such processes.
Improved Fashion Buying with Bayesian Updates
Authors: Eppen Gary D. , Iyer Ananth. V.
Published: November 2008

We focus on the problem of buying fashion goods for the “big book” of a catalogue merchandiser. This company also owns outlet stores and thus has the opportunity, as the season evolves, to divert inventory originally purchased for the big book to the outlet store. The obvious questions are: (1) how much to order originally, and (2) how much to divert to the outlet store as actual demand is observed.

We develop a model of demand for an individual item. The model is motivated by data from the women's designer fashion department and uses both historical data and buyer judgement. We build a stochastic dynamic programming (DP) model of the fashion buying problem that incorporates the model of demand. The DP model is used to derive the structure of the optimal inventory control policy. We then develop an updated Newsboy heuristic that is intuitively appealing and easily implemented. When this heuristic is compared to the optimal solution for a wide variety of scenarios, we observe that it performs very well. Similar numerical experiments show that the current company practice does not yield consistently good results when compared to the optimal solution.
Balancing Retailer Inventories
Authors: McGavin Edward J. , Ward James E. , Schwarz Leroy B.
Published: November 2008

This paper examines the optimality of inventory “balancing” in a one-warehouse N-retailer distribution system facing stochastic demand for a single product over T successive time intervals. In particular, we consider the division of predetermined quantities of warehouse stock among retailers in each interval. Balancing attempts to bring the retailer-inventories to the same (normalized with respect to first-interval demand) net inventory level. When the demand distribution over the T periods is symmetric with respect to all pairs of retailers, and retailer cost over the T-intervals is a convex function of the T shipments, we show that balancing divisions are optimal. The required convexity condition is shown to be satisfied for some familiar cost functions when shortages are backordered and lost. However for other cost functions, the convexity condition is satisfied under backordering, but not under lost sales. We also consider the nonidentical-retailer (demands are not symmetric) case and provide examples to show that balancing is generally not optimal, even for relatively common, simple cost functions.
A Branch-and-Price Algorithm for the Generalized Assignment Problem
Authors: Savelsbergh Martin
Published: November 2008

The generalized assignment problem examines the maximum profit assignment of jobs to agents such that each job is assigned to precisely one agent subject to capacity restrictions on the agents. A new algorithm for the generalized assignment problem is presented that employs both column generation and branch-and-bound to obtain optimal integer solutions to a set partitioning formulation of the problem.
A Differential Game Theoretic Model for Duopolistic Competition on Design Quality
Authors: Mukhopadhyay Samar K. , Kouvelis Panagiotis
Published: November 2008

In this paper we propose a differential game theoretic model to analyze the design quality and pricing decisions for a product over the product life cycle. The market is represented as a duopoly where our product competes against a similar product marketed by our competition. The duopolistic competition is modeled as a two-player nonzero sum noncooperative game. The resulting control theoretic model is solved under certain functional assumptions to describe the Nash equilibrium strategies of the two competitors. Finally, observations made on an extensive set of numerical experimentations over a variety of model parameters are summarized into a set of relevant managerial guidelines on developing design quality and pricing strategies.
Dynamic Scheduling Rules for a Multiproduct Make-to-Stock Queue
Authors: Perez Agnes Peña , Zipkin Paul
Published: November 2008

This paper develops a simple but effective heuristic policy for a stochastic production-inventory system, where several products share a single processor of limited capacity. Our policy combines the best features, and avoids the weaknesses, of prior approaches in the literature. Limited numerical tests suggest that the method performs well.
Optimality of (s, S) Policies in Inventory Models with Markovian Demand
Authors: Sethi Suresh P. , Cheng Feng
Published: November 2008

This paper is concerned with a generalization of classical inventory models (with fixed ordering costs) that exhibit (s, S) policies. In our model, the distribution of demands in successive periods is dependent on a Markov chain. The model includes the case of cyclic or seasonal demand. The model is further extended to incorporate some other realistic features such as no ordering periods and storage and service level constraints. Both finite and infinite horizon nonstationary problems are considered. We show that (s, S) policies are also optimal for the generalized model as well as its extensions.
Equilibrium Threshold Strategies: The Case of Queues with Priorities
Authors: Hassin Refael , Haviv Moshe
Published: November 2008

Multiplicity of solutions is typical for systems where the individual's tendency to act in a certain way increases when more of the other individuals in the population act in this way. We provide a detailed analysis of a queueing model in which two priority levels can be purchased. In particular, we compute all of the Nash equilibrium strategies (pure and mixed) of the threshold type.
Scheduling A Major College Basketball Conference
Authors: Nemhauser George L. , Trick Michael A.
Published: November 2008

The nine universities in the Atlantic Coast Conference (ACC) have a basketball competition in which each school plays home and away games against each other over a nine-week period. The creation of a suitable schedule is a very difficult problem with a myriad of conflicting requirements and preferences. We develop an approach to scheduling problems that uses a combination of integer programming and enumerative techniques. Our approach yields reasonable schedules very quickly and gave a schedule that was accepted by the ACC for play in 1997-1998.
Quality Control for Products Supplied with Warranty
Authors: Chen Jinfa , Yao David D. , Zheng Shaohui
Published: November 2008

A batch of products is to be supplied to customers with warranty. The units in the batch are either defective or nondefective, with different lifetime distributions. The defect rate—the proportion of defects in the batch—is itself a random variable, known only in terms of its distribution. We develop a sequential quality control procedure that exploits the knowledge of the defect distribution gained through inspection, and strikes an optimal balance between the inspection repair cost and the warranty cost. We identify a simple threshold policy, and we prove its optimality for a very general class of warranty cost functions without imposing any restrictions on the type of distributions involved. The key to optimality is that the warranty cost, as a function of the number of inspected units and the conditional defect index, satisfies a so-called K-submodularity property, which is a strengthening of the usual notion of submodularity.
Performance Bounds and Pathwise Stability for Generalized Vacation and Polling Systems
Authors: Altman Eitan , Foss Serguei , Riehl Eric , Stidham Shaler
Published: November 2008

We consider a generalized vacation or polling system, modeled as an input-output process operating over successive “cycles,” in which the service mechanism can be in an “up” mode (processing) or “down” mode (e.g., vacation, walking). Our primary motivation is polling systems, in which there are several queues and the server moves cyclically between them providing some service in each. Our basic assumption is that the amount of work that leaves the system in a “cycle” is no less than the amount present at the beginning of the cycle. This includes the standard gated and exhaustive policies for polling systems in which a cycle begins whenever the server arrives at some prespecified queue. The input and output processes satisfy model-dependent conditions: pathwise bounds on the average rate and the burstiness (Cruz bounds); existence of long-run average rates; a pathwise generalized Law of the Iterated Logarithm; or exponentially or polynomially bounded tail probabilities of burstiness. In each model we show that these properties are inherited by performance measures such as the workload and output processes, and that the system is stable (in a model-dependent sense) if the input rate is smaller than the up-mode processing rate.
The Dynamic and Stochastic Knapsack Problem
Authors: Kleywegt Anton J. , Papastavrou Jason D.
Published: November 2008

The Dynamic and Stochastic Knapsack Problem (DSKP) is defined as follows. Items arrive according to a Poisson process in time. Each item has a demand (size) for a limited resource (the knapsack) and an associated reward. The resource requirements and rewards are jointly distributed according to a known probability distribution and become known at the time of the item's arrival. Items can be either accepted or rejected. If an item is accepted, the item's reward is received; and if an item is rejected, a penalty is paid. The problem can be stopped at any time, at which time a terminal value is received, which may depend on the amount of resource remaining. Given the waiting cost and the time horizon of the problem, the objective is to determine the optimal policy that maximizes the expected value (rewards minus costs) accumulated. Assuming that all items have equal sizes but random rewards, optimal solutions are derived for a variety of cost structures and time horizons, and recursive algorithms for computing them are developed. Optimal closed-form solutions are obtained for special cases. The DSKP has applications in freight transportation, in scheduling of batch processors, in selling of assets, and in selection of investment projects.
Optimal Pricing of Priority Services
Authors: Rao S. , Petersen E. R.
Published: November 2008

We consider the problem of a service facility that offers m different priority classes to its n customers, and sets a tariff (price-schedule) to maximize profit. Each customer must use the service facility and will select an output rate and the priority classes used to maximize profit. The problem is formulated as a noncooperative game. We show that equilibrium output rates and assignments to priority classes can be determined by solving the integrated system problem (ISP) that maximizes the joint profit of all agents. The service facility can be represented by a network, and ISP is a traffic assignment problem. A tariff schedule that induces each customer to select the integrated system output rate and assignment is said to be vertically efficient. We show that the server can select vertically efficient tariffs that result in an equilibrium. Optimal pricing for the special case where the service facility is modeled as a priority queue is discussed. Examples are included to illustrate the results.
Evidence Propagation and Value of Evidence on Influence Diagrams
Authors: Ezawa Kazuo J.
Published: November 2008

In this paper, we introduce evidence propagation operations on influence diagrams, a concept of the value of evidence to measure the impact/value of new observations/experimentation, and a concept of the value of revelation. Evidence propagation operations are critical for the computation of the value of evidence, general update and inference operations in normative expert systems that are based on the influence diagram (generalized Bayesian network) paradigm. The value of evidence allows us to compute the outcome sensitivity directly defined as the maximum difference among the values of evidence, and the value of perfect information, as the expected value of the values of evidence. We define the value of revelation as the optimal value of the values of evidence. We discuss the relationship between the value of revelation and the value of control. We also discuss implementation issues related to computation of the value of evidence and the value of perfect information.
Direction Choice for Accelerated Convergence in Hit-and-Run Sampling
Authors: Kaufman David E. , Smith Robert L.
Published: November 2008

Hit-and-Run algorithms are Monte Carlo procedures for generating points that are asymptotically distributed according to general absolutely continuous target distributions G over open bounded regions S. Applications include nonredundant constraint identification, global optimization, and Monte Carlo integration. These algorithms are reversible random walks that commonly incorporate uniformly distributed step directions. We investigate nonuniform direction choice and show that, under regularity conditions on the region S and target distribution G, there exists a unique direction choice distribution, characterized by necessary and sufficient conditions depending on S and G, which optimizes the Doob bound on rate of convergence. We include computational results demonstrating greatly accelerated convergence for this optimizing direction choice as well as for more easily implemented adaptive heuristic rules.
Integrated Simulation, Heuristic and Optimisation Approaches to Staff Scheduling
Authors: Mason Andrew J. , Ryan David M. , Panton David M.
Published: November 2008

This paper details a new simulation and optimisation based system for personnel scheduling (rostering) of customs staff at the Auckland International Airport, New Zealand. An integrated approach using simulation, heuristic descent, and integer programming techniques has been developed to determine near-optimal staffing levels. The system begins by using a new simulation system embedded within a heuristic search to determine minimum staffing levels for arrival and departure work areas. These staffing requirements are then used as the input to an integer programming model, which optimally allocates full- and part-time staff to each period of the working day. These shifts are then assigned to daily work schedules having a six-day-on, three-day-off structure. The application of these techniques has resulted in significantly lower staffing levels, while at the same time creating both high-quality rosters and ensuring that all passenger processing targets are met. This paper charts the development of this system, outlines failures where they have occurred, and summarises the ongoing impacts of this work on the organisation.
Stochastic Network Interdiction
Authors: Cormican Kelly J. , Morton David P. , Wood R. Kevin
Published: November 2008

Using limited assets, an interdictor attempts to destroy parts of a capacitated network through which an adversary will subsequently maximize flow. We formulate and solve a stochastic version of the interdictor's problem: Minimize the expected maximum flow through the network when interdiction successes are binary random variables. Extensions are made to handle uncertain arc capacities and other realistic variations. These two-stage stochastic integer programs have applications to interdicting illegal drugs and to reducing the effectiveness of a military force moving materiel, troops, information, etc., through a network in wartime. Two equivalent model formulations allow Jensen's inequality to be used to compute both lower and upper bounds on the objective, and these bounds are improved within a sequential approximation algorithm. Successful computational results are reported on networks with over 100 nodes, 80 interdictable arcs, and 180 total arcs.
Valuing Oil Properties: Integrating Option Pricing and Decision Analysis Approaches
Authors: Smith James E. , McCardle Kevin F.
Published: November 2008

There are two major competing procedures for evaluating risky projects where managerial flexibility plays an important role: one is decision analytic, based on stochastic dynamic programming, and the other is option pricing theory (or contingent claims analysis), based on the no-arbitrage theory of financial markets. In this paper, we show how these two approaches can be profitably integrated to evaluate oil properties. We develop and analyze a model of an oil property—either a developed property or a proven but undeveloped reserve—where production rates and oil prices both vary stochastically over time and, at any time, the decision maker may terminate production or accelerate production by drilling additional wells. The decision maker is assumed to be risk averse and can hedge price risks by trading oil futures contracts. We also describe extensions of this model that incorporate additional uncertainties and options, discuss its use in exploration decisions and in evaluating a portfolio of properties rather than a single property, and briefly describe other potential applications of this integrated methodology.
Control of a Single-Server Tandem Queueing System with Setups
Authors: Duenyas Izak , Gupta Diwakar , Olsen Tava Lennon
Published: November 2008

This paper considers the control of a single-server tandem queueing system with setups. Jobs arrive to the system according to a Poisson process and are produced to order. A single server must perform a number of different operations on each job. There is a setup time for the server to switch between different operations. We assume that there is a holding cost at each operation, which is nondecreasing in operation number (i.e., as value is added to a job, it becomes more expensive to hold). The control problem is to decide which job the server should process at each point in time.

We formulate this control problem as a Markov-Decision Process. We partially characterize the optimal policy, develop an exact analysis of exhaustive and gated polling policies, and develop an effective heuristic policy. The results of a simulation study, which tests the performance of the policies considered, are reported. These computational results indicate that our heuristic is effective for a wide variety of cases.
Solving the Uncapacitated Network Design Problem by a Lagrangean Heuristic and Branch-and-Bound
Authors: Holmberg Kaj , Hellstrand Johan
Published: November 2008

The network design problem is a multicommodity minimal cost network flow problem with fixed costs on the arcs, i.e., a structured linear mixed-integer programming problem. It has various applications, such as construction of new links in transportation networks, topological design of computer communication networks, and planning of empty freight car transportation on railways. We present a Lagrangean heuristic within a branch-and-bound framework as a method for finding the exact optimal solution of the uncapacitated network design problem with single origins and destinations for each commodity (the simplest problem in this class, but still NP-hard). The Lagrangean heuristic uses a Lagrangean relaxation as subproblem, solving the Lagrange dual with subgradient optimization, combined with a primal heuristic (the Benders subproblem) yielding primal feasible solutions. Computational tests on problems of various sizes (up to 1000 arcs, 70 nodes and 138 commodities or 40 nodes and 600 commodities) and of several different structures lead to the conclusion that the method is quite powerful, outperforming for example a state-of-the-art mixed-integer code, both with respect to problem size and solution time.
Algorithms for Separable Nonlinear Resource Allocation Problems
Authors: Kodialam Muralidharan S. , Luss Hanan
Published: November 2008

We consider a simple resource allocation problem with a single resource constraint. The objective function is composed of separable, convex performance functions, one for each activity. Likewise, the constraint has separable, convex resource-usage functions, one for each activity. The objective is to minimize the sum of the performance functions, subject to satisfying the resource constraint and nonnegativity constraints. This problem extends the well-studied problem in which the resource constraint is linear. We present several algorithms to solve the problem. These algorithms extend approaches developed for the linearly constrained problem. They can readily solve large problems and find the optimal solution in a number of iterations that does not exceed the number of variables. We provide several examples for illustration purposes, present computational results, and highlight the similarities and differences among the algorithms.
Mosaicking of Aerial Photographic Maps Via Seams Defined by Bottleneck Shortest Paths
Authors: Fernandez Elena , Garfinkel Robert , Arbiol Roman
Published: November 2008

The Cartographic Institute of Catalonia (ICC) produces commercial aerial photographic maps of locations in Europe and South America. These maps are often so large that it is necessary to produce one map from two or more photographs, which are combined two at a time in a process called mosaicking. The objective is to make the final map appear to be the product of a single photograph by producing a seam that is invisible even to an expert cartographer. The problem and a variation are modeled via bottleneck shortest paths and cycles. Optimization algorithms are developed for both, and the first has been implemented with demonstrable impact on the company. The second represents a new class of constrained shortest cycle problems.
Submodular Returns and Greedy Heuristics for Queueing Scheduling Problems
Authors: Garbe R. , Glazebrook K. D.
Published: November 2008

We consider a range of controlled stochastic systems satisfying conservation laws together with a reducibility property that says that appropriate laws continue to hold when access to the system is restricted to a subset of all possible demand (job, customer) types. We show that for linear objectives, the optimum system-wide performance is a nondecreasing submodular (or supermodular) function of the subset chosen and that these properties are inherited from the geometry of the performance space concerned. These results are of considerable interest in their own right, but they also motivate the use of greedy heuristics for the solution of a range of job selection and scheduling problems which have hitherto seemed intractable. Computational experience suggests that such heuristics perform very well.
The Air Traffic Flow Management Problem with Enroute Capacities
Authors: Bertsimas Dimitris , Patterson Sarah Stock
Published: November 2008

Throughout the United States and Europe, demand for airport use has been increasing rapidly, while airport capacity has been stagnating. Over the last ten years the number of passengers has increased by more than 50 percent and is expected to continue increasing at this rate. Acute congestion in many major airports has been the unfortunate result. For U.S. airlines, the expected yearly cost of the resulting delays is currently estimated at $3 billion. In order to put this number in perspective, the total reported losses of all U.S. airlines amounted to approximately $2 billion in 1991 and $2.5 billion in 1990. Furthermore, every day 700 to 1100 flights are delayed by 15 minutes or more. European airlines are in a similar plight. Optimally controlling the flow of aircraft either by adjusting their release times into the network (ground-holding) or their speed once they are airborne is a cost effective method to reduce the impact of congestion on the air traffic system. This paper makes the following contributions: (a) we build a model that takes into account the capacities of the National Airspace System (NAS) as well as the capacities at the airports, and we show that the resulting formulation is rather strong as some of the proposed inequalities are facet defining for the convex hull of solutions; (b) we address the complexity of the problem; (c) we extend that model to account for several variations of the basic problem, most notably, how to reroute flights and how to handle banks in the hub and spoke system; (d) we show that by relaxing some of our constraints we obtain a previously addressed problem and that the LP relaxation bound of our formulation is at least as strong when compared to all others proposed in the literature for this problem; and (e) we solve large scale, realistic size problems with several thousand flights.
A Multiclass Hybrid Production Center in Heavy Traffic
Authors: Nguyen Viên
Published: November 2008

This paper presents an analysis of a single-stage hybrid production system that makes multiple types of products, some of which are made to-order while others are made to-stock. The analysis begins with a formal heavy traffic limit theorem of the production system, which is modeled as a mixed queueing network. Taking insights from the limit theorem, the analysis continues with the development of an approximation procedure. Numerical experiments indicate that this procedure provides good estimates for performance measures such as fill rates and average inventory levels.
A Dynamic Model for Requirements Planning with Application to Supply Chain Optimization
Authors: Graves Stephen C. , Kletter David B. , Hetzel William B.
Published: November 2008

This paper develops a new model for studying requirements planning in multistage production-inventory systems. We first characterize how most industrial planning systems work, and we then develop a mathematical model to capture some of the key dynamics in the planning process. Our approach is to use a model for a single production stage as a building block for modeling a network of stages. We show how to analyze the single-stage model to determine the production smoothness and stability for a production stage and the inventory requirements. We also show how to optimize the tradeoff between production capacity and inventory for a single stage. We then can model the multistage supply chain using the single stage as a building block. We illustrate the multistage model with an industrial application, and we conclude with some thoughts on a research agenda.
The Stabilizing Effect of Inventory in Supply Chains
Authors: Baganha Manuel P. , Cohen Morris A.
Published: November 2008

This paper presents a hierarchical model framework for the analysis of the stabilizing effect of inventories in multiechelon manufacturing/distribution supply chains. This framework is used to compare the variance of demand to the variance of replenishment orders at different echelons of the system (e.g., retailer, wholesaler). Empirical data and experience with management games suggest that, in most industries, inventory management policies can have a destabilizing effect by increasing the volatility of demand as it passes up through the chain (the “bullwhip” effect). Our model helps to explain these observations and indicates mechanisms that can promote stabilization. The analysis results also define sufficient conditions for the existence of stabilization and relate these conditions to the optimality of myopic control policies.
Scheduling with Finite Capacity Output Buffers
Authors: Hall Nicholas G. , Posner Marc E. , Potts Chris N.
Published: November 2008

In many scheduling problems, a job that completes processing may need to be held in an output buffer until the customer is ready to accept delivery. Buffer capacity is usually assumed to be infinite.

We study a number of the best known single machine scheduling problems, under several alternative assumptions about the capacity of the output buffer. Specifically, we allow the buffer capacity to be either zero, fixed, or specified as part of problem input. We also consider situations in which all jobs have the same storage requirement in the buffer, and others where the storage requirement may vary. Further, we consider generalizations where there is a time interval within which a customer accepts delivery without cost to the producer.

A classification scheme for these problems is provided. For each problem considered, we provide either an efficient algorithm or a proof that such an algorithm is unlikely to exist. Our results provide a mapping of the computational complexity of these problems which parallels those that are available for classical scheduling problems with infinite buffer capacity.
Managing Stochastic Multiproduct Systems: Model, Measures, and Analysis
Authors: Anupindi Ravi , Tayur Sridhar
Published: November 2008

We consider a model for managing a single stage that produces multiple items. The production rates are finite, and there are switchover times. The interarrival times and quantities of demands for the items are random, and demand may occur for a set of items. We consider order focussed measures: cost based on response times; service levels based on quoted lead times and Type-1 service.

We operate the stage in the following manner: (1) there is a cyclic schedule that determines the sequence of items and the number of times a particular item is produced in a cycle; (2) given a cyclic schedule, production of each item follows a modified base-stock policy or a (s, S) policy. We present a simulation based procedure to obtain good values for the base stock levels or S (for any fixed S − s) for each of the above performance measures. Numerical results indicate that good solutions can be obtained with modest computational effort. We also report on a real world implementation of this model.
Formulation of the Russell-Yasuda Kasai Financial Planning Model
Authors: Cariño David R. , Ziemba William T.
Published: November 2008

This paper describes the formulation of the Russell-Yasuda Kasai financial planning model, including the motivation for the model. The presentation complements the discussion of the technical details of the financial modeling process and the managerial impact of its use to help allocate the firm's assets over time discussed in Cariño et al. (1994, 1998, respectively). The multistage stochastic linear program incorporates Yasuda Kasai's asset and liability mix over a five-year horizon followed by an infinite horizon steady-state end-effects period. The objective is to maximize expected long-run profits less expected penalty costs from constraint violations over the infinite horizon. Scenarios are used to represent the uncertain parameter distributions. The constraints represent the institutional, cash flow, legal, tax, and other limitations on the asset and liability mix over time.
Concepts, Technical Issues, and Uses of the Russell-Yasuda Kasai Financial Planning Model
Authors: Cariño David R. , Myers David H. , Ziemba William T.
Published: November 2008

This paper discusses technical aspects of the Russell-Yasuda Kasai financial planning model. These include the models for the discrete distribution scenario generation processes for the uncertain parameters of the model, the mathematical approach used to develop the infinite-horizon end-effects part of the model, a comparison of algorithms used in the model's solution, and a comparison of the multistage stochastic linear programming model with the previous technology, static mean-variance analysis. Experience and benefits of the model in Yasuda-Kasai's financial planning process is also discussed.
Diagnosis with Dependent Symptoms: Bayes Theorem and the Analytic Hierarchy Process
Authors: Saaty Thomas L. , Vargas Luis G.
Published: November 2008

Judgments are needed in medical diagnosis to determine what tests to perform given certain symptoms. For many diseases, what information to gather on symptoms and what combination of symptoms lead to a given disease are not well known. Even when the number of symptoms is small, the required number of experiments to generate adequate statistical data can be unmanageably large. There is need in diagnosis for an integrative model that incorporates both statistical data and expert judgment. When statistical data are present but no expert judgment is available, one property of this model should be to reproduce results obtained through time honored procedures such as Bayes theorem. When expert judgment is also present, it should be possible to combine judgment with statistical data to identify the disease that best describes the observed symptoms. Here we are interested in the Analytic Hierarchy Process (AHP) framework that deals with dependence among the elements or clusters of a decision structure to combine statistical and judgmental information. It is shown that the posterior probabilities derived from Bayes theorem are part of this framework, and hence that Bayes theorem is a sufficient condition of a solution in the sense of the AHP. An illustration is given as to how a purely judgment-based model in the AHP can be used in medical diagnosis. The application of the model to a case study demonstrates that both statistics and judgment can be combined to provide diagnostic support to medical practitioner colleagues with whom we have interacted in doing this work.
Dynamic Scheduling of a Two-Class Queue with Setups
Authors: Reiman Martin I. , Wein Lawrence M.
Published: November 2008

We analyze two scheduling problems for a queueing system with a single server and two customer classes. Each class has its own renewal arrival process, general service time distribution, and holding cost rate. In the first problem, a setup cost is incurred when the server switches from one class to the other, and the objective is to minimize the long-run expected average cost of holding customers and incurring setups. The setup cost is replaced by a setup time in the second problem, where the objective is to minimize the average holding cost. By assuming that a recently derived heavy traffic principle holds not only for the exhaustive policy but for nonexhaustive policies, we approximate (under standard heavy traffic conditions) the dynamic scheduling problems by diffusion control problems. The diffusion control problem for the setup cost problem is solved exactly, and asymptotics are used to analyze the corresponding setup time problem. Computational results show that the proposed scheduling policies are within several percent of optimal over a broad range of problem parameters.
Coordinating Clearance Markdown Sales of Seasonal Products in Retail Chains
Authors: Bitran Gabriel , Caldentey René , Mondschein Susana
Published: November 2008

In this paper we propose a methodology to set prices of perishable items in the context of a retail chain with coordinated prices among its stores and compare its performance with actual practice in a real case study. We formulate a stochastic dynamic programming problem and develop heuristic solutions that approximate optimal solutions satisfactorily. To compare this methodology with current practices in the industry, we conducted two sets of experiments using the expertise of a product manager of a large retail company in Chile. In the first case, we contrast the performance of the proposed methodology with the revenues obtained during the 1995 autumn-winter season. In the second case, we compare it with the performance of the experienced product manager in a “simulation-game” setting. In both cases, our methodology provides significantly better results than those obtained by current practices.
Achieving Air Quality Standards in the European Union
Authors: Degraeve Zeger , Koopman Gert Jan
Published: November 2008

This paper develops a methodology to select a least cost mix of transport policy measures in different regions of the European Union to attain air quality standards by the year 2010. Two fundamental characteristics of air quality problems are addressed: their variation across regions and the interregional linkages resulting from ozone pollution. We propose a column generation approach to answer the question of which policies should be introduced where to arrive at a least cost solution for the Union as a whole satisfying the emissions reduction constraints. Our methodology can be applied to a wide range of environmental policy questions with a spatial dimension characterized by interdependencies across policy instruments and environmental processes. Improvements in vehicle technology are important for meeting air quality standards. Triggering such changes through economic instruments is attractive because this accommodates the geographical variation of air quality problems throughout the European Union. Different clean fuels are suggested for different regions. Taxation on road use also plays an important role in the mix of policies to curb air pollution. Furthermore, emissions reduction from nontransport sources are of major importance in all scenarios studied.
Constrained Maximum-Entropy Sampling
Authors: Lee Jon
Published: November 2008

A fundamental experimental design problem is to select a most informative subset, having prespecified size, from a set of correlated random variables. Instances of this problem arise in many applied domains such as meteorology, environmental statistics, and statistical geology. In these applications, observations can be collected at different locations and, possibly, at different times. Information is measured by “entropy.” Practical situations have further restrictions on the design space. For example, budgetary limits, geographical considerations, as well as legislative and political considerations may restrict the design space in a complicated manner. Using techniques of linear algebra, combinatorial optimization, and convex optimization, we develop upper and lower bounds on the optimal value for the Gaussian case. We describe how these bounds can be integrated into a branch-and-bound algorithm for the exact solution of these design problems. Finally, we describe how we have implemented this algorithm, and we present computational results for estimated covariance matrices corresponding to sets of environmental monitoring stations in the Ohio Valley of the United States.
Optimal Component Assignment and Board Grouping in Printed Circuit Board Manufacturing
Authors: Hillier Mark S. , Brandeau Margaret L.
Published: November 2008

We consider operation assignment problems arising from a printed circuit board assembly process. The research was inspired by an application at Hewlett Packard where hundreds of types of printed circuit boards require the insertion of a number of components. The components can be inserted manually or by semiautomated insertion machines. The machines are limited in terms of the number of different component types that they can hold.

We investigate how to assign the boards and components to the machines and manual process so as to minimize cost. An optimal solution technique is developed for the single-machine case and for the multiple-machine case where boards are not allowed to be set up on more than one process. In addition, a heuristic is developed which gives near-optimal solutions (within 0.3%) with much less computational effort.

Although the problem this paper specifically addresses is that of partially automated PC board assembly, the results apply to a more general set of problems. Other applications include completely automated PC board assembly, flexible manufacturing systems, and general operation assignment problems.
A Dynamic Stochastic Stock-Cutting Problem
Authors: Krichagina Elena V. , Rubio Rodrigo , Taksar Michael I. , Wein Lawrence M.
Published: November 2008

We consider a stock cutting problem for a paper plant that produces sheets of various sizes for a finished goods inventory that services random customer demand. The controller decides when to shut down and restart the paper machine and how to cut completed paper rolls into sheets of paper. The objective is to minimize long-run expected average costs related to paper waste (from inefficient cutting), shutdowns, backordering, and holding finished goods inventory. A two-step procedure (linear programming in the first step and Brownian control in the second step) is developed that leads to an effective, but suboptimal, solution. The linear program greatly restricts the number of cutting configurations that can be employed in the Brownian analysis, and hence the proposed policy is easy to implement, and the resulting production process is considerably simplified. In an illustrative numerical example using representative data from an industrial facility, the proposed policy outperforms several policies that use a larger number of cutting configurations. Finally, we discuss some alternative production settings where this two-step procedure may be applicable.
Parallel Machine Scheduling, Linear Programming, and Parameter List Scheduling Heuristics
Authors: Chan Lap Mui Ann , Muriel Ana , Simchi-Levi David
Published: November 2008

In this paper we consider a class of parallel machine scheduling problems and their associated set-partitioning formulations. We show that the tightness of the linear programming relaxation of these formulations is directly related to the performance of a class of heuristics called parameter list scheduling heuristics. This makes it possible to characterize the worst possible gap between optimal solutions for the scheduling problems and the corresponding linear programming relaxations. In the case of the classical parallel machine weighted completion time model we also show that the solution to the linear programming relaxation of the set-partitioning formulation is asymptotically optimal under mild assumptions on the distribution of job weights and processing times. Finally, we extend most of the results to the time-discretized formulation of machine scheduling problems.
A Multiattribute Utility Analysis of Alternatives for the Disposition of Surplus Weapons-Grade Plutonium
Authors: Dyer James S. , Edmunds Thomas , Butler John C. , Jia Jianmin
Published: November 2008

This paper describes an application of multiattribute utility theory to support the selection of a technology for the disposition of surplus weapons-grade plutonium by the Department of Energy (DOE). This analysis evaluated 13 alternatives, examined the sensitivity of the recommendations to the weights and assumptions, and quantified the potential benefit of the simultaneous deployment of several technologies. The measures of performance that were identified through the creation of a hierarchy of objectives helped to organize the information collected during the evaluation process, and the results of the analysis were presented to DOE on several occasions. This analysis supported the final DOE recommendation to pursue a strategy of the parallel development of two of the most preferred technologies.
Multiperiod Airline Overbooking with a Single Fare Class
Authors: Chatwin Richard E.
Published: November 2008

Consider a multiperiod airline overbooking problem that relates to a single-leg flight and a single service class. Passengers may cancel their reservations at any time, including being no-shows at flight-time. At that time, the airline bumps passengers in excess of flight capacity and pays a penalty for so doing. We give conditions on the fares, refunds, and distributions of passenger demand for reservations and cancellations in each period, and on the bumping penalty function, that ensure that a booking-limit policy is optimal, i.e., in each period the airline accepts reservation requests up to a booking limit if the number of initial reservations is less than that booking limit, and declines reservation requests otherwise. The optimal booking limits are easily computed. We give conditions under which the optimal booking limits are monotone in the time to flight departure. The model is applied to the discount allocation problem in which lower fare classes book prior to higher fare classes.
Capacity Expansion and Equipment Replacement: A Unified Approach
Authors: Rajagopalan S.
Published: November 2008

Businesses frequently have to decide which of their existing equipment to replace, taking into account future changes in capacity requirements. The significance of this decision becomes clear when one notes that expenditure on new plant and equipment is a significant proportion of the GDP in the United States. The equipment replacement literature has focused on the replacement issue, usually ignoring aspects such as future demand changes and economies of scale. On the other hand, the capacity expansion literature has focused on the expansion of equipment capacity to meet demand growth, considering economies of scale but ignoring the replacement aspect. This paper attempts to unify the two streams of research by developing a general model that considers replacement of capacity as well as expansion and disposal, together with scale economy effects. Even special cases of the problems discussed here, such as the parallel machine replacement problem, have been considered difficult so far. However, we show that the problem can be solved efficiently by formulating it in a novel, disaggregate manner and using a dual-based solution procedure that exploits the structure of the problem. We also provide computational results to affirm that optimal or near-optimal solutions to large, realistic problems can be determined efficiently. We demonstrate the robustness of this approach by showing how other realistic features such as quantity discounts in purchases, alternative technology types or suppliers, and multiple equipment types can be incorporated.