Expand +



New Advances in SAP APO to Optimize the Supply Chain

by Dr. Heinrich Braun | SAPinsider

October 1, 2000

by Dr. Heinrich Braun, SAP AG, and Claus Gruenewald, SAP AG SAPinsider - 2000 (Volume 1), October (Issue 2)
Optimizing mid-term and long-term supply chain planning promises tremendous benefits. SAP now has the technology to help master supply chain planning, and SAP APO delivers various optimization tools. This article covers those tools, and the advances SAP has made in optimization process for supply chain planning.

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 APO.

Tasks Challenges
Automatically 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.
Accurately 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 solution 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.
Provide seamless integration 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 following page.)
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 for:

  • 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.

Figure 1 Tasks and Challenges of Supply Chain Optimization

SAP's Advances in Optimization

With the increases in processing that have made possible initiatives such as industry solutions, SAP now has the technology to help master the necessary basic ingredients for truly optimizing supply chain planning.

For example:

  • SAP APO now enables transactional ERP systems in the supply chain to be interconnected, in order to accurately and easily reflect costs and pricing.

  • 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 (PP/DS) modules

  • Constraint Programming - e.g., in the Product Planning/Detailed Scheduling (PP/DS) modules

  • 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 SCP problems.

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 memory.

     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 run.

  • 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 algorithm.

     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 optimizer.

Figure 2 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 Levels

     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 planning).

Figure 3 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 into account.

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 approaches:

  • 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 weights).²

Seamless Integration

To seamlessly integrate the different levels of the supply chain, the aggregated plan must be disaggregated for short-term planning on the operational level.³

     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 detailed scheduling.

Decomposition Techniques

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 4.

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 class.

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.

Figure 4 Time Decomposition Model

Figure 5 Bottleneck Relaxation


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 these factors:

  • 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 optimization.

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 the solution.

      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 violations.

      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 Benefit

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.

An email has been sent to:

More from SAPinsider


Please log in to post a comment.

No comments have been submitted on this article. Be the first to comment!