Optimization technology driven supply chain planning solutions are based on a synchronized holistic methodology that seeks executable and optimal solutions for the enterprise at strategic, tactical, and operational levels. This may sound complex, but what it really boils down to, is using algorithms to effectively solve the Eight Queen Problem. They are often driven by a Single Data Model to ensure that the goals set at the strategic level can be achieved by translating the enterprise objectives into action at the shop floors, distribution centers, and beyond.
Enabling Technologies
Enabling technologies supporting this comprehensive solution include:
- Advanced Linear Programming (LP) based optimization methods
- Fast optimization heuristics based on Constraint Propagation (CP)
- Unified Data Model
- Data model representation
Linear Programming Based Optimization
Strategic planning problems dealing with sourcing decisions, product mix determinations, and routing configurations can be formulated much the same way as network flow problems where discrete events are aggregated and represented as continuous flows through the network. These problems can then be solved using LP techniques.
Eyelit Technologies’ Network Optimizer (SNO) deploys this technique to formulate the initial LP model. It is possible, however, that the LP solution may require hours of computing time even on the fastest machines. To avoid this, SNO takes advantage of certain characteristics of the initial system to substantially reduce the size of the LP problem and minimize search time.
The resulting LP problem is then solved using a LP solver. This methodology results in an order of magnitude decrease in the solution time and enables SNO users to perform real-time what-if analysis on the entire system as opposed to batch type analysis that could take hours at a time.
Constraint Propagation Search
Although LP techniques can produce excellent results at the higher levels of planning, they are usually unsuitable at the lower levels of planning.
This is due to the fact that optimization at the lower levels of planning revolves heavily around non-linearity and the sequencing of discrete events that cannot be effectively represented as continuous flows.
Discrete event optimization problems are in general intractable, meaning that the computation time required to obtain the optimal solution grows exponentially as the problem size grows.
Therefore, exact solutions to even small optimization problems might require hours of computation, and larger problems are practically impossible to solve exactly.
“Eyelit Technologies’ optimization technology is based on OR and AI technology to deliver the best result possible as fast as possible.”
As a result, the objective of the optimization at this level is to find a feasible solution that is as close as possible to optimal.
Many heuristics have been developed in the recent years that attempt to improve the solution quality on these types of optimization problems. Some of these heuristics such as simulated annealing, and genetic algorithms have gained much popularity because of their success in certain areas and are offered in most planning systems as the only methods of choice.
These algorithms attempt to search the solution space based on a trial and error approach, trying to improve the quality of the solution at each step. In general, this type of unconstrained search will lead to a substantial overhead in run time due to the fact that many of the steps in such algorithms are redundant and will fail to improve the quality of the solution.
Eyelit Technologies’ heuristic optimization approach, which is fundamentally based on Constraint Propagation, reduces the search space at every step and therefore converges to the optimal solution in much faster time that achieved by genetic algorithms or simulated annealing.
Solving the Eight Queen Problem
The Eight Queen problem in chess is a good example of how effective constraint propagation can be in speeding up the solution convergence. The objective of the Eight Queen problem is to place eight queens on the chess board in a way that no two queens can strike each other.
Figures 1 through 3 show the simplified 3 queen problem on a 4X4 chess board and how constraint propagation helps speed up the solution convergence.
As the first move we choose to place the first queen in the upper left square. If we were to solve this problem using an approach such as genetic algorithm or conventional search techniques, the second move could place a queen anywhere on the chessboard. This type of trial and error approach could lead to many unsuccessful trials before an acceptable move is found.
Figure 1. Place First Queen in Upper Left Square
A constraint propagation based algorithm will first eliminate all unacceptable moves after every step. In the three Queen problem, the first move will result in the elimination of the top row, the leftmost column and all the squares on the diagonal passing through the top left square. Having the search space reduced, the second step of the algorithm will only try one of the remaining six squares.
Figure 2. Search Space is Reduced After the First Move
After placing the second queen on the board, once again, new constraints are propagated, further reducing the search space. In this particular example, the search space is reduced to a single point after the second move, leaving one acceptable square on the board.
Figure 3. Search Space is Reduced to One Square After the Second Move
Constraint propagation techniques can also lead to drastic reduction in solution time for solving scheduling and sequencing problems. Eyelit Technologies Applications’ proprietary heuristics utilize this technique to produce scalable solutions outperform other approaches by more than an order of magnitude.
Unified Data Model
It is a well known fact that in a planning problem, the sum of local optimums is not equal to the global optimum. This means that optimizing supply chain network, sourcing, supply chain plan, shop floor plan, demand plan, etc., cannot be performed in isolation.
Meaningful optimization can only be performed if all aspects of the planning problem that affect enterprise objectives are considered at the same time.
Eyelit Technologies Applications’ Unified Data Model lays ground for a fundamentally sound optimization strategy which avoids the trap of local optimums and allows the enterprise objectives to permeate into all aspects of planning down to shop floor events.
High level objectives when propagated to the lower levels will also further constrain the solution at lower levels of planning. The outcome is similar to that of constraint propagation, i.e. at the lower levels of planning the search space is reduced by the propagation of the constraints at the higher levels.
Therefore, as a side benefit the solution time for the lower level planning problems is reduced due to the visibility into the constraints at higher levels of planning.
Data Representation
There are many instances where data representing one form of production is only slightly different from another. Most planning applications are unable to take advantage of the similarities between processes, routings, operations, etc.
Eyelit Technologies’ object data model is design to maximize data reuse by allowing different production processes to be defined using shared objects.
For example, if a process is only different from another in a few operations, “operation overrides” can be used to represent the new process without having to redefine the entire set of operations.
Also, routes can be broken into segments. A new route may only be different from an existing route in one segment, therefore, only that segment of the route has to be redefined.
Data reuse can lead to a much more compact data storage that requires considerably less memory. Smaller memory requirements also lead to faster execution times.
Additionally, Eyelit Technologies Applications constraint propagation heuristics take advantage of route segments to speed up the search by allowing partial backtracking within a route as opposed to backtracking all the way to the start of a route.
The combination of compact data storage and algorithmic efficiencies based on Eyelit Technologies Applications’ data representation can lead to significant improvements in total solution time.
“Meaningful optimization can only be performed if all aspects of the planning problem that affect enterprise objectives are considered at the same time.”