jump to navigation

Supply Chain Planning Algorithms December 12, 2007

Posted by Jeff in Technology.
Tags: , , , , ,


Supply chain planning is a critical task in operations management.  On the one hand, it algorithmically solves immediate problems of finding availability schedules, sourcing decisions and resource allocations to produce a plan that meets goals in an effective manner. But it also provides insight into the trade-offs of different factors, constraints and rules.

However, supply chain planning means different things under different situations.  In this post, we try to classify types of supply chain planning problems, address the modeling issues, and provide background regarding the algorithms used.

In the enterprise software paradigm, the supply chain planning element often goes under the name Advanced Planning and Scheduling (APS) in order to distinguish it from simpler approaches such as those based on simple demand accrual as used in MRP.  An APS module may help analyze the implications of alternative decisions and perform what-ifs.


Models and data are two very important elements of supply chain optimization, and a plan’s usefulness greatly depends on the quality of both.  Here are a set of guidelines from a recent Supply Chain Digest article on “Rules for Supply Chain Optimization Technology“:

  1. State Quantified and Measurable Objectives: For example, use an objective such as “minimize the sum of the daily fixed cost of assets”.
  2. Faithfully Represent Required Logistics Processes in Models: It is easy to make mistakes in the model such that it doesn’t represent the way things work in the real world.
  3. Explicitly Consider Variability: Too often, models associated with supply chain and logistics optimization either assume that there is no variability or assume that using average values are adequate.
  4. Ensure that Data is Accurate, Timely, and Comprehensive: If the data is not accurate and/or it is not received in time to include it in the optimization, the resulting solutions will obviously be suspect.

For example, in semiconductor operations, models must capture a number of important complexities including:

  • binning
  • downgrading
  • short product cycle times
  • customer requirements on part sourcing

Several of the traditional supply chain engines do not handle these issues well.  For instance, a humorous story that our staff has heard is that one time a major supply chain vendor visited a fabless company.  When the vendor was presented with the problem of binning, they finally decided that this was a feature they would have to model as “scrapping”.

The structure and level of detail in the planning model determines the type of planning algorithm to use.  In this posting, we will look at several examples of plans and algorithms.

Levels of Planning

Different organizations have different ideas regarding the time period that is to be modeled and optimized, and the amount of detail.  For instance, shipment scheduling may be done on a day-by-day basis, while optimization of warehouse locations or changes in supply chain strategy may take place in a matter of quarters or years.

The following diagram (from AMR in 1998) shows the relationship between operational, tactical, and strategic planning:

Planning Levels

Models that have a detailed and long time horizon or a large number of products, decisions, and constraints can be highly complex and difficult to optimize.  For example, a planning system might require an overnight runtime in order to generate the detailed production plans for several thousand products.  Hence, scoping the level of planning is critical when applying supply chain planning to your organization.

Aggregate Planning

First of all, let’s define the basic Supply Chain Planning problem.  This discussion is largely based upon the material in “Supply Chain Management” by Chopra and Meindl.  In this case, we seek to find values for the production and overtime levels, such that the solution meets the demand and minimizes cost.  We can formally state the problem as follows:

Given a demand forecast for each period in the planning horizon, determine the production level, inventory level, and the capacity level for each period that maximizes the firm’s profit over the planning horizon.

Inventory is allowed to be carried from one period to another, but at a cost.  There is a cost of adding a worker (factory) and a cost for overtime.  The objective function is the sum of the various costs:

  • Production cost
  • Overtime cost
  • Material cost
  • Inventory carry cost
  • Hiring cost
  • Layoff cost
  • Stockout cost

Solution to Aggregate Planning

Aggregate Planning is simpler than other planning problems because it isn’t computing a specific schedule.  Hence, it can be solved with standard Linear Programming (LP) techniques.  For example, you can set up the following decision variables:

  • Production in each time period
  • Carry over in each time period.
  • Number of workers added in each time period
  • Number of workers laid off in each time period
  • Overtime hours in each time period.

The resulting spreadsheet is shown below, with the decision variables shown in gray, and the optimal solution found using the Excel Solver

There are several factors worth considering when using LP modeling:

  • Is the objective function strictly linear?  Not all models are.  Remember that a linear model cannot have step functions or products of two decision variables.
  • Are the constraints linear?  If not, sometimes an approximation can be made.

Specific Supply-Demand Matching

While the above case is typical of Sales and Operations Planning, or Demand Planning, a different kind of model is needed for Production Scheduling, or Manufacturing Planning.  In this case, we are scheduling the specific manufacturing assignments for the products, matching each unit of demand to a specific manufacturing activity.

Rather than determine the total number of production activities in a period, consider a decision to determine a detailed list of:

(manufacturing start date, demand unit matched, supply unit consumed).

The number of decision variables is therefore three times that of total number of units — perhaps in the thousands, as opposed to dozens.

There are a number of different objectives that can be used in a planning problem.  Typically, the goal is to maximize, minimize, or satisfy something, such as:

  • profits or margins
  • costs or cycle times
  • customer service  levels
  • production throughput

Since a Linear Programming runtime increases as the square of the number of decision variables, a different approach is needed.  Instead, most of the approaches to planning are derived from robotic planning as developed in the artificial intelligence literature.  The paper by Nau, Gupta, and Regli specifically draws the relationship between AI planning and manufacturing operations planning.

Search-Based Solution to Specific Matching

The common approach is to carry out a search with backtracking.  The goal is to find a particular state that simultaneously satisfies all constraints.

The approach is to assign values to the constrained variables, each such assignment limiting the range of subsequent choices.   The set of possible values for the variables is called the “state space”.  Search algorithms, as discussed below, provide hints for how to handle dead-ends, and how to determine which possible assignment should be tried first in order to reduce the search time.

Example: The Eight-Queens Problem is to place eight queens on a standard chessboard in such a way that no two queens are attacking one another.  Here is an example of a possible solution:

The most common algorithm for solving constrained search problems is a type of depth-first search called backtracking. The most primitive version of backtracking assigns variables to values in a predetermined order, at each step attempting to assign a variable to the next value that is consistent with previous assignments and the constraints. If no consistent assignment can be found for the next variable, a dead-end is reached. In this case the algorithm goes back to one of the earlier variables and tries a different value.

The obvious approach is to assign variables in some order, then go back and change assignments when a conflict is detected.  For example, we would place the first queen in the upper left, and then place the second queen in a remaining valid spot, until we either succeeded or found a conflict.  Each time that a conflict is reached, we would back up a step and move the most recently placed queen to a different location and try again.

Backtracking and Thrashing

However, the run-time complexity of this approach is exponential, and it can suffer from thrashing; that is, search in different parts of the space keeps failing for the same reasons.

One common cause of thrashing is node inconsistency, in which there is a possible step or value that will cause the search to fail, independent of any other steps or values.  For example, if there are 4 possible load sizes that can be placed on each resource (for instance, a testing machine), but for machine 5, the largest load is not possible because of a machine defect, then any plan which tries to put the largest size load on machine 5 will be a failure and the search always fails immediately no matter how good the provisional plan is for machines 1, 2, 3, and 4. This can be resolved by removing such values before search begins.

Research in the late 1970’s and early 1980’s focused on improving planning and searches by controlling backtracking.  In general, the approach of non-chronological backtracking was developed, which uses additional information about dependency of choices that are being made.  There are two particular examples:

  • Look ahead: if there is a simple-fast evaluator of a plan or subplan that can be used to determine the effects of upcoming choices, apply it to determine and restrict the set of choices.
  • Look behind: rather than always undoing the most recent decision, look back through the set of choices made, and determine which one(s) had the most impact, then backtrack to that point.  This helps avoid the situation of exploring many choices in one low-value branch when there is another branch that contains high-value choices.

Another approach developed was tabu search: this enhances the performance of a local search method by using memory structures, and once a potential solution has been determined, it is marked as “taboo” (thus the name) so that the algorithm does not visit that possibility repeatedly.

Applying Heuristics

In the above example, the search process is largely exhaustive and blind.  Typically, a given path will be followed until the search finds that it either works or doesn’t, rather than using any available additional information about the path being followed.

Heuristics are guidelines that stem from practical knowledge and can be used to direct the search so that it doesn’t explore as many non-feasible solutions.

For instance, in a supply chain planning solution where distance leads to additional costs, one might ignore all solutions that try to source products from distant locations, in favor of solutionsinvolving closer locations.

The challenge is to determine useful heuristics and balance them, which is typically done by changing weights that are assigned to the heuristics.  Several commonly used heuristics in manufacturing operations are:

  • Assign steps by critical ratio, which is an index used to determine how much a task is on schedule. A value of 1.0 is “on schedule.” A value less than 1.0 is behind, and larger than 1.0 is ahead of schedule. The critical ratio is derived by dividing the time to scheduled completion by the time expected to finish it
  • Assign steps by First-in First-out, which is to complete each task in the order that it was started or assigned.
  • Assign steps by Earliest Due Date
  • Assign steps by Shortest Processing Time First

Approach Based on Theory of Constraints

A further example of heuristics that can guide the search process stems from what is called the “Theory of Constraints“.  This theory is often described as follows:

Think of your plant not as a collection of resources existing in isolation, but as a chain of resources required to perform in tandem towards common objectives. Just as its weakest link determines the strength of a chain, only a few critical resources constrain the performance of a plant. TOC is a systematic approach to identify such constraints and maximize their effectiveness.

The heuristics, then, focus on finding the critical constraints more than they emphasis finding the next possible assignment to make in the search.

At a conceptual level, the process is as follows:

  1. Identify the constraint (the thing that prevents the organization from obtaining more of the goal)
  2. Decide how to exploit the constraint (make sure the constraint is doing things that the constraint uniquely does, and not doing things that it should not do)
  3. Subordinate all other processes to the above decision (align all other processes to the decision made above)
  4. Elevate the constraint (if required, permanently increase capacity of the constraint; “buy more”)
  5. If, as a result of these steps, the constraint has moved, return to Step 1. Don’t let inertia become the constraint.

Within the supply chain planning space, the planning engine would carry out phases of determining the most important constraint (often by increasing production through each resource until the limiting one is found), then continue to move on to the next resource.  At all times, the algorithm is maintaining a list of the critical constraints and adding production within them.

This is similar to the algorithm for solving a Linear Programming problem, but it doesn’t have the limitations of linearity imposed by such an algorithm.

A TOC-based approach is used in the planning engines of products from i2 and Thru-Put Technologies.

Repair-Based Solution to Specific Matching

Repair-based search algorithms start with an initial solution and attempt to improve it by iteratively applying repair operators.  Such algorithms can often handle large-scale problems that may be difficult for systematic search algorithms, as repair-based scheduling is a high performance scheduling technology that takes into account global optimization factors over a longer timescale, providing powerful advantages over pure dispatching approaches.

For instance, in the eight-queen problem, we would start by placing all eight queens on the board at first, and then determine where the conflicts are.

Each of these conflicts is a candidate for the next repair step.  For instance, we would move one queen to a different location, and determine if that increases or decreases the number of conflicts.  By keeping track of how many conflicts each queen participates in, and making repair moves to minimize the number of conflicts, N-queens problems that previously couldn’t be solved (i.e., N>100) became solvable in a matter of seconds even for large problems.

In the case of supply chain planning, we would start by assigning all demand units to an activity, and then determine which activities are causing conflicts.  Possible reasons for the conflict would be:

  • Demand number not met
  • Resource capacity limit exceeded

Performance Results

A series of tests were run based on actual fab data: 1850 lots with 44,600 tasks to be scheduled over 24 hour period.  This type of scheduling problem is one that occurs within many supply chain planning problems.  The data was derived from the SEMATECH 300mm process flows, with the following characteristics:

  • a representative 300mm processing flow of 244 steps utilizing 35 different equipment types, divided into 95 stages for wafer move accounting. The nominal flow cycle time was 20.6 days.
  • a modeled WIP level of 200 lots of 24 wafers each, of two different products, with an approximate steady state starts rate of 10 lots/day. The initial WIP distribution was approximately uniform along the flow.
  • 4% hot lots among both WIP and new starts
  • due dates for all lots based on nominal flow cycle time
  • a close to capacity equipment complement, i.e. 8 of the 35 equipment types had expected utilization >90%
  • unscheduled machine downtime consistent with a 5% to 40% derating value depending on equipment type, and an 8 hour MTBF – this provides a very high frequency of disruptive equipment events
  • 14 day simulation interval with 10 minute resolution
  • 244 steps using 35 different equipment types.

Move rate. The average stage move rate for each method is given in the following table. The rate for each was very close to constant over the entire 14d duration of the simulation, which lends confidence that initial conditions were not a significant perturbing factor.

Average daily stage move rate(wafer state moves/day) 18,180 15,800 16,270

RBS achieves a move rate 15% greater than CR, and 12% greater than FIFO.

Cycle time. The median and standard deviation cycle time per step is given in the following table, for all lots with >10 completed steps during the simulation timespan.

Cycle Time RBS CR FIFO
Medium cycle time per scheduled step 2.29 2.58 2.72

The reduction achieved by RBS over the dispatching methods is 11-16% in cycle time and 8-19% in standard deviation of cycle time.

Other Algorithms

Here are two other approaches:

  • Simulated Annealing:   this is a class of probabilistic algorithms for the global optimization problem, that tries to find solutions by randomly generating solutions at different points in the search tree, rather than exhaustively evaluating all of them.
  • Genetic Algorithm:  this is related to the repair-based approach, in that a partial solution is being improved on iteratively, but it takes to approach of maintaining a “population” of partial solutions and trying to combine them to form a full solution.  This is called an evolutionary computation approach in that it mimics how genetic changes occur in real populations, using ideas of mutation, selection, and crossover.

Use of Algorithms in Today’s Supply Chain Planning Software

In 2003, OR/MS conducted a survey of Supply Chain Management software.  They reported:

While the supply chain planning side of the industry seems to be hit more strongly than the supply chain execution software, a majority of the problems afflicting supply chain planning software are common in most other IT applications. Less than half of business software purchased in 2001 is up and running. Some of the problems relate to product complexity, inadequate management and technical support (internal and external), implementation lead times and flaws, poor project management, and unrealistic customer expectations that eventually result in customer dissatisfaction.

Despite all the bad news, supply chain management is still a priority for a majority of business executives who are currently operating under excessive cost containment pressures, extra capacity in their markets, and volatility of global markets affected by wars, terrorism and health threats. The scope of SCM keeps growing within a company and across enterprises, and the demand for effective planning and execution makes it extremely difficult to dismiss new technology and cling to traditional solutions over the long term.

There are no surveys that we have seen that tabulate the algorithms being used, although informal surveys indicated that the majority of the software providers are using search and backtracking techniques.  Many are built around the CPLEX engine from iLOG, which is a sophisticated LP-based solver.

The Serus supply chain planning engine is one of the few that uses a repair-based algorithm.



1. vijaya - August 3, 2009

inventory management in SCM

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: