Optimizing mid-term and long-term planning - including supply network
planning and detailed scheduling - promises tremendous benefits, including:
- Lower inventories
- Reduced production and transportation costs
- Increased manufacturing throughput
- Higher levels of service
The results are improved product margins
and a better return on assets. The tasks and obstacles that line the path
to this payoff are listed in Figure 1.
When performing supply chain planning (SCP),
the IT staff or the supply chain planner is pressed to find the most accurate
and fastest view of the supply chain without overwhelming IT resources.
Relief comes in the form of SAP's Advanced Planner and Optimizer (SAP
APO), which is at the heart of SAP's Supply Chain Management (SCM) solutions.¹
The APO has always included modules that are integrated to enhance optimization,
but the most recent advances in Release 3.0 - developments such as liveCache
and new optimization libraries - offer your users an even bigger payoff
in their supply chain planning, scheduling, and analysis.
This article takes you through the benefits
of supply chain planning with SAP APO, and then goes in-depth into the
ways that supply chain planners, IT departments, and even the operations
research (OR) community generally can make the most of the R/3 supply
chain process and the new open structure of SAP APO.
With these specific needs in mind, this
article discusses the developments in SAP's optimization solution, SAP
update costs and pricing
||Any supply chain optimizer should consider in its objective
the following functions: storage costs, production costs, transportation
costs, and sales profits. These factors should be derived from actual
business pricing data, so that changes in the supplier's actual price
list are automatically reflected.
model the supply chain
||Modeling the supply chain on a reasonable level of detail
may generate very large optimization problems. You need to be able
to avoid these problems with the right solution, for example: global
optimization on a rough-cut model for mid-term planning, versus local
optimization on a detailed model for short-term planning.
|Offer a generic
||The optimizer should meet the needs of your particular
industry. At the same time, it should also provide a standard software
approach that can be configured to help you solve the supply chain
scenarios for various business areas (e.g., high-tech, process industry,
etc.), rather than individually developed optimizers tailored only
to a specific area.
||The system must be able to integrate different optimization
methods on different planning levels - operational, tactical, and
strategic - each automatically updated from the execution systems.
(For descriptions of these planning levels, see the sidebar on the
|Allow for scalability
You need solutions of a competitive quality that can successfully
consider various problem sizes and allowed runtimes. There is an
inevitable tradeoff between the quality of the solution and the
used runtime. Scalability means that you achieve a balance, allowing
for "graceful degradation" of the quality of the solution in exchange
- Lowering the runtime given a fixed problem
- Increasing the problem size given a fixed runtime (for example,
the 5 CPU hours during the night break)
Alternatively, you may expect significant improvements in the solution
quality by scaling up the runtime or the number of processors.
||Tasks and Challenges of Supply Chain Optimization
SAP's Advances in Optimization
With the increases in processing that have made possible initiatives
such as mySAP.com industry solutions, SAP now has the technology to help
master the necessary basic ingredients for truly optimizing supply chain
- SAP APO now enables transactional ERP systems in the supply chain
to be interconnected, in order to accurately and easily reflect costs
- SAP APO now has several gigabytes of main memory, which allows you
to adequately model the supply chain much faster.
- SAP APO now has advanced optimization libraries - e.g., fast linear
programming (LP) solvers with polynomial time complexity using interior
point methods and efficient constraint propagation for scheduling problems.
They can be used as basic building blocks for tackling the need for
a generic solution.
SAP APO delivers different optimization
tools for different SCP problems. These tools include:
- Genetic Algorithms - e.g., in the Product Planning/Detailed Scheduling
- Constraint Programming - e.g., in the Product Planning/Detailed Scheduling
- Mixed Integer Linear Programming - e.g., in the SNP module
- Tabu Search - e.g., in the Transportation Planning/Vehicle Scheduling
(TP/VS) module, as of APO 3.0
Because the optimizer server can now use
several gigaflops of CPU power in a multiprocessor architecture, the server
can enable computation of sophisticated optimization strategies. In the
following sections, we cover how SAP APO is meeting the challenges of
accuracy, generic solutions, seamless integration, and scalability for
Dual Server for Accurate Supply Chain Modeling
Of course, accurately modeling the complete supply chain often requires
a huge amount of information. SAP is now capitalizing on technologies,
such as 64-bit generation processors, that already make it possible to
maintain almost unlimited amounts of data using several gigabytes of main
With this technology in mind, SAP created
liveCache - a newly developed object database in main memory, designed
by SAP especially for planning problems that represent vast amounts of
relevant data: demand, supply, capacity profiles, and activities and their
time constraints, among others.
For example, take the data involved in
planning the actual week for a rescheduling run on the operational level.
The optimizer reads the planning problem out of liveCache and solves this
problem on a separate server.
SAP liveCache technology is already at
work in modules such as the SNP, PP/DS, ATP, and TP/VS modules. Customers
who implemented these modules are now using liveCache, and include Fischerwerke
and Wacker Siltronic AG of Germany.
This separation has two benefits:
- SAP APO performs better. The performance of the liveCache server
is not reduced during the CPU time that is consumed in the optimization
- SAP APO is more flexible. You, as the supply chain planner, have
some choices as to which optimization model you use. SAP APO's internal
model can use the liveCache model or it can use another optimization
One difficulty for many ERP systems is
data transfer. In most standard ERP systems, you need fast access to a
portion of a complex network for successful data transfer. liveCache technology
solves this problem, since it comprises object-oriented data structures
in main memory that are especially tailored for planning problems.
Figure 2 depicts the architecture
of the optimizer in SAP APO. The Core Model, or internal data model, is
the central component. The task of the model generator is to transfer
a selected planning problem from liveCache into the Core Model of the
||SAP APO Optimizer Model
|Supply Chain Planning: Three Levels
In this article, we discuss three levels of supply chain planning.
SAP has different modules and solutions that address each specifically,
all incorporated in the SAP APO. The levels are:
- Operational Level. APO Module: Detailed Scheduling (DS).
At this level, you monitor the short-term, day-to-day operations,
focusing especially on exceptions in supply chain operations.
The optimizer schedules orders according to manufacturing constraints
that handle complex manufacturing environments with alternative
routings and resources, secondary resources, and multistage production.
- Tactical Level. APO Modules: SNP, Capable to Match (CTM).
At this level, you monitor mid-term planning scenarios for the
global supply chain, from distribution centers to plants and suppliers.
The optimizer automatically processes bills of materials while
taking capacities into account, and optimizes transportation costs,
production costs, storage costs, and revenues for demand. The
sheer complexity of this global view is mastered by a rough-cut
model that aggregates the time in buckets (e.g., day or week)
and products and resources in families.
- Strategic Level. APO Module: Network Design. This stage
involves long-term planning for the supply chain. It is at this
level that you graphically construct and maintain a model of the
entire supply chain. You also analyze the optimal use of different
resources in your supply chain based on a long-term view (for
example, closing or creating distribution centers or plants).
Dual Modeling for Optimization Across Supply Chain
SAP APO provides a suite of special tools
tailored for all blocks of the SCP cube illustrated in Figure 3.
SAP APO's modeling approach consists of two types of planning: aggregated
planning based on LP solvers for a more global view of the supply chain
(for long- and mid-term planning), and detailed planning based on scheduling
algorithms to ensure accuracy at a finer level of analysis (for short-term
||Classification of Planning Problems
Aggregation As a Strategy for Long-Term and Mid-Term Planning
On the strategic and tactical levels (where mid- and long-term planning
occurs), SAP APO performs aggregated planning to provide a more global
view of the entire supply chain. For mid-term planning, this aggregation
provides an adequate level of detail, depending on the degree of uncertainty
in the planning data. Factors to consider when analyzing the level of
uncertainty in planning data include new orders, order cancellation, forecast
errors, and market changes. Mid-term and long-term planning problems may
include various constraints - for example, linear constraints such as:
- Due-date deadlines
- Maximum delay
- Shelf life (maximal range of coverage)
- Storage and handling capacity
- Capacity calendar for resourcesM
- Break calendar, including work stoppage, holidays, etc.
More difficult constraints are discrete
constraints such as:
- Minimal/discrete lot sizes
- Full truck load
- Discount rates (piecewise linear cost functions)
Supply chain planning problems that involve
only linear constraints can be reliably solved to optimality using the
LP solver of ILOG CPLEX. However, SCP problems that include the additional
constraints of the second group (discrete constraints) are much harder
to solve. Problems with discrete constraints are modeled as mixed integer
linear problems (MILP) and solved via ILOG CPLEX's branch-and-bound. In
order to achieve best solution quality in the given runtime, SAP has developed
heuristics that take the economical semantic of the decision variables
Scheduling for Detailed, Short-Term Planning
On the operational level, SAP APO performs detailed supply chain planning.
All the activities in the supply chain (e.g., transportation, production
lots, etc.) are scheduled precisely at a particular time on specific individual
resources, such as production resources, transportation resources, or
even warehouse capacity. With SAP APO, several supply chain planners can
work simultaneously on one plan, each focusing on a small section of the
larger supply chain.
Scheduling problems are modeled in the
most generic way possible through what is called Multi-mode Resource Constraint
Project Scheduling Problems with maximum and minimum time lags (MRCPSP/max).
Maximum time constraints include:
- Deadlines, shelf life, and expiration dates
- Storage capacities
- Sequence-dependent setup times
- Processing interruptions by breaks
- Objectives, such as minimizing setup times, setup costs, resource
costs, earliness, and due-date delays
APO Scheduling Approaches
The suite of algorithms in the current SAP APO uses the following three
- Constraint Programming (CP). The CP scheduler is the most
generic scheduler. It is based on the ILOG libraries and uses dynamic
constraint propagation at every optimization step.
- Genetic Algorithm (GA). The GA scheduler is based on an evolutionary
approach. The genetic representation of the supply chain comprises control
information, which is used by a fast scheduler for generating a new
supply chain solution.
- Repair Algorithm (RA). This scheduler is based on solving
a resource relaxation (i.e., respecting only time constraints and assuming
infinite resource capacity), which can be done in polynomial time. The
resource capacity constraint violation is solved by adding precedence
constraints between the conflicting resource requirements to dynamically
solve over-capacity conflicts and then, again, calling the solver for
the resource relaxation until no capacity overload remains.
However, the relative performance of these
alternative optimizers for detailed scheduling may depend on the individual
planning scenario. Therefore the supply chain planner, along with the
manager, may select the most appropriate algorithm after some experimental
studies. In SAP APO, supply chain planners can construct their own objective
function by combining the previous objectives with priorities (linear
To seamlessly integrate the different levels of the supply chain, the
aggregated plan must be disaggregated for short-term planning on the operational
Scheduling algorithms determine the resource
allocation out of a set of alternative resources (disaggregation of resource
families) and precise time scheduling (disaggregation of time buckets).
SAP APO provides a generic framework, which allows it to integrate several
scheduling algorithms based on CP, GA, or RA approaches. The planner may
select the most appropriate scheduler or may even combine them using a
script (e.g., first optimize the bottleneck resources with the GA scheduler
and then complete this schedule using the CP scheduler). Moreover, this
architecture is open, which allows us to integrate other optimizers for
Time Decomposition: This method breaks the large-scale scheduling
problem into a series of smaller-scale planning problems consisting
of smaller overlapping time frames. Imagine a moving planning window,
which slowly "glides" over your Gantt chart. In this way, SAP APO
solves smaller problems one by one, instead of solving the complete,
large-scale planning problem all at once, as shown in Figure
Resource Decomposition: The idea behind resource decomposition
is that it involves considering a planning window not defined by
a time frame but by a set of resources. As in time decomposition,
the set of activities outside the window is fixed. The challenge
of this decomposition technique is to define the set of resources
for each planning window in a sensible way. The objective is a decomposition
in loosely connected parts.
Product Decomposition: The idea behind product decomposition
is to define the planning window by the material flow: consider
all resources (e.g., production and transportation), intermediate
materials, and activities that could be used to produce a given
product. The challenge is to combine material flows with many common
resources. In this sense, it is similar to resource decomposition.
However, in product decomposition, activities using the same resources
but belonging to different material flows may not be rescheduled
at the same optimization step.
Priority Decomposition: The idea behind priority decomposition
is to decompose the problem into the set of activities that belong
to different priorities for the customer demands. Planners may use
this technique for optimizing first the activities of the highest
priority and then fixing them before optimizing the next priority
Bottleneck Relaxation: This technique is used for business
scenarios with a large-scale scheduling problem. The most important
(or expensive) resources create the bottleneck of the scheduling
problem. Therefore it may be a good strategy to first find a high-quality
schedule for the bottlenecked resources, and then relax the capacity
constraints on the non-bottleneck resources (i.e., plan them with
infinite capacity). In a second step, this schedule may be enhanced
to complete the schedule while fixing the optimized sequence of
the activities on the bottleneck resources. With SAP APO, this technique
is used for campaign optimization and block scheduling (see Figure
5). The blocks (e.g., production lot size for a certain product)
or campaigns (e.g., sequence of lot sizes) are built by focusing
on the bottleneck production stage.
||Time Decomposition Model
Complete optimizing procedures guarantee that the global optimum is
found with exponential time complexity. Because it will lead to unacceptable
runtime, however, such a guarantee is obviously useless for practical
purposes. Even reducing the quality grade requirement to 5 percent below
the optimum generally cannot be guaranteed. Here are some factors to consider,
depending on the kind of scaling needs you have, and how SAP APO addresses
- Scaling in quality - runtime versus optimization quality. If more
time is used for optimizing, then a higher-quality grade can be expected.
SAP APO's decomposition strategies give you flexibility when adjusting
procedures to fit the needs of the user.
- Scaling in problem size - runtime versus problem size. Time expenditure
generally increases in proportion to the problem size. In the case of
large optimizing problems, even algorithms with quadratic time complexity
can be too time consuming. The decomposition strategies in SAP APO have
a time complexity of O (n log n) using a constant window size, and can
thus solve large planning problems.
SAP APO provides a generic framework combining
several decomposition techniques (including time, resource, product, and
priority) and several basic optimizers (LP solver, CP scheduler, GA scheduler,
and RA scheduler). Decomposition focuses the optimization activities on
smaller problems within the larger planning problem. However, you must
be aware of the level of optimization and the size of the problem: fine
decomposition in small subproblems (such as local optimization) requires
low runtime, but runs the danger of a lower-quality local optimization.
On the other hand, coarse decomposition in large subproblems may cause
unacceptable runtime. By using the appropriate decomposition technique,
SAP APO can make it possible to seamlessly close the gap between local
improvement heuristics and global optimization.
When trying to improve on the current
solution, local improvement heuristics consider only the direct local
neighborhood (i.e., the valid solutions for a specific optimization problem).
This search may be trapped by local optima. Decomposition techniques can
scale up the neighborhood (i.e., increase the decomposition width). SAP
APO enables tuning of the optimal decomposition width. The methods of
decomposition (see the sidebar on the facing page) illustrate the various
ways SAP APO achieves a seamless transition from heuristics to global
Using Decomposition to Reduce Supply Chain Complexity
Even with SAP APO, there are limits to what a supply chain optimization
can do; one is the complexity of the supply chain. A supply chain that
is unnecessarily complex will extend the calculation time, or will never
find a feasible solution and lead to the problems discussed earlier in
this article. However, through decomposition, you can reduce the complexity
to match your resources.
The Two-Step Process of Decomposition
There are two stages to solving an optimization problem through decomposition.
First, generate a feasible solution by combining various decomposition
techniques with different optimizers in SAP APO. The architecture even
makes it possible to start several optimizers per planning window and
to use the best result in each case. Then, take further steps to improve
For mastering both cases, SAP's generic
architecture makes it possible to combine different decomposition strategies
with different optimizers. For example, we could first generate a solution
by choosing bottleneck relaxation as the decomposition method, and then
using the genetic algorithm as the optimizer. Then, at the second stage,
to improve on this solution, you could select time decomposition, using
constraint programming as the optimizer.
Taking Decomposition Further
You could even take this a step further and divide the second stage
into two phases: first optimize the customer service level (to minimize
due date violations), then minimize earliness (storage), for a result
that produces goods as late as possible without an increase in due date
SAP's architecture offers parallelization
that is seamlessly integrated into the decomposition strategies, so that
it is possible to start several optimizers, each with different objectives
per planning window, and run them in parallel using the computing power
of a multi-processor system.
Planning Your IT Resources for Maximum Supply Chain
With all the benefits that SAP APO has to offer, supply chain optimization
can still be limited by the available computing power. Less computing
power is often compensated for by more severe decomposition, which may
decrease the quality of the generated solutions. There may be a number
of reasons for limited computing power, and SAP APO offers you the flexibility
to address some of these causes at the source.
The problem may be due to multiple users
working in parallel. This problem is solved in SAP APO by a three-tier
client/server architecture configurable for multiprocessor servers.
Separating the application servers also
can alleviate this problem. liveCache and SAP APO may run on separate
application servers. This architecture is recommended for modeling a large
SCP problem, since both require high-level computing power and high main-memory
capacity. It is even possible to configure the system with several optimizer
servers or with multiprocessor architectures. On the other hand, smaller
companies can also use just one application server for both liveCache
and SAP APO.
Both the optimization algorithms and the
decomposition techniques offer a lot of potential in parallelization.
With the multiuser capability of SAP APO, the supply chain planner may
parallelize the optimization manually by using decomposition techniques.
Optimizing in a parallel session will separate parts of the supply chain,
and thus reduce the load on the computing resources.
In SAP APO Release 3.0, the inherent parallelization
of multiple agents may be used on a multiprocessor server. This approach
is integrated in the decomposition techniques. For each decomposed planning
problem, different agents may run in parallel. These agents may differ
in which basic optimizer (GA, CP, and RA) or objective function is used,
each doubling the focus on one single criterion of the given multicriteria
objective defined by the user (e.g., one function doubles the setup costs,
the other doubles the delay costs). After each optimization run, the user
may select one solution chosen from a set of solutions that have similar
overall quality but differ in the single criterion.
Conclusion - And An Invitation
SAP APO is a generic solution for optimizing the supply chain configurable
to master specific business scenarios. Because of its open architecture,
it is open to future enhancements concerning model functionality, improved
optimization algorithms (libraries), and higher degrees of parallelization.
The only limits of this algorithmic approach are the available computing
power and the complexity of the supply chain.
In order to benefit from the potential
of parallelization, SAP APO is designed for multiprocessor architectures.
However the user should not expect this to be the "silver bullet" that
solves all problems. Supply chain planners must still work carefully to
avoid too complex a supply chain calculation - which would unavoidably
result in poor optimization performance. This overview provides the groundwork
to better plan your own supply chain and take advantage of the new features
in SAP APO.
One additional note on what you can expect of SAP APO in the future:
because it has an open architecture, we also offer an invitation to the
OR community to contribute to truly optimizing the supply chain to meet
your optimization needs. In the future, you can look for announcements
regarding the APO Extension Workbench (APX). This tool will allow the
OR community to create and use customer-specific optimization algorithms
that may be integrated with SAP APO.
|¹ The first customer
shipment of SAP APO 3.0 was May 2000,
with general availability at the end
of September 2000.
|² For example, planners
may want to set priorities to meet different
objectives. If you must meet all due
dates, the supply chain must factor in
smaller lot sizes, which, of course,
will lead to higher production costs.
|³ For example, in
SNP you will have a kind of rough planning
phase, such as simply matching supply
and demand. This is basically the dispatching
of demand to different plants, which
is the aggregated plan. To effectively
detail scheduling of each of these various
plants, this plan then has to be disaggregated
for supply chain optimization.
Dr. Heinrich Braun has a degree in computer science and a doctoral degree
from the University of Karlsruhe. Dr. Braun joined SAP AG in 1996, and
in 1997 became project lead of the development team for SAP APO's optimization
algorithms. Since January 2000, he has worked as the development manager
for optimization algorithms in SAP APO.
Claus Grunewald has worked with SAP since 1996 in logistics development.
Mr. Grunewald is a product manager for SAP APO and is currently involved
with strategic business development for supply chain management.