Simulation And Optimization Are Not The Same
JeanFrancoisPuget 2700028FGP Comments (2) Visits (21890)
Selling optimization to happy users of simulation technology can be a tough nut to crack. Here is an example I find quite effective at opening eyes.
Before diving into it let me start with a disclaimer. I am not trying to show that optimization is superior to simulation, nor am I trying to undermine the value of simulation. I simply want to make clear that simulation and optimization are two different things, each with its own value. There are cases where optimization is a better fit, as shown below. There are also cases where simulation is a better fit. Go ask simulation people for these. And there are cases where both simulation and optimization can be used together. If you can't wait for the post where I will discuss how to use simulation and optimization together you can read this nice paper. It describes how the Mexico Central Bank developed a trade settlement system that leverages simulation and ILOG CPLEX. They won the Edelman Award for this.
So, here is the example. It is drawn from a real use case for a semi conductor plant. This plant takes as input silicon wafers and outputs chips. In order to produce chips, wafers need to go through various machines that basically print chips on them. For the sake of this discussion, it is sufficient to know that a sequence of operations has to be performed for each wafer. Each operations can be performed on a set of machines. Wafers move from machines to machines as operations are performed. At various points in the plant. wafers are waiting for their next operation. This is called WIP (Work In Progress).
When we approached this customer they were using a manufacturing execution system that uses rules to dispatch WIP to machines. In order to change the way the plant was operated they needed to change thee rules. This is where simulation kicked in. One way to optimize the plant efficiency is to evaluate alternate dispatching rules and select the one leading to best performance. This evaluation can be done by simulating the plant, and observing the result of using a given set of dispatching rules. With simulation of good quality it is possible to approximate the actual behavior of the plant quite closely. It means that simulation is a quite effective tool to evaluate and tune dispatching rules.
Let's use a very simple example to see how this works. We consider a plant with three machines. Wafers must be processed by machine 1 for a first operation, then by one of the two other machines for a second operation. These machines can process various wafer types, represented by colored circles in Figure 1. For instance Machine 2 can only process two of the three wafer types.
Figure 1. A three machines semi conductor plant
Assume that we start production with work in progress as shown in Figure 2.
Figure 2. Work in progress
A simulation practitioner creates a set of dispatching rules, and simulate their behavior. The practitioner has to create a behavioral model of the plant in order to simulate it. It is a model that can compute the state of the plant at time T+1 knowing the state of the plant at time T and the events that occur between T and T+1. In our example events are new wafers added to WIP, and operations completion by machines. In order to compute state at T+1 rules are triggered after each event, dispatching WIP to machines.
In our example we have two dispatching rules. A first rule assigns WIP to the first available machine. In case of tie between two available machines a second rule selects the less loaded machine. These rules would dispatch WIP evenly among available machines. For the sake of simplicity we assume that wafer processing time is one time unit for each machine.
Starting with WIP of Figure 2 these two dispatching rules yield the top row of Figure 3. The simulation of the plant yields the successive rows of Figure 3. Each row represents the status of the plant at successive time units. We see that the plant will use 5 time units to process the original WIP.
Figure 3. Simulated plant operations using dispatching rules
Optimization leads to a very different approach. Instead of a behavioral model, one needs to create a descriptive model. It is a model that lists production constraints, operations sequences, operation durations, etc. Each wafer is described by the complete sequence of operations that must be performed on it and their duration. The optimization problem is to assign each operation to one of the machines and to assign each operation a starting time such that all constraints are met. In addition we want to minimize the total processing time. Note that one could use alternate objective like maximizing throughput, or maximizing machine utilization rate. Constraints are numerous, here are few of them. A machine can only process one operation at a time. Operations must be executed in the specified order for a given wafer, WIP capacity is limited for each machine, etc. The result of optimization is a schedule that describes all operations, usually depicted as a Gantt chart. The Gantt chart shows the usage of machines over time. There is no need to run a simulation tool to see what will happen in the plant.
The Gantt chart for our example is shown in Figure 4. Only 4 time units are needed to process all wafers. This is better than the 5 time units needed when using dispatching rule simulation..
Figure 4. A Gantt chart.
In order to understand why the optimization solution is better here we can show the state of the plant at each time period, as in Figure 5.
Figure 5. Simulation of the plant using an optimized schedule
We can easily understand with the optimization solution is better here. It takes into account all wafers in the plant. It avoids assigning some wafers to Machine 3 in order to keep it available for the three wafers waiting for Machine 1.
One could argue that more complex dispatching rules are needed. For instance, a third rule could state that Machine 3 must be kept less busy in case green wafers would show up. This may improve the performance in the above case, but it could degrade it when there are no green wafers to be processed. One could say that with an even more complex set of dispatching rules the above case could be captured better. Indeed, one could imagine rules that look at WIP in front of the previous machine.
Truth is however that a real plant is much more complex. There are complex interaction between machines far apart in the processing flow. It is hopeless to capture these interactions with dispatching rules Optimization, by taking into account all WIP across all the plant, can come up with a global optimum.
So, what is it we can learn from this example? First, simulation and optimization lead to very different ways of tackling the problem. Simulation focus is on modeling the temporal behavior of the plant. Optimization focus is on capturing all dependencies and constraints. Second, the global view used by optimization leads to a global optimum when the local view used by simulation misses the global optimum. The use of dispatch rule simulation exhibits a myopic behavior.
Does it mean that optimization is always superior to simulation? Certainly not. The strength of optimization (global and complete view) is also its weakness. As soon as there is some unknown or some uncertainty simulation regains some value. For instance if operations durations on a given machine cannot be defined before hand then optimization isn't that useful.
I would summarize it as follow. Optimization is great when the system to be improved is well understood, i.e. when its behavior can be described analytically, using simple analytical functions (eg linear functions). Simulation is great when the system isn't understood correctly, or when unpredictable events can occur. Can we get the best of both? We can in some cases, watch this place for a forthcoming post about it.
Update on 23/07/201
As Charles Webster pointed out in a tweet, the above applies to human workflows. Replace each machine by a human, and wafers by, say, medical insurance claim. A first person could validate the claim, making sure that the form is filled correctly and that evidence is joined to it. Then the form is dispatch to a medical doctor. Some doctors have more specialized skills than others, hence some claims can only be processed by them. Our example show that assigning claims to doctors as they come may not lead to efficient claim processing. Optimization could lead to better processing by taking into account all claims in queue and doctor skills.