Optimization,
September 1, 2002 - June 30, 2003
Talk
Abstracts:
September
23-27, 2002
Material
from Talks
Dan
Adelman
(The University of Chicago, Graduate School
of Business) dan.adelman@gsb.uchicago.edu
http://gsbwww.uchicago.edu/fac/daniel.adelman/research/
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
