HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program
September 23-27, 2002

The Price-Directed Approach to Approximate Dynamic Programming: Application to Inventory Routing     Slides:    pdf

In recent years there has been growing interest in approximate dynamic programming techniques for solving operational problems in the supply chain that are not amenable to traditional lines of analysis. Attention thus far has focused on devising rigorous simulation-based methods for adaptively computing value function approximations.

We will present a different, complementary approach to approximate dynamic programming, which we call price-directed control, that computes value function approximations directly using optimal dual prices of math programming models. These models are tractable relaxations of the underlying control problem. The resulting approximations are not subject to randomness and simulation error, and thus have more stable convergence properties. They also yield a bound against which the performance of any policy, including the price-directed policy, can be compared to obtain a guarantee relative to an optimal policy. Furthermore, duality theory can be exploited to discover economic and structural properties potentially useful to managers. However, the resulting models still can be challenging to solve, so there is opportunity for researchers to devise new computational techniques and paradigms in conjunction with new applications of the technique.

This talk will be a detailed case study on how to apply this approach in the context of inventory routing, which remains one of the most important unsolved problems in the supply chain.

Ravindra K. Ahuja (Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611)  ahuja@ufl.edu  http://www.ise.ufl.edu/ahuja

Network Optimization in Transportation Scheduling    Slides:    html    pdf    ppt

In the past decades, many advances have taken place in road, air, and rail transportation scheduling and substantial savings have been obtained by using better modeling and optimization techniques. Many of the scheduling problems arising in transportation are currently solved using a series of models where the output of one model becomes the input of the next model. The current area of research in this field is to integrate multiple models allowing greater possibilities for improvement. However, integrated models are too large to be solved optimally using existing techniques. We have been involved in developing heuristic techniques to solve several such problems in transportation scheduling which combine neighborhood search techniques with linear and integer programming. The talk will describe some important problems in airline and railroad scheduling, and will outline algorithmic approaches we have developed to solve them. Computational results of these algorithms will also be presented.

Andy Boyd (Department of Science and Research, PROS Revenue Management, Inc.)  aboyd@prosrm.com

Revenue Management and Dynamic Pricing in the Supply Chain

Supply chain management has historically focused on the planning, scheduling, and operational challenges encountered when supplying physical goods to the market. Equally important yet frequently neglected is the demand side of the equation, an area where the service industries have focused intensively. In particular, the travel and transportation industries have pioneered many highly successful demand management practices. Most notable among these practices is revenue management, which applies forecasting and optimization methodologies to address pricing and/or finished product inventory management. We discuss the role of revenue management and dynamic pricing in the overall value chain, discuss the underlying mathematical concepts that drive the value proposition, and highlight challenges.

Brenda Dietrich (Department Manager, Mathematical Sciences IBM Research)  dietric@us.ibm.com

Use of Optimization with IBM's Supply Chain

IBM uses optimization throughout its complex supply chain, in activities ranging from product design to production planning to reverse logistics. I will provide an overview of these activities, with details on a few of the more interesting ones.

Awi Federgruen (Graduate School of Business, Columbia University New York, NY 10027)  af7@columbia.edu

A General Equilibrium Model for Retail Industries with Price and Service Competition

Joint work with Fernando Bernstein (Fuqua School of Business Duke University Durham, NC 27708).

This paper develops a stochastic general equilibrium inventory model for an oligopoly, in which all inventory constraint parameters are endogenously determined. We propose several systems of demand processes whose distributions are functions of all retailers' prices and all retailers' service levels. We proceed with the investigation of the equilibrium behavior of infinite horizon models for industries facing this type of generalized competition, under demand uncertaintly.

We systematically consider the following three competition scenarios. (I) price competition only: here, we assumethat the firms' service levels are exogenously specified but characterize how the price and inventory strategy equilibrium varies with the chosen service levels. (II) simultaneous price and service level competition: here, each of the firms simultaneously chooses a service level and a combined price and inventory strategy. (III) two-stage competition: the firms make their competitive choices sequentially; in a first stage, all firms simultaneously choose a service level; in a second stage, the firms simultaneously choose a combined pricing and inventory strategy with full knowledge of the service levlels selected by all competitors.

Marshall Fisher (The Wharton School, University of Pennsylvania) fisher@wharton.upenn.edu

Rocket Science Retailing: What research opportunities does it create for us?     Slides:     html    pdf    ppt

Retailing is a big industry. In the U.S., retail business represents forty percent of the economy and is the largest employer. Retail supply chain management is still more art than science, but this is changing rapidly as retailers begin to apply analytic models to the huge volume of data they are collecting on consumer purchases and preferences. This industry-wide movement resembles the transformation of Wall Street that occurred in the 1970's when physicists and other 'rocket scientists' applied their analytic skills to investment decisions.

The rocket science retailing movement will create enormous opportunities for our profession. To better understand these opportunities, Ananth Raman and I have been working with about 40 leading retailers to assess their progress towards rocket science retailing and to accelerate that progress through selected research projects with the retailers. This talk will describe findings from this work including:

1) How do retail supply chains function?
2) What decisions arise in retail supply chain management that lend themselves to analysis?
3) Synopsis of prior research on selected topics including managing short life cycle products to maximize life cycle profits, merchandise testing and store level assortment planning?
4) What are the exciting future research frontiers?

Alan King (Mathematical Sciences Department, IBM Thomas J. Watson Research Center)  kingaj@us.ibm.com  http://www.research.ibm.com/people/k/kingaj/

Optimization Models for the Financial Valuation of Supply Chain Risks     Slides:    pdf

The valuation of financial options, as is well known, is based on the recognition that an option's payouts can be replicated by a trading program that "manufactures" an equivalent payout distribution from an initial infusion of cash equal to the value of the option. One may in fact develop a quite satisfactory and practical theory of options pricing based on an optimization formulation of this replication model as a multiperiod stochastic production-inventory problem. This talk will explore how this optimization-based valuation approach may be extended to the valuation and management of risky supply chain contracts.

Moshe Kress (Center for Military Analyses, Haifa, Israel)  kress@ie.technion.ac.il

Optimizing Supply Chains in Military Operations    Slides:    html    pdf    ppt

During military operations, supplies such as fuel, ammunition and food are delivered to the theater of operations by a large-scale supply chain. This chain originates at the strategic level (e.g., depots, arsenals and home bases) and terminates at the tactical level (e.g., battalions). There are some fundamental differences between a business supply chain and its military counterpart. The main differences are in the underlying logistic network, the characterization of uncertainty and the measures of effectiveness and efficiency that are utilized. In this talk we present the main features of a military supply chain during a military operation and discuss some typical stochastic optimization modeling issues.

Robert C. Leachman (Department of Inudstrial Engineering and Operations Research, University of California at Berkeley)

Scheduling Dedicated Lithography Equipment     Slides:    html    pdf    ppt

A common strategy to achieve a successful and stable process for the fabrication of advanced digital semiconductors involves what is termed the dedication of lithography equipment. In order to maximize registration of multiple mask layers, the same machine may be required to be used for the exposure of critical layers. Moreover, only certain machines matched to a given machine may be used at other layers. This strategy poses a considerable challenge for scheduling lot releases. Lots must be assigned to machines before release, and, once released, cannot be re-assigned. It is difficult to balance utilization of lithography equipment, resulting in situations where some machines have large queues yet others are idle.

A scheduling system based on integer goal programming has been developed and implemented to cope with this challenge. Multiple objective functions for minimizing machine overloads and balancing equipment workloads are optimized. Implementation in one advanced fabrication facility reduced average queue times at lithography by about 40%, resulting in product flow time reduction of about 36 hours.

Warren B. Powell (Director, CASTLE Laboratory, Department of Operations Research and Financial Engineering, Princeton University)  powell@princeton.edu  http://www.castlelab.princeton.edu

Adaptive learning algorithms for stochastic resource allocation     Slides:    pdf

One of the challenges arising in supply chain management is the need to make decisions before all the information is in. This arises in freight transportation when companies have to move equipment to handle the needs of shippers before their demands become known. The same problem is faced by manufacturers who have to plan what products to make before the size of a market is known, or by the same companies who have to decide how much product to ship to a location. In some cases, a company might want to provide a discount if a customer books an order in advance, in which case the company needs to determine the appropriate size of the discount. In addition to the uncertainty, most real problems are characterized by different types of resources or products and substitutable demands.

We propose an algorithmic strategy based on approximate dynamic programming which replaces the value function with a special class of functional approximations. The method requires using an unusual dynamic programming recursion, and easily handles very large scale problems. The strategy is provably optimal for some special cases, and appears to outperform provably optimal algorithms for more general cases because it has a much faster rate of convergence. It also has the nice property of naturally producing integer solutions.

The talk will describe problems where the technique is being put into production, and outline some remaining research challenges.

Tianbing Qian (Motorola)  Tianbing.Qian@motorola.com

Enterprise Capacity Planning at Motorola Semiconductors (for Poster Session)

Sales & Operations Planning (S&OP) is the business process in semiconductor industry where major capital decisions are made regarding capacity deployment and demand fulfillment for the near to mid-term horizon. With recent trends of semiconductor manufacturing shifting towards offshore foundries and subcontractors, the enterprise level S&OP problem becomes even more global and dynamic. This talk will present modeling issues unique to the semiconductor S&OP problem, describe a large-scale S&OP implementation at Motorola, and discuss challenges facing today's enterprise supply chain planning systems.

H. Edwin Romeijn (Department of Industrial and Systems Engineering, University of Florida)  romeijn@ise.ufl.edu  http://www.ise.ufl.edu/romeijn/

Assignment problems in supply chain optimization (for Poster Session)

We consider logistics problems in a network consisting of retailers and suppliers, where we are interested in finding a minimum cost production, inventory, and transportation plan. We impose a so-called single-sourcing structure on the solution, which means that each retailer is assigned to a single supplier. We can often formulate the constrained problem as a problem with assignment decision variables only, and a nonlinear objective function. We study greedy heuristics as well as a column generation approach to solving the problem to optimality. We pay particular attention to the pricing problems associated with the latter approach. These problems are also of independent interest in settings where suppliers have demand choice flexibility, and the goal is to maximize profit rather than minimize cost.

Robin Roundy (School of Operations Research and Industrial Engineering, Cornell University)  robin@orie.cornell.edu

Strategic Capacity Planning for the Semiconductor Industry: Current Industrial Practice and New Directions

Joint work with Metin Cakanyldirim, and Woonghee Tim Huh.

Semiconductor manufacturing is one of the world's leading industries. Capacity planning decisions are crucial and challenging. A modern fab costs \$1.5-2 billion. About 65% of that is for machine tools. The semiconductor industry is increasingly effected by short and shrinking product life cycles, by fierce competition, by unpredictable and volatile markets, and by rapid changes in technology. Yet this industry relies on machine tools that have very long procurement lead times and are extremely expensive.

We will present an overview of a long-range research effort designed to provide the semiconductor industry with useful tools for optimizing capacity plans in a stochastic environment. We will review current business practices in strategic capacity planning in the semiconductor industry, and will discuss model-based evaluations of some of those practices. We will present new methods for statistically modeling and quantifying the errors in demand forecasts. We will present a novel approach for modeling demand for multi-dimensional capacity planning problems, and discuss the practical and algorithmic implications of different ways of modeling stockouts. We present efficient algorithms for provably solvable versions of the strategic capacity planning problems, and summarize the current status of research on versions that are not provably solvable.

Jeremy F. Shapiro (Slim Technologies)  jshapiro@slimcorp.com

Business Process Expansion to Exploit Optimization Models for Supply Chain Planning     Slides:    html     pdf    ppt

In a recent survey of leading manufacturers about supply chain planning systems, AMR Research found that success with these systems is more dependent on effective change management than technology. In this talk, we discuss aspects of change management, or business process expansion, that need to be better understood if supply chain managers are to more fully exploit optimization models in achieving competitive advantage. The topics to be discussed include:

• Differentiating transactional IT from analytical IT Designing and developing software to construct the supply chain decision database from an ERP database

• Understanding and modifying behavioral realities underlying organizational decision-making

• Reconciling exploration and exploitation in the development and use of optimization modeling systems

• Implementing business process expansion to achieve tactical supply chain planning supported by optimization models

David Simchi-Levi (Engineering Systems Massachusetts Institute of Technology)  dslevi@MIT.EDU  http://slevi1.mit.edu/~levi/

Coordinating Inventory Control and Pricing Strategies with Random Demand and Fixed Ordering Cost

We analyze a single product, periodic review model in which pricing and production/inventory decisions are made simultaneously. Demands in different periods are random variables that are independent of each other and their distributions depend on the product price. Pricing and ordering decisions are made at the beginning of each period and all shortages are backlogged. Ordering cost includes both a fixed cost and a variable cost proportional to the amount ordered. We consider both the finite and infinite horizon models. In the finite horizon model the objective is to find an inventory policy and a pricing strategy maximizing expected discounted profit over the finite horizon. In the infinite horizon the objective is to maximize expected discounted, or expected average profit. For the finite horizon case, we show, by employing the classical k-convexity concept, that an (s,S,p) policy is optimal when the demand functions are additive. In such a policy, the period inventory is managed based on the celebrated (s,S) policy and price is determined based on the inventory position at the beginning of each period. For the model with more general demand functions, we show that an (s,S,p) policy is not necessarily optimal. We introduce a new concept, the symmetric k-convex functions, and apply it to provide a characterization of the optimal policy. Surprisingly, in the infinite horizon case, the concept of symmetric k-convex functions allows us to show that a stationary (s,S,p) policy is optimal for both discounted and average profit models even for general demand functions.

Jayashankar M. Swaminathan (University of North Carolina, Chapel Hill)  msj@unc.edu

Coordinating Prices on Traditional and Internet Channels

The Internet has provided a new avenue to conduct business for both manufacturers and retailers. Two important decisions that need to be considered are - (1) the degree of independence of the new channel and (2) the pricing of goods across the two channels. In this talk, I will first introduce analysis of a monopolistic retailer and study alternative pricing strategies under different degrees of autonomy for the Internet operations using a micro level consumer utility model for demand generation. Next, I will discuss results considering the same issue from a manufacturer's standpoint who has an existing retail channel. Finally, I will discuss theoretical bounds on the performance using a macro level demand model and provide insights on the pricing by pure and hybrid retailers (having both traditional and internet channel) under competition.

Sridhar Tayur (Graduate School of Industrial Administration (GSIA), Carnegie Mellon University (CMU))  stayur@cyrus.andrew.cmu.edu  http://www.gsia.cmu.edu/andrew/stayur/

From 'Academic Building Blocks' to Enterprise Optimization in Supply Chain Management

Imbedding Optimization within the workflow at an enterprise level is the current challenge in supply chain management. This is particularly difficult not only because of the data and user challenges, but also because the available intellectual property in OR/MS literature is in 'simple building blocks' to begin with. This talk will discuss one approach to bridging this very wide gap.

Laurence A. Wolsey (CORE)  wolsey@core.ucl.ac.be

Solving Multi-Item Lot-Sizing Problems with an MIP Solver using Classification and Reformulation

Based on research on the polyhedral structure of lot-sizing models over the last twenty years, there is a nontrivial fraction of practical lot-sizing problems that can now be solved by nonspecialists just by taking an appropriate a priori reformulation of the problem, and then feeding the resulting formulation into a commercial mixed integer programming solver.

This approach is based on the fact that many multi-item problems decompose naturally into a set of single-item problems with linking constraints, and that there is now a large body of knowledge about single-item problems. To put this knowledge to use, we propose a classification of lot-sizing problems (in large part single-item), and then indicate in a set of Tables what is known about a particular problem class, and how useful it might be. Specifically we indicate for each class i) whether a tight extended formulation is known, and its size, ii) whether one or more families of valid inequalities are known defining the convex hull of solutions, and the complexity of the corresponding separation algorithms, and iii) the complexity of the corresponding optimization algorithms (which would be useful if a column generation or Lagrangian relaxation approach was envisaged).

Three distinct multi-item lot-sizing instances are then presented to demonstrate the approach, and comparative computational results are presented.

Slides for "Classification and Reformulation: a Direct Way to Tackle Multi-Item Lot-Sizing Problems:     pdf    ps

S. David Wu (Department of Industrial and Systems Engineering, Lehigh University)  david.wu@lehigh.edu  http://www.lehigh.edu/~sdw1/

Managing High-Tech Capacity via Reservation Contracts*    Slides:    html    pdf    pps    ppt     Paper:   pdf

Note: Other related papers can be found on my web site http://www.Lehigh.edu/~sdw1/ under "Papers."

We study capacity reservation contracts in a high-tech manufacturing environment. Motivated by our work at a major telecommunications device manufacturer in the U.S., we consider contracts that allow the manufacturer (the supplier) to share the risk of capacity expansion with her OEM customers (the buyer). This is important, as the capacity cost is enormous in this industry, while the market demand highly volatile. We focus on short-life-cycle, make-to-order products under stochastic demand. The supplier and the buyer are partners who enter a design-win" agreement to develop the product, and who share demand information. The supplier would expand her capacity in any case, but reservation may encourage her to expand more aggressively. To reserve capacity, the buyer pays a fee upfront while (a pre-specified portion of) the fee is deductible from the order payment. As capacity expansion demonstrates diseconomy of scale in this context, we assume convex capacity costs. We first analyze the players' incentives in a one-supplier, one-buyer setting. We show that as the buyer's revenue margin decreases, the supplier faces a sequence of three profit scenarios with decreasing desirability. We examine the effects of market size and demand variability to the contract conditions, and show that it is the demand variability that affects the reservation fee, and that the convex cost assumption leads to different insights than the linear cost cases in the literature. We generalize the analysis to a one-supplier, two-buyer system where the buyers compete for capacity in a Nash game. We show that the game is sensitive to the reservation fee, and the supplier could dictate whether the buyers play a fixed capacity game (FCG), or a variable capacity game (VCG). We discuss buyer behaviors and their optimal strategy under both situations. We propose a number of channel coordination contracts, and discuss additional cases when the supplier has the option not to comply with the contract, and when the buyer's (in this case, a contract manufacturer) market size is only partially known. I will conclude the talk by summarizing insights useful for high-tech capacity management, and relevance to recent trends in contract manufacturing.

*(joint work with Murat Erkoc).

Dr. S. David Wu is Lee A. Iacocca Professor and Chairman of the Department of Industrial and Systems Engineering at Lehigh University. He is also founder and co-Director of the Manufacturing Logistics Institute (MLI), a research institute created in 1995 to promote the integration between academic and industrial research in Logistics. In 1999, Professor Wu created the Global Manufacturing Logistics Fellows program in partnership with the Wharton School at the University of Pennsylvania. With significant funding from the National Science Foundation, the fellows program forms global alliance with some 14 international institutions throughout Europe, Asia/Pacific and the Mid-East. Professor Wu.s research is in the areas of supply chain coordination; focus on combining the insights from game theoretic and optimization models. He has published more than 80 articles in this and related areas. He is currently co-editing the Handbook of Supply Chain Analysis in the eBusiness Era (Kluwer Academic Press) with David Simchi-Levi (MIT) and Max Shen (Florida). Professor Wu.s research has been supported by NSF, DOD, Sandia National Laboratory and industrial firms such as Agere Systems, Lucent Technologies, Ford, Unisys, and Bethlehem Steel. He currently serves on the editorial boards of IEEE Transactions on Robotics and Automation, IIE Transactions, and Journal of Manufacturing Systems. He holds an M.S. and Ph.D. degrees in Industrial Engineering from the Pennsylvania State University (1987). In 1995-1996, he was a visiting professor at the University of Pennsylvania.

Paul Zipkin (The T. Austin Finch, Sr. Professor of Business, The Fuqua School of Business, Duke University)  Paul.Zipkin@Duke.Edu

A Series System with Returns: Stationary Analysis

This paper analyzes a series inventory system with stationary costs and stochastic demand over an infinite horizon. A distinctive feature is that demand can be negative, representing returns from customers, as well as zero or positive. We observe that, as in a system with nonnegative demand, a stationary echelon base-stock policy is optimal here. However, the steady-state behavior of the system under such a policy is different from that in systems with nonnegative demands. We present an exact procedure and several approximations for computing the operating characteristics and system costs for any stationary echelon base-stock policy, and also describe an algorithm for computing a good policy. Finally, we describe how to extend the analysis to the case where returns occur at multiple stages instead of just at the stage closest to demand. (This is joint work with G. DeCroix and J. Song.)

Material from Talks

Optimization, September 1, 2002 - June 30, 2003
 Connect With Us: Go
 © 2015 Regents of the University of Minnesota. All rights reserved. The University of Minnesota is an equal opportunity educator and employer Last modified on October 06, 2011 Twin Cities Campus:   Parking & Transportation   Maps & Directions Directories   Contact U of M   Privacy